Типові класи задач дослідження операцій

Задачі керування запасами. Це один з найпоширеніших та доб­ре вивчених класів задач. Вони мають такі особливості. Із збільшен­ням рівня запасів підвищуються витрати на їхнє зберігання, але зме­ншуються втрати внаслідок можливого дефіциту.

Задачі керування запасами характеризуються такими елементами: системою постачання, попитом на предмети постачання, способами поновлення запасів, функцією витрат, обмеженнями, стратегіями ке­рування запасами.

Системи постачання поділяються на децентралізовані та центра­лізовані. Попит на предмети постачання буває стаціонарним або не­стаціонарним, детермінованим або випадковим.

Розрізняють такі способи поповнення запасів: миттєва поставка (коли нехтують затримкою часу і моменту оформлення замовлення на поставку до моменту самої поставки); затримка поставки на детермі­нований проміжок часу; затримка поставки на випадковий інтервал.

Функція витрат являє собою критерій ефективності обраної страте­гії керування запасами і включає такі складові: витрати на зберігання запасів, вартість поставки, втрати (штрафи) внаслідок дефіциту.

Найпоширенішими в задачах керування запасами є такі обмежен­ня: на максимальний обсяг (рівень) запасів на складах, на максима­льну вартість запасів, на число поставок, на вартість поставки, на ймовірність дефіциту і т. п.

Задачі розподілу ресурсів. Вони виникають, коли є повний набір робіт, які потрібно виконати, а наявних ресурсів для виконання кож­ної роботи найкращим чином не вистачає.

Залежно від умов задачі розподілу ресурсів поділяються на такі групи.

Задано як роботи, так і ресурси. Розподілити ресурси поміж робота­ми так, щоб максимізувати певний критерій ефективності (наприклад, прибуток) або мінімізувати очікувані витрати (виробничі втрати).

Приклад. Відомі виробничі завдання та виробничі потужності підприємства. При існуючих різних способах виготовлення виробів (наприклад, обробка на різних верстатах) обмеження потужностей не дає змоги для кожного виробу використати найкращу технологію. Які способи виробництва потрібно вибрати, щоб виконати завдання з мінімальними витратами?

Задано лише наявні ресурси. Визначити, який склад робіт можна виконати з цими ресурсами, щоб забезпечити максимум деякої міри ефективності.

Приклад. Задано підприємство з певними виробничими, матеріаль­ними та трудовими ресурсами. Вибрати такий асортимент виготовлюваної продукції, який забезпечить максимальний прибуток.

Задано лише роботи, які потрібно виконати. Підібрати такі ресурси, що дають змогу виконати їх з мінімальними виробничими витра­тами.

Приклад. Відомий місячний розклад руху пасажирських літаків авіалініями. Яка кількість екіпажів потрібна, щоб виконати план пере­везень з мінімальними експлуатаційними витратами?

Задачі ремонту та заміни обладнання. Ці задачі виникають у тих випадках, коли устаткування з часом спрацьовується, старіє і підлягає ремонту або повній заміні.

Зношене обладнання може підлягати в деякі моменти часу ремонту, який підвищує його ефективність до певної величини або повній заміні. З кожним ремонтом пов'язані витрати відповідні витрати. Потрібно визначити строки відновлювальних ремонтів, їхню кількість, а також момент заміни старого обладнання модернізованим, за яких мінімізуються середні витрати на ремонт та заміну обладнання за весь період його життєвого циклу.

Існує і таке обладнання, в якому деталі повністю виходять з ладу, не відновлюються і підлягають заміні (наприклад, радіодеталі, кон­денсатори, транзистори тощо). Постановка задачі ремонту та заміни у цьому випадку така.

Для виявлення можливих несправностей потрібно визначити строки профілактичного контролю, за яких мінімізується сума витрат на проведення контролю та очікуваних витрат від простою облад­нання через вихід з ладу (зіпсування) деталей в інтервалі між сусідні­ми моментами контролю.

