Двойственная задача линейного программирования

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

1. Задача оптимального планирования производства.

Как известно, эта задача формализуется как стандартная задача линейного программирования:

Напомним содержательный смысл параметров и переменных задачи: b_i – общее количество ресурса R_i, a_ij – количество ресурса R_i, расходуемого на производство единицы продукта P_j, c_j – прибыль от реализации единицы продукта P_j, x_j – количество продукта P_j, планируемое к выпуску.

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

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

В этой связи возникает двойственная задача: установить такие цены на ресурсы (внутри объединения), чтобы минимизировать их общую стоимость (интерес покупателя) при условии, чтобы стоимость расхода ресурсов на единицу продукта была не ниже соответствующей прибыли от реализации (интерес продавца).

Проведем формализацию этой задачи. Пусть у_i≥ 0, - планируемая цена (оценка) ресурса R_i, i= 1,…,m. Тогда общая стоимость ресурсов выражается величиной .

Стоимость ресурсов, необходимых для производства единицы продукта P_j, равна .

С учетом заявленных требований приходим к следующей задаче линейного программирования относительно переменных у₁…..у_m:

Это двойственная задача по отношению к прямой задаче (2.14). По существу, она является канонической задачей линейного программирования (как и прямая задача).

Двойственная задача - это вспомогательная задача линейного программирования, которая формулируется из исходной (прямой) задачи с помощью определенных правил.

Переменные прямой задачи.

Правые части ограничения двойственной задачи	с1	с2……	сj	……cn
Коэф. левых частей ограничений двойственной задачи	а11	а12…….	a1n	…..a1m	b1	←y1	Переменные двойственной задачи
a21	a22…….	a2j	…..a2m	b2	←y2
:	:	:	:	:	:
am1	am2…….	amj	…..amn	bm	←ym

Правила постановки двойственной задачи:

1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2) Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

3) Коэффициенты а_ij при некоторой переменной - x_j фигурирующие в ограничениях прямой задачи, становится коэффициентами левой части соответствующего ограничения двойственной задачи, а соответствующий коэффициент c_j в целевой функции прямой при той же переменной x_j становится постоянной правой части ограничений двойственной задачи.

Из правил следует, что двойственная задача имеет m переменных (у₁,...,y_m) и n ограничений, соответствующих n переменным прямой задачи.

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

Таблица 42