Показать что отношение двойственности симметрично

Симметричные и несимметричные двойственные задачи

Различают симметричные, несимметричные и смешанные двойственные задачи.

Симметричные двойственные задачи.

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

Дана исходная задача.

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:

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

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

Дана исходная задача.

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, согласно записанным правилам:

Смешанные двойственные задачи.

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

Зная решение одной из двойственных зада можно найти решение другой задачи.

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

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

Источник

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

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

Симметричная двойственная задача

Исходную задачу (1) часто называют прямой задачей, а задачу (2) – двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) – двойственной. Задачи (1) и (2) называются симметричными двойственными задачами.

Пример составления симметричной двойственной задачи

Дана задача линейного программирования:
;

Составить двойственную задачу.

Перепишем систему ограничений, явно указывая коэффициенты при переменных:

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, третью строку запишем как третий столбец.

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

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

Задача на максимум

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1) ;
(5.2)

Двойственная задача имеет вид:
(6.1) ;
(6.2)

Связь с симметричной парой двойственных задач

Покажем, что несимметричную пару задач (3)-(4) можно получить из симметричной пары (1)-(2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)
и системой ограничений
(3.2)
Каждое равенство можно представить двумя неравенствами:

Неравенства со знаками умножим на –1 :

Система ограничений имеет неравенств.

По формулам (1)-(2) получаем двойственную задачу:
;

двойственная задача имеет неотрицательных переменных:
.
Нетрудно видеть, что эти переменные входят в задачу в виде разностей
.

И мы получаем двойственную задачу (4):
(4.1) ;
(4.2)

Если мы за исходную задачу возьмем (4), то, выполняя все действия в обратном порядке, получим двойственную задачу (3).

Тем же способом можно из задачи (5) получить двойственную задачу (6) и из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

Все это позволяет нам сформулировать правила составления двойственных задач.

Правила составления двойственных задач

Пример составления смешанной двойственной задачи

Дана задача линейного программирования:
;

Составить двойственную задачу.

Перепишем систему ограничений, явно указывая коэффициенты при переменных:

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, и так далее.

Составим двойственную задачу как для симметричной пары.
;

Поскольку в исходной задаче переменные и могут иметь произвольные знаки, то 3-я и 4-я строки системы ограничений двойственной задачи являются равенствами.

Таким образом, двойственная задача имеет вид:
;

Источник

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

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

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

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

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

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

Теорема существования решения

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

Теорема (принцип) дополняющей нежесткости

Оптимальное решение прямой задачи программирования получается только при одном значении x_Q. Это справедливо и для переменной y_Q в двойственной задаче.

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

Основное неравенство двойственности. Для любых допустимых решений Х и Y пары двойственных ЗЛП имеет место неравенство

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

Теорема существования (малая тероема двойственности)

Чтобы прямая и двойственная задачи имели opt решения, необходимо и достаточно, чтобы существовали допустимые решения для каждой из них.

Теорема 1 двойственности.

Если одна из пары двойственных задач имеет opt решение, то и другая его имеет. Причем экспериментальные решения их целевых ф. равны; если же ЦФ одной из задач не ограничена, то система ограничений другой противоречива. Интерпретация: оптимальное использование ресурсов – opt план. Суммарная оценка ресурсов = оценке продукта полученного при opt плане. Любой другой план не рентабелен. C_j – стоимость единицы продукции (внешняя оценка) y_i – стоимость единицы ресурса (внутренняя оценка). Эти двойственные оценки выступают как инструменты балансирования затрат и результатов. Имеет место x_j ​ ​ y_m +_j ; x_n+i y_i.

Теорема 2 двойственности (о дополняющей нежесткости)

Для того, чтобы допустимые решения X и Y пары двойственных задач были оптимальными, необходимо и достаточно выполнить условия:

То есть, если какое-либо ограничение одной ЗЛП обращается ее opt планом в строгое равенство, то соответствующая переменная двойственной задачи в ее opt плане равна нулю; если же какая-либо переменная opt-го решения одной ЗЛП положительна, то соответствующее ограничение в двойственной ЗЛП ее opt планом обращается в точное равенство.

Теорема Кёнига хорошо иллюстрирует использование принципа двойственности ЗЛП.

Формулирование теоремы. Максимальное число попарно неколлинеарных единиц любой булевой матрицы равно минимальному числу линий, покрывающих все единицы матрицы.

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

Минимальное число линий, покрывающих все единицы матрицы [C_ij], найдем, решив линейную задачу:

