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

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

max

(3)

Двойственная задача по отношению к задаче (3) запишется в виде

min

(4)

При построении двойственной задачи соблюдаются следующие правила:

1. каждому i-му ограничению задачи (3) соответствует переменная y_i задачи (4), и, наоборот, каждому j-му ограничению двойственной задачи (4) соответствует переменная x_j задачи (3);

2. матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием;

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

4. если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется;

5. в задаче (3) ограничения-неравенства следует записывать со знаком ≤, а для задачи (4) – со знаком ≥;

6. если на j-ю переменную задачи (3) наложено условие неотрицательности, то j-е ограничение задачи (4) будет неравенством. В противном случае j-е ограничение будет равенством; аналогично связаны между собой ограничения задачи (3) и переменные задачи (4).