Задачі масового обслуговування. Вони пов'язані з досліджен­нями та аналізом систем обслуговування з чергами заявок. З явищем виникнення черг доводиться стикатися у виробничій практиці та по­всякденному житті. Типовими прикладами є черги клієнтів в ательє побутового обслуговування; абонентів, які чекають виклику на міжміській АТС; покупців біля кас універмагу тощо.

Черги виникають через те, що потік заявок (абонентів) не керова­ний і випадковий, а кількість приладів обслуговування (злітно-посадкових смуг аеродрому, приймальників в ательє або касирів у магазині) обмежена. Якщо кількість приладів обслуговування взяти досить великою, то черги виникатимуть рідко і середній час чекання в черзі буде невеликим, проте неминучі тривалі простої приладів обслуговування. Якщо, навпаки, кількість приладів обслуговування мала, то виникають великі черги і мають місце великі витрати через чекання в черзі Тому одна з можливих задач масового обслуговування така: ви­начити таке число приладів коли мінімізується сума очікуваних втрат від чекання в черзі та простоїв обладнання.

Задачі календарного планування. Вони ха­рактеризуються такими особливостями. Є множина деталей (робіт), що підлягають обробці, на деякій множині верстатів. Задано технологічні маршрути обробки деталей, які назначають порядок проходження верстатів. У загально­му випадку для різних деталей технологічні маршрути неоднакові.

Оскільки одночасно обробляти на верстаті більш як одну деталь не можливо, то біля окремих верстатів утворюються черги.

Потрібно визначити такі черговості обробки деталей на кожному верстаті, для яких оптимізується певний критерій оптимальності, напри­клад, загальна тривалість всього комплексу робіт. Така задача і зветься задачею календарного планування (КП) або складання роз­кладу, а вибір черговості запуску деталей в обробку — упорядкуван­ням.

Найчастіше в задачах календарного планування використовують­ся такі критерії.

Мінімізація загальної тривалості робіт, тобто інтервалу між мо­ментами початку першої операції та закінчення останньої операції для останньої деталі.

Мінімізація сумарних штрафів (втрат) через запізнення.

Мінімізація загальною запізнення.

Мінімізація максимального запізнення.

Максимізація завантаження верстатів.

Задачі календарного планування належать до комбінаторних задач. Загальна кількість можливих варіантів розкладів у загальній задачі для m верстатів та n деталей. Тому для розв'язання таких задач послуговуються, в основному, наближе­ними евристичними методами, за вийнятком окремих випадків, задачі для т = 1; т = 2 та т = 3.

Задачі сітьового планування та керування. У цих задачах розгля­дають співвідношення між строком закінчення певного комплексу опе­рацій, з яких він складається, і моментами початку виконання всіх опе­рацій комплексу. Вони актуальні при розробці складних проектів.

Для строгої постановки цих задач необхідні такі умови:

- наявність точно визначеної множини операцій, які потрібно вико­нати для закінчення всього комплексу, що включає ці операції як свої складові;

- множина операцій комплексу (проекту) упорядкована так, що для кожної з них відомо, які операції безпосередньо їй передують, а які безпосередньо слідують за нею;

- в межах заданого відношення порядку операції можна починати і закінчувати незалежно одну від одної;

- відомий взаємозв'язок між величиною використованого ресурсу та тривалістю кожної операції.

Задачі планування та розміщення об'єктів. Ці задачі характе­ризуються такими особливостями. На території деякого регіону зада­но вихідне розміщення наявних об'єктів (наприклад, споживачів про­дукції та складів) і потрібно визначити кількість нових об'єктів та місця їх розміщення з урахуванням їхньої взаємодії із наявними та між собою, таким чином, щоб оптимізувати деякий критерій ефек­тивності. Розглянемо основні показники та характеристики цих за­дач. До них належать:

а) характеристики наявних та нових об'єктів;

б) характер взаємодії між ними;

в) тип простору рішень (розміщень);

г) міра відстані між об'єктами (метрика простору розміщень);

д) критерій оцінки варіантів рішень.

Одним з основних показників, що характеризують нові об'єкти, є їхня кількість. Крім того, залежно від розмірів, кожний новий об'єкт

