Прямая и двойственная задачи линейного программирования: Двойственная задача линейного программирования / Хабр

Тогда его двойной

(DUAL)

Min Z _w = b ₁ w ₁ +b ₂ w ₂ +……..+b _m w _m

с.т.

A ₁₁ W ₁ +A ₂₁ W ₂ +…… .. +A _M1 W _M D ₁

A ₁₂ W ₁ +A

A ₁₂ W ₁ +A

.

.

a _1n w ₁ +a _2n W ₂ +…… .. +A _MN W _M D _N

и W ₁ , W ₂ , W ₃ , ……. W _M 0

Некоторые важные результаты и теорема

1. Если мы возьмем двойственное к двойственному, то оно будет первичным.

2. Если конкретным ограничением в простом является совершенное равенство, то соответствующая двойная переменная не имеет ограничений.

3. Если какая-либо переменная неограничена по знаку в простом числе, то соответствующее ограничение двойственности есть полное равенство.

Пример 1

Основной

Max Z = x + y

ст. x-y 20

2x +3y 4

5x – 2y 2

x, y 0

Решение

Max Z = x + y

ст. x-y 20 ………… W ₁

2x +3y 4 …………… W ₂

5x-2y 2 …………. W ₃

Двойной

мин. Z _W =20w ₁ + 4w ₂ + 2w ₃

S.t w ₁ +2w ₂ +5w ₃  1

  -w ₁ + 3w ₂ -2w ₃ 1

w ₁ , w ₂ , w ₃ 0

Example 2

Первичный

Min Z = x ₁ +x ₂ +x ₃

ст. 2x ₁ +3x ₂ +5x ₃ 2

3x ₁ +x ₂ +7x ₃ = 3

x ₁ +4x ₂ +6x _{3 1 +4x 2 +6x 3 1 +4x 2 +6019 3 1 +4x 2 .0020 5}

x ₁ , x ₂ , x ₃ 0

Двойник

MAX Z _W = 2x ₁ +3x ₂ +5x ₃ 3

3w ₁ +w ₂ +4w ₃ 1

5w ₁ +7w ₂ +6w ₃  1

w ₁ , w ₃ 0, w ₂ неограничен

Правила решения

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

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

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

Некоторые полезные свойства

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

 1. Любое допустимое решение двойственной задачи устанавливает границу оптимального значения целевой функции в прямой задаче.

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

3. Двойной может быть полезен для анализа чувствительности. Изменение правого ограничения первичного уравнения или добавление к нему нового ограничения может сделать исходное оптимальное решение невозможным.

4. Переменные, которые мы получаем в двойном LPP, дают теневые цены для ограничений основного LPP. Например, предположим, что у вас есть задача максимизации прибыли с ограничением ресурсов, скажем, «j». Тогда значение y _j соответствующей двойной переменной в оптимальном решении говорит вам, что вы получаете увеличение y _j в максимальной прибыли на каждую единицу увеличения количества ресурса j.

5. Иногда проще решить дуал ЛПП. Первичная задача, имеющая много ограничений и мало переменных, может быть преобразована в двойственную задачу с небольшим количеством ограничений и множеством переменных.

#jims #jimsdelhi #managementcollegeindelhi #pgdmcollegesindelhi #mbacollegesindelhi #toppgdmCollegesindelhi #topbschoolsindelhi

Для получения дополнительной информации посетите: https://www.jagannath.org/

Двойственность в линейном программировании | Science4All

Мои статьи по линейной алгебре и линейному программированию являются обязательным условием для этой статьи.

Двойственность — это понятие из математического программирования. В случае линейного программирования двойственность дает гораздо более удивительные результаты.

Двойственная линейная программа

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

$$\textrm{Maximise} \quad \textrm{Value}_\textrm{gold} volume_\textrm{gold} + \textrm{Value}_\textrm{bills} volume_{\textrm{bills}} \\ \\
\textrm{При условии} \quad volume_{\textrm{золото}} + volume_{\textrm{счета}} \leq \textrm{Объем}_{\textrm{лимит}} \\
\textrm{} \qquad \qquad \quad \;\; \textrm{Плотность}_\textrm{золото} volume_{\textrm{золото}} + \textrm{Плотность}_\textrm{банкноты} Volume_{\textrm{банкноты}} \leq \textrm{Вес}_{\textrm {limit}} \\
\textrm{} \qquad \qquad \quad \;\; volume_{\textrm{gold}} \geq 0 \\
\textrm{} \qquad \qquad \quad \;\; volume_{\textrm{bills}} \geq 0$$

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

В исходной программе ограничения имели постоянные числа справа от них. Эти постоянные числа являются нашими ресурсами. Они говорят, что мы можем сделать относительно каждого ограничения. Двойная проблема состоит в том, чтобы оценить, сколько стоят наши объединенные ресурсы. Если предложение соответствует спросу, наши ресурсы будут такими же, как и их потенциал, а это стоит грабежа. Сладкий, правда?

Ресурсы — это концепция, которую я придумал. Это не стандартная концепция.

Давайте подробнее. В двойной задаче мы будем приписывать значения ресурсам (например, «сколько они стоят»). Эти значения называются двойными переменными. В нашем случае у нас есть два ограничения, поэтому у нас будет 2 двойных переменных. Первая двойная переменная, назовем ее $value_{\textrm{volume}}$, относится к значению одной единицы объема. Как вы уже поняли, вторая двойная переменная относится к значению одной единицы веса. $value_{\textrm{weight}}$ кажется подходящим названием для него, верно?

Теперь, держу пари, вы можете записать стоимость ограбления с помощью этих двух новых переменных… Посмотрим, получим ли мы тот же результат.

$$\textrm{Общее значение} = значение_{\textrm{объем}} \textrm{Объем}_{\textrm{лимит}} + значение_{\textrm{вес}} \textrm{Вес}_{\textrm {limit}}$$

Это хорошо, но как определяются значения объема и веса?

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

Очевидно, что стоимость ресурсов зависит от фактической стоимости золота и банкнот на единицу объема. Давайте подумаем о стоимости золота (и тогда вы сможете применить те же рассуждения к векселям). Если бы ограничения позволили нам украсть еще один объем золота, то дополнительная стоимость ограбления была бы по крайней мере равна стоимости этого одного объема золота, верно? Их может быть больше, если мы воспользуемся новыми ограничениями, чтобы украсть что-то еще, кроме золота, которое стоит больше. Я говорю о том, что если бы общий объем позволил нам украсть еще одну единицу объема золота и если бы мы могли унести еще одну единицу веса одного объема золота, то стоимость этой дополнительной кражи составила бы как минимум стоимость еще одного тома золота. Давайте напишем это.

$$value_{\textrm{volume}} + value_\textrm{weight} \textrm{Density}_\textrm{gold} \geq \textrm{Value}_\textrm{gold}$$

Я позвольте вам написать подобное ограничение для счетов. На самом деле, мы можем проделать это рассуждение с любой переменной основной задачи и задать себе вопрос: «Если мы добавим одну единицу переменной, как это повлияет на общую оценку?» Из этого мы выводим ограничение на двойственные переменные. Как видите, любая переменная в основной задаче связана с ограничением в двойственной задаче, и наоборот.

Мы почти закончили. Заметим тот факт, что если мы увеличим общий объем, то у нас будет больше возможностей для первичных переменных, то есть объемов украденного золота и банкнот. Следовательно, значение единицы объема не может быть отрицательным. Это добавляет еще два ограничения на знак двойственных переменных. Теперь мы закончили и можем написать двойственную задачу.

$$\textrm{Минимизировать} \quad value_{\textrm{volume}} \textrm{Volume}_{\textrm{limit}} + value_{\textrm{weight}} \textrm{Weight}_{\textrm {лимит}} \\\\
\textrm{При условии} \quad value_{\textrm{объем}} + value_\textrm{вес} \textrm{Плотность}_\textrm{золото} \geq \textrm{Значение}_\textrm{золото} \\
\textrm{} \qquad \qquad \quad \;\; value_{\textrm{объем}} + value_\textrm{вес} \textrm{Плотность}_\textrm{купюры} \geq \textrm{Value}_\textrm{счета} \\
\textrm{} \qquad \qquad \квадратный \;\; value_\textrm{volume} \geq 0 \\
\textrm{} \qquad \qquad \quad \;\; value_\textrm{weight} \geq 0 $$

Эй, это похоже на линейную программу…

И так всегда! Двойственная программа линейной программы — это линейная программа! Давайте посмотрим на допустимое множество.

Важно отметить, что информация о основных целевых функциях появляется в двойном допустимом множестве. Однако при этом теряется информация о первичных ресурсах. Эта информация появится, если мы нарисуем наборы уровней двойной целевой функции. Тем не менее, если мы нарисуем первичные и двойственные допустимые множества, мы получим всю информацию о линейных программах.

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

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

