Применение методов линейного программирования

 Е (А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

 Е (А, х, y).

Подобно  играм, имеющим седловые точки  в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями  игроков 1 и 2 называются такие наборы  хо, уо  соответственно, которые удовлетворяют равенству

 Е (А, х, y) =  Е (А, х, y) = Е (А, хо, уо).

Величина  Е (А, хо ,уо) называется при этом ценой игры и обозначается через  u.

Имеется и другое определение оптимальных смешанных  стратегий:  хо, уо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, х, уо)<= Е (А, хо, уо)<= Е (А, хо, у)

Оптимальные смешанные  стратегии и цена игры называются решением матричной игры.

Основная теорема  матричных игр имеет вид :

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

 Е (А, х, y)  и    Е (А, х, y)   существуют и равны между собой.

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования.

Пусть игра m × n задана платежной матрицей p = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В — стратегиями B₁ , B₂ , ..., B_m . Необходимо определить оптимальные стратегии S*_A = ( p*₁ ,  p*₂ , ... ,  p*_m ) и S*_B = ( q*₁ , q*₂ , ... ,  q*_n ), где p*_i, q*_j — вероятности применения соответствующих чистых стратегий A_i , B_j,   p*₁  + p*₂ +...+ p*_m =1, q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = ( p*₁ ,  p*₂ , ... ,  p*_m ) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a_j = a_1j p₁ + a_2j p₂ +...+ a_m j p_m , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ , ..., A_m и результаты складываются).

Для оптимальной  стратегии S*_A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

Каждое  из неравенств можно разделить на число v > 0. Введем новые переменные:

Тогда система (2.3.1) примет вид:

Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v.  
Разделив на v ≠ 0 равенство p₁ + p₂ + ...+ p_m = 1 , получаем, что переменные x₁ (i = 1, 2, ..., m) удовлетворяют условию: x₁ + x₂ + ...+ x_m = 1/v. Максимизация цены игры v эквивалентна минимизации величины1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (2.3.3) и при этом линейная функция

обращалась  в минимум. Это задача линейного программирования. Решая задачу (2.3.3)—( 2.3.4), получаем оптимальное решение p*₁ + p*₂ + ...+ p*_m и оптимальную стратегию S_A .  
Для определения оптимальной стратегии S*_B = (q*₁ + q*₂ + ...+ q*_n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти  . Переменные q₁ , q₂ , ..., q_n удовлетворяют неравенствам:

которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял, игрок А.  
Если обозначить

то получим  систему неравенств:

Переменные y_j (1, 2, ..., n) удовлетворяют условию  .  
Игра свелась к следующей задаче  
Определить значения переменных y_j ≥ 0, j = 1, 2, ..., n,  которые удовлетворяют системе неравенств (2.3.7) и максимизируют линейную функцию

Решение задачи линейного программирования (2.3.6), (2.3.7) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ + ...+ q*_n) . При этом цена игры

Составив  расширенные матрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Практическая часть  

Постановка задачи: Для производства трёх видов продукции используется три вида сырья. Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы

продукции приведены в таблице:

Определить план выпуска продукции для получения максимальной прибыли, чтобы сырьё IIвида было израсходовано полностью. Оценить каждый из видов сырья, используемых для производства продукции. 
 

                          Вид таблицы по заданию поставленной задачи: 
 

Решение поставленной задачи: 

Предположим, что  производится x₁ изделий А,  изделий В и  изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

  3.1. Построим математическую модель задачи:

        тогда функция цели:  ¬

   Z-0 = 3X₁ + 7X₂ + 2X₃   – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать. 

Подсчитаем затраты  сырья:

Сырье 1-го типа: 4 х1 + 2 х2 + 0 х3 , по условию затраты не превосходят 19,

Сырье 2-го типа: 0 х1 + 1 х2 + 1 х3, по условию затраты не превосходят 8,

Сырье 3-го типа: 1x1 + 2x2 + 0x3, по условию затраты не превосходят 24.

при следующих  условиях:

           

                                          

X₁, X₂, X₃ ≥ 0. 
 

4X₁+2X   ≤ 19

  X₂ + X₃ = 8

  X₁+2X₂ ≤24 

3.2. Выбираем метод решения и приводим задачу к каноническому виду:

Пришли к задаче линейного программирования:

припишем каждому  из видов сырья, используемых для  производства продукции. Тогда общая оценка сырья, используемого на производство продукции, составит:

Получили математическую модель. Необходимо максимизировать  функцию цели                                          ↓