4. Теория двойственности в линейном программировании

В данном разделе вводится важное понятие теории линейного программирования – понятие двойственности. Двойственная задача - это вспомогательная задача линейного программирования (ЛП), формулируемая с помощью определённых правил непосредственно из условий исходной (прямой) задачи. Часто рассматриваются формулировки двойственной задачи, соответствующие различным формам записи прямой задачи. Однако опыт показывает, что на начальной стадии изучения ЛП детали различных формулировок двойственной задачи нередко затрудняют восприятие материала. Кроме того, практическое использование теории двойственности не требует знания деталей различных формулировок двойственной задачи. Здесь даётся обобщённая формулировка двойственной задачи ЛП, которая применима к любой форме представления прямой задачи. Это объясняется тем, что использование симплексного и других методов решения задач ЛП требует приведения ограничений любой задачи ЛП к стандартной (канонической) форме, поэтому двойственная задача будет сформулирована в соответствии со стандартной формой ограничений прямой задачи.