В дуальности есть еще кое-что интересное: она дает прямой анализ чувствительности. Рассмотрим наши основные проблемы. Было бы интересно узнать, насколько больше я мог бы получить, будь мой рюкзак больше или тело сильнее. Это кажется сложным вопросом в основной программе, но в двойной программе это очень очевидно. Если в рюкзаке окажется на одну единицу объема больше, то дополнительная стоимость ограбления составит $value_\textrm{volume}$. На самом деле это минимизирует дополнительную ценность, которую я буду иметь, но это идеальное приближение для небольшого дополнительного объема рюкзака.

Но это еще не все. В линейном программировании двойственность дает гораздо больше потрясающих результатов! В частности, существует сильная связь между простыми основаниями и двойственными основаниями.

Двойные основания

Заметим, что основная задача эквивалентна следующей формулировке.

$$\textrm{Maximise} \quad \textrm{Value}_\textrm{gold} volume_\textrm{gold} + \textrm{Value}_\textrm{bills} volume_{\textrm{bills}} \\ \\
\textrm{При условии} \quad volume_{\textrm{золото}} + volume_{\textrm{счета}} + volume_{\textrm{unused}} = Volume_{\textrm{limit}} \\
\textrm{} \qquad \quad \;\; \textrm{Плотность}_\textrm{золото} volume_{\textrm{золото}} + \textrm{Плотность}_\textrm{счета} volume_{\textrm{счета}} + вес_{\textrm{неиспользованный}} = Weight_ {\textrm{limit}} \\
\textrm{} \qquad \qquad \quad \;\; volume_{\textrm{gold}} \geq 0 \\
\textrm{} \qquad \qquad \quad \;\; volume_{\textrm{счета}} \geq 0 \\
\textrm{} \qquad \qquad \quad \;\; volume_{\textrm{unused}} \geq 0 \\
\textrm{} \qquad \qquad \quad \;\; weight_{\textrm{unused}} \geq 0. $$ 9T \\
\textrm{} \qquad \qquad \quad \;\; y, s \geq 0.$$

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

Хорошо, я действительно не понял две последние формулы…

Не волнуйся, это не так важно. Это даже не стандартная формулировка. Мне нравится эта формулировка, потому что она показывает сходство между первичной и двойной программами. Это также хороший способ описать двойственность и ее свойства. Будьте осторожны с другими препаратами. Результаты, которые я приведу здесь, может быть трудно перенести на другие формулировки.

Обратите внимание, что теперь у нас есть переменные, представленные векторами $x$, $e$, $y$ и $s$. Кроме того, каждая переменная векторов $e$ и $s$ фигурирует одна в одном из ограничений первичной или двойственной программы.

Это хорошо, но я действительно не понимаю, что представляют собой эти резервные переменные…

Переменные легко понять на следующем графике. Начальные переменные $x$ — это координаты точек, а переменные резерва — расстояния от различных ограничений. Блок переменных резерва немного сложнее. Чтобы представить это, имейте в виду, что пределы ограничений являются наборами уровней. Эти наборы уровней перемещаются по мере изменения значения, которое они принимают.

Обозначим через $n$ количество переменных $x$, а через $m$ количество переменных $e$. Обратите внимание, что $n$ — это количество ограничений в двойственной программе, а $m$ — это количество ограничений в основной программе. Следовательно, основная база определяется выбором $m$ переменных, значения которых будут обнулены. Эти переменные $m$ образуют «базу ограничений», о которой я упоминал в статье о линейном программировании. Остальные $n$ переменных являются «базовыми» в обычном их определении.

Будьте осторожны, эти обозначения не являются стандартными обозначениями.

Что интересно, так это то, что двойные основания ведут себя противоположным образом. На самом деле, они требуют $n$ переменных в базе ограничений и $m$ переменных в базе. Что еще более интересно, так это то, что мы можем сопоставить каждое простое основание с двойным основанием. По сути, каждой переменной вектора $y$ соответствует ограничение, которому соответствует переменная вектора $e$. Аналогично сопоставляем переменные векторов $x$ и $s$. Таким образом, с любым основным основанием мы можем связать двойное основание, выбрав добавление переменных двойного основания, которые соответствуют основным переменным, не входящим в основное основание. Другими словами, всякий раз, когда мы не фиксируем первичную переменную на 0, мы фиксируем соответствующую двойственную переменную на 0.

Это дает нам следующее сопоставление оснований (нарисованных по цветам точек).

