Опорний конспект лекцій з курсу Дослідження операцій Тема 2 Методи відшукання оптимальних розв’язків в задачах ДО, НУДПСУ

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

План

1. Основні методи відшукання оптимальних розв'язків.

2. Задачі теорії масового обслуговування.

3. Задачі мережевих моделей планування і управління.

4. Задачі, що вирішуються методом імітаційного моделювання.

5. Обмеження методу імітаційного моделювання.

6. Поняття оптимізаційної задачі. Її найзагальніший математичний вигляд. Нерозв'язність оптимізаційної задачі.

7. Задача лінійного програмування, її характерні риси.

8. Канонічна форма задачі лінійного програмування.

1.4. Методи відшукання оптимальних розв’язків в задачах ДО. Класифікація методів

До основних методів відшукання оптимальних розв'язків відносяться:

• математичне програмування. У свою чергу методи математичного програмування поділяються на наступні:

• лінійне програмування;

• нелінійне програмування;

• динамічне програмування;

• цілочисельне програмування;

• стохастичне програмування;

• евристичне програмування;

• теорія масового обслуговування;

• мережеві моделі планування і управління;

• імітаційне моделювання.

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

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

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

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

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

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

З використанням мережевих моделей планування і управління можна вирішувати:

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

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

• задачі мережевого планування.

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

1) потрібна наявність висококваліфікованих фахівців, оскільки він містить в собі елементи всіх вище перелічених методів;

2) розв'язок обходиться дорожчим, ніж при використанні інших методів.

2. ЛІНІЙНЕ ПРОГРАМУВАННЯ

Часом народження лінійного програмування прийнято вважати 1939 р., коли була надрукована брошура Л.В.Канторовича «Математичні методи організації і планування виробництва». Оскільки методи, що викладені Л.В.Канторовичем, були мало придатні для ручного рахунку, а швидкодіючих обчислювальних машин у той час не існувало, робота Л.В.Канторовича залишилася майже не відміченою.

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

Американський математик А.Данциг в 1947 році розробив вельми ефективний конкретний метод чисельного розв'язку задач лінійного програмування (він отримав назву симплекс-методу). Ідеї лінійного програмування протягом п'яти-шести років набули грандіозного поширення в світі, і імена Купманса і Данцига сталі всюди широко відомі.

Своє друге народження лінійне програмування отримало на початку п'ятдесятих років з появою ЕОМ. Тоді почалося загальне захоплення лінійним програмуванням, що викликало у свою чергу розвиток інших розділів математичного програмування. У 1975 році академік Л.В.Канторович і американець професор Т.Купманс отримали Нобелівську премію з економічних наук за «внесок в розробку теорії і оптимального використання ресурсів в економіці».

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

У найзагальнішому вигляді задача математично записується таким чином

Z = f(х)→max, хÎW,                                                                        (2.1)

де х = (x₁, x₂,..., x_n);

W – область допустимих значень змінних x₁, x₂,..., x_n;

f(х) – цільова функція.

Для того, щоб вирішити задачу оптимізації, досить знайти її оптимальний розв'язок, тобто вказати х_*ÎW таке, що f(х_*) ³ f(х) при будь-якому хÎW.

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

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

2.1. Задача лінійного програмування

Лінійне програмування є найбільш простим і краще всього вивченим розділом математичного програмування. Характерні риси задач лінійного програмування наступні:

1) показник оптимальності f(х) є лінійною функцією від елементів рішення x = (x₁, x₂,..., x_n);

2) обмежувальні умови, що накладаються на можливі розв'язки, мають вид лінійних рівностей або нерівностей.

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

При цьому система лінійних рівнянь (2.3) і нерівностей (2.4), (2.5), що визначає допустиму множину розв'язків задачі W, називається системою обмежень задачі лінійного програмування, а лінійна функція f(х) називається цільовою функцією або критерієм оптимальності.

У окремому випадку, якщо I = Ø, то система (2.3) – (2.4) складається тільки з лінійних нерівностей, а якщо I = M, то – з лінійних рівнянь.

