Опорний конспект лекцій з курсу Дослідження операцій Тема 1 Загальні поняття, НУДПСУ

 ОПОРНИЙ КОНСПЕКТ ЛЕКЦІЙ З КУРСУ

«ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»

Лекція №1. ЗАГАЛЬНІ ПОНЯТТЯ. Мета і основні поняття в ДО. Основні елементи методу ДО. Основні задачі, вирішувані методом ДО. Класифікація задач

План

1. Поняття операції та розв'язку. Мета ДО.

2. Елементи розв’язку. Цільова функція.

3. Приклади задач ДО.

4. Основні задачі застосування методів ДО.

5. Специфічні риси методу ДО. Основні елементи операційного підходу. Основні етапи застосування методу ДО.

6. Типи задач ДО. Загальні методи їх розв'язку.

1. ЗАГАЛЬНІ ПОНЯТТЯ

1.1. Мета і основні поняття в ДО

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

Кожен певний вибір залежних від нас параметрів називається розв’язком.

Метою дослідження операцій є попереднє кількісне обгрунтування оптимальних розв’язків.

Ті параметри, сукупність яких утворює розв’язок, називаються елементами розв'язку.. Як елементи розв’язку можуть виступати різні числа, вектори, функції, фізичні ознаки і т.д.

Приклад: перевезення однорідного вантажу.

Існують пункти відправлення: А₁, А₂, А₃,…, А_m.

Є пункти призначення: В₁, В₂, В₃,…, В_n.

Елементами розв’язку тут будуть числа x_ij, що показують, яка кількість вантажів буде відправлена з i-того пункту відправлення в j-ий пункт призначення.

Сукупність цих чисел: x₁₁, x₁₂, x₁₃,…, x_1m,…, x_n1, x_n2,…, x_nm  утворює розв’язок.

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

Цей показник вибирається так, щоб він відображав цільову спрямованість операції. Вибираючи розв’язок, прагнемо, щоб даний показник прагнув до максимуму або до мінімуму. Якщо W – дохід, то W → max; а якщо W – витрата, то W → min.

Якщо вибір залежить від випадкових чинників (погода, відмова техніки, коливання попиту і пропозиції), то як показник ефективності вибирається середнє значення – математичне очікування – W.

Як показник ефективності іноді вибирають імовірність досягнення мети. Тут мета операції супроводжується випадковими чинниками і працює за схемою ТАК-НІ.

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

1) План постачання підприємства.

Показник ефективності видно в меті. R – число – вартість перевезень R→min. При цьому всі обмеження повинні бути виконані.

2) Споруда ділянки магістралі.

У завданні велику роль грають випадкові чинники. Як показник ефективності вибирають середній очікуваний час Т закінчення будівництва, тоді Т→min.

3) Вибірковий контроль продукції.

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

4) Військові дії.

Операція повинна бути спланована так, щоб знищити ворожий об'єкт. Як цільова функція – імовірність того, що відбудеться подія А (знищення), тобто Р(А)→1.

1.2. Основні елементи методу ДО

При розв'язку будь-якої конкретної задачі застосування методів ДО полягає в наступному:

• побудова математичних, економічних і статистичних моделей для задач ухвалення рішень і управління в складних ситуаціях в умовах невизначеності (наявність випадкових чинників);

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

Методи ДО мають ряд специфічних рис. Щоб підхід до розв'язку задач можна було вважати операційним, він повинен містити наступні елементи:

1. Орієнтація на ухвалення розв’язків. Основні результати аналізу повинні мати безпосереднє і повністю визначене відношення до вибору способу дій (стратегії або тактики);

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

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

4. Необхідність використання ЕОМ. Ця умова зовсім не є лише бажаною, вона скоріше необхідна. Це обумовлюється складністю використовуваних математичних моделей і великим обсягом початкових даних. Обчислення можуть бути громіздкими – необхідно використовувати ЕОМ; а можуть бути нескладними, але у великих обсягах (статистичні моделі).

Основні етапи застосування методу ДО:

1. визначення мети;

2. складання плану розробки проекту;

3. формулювання проблеми;

4. побудова моделі;

5. розробка обчислювального методу;

6. розробка технічного завдання на програмування, саме програмування і відладка програми;

7. збір даних;

8. перевірка моделі;

9. реалізація результатів, тобто ухвалення розв'язку.

1.3. Основні задачі, вирішувані методом ДО. Класифікація задач

Накопичений досвід в розв’язку задач ДО і його систематизація дозволили виділити наступні типи задач:

• задача управління запасами;

• задача розподілу ресурсів;

• задача ремонту і заміни устаткування;

• задача масового обслуговування;

• задача впорядковування;

• задача мережевого планування і управління (МПУ);

• задача вибору маршруту;

• комбіновані задачі.

1. Задача управління запасами

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

