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

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется прямой или исходной. Многие ЗЛП первоначально ставятся в виде исходных или двойственных задач, поэтому говорят о паре взаимно двойственных, симметричных, задач линейного программирования, которые имеют вид:

.

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована так.

Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных стоимостях единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении?

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

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

• 1) если прямая задача решается на максимум, то двойственная — на минимум, и наоборот;
• 2) в задаче на максимум ограничения — неравенства имеют знак ««, а в задаче минимизации — ««;
• 3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;
• 4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;
• 5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;
• 6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается ограничение-неравенство, если же нет, то как ограничение-равенство;
• 7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.