Дослідження операцій

Матеріал з USIC Wiki
Перейти до: навігація, пошук
Для ФЕН

Ця стаття особливо стосується студентів ФЕН

Те що нас найбільше турбує

Симплекс - головне в нашому житті. Долі не існує
Дзен про симплекс

Ха! Дзену не існує
Доля про Дзен

Що воно збіса таке?

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

  • Цільова функція. Її треба мінімізувати (як ото витрати, кількість сплячих студентів, працю) або максимізувати (прибуток, корисність, час сну на парі, бал)
  • Обмеження. Це такі рівняння та нерівності, які обов'язково мають виконуватися.

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

Гарно розв'язана задачка має задовольняти два критерії

  • Критерій допустимості="ВСІ ОБМЕЖЕННЯ МАЮТЬ ВИКОНУВАТИСЯ!"
  • Критерій оптимальності="За даного рівня ВИКОНАННЯ ОБМЕЖЕНЬ! вже не можна знайти кращої точки"

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

Що ж, до бою!

Задача ЛП

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

На щастя, існують способи розвязати задачу ЛП; на жаль, вони досить складно реалізуються :-)

Найбільш популярним способом розвязування задач ЛП є симплекс-метод.

Приклад задачі ЛП:
Максимізувати 5x1+4x2
За умов

  • x1 ≤ 2
  • x1+x2 ≤ 3

Графічний метод

OR LessConstr.png

Обмеження типу "менше-рівне"

OR MoreConstr.png

Обмеження типу "більше-рівне"

УВАГА: МЕТОД РОЗВ'ЯЗУЄ ЛИШЕ ЗАДАЧІ ЛП ДЛЯ ДВОХ ЗМІННИХ (якщо Ви, звичайно, не оперуєте n-вимірними просторами усно)
УВАГА: Надалі розглядаємо лише випадок, коли всі змінні невід'ємні. Як цього досягти, читайте далі.


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

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

a * x1 + b * x2 ___ c

де замість нижнього підкреслення має стояти знак нерівності (або ж рівності).

Обмеження зі знаком нерівності (≤, ≥) на графіку мають вигляд півплощин. Будують їх просто: малюють пряму, що описується рівнянням обмеження, потім підставляють будь-яку точку (наприклад, початок координат) в обмеження, і якщо виходить правда (типу 13+15 ≤ 100), то замальовують півплощину з цією точкою, інакше замальовують іншу площину.