можна розглянути або як точку, або як простягнений об'єкт. В останньому випадку керуючою змінною є форма об'єкта або форма займаємої їм площини, а задача зводиться до задачі планування роз­міщення. Щодо наявних об'єктів, то вони також, в залежності від розмірів, можуть розглядатися як точкові або як протяжні об'єкти.

Крім того, розміщення може бути статичним або динамічним, де­термінованим або стохастичним. Якщо розміщення наявних об'єктів є керованою змінною, то виникає задача перепланування (розміщен­ня).

Міра відстані (метрика простору розміщень) також має врахову­ватися при формулюванні задач розміщення.

Часто як наближену оцінку фактичних відстаней використовують евклідову відстань. Можливі різні критерії оптимальності: мініміза­ція сумарних витрат, мінімізація максимальних витрат, максимізація деякого прибутку. Взаємодія нових і наявних об'єктів може бути:

а) такою, що залежить від розміщення, і незалежною від нього;

б) статичною або динамічною;

в) детермінованою або стохастичною.

Простір розв'язків може бути неперервним, коли нові об'єкти можуть бути розміщені в будь-якій його точці, та дискретним, коли задано лише кінцеву множину точок, де можливе розміщення нових об'єктів. Розглянемо деякі типові постановки задач розміщення.

Задачі про покриття. До цього типу належить, зокрема, задача ви­значення місць розміщення складів при обмеженні, що відстань від складу до кожного споживача, якого він обслуговує, не перевищує 50 км, або задача розміщення пожежних команд, таким чином, щоб відстань до будь-якої точки міста була подолана відповідною пожеж­ною командою не більш як за 10 хв.

Задачі транспортного типу (або вибору маршрутів перевезень). Такі задачі найчастіше зустрічаються при дослідженні різноманітних процесів на транспорті та в системах зв'язку. Типовою задачею є за­дача знаходження деякого маршруту проїзду з міста А в місто В при наявності декількох маршрутів через різні проміжні пункти (міста). Вартість проїзду за обраним маршрутом відома, потрібно визначити найбільш економічний маршрут згідно з обраним критерієм оптима­льность На допустимі маршрути може бути накладено ряд обмежень. Так, наприклад, може заборонятися повернення до вже пройденого пункту або вимога обходу усіх пунктів транспортної мережі за умо­ви, що в кожному пункті можна побувати лише один раз (задача комівояжера).

Часто вводять обмеження на пропускні здатності комунікацій.

Комбіновані задачі.Досить часто практичні задачі дослідження операцій містять декілька розглянутих вище типових задач одночасно. Такі задачі є комбінованими. Наприклад, при плануванні керування ви­робництвом часто доводиться розв'язувати такий комплекс задач.

Скільки виробів кожного типу потрібно випустити та які оптимальні розміри партій (типова задача планування виробництва).

Як розподілити одержані виробничі замовлення по типах облад­нання (станкам) після того, як визначено оптимальний план вироб­ництва (типова задача розподілу ресурсів).

В якій послідовності і коли слід виконувати виробничі замовлен­ня (типова задача календарного планування).

Оскільки ці три задачі не можна вирішувати ізольовано, незалеж­но одну від одної, то можливий такий підхід до вирішення комбіно­ваної задачі.

Спочатку одержують оптимальний розв'язок задачі планування виробництва. Потім, залежно від цього оптимуму, знаходять най­кращий розподіл обладнання. Нарешті, на основі такого розподілу складають оптимальний графік виконання робіт.

Однак, така послідовна оптимізація часткових задач не завжди приводить до оптимального розв'язку задачі в цілому. Поки що не знайдено метод, який би дав змогу отримати одночасний оптимум для усіх трьох задач, а можливо він і зовсім не існує для конкретних задач. Тому для розв'язання подібних комбінованих задач викорис­товують метод послідовних наближень, який дає можливість наблизитися до шуканого розв'язку комбінованої задачі якомога ближче.

Вище наведена класифікація задач дослідження операцій звичай­но не є вичерпною і остаточною. З часом деякі класи задач об'єднуються і стає можливе їхнє спільне розв'язання, крім того з'являються нові класи задач.