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

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

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

∑ 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*.

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