Обмеження зі знаком рівності виглядають як прямі (взагалі-то такі обмеження нетипові для задач ЛП з графічним розв'язком). Розв'язок, очевидно, перебуває на такій прямій.

Обов'язково позначайте кожну проведену лінію номером відповідного обмеження - потім легше роздуплятись інтерпретувати результати буде.

OR Optimum.png

Створений обмеженнями многокутник, вектор нормалі та позначений червоним оптимальний розв'язок. У роботах не забувайте також будувати лінії рівня.


Далі цікавіше. Після нанесення всіх обмежень на графік слід побудувати зону перетину цих обмежень. У цій зоні мають виконуватися ВСІ обмеження (в тому числі й НЕВІД'ЄМНІСТЬ змінних). Якщо тобі пощастило, у тебе вийде опуклий многокутник (а тобі завжди пощастить ). Варто зазначити, що одна з його вершин і є розв'язком задачі. Як же знайти цю заповітну вершину?

Наступне речення треба запам'ятати й використовувати в письмових роботах: "Побудуємо вектор нормалі цільової функції". Вектор нормалі будується дуже просто: на осі x1 відраховуємо стільки клітинок, скільки є коефіцієнтом при x2, а на осі x2 - стільки, скільки є коефіцієнтом при x1. Від центру координат до отриманої точки малюємо стрілочку-вектор. Стрілочка показує нам, в яку сторону зростає функція. Зауважте, саме ЗРОСТАЄ - тобто якщо в нас задача мінімізації, то рухатися треба в інший бік.

Після цього треба побудувати кілька ліній рівня. Лінії рівня - це лінії, на кожній з яких усі точки відповідають одному й тому ж значенню ц.ф. Це просто кілька прямих, перпендикулярних до вектора нормалі, їх варто намалювати олівчиком, або не сильно притискаючи ручку до паперу. Бажано намалювати ці лінії так щоб було видно логіку оптимізації - тобто з найвіддаленішої від оптимуму точки все ближче і ближче до оптимальної. Не слід малювати нормалі, які не проходять через жодну з точок перетину обмежень(кутів) - це зайвий геморо... морока. Тобто зайва.

Врешті-решт проведіть одну лінію через оптимальну точку (а може, й відрізок - і таке буває).

Далі йде найприємніша частина. Ми вже знайшли оптимальну точку, але ще не знаємо значень змінних та ц.ф. Тому дізнаємося, які обмеження є активними (це ті дві лінії, які перетинаються в оптимальній точці - а номерки-то ми вже проставили, тому визначити рівність буде легко). Активні обмеження виконуються як рівності (це має бути видко з малюнку), тому просто розв'язуємо систему рівнянь, отриманих із активних обмежень шляхом вилучення галочки < чи >. Voila! (для тих, хто не зрозумів - "Вуаля!"). Маємо значення змінних. Підставляємо в ц.ф., одержуємо її значення. Все! Розв'язок у нас в кишені.

А тепер про різне западло, яке, на жаль трапляється навіть в цьому методі.

  • Нескінченна кількість розв'язків
  • Необмежений розв'язок


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

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

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


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

Симплекс-метод

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

Тут ми не будемо заглиблюватися в більш детальне його описання, обмежимося лише тим, що варто знато на контрольній. Але не хвилюйтеся - і поверхового вивчення досить, щоб надовго оглушити й осліпити свідомість юного економіста.

Почнемо з переформулювання задачі ЛП.

Стандартна форма

Нехай у нас є така задача:

z(x) = 5*x1 + 4*x2 - 2*x3мінімізувати

за умов:

x1 + 2*x2 = 10        (1)
5*x2 - 3*x3 ≥ 50      (2)
2*x2 + x3 ≤ -2        (3)

Змінна x1 ∈ R - тобто вільна, інші - невід'ємні (≥ 0)


Щоб розв'язати її симплекс-методом, слід записати її в так званій стандартній формі. Стандартна форма полягає в наступному:

  1. Усі змінні НЕВІД'ЄМНІ
  2. Права частина (число) кожного обмеженяя - НЕВІД'ЄМНА
  3. Усі обмеження - РІВНОСТІ


З першим пунктом усе зрозуміло - зазвичай усі змінні невід'ємні за умовою (ну не буває на виробництві -2 чавунні болванки, самі знаєте). Якщо кілька змінних є недодатні, робимо заміну: нехай x`n = (-xn) Тоді x`n ≥ 0. Якщо вам не пощастило і кілька змінних є вільними, робимо дещо екзотичну заміну: нехай xv = (x+v - x-v). Відповідно, дві нові змінні невід'ємні. Далі просто розв'язуємо задачу з новими змінними. Не забудьте в кінці підставити все назад.

Застосуємо правило до нашої задачі: x1 = (x+1 - x-1). Маємо:

z(x) = 5*(x+1 - x-1) + 4*x2 - 2*x3мінімізувати
x+1 - x-1 + 2*x2 = 10


Тепер другий пункт (усі змінні вже невід'ємні!). Немає нічого простіше - просто домножаємо "погане" обмеження на -1 (так-так, знак нерівності також змінюється). Якщо чесно, бувають ситуації, коли цей крок робити не потрібно. Це стосується двоїстого симплексу

Для нашої задачі: перетворимо обмеження (3) на кошерне.

 -2*x2 - x3 ≥ 2        (3`)


Ну, і на десерт третій пункт. Припустимо, що у вас є обмеження

2x + 3y + 4z ≤ 5. 

Що це може означати? Можна сказати, що існує певна змінна-нестача t, така, що

2x + 3y + 4z + t = 5 

Нестача - тому що для виконання рівності як раз не вистачає t. Звідси й правило: якщо у нас є обмеження вигляду ≤, ми створюємо додаткову змінну sj (≥0), додаємо її в ліву частину обмеження і міняємо знак цього обмеження на "=".

Аналогічно можна вивести правило для обмежень вигляду ≥: створюємо додаткову змінну-надлишок Sj, додаємо її в ліву частину обмеження і міняємо знак цього обмеження на "=". Наша додаткова змінна буде базисною

Що ж, наша задача вимагає переписати обмеження (2) і (3). Додамо змінні-надлишки S1 та S2:

 5*x2 - 3*x3 - S1 = 50     (2`)
-2*x2 - x3 - S2 = 2        (3`)

Отже, кожну задачу ЛП можна записати в стандартній формі. Це дуже важливий крок, адже тільки задачі в стандартній формі піддаються розв'язку через симплекс-метод.

Базис

Базис, базис... Так, і що ж ми назвемо базисом?
Дж. Данціг

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

Тут ми відповімо на одвічне питання - що таке Базис?

Термін базис походить бозна-звідки і означає "система лінійно незалежних векторів".

В симплекс таблиці в нас є трохи більше змінних, ніж потрібно для однозначного розв'язку. Тому деякі ми називаємо небазисними і вони стають рівними 0 (магія, правда?). Решта має певне значення - і ми їх називаємо базисними.

Тепер кілька правил і законів:

  • Базисних змінних має бути стільки ж, скільки обмежень.
  • Кожна базисна змінна відповідає обмеженню.
  • Коефіцієнт при базисній змінній в своєму обмеженні - 1
  • Базисна змінна дорівнює правій стороні свого обмеження.
  • Коефіцієнт при базисній змінній не в своєму обмеженні - 0.
  • Коефіцієнт при базисній змінній в Z-рядку - 0.
  • Небазисні змінні =0.
Зверніть увагу Прикол в тому, що деякі базисні змінні також можуть дорівнювати нулеві - це називається виродженість, і це в певному сенсі дуже неприємно. Але не будемо забігати наперед
.

Все отак просто. Тепер зробимо маленьку задачку.

Z=x1+x2 ->max

За умов

2x1+x2 ≤ 4 (1)
x1+x2 ≥ 1 (2)
x2=2 (3)

Переведемо її в стандартну форму.

Z=x1+x2 ->max

За умов

2x1+x2+s1=4 (1)
x1+x2-s2=1 (2)
x2=2 (3)

Подамо у вигляді таблички - це симплекс-таблиця, просто дечого писати ми не будемо.

Базис x1 x2 s1 s2 s3 РЗ
Z-рядок
2 1 1 0 0 4
1 1 0 -1 0 1
0 1 0 0 0 2

Тепер глянемо, де в нас тут базис. Його гарно видно в обмеженні (1) - такі поки що вам траплятися лише і будуть.

Гарно вийшло б з обмеженням (2), але там коефіцієнт при базисній змінній = -1, а отже, все погано. З обмеженням (3) в нас взагалі жахлива ситуація - там навіть нема що назвати базисом.

Тепер нова редакція правил для симплекс-таблиці

Тепер кілька правил і законів:

  • Базисних змінних має бути стільки ж, скільки обмежень. В колонці базис ми записуємо лише одну змінну на рядок.
  • Кожна базисна змінна відповідає обмеженню. Записуємо кожному рядку свою змінну, а не якусь ліву.
  • Коефіцієнт при базисній змінній в своєму обмеженні - 1.
  • Базисна змінна дорівнює правій стороні свого обмеження. Якщо в колонці "базис" в нас написано x2, а в колонці РЗ (права сторона) - 234,12, то x2=234,12 і нічому іншому.
  • Коефіцієнт при базисній змінній не в своєму обмеженні - 0. В колонці базисної змінної може бути лише одна одиниця, решта - нулі.
  • Коефіцієнт при базисній змінній в Z-рядку - 0.
  • Небазисні змінні = 0. It`s fun!!!

Не перемикайтеся! Зараз власне про симплекс.

Чому саме симплекс?

200px200px200px

Так рухається симплекс-мурашка (темна) в напрямку до зеленого оптимуму

Власне кажучи, на попередній главі ми могли б закінчити розділ "Задача ЛП". Чому? Тому що ми її, по суті, розв'язали. Саме так, розв'язали. Після того як ми переписали задачу в стандартній формі та познайомилися з містером Базисом, далі йде справа техніки - для кожного базису розв'язуємо систему обмежень (поклавши небазисні змінні = 0) і знаходимо значення ц. ф. Відкидаємо недопустимі розв'язки (коли базисні змінні від'ємні) і вибираємо з того, що залишилося, найоптимальніший розв'язок. Все. Крапка.

Чому ж Данціг не заспокоївся і придумав симплекс. Через недосконалість цього світу. За скільки часу ви розв'язуєте велику систему рівнянь? А багато систем?

А систем багато. Для задачі з n змінними та m обмеженнями, отримуємо Cmn різних базисів. Для задачі 4x2 - 6 штук. Для задачі 10х5 - 252 штуки. Для задачі 100х200 (таких на контрольній не буде) - 9*1058 базисів.

Якщо ви вважаєте, що комп'ютер зможе зробити таку брудну роботу, то знайте, що такий пошук розв'язку - NP-повний алгоритм, тобто час його виконання пропорційний числу em*n. А це означає, що будь-яку мало-мальськи цікаву задачку ЛП навіть крута машина буде розв'язувати цілу вічність.

Симплекс-алгоритм, якщо на нього подивитися збоку, виглядає так: ви є маленькою мурашкою на кутку величезної фігури і повзете лише в одну сторону: сторону покращення. Тому він працює значно швидше ніж повний перебір. Зазвичай симплекс вправляється за час, пропорційний до числа m*n.

Зверніть увагу Більш детально про це все - тут

Тепер поговоримо, як можна побудувати симплекс-таблицю до кінця.

Створення симплекс-таблички

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

Задачу ми будемо розв'язувати таку:

Z(x) = 5*x1 + 4*x2 -> max

6*x1 + 4*x2 ≤ 24
x1 + 2*x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2

xi ≥ 0

Як бачите, лише обмеження "≤" - такі обмеження дуже легко формують базис. Ця задача є в Тасі під кодовою назвою Reddy Mikks. Можете нас перевіряти. Перше, що ми робимо - це перетворюємо її в стандартну:

Z(x) = 5*x1 + 4*x2 -> max

6*x1 + 4*x2 + s1 = 24
  x1 + 2*x2 + s2 = 6
  -x1 +   x2 + s3 = 1
         x2 + s4 = 2

Чудово, ми додали всього 4 змінні - вони і стануть нашим базисом. Як вже неодноразово згадувалося, це найлафовіша ситуація. Далі ми будуємо симплекс-таблицю. До речі, тут серед студентів, що досліджують операції, існує певна війна стандартів - частина використовує таблиці в стилі Шпортюка-Зайченка, а частина - в стилі Тахи. На контрольних дозволено використовувати обидва стилі. В принципі, різниці між ними мало, але певні незбіги є. Чисто з зовнішніх обставин далі усе написане в стилі Тахи. Якщо Ви петраєте в стилі Шпортюка - додайте, будь-ласка, відповідні таблички.

Базис x1 x2 s1 s2 s3 s4 РЗ
Z -5 -4 0 0 0 0 0
s1 6 4 1 0 0 0 24
s2 1 2 0 1 0 0 6
s3 -1 1 0 0 1 0 1
s4 0 1 0 0 0 1 2

Ось так наша задачка виглядає у вигляді таблички. Тут варто згадати про три речі - Z-рядок, Базис-стовбець і RHS-стовпчик.

  • Z-рядок - рівняння яке репрезентує нашу цільову функцію. Формується він з цільової функції за принципом: Z - Z(x1,x2...)=0 (одним словом 1-1=0). Затяті тахівці зазвичай пишуть після Базис-стовбця ще стовбець Z, та не вірте їм, капіталістам затятим - так робити на... просто не треба.
    На практиці ми беремо коефіцієнти при цільовій функції і дописуємо мінус, а в в кінці(в RHS'і) пишемо нуля
  • RHS (українською РЗ або пРава Зторона чи РеЗультат) - стовбець, в який пишемо значення рівності. Для виразу 2+2=5, RHS - 5.
  • Базис-стовпчик записує нам, яка змінна є базисною в рядку (що таке базисна? Тоді дивися попередній розділ)

Ітерація і з чим її їдять

Ми обираємо клітинку(тобто рядок та стовпчик) з ненульовим значенням і називаємо її головною (ще можна називати фіолетовою, стратегічною, козирною чи навіть найбільш корисною - річ не в назві). Стовпчик, який ми вибрали(козирний) позначаєх змінну, яку ми введемо в базис, а рядочок(теж козирний. Люблю термінологію, позичену з азартних ігор) - ту яку виведемо. Тобто після вибору клітинки, те що пише в її стовпчику зверху - те що входить, а в її рядочку - виходить) Зробимо все на прикладі s1 як змінної для виводу та x1 як змінної вводу (взагалі-то, цей випадок не такий випадковий, як здаєцця - в наступній статті ми все пояснимо).

  1. Ділимо головний рядок на значення головної клітинки і отримуємо:
Базис x1 x2 s1 s2 s3 s4 РЗ
Z
s1
s2
s2
s4
  1. Беремо по черзі незаповнені рядки і робимо так, щоб в них в козирному стовпчику були лише нулі.

Це робиться так: домножуємо козирний рядок на значення клітинки на перетині козирного стовпчика і рядка який ми опрацьовуємо, і віднімаємо від опрацьовуваного рядка. Беремо Z-рядок:

Базис x1 x2 s1 s2 s3 s4 РЗ
Z -5 -4 0 0 0 0 0

Яке в нас значення першої клітинки козирного рядка? 1? Так, дійсно і завжди 1! Домножимо на -4 і дістанемо -4 - клас! А тепер уявімо, що нам важче віднімати, ніж додавати - чомусь психологічно це так і є... Тому домножимо на 4 і додамо до нашої червоної клітинки. Дістали 0 - і це правильно! Тепер повторимо всю цю біліберду з кожною клітинкою...

Базис x1 x2 s1 s2 s3 s4 РЗ
Z -5 + 4*1 -4 + 4*-1 0 + 5*0 0 + 5*0 0 + 5*1 0 + 5*0 0 + 5*1

Тепер перемалюємо нашу табличку згідно з отими всіма правилами.

Базис x1 x2 s1 s2 s3 s4 РЗ
Z 0 -9 0 0 5 0 5
s1 0 10 1 0 -6 0 18
s2 0 3 0 1 -1 0 5
s3 1 -1 0 0 1 0 1
s4 0 1 0 0 0 1 2

Критерій оцінки прямого симплексу

За Тахою

Ну, з цим у них не мало б бути жодних проблем...
Дж. Данціг (зі збірника «10000 великих помилок Дж. Данціга»)

Візьмемо задачку, яка з часом набридне вам до оскоми - знаменитий «Редді Міккс» Тепер ми пояснимо, навіщо ми обирали саме таку козирну клітинку:

  1. Вибираємо такий
Базис x1 x2 s1 s2 s3 s4 РЗ
Z
s1
s2
s3 -1 1 0 0 1 0 1
s4

Двоїста задача

Якщо я дійсно читаю не в тому напрямку, чому в мене правильна відповідь?
Невідомий японець в листі Данцігу

Критерій оцінки двоїстого симплексу

Узагальнені симплекс-методи

Проблеми симплексу

Транспортна задача

Північно-західний кут

Найменша ціна

Фогель

Потенціали

Мої потенціали. Мої потенціали. Я заплутався в моїх. Потенціалах.
Гурт Мері про метод потенціалів

Цілочисельне ЛП

Метод Гоморі

Метод гілок та границь

Теорія ігор

Знову Данціг?
Дж. Неш

Ігри з природою

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

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

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

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

Розв'язують ці задачі наступним чином. Будують матрицю виграшів (чи програшів), аналогічно до ант. ігор. Кожне число в цій матриці відповідає виграшу/програшеві нашого героя в випадку j, якщо він застосував стратегію i. Побудуємо таку матрицю для нашої задачі.

aij S1 S2 S3 S4

Sj - каверзи природи: 1 - посуха, 2 - холод, 3 - дощ, 4 - так собі.
Ai - наші дії: 1 - огірки, 2 - банани (бачите, як їх ковбасить від холоду?), 3 - картопля-пофігіст.

A1 -2 3 5 1
A2 10 -5 0 0
A3 2 2 2 1

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

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

Песимістичний критерій (критерій Вальда)

TPRK:N34

Для нашої задачі маємо:

aij S1 S2 S3 S4 min
A1 -2 3 5 1 -2
A2 10 -5 0 0 -5
A3 2 2 2 1 1 <- наш вибір

Ми як песимісти обрали найменш ризикову картоплю.

Заснований на ризиках критерій Севіджа

TPRK:N35

Оптимістично-песимістичний критерій Гурвіца

TPRK:N36

Розв'яжемо нашу задачу з коефіцієнтом песимізму χ = 0.25.

aij S1 S2 S3 S4 min max G
A1 -2 3 5 1 -2 5 3.25
A2 10 -5 0 0 -5 10 8.75 <- наш вибір
A3 2 2 2 1 1 2 1.75

Внаслідок того, що ми оптимістично дивимося на цей світ, програш -5 при заморозках нас не лякає.

Імовірнісний критерій Лапласа

TPRK:N37

Імовірнісний критерій від знаменитого математика Лапласа грунтується на такому твердженні:

ЯКЩО МИ НІЧОГО НЕ ЗНАЄМО ПРО ІМОВІРНОСТІ ВИПАДАННЯ ПЕВНОЇ СТРАТЕГІЇ, ТО ЧОМУ Б НЕ ВВАЖАТИ ЇХ РІВНИМИ.

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

Наша задача:

aij S1 S2 S3 S4 M
A1 -2 3 5 1 1.75 <- наш вибір
A2 10 -5 0 0 1.25
A3 2 2 2 1 1.75 <- наш вибір

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

Антагоністичні ігри

Класична теорія оптимізації