Правила построения двойственной ЗЛП

Существует много различных комбинаций ограничений и целевой функции для записи исходной задачи. Для упрощения задачи построения двойственной ЗЛП запишем прямую задачу в стандартном виде:

,

.

Правила построения двойственной ЗЛП:

1) Если прямая задача решается на максимум, то двойственная – на минимум, и наоборот.

2) В задаче на максимум ограничения-неравенства имеют смысл , а в задаче на минимум – .

3) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот.

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

5) Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот.

6) Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство.

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

Пример. К данной ЗЛП составить двойственную задачу:

.

Преобразуем исходную ЗЛП к стандартному виду с максимизацией целевой функции:

.

Составим двойственную ЗЛП по ранее указанным правилам:

.

Дата добавления: 2014-12-07