Зависимость оптимального результата в задаче ЛП от правой части ограничений

Лекция 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.

Зависимость оптимального результата в задаче ЛП от правой части ограничений

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

Пусть в исходной задаче ЛП

∑ a_ij x_j ≤ b_i (i=1, …, m)

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

∑ c_j x_j → max

величины a_ij и c_j неизменны, а правые части ограничений b₁ ,…,b_m могут меняться. Тогда любому вектору b=b₁, …, b_m будет соответствовать (если оно существует) свое оптимальное решение х*_b и соответствующее оптимальное значение целевой функции Z_max=Z_max(b₁, …, b_m)= F(b)= F(х*_b).

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

Для функции F(b) отметим два свойства.

1. Функция F(b) положительно однородная функция первой степени: F(λb) = λF(b) при λ ≥ 0.

Действительно, легко проверить, что если х* – оптимальное решение при правой части b,то λх*– допустимое решение при правой части λb. Поэтому ∑ c_i(λx_i*) = λ ∑ c_i x_i*, откуда получаем:

F(λb) ≥ λF(b). Подумайте, почему λх* - допустимое и, более того, оптимальное решение при правой части λb и, следовательно, в последнем неравенстве фактически можно поставить равенство.

2. Функция F(b) – вогнутая функция (без доказательства):

F(αb¹ + (1-α)b²) ≥ αF(b¹) + (1-α)F(b²) для всех 0<α<1.

Третья Теорема двойственности: Если двойственная задача имеет (при некотором векторе b) единственное решение y*= y₁*, …, y_m*, то функция F(b) для прямой задачи дифференцируема в точке b и ее частные производные равны оптимальным двойственным переменным (оценкам):

∂F(b)/ ∂b_i = y_i*, (i=1, …, m),

то есть grad F(b) = y*. Более того, в некоторой окрестности данной точки b функция F(b) линейна по переменным b₁, …, b_m: F(b) = y₁*b₁ + … + y_m*b_m.

Замечание. Доказательство линейности функции максимума основано на том свойстве, что если оптимальное решение двойственной задачи единственно, то оно не меняется при достаточно малых изменениях коэффициентов целевой функции двойственной задачи. При этом Z(x*)=<c,x*>=<b,y*> и пока y* не изменяется, оптимальное значение Z(x*)=F(b) зависит от b линейно с коэффициентами y₁*,…, y_m*.

Вывод. В силу линейности F(b) числа y_i* показывают прирост оптимального значения Z_max = F(b) при изменениях ограничений на ресурсы b_i.:

∆ Z_max = ∆ F(b) = F(b+∆b)-F(b)= y₁*∆b₁ + … + y_m*∆b_m.

Поэтому естественно считать y_i* оценкой i-го ресурса.

Приведем еще один довод в «оправдание»термина «оценки» для двойственных переменных.

Если b и Z имеют размерности натуральных единиц и денег, то y_i*= ∂F(b)/ ∂b_i = ∂Z_max / ∂b_i имеет размерность [деньги]/ [нат. ед], то есть размерность цены.

Замечание. Если решение двойственной задачи при некотором векторе b не единственно, то функция F(b) в данной точке недифференцируема. Однако можно вычислить ее производную по направлению. Напомним ее определение.

Производной функции ƒ(x) по направлению s (║s║= 1) называется следующий предел:

lim ƒ(x + αs) – ƒ(x).

α→0 α

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

Пусть векторы y¹, …, y^k – вершины (крайние точки) многогранника всех оптимальных оценок y* в двойственной задаче (при данном b). Тогда производная по направлению для функции F(b) вычисляется по формуле:

∂F/∂s = min ∑s_jy_jⁱ = min <s, yⁱ>.

Здесь минимум берется по i от 1 до k, то есть по всем вершинам y¹, …, y^k, а s – единичный вектор: s = (s₁, …,s_m), ║s║= 1.

Итак, вектор двойственных оценок y*=(y₁*, …, y_m*) указывает направление наивыгоднейшего увеличения запасов ресурсов. Если y_i*=0, то данный ресурс увеличивать бесполезно.

Замечание. Указанная характеристика зависимости оптимального результата от запасов ресурсов локальна. Она справедлива до тех пор, пока изменения вектора b не вызовут изменения оптимального решения двойственной задачи – оценки y*.

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

ПРИЛОЖЕНИЕ К ЛЕКЦИИ – ПРИМЕРЫДЛЯ СЕМИНАРА.

Рассмотрим примеры применения соотношений двойственности для решения задач ЛП и для анализа оптимальных решений.

Пример

Решить следующую задачу, используя двойственную к ней.

3x₁ + x₂ – 4x₃ – x₄ ≤ -3

