Теорія ігор онлайн калькулятор з покроковим розв'язком

Кількість стратегій гравця 1:

Кількість стратегій гравця 2:

matrixA,0,0,matrixmatrixA,1,0,matrixmatrixA,2,0,matrixmatrixA,3,0,matrix

matrixA,0,1,matrixmatrixA,1,1,matrixmatrixA,2,1,matrixmatrixA,3,1,matrix

matrixA,0,2,matrixmatrixA,1,2,matrixmatrixA,2,2,matrixmatrixA,3,2,matrix

matrixA,0,3,matrixmatrixA,1,3,matrixmatrixA,2,3,matrixmatrixA,3,3,matrix

Про калькулятор теорії ігор

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

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

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

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

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

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

Що таке матрична гра (теорія ігор)?

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

Як знайти розв'язок у чистих стратегіях (сідлова точка)?

Для кожного рядка знайдіть мінімум рядка (найгірша виплата, яку гравець 1 може гарантувати, обравши цей рядок). Для кожного стовпця знайдіть максимум стовпця (найгірше, що може гарантувати гравець 2, обравши цей стовпець). Якщо максимум мінімумів рядків дорівнює мінімуму максимумів стовпців, то в цьому елементі існує сідлова точка; ціна гри дорівнює цьому спільному числу, і обидва гравці повинні використовувати відповідну чисту стратегію.

Як знайти розв'язок у змішаних стратегіях?

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

Приклад розв'язання матричної гри

	B₁	B₂	B₃	min
A₁	2	4	3	2	t₁
A₂	3	1	4	1	t₂
A₃	4	3	2	2	t₃
max	4	4	4

Нижня ціна гри (максимін)

α = 2

Верхня ціна гри (мінімакс)

β = 4

α ≠ β — сідлової точки немає. Розв'яжемо матричну гру шляхом зведення до задачі лінійного програмування.

F(x) = x₁+x₂+x₃ → min

F(x) = x₁+x₂+x₃+0x₄+0x₅+0x₆+Mx₇+Mx₈+Mx₉ → min

2x₁+3x₂+4x₃ ≥ 1

2x₁+3x₂+4x₃-x₄+x₇ = 1

4x₁+x₂+3x₃ ≥ 1

4x₁+x₂+3x₃-x₅+x₈ = 1

3x₁+4x₂+2x₃ ≥ 1

3x₁+4x₂+2x₃-x₆+x₉ = 1

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

Далі необхідно позбутися нерівностей, для чого вводимо компенсуючі змінні в ліву частину нерівностей. Якщо нерівність виду ≤, то компенсуюча змінна має знак +, якщо нерівність виду ≥, то компенсуюча змінна має знак -. Компенсуючі змінні входять до цільової функції задачі з нульовим коефіцієнтом.

Тепер у системі обмежень необхідно знайти достатню кількість базисних змінних. Кожне обмеження повинно мати одну базисну змінну. Базисна — це змінна, яка має коефіцієнт 1 при ній та зустрічається лише в одному обмеженні. Якщо в деякому обмеженні базисних змінних немає, то ми додаємо їх штучно, і штучні змінні входять до цільової функції з коефіцієнтом -M, якщо цільова функція прямує до max, і M, якщо цільова функція прямує до min.

Опис

Ітерація 1

B	Cb	P	x₁↓	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	1	1	1	0	0	0	M	M	M	Q
x₇	M	1	2	3	4	-1	0	0	1	0	0	12
x₈←	M	1	4	1	3	0	-1	0	0	1	0	14
x₉	M	1	3	4	2	0	0	-1	0	0	1	13
min		3M	9M-1	8M-1	9M-1	-M	-M	-M	0	0	0

Елементи стовпця базису (B)

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

B₁ = x₇;

B₂ = x₈;

B₃ = x₉;

Елементи стовпця Cb

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

Cb₁ = M;

Cb₂ = M;

Cb₃ = M;

Значення вільних змінних і стовпця P

На цьому етапі обчислень не потрібно, просто переносимо значення з попереднього етапу до відповідних клітинок таблиці:

P₁ = 1;

P₂ = 1;

P₃ = 1;

x_1,1 = 2;

x_1,2 = 3;

x_1,3 = 4;

x_1,4 = -1;

x_1,5 = 0;

x_1,6 = 0;

x_1,7 = 1;

x_1,8 = 0;

x_1,9 = 0;

x_2,1 = 4;

x_2,2 = 1;

x_2,3 = 3;

x_2,4 = 0;

x_2,5 = -1;

x_2,6 = 0;

x_2,7 = 0;

x_2,8 = 1;

x_2,9 = 0;

x_3,1 = 3;

x_3,2 = 4;

x_3,3 = 2;

x_3,4 = 0;

x_3,5 = 0;

x_3,6 = -1;

x_3,7 = 0;

x_3,8 = 0;

x_3,9 = 1;

Значення цільової функції

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

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) = (M * 1) + (M * 1) + (M * 1) = 3M;

Оцінки керованих змінних

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

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1)) - k_x₁ = ((M * 2) + (M * 4) + (M * 3)) - 1 = 9M-1;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2)) - k_x₂ = ((M * 3) + (M * 1) + (M * 4)) - 1 = 8M-1;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3)) - k_x₃ = ((M * 4) + (M * 3) + (M * 2)) - 1 = 9M-1;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4)) - k_x₄ = ((M * -1) + (M * 0) + (M * 0)) - 0 = -M;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5)) - k_x₅ = ((M * 0) + (M * -1) + (M * 0)) - 0 = -M;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6)) - k_x₆ = ((M * 0) + (M * 0) + (M * -1)) - 0 = -M;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7)) - k_x₇ = ((M * 1) + (M * 0) + (M * 0)) - M = 0;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8)) - k_x₈ = ((M * 0) + (M * 1) + (M * 0)) - M = 0;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9)) - k_x₉ = ((M * 0) + (M * 0) + (M * 1)) - M = 0;

Елементи стовпця Q

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

Кількість змінних у базисі завжди стала, тому необхідно вибрати, яку змінну виводити з базису, для чого обчислюємо Q.

Елементи стовпця Q обчислюються шляхом ділення значень зі стовпця P на значення зі стовпця, що відповідає змінній, яка вводиться до базису:

Q₁ = P₁x_1,1 = 12 = 12;

Q₂ = P₂x_2,1 = 14 = 14;

Q₃ = P₃x_3,1 = 13 = 13;

Виводимо з базису змінну з найменшим додатним значенням Q.

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

Цей елемент дозволить нам обчислити елементи таблиці наступної ітерації.

Опис

Ітерація 2

B	Cb	P	x₁	x₂↓	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	1	1	1	0	0	0	M	M	M	Q
x₇	M	12	0	212	212	-1	12	0	1	-12	0	15
x₁	1	14	1	14	34	0	-14	0	0	14	0	1
x₉←	M	14	0	314	-14	0	34	-1	0	-34	1	113
min		34M+14	0	534M-34	214M-14	-M	114M-14	-M	0	-214M+14	0

Елементи стовпця базису (B)

За результатами обчислень попередньої ітерації виводимо змінну з базису x₈ та ставимо на її місце x₁. Всі інші клітинки залишаються незмінними.

Елементи стовпця Cb

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

Cb₁ = M;

Cb₂ = 1;

Cb₃ = M;

Значення вільних змінних і стовпця P

(Дані з попередньої ітерації беруться як вхідні дані)

Заповнюємо нулями всі клітинки, що відповідають змінній, яка щойно введена до базису:

(Розв'язуючий елемент залишається незмінним)

x_1,1 = 0;

x_3,1 = 0;

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

x_2,1 = x_2,1x_2,1 = 44 = 1;

x_2,2 = x_2,2x_2,1 = 14 = 14;

x_2,3 = x_2,3x_2,1 = 34 = 34;

x_2,4 = x_2,4x_2,1 = 04 = 0;

x_2,5 = x_2,5x_2,1 = -14 = -14;

x_2,6 = x_2,6x_2,1 = 04 = 0;

x_2,7 = x_2,7x_2,1 = 04 = 0;

x_2,8 = x_2,8x_2,1 = 14 = 14;

x_2,9 = x_2,9x_2,1 = 04 = 0;

P₂ = P₂x_2,1 = 14 = 14;

Решта порожніх клітинок, крім рядка оцінок та стовпця Q, обчислюються методом прямокутника відносно розв'язуючого елемента:

x_1,2 = (x_1,2 * x_2,1) - (x_1,1 * x_2,2)x_2,1 = (3 * 4) - (2 * 1)4 = 212;

x_1,3 = (x_1,3 * x_2,1) - (x_1,1 * x_2,3)x_2,1 = (4 * 4) - (2 * 3)4 = 212;

x_1,4 = (x_1,4 * x_2,1) - (x_1,1 * x_2,4)x_2,1 = (-1 * 4) - (2 * 0)4 = -1;

x_1,5 = (x_1,5 * x_2,1) - (x_1,1 * x_2,5)x_2,1 = (0 * 4) - (2 * -1)4 = 12;

x_1,6 = (x_1,6 * x_2,1) - (x_1,1 * x_2,6)x_2,1 = (0 * 4) - (2 * 0)4 = 0;

x_1,7 = (x_1,7 * x_2,1) - (x_1,1 * x_2,7)x_2,1 = (1 * 4) - (2 * 0)4 = 1;

x_1,8 = (x_1,8 * x_2,1) - (x_1,1 * x_2,8)x_2,1 = (0 * 4) - (2 * 1)4 = -12;

x_1,9 = (x_1,9 * x_2,1) - (x_1,1 * x_2,9)x_2,1 = (0 * 4) - (2 * 0)4 = 0;

P₁ = (P₁ * x_2,1) - (x_1,1 * P₂)x_2,1 = (1 * 4) - (2 * 1)4 = 12;

x_3,2 = (x_3,2 * x_2,1) - (x_3,1 * x_2,2)x_2,1 = (4 * 4) - (3 * 1)4 = 314;

x_3,3 = (x_3,3 * x_2,1) - (x_3,1 * x_2,3)x_2,1 = (2 * 4) - (3 * 3)4 = -14;

x_3,4 = (x_3,4 * x_2,1) - (x_3,1 * x_2,4)x_2,1 = (0 * 4) - (3 * 0)4 = 0;

x_3,5 = (x_3,5 * x_2,1) - (x_3,1 * x_2,5)x_2,1 = (0 * 4) - (3 * -1)4 = 34;

x_3,6 = (x_3,6 * x_2,1) - (x_3,1 * x_2,6)x_2,1 = (-1 * 4) - (3 * 0)4 = -1;

x_3,7 = (x_3,7 * x_2,1) - (x_3,1 * x_2,7)x_2,1 = (0 * 4) - (3 * 0)4 = 0;

x_3,8 = (x_3,8 * x_2,1) - (x_3,1 * x_2,8)x_2,1 = (0 * 4) - (3 * 1)4 = -34;

x_3,9 = (x_3,9 * x_2,1) - (x_3,1 * x_2,9)x_2,1 = (1 * 4) - (3 * 0)4 = 1;

P₃ = (P₃ * x_2,1) - (x_3,1 * P₂)x_2,1 = (1 * 4) - (3 * 1)4 = 14;

Значення цільової функції

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) = (M * 12) + (1 * 14) + (M * 14) = 34M+14;

Оцінки керованих змінних

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1)) - k_x₁ = ((M * 0) + (1 * 1) + (M * 0)) - 1 = 0;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2)) - k_x₂ = ((M * 212) + (1 * 14) + (M * 314)) - 1 = 534M-34;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3)) - k_x₃ = ((M * 212) + (1 * 34) + (M * -14)) - 1 = 214M-14;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4)) - k_x₄ = ((M * -1) + (1 * 0) + (M * 0)) - 0 = -M;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5)) - k_x₅ = ((M * 12) + (1 * -14) + (M * 34)) - 0 = 114M-14;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6)) - k_x₆ = ((M * 0) + (1 * 0) + (M * -1)) - 0 = -M;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7)) - k_x₇ = ((M * 1) + (1 * 0) + (M * 0)) - M = 0;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8)) - k_x₈ = ((M * -12) + (1 * 14) + (M * -34)) - M = -214M+14;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9)) - k_x₉ = ((M * 0) + (1 * 0) + (M * 1)) - M = 0;

Елементи стовпця Q

Q₁ = P₁x_1,2 = 12212 = 15;

Q₂ = P₂x_2,2 = 1414 = 1;

Q₃ = P₃x_3,2 = 14314 = 113;

Виводимо з базису змінну з найменшим додатним значенням Q.

Цей елемент дозволить нам обчислити елементи таблиці наступної ітерації.

Опис

Ітерація 3

B	Cb	P	x₁	x₂	x₃↓	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	1	1	1	0	0	0	M	M	M	Q
x₇←	M	413	0	0	2913	-1	-113	1013	1	113	-1013	435
x₁	1	313	1	0	1013	0	-413	113	0	413	-113	310
x₂	1	113	0	1	-113	0	313	-413	0	-313	413	∞
min		413M+413	0	0	2913M-413	-M	-113M-113	1013M-313	0	-1213M+113	-11013M+313