Ограничения двух графов могут совпадать. Неотрицательные ограничения исходных переменных соответствуют фактическим ограничениям в другой другой программе. База, определяемая пересечением двух цветов ограничений в одной задаче, сопоставляется с базой, определяемой пересечением двух других цветов ограничений в другой задаче. На двух графиках не было нарисовано только основное основание, связанное с двойным желтым основанием, потому что невозможно было нарисовать основное пересечение зеленых и синих ограничений.

Подождите… Еще интереснее: значения целевой функции простого основания и связанного с ним двойного основания совпадают! Учитывая то, как мы ввели дуальную программу, это очень удивительно. Вы можете доказать это с помощью вычислений, но настоящая причина, по которой мы получили такой результат, связана с построением лагранжиана. Если бы мы это сделали, мы могли бы легко доказать, что для любых прямых и двойственных переменных, удовлетворяющих ограничениям равенства, разность прямой по двойственным целевым функциям равна $s^Tx + y^Te$. Это значение называется дополняющая ненадежность . Оно равно нулю, если двойственные переменные соответствуют двойственному основанию простых переменных.

Подождите… Если обе программы имеют одинаковые значения, не должна ли двойная целевая функция всегда быть выше, чем основная целевая функция?

На самом деле обе программы имеют одинаковые значения. Поскольку основная программа представляет собой задачу максимизации, значение ее целевой функции всегда меньше оптимального значения. А в дуальной программе наоборот. Однако это рассуждение работает только для переменных допустимого множества! Таким образом, задача оптимизации эквивалентна поиску первичной допустимой базы с ассоциированной с ней двойственной допустимой базой!

На двух графиках только розовые точки являются первичными и двойственными: они представляют решение линейных программ!

Круто! Можем ли мы использовать его для разработки алгоритма оптимизации?

Да, можем. И это дает нам… симплекс-метод! По сути, симплекс-метод состоит в переходе от изначальной допустимой базы к строго лучшей первичной допустимой базе. Но его можно в равной степени рассматривать как алгоритм, который переходит от первично допустимых оснований к первично допустимым основаниям с ассоциированным двойным основанием, которое становится все более и более выполнимым. Этот критерий «близости к осуществимости» может, например, означать наличие самой отрицательной переменной как можно ближе к 0. Как только самая отрицательная переменная двойного основания неотрицательна, у нас есть двойное допустимое основание. Таким образом, мы достигли оптимума.

Точно так же мы могли бы перейти от допустимых двойных оснований к допустимым двойным основаниям, пытаясь достичь соответствующей допустимой первичной базы. Это эквивалентно применению симплексного метода к двойной программе и известно как двойной симплекс.

Как вы понимаете из этого замечания, существует огромная связь между двойными переменными и снижением затрат. Это можно наблюдать на графике слева. Сниженная стоимость говорит вам, насколько увеличится целевая функция, если вы потеряете одно из ограничений базового ограничения и отойдете от него на краю, определяемом другими ограничениями базового ограничения, на 1 единицу связанной переменной резерва. с этим ограничением. Эта приведенная стоимость является приращением значения целевой функции при движении по зеленой стрелке.

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

Как видно на графике, двойная переменная противоположна приведенной стоимости резервной переменной, связанной с двойной переменной. Будьте осторожны со знаком. Наш результат верен здесь, потому что у нас меньше или равно неравенств в основной программе (или, что то же самое, перед переменными резерва стоит «+»). Если бы у нас были более высокие или равные неравенства или резервные переменные, которым предшествует минус, у нас было бы равенство приведенных затрат и двойных переменных.

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

Отличная идея! Это приводит к… методу внутренних точек! Идея метода внутренних точек состоит в том, чтобы оставаться внутри допустимого множества и сходиться к оптимуму. Это позволяет избежать возможных многочисленных итераций перехода от экстремальных точек к экстремальным точкам и пропускает проблемы вырождения. Для большого числа переменных метод внутренних точек быстрее, чем симплексный метод.

Для заданного положительного действительного числа µ метод внутренней точки состоит в нахождении прямого и двойственного векторов, которые удовлетворяют ограничениям равенства, являются положительными и такими, что произведение каждой простой переменной на связанную с ней двойственную переменную равно № . Затем, уменьшая значение µ , мы приближаемся к прямому и двойственному оптимальным решениям. Преимущество такого метода заключается в том, что мы можем использовать алгоритмы на основе градиента для оптимизации проблемы, что гарантирует очень быстрое решение. Другое очень интересное преимущество заключается в том, что его можно обобщить на полуопределенное программирование.

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

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

Вырождение

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

Что не так с этим чемоданом?

