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

Для построения двойственной задачи необходимо свести прямую задачу к стандартному виду. Считают, что задача линейного программирования представлена в стандартном виде, если для отыскания максимального значения целевой функции все неравенства ее системы ограничений приведены к виду «», а для задачи на отыскание минимального значения — к виду «».

Если прямая задача линейного программирования представлена в стандартном виде, то двойственная задача образуется по таким правилам:

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

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

3. Если целевая функция прямой задачи задается на поиск наибольшего значения (max), то целевая функция двойственной задачи - на определение наименьшего значения (min), и наоборот.

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

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

6. Матрица

,

которая состоит из коэффициентов при переменных в системе ограничений прямой задачи, и матрица коэффициентов в системе ограничений двойственной задачи

образовываются одна из одной транспонированием, т.е. заменой строк столбцами, а столбцов - строками.

Процесс построения двойственной задачи удобно изобразить схематично:

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

Рисунок 3.1 - Схема построения двойственной задачи к прямой

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

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

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

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

Прямая задача	Двойственная задача
Симметричные задачи
Прямая задача	Двойственная задача
Несимметричные задачи