Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Общая схема построения двойственной задачи

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

F Если задана общая задача ЛП

f(x) = c1x1 + ... + сjхj + сj+1хj+1 + ... + сnxn max, x D, (1.50)

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется общая задача ЛП

где D* определяется системой уравнений и неравенств:

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj ≥ 0 или uj ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (ajuсj или aixbj).

5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aixbj или ajuсj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui ≥ 0 или xi ≥ 0).

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

Тем самым имеет смысл говорить о паре взаимно двойственных задач.

В матричной форме пара двойственных общих задач линейного программирования может быть кратко записана как:

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D, f):

тогда двойственной к ней будет задача (D*, f*):