Методи математичного програмування
Лінійне програмування
Економічні завдання, що розв’язуються із застосуванням лінійного програмування, характеризуються альтернативністю розв’язків і певними обмежуючими умовами. Розв’язати таке завдання – означає вибрати з альтернативних варіантів кращий, оптимальний.
У загальному випадкові математична модель оптимізаційного завдання має вигляд
тах (тіп): Z = Z(Х), за умови, що f(X) > < bi.
Якщо цільова функція та функції, що входять до системи обмежень, лінійні, то така задача називається задачею лінійного програмування. Якщо ж цільова функція або система обмежень нелінійна, така задача називається задачею нелінійного програмування.
За внесок у створення теорії лінійного програмування академік Л.В. Канторович був нагороджений Нобелівською премією з економіки. Лінійне програмування об’єднує методи розв’язання завдань, які описуються лінійними рівняннями:
1) складання оптимального плану виробництва;
2) вибір структури інвестицій;
3) раціональний розподіл матеріалів;
4) складання розкладу;
5) маршрутизація перевезень;
6) визначення мінімальної вартості кормових раціонів при заданій
кількості кормів.
Динамічне програмування
Методи динамічного програмування застосовуються при розв’язанні задач оптимізації, в яких цільова функція або обмежена, або характеризується нелінійними залежностями. Ознаками нелінійності є, зокрема, наявність змінних, у яких показник ступеня відрізняється від одиниці, а також наявність змінної в показнику ступеня, під коренем, під знаком логарифму.
Приклади нелінійних залежностей доволі різноманітні. Наприклад, економічна ефективність виробництва зростає або знижується непропорційно до змін масштабів виробництва; величина витрат на виробництво продукції зростає у зв’язку зі збільшенням обсягів продукції, але не пропорційно їм. Це пов’язано з тим, що витрати поділяються на змінні та постійні.
Для розв’язання задач лінійного та нелінійного програмування використовуються персональні комп’ютери.
Теорія ігор як метод дослідження операцій – це теорія математичних моделей прийняття оптимальних рішень в умовах невизначеності або конфлікту декількох сторін, що мають різні інтереси і для досягнення своїх цілей користуються різними шляхами. Основними поняттями теорії ігор є поняття конфлікту, кроку (ходу), стратегії.
Конфлікт – це явище, про яке доцільно з’ясувати: хто і як бере в ньому участь, які його можливі наслідки, хто є зацікавленим у тих наслідках, у чому ця зацікавленість проявляється і т. ін. Усі ці дані повинні бути записані у вигляді найпростіших математичних співвідношень.
Учасники, які беруть участь у конфлікті, називаються гравцями. Під грою розуміють таку послідовність дій (ходів) гравців (їх, як правило, позначають А, В, С, ...), яка здійснюється відповідно до чітко сформульованих правил, які враховують усі можливі ситуації, що можуть трапитися. Вважається, що інтереси гравців піддаються кількісному опису, тобто задаються певними числами.
Ходом гравця називається вибір однієї з можливих, згідно з правилами гри, дії та її здійснення.
Стратегією гравця називається план, що показує, який вибір він буде здійснювати в будь-якій можливій ситуації і при будь-якій можливій фактичній інформації.
Рішення, які приймаються за допомогою теорії ігор, корисні при складанні планів в умовах можливих протидій конкурентів або невизначеності у зовнішньому середовищі. При цьому визначаються наступні умови гри: правила гри і кількість учасників, можливі стратегії гравців та можливість отримання вигоди.
Завданням теорії ігор є розроблення рекомендацій гравцям, тобто визначення для них оптимальних стратегій. Під оптимальною стратегією розуміють таку стратегію, яка при багатократному повторенні забезпечує гравцю максимально можливий середній виграш.
Залежно від цілей гри і її характеру допускається така умовна класифікація:
1) за кількістю гравців, які беруть участь у грі:
- гра двох осіб;
- гра трьох осіб і т. д.;
2) за кількістю стратегій:
- задачі із кінченою кількістю стратегій;
- задачі з нескінченою кількістю стратегій;
3) за властивостями цільової функції гри:
- ігри з нульовою сумою;
- ігри з ненульовою сумою;
4) за попередньою домовленістю відносно можливих дій:
- кооперативні (з деякими домовленостями);
- некооперативні (без будь-яких домовленостей);
5) за кінцевим результатом:
- антагоністичні (перемога однієї сторони неминуче призводить до поразки іншої сторони);
- матричні (набір стратегій обмежений).
Розглянемо гру, в якій беруть участь два гравці, один із яких може вибрати стратегію і із п своїх можливих стратегій (і = 1, 2, ..., п), другий, не знаючи вибору першого, вибирає стратегію j із своїх можливих стратегій (j = 1, 2, ..., т). У результаті перший гравець (А) виграє аіj, а другий (В) програє цю величину.
Величини аіj утворюють платіжну матрицю (матрицю гри):
В1 ... Вт
А1 а11 ... а1т
А2 а21 ... а2т
[аіj] = ... ... ...
Ап ап1 ... апт
Рядки матриці [аіj] відповідають стратегіям (А1, А2, ..., Ап) гравця А, а стовпці – стратегіям (В1, В2, ..., Вт) гравця В. Дані стратегії називаються чистими. Будемо вважати, що при аіj > 0 гравець А виграє, а гравець В програє величину аіj. Якщо аіj < 0, то, навпаки, виграє гравець В і програє гравець А.
Спочатку знайдемо найкращу із стратегій гравця А, тобто найкращу серед А1, А2, ..., Ап з урахуванням можливих відповідей на неї гравця В. При цьому потрібно розраховувати на те, що на довільну стратегію Аі гравець В відповість стратегією Вj, для якої виграш гравця А виявиться мінімальним. Для знаходження стратегії Вj необхідно в і-му рядку платіжної матриці знайти бі = тіп аіj. При зміні стратегій гравця А одночасно будуть змінюватися відповідні їм числа бі. Зрозуміло, що гравцеві А вигідно завжди спинитися на такій стратегії Аі, для якої значення б = тах бі, або, враховуючи значення бі, одержимо б = тах тіп аіj.
Число б називається нижньою ціною гри або максиміном, а відповідна його стратегія (рядок) – максимінною.
Якщо гравець А буде дотримуватись максимінної стратегії, то йому, при довільній поведінці гравця В, у будь-якому випадкові гарантований виграш не менший від б.
Аналогічно можна визначити найкращу стратегію гравця В, мета якого – привести виграш гравця А до мінімуму. Для цього гравець В прагне для кожної своєї стратегії Вj одержати максимальне значення виграшу при довільній стратегії гравця, тобто він шукає значення вj = maxi aij.
Проте гравець В не може розраховувати на те, що гравець А дозволить йому одержати будь-який із виграшів вj. Єдине, на що може розраховувати гравець В, то це на те, щоб одержати виграш, який буде не меншим за величину в = тіп тах аіj.
Величина в називається верхньою ціною гри, або мінімаксом, а відповідна йому стратегія гравця (стовпець) – мінімаксною. Мінімаксна стратегія є найобережнішою стратегією для гравця В, яка забезпечує йому в будь-якому випадку програш, не більший від б і відповідно виграш гравцеві А, так само не більший від в. Якщо б = в = v, то число v називається ціною гри.
Гра, для якої б = в, тобто мінімаксне значення рівне максимінному, називається грою із сідловою точкою. Для гри із сідловою точкою знаходження розв’язку полягає у виборі максимінної і мінімаксної стратегій, які є оптимальними. «Оптимальність» тут означає, що ні один гравець не прагне змінити свою стратегію, оскільки його суперник може на це відповісти вибором іншої стратегії, яка може дати гірший результат для першого гравця.
Узагалі значення гри повинно задовольнити нерівності:
[Максимінне [Значення [Мінімаксне
значення] £ гри] £ значення]
Покажемо застосування теорії ігор у формуванні виробничої програми підприємства. ДП «Веселка» виготовляє продукцію двох видів: кухонні комбайни та міксери, збут яких залежить від обсягів виробництва аналогічної продукції конкуруючим підприємством. Затрати на виробництво і збут одного кухонного комбайна становлять 360 грн., міксера – 120 грн., а ціна реалізації одиниці продукції дорівнює відповідно: 480 грн. та 190 грн. При виборі підприємством-конкурентом стратегії С ДП «Веселка» може реалізувати протягом місяця 200 кухонних комбайнів та 340 міксерів; при виборі підприємством-конкурентом стратегії Д – 180 кухонних комбайнів і 390 міксерів. Необхідно знайти оптимальну стратегію випуску продукції з урахуванням зовнішніх факторів, при якій підприємство отримає середній прибуток незалежно від стратегії підприємства-конкурента.
Підприємство може приймати дві стратегії: організувати випуск продукції в розрахунку на стратегію С підприємства-конкурента (стратегія А) або в розрахунку на його стратегію Д (стратегія В).
Якщо ДП «Веселка» прийме стратегію А, то його прибуток при виборі підприємством-конкурентом стратегії С становитиме:
200´(480-360) + 340´(190-120) = 24000 + 23800 = 47800 грн.
При стратегії Д підприємства-конкурента ДП «Веселка» буде здійснювати свою стратегію В, маючи прибуток:
180´(480-360) + 390´(190-120) = 21600 + 27300 = 48900 грн.
Якщо ДП «Веселка» буде поперемінно використовувати то стратегію А, то стратегію В, то така стратегія називатиметься змішаною, а її елементи А і В – чистими стратегіями.
Якщо гравець Р1 (ДП «Веселка») прийме оптимальну змішану стратегію, то незалежно від стратегії гравця Р2 (підприємство-конкурент) він повинен отримати однаковий середній прибуток.
Позначимо частоту використання гравцем Р1 стратегії А через f, тоді частота використання ним стратегії В буде рівна (1-f). Визначимо середній прибуток за формулою
47800f = 48900 (1-f);
47800f = 48900 - 48900f;
96700f = 48900;
f = 48900¸96700 = »0,5057.
1-f = 47800¸96700 = »0,4943.
При стратегії С гравця Р2 середній прибуток ДП «Веселка» буде становити :
47800´(48900¸96700) = 24172 грн.
При стратегії Д гравця Р2 середній прибуток підприємства становитиме:
46900´(1 - 48900¸96700) = 48900´(47800¸96700) = 24172 грн.
Отже, гравець Р1, використовуючи чисті стратегії А і В у співвідношенні 489 : 478, буде мати оптимальну змішану стратегію, що забезпечить йому середній прибуток у сумі 24172 грн. незалежно від стратегії підприємства-конкурента.
Нарешті, визначимо оптимальні обсяги випуску продукції:
(200+340)´48900¸96700 + (180+390)´47800¸96700 =
= ((200´48900 + 180´47800) + (340´48900 + 390´47800)) ¸
¸ 96700 = (183840000 + 352680000) ¸ 96700 = 190 + 365.
Отже, оптимальна стратегія ДП «Веселка» означає випуск 190 кухонних комбайнів і 365 міксерів. Тоді при будь-якій стратегії підприємства-конкурента воно отримає середній прибуток у сумі 24172 грн.
