45460

Двойственность в ЛП, построение моделей двойственных задач

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-11-17

139 KB

20 чел.

17 Двойственность в ЛП, построение моделей двойственных задач.

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

Рассмотрим общий и симметричный случаи. Если в исходной задаче все условия представлены в виде неравенств и все переменные ограничены по знаку, то имеет место симметричная пара. Если в исходной задаче есть равенства и/или переменные не ограничены по знаку, то имеет место общий случай.

ПРИМЕР Рассмотрим планирование некоторого производства. Для выпуска 3 видов продукции необходимы  4 вида ресурсов.Известно: стоимость единицы продукции, норма расхода каждого вида ресурса на единицу продукции.

Прямая задача:

L=C 1 x 1 + C 2 x 2 + C 3 x 3   max;

U 1 : a 1 1 x 1 + a 1 2 x 2 + a 1 3 x 3 b 1 ;

U 2 : a 2 1 x 1 + a 2 2 x 2 + a 2 3 x 3 b 2 ;

U 3 : a 3 1 x 1 + a 3 2 x 2 + a 3 3 x 3 b 3 ;

U 4 : a 4 1 x 1 + a 4 2 x 2 + a 4 3 x 3 b 4 ; x j   0

Двойственная задача:  = b 1 U 1 + b 2 U 2 + b 3 U 3 + b 4 U 4  min ;

a 1 1 U 1 + a 2 1  U 2  + a 3 1 U 3 + a 4 1 U 4 C 1 ;

а 1 2 U 1 + a 2 2  U 2  + a 3 2 U 3 + a 4 2 U 4 C 2 ;  (1)

a 1 3 U 1 + a 2 3  U 2  + a 3 3 U 3 + a 4 3 U 4 C 3 ; U I   0.

Это симметричная пара. Правила:

  1.        Если в прямой задаче  целевая функция минимизируется, то в двойственной – максимизируется, и наоборот.
  2.        Коэффициенты критерия двойственной задачи образуются из компонентов вектора ограничений прямой задачи.
  3.        Компоненты вектора ограничений двойственной задачи образуются из коэффициентов линейной формы (критерия) прямой задачи. Матрица условий двойственной задачи образуется транспонированием матрицы условий прямой задачи. Знаки неравенств двойственной задачи обратны знакам неравенств прямой.

Правила 1) – 4)  свойственны любым задачам, а 5)  - только симметричным. В двойственной задаче U i  - переменные (двойственные переменные). Число условий двойственной задачи равно числу переменных прямой задачи. Число переменных двойственной задачи равно числу условий прямой задачи. Если для двойственной задачи построить двойственную, то получим прямую.

Уравнение размерности: [a][U]=[C].

Пусть В 1 – фонд временного оборудования (сколько часов оборудование может работать в течение определенного времени). Тогда

U имеет смысл стоимости единицы ресурса в единицах критерия, поэтому двойственные переменные называют теневыми ценами (та цена, по которой готовы приобрести единицу ресурса).

ПРИМЕР.

В левой части (1) определяются затраты по всем видам ресурсов на единицу продукции, в правой – произведенная стоимость, следовательно, эти неравенства означают, что суммарные затраты произведенной продукции не могут быть меньше, чем произведенная стоимость. Другой вариант интерпретации двойственной задачи. Общий случай: будем опираться на правила построения симметричной пары. Среди условий прямой задачи имеет место равенство. Пусть k - е условие -  равенство (остальные условия представлены неравенствами).

   

Двойственная задача:

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

 

В двойственной задаче:

18  Экономическая интерпретация двойственности

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

Интерпретация двойственной задачи

