Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 13

Следовательно, значение матричной игры (3.2.14) неотрица- тельно. Кроме того, если это значение равно нулю, то для всех оптимальных стратегий з игрока И мы должны иметь з„+, — — О. Из теорем И. 4.4 и И. 4.6 следует, что игрок 1 должен иметь та- кую стратегию 1 = (1ь..., ! ), что т ~~~~ ( — ап) г! ) О, / = 1, ..., и, ! ! ~ сА) О. ! ! По предположению, задача (3.2.1) — (3.2.3) допустима. Пусть х = (хь...,х ) принадлежит ее допустимому множеству. Тогда 63 111. 2 Двойетвенноете для любого положительного числа а вектор х+ се! также будет принадлежать этому допустимому множеству.

Кроме того, (х+ а1) Ст = «Ст+ а1Ст и правая часть этого равенства может быть сделана произвольно большой за счет увеличения а. Значит, задача (3.2.1) — (3.2.3) неограниченна. Таким образом, для пары двойственных задач (3.2,1) †(3.2.3) и (3,2,4) — (3.2.6) возможны четыре варианта. Либо обе задачи являются недопустимыми, либо одна задача недопустима, а другая неограниченна, либо обе допустимы и ограниченны. В последнем случае тот факт, что допустимое множество замкнуто, позволяет утверждать, что обе задачи будут иметь решения.

Следующая очень важная теорема поясняет соотношение между ними в этом последнем случае. 1!!.2.6. Теорема. Пусть обе двойственные задачи (3,2.!)— (3.2.3) и (3.2.4) — (3.2.6) являются допустимылш. Тогда обе они имеют решения х' и у* соответственно и, кроме того, х*Ст = Ву', т. е. обе задачи имеют одно и то же значение. До к аз а тел ьств о. Рассмотрим игру с матрицей М= — А': О':. Ст где О представляет собой матрицу соответствующих размеров, все элементы которой равны нулю. Матрица М кососимметрическая; следовательно, значение игры равно нулю. Предположим теперь, что з = (зь..., з„,+„+1) — оптимальнан стратегия для игрока 1. Положим у = (з~ ...

зв) х = (з„+„..., з„+ ), Ш = зв.ке+~ Ввиду оптимальности з и того, что значение игры равно нулю, мы получаем — хА +шВ~О, уАт — шС ~ Π— уВт+,Ст ~ О. Гл, В!. Линейное программирование Пусть гв ) О. Если положить х* = х/тв и у' = д/ш, то ясно, что х'А~В, Ат~С х*, у*= О х"Ст ~ у*Вт. Это означает, что х* и у" принадлежат допустимым множествам для задач (3.2.1) — (3.2.3) и (3.2.4) — (3.2.6).

Из теоремы П1.2.1 и следствия П1. 2.2 получаем, что х* и у* являются решениями этих двух задач и, кроме того, х*Ст = у'Вт. Предположим теперь, что ии для какой оптимальной стратегии э игрока 1 не имеет место неравенство э +„ег ) О. В этом случае по теореме П. 4.4 игрок П имеет оптимальную стратегию г= (г„...

...,г +н+г), скалярное произведение которой с последней строкой матрицы М отрицательно. Так как оба игрока имеют одинаковые множества оптимальных стратегий, мы должны иметь г +„+, — — О, Если положить теперь у=(г„..., г„), х = (г„+, > ...> гм+н), то — хА~ О, уАта о — уВт+ хСт > О, или, равносильно, хА~О, уАт) О хСт) дВт.

