Главная | Обратная связь

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

ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

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

 

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

Как уже отмечалось выше, любую задачу линейного программирования можно записать следующим образом:

, (3.1)

(3.2)

(3.3)

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

Модель двойственной задачи имеет вид:

, (3.4)

, (3.5)

(3.6)

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

Взаимно двойственные задачи должны удовлетворять следующим условиям:

1. В одной задаче ищется максимум линейной формы, а в другой – минимум.

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

3. В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла, а именно: в задаче, в которой ищется макисимум линейной формы, все неравенства вида ≤, а в задаче, в которой ищется минимум линейной формы, - противоположного смысла, т.е. ≥.

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

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

6. Условия неотрицательности переменных существуют в обеих задачах.

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

1) привести все неравенства системы ограничений исходной задачи к одному виду, а именно: если в исходной задаче ищется максимум линейной формы, то все неравенства системы ограничений привести к виду ≤, а если минимум – то к виду ≥. Для этого неравенства, в которых это требование не выполняется, умножить на ( - 1);

2) выписать матрицу коэффициентов А при переменных исходной задачи, полученных после преобразований, указанных в пункте 1, и транспонировать ее;

 

3) составить систему ограничений двойственной задачи, для чего коэффициентами при переменных взять элементы транспонированной матрицы А^т, неравенствам придать противоположный по сравнению с неравенствами пункта 1 смысл, а в качестве свободных членов взять коэффициенты при переменных линейной формы исходной задачи;

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

5) указать, что необходимо найти при решении задачи, а именно: минимум линейной формы, если в исходной задаче ищется максимум, и наоборот;

6) записать условие неотрицательности переменных двойственной задачи.

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