Существование рационально — двойственность в линейном программировании

При решении задачи программирования (не ограничиваясь линейным программированием) нам часто необходимо знать, имеет ли задача допустимое решение (иногда ограничения очень сложные, не говоря уже об оптимальном решении, найти допустимое решение сложно), или оценить Насколько далеко текущее оптимальное решение диссоциации (итерационные решения часто используются для крупномасштабных задач. Если вы можете грубо оценить качество текущего решения, вы будете иметь приблизительное представление о том, когда алгоритм завершится Если вы получите приемлемое приближенное решение, вы также можете его остановить заранее) и судить о том, является ли оптимальное решение исходной задачи неограниченным (если это произойдет, итерация не будет остановлена).

Начнем с теории двойственности.

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

Для задачи оптимизации с ограничениями из условия неравенства:

min \quad z=c^Tx \qquad s.t. \quad Ax \geq b(x \geq 0)

Его двойная проблема

max \quad w =b^Ty \qquad s.t. \quad A^Ty \leq c(y \geq 0)

Вот и возникает проблема, вроде бы полная закономерность, но на самом деле совсем не запутанная.почему так? Позвольте мне дать вам каштан, чтобы проиллюстрировать.

Электростанция производит бытовую технику, а существующие ресурсы производят два продукта.

\begin{array}{c} % inner horizontal array of arrays 内层水平表格 \begin{array}{c|cccc} \Delta&产品1&产品2&总限时\\ \hline 设备A & 0 & 5 & 15hour \\ 设备B & 6 & 2 & 24hour \\ 调试工序 & 1 & 1 & 5hour \\ \hline 利润 & 2 & 1 & \end{array} \end{array}

Эта таблица означает, что наш завод делит в общей сложности 15 часов рабочего времени на оборудование А, 24 часа на оборудование В и 5 часов на процесс отладки.Время, затрачиваемое оборудованием А и оборудованием В на производство продуктов 1 и 2 показано в таблице Как показано (0 означает отсутствие производства), последний продукт 1 получает прибыль в размере 2, а последний продукт 2 получает прибыль в размере 1. Что касается фабрики, как распределить максимальную прибыль.

Тогда мы можем легко записать ее как задачу оптимизации с несколькими условными ограничениями.

\begin{matrix} & max \quad z=2x_1+x_2 \\ s.t. & 6x_1+2x_2 \leq 24 \\ & x_1+x_2 \leq 5 \\ & x_1,x_2 \geq 0 \\ \end{matrix}

Мышление производителя заключается в том, что у меня так много ресурсов, и я хочу превратить их в деньги как можно больше. В это время кто-то пришел, чтобы купить производителя.Конечно, он не хотел, чтобы производитель имел высокую прибыль.Из-за высокой прибыли производителя ему пришлось потратить больше денег, чтобы купить производителя. Однако прибыль производителей не бесконечно мала, ведь вещи, которые они производят, настолько прибыльны. Мы устанавливаем прибыль устройства A равной y_1 юаней/час, прибыль устройства B составляет y_2 Юань/час, прибыль от процесса отладки составляет y_3 юаней/час.

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

Исходя из этого итогового показателя, покупателю нужна минимально возможная общая прибыль:

Итак, наш вопрос звучит так:

\begin{matrix} & min \quad w=15y_1+24y_2+5y_3 \\ s.t. & 6y_2+y \geq 2 \\ & 5y_1 +2y_2+y_3 \geq 1 \\ & y_1,y_2,y_3 \geq 0 \\ \end{matrix}

Это двойная проблема исходной проблемы. Проблема двойственности часто имеет очевидные экономические последствия.

основные правила

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

Если i-е ограничение максимальной задачи принимает «≥», то i-я переменная минимальной задачи ≤ 0

i-е ограничение минимальной задачи принимает «≤», тогда i-я переменная максимальной задачи равна ≤ 0

i-е ограничение исходной задачи равно, а i-я переменная двойственной задачи не ограничена

j-я переменная максимальной задачи ≤ 0, тогда j-е ограничение минимальной задачи принимает «≤»

j-я переменная минимальной задачи ≤ 0, тогда j-е ограничение максимальной задачи принимает значение «≥»

j-я переменная исходной задачи не ограничена, а j-е ограничение двойственной задачи равно

Вышеупомянутые правила являются конкретными правилами преобразования.Фактически, закон преобразования состоит в том, что если исходная задача не соответствует стандартной форме (1) или (2), указанной выше, то i-е ограничение исходной задачи не соответствует удовлетворяют требованиям, то соответствующая i-я переменная двойственной задачи должна быть ≤ 0; аналогично, если i-я переменная исходной задачи не удовлетворяет требованиям (то есть xi≤ 0), i-я ограничение соответствующей двойственной задачи должно менять знак.

Теорема двойственности включает ряд теорем, в том числе теорему о слабой двойственности, теорему о сильной двойственности, теорему об оптимальности и теорему о дополнительной релаксации. С помощью этих теорем исходная проблема, которую было трудно решить, может быть решена путем введения двойственной теории Конкретное содержание каждой теоремы состоит в следующем:

Теорема слабой двойственности

Объективное значение любого допустимого решения максимальной задачи является нижней границей объективного значения минимальной задачи; Объективное значение любого допустимого решения минимальной задачи является верхней границей объективного значения максимальной задачи.

Сильная теорема двойственности

Если исходная задача имеет оптимальное решение, то двойственная задача также имеет оптимальное решение, и значения целевой функции оптимальных решений двух задач равны.

неограниченный

Если исходная задача (двойственная задача) имеет неограниченное решение, то двойственная задача (исходная задача) не имеет допустимого решения.

Заметим, что обратной неограниченности не существует. Если исходная (двойственная) задача не имеет допустимого решения, то двойственная (исходная) задача имеет либо неограниченное решение, либо не имеет допустимого решения.

оптимальность

как $\overline{x}$ и $\overline{y}$ являются допустимыми решениями основной задачи и двойственной задачи соответственно, то основная задача и двойственная задача имеют оптимальные решения, и когда $c^T\overline{x}=b^T \overline{y}$ час, $\overline{x}$ и $\overline{y}$ являются оптимальными решениями прямой и двойственной задач соответственно.

Дополнительная теорема о релаксации

как $\overline{x}$ и $\overline{y}$ являются допустимыми решениями основной задачи и двойственной задачи соответственно, то необходимые и достаточные условия для того, чтобы они были оптимальными решениями основной задачи и двойственной задачи, таковы: $\overline{x}^T(A^T\overline{y}−c)=0$ и $\overline{y}^T(A\overline{x}−b)=0$ С помощью теоремы о дополнительной релаксации можно получить оптимальное решение исходной задачи (двойственной задачи) и оптимальное решение ее двойственной задачи (исходной задачи).