Оптимальному решению (u*_i, v*_j) последней задачи отвечает минимальное покрытие, состоящее из множества строк I, для которых u*_i = 1 и столбцов J, для которых u*_j =1.

Матрицы А и А Т коэффициентов (*), (**), (***) являются абсолютно унимодулярными, как матрицы двудольного графа. Поэтому условия целочисленности переменных заменяем на условие их неотрицательности, и тогда получаем пару двойственных задач линейного программирования и согласно теореме двойственности имеем:

Линией матрицы называется ее строка или столбец. Два элемента матрицы называются неколлинеарными, если они не лежат на одной линии.

Матрица называется абсолютно унимодулярной, если все ее ненулевые миноры равны 1, либо -1.

Следствие. Матрица инциденций неориентированного графа G абсолютно унимодулярна тогда и только тогда, когда G – двудольный граф. В двудольном графе все простые циклы имеют четкую длину

Принцип двойственности в задачах линейного программирования.

Предположим, что руководство предприятия из анализа конъюнктуры рынка продукции приняли решение: производство сократить, а от запасов сырья избавиться, (продать на рынке) и при этом не нанести себе убытков.

С этой целью руководство должно назначить стоимости y_i за единицу сырья вида S_i, стремясь при этом минимизировать общую стоимость сырья (чтобы быстрее продать сырье): Ф = Σ 4 _i=1 b_iy_i

Выручка предприятия от продажи сырья, расходуемого на единицу продукции П_i, составит: Σ 4 _i=1 a_ij y_i

И по условию она не должна быть меньше С_j (в противном случае предприятию выгоднее не продавать сырье, а использовать его для нужд производства, выпуска продукции).

Сформулируем исходную и двойственную задачи:

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

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

Коэффициенты ЦФ первой задачи являются свободными членами системы ограничений второй.

Свободные члены системы ограничений первой задачи являются коэффициентами линейной системы во второй задаче.

Матрица коэффициентов второй задачи является транспонированной к матрице коэффициентов ограничений первой задачи.

Знаки неравенств в ограничениях второй задачи противоположны знакам неравенств в ограничениях первой задачи.

Для того чтобы векторы X opt = и Y opt = были решениями пары задач, необходимо и достаточно, чтобы их компоненты удовлетворяли следующим условиям:

Эти условия называют принципом дополняющей нежесткости. Если исходная (прямая) задача задана в канонической форме, то двойственная к ней называется несимметричной. Для несимметричной двойственной задачи соблюдается условие y_i ≥ 0.

Теория ЗЛП доказывает, что компоненты оптимальных планов взаимно двойственных задач, приведенных к каноническому виду, соответствуют одни другим. То есть базисные переменные основной задачи соответствуют свободным переменным двойственной задачи и наоборот, j = 1(1)n, x*_j ​ y*_{m +j} ; x*_n+i ​ y*_i ; i = 1(1)m.

Размерности в табличке m и n берутся в задаче для y-ков записанной в канонической форме.

Пример. Двойственный симплекс метод.

Исходная задача. Имеется три вида продуктов П_j, причем единица веса каждого из видов продуктов содержит a_ij единиц (питательных веществ). Для нормальной жизнедеятельности человек должен потреблять не менее b_i единиц вещества B_i в сутки. Стоимость единицы продукта П_j равняется C_j. Требуется составить оптимальный суточный рацион питания, т.е. найти количество x_j продукта, которое должен потреблять человек, чтобы стоимость питания была бы минимальной, если известно, что

такие значения его компонентов x_j, j = 1(1)3, которые минимизируют целевую функцию (Ц) Q = 3x₁ + 2x₂ + x₃ и удовлетворяют ограничениям неравенствам

x_j ≥ 0; j = 1(1)3 = n

Для приведения задачи к каноническому виду введем дополнительные переменные x₄, x₅, x₆, x₇, переменных стало больше чем уравнений n – m = 7 – 4 = 3, следовательно, части из них (трем любым,) для получения решения можно задать произвольные значения (задают, как правило, нулевые значения), возникает число сочетаний из n по m вариантов. Система ограничений примет вид равенств

x_j ≥ 0; j = 1(1)3 = n, i = 1(1)4 = m.

Назначаем опорный план. Выбор в качестве базисных переменных x₄, x₅, x₆, x₇ приводит к недопустимому опорному плану. Так как знаки левой и правой частей различны. (Свободные переменные x₁ = x₂ = x₃ = 0) Метод искусственного базиса приводит к увеличению числа неизвестных задач, что нежелательно. Анализ задачи показывает, что число уравнений в системе ограничений больше числа переменных. Поэтому попытаемся применить принцип двойственности, т.е. вначале решим двойственную ЗЛП, а затем найдем решение исходной.

