Лекция: Общее правило построения двойственной пары.

К пяти признакам сформулированным ранее, необходимо добавить следующие:

1) в исходной ограничения неравенства следует записывать со знаком, если целевая функция стремится к минимуму, и со знаком, если целевая функция стремится к максимуму;

2) каждому ограничению неравенства исходной задачи соответствует в двойственной задаче условие не отрицательности переменных ;

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

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

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

Сведение матричной игры к двойственной задаче линейного программирования.

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

Соотношениям отыскания и можно поставить в соответствие эквивалентные им задачи

(7.1)

Здесь есть математическое ожидание выигрыша первого игрока.

Тогда для любой чистой стратегии y(j) игрока В

можно записать

, (7.2)

а для любой чистой стратегии x(i) игрока А

можно записать

. (7.3)

Следовательно, задачи (7.1) – (7.3) допускают следующую запись в форме задач линейного программирования

, (7.4)

. (7.5)

Нетрудно видеть, что задачи (7.4) и (7.5) взаимно двойственные, а поэтому их оптимальные значения должны совпадать, т.е., где V – цена игры (требуемое значение эффективности).

Для задачи (7.4) положим и, (7.6)

а для задачи (7.5) положим и. (7.7)

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

минимизировать линейную функцию

(7.8)

при условиях

,;,, (7.9)

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

максимизировать линейную функцию

(7.10)

при условиях

,;,. (7.11)

Исходя из основной теоремы теории двойственности, задачи (7.8) – (7.11) имеют конечное решение и .

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

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

По данным наблюдений за предшествующие одиннадцать лет предприятие в течение апреля – мая в условиях тёплой погоды может реализовать 600 костюмов, 2000 платьев и 300 плащей, в условиях прохладной погоды – 1000 костюмов, 500 платьев и 800 плащей и в условиях обычной погоды 800 костюмов, 1100 платьев и 600 плащей. Затраты на единицу продукции в течение указанных месяцев составили для костюмов 30 ден. ед., для платьев 10 ден. ед. и плащей 15 ден. ед., а цена реализации равна соответственно 50 ден. ед., 20 ден. ед. и 28 ден. ед.

Задача заключается в максимизации средней величины прибыли от реализации выпущенной продукции с учётом неопределённости погоды в рассматриваемые месяцы.

Подобная задача рассматривается как игра с природой. Её отличительная особенность состоит в том, что в ней сознательно действует только один из участников (предприятия), называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные ходы партнёр по игре.

Первоочередной задачей является построение платёжной матрицы.

Предприятие располагает тремя чистыми стратегиями: стратегия Р1 с расчетом на тёплую погоду, стратегия Р2 с расчётом на прохладную погоду и стратегия Р3 с расчётом на обычную погоду.

Природа, рассматривается как второй игрок, также располагает тремя стратегиями: обычная погода (стратегия П1), прохладная погода ( стратегия П2) и тёплая погода (стратегия П3).

Если предприятие выберет стратегию Р1, то в случае обычной погоды (стратегия природы П1) доход составит

в случае прохладной погоды (стратегия природы П2) доход будет равен

и в случае теплой погоды (стратегия природы П3) имеем доход, равный

Если предприятие выберет стратегию Р2, то реализация продукции в условиях обычной погоды даёт доход

в условиях холодной погоды доход будет

а в условиях тёплой погоды имеем доход

Если предприятие выберет стратегию Р3, то в случае обычной погоды доход будет равен

при прохладной погоде имеем доход, равный

и в случае тёплой погоды доход составит

Результаты вычислений сведены в табл. 7.1.

Платёжная матрица рассматриваемой производственной ситуации имеет вид

. (7.12)

Таблица 7.1

Платёжная матрица

Платит, естественно, не природа, а некая третья сторона (или совокупность сторон, влияющих на принятие решений игроком 1 и объединённых в понятие «природа»). В данной ситуации платит само предприятие, получая меньшую или большую прибыль.

Для матрицы (7.12), исходя из общей постановки (7.8) – (7.11), имеем следующую пару двойственных задач:

для определения оптимальной стратегии Р нужно решить задачу линейного программирования: найти минимум функции

(7.13)

при ограничениях

(7.14)

Оптимальную стратегию игрока 2 определим, решив задачу линейного программирования: найти максимум функции

(7.15)

при ограничениях

(7.16)

Решаю более простую обратную задачу (7.15) – (7.16). Вводя положительные базисные переменные (б.п.), систему неравенств (7.16) записываем в виде системы уравнений

(7.17)

Систему (7.17) запишем в виде симплекс-таблицы 7.2.

Таблица 7.2

Симплекс-таблица

Совершив три шага жордановых исключений, получаем табл. 7.3.

Так как в табл. 7.3 все элементы в z – строке и 1 – столбце неотрицательны, то получаем оптимальное решение.

Таблица 7.3

Симплекс-таблица

Переходим к решению прямой задачи. Установим соответствие переменных двойственных задач:

С.П. Б.П.

Транспортируем табл. 7.3, знаки перед всеми элементами, кроме элементов z – строки, меняем на обратные, переменные заменяем на соответствующие переменные, получаем табл. 7.4.

Таблица 7.4

Транспортированная симплекс-таблица 7.3

Из табл. 7.4 получаем оптимальное решение. Так как, то цена игры. Из получаем. Аналогично получим и .

Это означает, что означает, что стратегию Р1 нужно применять с вероятностью, стратегию Р2 – с вероятностью, и стратегию Р3 – с вероятностью .

Формируем оптимальный план производства:

Таким образом, предприятие при производстве 801 костюма, 1239 платьев и 554 плащей получит наибольшую прибыль, которая в среднем составит 20833 ден. ед.

Для приведённой формулировки производственной задачи получили однозначный ответ.

Недостатком данного метода является достаточно большой объём вычислительных операций даже для матрицы с размером. Однако применение ЭВМ снимает это неудобство.