Метод одновременного решения пары двойственных задач

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

1. Обе задачи приводят к каноническому виду и устанавливают соответствие между переменными обеих задач.

2. Решают с помощью симплекс-метода ту из двух задач, где свободные члены в выражениях для базисных переменных неотрицательны (предполагается, что одна из задач таким свойством обладает).

3. На основании первой теоремы двойственности определяют оптимальное значение целевой функции второй задачи: или f_max = g_min.

4. На основании второй теоремы двойственности выписывают оптимальное решение второй задачи. Для этого целевую функцию первой задачи выражают через свободные, или неосновные, переменные. Тогда компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции прямой задачи, выраженной через неосновные переменные ее оптимального решения.

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

Вернемся к примеру п. 4.3.

Прямая ЗЛП: Двойственная ЗЛП:

Канонический вид:

Установим соответствие между переменными двух задач:

Переменные прямой задачи I
Первоначальные	Дополнительные
х1 y4	х2 y5	х3 y1	х4 y2	х5 y3
Дополнительные	Первоначальные
Переменные двойственной задачи II

 

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

х₃ = 4 – х₁ – 2х₂,

х₄ = 3 – х₁ – х₂,

х₅ = 8 – 2х₁ – х₂.

Итоговая симплекс-таблица решения прямой задачи имеет вид:

сi	БП
х1	х2	х3	х4	х5	bi
	x2				-1
	x1			-1
	x5				-3
D j

 

Значение целевой функции двойственной задачи равно значению целевой функции прямой задачи: = = 10.

Оптимальное решение прямой задачи: = (2, 1, 0, 0, 3).

Оптимальное решение двойственной задачи: = (1, 2, 0, 0, 0), поскольку y₁ «x₃, y₂ «x₄, y₃ «x₅, y₄ «x₁, y₅ «x₂.

Последней симплекс-таблице соответствуют следующие уравнения для базисных переменных, входящих в целевую функцию:

х₁ – х₃ + 2х₄ = 2,

х₂ + х₃ – х₄ = 1.

Откуда

х₁ = 2 + х₃ – 2х₄,

х₂ = 1 – х₃ + х₄.

Выразим целевую функцию через свободные переменные:

= 3×(2 + х₃ – 2х₄) + 4×(1 – х₃ + х₄) = 10 – х₃ – 2х₄.

Таким образом, в соответствии со второй теоремой двойственности y₁ = 1, y₂ = 2, значения остальных переменных оптимального решения двойственной задачи y₃, y₄, y₅ равны нулю, поскольку они не входят в выражение целевой функции.

Следует отметить, что положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи:

Переменные прямой задачи I
Первоначальные	Дополнительные
Дополнительные	Первоначальные
Переменные двойственной задачи II

 

Такое соответствие было отмечено в рассмотренной ранее теореме.