Двойственность в линейном программировании, страница 7

min 4х₁ + 15х₂ + 40х₃

380х₁ + х₂ + 2х₃ ³ 4

-380х₁ - х₂ - 2х₃ ³ -6

90х₂ + 50х₃ ³ 44

-20х₂ - 80х₃ ³ -25

х₁ + х₂ + х₃ = 0,5

х_1-3 ³ 0

Построим задачу, двойственную к данной*:

max 4y₁ – 6y₂ + 44y₃ – 25y₄ + 0,5у₅

380y₁ – 380y₂ + у₅ £ 4

y₁ – y₂ + 90y₃ – 20y₄ + у₅ £ 15

2y₁ – 2y₂ + 50y₃ – 80y₄ + у₅ £ 40

у_1-4 ³ 0

Чтобы решить ее симплекс-методом, приведем ее к канонической форме. Для этого нужно ввести три дополнительных переменных. Кроме того, поскольку переменная у₅ не ограничена по знаку (т.к. она соответствует уравнению прямой задачи), следует заменить ее на разность двух неотрицательных переменных (у₅ = у₅`- у₅``):

max 4y₁ – 6y₂ + 44y₃ – 25y₄ + 0,5у₅` – 0,5у₅``

380y₁ – 380y₂ + у₅` – у₅``+ y₆ = 4

y₁ – y₂ + 90y₃ – 20y₄ + у₅` – у₅``+ y₇ = 15

2y₁ – 2y₂ + 50y₃ – 80y₄ + у₅` – у₅``+ y₈ = 40

у_{1-4, 6-8,}  у₅`, у₅``³ 0

В этой задаче имеется готовый базис, и можно сразу же решить ее симплекс-методом, не используя метод искусственного базиса*. Решение приведено в таблице 20.

Таблица 20 – Решение двойственной задачи

5.6.2 Выполнение основной теоремы двойственности

Сравним полученный результат с оптимальной симплексной таблицей для прямой задачи (см. таблица 19).

Как и следовало ожидать в соответствии с основной теоремой двойственности, получено то же самое значение оптимума – 7,378.

Из таблицы 20 базисные переменные у₃ = 0,122; у₅` = 4; у<sub>8</sub> = 29,889. Небазисные переменные  у<sub>1</sub> = у<sub>2</sub> = у<sub>4</sub> = у<sub>5</sub>``= у<sub>6</sub> = у<sub>7</sub> = 0. Так как у<sub>5</sub> = у<sub>5</sub>`- у₅``, у₅ = 4 – 0 = 4. Таким образом, оптимальный план Y^* = (0; 0; 0,122; 0; 4; 0; 0; 29,889).