При описі реальної ситуації за допомогою лінійної моделі слід перевіряти наявність у моделі таких властивостей, як пропорційність і адитивність. Пропорційність означає, що внесок кожної змінної в цільовій функції і загальний об'єм споживання відповідних ресурсів повинні бути прямо пропорційні величині цієї змінної. Наприклад, якщо, продаючи j-й товар в загальному випадку за ціною 100 рублів, фірма робитиме знижку при певному рівні закупівлі до рівня ціни 95 рублів, то буде відсутня пряма пропорційність між доходом фірми і величиною змінної x_j. Тобто в різних ситуаціях одна одиниця j-го товару приноситиме різний дохід. Адитивність означає, що цільова функція і обмеження повинні бути сумою внесків від різних змінних.

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

Допустимий розв'язок – це сукупність чисел (план) x = (x₁, x₂,..., x_n), що задовольняють обмеженням задачі.

Оптимальний розв'язок – це план, при якому цільова функція приймає своє максимальне (мінімальне) значення.

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

Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування в канонічній формі. Для цього в загальному випадку потрібно уміти зводити задачу максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підкоряються умові позитивності. Максимізація деякої функції еквівалента мінімізації тієї ж функції, узятої з протилежним знаком, і навпаки.

Правила приведення задачі лінійного програмування до канонічного вигляду полягають в наступному:

1)  якщо в початковій задачі потрібно визначити максимум лінійної функції, то слід змінити знак і шукати мінімум цієї функції;

2)  якщо в обмеженнях права частина негативна, то слід помножити це обмеження на – 1;

3)  якщо серед обмежень є нерівності, то шляхом введення додаткових ненегативних змінних вони перетворяться в рівність;

4)  якщо деяка змінна x_k не має обмежень по знаку, то вона замінюється (у цільовій функції і у всіх обмеженнях) різницею між двома новими ненегативними змінними: х_k = х¹_k – х_l, де l – вільний індекс х¹_k ³ 0, х_l ³ 0.

Приклад 2.1. Приведення до канонічної форми задачі лінійного програмування

minZ = 2х₁ + 3х₂ – х₃;

2х₂ – х₃ ≤ 5;

х₁ + х₂ – х₃ ³ – 1;

2х₁ – х₂ ≤ – 3;

х₁ ≤ 0, х₂ ³ 0, х₃ ³ 0.

Введемо в кожне рівняння системи обмежень вирівнюючі змінні x₄, x₅, x₆. Система запишеться у вигляді рівностей, причому в перше і третє рівняння системи обмежень змінні x₄, x₆ вводяться в ліву частину із знаком «+», а в друге рівняння вводиться x₅ із знаком «–».

2х₂ – х₃ + х₄ = 5;

х₁ + х₂ – х₃ – х₅ = – 1;

2х₁ – х₂ + х₆ = – 3;

х₄ ³ 0, х₅ ³ 0, х₆ ³ 0.

Вільні члени в канонічній формі повинні бути позитивними, для цього два останні рівняння помножимо на – 1

2х₂ – х₃ + х₄ = 5;

– х₁ – х₂ + х₃ + х₅ = 1;

– 2х₁ + х₂ – х₆ = 3;

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

х₁ = х¹₁ – х₇ де х₇ ³ 0.

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

minZ = 2х¹₁ + х₂ – х₃ – 2х₇,

2х₂ – х₃ + х₄ = 5;

– х¹₁ – х₂ + х₃ + х₅ + х₇ = 1;

– 2х¹₁ + х₂ – х₆ + 2х₇ = 3;

х¹₁ ³ 0, х_і ³ 0, і = 2,…,7.

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

1. Основні методи відшукання оптимальних розв'язків.

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

3. Задачі теорії масового обслуговування.

4. Задачі мережевих моделей планування і управління.

5. Задачі, що вирішуються методом імітаційного моделювання.

6. Які існують обмеження методу імітаційного моделювання?

7. Що таке оптимізаційна задача?

8. Як розуміти нерозв'язність оптимізаційної задачі?

9. Що таке задача лінійного програмування?

10. Які характерні риси задачі лінійного програмування?

11. Що таке система обмежень задачі лінійного програмування?

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

13. Навіщо потрібна перевірка наявності у моделі властивостей пропорційності та адитивності?

14. Що таке допустимий та оптимальний розв'язки задачі лінійного програмування?

15. Що таке канонічна форма задачі лінійного програмування?

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

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