Что отражает двойственная модель? Оказывается, она дает возможность оценить решение исходной (прямой) задачи. В рассматриваемом примере прямая задача состоит, фактически, в наилучшем использовании всех имеющихся ресурсов. Каждому варианту плана поизводства продукции соответствует свое использование ресурсов, а, следовательно, и их полезность или значимость. Под последним понимается степень влияния ресурса на результат. Так как каждому условию прямой задачи, отражающему использование ресурса, ставится в соответствие двойственная переменная, то именно она и является мерилом значимости этого ресурса. Действительно, рассмотрим уравнение размерности условия двойственной задачи [A][U]=[C]. Пусть, например, ресурс – фонд времени оборудования (сколько часов оборудование может быть загружено в течение планового периода). Тогда размерность двойственной переменной будет.Итак, U дает стоимость единицы ресурса в единицах критерия, то есть в нашем случае – прирост произведенной стоимости в рублях на каждый дополнительный час работы оборудования. Ниже, в теоремах двойственности, это будет показано строго математически. Поэтому двойственные переменные называют также теневыми ценами. Чтобы увидеть отличие теневой цены от рыночной, возьмем конкретные цифры. Пусть рыночная цена некоторого ресурса, полностью используемого в производстве, равна 500 руб/кг и 1 кг достаточно (при наличии других ресурсов) для выпуска дополнительной продукции на сумму 100000 руб. Тогда теневая цена этого ресурса равна 100000 руб. Если поставщик сорвал поставку данного ресурса, то он должен нести ответственность не в размере рыночной цены, а по теневой цене за каждую единицу недопоставленного ресурса. Такое предложение было высказано впервые Л. Канторовичем, который называл двойственные переменные объективно обусловленными оценками, сокращенно О.О.О. (объективные цены, складывающиеся в конкретной ситуации производства и потребления).Таким образом, чем больше абсолютная величина двойственной переменной, тем выше значимость ресурса в полученном решении, и наоборот, более сильному влиянию ресурса на критерий соответствует большее значение двойственной переменной. Теперь интерпретируем условия двойственной задачи. Если Ui – объективная цена за единицу ресурса, то левая часть неравенства двойственной модели представляет собой полные затраты на производство единицы продукции, а все неравенство отражает тот факт, что произведенная стоимость Ci не может превышать суммарных затрат. Значимость ресурса эквивалентна его дефицитности. Поэтому критерий двойственной задачи можно интерпретировать как суммарную дефицитность ресурсов, которую следует минимизировать.Другая трактовка заключается в том, что двойственная задача моделирует взаимодоговоренности Покупателя и Продавца ресурсов. Продавец готов продать свои ресурсы, отказавшись от производства продукции, если цены на них (Ui) будут такими, что он получит за ресурсы, расходуемые им на единицу продукции, не меньше Ci, то есть не меньше того, что он имел бы от производства этой продукции. Эти требования выражаются неравенствами двойственной задачи. С другой стороны, Покупатель стремится к таким ценам, которые минимизируют плату за все ресурсы. Это стремление и выражает критерий двойственной задачи.

19 Теоремы двойственности.

Теорема 1. Если в оптимальном решении прямой задачи условие выполняется как строгое неравенство:

то соответствующая двойственная переменная равна нулю:

 U * i=0.   (2)

(1) означает, что это ресурс используется не полностью, следовательно, такое изменение этого ресурса не влияет на расширение, то есть значение двойственной переменной равно нулю. Или, если дополнительная переменная больше нуля, то соответствующая двойственная переменная равна нулю.

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

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

Геометрическая интерпретация:

                                                                       

          b2                    L*     D – допустимое множество;

      b1                             1)изменение b4 не повлияло на L*;

                             D                         2)изменение  b1 и b2 влечет за собой             b3                                      изменение критерия.

         b4   

Допустим, что решение не является единственным

          A                *изменяем b1 – критерий не меняется;

                 b2  *при любом измененииb2 происходит

   b1                  b3       L*            изменение критерия.

b5         D

                      b4 