-2x₁ – 4x₂ –x₃ + x₄ ≤ -3

x₁…x₄ ≥ 0

Z = -4x₁ – 18x₂ – 30x₃ – 5x₄ → max

План решения.

1.Построить двойственную задачу (в ней будет две переменные).

2. Решить ее на плоскости геометрическим способом.

3. Использовать условия дополняющей нежесткости для нахождения решения исходной задачи

4. Проверить (для контроля) выполнение достаточного условия оптимальности из 1-й теоремы.

Двойственная задача: активность ограничений в точке оптимума

3y₁ – 2y₂ ≥ -4 (1) (>) 6 >-4

y₁ – 4y₂ ≥ -18 (2) (=) -18 = -18

-4y₁ – y₂ ≥ -30 (3) (=) -30 = -30

-y₁ + y₂ ≥ -5 (4) (>) 0 >-5

y₁, y₂ ≥ 0

F(y) = -3y₁ – 3y₂ → min

Построив область допустимых решений, с помощью линий уровня целевой функции, найдите оптимальное решение двойственной задачи: y* = (6, 6).

Найдем решение прямой задачи, используя условия дополняющей нежесткости (УДН). Первая группа УДН имеет вид:

[3x₁* + x₂* - 4x₃* - x₄* + 3]y₁* = 0

[-2x₁* - 4x₂* - x₃* + 4x₄* + 3]y₂* = 0.

Так как обе компоненты оптимального решения y* = (6, 6) двойственной задачи положительны, оба ограничения в исходной задаче должны в точке оптимума x* выполняться как равенства.

Подставив y* в ограничения двойственной задачи, видим, что первое и четвертое ограничение неактивны. Поэтому из второй группы УДН (выпишите их самостоятельно) следует, что соответствующие компоненты оптимального решения прямой задачи равны нулю: x₁* = 0, x₄* = 0.

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

х₂* - 4х₃* = -3

-4х₂* - х₃ = -3

Решение этой системы: х₂ = 9/17, х₃ = 15/17 Следовательно, оптимальное решение прямой задачи (с учетом ранее установленного ранее х₁* = 0, х₄* = 0) имеет вид: x* = (0, ⁹/₁₇, ¹⁵/₁₇,0).

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

x* = (0, ⁹/₁₇, ¹⁵/₁₇, 0) и y* = (6, 6) – оптимальные решения прямой и двойственной задачи.

Для контроля проверим выполнение условия оптимальности из 1-й теоремы:

Z(x*) = -4*0 – 18*(9/17) – 30*(15/17) – 5*0=36, F(y*)= -3*6-3*6 = 36

Ответ. Оптимальное решение x* = (0, ⁹/₁₇, ¹⁵/₁₇,0), значение целевой функции Z(x*) = 36.

Пример

Является ли х* = (0, 4, 5, 0, 0,11) оптимальным решением следующей задачи ЛП?

x₁ + x₂ + 3x₃ + x₄ + 2x₅ = 19

x₁ + 5x₂ - 5x₃ - x₄ + 2x₅ = -5

x₁ - x₂ + 2x₃ + 10x₅ + x₆ = 17

Z = 2x₂ – 4x₃ + 3x₅ → max

x₁,…, x_n≥0.

 

Проверим х* на допустимость: 19 = 19

-5 = -5 ═> х* - допустимое решение.

17 = 17

Выпишем двойственную задачу:

 

y₁ + y₂ + y₃ ≥ 0 (1)

y₁ + 5y₂ – y₃ ≥ 2 (2) (=)

3y₁ – 5y₂ + 2y₃ ≥ -4 (3) (=)

y₁ – y₂ ≥ 0 (4)

2y₁ + 2y₂ + 10y₃ ≥ 3 (5)

y₃ ≥ 0 (6) (=)

F = 19y₁ – 5y₂ + 17 y₃ → min

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

Предположим, что х* оптимально. Так как х₂* = 4, х₃* = 5, х₆* = 11 положительны, соответствующие ограничения двойственной задачи в ее оптимальном решении y* выполняются как равенства. Выпишем отдельно эти уравнения:

y₁ + 5y₂ – y₃ = 2

3y₁ – 5y₂ + 2y₃ = -4

y₃ = 0

Решение этой СЛУ: (-0,5; 0,5; 0). Напомним, что переменные y не обязаны быть неотрицательными.

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

ограничение (5) не выполняется. Значит, не существует допустимого решения двойственной задачи y*, которое вместе с x* удовлетворяет условиям дополняющей нежесткости. Это противоречит предположению об оптимальности x*.

Вывод: х* - допустимое, но не оптимальное решение исходной задачи.