15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ

Единица продукта за

Ръ «12 «22

Л ап «21

hi

&2

Цена (в пенсах единицу) . . Калорий (единиц) Белков (единиц) Двойственная задача Максимизировать

при условии

аіі?і + ааіЕа<Л»

ац?і + Яаа|а<ра,

Бі>0, ?2>О.

Эти задачи можно сформулировать так: Прямая задача Минимизировать

(1>

2 = Pixi + V%x 2 при условии

а11ж1 + а12х2>&1, а21л;1 + а22л;2>&2, #!>(), я2>0. Допустимые решения для х и ? удовлетворяют; неравенствам системы (1); оптимальное допустимое решение удовлетворяет также условиям максимума или минимума.

Рассмотрим игру с двумя участниками и нулевой суммой, платежная; матрица которой— квадратная пятого порядка: 0 0 «її «21 -Pi 0 0 «12 «22 —«11 0 0 Ьу — ^21 — «22 0 0 h ? Pi Рг 0 J 446 Поскольку эта матрица кососимметрическая, то из раздела 14.7 следует, что игра справедлива (цена игры равна нулю) и что оптимальной для обоих игроков является одна и та же смешанная стратегия у = = (2/1» Уъ> Уз» УьІ- Тогда в соответствии со свойством II раздела 14.7: I

<*1іУз + ЧхУь - РхУь < 0,) II Яі2Уз + а22У*- Р*Уь<°> I III

— аиг/і-а122/2 + b1y5<0, } (3> IV

-а2іУі-а22у2 +Ь2у5<0, V

АУх + р2у2 — Ьгуз - &2г/4 < 0.

Нули в правой части неравенств объясняются тем, что [игра справедлива (цена игры равна нулю).

Пусть уъф0. Но в соответствии со свойством (III) раздела'14.7 знак неравенства (<) в условии (V) системы неравенств (З)^означал бы, что для обоих игроков у6 = 0. Следовательно, условие Y [выражается равенством; (V) ргуг + р2у2 - Ъхуз - &2г/4 = 0.

Введем новые переменные:

Г—Ж ^ _ У* t _ Уз t _ 2/4

Тогда система неравенств (3) превращается в следующую систему: II

«12^1+«22^2 <Р2» III

dnxi + bv IV

«2Л + а22^2>&2» V

рххг + р2х2 = Ь&І + Ь212.

Здесь неравенства I —IV суть ограничения прямой и двойственной задачи линейного программирования (1).

Введем переменные z = ргхг + р2х2 и ? = Ъ+ Ь2?2 ДЛЯ любых стратегий, примененных двумя игроками, не обязательно оптимальных. Тогда условие (V) является утверждением, что если игроки применяют оптимальные стратегии, то z = Естественно предположить, что, если стратегии не являются оптимальными, z превышает то есть что z превышает (или по меньшей мере равен) свое оптимальное значение (то есть минимум), и что ? становится меньше (или по крайней мере равен) своего оптимального значения (то есть максимума). И действительно дело обстоит именно так, хотя это нелегко доказать математически (см. 15.4 и 15.5). Если же мы будем считать это предложение доказанным, то условие (V) можно истолковывать следующим образом. При оптимальной стратегии игры значение выражения z = p1x1 + p2x2 становится минимальным, а значение ? = = Wh + &2Б2 достигает максимальной величины, причем эти значения равны между собой.

Следовательно, решение игры (2) является решением как прямой, так и двойственной ей задачи линейного программирования (1). Можно сделать следующий вывод:

Игра, характеризуемая платежной матрицей (2), имеет оптимальное решение:

(Уі> У2» Уъ, Уы Уъ)• Если уъФ 0, то хх = уг/уь и х2 — у2/уъ есть решение прямой задачи линейного программирования (1), a h = y3/y5 и —уJyb —решение двойственной ей задачи.

В прямой и двойственной задачах (1) минимум z равен максимуму Этим мы достигаем двоякого результата. Во-первых, мы показываем, что прямая и двойственная задачи имеют одно и то же решение. Во-вторых, решение каждой из этих задач, можно получить на основе решения игры, характеризуемой некоторой заданной платежной матрицей.

Для этого уъ должно быть отличным от?нуля.

Пример

В задаче питания (см. 15.1 и 15.2) прямая и двойственная ей задача линейного программирования описываются следующими численными системами (при неотрицательных значениях х и |).

Минимизировать Максимизировать * = 6*i+21*,, C = 3g1 + 4glf-

при условии #1 + 2*2^3, <6, • (4)

*I+4*2^4. 2g1+4g2<21.J

Платежная матрица соответствующей игры имеет вид: (5) 0 0 1 1 — 6 0 0 2 4 — 21 —1 — 2 0 0 3 —1 —4 0 0 4 6 21 — 3 — 4 0 Решение задач (4) можно получить на основе матрицы (5), и наоборот. Необходимо лишь связать вероятности оптимальной стратегии уъ у2, у3, г/4, уь матрицы (5) с переменными * и | системы (4):

т -Уі т — 2/2 t Уъ г _ 2/4

1 — 77" » 2 — » 51 — —— > 52 — • У ь 2/5 Уъ 2/5

На этом простом примере можно продемонстрировать оба метода1 решения.

Первый метод решения. Решив систему (4) с помощью графических} методоо, описанных в разделах 15.1 и 15.2, получаем решение:

*і = 2; *2 = ~2 "> = у '» ?2=2"» 1

mm 2 = max ?—22 — .

Значит, в решении системы (5) должно соблюдаться соотношение:

13 9 2/1:2/2 : Уз • Уь : 2/5=2 : у : у : у :

Чтобы получить абсолютные значения уу необходимо лишь принять во внимание, что 2/1+У2+2/з+2/4+2/5 = 1; это—важнейшее свойство всякой стратегии. Нетрудно установить, что мы получаем абсолютные величины у, умножая на 2/19 элементы приведенного выше соотношения. Следовательно, решением игры (5) явится смешанная стратегия (4/І9, V19, 3/i9, 9/19, 2/19); цена игры равна нулю, игра справедлива.

Второй метод решения. Найти решение игры (5) можно с помощью метода, описанного в разделе 14.8. Если (уъ г/2, y3t 2/4, уъ) является оптимальной стратегией для каждого из игроков, причем цена игры равна нулю, то:

2/1+ 2/2+ 2/з+ 2/4+ 2/5 = 1, 2/з+ 2/4— 62/5 < О, 22/3+42/4—21у6< О, —

2/1— 2?/2 + З2/5 < О, —

2/1— + 42/5 < О, §Уі + 2І2/2 — Зг/з — 4^4 <0. Проверим, можно ли заменить все неравенства равенствами при положительных значениях у.

3 9 2/3*2/4:2/5=-^ : у :

Решаем совместно четвертое и пятое уравнения:

1

УІ'У2'Уь = 2: J-'- 1• .

Затем определяем абсолютные значения у, используя полученные соотношения совместно с первым уравнением системы; эти значения равны (4/I9, 1/i9, 3/1Э, 9/19, 2/19)- Если это и есть решение игры (5), то полученные значения у должны удовлетворять последнему уравнению системы. Легко проверить, что это действительно так. Следовательно, мы получили решение игры (5). На его основе получаем решения системы (1):

_9. „ 1 . t _ 3 . t _ 9 xi — А х2 — "2"» 5i — у J Ь2 — ~2 •

Первые две величины минимизируют z (г = 227г пенсов), вторые максимизируют С (? = 2272 пенсов).

Задачи и упражнения 1.

Записать упражнение 5 раздела 15.1 с помощью буквенных обозначений:

Минимизировать z=рххг -f- prfc*,

при условии

ЯіЛ+ЯігЯг^Ьі,

аЧ\х\ а22х2 ^ &2»

Затем сформулировать двойственную задачу с теми же постоянными коэффициентами. В примере, приведенном в тексте данного раздела, матрица коэффициентов [arsl квадратная, а в данной задаче прямоугольная. Какое влияние это оказывает на симметричность прямой и двойственной задач? 2.

Построить платежную матрицу игры, соответствующую предыдущей задаче линейного программирования. Показать, что это — квадратная матрица, порядок которой равен 6. Почему матрица игры продолжает оставаться квадратной, хотя матрица коэффициентов [ars] является прямоугольной? 3.

Найти решение игры, приведенной в предыдущем упражнении, но с численными коэффициентами, взятыми из упражнения 5 раздела 15.1 Таким путем проверить правильность общего решения этого упражнения. Решить также двойственную задачу и сравнить полученный результат с решением упражнения 4 раздела 15.2, где графическое решение оказалось невозможным. 4.

Сформулировать в буквенных коэффициентах прямую и двойственную задачи упражнения 6 раздела 15.1; построить платежную матрицу соответствующей игры. Показать, что эта матрица аналогична матрице упражнения 2 настоящего раздела.