ГЛАВА XIV. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

В этой главе мы разберем особые типы задач на отыскание минимума или максимума, а именно так называемые задачи линейного программирования, которые часто встречаются в экономике и тесно связаны с теорией игр. Мы начнем с примера. Пусть некий человек Смит обнаружил, что для того, чтобы быть здоровым, ему необходимо принимать по меньшей мере единиц составного химического вещества (витамина или некоторой соли) и по меньшей мере единиц составного химического вещества . Допустим, далее, что он не может покупать или в чистом виде, но может покупать лекарство по центов за унцию, причем каждая унция содержит единиц вещества единиц вещества и может также покупать лекарство по центов за унцию, причем каждая унция содержит единиц вещества единиц вещества Смиту надо решить, какие относительные количества лекарств ему нужно покупать ежедневно, чтобы получить требуемое количество веществ по минимальной стоимости. Если Смит покупает унций лекарства унций лекарства , то это будет ему стоить

и он получит количества веществ соответственно

и

Следовательно, он хочет выбрать такие неотрицательные чтобы они удовлетворяли неравенствам

и чтобы одновременно величина

была возможно меньше.

При данных числовых значениях параметров эту задачу можно решить простыми методами аналитической геометрии. Так, например, допустим, что

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

пару , для которой линейная форма

имеет минимум. Мы проводим прямые

и

как показано на рис. 50, и заключаем, что пары удовлетворяющие данным неравенствам, суть координаты точек заштрихованной области рисунка. Мы проводим также семейство параллельных прямых

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

проходила через А — точку пересечения прямых

Решая совместно эти два уравнения, мы находим:

Итак, самый дешевый курс лечения получается в том случае, если брать по 5/2 унции лекарств при этом необходимое количество веществ будет получено за

Рис. 50.

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

В этом случае оказывается, что самая дешевая комбинация лекарств получается, если взять в качестве пар координаты точки В на рис. 50, то есть если взять . Тогда Смит получит самое дешевое требуемое лечение, покупая лишь но совсем не покупая ; при этом он за

получает единиц вещества

и единиц вёщества

Заметим, что обычные способы отыскания максимумов и минимумов с помощью дифференциального исчисления мало помогают при решении задач, подобных описанной выше. Это объясняется тем, что минимальные или максимальные значения функций достигаются в точках границы заштрихованной области, а не в тех точках, где производные равны нулю.

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

Так возник особый раздел математики, который называется линейным программированием. Под задачей линейного программирования понимается задача отыскания минимального или максимального значения линейной функции, когда переменные подчиняются линейным неравенствам. Общую задачу линейного программирования можно сформулировать следующим образом: выбрать рреди -мерных векторов , удовлетворяющие неравенствам

-мерный вектор для которого достигается минимум или максимум линейной функции

Мы не дадим какой-либо общей теории линейного программирования, так как это находится вне рамок настоящей книги, а ограничимся указанием некоторых связей между этим вопросом и. теорией игр. Мы увидим, что задачу решения произвольной прямоугольной игры можно рассматривать как особую задачу линейного программирования, и обратно, многие задачи линейного программирования можно привести к задачам теории игр.

Но прежде чем приступить к рассмотрению связи между линейным программированием и теорией игр, сделаем несколько очевидных замечаний о существовании решений задач линейного программирования.

Прежде всего очевидно, что задача линейного программирования не обязательно должна иметь решение. Может оказаться, например, что данные неравенства несовместимы. Так, не имеет решения, задача отыскания минимума функции

при соблюдении неравенств

Но даже в случае совместности неравенств задача может не иметь решения вследствие неограниченности множества точек, координаты которых удовлетворяют данным неравенствам. Так, не имеет решения задача отыскания минимума функции

при соблюдении неравенств

С другой стороны, задача линейного программирования может иметь больше одного решения. Так, любая пара является решением задачи отыскания минимума функции

при соблюдении неравенств

Легко показать, что любая выпуклая линейная комбинация решений задачи линейного программирования также есть решение; поэтому, если задача линейного программирования имеет больше одного решения, то она имеет бесконечное число решений.

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

при соблюдении равенств

очевидно, равнозначна задаче отыскания минимума функции

при соблюдении неравенств

эта задача уже является задачей линейного программирования.

Мы покажем теперь, что решение произвольной прямоугольной игры можно свести к решению задачи линейного программирования. Разберем эту задачу для игры с матрицей 3x2 (это ограничение мы налагаем лишь для упрощения обозначений; в случае игры исследование аналогично).

Пусть матрица игры такая:

и v — цена игры.

Цена v есть наименьшее число z такое, что для некоторого элемента множества

а по теореме 2.10 стратегия оптимальна для тогда и только тогда, когда удовлетворяют неравенствам (1), с заменой на . Но, очевидно, три числа удовлетворяют неравенствам (1) тогда и только тогда, когда имеются такие неотрицательные числа , что

то есть такие, что

Итак, рассматривая систему

мы видим, что у есть наименьшее значение 2, которое определяется некоторыми числами , удовлетворяющими системе (2). Далее, стратегия оптимальна для тогда и только тогда, когда (для некоторых ) удовлетворяют системе (2) при замене z на v. Итак, задача отыскания цены игры и оптимальных стратегий для игрока сводится к решению системы (2) как задачи линейного программирования. Подобным же образом мы можем решить задачу отыскания оптимальных стратегий для игрока ; в этом случае задача линейного программирования представляет задачу отыскания максимума некоторой величины.

Таким образом, мы нашли, что задача решения произвольной прямоугольной игры может быть приведена к линейному программированию особой формы:

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

Для задачи линейного программирования, заданной системой (3), матрица игры, при условии, что мы хотим свести к минимуму величину z, будет такова:

Можно теперь показать, что справедливо следующее предложение: задача линейного программирования, заданная системой (3), имеет решение тогда и только тогда, когда в игре с матрицей В есть оптимальная стратегия такая, что ; далее, если оптимальная стратегия игры такая, что и если мы положим

и

то и z представляют решение задачи линейного программирования;

Библиографические замечания

Доказательство равнозначности задачи решения игры с задачей линейного программирования смотрите в работах Данцига [24] или Гейля, Куна и Танкера [41]. Другие выводы, связанные с теорией линейного программирования, смотрите в работах Данцига [23], [25] и [26] и Данцига и Вуда [27].