Плохо для симплексного алгоритма. Сначала он заставляет нас сделать выбор. Предположим, что мы находимся на базе ограничений, определяемой зеленым и желтым ограничениями, и что симплекс-алгоритм решает отказаться от зеленого ограничения. Затем мы будем двигаться по желтому ограничению, пока не достигнем черной точки. Эта черная точка может быть определена тем фактом, что мы пересекли ограничение красного или синего цвета. Один из них будет добавлен в базу ограничений. Нам нужно сделать выбор. На самом деле это не проблема. А вот замечание — большая проблема.

Предположим, что синие и желтые ограничения образуют базу ограничений (это означает, что в базе находятся переменные резерва, соответствующие зеленым и красным ограничениям). Если мы вынесем желтые ограничения из базы ограничений, то мы будем двигаться по синей линии от желтых ограничений. Направление вдоль синего ограничения улучшает целевую функцию, а это означает, что оно связано с положительной приведенной стоимостью. Поэтому следует ожидать строгого возрастания целевой функции. Тем не менее, из-за того, что красное ограничение пересекается в черной точке, красное ограничение будет добавлено к базе ограничений, которая, следовательно, будет определять ту же самую черную точку. {14}$. Правление Блэнда имеет хорошие шансы посетить половину из них… Это займет целую вечность! Может быть, дни… Это очень-очень плохо. И все же размерность 25 очень маленькая.

Хорошо, вы правы, вырождение очень плохо для симплексных методов… Что мы можем с этим поделать?

Мы могли бы подумать о добавлении небольших возмущений в ограничениях. Это позволит избежать вырождения. Однако на самом деле это не улучшит разрешение, так как создаст несколько точек очень близко друг к другу. Симплекс-метод по-прежнему будет перемещаться по этим точкам с очень небольшим улучшением целевой функции. По сути, все еще есть хороший шанс посетить половину всех баз, связанных с вырожденной точкой, так что это все еще нехорошо. Такие случаи настолько похожи на вырождение, что их можно считать таковыми.

Проблема вырождения часто решается путем управления набором ограничений и набором переменных. В нашем случае, если бы мы могли обнаружить, что основное синее ограничение бесполезно, мы бы решили проблему вырождения. В Монреале также были разработаны несколько методов, таких как агрегация динамических ограничений (DCA), интегральный первичный симплекс (IPS) и улучшенная генерация столбцов (ICG). Короче говоря, я бы сказал, что они классифицируют переменные в зависимости от того, как они появляются в ограничениях, и решают только небольшую группу переменных. Они могут рассматривать другие переменные, если критерий оптимальности не выполняется. Узнайте больше из моей статьи о создании столбцов.

Причина, по которой я решил поговорить о вырождении в статье о двойственности, заключается в том, что двойственность предлагает интересное понимание вырождения.

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

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

Всегда ли вырожденная крайняя точка связана с двойным ограничением?

Нет. Обозначим n размерность первичного допустимого множества. Рассмотрим вырожденную точку. Назовем вырожденность количеством ограничений, которые не требуются для ее определения. Обозначим d вырождение. В нашем случае вырождение d равно 1. Тогда число отличных от нуля простых переменных в этой точке равно n-d . Таким образом, количество двойных ограничений, которые есть во всех базах двойных ограничений, связанных с вырожденной точкой, равно 9.0533 н-д тоже. Их пересечение определяет двойственное пространство, связанное с вырожденной точкой. Поскольку двойное пространство требует n ограничений для определения точки, двойное пространство, связанное с вырожденной точкой, представляет собой векторное пространство размерности d . Оно соответствует ограничению, если d = n-1 , но обычно представляет собой векторное пространство меньшей размерности. Поскольку все это векторное пространство соответствует единственной первичной точке, которая имеет единственное целевое значение, все векторное пространство имеет единственное целевое значение. Следовательно, все векторное пространство включено в набор уровней двойной целевой функции.

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

Что происходит в неоптимальной вырожденной точке?

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

Зеленое ограничение по-прежнему представляет двойной набор, связанный с вырожденной точкой. Однако в этом случае весь этот двойственный набор невозможен.

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

Двойная переменная стабилизация (DVS) следует этой идее. Было доказано, что такие случаи эффективны, особенно в случае генерации столбцов. Идея состоит в том, что как только итерации симплекса дают близкие двойственные точки, мы добавляем штраф к двойственным точкам, далеким от тех, которые мы недавно нашли. Прочитайте мою статью о DVS, чтобы лучше понять это.

Подведем итоги

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

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