Проверить (для контроля) выполнение достаточного условия оптимальности из 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

Проверим х* на допустимость: 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₁ + 5y₂ – y₃ = 2

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

y₃ = 0

Решение этой СЛУ : (-0,5; -0,5; 0).

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

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

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