Елементи стовпця базису (B)

За результатами обчислень попередньої ітерації виводимо змінну з базису x₉ та ставимо на її місце x₂. Всі інші клітинки залишаються незмінними.

Елементи стовпця Cb

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

Cb₁ = M;

Cb₂ = 1;

Cb₃ = 1;

Значення вільних змінних і стовпця P

(Дані з попередньої ітерації беруться як вхідні дані)

Заповнюємо нулями всі клітинки, що відповідають змінній, яка щойно введена до базису:

(Розв'язуючий елемент залишається незмінним)

x_1,2 = 0;

x_2,2 = 0;

x_3,1 = x_3,1x_3,2 = 0314 = 0;

x_3,2 = x_3,2x_3,2 = 314314 = 1;

x_3,3 = x_3,3x_3,2 = -14314 = -113;

x_3,4 = x_3,4x_3,2 = 0314 = 0;

x_3,5 = x_3,5x_3,2 = 34314 = 313;

x_3,6 = x_3,6x_3,2 = -1314 = -413;

x_3,7 = x_3,7x_3,2 = 0314 = 0;

x_3,8 = x_3,8x_3,2 = -34314 = -313;

x_3,9 = x_3,9x_3,2 = 1314 = 413;

P₃ = P₃x_3,2 = 14314 = 113;

x_1,1 = (x_1,1 * x_3,2) - (x_1,2 * x_3,1)x_3,2 = (0 * 314) - (212 * 0)314 = 0;

x_1,3 = (x_1,3 * x_3,2) - (x_1,2 * x_3,3)x_3,2 = (212 * 314) - (212 * -14)314 = 2913;

x_1,4 = (x_1,4 * x_3,2) - (x_1,2 * x_3,4)x_3,2 = (-1 * 314) - (212 * 0)314 = -1;

x_1,5 = (x_1,5 * x_3,2) - (x_1,2 * x_3,5)x_3,2 = (12 * 314) - (212 * 34)314 = -113;

x_1,6 = (x_1,6 * x_3,2) - (x_1,2 * x_3,6)x_3,2 = (0 * 314) - (212 * -1)314 = 1013;

x_1,7 = (x_1,7 * x_3,2) - (x_1,2 * x_3,7)x_3,2 = (1 * 314) - (212 * 0)314 = 1;

x_1,8 = (x_1,8 * x_3,2) - (x_1,2 * x_3,8)x_3,2 = (-12 * 314) - (212 * -34)314 = 113;

x_1,9 = (x_1,9 * x_3,2) - (x_1,2 * x_3,9)x_3,2 = (0 * 314) - (212 * 1)314 = -1013;

P₁ = (P₁ * x_3,2) - (x_1,2 * P₃)x_3,2 = (12 * 314) - (212 * 14)314 = 413;

x_2,1 = (x_2,1 * x_3,2) - (x_2,2 * x_3,1)x_3,2 = (1 * 314) - (14 * 0)314 = 1;

x_2,3 = (x_2,3 * x_3,2) - (x_2,2 * x_3,3)x_3,2 = (34 * 314) - (14 * -14)314 = 1013;

x_2,4 = (x_2,4 * x_3,2) - (x_2,2 * x_3,4)x_3,2 = (0 * 314) - (14 * 0)314 = 0;

x_2,5 = (x_2,5 * x_3,2) - (x_2,2 * x_3,5)x_3,2 = (-14 * 314) - (14 * 34)314 = -413;

x_2,6 = (x_2,6 * x_3,2) - (x_2,2 * x_3,6)x_3,2 = (0 * 314) - (14 * -1)314 = 113;

x_2,7 = (x_2,7 * x_3,2) - (x_2,2 * x_3,7)x_3,2 = (0 * 314) - (14 * 0)314 = 0;

x_2,8 = (x_2,8 * x_3,2) - (x_2,2 * x_3,8)x_3,2 = (14 * 314) - (14 * -34)314 = 413;

x_2,9 = (x_2,9 * x_3,2) - (x_2,2 * x_3,9)x_3,2 = (0 * 314) - (14 * 1)314 = -113;

P₂ = (P₂ * x_3,2) - (x_2,2 * P₃)x_3,2 = (14 * 314) - (14 * 14)314 = 313;

Значення цільової функції

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) = (M * 413) + (1 * 313) + (1 * 113) = 413M+413;

Оцінки керованих змінних

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1)) - k_x₁ = ((M * 0) + (1 * 1) + (1 * 0)) - 1 = 0;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2)) - k_x₂ = ((M * 0) + (1 * 0) + (1 * 1)) - 1 = 0;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3)) - k_x₃ = ((M * 2913) + (1 * 1013) + (1 * -113)) - 1 = 2913M-413;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4)) - k_x₄ = ((M * -1) + (1 * 0) + (1 * 0)) - 0 = -M;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5)) - k_x₅ = ((M * -113) + (1 * -413) + (1 * 313)) - 0 = -113M-113;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6)) - k_x₆ = ((M * 1013) + (1 * 113) + (1 * -413)) - 0 = 1013M-313;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7)) - k_x₇ = ((M * 1) + (1 * 0) + (1 * 0)) - M = 0;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8)) - k_x₈ = ((M * 113) + (1 * 413) + (1 * -313)) - M = -1213M+113;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9)) - k_x₉ = ((M * -1013) + (1 * -113) + (1 * 413)) - M = -11013M+313;

Елементи стовпця Q

Q₁ = P₁x_1,3 = 4132913 = 435;

Q₂ = P₂x_2,3 = 3131013 = 310;

Q₃ = P₃x_3,3 = 113-113 = ∞;

Виводимо з базису змінну з найменшим додатним значенням Q.

Цей елемент дозволить нам обчислити елементи таблиці наступної ітерації.

Опис

Ітерація 4

B	Cb	P	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	1	1	1	0	0	0	M	M	M	Q
x₃	1	435	0	0	1	-1335	-135	27	1335	135	-27
x₁	1	17	1	0	0	27	-27	-17	-27	27	17
x₂	1	335	0	1	0	-135	835	-27	135	-835	27
min		1235	0	0	0	-435	-335	-17	-M+435	-M+335	-M+17

Елементи стовпця базису (B)

За результатами обчислень попередньої ітерації виводимо змінну з базису x₇ та ставимо на її місце x₃. Всі інші клітинки залишаються незмінними.

Елементи стовпця Cb

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

Cb₁ = 1;

Cb₂ = 1;

Cb₃ = 1;

Значення вільних змінних і стовпця P

(Дані з попередньої ітерації беруться як вхідні дані)

Заповнюємо нулями всі клітинки, що відповідають змінній, яка щойно введена до базису:

(Розв'язуючий елемент залишається незмінним)

x_2,3 = 0;

x_3,3 = 0;

x_1,1 = x_1,1x_1,3 = 02913 = 0;

x_1,2 = x_1,2x_1,3 = 02913 = 0;

x_1,3 = x_1,3x_1,3 = 29132913 = 1;

x_1,4 = x_1,4x_1,3 = -12913 = -1335;

x_1,5 = x_1,5x_1,3 = -1132913 = -135;

x_1,6 = x_1,6x_1,3 = 10132913 = 27;

x_1,7 = x_1,7x_1,3 = 12913 = 1335;

x_1,8 = x_1,8x_1,3 = 1132913 = 135;

x_1,9 = x_1,9x_1,3 = -10132913 = -27;

P₁ = P₁x_1,3 = 4132913 = 435;

x_2,1 = (x_2,1 * x_1,3) - (x_2,3 * x_1,1)x_1,3 = (1 * 2913) - (1013 * 0)2913 = 1;

x_2,2 = (x_2,2 * x_1,3) - (x_2,3 * x_1,2)x_1,3 = (0 * 2913) - (1013 * 0)2913 = 0;

x_2,4 = (x_2,4 * x_1,3) - (x_2,3 * x_1,4)x_1,3 = (0 * 2913) - (1013 * -1)2913 = 27;

x_2,5 = (x_2,5 * x_1,3) - (x_2,3 * x_1,5)x_1,3 = (-413 * 2913) - (1013 * -113)2913 = -27;

x_2,6 = (x_2,6 * x_1,3) - (x_2,3 * x_1,6)x_1,3 = (113 * 2913) - (1013 * 1013)2913 = -17;

x_2,7 = (x_2,7 * x_1,3) - (x_2,3 * x_1,7)x_1,3 = (0 * 2913) - (1013 * 1)2913 = -27;

x_2,8 = (x_2,8 * x_1,3) - (x_2,3 * x_1,8)x_1,3 = (413 * 2913) - (1013 * 113)2913 = 27;

x_2,9 = (x_2,9 * x_1,3) - (x_2,3 * x_1,9)x_1,3 = (-113 * 2913) - (1013 * -1013)2913 = 17;

P₂ = (P₂ * x_1,3) - (x_2,3 * P₁)x_1,3 = (313 * 2913) - (1013 * 413)2913 = 17;

x_3,1 = (x_3,1 * x_1,3) - (x_3,3 * x_1,1)x_1,3 = (0 * 2913) - (-113 * 0)2913 = 0;

x_3,2 = (x_3,2 * x_1,3) - (x_3,3 * x_1,2)x_1,3 = (1 * 2913) - (-113 * 0)2913 = 1;

x_3,4 = (x_3,4 * x_1,3) - (x_3,3 * x_1,4)x_1,3 = (0 * 2913) - (-113 * -1)2913 = -135;

x_3,5 = (x_3,5 * x_1,3) - (x_3,3 * x_1,5)x_1,3 = (313 * 2913) - (-113 * -113)2913 = 835;

x_3,6 = (x_3,6 * x_1,3) - (x_3,3 * x_1,6)x_1,3 = (-413 * 2913) - (-113 * 1013)2913 = -27;

x_3,7 = (x_3,7 * x_1,3) - (x_3,3 * x_1,7)x_1,3 = (0 * 2913) - (-113 * 1)2913 = 135;

x_3,8 = (x_3,8 * x_1,3) - (x_3,3 * x_1,8)x_1,3 = (-313 * 2913) - (-113 * 113)2913 = -835;

x_3,9 = (x_3,9 * x_1,3) - (x_3,3 * x_1,9)x_1,3 = (413 * 2913) - (-113 * -1013)2913 = 27;

P₃ = (P₃ * x_1,3) - (x_3,3 * P₁)x_1,3 = (113 * 2913) - (-113 * 413)2913 = 335;

Значення цільової функції

Min_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) = (1 * 435) + (1 * 17) + (1 * 335) = 1235;