13.2.15) В неравенстве (3.2.15) либо левая часть положительна, либо правая часть отрицательна. допустим, что левая часть положительна. По предположению, задача (3.2.1) — (3.2.3) допустима; пусть х' принадлежит ее допустимому множеству. Легко видеть, что х'+ ах для любого положительного се также принадлежит допустимому множеству и (х'+ ах)Ст может быть сделано произвольно большим при возрастании а. Значит, задача (3.2.1)— (3.2.3) неограниченна. Но это означает, что задача (3.2.4) — (3.2.6) недопустима.

Аналогично, если правая часть (3.2.15) отрицательна, то задача (3.2.4) — (3.2.6) неограниченна, а задача (3.2.1)— (3.2.3) недопустима. Полученное противоречие доказывает теорему. 65 /П.8. Решение задач линейного нрограммированин 1Н. 3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЕРОГРАММИРОВАНИЯ На первый взгляд может показаться, что задачи линейного программирования можно решать методами математического анализа, полагая частные производные равными нулю. Однако на самом деле целевая функция линейна, так что все ее частные производные постоянны; решение задачи линейного программирования будет находиться на границе допустимого множества.

Метод, который обычно используется для решения задач линейного программирования, основывается на следующих соображениях. (3.3.!) Допустимое множество является пересечением нескольких полупространств; так как каждое полупространство выпукло, допустимое множество оказывается выпуклым многогранником. (3.3.2) Таккакдопустимое множество выпукло, а целевая функция линейна, любой локальный экстремум целевой функции будет глобальным экстремумом. (3.3.3) Так как целевая функция линейна, экстремум будет достигаться в одной из крайних точек (вершин) допустимого множества (многогранника) . С геометрической точки зрения симплекс-метод может быть описан следующимобразом. Находится одна из вершин многогранника (это можно сделать и аналитически, решая систему и уравнений, задаваемых ограничениями).

Затем рассматриваются все ребра, сходящиеся в этой вершине. Если целевая функция не может быть улучшена при передвижении вдоль любого из этих ребер, то данная вершина является локальным экстремумом, а следовательно (на основании замечания (3.3.2)), и глобальным экстремумом. Если же целевая функция улучшается вдоль одного из ребер, то мы переходим по этому ребру к вершине, расположенной на другом его конце, и повторяем этот процесс. Так как целевая функция на каждом шаге улучшается, через одну и ту же вершину нельзя пройти дважды. Йо поскольку имеется лишь конечное число вершин, этот процесс через конечное число шагов приведет нас к решению. 111.

3.1. П р и м е р. Поясним эту идею на примере: максимизировать ш = 2х + у х(1, при условиях у(1, 2х + 2у ~ 3, х, уй.О. 3 зак. 8зз Ге. 01. Линейное нрогроммировоние Допустимое множество на рис. Ш.З.! затенено. Стрелка указывает градиент целевой функции. Если начинать из начала координат, то мы видим, что ш возрастает вдоль любого начинающегося в нем ребра.

Возьмем, например, ребро, идущее к (1,О). В точке (1,О) мы находим, что ш возрастает вдоль ребра, идущего в точку (0,1) 1,О) (0,0) Р и е. П!. 3.1. (1, '/в). В этой точке находим, что ш убывает вдоль обоих сходящихся в ней ребер. Поэтому можно заключить, что точка (1, ~/в) является решением нашей задачи. 1Н. 4. АЛРОРИФМ СИМПЛЕКС-МЕТОДА Теперь опишем указанный выше метод алгебраически. Введем одно схематическое обозначение, чтобы добиться некоторого упрощения символики. Пусть дана система неравенств а„х, +анхо+ ... +а,х„~ Ь„ амх, +амх,+ ... + а,х Я Ьм (3.4.1) . а,„х, + ае„х, + ... + а „х„ ~ Ь„, которая вместе с обычными ограничениями неотрицательности ха- рактеризует допустимое множество некоторой задачи линейного программирования.

Эту систему можно переписать в виде анх, +а„х,+ ... +а,х — Ь,= — иь а их, + амх, + ... + а„„х,„— Ье = — ит, (3.4.2) а„,х, +агнхе+ ... +а „х — Ь„= — и„, 7!/. 4. Алеорифм симплекс-метода 67 = — и, (3.4.3) Итак, каждая строка внутри рамки этой схемы представляет линейное уравнение, которое получается в результате умножения каждого элемента строки на элемент, расположенный над строкой (вне рамки) и соответствующим столбцом; полученная сумма затем приравнивается элементу,' стоящему вне рамки справа. Главное преимущество такой схемы, как отмечалось выше, состоит в том, что она позволяет избежать повторения переменных хь ...

..., х и тем самым упрощает запись. Можно также ввести в схему (3.4,3) и целевую функцию, обозначая ее, например, через тс и приписывая ее к схеме, т. е. добавляя внизу строку с~ сг... с О ~='тс. (3.4.4) Если сделать все это, то можно видеть, что схему, соответствующую задаче линейного программирования (3.2.1) — (3.2.3), можно также использовать для получения двойственной задачи (3.2.4) — (3.2.6), Действительно, для представления уравнений системы (3.2.5) можно использовать столбцы.

В результате мы получаем двойную схему х, х, ... х 1 ь, Ьг У~ Уг аь аг> ап ан ... а„, аг а„...ат а,„аг„... а „ (3.4.5) Уп — Ь„ — 1 с, с, ...с„ ! ! о! ог опт которая описывает две двойственные (3.2.4) — (3.2.6) одновременно. ат' задачи (3.2.1) — (3.2.3) и где ав 1 = 1, ..., л, — так называемые свободтсьте переменные, подчиненные условию неотрицательности. Ограничения (3.4.1) сведены теперь к этой системе уравнений вместе с ограничениями неотрицательности х,~О, ит~О. Мы будем отождествлять систему уравнений (3.4.2) со схемой Х, Хг ...