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

Пример 4.5. Рассмотрим задачу:

(4.17)

Ее решение . Найдем решение задачи, двойственной к (4.17), используя теорему 4. Запишем двойственную к (4.17) задачу:

(4.18)

Применяем соотношение (4.16). Так как х₁^* = 3/2 > 0, то 3у₁^* + 4у₂^* + у₃^* = 2. Далее, так как 3х₁^* + х₂^* = 9/2 + 0 > 3, то у₁^* = 0, и так как х₁^* + 2х₂^* = 3/2 + 0 < 3, то у₃^* = 0. В итоге имеем:

3у₁^* + 4у₂^* + у₃^* = 2, у₁^* = у₃^* = 0,

т.е. вектор является решением задачи (2.18) на основании теоремы 4. Вычислим , что соответствует утверждению теоремы 3.

Пример 4.6. Найти решение прямой и двойственной задач.

Двойственная задача содержит две переменные, т.е. ее можно решать графически (рис. 4.1).

Рис. 4.1

Как видно из рис. 4.1, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y₁ + 2Y₂ = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10Y₁ + 8Y₂ = const в направлении, противоположном вектору = (10; 8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:

Y₁ + 2 Y₂ = 5,

2 Y₁ – Y₂ = 12,

откуда

= 29/5; = -2/5 и = 54 .

Ипользуя теорему 4, находим решение исходной задачи. Так как > 0 и < 0, то оба ограничения прямой задачи имеют вид строгих равенств.

Х₁ + 2Х₂ + 3Х₃ = 10;

2Х₁ – Х₂ + 3Х₃ = 8. (4.19)

Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 – 6/5 = 24/5 > 4), то = 0. Решая систему (4.19), получаем:

= 26/5; = 12/5; = 0; f( ) = 54,8.

Получение оптимального решения двойственной задачи из симплекс-таблицы решения прямой задачи

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

(2.20)

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

;

. (4.21)

Предположим, что ЗЛП (4.20) имеет решение. Решения обеих задач могут быть записаны в виде:

= ; = ,

где = = ( , …, )

матрица, обратная для базисной подматрицы . Матрица подматрицы расположена на месте единичной подматрицы в исходной матрице .

Кроме того, можно показать, что

, , (4.22)

откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы ( ) равна разности между левой и правой частями ограничений двойственной ЗЛП:

= . (4.23)

Пример 4.7. Решить следующую ЗЛП:

max (4Х₁ + Х₂ + 2Х₃ + 3Х₄);

Х₁ +2Х₂ + 3Х₃ – Х₅ + Х₇ = 50;

–3Х₂ +Х₃ + Х₄ +2Х₅ + 4Х₇ = 10;

4Х₂ + Х₅ + Х₆ – 1/2 Х₇ = 24;

. (4.24)

Найти решение задачи, двойственной к ЗЛП (4.24).

Так как расширенная матрица

=

системы линейных уравнений (4.24) является К-матрицей, то ЗЛП (4.24) можно решить симплекс-методом. Результаты решения приведены в таблице: