2015-03-20
8060
Различают симметричные, несимметричные и смешанные двойственные задачи.
Симметричные двойственные задачи.
В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Дана исходная задача.
при ограничениях
Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:
при ограничениях
,
Несимметричные двойственные задачи.
В несимметричных задачах система ограничений исходной задачи задается в виде равенств, а система ограничений двойственной в виде неравенств, причем если в целевой функции двойственной задачи требуется найти минимум, то знак неравенств ≥, если максимум, то ≤. Кроме того, в двойственной задаче переменные могут принимать любое значение, в том числе и отрицательные.
Дана исходная задача.
при ограничениях
Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:
|
|
|
при ограничениях
,
Смешанные двойственные задачи.
Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.
Зная решение одной из двойственных зада можно найти решение другой задачи.
Теорема. Если одна из пары двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, причем для любых оптимальных решений 
и 
выполняется неравенство
Если одна из двойственных задач неразрешима ввиду того, что 
(или 
), то другая задача не имеет допустимых решений.