Оцінки керованих змінних

Min_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1)) - k_x₁ = ((1 * 0) + (1 * 1) + (1 * 0)) - 1 = 0;

Min_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2)) - k_x₂ = ((1 * 0) + (1 * 0) + (1 * 1)) - 1 = 0;

Min_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3)) - k_x₃ = ((1 * 1) + (1 * 0) + (1 * 0)) - 1 = 0;

Min_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4)) - k_x₄ = ((1 * -1335) + (1 * 27) + (1 * -135)) - 0 = -435;

Min_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5)) - k_x₅ = ((1 * -135) + (1 * -27) + (1 * 835)) - 0 = -335;

Min_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6)) - k_x₆ = ((1 * 27) + (1 * -17) + (1 * -27)) - 0 = -17;

Min_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7)) - k_x₇ = ((1 * 1335) + (1 * -27) + (1 * 135)) - M = -M+435;

Min_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8)) - k_x₈ = ((1 * 135) + (1 * 27) + (1 * -835)) - M = -M+335;

Min_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9)) - k_x₉ = ((1 * -27) + (1 * 17) + (1 * 27)) - M = -M+17;

Відповідь

Оскільки серед оцінок керованих змінних немає додатних значень, поточна таблиця має оптимальний розв'язок.

Значення цільової функції:

F* = 1235;

Змінні, що присутні в базисі, дорівнюють відповідним клітинкам стовпця P, всі інші змінні дорівнюють нулю:

x₁ = 17;

x₂ = 335;

x₃ = 435;

Опис

Answer

v → max min

F* = 1235

X* = (17; 335; 435)

Стратегії гравця I3Стратегії гравця II3ТипМішана стратегія

Часті запитання

Що розв'язує цей калькулятор теорії ігор?

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

Що таке сідлова точка?

Сідлова точка — це елемент, який є мінімумом свого рядка та максимумом свого стовпця. Якщо вона існує, гра має розв'язок у чистих стратегіях, а значення сідлової точки є ціною гри.

Як обчислюються мішані стратегії?

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

Що означає «ціна гри»?

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

Джерела

Google Play App Store

x_i ↓	— вводимо змінну до базису;
x_i←	— виводимо змінну з базису;
x_i	— розв'язуючий елемент;
x_i	— базисний елемент;
B	— базис;
Cb	— коефіцієнт при базисній змінній;
P	— план;

Про калькулятор теорії ігор

Що таке матрична гра (теорія ігор)?

Як знайти розв'язок у чистих стратегіях (сідлова точка)?

Як знайти розв'язок у змішаних стратегіях?

Приклад розв'язання матричної гри

Часті запитання

Пов'язані калькулятори

Джерела