y_i ≥ 0; i = 1(1)4.

при ограничениях (в ограничения добавили новые переменные):

y_i ≥ 0; i = 1(1)7.

Базисные переменные y₅, y₆, y₇ и ЦФ выражаем через свободные переменные, т.е. из свободных членов (правых частей, обозначенных γ_i ) вычитаем левые части ограничений

γ₀ =0, так как ЦФ не содержит свободного члена.

и строим симплекс таблицу с двумя полуклетками. Направляющий столбец y₃, направляющая строка y₆.

Анализ таблицы показывает, что все коэффициенты ЦФ при свободных переменных положительны. Следовательно, план Y не является оптимальным, ЦФ можно уменьшить, увеличивая значения соответствующих свободных переменных.

Находим γ = max<γ_i> =max <0,2; 0,5; 0,6; 0,1>= 0,6. Переменную y₃ надо ввести в базис. После этого устанавливаем, существует ли оптимальный план. В направляющем столбце все коэффициенты положительны, следовательно, оптимальный план существует. В базисе есть переменные, которые можно уменьшать до нуля увеличивая значения y₃, тем самым минимизируя ЦФ. Раньше других в нуль обратиться переменная y₆ и ее исключаем из базиса.

После замены переменных в базисе переходим к новой симплексной таблице.

Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.

Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.

Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.

Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

Источник

Двойственная задача линейного программирования. Онлайн калькулятор

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

Предупреждение

Запись

1. Построение двойственной задачи к исходной задаче линейного программирования

Пусть задана прямая задача линейного программирования (ЛП) в общем виде:

Задаче (1) соответствует следующая двойственная задача ЛП:

Отметим, что если задача ЛП (2) является двойственной к задаче ЛП (1), то задача ЛП (1) является двойственной к задаче ЛП (2). Говорят, что задачи ЛП (1) и (2) взаимно двойственные задачи линейного программирования.

Рассмотрим подробно процесс построения двойственной задачи к исходной задачи линейного программирования. Для построения двойственной задачи:

2. Каждому ограничению исходной задачи ставится в соответствие переменная . Число переменных двойственной задачи равно числу ограничений исходной задачи, а число ограничений двойственной задачи равно числу переменных исходной задачи.

3. Если в исходной задаче целевая функция исследуется на максимум, то целевая функция двойственной задачи исследуется на минимум.

4. Свободные члены исходной задачи становятся коэффициентами целевой функции двойственной задачи.

5. Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной задачи.

6. Матрица коэффициентов двойственной задачи получается транспонированием матрицы коэффициентов исходной задачи.

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

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

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

2. Теория двойственности в задачах линейного программирования

Утверждение 1. Если X и Y − допустимые точки задач (1) и (2), соответственно, то

При этом, если для каких то допустимых точек и выполнено равенство , то и являются решениями задач (1) и (2) соответственно.

Доказательство. Запишем взвимно двойственные задачи (1) и (2) в матричном виде.

где ,,,,,,

матрица коэффициентов ограничений исходной задачи, которая разделена на четыре матрицы следующих порядков: ,,,.

Сделаны также следующие обозначения:

, ,

где , , .

(6)

(5b) и (5c) можно записать так:

,

(7)

Легко показать, что

(9)

Множители в правой части выражения (9) неотрицательны. Тогда их произведение не отрицательно, т.е. выполнено условие (8).

Учитывая (7) и (8) упростим выражение 6:

(10)

(11)

(4b) и (4c) можно записать так

(12)

Учитывая (12) и Y₁ упростим выражение (11):

т.е. выполнено условие (3).

Докажем вторую часть утверждения 1. Для любой допустимой точки x задачи (1) в том числе . Тогда

Поэтому наибольшее значение целевой функции задачи (1).

С другой стороны для любой допустимой точки y задачи (2)

т.е. − наименьшее из значений целевой функции задачи (2). Таким образом получили, что является решением задачи (1), а является решением задачи (2).

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

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

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

Представленные задачи взаимно двойственные, и в этих задачах допустимые области пусты.

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

или выполняется условие:

Докажем эквивалентность условий (15) и (16) с условием (17).

, .

(18)

.

(21)

,

(22)

Подставляя (19),(20) в (21),(22) соответственно и упрощая получим:

,

(23)

,

(24)

Выразив, например, через остальные слагаемые из (23) и подставляя в (24) получим:

А Запись (25) − это другой вид записи равенства (17).

3. Двойственные к разным формам задач линейного программирования

