Двойственная задача для задачи ЛП в канонической форме.

Лекция 5.

Рассмотрим задачу ЛП, в которой все нетривиальные ограничения - равенства:

Каноническая задача ЛП Двойственная к ней задача ЛП имеет вид

Ax = b A^Ty ≥ c

(P) x ≥ 0 (D) y_i - любого знака

<c, x> → max <b, y> → min

Этот результат можно получить, сведя задачу (Р) к стандартной форме путем замены каждого равенства эквивалентной ему системой двух неравенств противоположного знака:

Ax ≤ b

(P′) Ax ≥ b

x ≥ 0

<c, x> → max

и построив затем для задачи (P′) двойственную. После соответствующих преобразований последняя приводится к виду (D). Отличие от задачи, двойственной к стандартной (где все ограничения – неравенства), состоит только в том, что на переменные двойственной задачи

не накладываются условия неотрицательности.

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

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

(≥)_i → y_i ≥ 0, (=)_k → y_k любого знака

- матрица коэффициентов транспонируется: A → A^T ;

- векторы b и c меняются «ролями»: b ↔ c;

- изменяется направление неравенств: ≤ ↔≥ , при этом, если на какую-либо прямую переменную x_j не наложено ограничение неотрицательности, соответствующее ограничение двойственной задачи записывается как равенство;

- оператор max заменяется на min: max ↔ min.

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

Z = ∑ c_j x_j → max F = ∑ b_i y_i → min

∑ a_ij x_j ≤ b_i (i=1,…, k) ∑ a_ij y_i ≥ с_j (j=1, …, L)

(P) ∑ a_ij x_j = b_i (i=k+1,…, m) (D) ∑ a_ij y_i = с_j (j=L+1, …, n)

x_j ≥ 0 (j=1,…, L) y_i ≥ 0 (j=1, …, k)

x_j любого знака (j=L+1, …, n) y_i любого знака (i=k+1,…, m)

Экономическое содержание теорем двойственности.

Рассмотрим задачу ЛП: ∑ a_ij x_j ≤ b_i (i=1,…, m)

x_j ≥ 0 (j=1,…, n)

∑ c_j x_j → max .

Если все параметры в этой задаче a_ij, b_i, c_j неотрицательны, можно интерпретировать ее как рассмотренную нами ранее задачу оптимального использования m ресурсов R₁,…,R_m (запасы которых равны b₁,…,b_m )

для выпуска n видов продукции в объемах х₁ ,…,x_n в целях максимизации прибыли при заданных ценах на продукцию с₁ ,…,c_n.

Экономическое содержание Первой теоремы двойственности.

Назовем оптимальные двойственные переменные y₁*, …, y_m* оценками ресурсов R₁,…,R_m (основания для такого названия станут ясны из дальнейшего).

Пусть x*, y* - оптимальные решения прямой и двойственной задачи. Тогда по Первой теореме двойственности <c, x*> = <b, y*>. Заметим, что <c, x*>=∑ c_j x_j* - это стоимость оптимального выпуска x* в заданных внешних ценах с₁ ,…,c_n., а <b, y*>=∑ b_i y_i* - это стоимость вектора ресурсов в оптимальных двойственных оценках y₁*, …, y_m*.

Вывод.Выпуск х* оптимален тогда и только тогда, когда существуют оптимальные двойственные оценки y* и стоимость выпуска в заданных ценах равна стоимости ресурсов в двойственных (вычисленных) оценках: <c, x*> = <b, y*>. Фактически это перефразировка Первой теоремы.

Экономическое содержание Второй теоремы двойственности

Условия дополняющей нежесткости (ДН) говорят следующее.

Если по оптимальному плану производства х* i-й ресурс расходуется не полностью (∑a_ij x_j* < b_i), то двойственная оценка этого ресурса равна нулю: y_i* = 0; если же оценка некоторого ресурса положительна, то соответствующий ресурс на оптимальном решении расходуется полностью.

Таким образом, двойственная оценка является мерой дефицитности ресурса.

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

Если оценка ресурсов, расходуемых на производство единицы j-го вида продукции, больше цены этой продукции (∑ a_ij y_i* > c_j), то j-ая продукция не выпускается: x_j* = 0; если же при оптимальном плане производства некоторая продукция выпускается, то оценка ресурсов, затраченных на ее выпуск, в точности равна стоимости продукции.

Вывод. Оценки y* определяют эффективность выпуска разной продукции. Продукция j выпускается тогда и только тогда, когда оценка ресурсов, затраченных на единицу продукции, и цена этой продукции совпадают: ∑ a_ij y_i* = с_j.