Теорема 1`. Если в оптимальном решении двойственной задачи условие выполняется как строгое неравенство:

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

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

Если произведенная стоимость равна затратам, то  производим эту продукцию.

Вторая основная теорема двойственности

Для того, чтобы векторы x* и U* являлись оптимальными решениями прямой и двойственной задачи соответственно, необходимо и достаточно выполнение следующих условий:

ПРИМЕР. Прямая задача:

L=7x1+5x2max  U1: 2x1+3x219; U2: 2x1+ x2 13;

                           U3  3x2 15; U4: 3x1  18; x1, x2 0.

Двойственная задача:

=19U1+13U2+15U3+18U4miin;

2U1+2U2+3U47; 3U1+U2+3U35; Ui 0 i.

                                    

Так как х5 и х6 не равны нулю, то третье и четвертое условие прямой задачи выполняются как строгие неравенства.

.

Теорема 3. Если x и U – допустимые решения прямой и двойственной задачи соответственно, то есть они удовлетворяют модели. прямая задача:

L=CTxmax; AxB; x0.

двойственная задача:

=BTUmin;  AT UC; U0, то  L(x) (U).

Доказательство.

Теорема 4. Если x* и U* - допустимые решения прямой и двойственной задачи L(x*)= (U*), то эти решения  являются оптимальными решениями прямой и двойственной задачи соответственно. Доказательство. Из теоремы (3) следует:x: L(x)  (U*).

И, так как L(x*)= (U*) по условию, то  x L(x) L(x*), следовательно, х*- оптимальное решение прямой задачи.

Аналогично доказывается, что U* - оптимальное решение двойственной задачи.

Теорема5. Для любых оптимальных x* и U* линейные формы равны:  L(x*)= (U*).

Доказательство.

левые части равны между собой, следовательно, L(x*)=(U*).

Теорема 6. Если линейная форма одной из задач двойственной пары не ограничена, то условия другой противоречивы. (Обратное не всегда правильно)

Доказательство. Допустим, что при неограниченности L(x) в прямой задаче условия двойственной задачи непротиворечивы, то есть совместны, следовательно, существует допустимое решение, а значит. значение критерия конечно.

L(x)(x), получается противоречие условию теоремы.

Следовательно, условия двойственной задачи противоречивы.

Первая основная теорема двойственности.

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

Исходя из теории двойственности, получаем методы:

  1.  двойственный симплекс-метод (метод последовательного улучшения оценок) – по сути, является обратным симплекс-методу. В основе лежит то, что начинаем работу с условиями прямой задачи и постепенно переходим на решение двойственной.

Прямую задачу решают двойственно: строят оптимальные решения. но берут недопустимые Х. Далее  при Δ0 идут так, чтобы Х стремились бы к допустимым. Вначале выбирают строку по minX (из отрицательных). Затем делят Δ на отрицательное и по минимальному отношению находят направляющий столбец. Последующие действия – то есть же самые.

  1.  метод сокращения невязок(венгерский метод), в нем используются оба подхода.

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

20 Двойственный и модифицированный симплекс методы.

Модифицированный алгоритм (обратной матрицы)

 Для всего текущего решения   - величина одна и та же.  

 

Для вычисления оценок мы можем использовать только обратную матрицу. Пусть имеется матрица, обратная базисной. Тогда по формуле (5) вычислим А, по формуле (4) вычисляем Δj для небазисных переменных. Далее действуем, как в стандартном методе, то есть находим переменную, которая должна вводиться в решение. Восстанавливаем столбец, который будет играть роль направляющего: по формуле (3)  (Arr-й вектор условий ) вычисляем

Находим направляющий элемент. Затем получаем новую обратную матрицу путем симплекс-преобразования обратной матрицы. Далее процесс повторяется. Часто этот метод основан на мультипликативном представлении обратной матрицы. Это позволяет значительно экономить объем обратной матрицы. В начальном решении матрица и обратная  матрица равны (единичные). Далее:

- это мультипликативное представление. Ek  хранит отношения направляющей строки.

- этот вариант тем эффективнее, чем меньше плотность вариантов, но недостатком является то, что неразрешимость задачи появляется немного позднее.

27 Двойственность Т-задач, экономическая интерпретация потенциалов.

Двойственность транспортных задач

Чтобы построить двойственную задачу, необходимо провести преобразование прямой задачи:

Двойственная задача:

Δij0.Итак, двойственные переменные играют роль потенциалов.

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

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


 

А также другие работы, которые могут Вас заинтересовать

36902. Изучение среды и простейших элементов 405.5 KB
  Домашнее задание выполняется по различным вариантам. В данном варианте меняется только цвет фона всей формы и цвет фона окна Text3. Варианты индивидуальных заданий. Разработать Windowsприложение вычисления значения функции у средствами Visul Bsic Вариант №1 у = b^2 c^2 t^2 Вариант №2 y = bc^3 c t^2 Вариант №3 y = b^3 c t^2 Вариант №4 y = c3 t c^2 Вариант №5 y = c^2 b t^2 Вариант №6 y = tk^5 c b^3 Вариант №7 y = c^3 t^2 b^5 Вариант №8 y = c^2 t b^2 Вариант №9 y = c^3 t b^2...
36903. Разработка приложений с разветвляющимися алгоритмами 359 KB
  Lbel1 Cption При х = Lbel2 Cption Функция вычисляется по формуле: Lbel3 Cption Получен результат Y = Lbel4 Cption Lbel5 Cption Лабораторная работа 2.Вариант 37 Text1 Text Text2...
36904. Изучение основных явлений поляризации света 483 KB
  Изучение основных явлений поляризации света. Цель работы: Получение и исследование поляризованного света и исследование свойств обыкновенных и необыкновенных лучей полученных с помощью двояко преломляющего кристалла. Принципиальная схема установки или её главных узлов: 1 упражнение: 2 упражнение: ИС источник света; ИС источник света; П поляроид 1поляризатор; Д...
36905. Изучение физических явлений, лежащих в основе работы полупроводникового фотоэлемента с запирающим слоем, определение зависимости фототока от освещенности, снятие ширины запрещенной зоны полупроводника 713 KB
  Цель работы: Изучение физических явлений лежащих в основе работы полупроводникового фотоэлемента с запирающим слоем определение зависимости фототока от освещенности снятие ширины запрещенной зоны полупроводника. На рисунке выше Ес энергия дна свободной зоны Ев энергия потолка валентной зоны; Fм Fп уровни Ферми металла и полупроводника Ам Ап работы выхода электрона из металла и полупроводника. Если уровень Ферми изолированного металла Fм лежит выше уровня Ферми полупроводника Fп т. Ам Ап то в первый момент их...
36906. Измерение холловской разности потенциалов в полулроводниковой пластине и определение концентрации, подвижности и знака носителей заряда, участвующих в токе 294.5 KB
  Эффект Холла в полупроводниках. Основные теоретические положения к данной работе основополагающие утверждения: формулы схематические рисунки: Эффект Холла заключается в возникновении поперечной разности потенциалов при пропускании тока через металлическую или полупроводниковую пластинку помещенную в магнитное поле направленное под некоторым углом к направлению тока. Классическая...
36907. Подтверждение боровской теории строения водородоподобных атомов 255.5 KB
  Основные теоретические положения к данной работе основополагающие утверждения: формулы схематические рисунки: В основе теории Бора лежат следующие постулаты: Первый постулат Бора постулат стационарных состояний: существуют некоторые стационарные состояния атома находясь в которых он не излучает энергии. Второй постулат Бора правило квантования орбит утверждает что в стационарном состоянии атома электрон двигаясь по круговой орбите должен иметь квантованные значения момента импульса удовлетворяющие условию где п = 1; 2;...
36908. Изучение процессов генерации и рекомбинации неравновесных носителей заряда в твердых телах при возбуждении их светом, экспериментальная проверка кинетики затухания рекомбинационной люминесценции при наличии центров захвата(ловушек) 658 KB
  Таблицы и графики Результаты измерений и расчетов: tc I1 мА I2 мА I3 мА I4 мА I5 мА Icp мА y = 10 0292 0284 0305 0293 0290 0293 0306 15 0264 0260 0265 0263 0261 0263 0379 20 0237 0238 0241 0243 0235 0239 0446 25 0220 0219 0216 0225 0228 0222 0501 30 0210 0209 0210 0203 0220 021 0543 35 0196 0192 0190 0195 0193 0193 061 40 0187 0185 0180 0179 0182 0183 0653 50 0170 0165 0165 0167 0170 0167 073 60 0158 0154 0156 0153 0154 0155 0796 70 0149 0147 0143 0144 0146...
36909. Кластерный анализ. Агломеративные методы 16.97 KB
  В качестве выбора нового расстояния между кластерами рассмотреть: 1Метод дальнего соседа 2Метод ближнего соседа. 3 Используем метод дальнего соседа. 4 Используем метод ближнего соседа. Решение поставленной задачи: 1Центрируем и нормируем: 2Рассчитаем матрицу расстояний: 1 2 3 4 5 6 Далее поскольку матрицы будут симметричными будут записаны полученные данные только над главной диагональю 3По методу...
36910. МОДЕЛИРОВАНИЕ ЗВЕНЬЕВ АВТОМАТИЧЕКСКИХ СИСТЕМ 346.5 KB
  1 Безынерционное звено Рис. 2 Интегрирующее звено Рис. 3 Апериодическое звено 1 порядка Рис. 4 Колебательное звено Переходные ht и передаточные Wp характеристики звеньев имеют вид: Безынерционное звено Wp=k Интегрирующее звено Wp=k p Апериодическое звено Wp=k Tp1 Колебательное звено Wp=k1 T2p22k2Tp1...