§6. Прямая и двойственная задача линейного программирования.

6.1 Постановка задачи

Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.

Эти задачи экономически могут быть сформулированы следующим образом.

Прямая задача: сколько и какой продукции х_i (i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции С_i, объемом имеющихся ресурсов b_j (j=1,2,…, m) и нормах расхода ресурсов а_ij максимизировать выпуск продукции в стоимостном виде.

Двойственная задача: какова должна быть оценка единицы каждого ресурса y_j (j=1, 2,…, m), чтобы при заданных b_j, c_i и а_ij минимизировать общую оценку затрат на все ресурсы.

Правила построения двойственной задачи по имеемой прямой задаче:

1. Число переменных в двойственной задаче равно коли­честву функциональных ограничений в прямой задаче (т.е., если в прямой задаче вектор переменных записывается как n-мерный вектор-столбец, то в двойственной задаче вектор переменных будет представлять собой n-мерный вектор — строку и наоборот).

2. Если прямая задача ставится как задача максимизации, то двойственная — как задача минимизации и наоборот.

3. Компоненты вектора функциональных ограничений B=(b₁,b₂,...b_m) в прямой задаче становятся коэффициен­тами целевой функции в двойственной задаче.

Применение этих трех правил позволяет сформировать целевую функцию двойственной задачи:

4. Матрица коэффициентов при переменных в системе функциональных ограничений двойственной задачи полу­чается транспонированием матрицы коэффициентов при переменных в системе функциональных ограничений пря­мой задачи.

5. Знак неравенств функциональных ограничений в пря­мой задаче меняется на обратный в двойственной, т.е. «≤» на«».

6. Коэффициенты целевой функции прямой задачи c₁ c₂, …, c_n становятся вектором ограничений в двойствен­ной задаче.

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

7, Прямые ограничения на неотрицательность переменных для двойственной задачи сохраняются.

Таким образом, исходную и двойственную к ней задачу можно представить следующим образом:

Прямая задача	Двойственная задача
Целевая функция
Функциональные ограничения
Прямые ограничения

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

Прямая задача	Двойственная задача
Целевая функция
Функциональные ограничения
Прямые ограничения

В этой задаче – предельные оценки стоимости единицы каждого ресурса, целевая функция – оценка стоимости всех ресурсов, а каждое ограничение есть условие, что оценка ресурсов, идущих на производство продукции , не менее чем цена единицы продукции.