• сума очікуваних витрат на зберігання;
• сума втрат із-за дефіциту.

Залежно від умов, завдання управління запасами діляться на 3 групи:

а) моменти постачань або оформлення замовлень на постачання, поповнення запасів фіксовані. Визначити об'єми вироблюваної партії запасів або об'ємів запасів, що купуються;

б) об'єми вироблюваної партії запасів або об'ємів запасів, що купуються, партії запасів фіксовані. Визначити моменти оформлення замовлень на постачання;

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

2. Задача розподілу ресурсів

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

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

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

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

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

в) задані тільки роботи. Визначити, які ресурси необхідні для того, щоб мінімізувати сумарні витрати виробництва.

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

3. Задача ремонту і заміни устаткування

Виробниче устаткування з часом зношується і підлягає попереджувально-відновному ремонту. Устаткування також застаріває (морально і фізично) і підлягає повній заміні. При цьому постановка задачі така: визначити такі терміни ремонту і заміни устаткування, при яких мінімізується сума витрат на ремонт і заміну устаткування при його старінні. Іноді в устаткуванні виходять з ладу окремі елементи (наприклад, мікросхеми) – в даному випадку потрібно визначити такі терміни профілактичного ремонту по заміні деталей, що вийшли з ладу, щоб витрати на даний елемент були мінімальними.

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

4. Задача масового обслуговування

Дані задачі виникають там, де утворюється черга. З утворенням черги доводиться стикатися як у виробництві, так і в побуті (виробництво: черговість виконання замовлення; у побуті: магазин, поліклініка). Подібні задачі існують і на транспорті.

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

У даних задачах можлива наступна постановка: визначити, яка кількість каналів обслуговування необхідна, щоб звести до мінімуму сумарні витрати, пов'язані з невчасним обслуговуванням і простоєм каналів. Для розв'язку задач використовується теорія масового обслуговування.

5. Задача впорядковування

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

• мінімізація загальної тривалості робіт (тобто інтервалу часу між моментом початку першої операції і моментом закінчення останньої);
• мінімізація загального запізнювання. Запізнювання визначається як різниця між фактичним і плановим термінами обробки кожної деталі. Загальне запізнювання дорівнює сумі запізнювань за всіма деталями.

6. Задача мережевого планування і управління (МПУ)

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

• повинна існувати точно визначена кількість операцій;

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

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

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

Якщо всі умови виконані, то можливі наступні постановки задачі:

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

• мінімізуються загальні витрати на виконання всього комплексу операцій;

• визначається імовірність невиконання комплексу робіт у встановлені терміни;

• визначаються середньоквартальні відхилення необхідних ресурсів від готівки.

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

7. Задача маршрутизації

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

• забороняється повертатися у вже пройдений пункт;

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

Критерії оптимізації: мінімізація загального часу проходження маршруту або мінімізація загальних витрат.

Дані задачі найбільш вивчені і в літературі носять специфічні назви – задача про комівояжера або задача про максимальний потік.

8. Комбіновані задачі

Включають декілька типових задач одночасно.

Приклад: при плануванні і управлінні виробництвом необхідно вирішити комплекс задач:

1)  скільки виробів кожного найменування необхідно випустити і які оптимальні розміри партії виробів – задача планування виробництва;

2)  розподілити замовлення або деталі по видах устаткування, причому оптимальний план виробництва заданий – задача розподілу;

3)  визначити, в якій послідовності слід виконати виробничі замовлення – календарне планування.

Ці задачі не можна вирішувати незалежно одна від одної. Критерії ефективності цих задач часто суперечать один одному. Тому при розв'язку задач часто використовують наступні методи.

Метод послідовного наближення – за допомогою цього методу можна дуже близько підійти до оптимального розв'язку.

Метод імітаційного моделювання – заснований на методі Монте-Карло (використання випадкових чисел) і вимагає величезної кількості обчислень, оскільки розглядається дуже багато варіантів розв'язку.

Контрольні запитання

1. Що є метою дослідження операцій?

2. Що таке операція?

3. Що таке розв'язок?

4. Що таке цільова функція?

5. Подайте основні етапи застосування методів ДО при розв'язку будь-якої конкретної задачі.

6. Основні елементи операційного підходу.

7. Основні етапи застосування методу ДО.

8. Подайте типи задач ДО.

9. Сформулюйте задачу управління запасами.

10. Сформулюйте задачу розподілу ресурсів.

11. Сформулюйте задачу ремонту і заміни устаткування.

12. Сформулюйте задачу масового обслуговування.

13. Сформулюйте задачу впорядковування.

14. Сформулюйте задачу мережевого планування і управління (МПУ).

15. Сформулюйте задачу вибору маршруту.

16. Подайте приклад комбінованої задачі.

З повагою ІЦ “KURSOVIKS”!