Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ГЛАВА XIV. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕВ этой главе мы разберем особые типы задач на отыскание минимума или максимума, а именно так называемые задачи линейного программирования, которые часто встречаются в экономике и тесно связаны с теорией игр. Мы начнем с примера. Пусть некий человек Смит обнаружил, что для того, чтобы быть здоровым, ему необходимо принимать по меньшей мере
и он получит количества веществ
и
Следовательно, он хочет выбрать такие неотрицательные
и чтобы одновременно величина
была возможно меньше. При данных числовых значениях параметров эту задачу можно решить простыми методами аналитической геометрии. Так, например, допустим, что
Тогда нам нужно выбрать из пар чисел
пару
имеет минимум. Мы проводим прямые
и
как показано на рис. 50, и заключаем, что пары
для разных значений
проходила через А — точку пересечения прямых
Решая совместно эти два уравнения, мы находим:
Итак, самый дешевый курс лечения получается в том случае, если брать по 5/2 унции лекарств
Рис. 50. Нужно заметить, что при некоторых значениях В этом случае оказывается, что самая дешевая комбинация лекарств получается, если взять в качестве пар
получает единиц вещества
и единиц вёщества
Заметим, что обычные способы отыскания максимумов и минимумов с помощью дифференциального исчисления мало помогают при решении задач, подобных описанной выше. Это объясняется тем, что минимальные или максимальные значения функций достигаются в точках границы заштрихованной области, а не в тех точках, где производные равны нулю. Наконец, следует заметить, что примененный нами геометрический способ решения задачи был бы чрезвычайно громоздким при решении задач с большим числом переменных. Так, например, если бы нужно было сделать выбор из шесзчи лекарств, а не из двух, то при этом способе нужно было бы рассматривать области шестимерного пространства. Поскольку задачи такого рода очень важны (они возникают, например, при составлении графика движения товарных поездов, перевозящих данное количество товаров при минимальных затратах или в минимальное время), необходимо иметь общие методы их решения.. Так возник особый раздел математики, который называется линейным программированием. Под задачей линейного программирования понимается задача отыскания минимального или максимального значения линейной функции, когда переменные подчиняются линейным неравенствам. Общую задачу линейного программирования можно сформулировать следующим образом: выбрать рреди
Мы не дадим какой-либо общей теории линейного программирования, так как это находится вне рамок настоящей книги, а ограничимся указанием некоторых связей между этим вопросом и. теорией игр. Мы увидим, что задачу решения произвольной прямоугольной игры можно рассматривать как особую задачу линейного программирования, и обратно, многие задачи линейного программирования можно привести к задачам теории игр. Но прежде чем приступить к рассмотрению связи между линейным программированием и теорией игр, сделаем несколько очевидных замечаний о существовании решений задач линейного программирования. Прежде всего очевидно, что задача линейного программирования не обязательно должна иметь решение. Может оказаться, например, что данные неравенства несовместимы. Так, не имеет решения, задача отыскания минимума функции
при соблюдении неравенств
Но даже в случае совместности неравенств задача может не иметь решения вследствие неограниченности множества точек, координаты которых удовлетворяют данным неравенствам. Так, не имеет решения задача отыскания минимума функции
при соблюдении неравенств
С другой стороны, задача линейного программирования может иметь больше одного решения. Так, любая пара
при соблюдении неравенств
Легко показать, что любая выпуклая линейная комбинация решений задачи линейного программирования также есть решение; поэтому, если задача линейного программирования имеет больше одного решения, то она имеет бесконечное число решений. Наконец, следует указать, что многие задачи, с первого взгляда не являющиеся задачами линейного программирования, можно легко преобразовать в задачи этого типа. Так, задача отыскания минимума функции
при соблюдении равенств
очевидно, равнозначна задаче отыскания минимума функции
при соблюдении неравенств
эта задача уже является задачей линейного программирования. Мы покажем теперь, что решение произвольной прямоугольной игры можно свести к решению задачи линейного программирования. Разберем эту задачу для игры с матрицей 3x2 (это ограничение мы налагаем лишь для упрощения обозначений; в случае игры Пусть матрица игры такая:
и v — цена игры. Цена v есть наименьшее число z такое, что для некоторого элемента
а по теореме 2.10 стратегия
то есть такие, что
Итак, рассматривая систему
мы видим, что у есть наименьшее значение 2, которое определяется некоторыми числами Таким образом, мы нашли, что задача решения произвольной прямоугольной игры может быть приведена к линейному программированию особой формы:
(В только что рассмотренной игре мы имели Для задачи линейного программирования, заданной системой (3), матрица игры, при условии, что мы хотим свести к минимуму величину z, будет такова:
Можно теперь показать, что справедливо следующее предложение: задача линейного программирования, заданная системой (3), имеет решение тогда и только тогда, когда в игре с матрицей В есть оптимальная стратегия
и
то Библиографические замечанияДоказательство равнозначности задачи решения игры с задачей линейного программирования смотрите в работах Данцига [24] или Гейля, Куна и Танкера [41]. Другие выводы, связанные с теорией линейного программирования, смотрите в работах Данцига [23], [25] и [26] и Данцига и Вуда [27].
|
1 |
Оглавление
|