Лекция 13. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ДЗЛП)

Формулировка и правила составления ДЗЛП

Для любой ЗЛП можно сформулировать задачу-двойник, или двойственную задачу (ДЗЛП). ДЗЛП является зеркальным отражением исходной задачи, так как ее формулировка использует те же параметры, а ее решение может быть получено одновременно с решением исходной задачи. Исходная задача и ДЗЛП симметричны: если ДЗЛП рассматривать как исходную, то исходная будет для нее ДЗЛП.

Сформулируем ДЗЛП к задаче об оптимальном плане мебельного цеха. Есть покупатель на все ресурсы мебельного цеха (Р Р2 и Р). Таблица параметров остается той же. Какие цены на эти ресурсы надо назначить, чтобы продать их было не менее выгодно, чем производить продукцию? Какую минимальную сумму можно выручить при этом условии?

Так как имеется три вида ресурсов, то ДЗЛП должна иметь три переменных решения - это цены, назначаемые производителем при продаже: yj - цена единицы ресурса Рр у2- цена единицы ресурса Р у - цена единицы ресурса Р3. Эти цены называются теневыми. Они характеризуют ценность ресурсов для производителя и не имеют отношения к рыночным ценам.

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

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

Для иллюстрации симметрии исходной ЗЛП и ДЗЛП составим таблицу.

Исходная ЗЛП

Двойственная ЗЛП

Переменные решения

ХрХ2

УрУгУз

Целевая функция

Прибыль

F = Х]+ 2x2 max

Издержки

Z = 8уj + 2 Оу, + 5у3 -> min

Ограничения

Xj+ х2 < 8 х + 4x2 < 20 xt<5 xpx2>0

L Ч-Ч-ьа

'»?» |_) Н-

IV IV .<

О

IV

н-*

Сформулируем правила составления ДЗЛП.

Если целевая функция исходной задачи максимизируется, то в ДЗЛП минимизируется.

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

Матрица коэффициентов в системе ограничений исходной задачи и аналогичная матрица ДЗЛП получаются друг из друга транспонированием.

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

В задаче максимизации все неравенства вида «<», а в задаче минимизации - вида «>».

Пример. Составить задачу, двойственную к данной:

F ' 2х,+ х, + 6х,—> min х1-Зх2+2х3=1, 2Xj+4x2+x3 < 7, -Х!+Х2+Зхз > 6, Xj >0,j=l,2,3.

РЕШЕНИЕ

Согласно пятому правилу все ограничения задачи на минимум должны иметь вид «>». Поэтому умножим второе ограничение на-1:

F = 2х,+ х, + 6х,—> min

1 2 ?

х1-Зх2+2х3=1,

  • -2х(-4х23 > -7,
  • -х,+х2+Зх3 > 6, X, >0,j=l,2,3.

Составим двойственную задачу:

Z = yj- 7у2 + 6у3—> max 'у,-2у,-у3 <2, -Зу.^Уз+Уз <1, 2У|-У2+3Уз ^6, y)>0,j=2,3.

Переменная у соответствующая ограничению-равенству, может быть любого знака.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >