Двойственность в линейном программировании и теория матричных игр

Московский государственный технический университет
имени Н. Э. Баумана
Н. С. Васильев, В. В. Станцо
Двойственность в линейном программировании
и теория матричных игр
Рекомендовано Научно-методическим советом МГТУ
им. Н. Э. Баумана в качестве учебного пособия
Под редакцией Р. С. Исмагилова
Москва
Издательство МГТУ им. Н. Э. Баумана
2010

УДК 51
ББК 22.18
В19
Рецензенты: Г. С. Дерябина, В. Г. Ушаков
Васильев Н. С.
В19
Двойственность в линейном программировании и теория матричных игр : учеб. пособие / Н. С. Васильев, В. В. Станцо. — М. :
Изд-во МГТУ им. Н. Э. Баумана, 2010. — 45, [3] с. : ил.
Изложены основные понятия и методы, применяемые в исследовании операций. Разобраны примеры задач о принятии решений в условиях
неопределенности. Представлен набор упражнений для самостоятельной
работы студентов и проведения семинарских занятий.
Для студентов факультетов ИБМ и ФН МГТУ им. Н. Э. Баумана.
УДК 51
ББК 22.18
c
⃝МГТУ им. Н. Э. Баумана, 2010

Введение
В исследовании операций изучаются вопросы принятия решений
в организационных задачах, относящихся к сфере экономики, техники, военного дела. При этом лицо, принимающее решение (ЛПР),
должно учесть неконтролируемые факторы — случайные (природные) воздействия или целенаправленные, активные действия других
участников операции.
Линейное программирование (ЛП) — раздел исследования операций, в котором изучаются линейные оптимизационные задачи [1–3].
Каждой такой задаче отвечает двойственная задача. Можно считать,
что, например, в задаче, двойственной к задаче ЛП «Планирование
производства», имеется второй участник операции — рынок, описываемый с помощью теневых цен — двойственных переменных [4–7].
Теория игр — раздел исследования операций, в котором изучаются процессы принятия решений в условиях конфликта [1, 4].
Простейшими моделями конфликтых ситуаций могут служить игры
«Камень — ножницы — бумага» или «Чет-нечет». Методы решения
подобных задач основаны на применении ЛП. Принимающий решение субъект (игрок) располагает информацией о множестве возможных ситуаций, в одной из которых он находится. Игрок может выбирать стратегию на основании заданной совокупности ситуаций,
стремясь увеличить количественную меру выигрыша, получаемого
в зависимости от ситуации. Все игроки (за исключением игрока —
природы) действуют разумно. Главный вопрос теории игр: какими принципами выбора стратегии руководствоваться в условиях
неопределенности, ведь действия остальных участников конфликта,
порождающие ту или иную ситуацию, не известны. Оказывается,
что в игре не всегда целесообразно применять одно и то же решение (чистую стратегию) — во многих случаях лучше использовать
вероятностное поведение (смешанную стратегию) [4, 8].
3

Антагонистическими называются игры двух игроков, интересы
которых прямо противоположны. Во многих общественных процессах затрагиваются не совпадающие, но и не противоположные
интересы участников. Изучением таких явлений занимается теория
неантагонистических игр. Ее цель — выработка способов принятия
решений участниками игры.
Теория неантагонистических игр указала на отсутствие единого и объективного понятия оптимальности выбора стратегий
и на невозможность полной формализации этого процесса. В этом
ее существенное отличие от теорий математического программирования и антагонистических игр, где оптимальность выбора понимается однозначно и выражается точками экстремума (седловыми
точками) целевых функций.
В пособии изложены основные результаты теории исследования
операций. Рассмотрено много примеров решения задач, предложено
около 60 упражнений разной степени трудности для самостоятельной работы.
Некоторые задачи целесообразно разобрать на семинарах, например задачу «Планирование производства». Ее различные формулировки встречаются во всех главах пособия. Эти обобщения
связаны с необходимостью учета неопределенных факторов, присущих указанной экономической операции.
Решение текстовых задач, содежащихся в пособии, развивает
навыки формализации изучаемых операций с целью последующего
применения математического аппарата*.
*Авторы весьма признательны старшему научному сотруднику кафедры ВМиК
МГУ им. М. В. Ломоносова В. И. Громыко за помощь в оформлении пособия.
4

1. Двойственность в линейном
программировании
Задачей линейного программирования (ЗЛП, [2, 3]) называется
такая задача математического программирования:


f
 f
x

 extr
f
x: x
 D
,
(extr означает максимум или минимум в зависимости от постановки задачи [2, 3]), где в условиях задачи:
• допустимое множество D точек (векторов) в арифметическом
линейном пространстве задается системой линейных ограничений (уравнений и нестрогих неравенств);
• целевая функция f
x1, x2, ... , xn
 линейна.
Оптимальным решением оптимизационной задачи называется
элемент x
.
ЗЛП называется стандартной, если все ограничения имеют вид
неравенств и на все переменные xi наложены условия xi
 0.
Пример 1.1. Задача «О наилучшем использовании ресурсов».
Предприятие выпускает n видов продукции, используя m видов
ресурсов. Затраты i-го ресурса на производство единицы продукции j-го вида равны aij. Запасы i-го ресурса равны bi. Прибыль
от реализации единицы продукции j-го вида равна cj. Составить
оптимальный план производства.
Формализация. Введем переменные xj — количество производимой продукции j-го вида. Оптимальный план максимизирует
суммарную прибыль, которая равна c1x1
 ...
 cnxn. Затраты i-го
ресурса на производство всей продукции j-го вида равны aijxj.
Общий расход i-го ресурса равен ai1x1
 ...
 ainxn и не должен
превышать bi. Таким образом, приходим к следующей стандартной
5