4.2.5. Значения целевых функций прямой и обратной задач

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

Для любой пары допустимых решений прямой и двойственной задач

Значение целевой функции (Значение целевой функции в задаче максимизации ) в задаче минимизации )

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

Пример 4.2.3

В примере 4.2.1 прямая и двойственная задачи имеют допустимые решения х, = 0, х2 = 0, х3 = 8/3 и у, = 6, у2 = 0. Для этих решений значения целевых функций соответственно равны г =32/3 и w = 60. Для оптимальных решений х, = 26/5, х2 = 12/5, х3 = 0 и у, = 29/5, у2 = -2/5 имеем z = w = 54,8. Таким образом, приведенные значения целевых функций подтверждают сформулированное соотношение.

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

УПРАЖНЕНИЯ 4.2.5

1. Определите интервалы изменения значений целевой функции в следующих задачах ЛП.

a) Минимизировать г = 5л:, + 2х2 при ограничениях

л:,-л:2>3, 2л:, + 3лг2>5, л: лс2>0.

b) Максимизировать z = хх + 5лс2 + Зх3 при ограничениях

л:, + 2х2 + х3 = 3, 2л:, - х2 = 4, л: х2, х3>0.

c) Максимизировать z = 2л:, + х2 при ограничениях

х, -х2<10, 2л:, <40, л: л:2>0.

d) Максимизировать г = 3jc, + 2х2 при ограничениях

2jc, + х2<3, Зл:, + 4х2 > 12, хг,х2>0.

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

a) дс1 = 3,лс2=1;у, = 4,у2=1.

b) х1 = 4, *г=1;у, = 1, у, = 0.

c) jc1 = 3,jc2 = 0;j/1 = 5,j/2 = 0.

4.3. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННОСТИ

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

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

Исходя из модели распределения ресурсов, прямая задача отображает п видов экономической (производственной) деятельности и возможности получения т ресурсов. В прямой задаче коэффициент с\ представляет собой прибыль на единицу продукции у-го вида экономической деятельности, причем на единицу продукции этого вида деятельности расходуется ац единиц ресурса I, максимальные запасы которого ограничены величиной bt.

Прямая задача Двойственная задача

4.3.1. Экономическая интерпретация переменных двойственной задачи

Соотношение из раздела 4.2.5 устанавливает, что для любой пары допустимых решений прямой и двойственной задач значения (конечные) их целевых функций удовлетворяют неравенству

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

Рассмотрим сначала вариант оптимума, т.е. когда z = w. Исходя из представления прямой задачи как модели распределения ресурсов, можно считать, что величина z соответствует величине дохода (в долларах3). Поскольку bt - общее доступное количество ресурса i, равенство z = w можно переписать следующим образом.

Доход (долл.) = ]Г (количество ресурса i) х (доход (долл.) на единицу ресурса i).

Это означает, что переменная yt двойственной задачи должна представлять стоимость единицы ресурса i. (Данное понятие уже вводилось в разделе 2.3.3, исходя из графического представления задачи ЛП.) В литературе по исследованию операций переменные yt двойственной задачи часто называют двойственными ценами. Кроме того, иногда их именуют теневыми ценами и симплексными мультипликаторами.

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

доход < общая стоимость ресурсов.

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

Пример 4.3.1

Приведем формулировки прямой и двойственной задач, описывающие модель производства компании Reddy Mikks из примера 2.1.1.

Прямая задача

Двойственная задача

Максимизировать z= 5xi + 4хг при ограничениях

6xi + 4хг i 24 (ресурс 1, сырье М1), Xi + 2X2 < 6 (ресурс 2, сырье М2), -Xi + хз < 1 (ресурс 3), хг < 2 (ресурс 3), Хь х2 > 0.

Минимизировать w= 24yi + буг + уз + 2у4

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

6yi + уг - уз s 5,

4yi + 2уг + уз + уд > 4,

У1.У2, Уз, У4>0.

Оптимальное решение: X! =3, хг = 1,5, z= 21

Оптимальное решение:

yi = 0,75, уг = 0,5, уз = у4 = 0, w= 21

Читатель вместо долларов может, конечно, подставить любую другую денежную единицу - это не принципиально для понимания изложенного материала. - Прим. ред.