дорівнює числу змінних прямої задачі.
2.Якщо цільова функція прямої задачі орієнтована на максимум, то цільова функція двоїстої задачі орієнтована на мінімум. У прямій задачі на максимум обмеження необхідно записати зі знаками «» або «». p>. Матриця коефіцієнтів двоїстої задачі є транспонованою матрицею коефіцієнтів прямої задачі.
. Коефіцієнти цільової функції двоїстої задачі є вільними членами обмежень прямої задачі.
. Якщо обмеження в прямій задачі задано у вигляді рівняння, то відповідна йому змінна в двоїстої завданню не визначена за знаком. В інших випадках. p>. Якщо яка-небудь змінна в прямій задачі не визначена за знаком, то відповідне обмеження двоїстої завдання задається у вигляді рівняння. В інших випадках знак нерівності. br/>
Рішення парних матричних ігор з нульовою сумою
Спрощена, формалізована модель конфліктної ситуації називається грою, а конфліктуючі сторони - гравцями. При вирішенні парних матричних ігор рядка матриці відповідають стратегіям першого гравця, а стовпці - стратегіям другого гравця. p align="justify"> Нижня ціна гри
- гарантований мінімальний виграш першого гравця (В«Максиміна стратегіяВ»).
Верхня ціна гри
- гарантований максимальний програш другого гравця В«мінімаксна стратегіяВ».
Якщо, то маємо гру з сідловою. Інакше - ціна гри C:
В
Вирішити гру можна графічно (якщо є гравець з двома стратегіями) або як пару двоїстих задач лінійного програмування.
Алгоритм розв'язання гри графічним методом
. Ймовірності гравця, що має дві стратегії, відзначають на горизонтальній числовій осі. У точках 0 і 1 відновлюють два перпендикуляра, на яких відзначають стратегії іншого гравця, поєднуючи їх відрізками. p>. Якщо перший гравець має дві стратегії (в матриці 2 рядки), то на нижній ламаної вибирають саму верхню точку (вершину). Якщо другий гравець має дві стратегії, то на верхній ламаної вибирають нижню точку. p>. Довжина перпендикуляра, опущеного з отриманої вершини на числову вісь, дорівнює ціні гри C. Причому
В
4. Стратегії, що брали участь у визначенні даної вершини, називаються активними стратегіями. З їх допомогою складаються системи рівнянь для визначення ймовірностей використання гравцями своїх оптимальних стратегій. br/>
Алгоритм відомості матричної гри до ЗЛП
1. По теоремі про ціну гри
і
Знаючи, що,,
припускають
2. Отримують пряму і двоїсту задачу лінійного програмування
,;
,
3. Вирішивши ЗЛП, визначити ціну гри можна за формулою
В
а ймовірності.
Рішення статистичної ігри
Ігри, в яких один противник "природа", а інший - людина або один з гравців діє не свідомо, а у відповідності з певними законами, називаються іграми з "природою" або статистичними іграми.
Для складання матриці ризиків визначають різниці між максимальним виграшем, який отримав би гравець, знаючи стан природи, і виграшем, який отримає гравець, застосовуючи стратегію.
Якщо відомо розподіл ймовірностей станів В«природиВ»
В
то використовують критерій Байєса
(максимум математичного очікування виграшу) або
(мінімум математичного сподівання ризику).
Якщо розподіл ймовірностей станів "природи" невідомо, то використовують:
а) принцип "недостатнього підстави Лапласа", де кожний стан природи равновероятно, тобто р1 = р2 = ... = р n = 1/n;
б) максимина критерій Вальда:;
в) критерій мінімального ризику Севіджа:;
р) критерій Гурвіца
де
при = 0 - крайній оптимізм, при = 1 - крайній песимізм
Рішення транспортної задачі методом потенціалів
Вихідні дані
- вектор запасів постачальників (стовпець), - вектор потреб споживачів (рядок), - матриця тарифів (транспортні витрати при перевезенні одиниці вантажу з пункту в пункт).
Якщо
В
то маємо закриту модель задачі. Якщо
В
то дану відкриту модель задачі, необхідно звести до закритої моделі, ввівши відсутнього фіктивного споживача або постачальника з нульовими тарифами.
Опорний план будується трьома методами: північно-західного кута, мінімального елементу та апроксимації Фогеля:
а) метод північно-західного кута: заповнення клітин таблиці починається з лівої верхньої клітини ("північно-західної"), в яку ставлять максимально можливе число, тобто мінімальне з чисел запасів і потреб для цієї клітини. При цьому вичерпуються або запаси, або потреби (викреслюється рядок або стовпець), вибирається наступна В«північно-західнаВ» клітка і т.д. Число заповнених клітин одно m + n-1. Якщо на якомусь кроці викреслюються одночасно пос...
