<<
>>

15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ

Теперь можно обобщить результаты, полученные в разделе 15.3, где решение простой задачи линейного программирования было сведено к решению некоторой задачи игры. Этот метод разработан Данцигом и приведен в [9, гл.
XX]; он кладет в основу сформулированную выше основную теорему двойственности. Метод основан на следующем положении.

Всякая задача линейного программирования (минимизировать выражение z = р'х при условии Ах>Ь и х>0) совместно с двойственной ей задачей (максимизировать выражение ? = при условии А|<р и ?>0) может быть сведена к некоторой игре с двумя участниками и нулевой суммой; и обратно, всякая игра с двумя участниками и нулевой суммой может быть представлена в форме некоторой задачи линейного программирования.

Во-первых, докажем прямую посылку. Предположим, что решение задачи линейного программирования существует, так что й минимум z и максимум ? равны одной и той же величине М. При допустимых значениях х и g удовлетворяются обе системы неравенств:

Ах>Ь и А'|< р.

Запишем эти неравенства в развернутом виде: (1)

а11Х1 + Ч&2 + • • • + «і А > bv а21х1 + а22х2 + . . . + а2пхп > 62, auh + Я21?2 + ... + ат11т < р„ alill+a22l2 + • • • +ат?т<Р2> ат1Х1 + ат2х2 + • • • + атпхп > Ът> аігЛі + а2п%2 + ? • - + тгЛт < Рп ? -

При оптимальных допустимых значениях переменных z = ? = Д/. Следовательно, z—? = 0:

РА + Р2Х«+••• + Рпхп - (hli + Ь2І2 + • • ? + КЪы) = 0. (2)

Введем в систему (1) «фиктивную» переменную и {и — 1) и преобразуем неравенства так, чтобы в правой части каждого из них появились нули, и все неравенства имели в правой части «<0». Тогда (1) и (2) в совокупности образуют систему:

allh + <*21І2 + • • • Jr^mllm - Plu < 0, аі2%1 + 0>22І2 + • - - + ат2Іт ~ Pa" < аі*Лі + а2пІ2 +

? +атЛт— Рпи<°>

(3>

+ b1u<.0, I, ? Я21*^1 &22Х2 ' + bmu< 0, . =0.

• • - Kir,

Pixi + P&t +

+ Рпхп- bih-hh.

~ 451 В соответствии со свойством II раздела 14.7, система (3) означает, что элементы решения

(х„хг% Б1в Ее, - -- .Em, и), (4)

пропорциональны вероятностям оптимальной стратегии игры, платежная матрица которой кососимметрическая: 0 asr 1

2

J — Ps і n строк (s= 1, 2, . — ars 0 Ьг m строк (r = 1, 2,.. ,,m) Ps -Ьг 0 1 строка п т 1

столб- столб- стол- цов цов бец (5 = 1, 2, . .п) (г = 1, 2, . . .,го).

Эту блочную матрицу можно записать более сжато: 0 A' -P" -A 0 b P' -b' 0 _ Цена игры равна нулю, о чем свидетельствуют кососимметричность матрицы (5) и нулевые значения правых частей неравенств системы (3). Оба игрока имеют одну и ту же оптимальную стратегию, однако элементы (4) только пропорциональны элементам стратегии, так как необходимо изменить шкалу их так, чтобы сумма абсолютных величин была равна 1. Вместе с тем система (3) является однородной относительно всех переменных, так что изменение шкалы абсолютных значений роли не играет. Последнее условие системы (3) есть равенство, поскольку мы предположили существование решения задачи (1) и поскольку ифО. Следовательно, если задача линейного программирования имеет решение, то игра с платежной матрицей (5) имеет оптимальную стратегию с ненулевым последним элементом и, и задача линейного программирования и задача игры соответствуют друг другу. Можно снять сделанное нами здесь ограничение, допустив как отсутствие решения задачи линейного программирования, так и возможность нулевого значения последнего элемента оптимальной стратегии игры. Это завершает доказательство. Обобщим полученные результаты: задача линейного программирования связана с игрой, имеющей платежную матрицу (5). Оптимальная стратегия этой игры должна существовать и определяется вектором (4). Если и = О, задача линейного программирования решения не имеет. Если и Ф 0, можно пропорционально изменить абсолютные значения элементов решения (4) так, чтобы и = 1; тогда значения х и ? и явятся решением прямой и двойственной ей задачи линейного программирования.

Во-вторых, докажем обратную посылку теоремы.

Пусть игра характеризуется платежной матрицей С = [crs] порядка т X п. Если первый (максимизирующий) игрок применяет смешанную стратегию (zt, z2,..., zn),

т

то математическое ожидание его выигрыша есть М = min 2crszr» и игрок

S Г=1

т

стремится максимизировать М. Поэтому 2crszr>M для каждого s.

г= 1

В матричных обозначениях это записывается следующим образом:

Cz>M{l},

или

Сх>{1}, где х = .

Всегда можно преобразовать это выражение так, чтобы выполнялось неравенство М > О (например, прибавляя к каждой crs постоянную величину). Мы налагаем следующие ограничения: (I) z>0, а поэтому и х>0;

т т

(II) = 1» а поэтому == или же = один

г=1 г=1

из игроков достигает максимума М, он применяет оптимальную стратегию. Тогда минимизируется [1]х = ИМ. Следовательно, оптимальная стратегия игры определяется вектором х, при котором минимизируется

при условии

Сх>{<1},

и

х> 0.

Это — задача линейного программирования с технологической матрицей С и двумя заданными (единичными) векторами. Оптимальная стратегия второго (минимизирующего) игрока приводит ко второй задаче линейного программирования — двойственной. Это завершает доказательство.

Значение полученного результата заключается в том, что метод решения игровой задачи одновременно позволяет решить и задачу линейного программирования, и наоборот, метод решения задачи линейного программирования дает возможность решить также и игровую задачу. Далее, как указали Дорфман, Самуэльсон и Солоу [7], любую задачу игры можно представить в виде задачи линейного программирования, а последнюю, в свою очередь,— в виде игры, матрица которой кососимметрическая. Таким образом, любую игру можно преобразовать в игру с кососимметрической матрицей, то есть в справедливую игру, с одинаковыми оптимальными стратегиями обоих игроков. Это является значительным преимуществом.

Остается разработать более универсальный метод решения задач линейного программирования и, следовательно, задач из области игр.

Таким методом является симплексный метод, который по сути дела представляет собой итеративный метод практического выполнения вычислительных операций на автоматических вычислительных машинах. Как указывается в [9], возможны и другие методы, однако, по-видимому, из существующих в настоящее время вычислительных методов симплексный метод пока является наилучшим.

Задачи линейного программирования и задачи игры эквивалентны с точки зрения формальной алгебры, что позволяет расширить возможности решения подобных задач. Однако эти задачи не обязательно эквивалентны с точки зрения их интерпретации. Два участника игры и не помышляют о том, чтобы решать своей игрой задачи линейного программирования. Если же ставится задача линейного программирования, как, например, задача питания, это вовсе не значит, что на самом деле имеется игра с двумя участниками. Правда, в этой задаче можно считать первым «игроком» потребителя, минимизирующего стоимость питания, а его противником, вторым «игроком», природу, столь скупо отпускающую необходимые питательные вещества. Однако такое толкование настолько далеко выходит за рамки понятия «игры», что является искусственным.

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ:

  1. 14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ
  2. ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  3. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  4. 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
  5. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  6. 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  7. 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
  8. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  9. 15.8. СИМПЛЕКСНЫЙ МЕТОД
  10. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  11. 16.1. ВВЕДЕНИЕ. ОБЩЕЕ ЭКОНОМИЧЕСКОЕ РАВНОВЕСИЕ
  12. 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
  13. 16.9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ; МОДЕЛЬ РОСТА НЕЙМАНА
  14. 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
  15. 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