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

при условиях

Пусть при
совпадают с
есть единичный орт
а
при
. В разд. 1.3-1.5 мы видели, что обычное условие наличия безусловного экстремума функции во внутренней точке есть обращение в нуль градиента функции в этой точке.
Если при этом должны выполняться некоторые ограничения на переменные в виде равенств, то условием наличия экстремума в допустимой точке будет требование, чтобы в этой точке градиент функции и нормали к поверхностям, соответствующим ограничениям, были направлены «в одну сторону».
Более точно градиент функции в этой точке должен быть неотрицательной линейной комбинацией этих нормалей к поверхностям-ограничениям. В задаче линейного программирования каждое неравенство определяет допустимую область — полупространство. Для того чтобы допустимая точка была оптимальной, необходимо, чтобы градиент целевой функции в точке
выражался в виде неотрицательной линейной комбинации направляющих векторов тех и только тех ограничений, которые в точке
обращаются в равенства, т.е. градиент целевой функции (вектор
) есть неотрицательная линейная комбинация нормалей векторов
для ограничений, обращающихся в равенство:

где — соответствующие коэффициенты линейной комбинации.
Из условий дополняющей нежесткости в слабой форме следовало: если , то
, и если
, то
.
В сильной форме утверждалось, что если , и если
, то
.
На рис. 2.4 изображены три гиперплоскости и нормали к ним
. Если векторстакой, как показано на рис. 2.4, то он может быть выражен в виде неотрицательной линейной комбинации векторов
и
; вершина, обозначенная кружком, соответствует оптимальному решению. Здесь

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


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


Для решения задач линейного программирования разработан так называемый двойственный симплекс-метод. Процедуру начинают с двойственно допустимого решения, когда одновременно

и сохраняют его двойственно допустимым на протяжении всех шагов. Он реализуется посредством таких же таблиц, как и прямой симплекс-метод. Но здесь сначала определяется, какая переменная должна быть выведена из базиса, а затем — какая должна быть введена в базис.
Всегда имеется возможность выбора: решать прямую или двойственную задачу, использовать прямой или двойственный симп-лекс-метод. Выбирают ту модификацию задачи, которую проще решать. Например, если исходная задача содержит переменные, на которые не наложено условие неотрицательности, тобываетудоб-нее решать двойственную задачу. Прежде чем записать двойственную задачу, полезно в исходной прямой задаче освободиться от ограничений в виде равенств, поскольку они будут порождать в двойственной задаче переменные, принадлежащие всей действительной оси.
В симплекс-таблице оптимального решения прямой задачи линейного программирования присутствует и решение двойственной к ней задаче. Чтобы это увидеть, надо элементы строки, где стоят коэффициенты целевой функции, представить в виде
, где
— вектор, состоящий из коэффициентов целевой функции исходной задачи, стоящих в базисных клетках оптимального решения;
— элементы
-го столбца симплекс-таблицы оптимального решения, и добавить в симплекс-таблицу дополнительную строку
. В строке
в столбцах базисных переменных исходной задачи (обычно это последние
столбцов) находится оптимальное решение двойственной задачи.
Таким образом, оптимальное решение двойственной задачи — это
последних элементов строки
оптимальной симплекс-таблицы прямой задачи; а оптимальным решением
прямой задачи — это
последних элементов строки
оптимальной таблицы двойственной задачи.
В литературе, кроме того, описаны методы одновременного решения прямой и двойственной задач, например метод последовательного сокращения невязок

при фиксированных значениях .
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: