Пример решения матричной игры методом линейного программирования
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
6x1 + 5x2 + 7x3≤1
10x1 + 4x2 + 7x3≤1
13x1 + 10x2 + 4x3≤1
7x1 + 11x2 + 5x3=1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 = 1
10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 = 1
13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 = 1
7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 = 1
Введем искусственные переменные x.
6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 + 0x7= 1
10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 + 0x7= 1
13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 + 0x7= 1
7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 + 1x7= 1
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = x1+x2+x3 — Mx7 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 1-7x1-11x2-5x3
которые подставим в целевую функцию:
F(X) = x1 + x2 + x3 — M(1-7x1-11x2-5x3) => max
или
F(X) = (1+7M)x1+(1+11M)x2+(1+5M)x3+(-1M) => max
Второй способ нахождений двойственной задачи
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда
Решение матричной игры симплексным методом
Найти решение матричной игры. Решить матричные игры симплексным методом.
Задание. Свести задачу, заданную платежной матрицей, к задаче линейного программирования (предварительно упростив задачу, убрав строго доминируемые стратегии, если это возможно) и решить симплекс методом.
Решение проводим с помощью калькулятора.
| Игроки | B1 | B2 | B3 | a = min(Ai) |
| A1 | 0 | 3 | 1 | 0 |
| A2 | 3 | 0 | 5 | 0 |
| A3 | 2 | 1 | 1 | 1 |
| b = max(Bi ) | 3 | 3 | 5 | 0 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 = 1
3x1 + 0x2 + 1x3 + 0x4-1x5 + 0x6 = 1
1x1 + 5x2 + 1x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
0x1-3x2-2x3 + 1x4 + 0x5 + 0x6 = -1
-3x1 + 0x2-1x3 + 0x4 + 1x5 + 0x6 = -1
-1x1-5x2-1x3 + 0x4 + 0x5 + 1x6 = -1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,-1,-1,-1)
| План | Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| 0 | x4 | -1 | 0 | -3 | -2 | 1 | 0 | 0 |
| x5 | -1 | -3 | 0 | -1 | 0 | 1 | 0 | |
| x6 | -1 | -1 | -5 | -1 | 0 | 0 | 1 | |
| Индексная строка | F(X0) | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A -1 =
Оптимальный план двойственной задачи равен:
y1 = 1 /3, y2 = 1 /3, y3 = 0
Z(Y) = 1* 1 /3+1* 1 /3+1*0 = 2 /3
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 2 /3 = 1 1 /2
Оптимальная стратегия игрока А: P( 1 /2 ; 1 /2; 0)
Оптимальная стратегия игрока B: Q( 1 /2; 1 /2; 0)
Пример №3 . Предприятие выпускает скоропортящуюся продукцию, которую сразу можно доставить потребителю (А1 стратегия). Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия) . Потребитель может приобрести немедленно (В1 стратег) ,через некоторое время (В2 стратег) или после длительного периода (В3 стратегия).
В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции. Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3 . Определить оптимальные пропорции для применения стратегий А1,А2,А3. Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.
| Игроки | B1 | B2 | B3 | a = min(Ai) |
| A1 | 2 | 3 | 2 | 2 |
| A2 | 4 | 2 | 1 | 1 |
| A3 | 1 | 3 | 3 | 1 |
| b = max(Bi ) | 4 | 3 | 3 | 0 |
Решение матричной игры находим через сервис решение матричной игры.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2 Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
2x1+4x2+x3 >= 1
3x1+2x2+3x3 >= 1
2x1+x2+3x3 >= 1
F(x) = x1+x2+x3 = min
найти максимум функции Ф(y) при ограничениях:
2y1+3y2+2y3 4y1+2y2+y3 y1+3y2+3y3 Ф(y) = y1+y2+y3 = max
Решаем эти системы симплекс-методом.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
2x1 + 4x2 + x3≥1
3x1 + 2x2 + 3x3≥1
2x1 + x2 + 3x3≥1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 4x2 + 1x3-1x4 + 0x5 + 0x6 = 1
3x1 + 2x2 + 3x3 + 0x4-1x5 + 0x6 = 1
2x1 + 1x2 + 3x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
-2x1-4x2-1x3 + 1x4 + 0x5 + 0x6 = -1
-3x1-2x2-3x3 + 0x4 + 1x5 + 0x6 = -1
-2x1-1x2-3x3 + 0x4 + 0x5 + 1x6 = -1
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 5 /11 = 2 1 /5
p1 = 2 1 /5•0 = 0
p2 = 2 1 /5• 2 /11 = 2 /5
p3 = 2 1 /5• 3 /11 = 3 /5
q1 = 2 1 /5• 2 /11 = 2 /5
q2 = 2 1 /5•0 = 0
q3 = 2 1 /5• 3 /11 = 3 /5
Оптимальная стратегия игрока А: P( 0; 2 /5; 3 /5)
Оптимальная стратегия игрока B: Q( 2 /5;0; 3 /5)
Матричная и развернутая формы задачи линейного программирования
Линейное программирование. Решение задачи. Методические указания и варианты индивидуальных заданий для студентов заочного факультета, – СПб.: Петербургский государственный университет путей сообщения, 2006, 22 с.
Содержание пособия соответствует разделам математического программирования, изучаемым студентами в 3 семестре. Пособие предназначено для студентов специальностей УПП заочного факультета ПГУПС.
Рецензент: профессор В.В. Гарбарук (кафедра «Высшая математика» ПГУПС)
© Петербургский государственный университет
Постановка задачи
Главным объектом изучения в линейном программирование является задача, которая в наиболее общей форме формулируется следующем образом.
Задача. Найти экстремум линейной функции F, если ее аргументы удовлетворяют некоторым ограничениям.
Настоящие методические указания посвящены анализу задачи линейного программирования, даны ее различные формы записи и указаны некоторые способы ее решения.
Каждый студент должен будет сделать для своей задачи все ниже перечисленные действия.
1. Записать задачу в матричной форме
2. Записать каноническую задачу.
3. Решить задачу геометрически.
4. Найти начальный базисный план с помощью искусственных переменных.
5. Решить задачу симплекс-методом.
6. Написать двойственную задачу к искомой в матричной и развернутой формах.
7. Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.
Варианты задач и пример решения указаны в конце этих указаний.
Матричная и развернутая формы задачи линейного программирования
В этом параграфе мы сравним две формы записи задачи линейного программирования.
Определение 1. Следующая задача называется стандартной задачей линейного программирования.
Задача 1. Найти
где A – матрица системы ограничений, имеющая m строк и n столбцов, b – столбец из m элементов; c, x – столбцы из n элементов. Таким образом, эти матрицы имеют вид
В развернутой форме эта стандартная задача линейного программирования может быть записана в следующем виде.
Задача 1’. Найти максимум линейной функции
Определение 2. Решением этих задач называется матрица (упорядоченный набор чисел) , удовлетворяющая системе ограничений (2) и обеспечивающая максимальное значение функции (1). Иногда это решение называется оптимальным планом задачи. Значение функции на оптимальном плане обозначается .
Определение 3. Линейная функция F задачи 1 называется целевой функцией, а множество D решений системы (2) – множеством допустимых решений (планов) этой задачи.
Пример 1. Записать задачу линейного программирования (1), (2) с матрицами
Решение. В развернутой форме задача формулируется следующим образом.
Найти максимум функции при ограничениях
Пример 2. Записать следующую задачу линейного программирования в матричной форме.
Минимизировать линейную функцию при ограничениях
Решение. Для того чтобы записать эту задачу в матричной форме (1, 2), изменим неравенства в ограничениях задачи так, чтоб они имели одинаковый знак. Для этого умножим первое неравенство на –1. Мы получим следующую систему ограничений задачи:
Тогда в матричной форме задача примет вид