В статье Формы записи задачи линейного программирования мы рассмотрели различные формы записи задачи линейного программирования. В этом параграфе мы рассмотрим двойственные задачи к задачам ЛП в различных формах.

1) Двойственной к задаче ЛП в канонической форме

,

является задача ЛП в основной форме

2) Двойственной к задаче ЛП в основной форме

является задача ЛП в канонической форме

3) Двойственной к задаче ЛП в стандантной форме

является задача ЛП также в стандартной форме

Все эти три пары взаимно двойственных задач получаются из пары двойственных задач в общем виде (1) и (2) при различных значениях n₁ и m₁. Первая пара задач получается из (1) и (2) при m₁=0, n₁=n. Вторая пара задач получается из задач (1) и (2) при m₁=m, n₁=0. Третья пара задач получается из (1) и (2) при m₁=m, n₁=n.

Иногда более удобно рассматривать задачи ЛП в векторно-матричной форме. Высше представленные пары двойственных задач представим в векторно-матричной форме записи.

1) Двойственной к задаче ЛП в канонической форме

является задача ЛП в основной форме

2) Двойственной к задаче ЛП в основной форме

является задача ЛП в канонической форме

3) Двойственной к задаче ЛП в стандантной форме

является задача ЛП также в стандартной форме

где векторы строки порядка и соответственно, векторы-столбцы порядка и соответственно, − матрица порядка .

4.Условие дополняющей нежесткости

Равенства (15) и (16) называются условиями дополняющей нежесткости. Рассмотрим уравнение (16). Левая часть уравнения является скалярным произведением неотрицательных векторов и , а это означает, что если один из координат одного из этих векторов больше нуля, то соответствующая координата другого вектора равна нулю (поскольку их скалярное произведение равно нулю). Получается, что если в системе линейных неравенств (4b) некоторое неравенство в точке не удовлетворяется как равенство, то соответствующая координата вектора равна нулю и обратно − если некоторая координата вектора больше нуля, то соответствующее неравенство в системе (4b) в точке удовлетворяется как равенство.

Аналогичные рассуждения можно привести и для равенства (15). Условие дополняющей нежесткости позволяет найти оптимальный план двойственной задачи, если известен оптимальный план исходной задачи. Рассмотрим это на примере пар двойственных задач ЛП записанных в стандартной форме.

Пример 1. Дана следующая задача ЛП:

Решить данную задачу. Построить двойственную задачу и найти ее решение используя решение исходной задачи.

Запишем задачу ЛП в матричном виде:

, , , .

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

Решая систему линейных уравнений (27) получим координаты точки M, т.е. оптимальный план задачи ЛП (26):

или в векторном виде:

Целевая функция в этой точке равна:

Построим двойственную к (26) задачу ЛП:

В векторно матричном виде задача ЛП (30) будет выглядеть так:

Условие дополняющей нежесткости (15) и (16) в случае задач ЛП в стандартной форме примут вид:

Условие (32) позволяет найти оптимальный план двойственной задачи ЛП (30). Поскольку все координаты оптимального плана исходной задачи положительны, то из равенства (32) следует, что неравенства (30b) и (30c) в оптимальной точке должны выполняться как равенства, т.е. надо решить систему линейных уравнений

Решив данное уравнение находим оптимальный план

Найдем значение целевой функции в данной точке:

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

Графический метод решения задачи ЛП (30) смотрите на Рис.2:

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

Пример 2. Дана следующая задача ЛП:

Решить данную задачу. Построить двойственную задачу и найти ее решение используя решение исходной задачи и условия дополняющей нежесткости.

Запишем задачу ЛП в матричном виде:

, , , .

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

Из Рис.3 видно, что оптимальным является точка

Целевая функция в этой точке равна:

Построим двойственную задачу:

В оптимальной точке ограничение (33b) удовлетворяется как строгое неравенство следовательно исходя из условия дополняющей нежесткости (31), первая координата вектора должна быть равна нулю: . Из равенства (32) следует, что неравенство (34b) в оптимальной точке должно выполняться как равенство, поскольку соответствующая координата опттимального плана исходной задачи больше нуля. Таким образом имеем систему линейных уравнений:

Откуда получим .

В векторном виде оптимальный план двойственной задачи имеет вид:

Найдем значение целевой функции в данной точке:

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

Графический метод решения задачи ЛП (34) представлен на Рис.4. Прямая, ортогональная к вектору целевой функции B перемещаем перпендикулярно к вектору целевой функции до соприкосновения к допустимой области задачи ЛП (желтая область). Полученная точка M является решением задачи ЛП.

Источник