Двойственная задача как найти ограничения - Сайт, где вы сможете решить свои вопросы

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

Время на прочтение
9 мин

Количество просмотров 26K

Прочие статьи цикла

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

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

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

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

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

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

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

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

Если (x_Q, x_L) – оптимальное решение прямой задачи, а (y_Q, y_L) – решение двойственной задачи, то (x_Q, x_L, y_Q, y_L) – решение задачи Лагранжа. В частности, в этом случае удовлетворяются соотношения между переменными прямой и двойственной задач и условия дополняющей нежесткости.
Оптимальное решение прямой задачи программирования получается только при одном значении x_Q. Это справедливо и для переменной y_Q в двойственной задаче.

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

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

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

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

Чтобы прямая и двойственная задачи имели 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, стремясь при этом минимизировать общую стоимость сырья (чтобы быстрее продать сырье): Ф = Σ⁴_i=1 b_iy_i

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

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

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

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

Если первая задача сформулирована на поиск максимума, то вторая формулируется на поиск минимума линейной функции.
Коэффициенты ЦФ первой задачи являются свободными членами системы ограничений второй.
Свободные члены системы ограничений первой задачи являются коэффициентами линейной системы во второй задаче.
Матрица коэффициентов второй задачи является транспонированной к матрице коэффициентов ограничений первой задачи.
Знаки неравенств в ограничениях второй задачи противоположны знакам неравенств в ограничениях первой задачи.

Оптимальный план X^opt_<n>одной из задач тесно связан с оптимальным планом Y^opt_<n> другой. Если одна из задач имеет решение, то другая также разрешена, причем для оптимальных клонов X^opt_<n> =<x₁, x₂,…x_n> и Y^opt_<m> =<y₁, y₂,…y_m> справедливо равенство Q( X^opt ) =Q’( Y^opt ). Если линейная форма одной из задач неограниченна, то условия другой задачи несовместны. Если A^-1 обратная матрица к матрице В, состоящей из векторов базиса оптимального плана исходной задачи, то оптимальный план двойственной задачи равен Y^opt_<m> =СВ ^-1, здесь С – вектор базисных переменных. Решение двойственной задачи получается в последней симплексной таблице исходной задачи, в (m+1) строке, в столбцах, соответствующих дополнительным параметрам.

Для того чтобы векторы X^opt_<n> =<x₁, x₂,…x_n> и Y^opt_<m> =<y₁, y₂,…y_m> были решениями пары задач, необходимо и достаточно, чтобы их компоненты удовлетворяли следующим условиям:

Эти условия называют принципом дополняющей нежесткости. Если исходная (прямая) задача задана в канонической форме, то двойственная к ней называется несимметричной. Для несимметричной двойственной задачи соблюдается условие 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₃ и удовлетворяют ограничениям неравенствам

0,3x₁+ 0,2x₂+ 0, 4x₃≥ 0,2;

0,4x₁+ 0,3x₂+ 0,45x₃≥ 0,5;

0,2x₁+ 0,3x₂+ 0, 1 x₃≥ 0,6;

0,1x₁+ 0,2x₂+ 0,05x₃≥ 0,1;

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

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

0,3x₁+ 0,2x₂+ 0,4x₃– x₄= 0,2;

0,4x₁+ 0,3x₂+ 0,45x₃– x₅= 0,5;

0,2x₁+ 0,3x₂+ 0,1x₃– x₆= 0, 6;

0,1x₁+ 0,2x₂+ 0,05x₃– x₇= 0, 1;

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

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

Двойственная задача. Коэффициентами линейной формы в двойственной задаче выступают правые части b_i , i = 1(1)4 = m, исходной основной задачи. Переменные получают другие имена y₁, y₂, y₃, y₄, и формулируется двойственная задача иначе. Найти максимум линейной формы Q’:

Q’=0,2y₁+ 0,5y₂+ 0,6y₃+ 0,1y₄;

при ограничениях

0,3y₁+ 0, 4y₂+ 0,2y₃+ 0,1y₄≤ 3;

0,2y₁+ 0, 3y₂+ 0,3y₃+ 0,2y₄≤ 2;

0,4y₁+ 0,45y₂+ 0,1y₃+ 0,05y₄≤ 1;

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

Приведем задачу к каноническому виду, вводим дополнительные неотрицательные переменные y₅, y₆ , y₇:

Найти минимум ЦФ (знаки у коэффициентов ЦФ поменяли на противоположные): Q’= – 0,2y₁– 0,5y₂– 0, 6y₃– 0,1y₄;

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

0,3y₁+ 0, 4y₂+ 0,2y₃+ 0, 1y₄+ y₅= 3;

0,2y₁+ 0, 3y₂+ 0,3y₃+ 0, 2y₄+ y₆= 2;

0,4y₁+ 0,45y₂+ 0,1y₃+ 0,05y₄+ y₇= 1,

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

Задача решается симплекс методом. Исходный опорный план в качестве переменных может иметь y₅, y₆, y₇ и свободные переменные y₁= y₂= y₃= y₄= 0, т.е. Y_<7> = [0, 0, 0, 0, 3, 2, 1] .

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

y₅= 3 – (0,3y₁+ 0,4y₂+ 0,2y₃+ 0,1y₄);

y₆= 2 – (0,2y₁+ 0,3y₂+ 0,3y₃+ 0,2y₄);

y₇= 1 – (0,4y₁+ 0,45y₂+ 0,1y₃+ 0,05y₆);

Q’₁=γ₀ – Σ⁴_i=1 γ_iy_i= 0 -(0,2y₁+ 0,5y₂+ 0, 6y₃+ 0,1y₄);

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

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

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

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

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

Анализ этой таблицы показывает, что все коэффициенты в выражении ЦФ свободных переменных отрицательны. Следовательно, опорный план Y_<7>= [0, 0, 20/3, 0, 5/3, 0, 1/3] является оптимальным. ЦФ при этом Q’₁= – 4 достигла наименьшего значения. Возвращаемся к двойственной задаче. Используя соответствие между оптимальными планами двойственных задач ЛП, определяем: базисными переменными в оптимальном плане будут x₂ x₄ x₅ x₇; их значения с противоположным знаком записаны в последней строке таблицы. Таким образом, X^opt_<n> =<0; 2; 0; 0; 2; 0; 1; 0; 1/30>, т.е. оптимальный рацион из двух единиц продукта П₂. Стоимость такого рациона минимальна и составляет 4 единицы. Это значение с противоположным знаком записано в той же таблице.

Литература

Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
Квейд Э. Методы системного анализа // Новое в теории и практике управления производством в США.–М.: Прогресс, 1971.– с.78-99. .
Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.
Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.
Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.
Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

Источник

Двойственная задача^[1] для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом:

Каждая переменная в прямой задаче становится ограничением двойственной задачи;
Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.

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

Теорема о сильной двойственности утверждает, что более того, если прямая задача имеет оптимальное решение, то двойственная задача имеет также оптимальное решение, и эти два оптимума равны^[2].

Эти теоремы принадлежат более широкому классу теорем двойственности в оптимизации. Теорема о сильной двойственности является одним из случаев, в котором разрыв двойственности (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0.

О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна^[3]. Там же можно прочитать об экономическом смысле задачи^[4].

Построение двойственной задачи[править | править код]

Если дана прямая задача линейного программирования, для построения двойственной задачи может быть использован следующий алгоритм^[5].

Пусть прямая задача определена как:

Двойственная задача строится следующим образом.

Каждое ограничение прямой задачи становится двойственной переменной. Таким образом, получаем m переменных: ${displaystyle y_{1},ldots ,y_{m}}$ .
Знак ограничения каждой двойственной переменной «противоположен» знаку ограничения в прямой задаче. Таким образом, « ${displaystyle geqslant b_{j}}$ » становится ${displaystyle y_{j}leqslant 0}$ , « ${displaystyle leqslant b_{j}}$ » превращается в ${displaystyle y_{j}geqslant 0}$ , а « ${displaystyle =b_{j}}$ » превращается в ${displaystyle y_{j}in mathbb {R} }$ .
Целевая функция двойственной задачи равна (минимизировать) ${displaystyle b_{1}y_{1}+cdots +b_{m}y_{m}}$
Каждая переменная прямой задачи становится двойственным ограничением. Таким образом, получаем n ограничений. Коэффициент двойственной переменной в двойственных ограничениях равен коэффициенту переменной из ограничения прямой задачи. Таким образом, каждое ограничение i есть: ${displaystyle a_{1i}y_{1}+cdots +a_{mi}y_{m}lesseqqgtr c_{i}}$ , где символ перед $c_{i}$ аналогичен ограничению на переменную i в прямой задаче. Так, ${displaystyle x_{i}leqslant 0}$ превращается в « ${displaystyle leqslant c_{i}}$ », ${displaystyle x_{i}geqslant 0}$ превращается в « ${displaystyle geqslant c_{i}}$ », а ${displaystyle x_{i}in mathbb {R} }$ превращается в « ${displaystyle =c_{i}}$ ».

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

Векторные формулировки[править | править код]

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

Прямая	Двойственная	Примечания
Максимизировать ${displaystyle mathbf {c} ^{T}mathbf {x} }$ при ограничениях	Минимизировать ${displaystyle mathbf {b} ^{T}mathbf {y} }$ при ограничениях ${displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0}$	Такая задача называется «симметричной» двойственной задачей
Максимизировать ${displaystyle mathbf {c} ^{T}mathbf {x} }$ при ограничениях	Минимизировать ${displaystyle mathbf {b} ^{T}mathbf {y} }$ при ограничениях ${displaystyle mathbf {A} ^{T}mathbf {y} =mathbf {c} ,mathbf {y} geqslant 0}$	Такая задача называется «асимметричной» двойственной задачей
Максимизировать ${displaystyle mathbf {c} ^{T}mathbf {x} }$ при ограничениях	Минимизировать ${displaystyle mathbf {b} ^{T}mathbf {y} }$ при ограничениях ${displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} }$

Теоремы двойственности[править | править код]

Ниже мы предполагаем, что прямая задача поставлена как «Максимизировать ${displaystyle mathbf {c} ^{T}mathbf {x} }$ при ограничениях [ограничения]», а двойственная задача поставлена как «Минимизировать ${displaystyle mathbf {b} ^{T}mathbf {y} }$ при ограничениях [ограничения]».

Слабая двойственность[править | править код]

Теорема о слабой двойственности утверждает, что для каждого допустимого решения x прямой задачи и каждого допустимого решения y двойственной задачи: ${displaystyle mathbf {c} ^{T}mathbf {x} leqslant mathbf {b} ^{T}mathbf {y} }$ . Другими словами, значение целевой функции для каждого допустимого решения двойственной задачи является верхней границей целевой функции прямой задачи, а значение целевой функции любого допустимого решения прямой задачи является нижней границей для целевой функции двойственной задачи. Из этого следует, что

${displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} leqslant min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }$

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

Теорему о слабой двойственности относительно легко доказать^[6]. Предположим, что прямая задача линейного программирования звучит как «Максимизировать ${displaystyle mathbf {c} ^{T}mathbf {x} }$ при ограничениях ». Предположим, что мы создаём линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты при x не меньше ${displaystyle mathbf {c} ^{T}}$ . Эта линейная комбинация даёт нам верхнюю грань для целевой функции. Переменные y двойственной задачи являются коэффициентами этой линейной комбинации. Двойственная задача пытается найти такие коэффициенты, которые минимизируют результирующую правую часть. Это даёт задачу линейного программирования «Минимизировать ${displaystyle mathbf {b} ^{T}mathbf {y} }$ при ограничениях ${displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0}$ »^[7]. См. «Простой пример» ниже.

Сильная двойственность[править | править код]

Теорема о сильной двойственности утверждает, что границы, определяемые теоремой о слабой двойственности жёсткие, то есть

${displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} =min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }$

Теорему о сильной двойственности существенно труднее доказать. Обычно доказательство использует теорему о слабой двойственности в качестве леммы^[8].

Одно доказательство использует симплекс-метод и опирается на доказательство того, что, при подходящем правиле выбора выводимого столбца, он даёт правильное решение. Доказательство устанавливает, что, когда симплекс-метод завершается решением прямой задачи линейного программирования, можно из конечной таблицы прочесть решение двойственной задачи. Таким образом, после прогона симплекс-алгоритма мы получим решения как прямой, так и двойственной задачи одновременно^[9].

Другое доказательство использует лемму Фаркаша^[10]

Теоретическое приложение[править | править код]

Слабая двойственность имеет интересное теоретическое приложение — она показывает, что нахождение отдельного допустимого решения настолько же трудно, насколько нахождение оптимального допустимого решения. Предположим, что мы имеем систему предсказывания, что данная задача линейного программирования находит произвольное допустимое решение (если оно существует). Если задача звучит как «Максимизировать ${displaystyle mathbf {c} ^{mathbf {x} }}$ при ограничениях », мы можем построить другую задачу путём комбинирования её с двойственной ей задачей. Комбинированная задача имеет как x, так и y в качестве переменных:

Максимизировать 1

при ограничениях ${displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {c} ^{T}mathbf {x} geqslant mathbf {b} ^{T}mathbf {y} ,mathbf {x} geqslant 0,mathbf {y} geqslant 0}$

Если комбинированная задача имеет допустимое решение (x,y), то по слабой двойственности ${displaystyle mathbf {c} ^{T}mathbf {x} =mathbf {b} ^{T}mathbf {y} }$ . Таким образом, x должно быть максимальным решением прямой задачи, а y должно быть минимальным решением двойственной задачи. Если комбинированная задача не имеет допустимого решения, то и прямая задача допустимого решения не имеет.

Примеры[править | править код]

Простой пример[править | править код]

Рассмотрим прямую задачу с двумя переменными и одним ограничением:

Максимизировать ${displaystyle 3x_{1}+4x_{2}}$

При условиях

${displaystyle {begin{aligned}&5x_{1}+6x_{2}=7\&x_{1}geqslant 0,x_{2}geqslant 0end{aligned}}}$

Применив вышеизложенный рецепт построения двойственной задачи, получим задачу с одной переменной и двумя ограничениями:

Минимизировать ${displaystyle 7y_{1}}$

При условиях

${displaystyle {begin{aligned}&&5y_{1}geqslant 3\&&6y_{1}geqslant 4\&&y_{1}in mathbb {R} end{aligned}}}$

Легко видеть, что максимум прямой задачи достигается, когда переменная x₁ минимизируется до её нижней границы (0), а переменная x₂ максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен .

Аналогично, минимум двойственной задачи достигается, когда y₁ минимизируется до его нижнего значения при ограничениях: первое ограничение даёт значение 3/5, в то время как второе даёт более строгую границу 4/6, так что фактический минимум равен 4/6 и минимум целевой функции равен .

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

Мы используем этот пример для иллюстрации доказательства теоремы о слабой двойственности. Предположим, что в прямой задаче линейного программирования мы хотим получить верхнюю границу целевой функции ${displaystyle 3x_{1}+4x_{2}}$ . Мы можем использовать ограничение, умноженное на некоторый коэффициент, скажем, y_1 . Для любого y_1 мы имеем: ${displaystyle y_{1}cdot (5x_{1}+6x_{2})=7y_{1}}$ . Теперь, если ${displaystyle y_{1}cdot 5x_{1}geqslant 3x_{1}}$ и ${displaystyle y_{1}cdot 6x_{2}geqslant 4x_{2}}$ , то ${displaystyle y_{1}cdot (5x_{1}+6x_{2})geqslant 3x_{1}+4x_{2}}$ , так что ${displaystyle 7y_{1}geqslant 3x_{1}+4x_{2}}$ . Следовательно, целевая функция двойственной задачи является верхней границей целевой функции прямой задачи.

Пример фермера[править | править код]

Рассмотрим фермера, который может выращивать пшеницу и ячмень на площади L, используя удобрения F и пестициды P.
Чтобы вырастить одну единицу пшеницы на единице площади, нужно использовать $F_{1}$ единиц удобрений и P_1 единиц пестицидов.

Прямой задачей будет решение фермера, сколько пшеницы ( $x_{1}$ ) и ячменя ( $x_{2}$ ) выращивать, если их продажные цены равны $S_{1}$ и $S_{2}$ за единицу.

Максимизировать:

${displaystyle S_{1}cdot x_{1}+S_{2}cdot x_{2}}$

(максимизировать доход от выращивания пшеницы и ячменя)

при ограничениях:

${displaystyle x_{1}+x_{2}leqslant L}$

(фермер не может использовать больше земли, чем у него есть)

${displaystyle F_{1}cdot x_{1}+F_{2}cdot x_{2}leqslant F}$

(фермер не может использовать больше удобрений, чем есть в наличии)

${displaystyle P_{1}cdot x_{1}+P_{2}cdot x_{2}leqslant P}$

(фермер не может использовать больше пестицидов, чем у него есть)

${displaystyle x_{1},x_{2}geqslant 0}$

(нельзя вырастить отрицательную величину зерна).

Для двойственной задачи предположим, что y единиц цены для каждой из этих видов продукта (входы) представлены группой планирования. Задачей группы планирования является минимизация полной стоимости производство продукции при заданных величинах потребления ресурсов с определением стоимости единицы ресурса (выход). Это соответствует следующей задаче линейного программирования:

Минимизировать

${displaystyle Lcdot y_{L}+Fcdot y_{F}+Pcdot y_{P}}$

(минимизировать полную стоимость производства продукции как «целевая функция»)

при ограничениях:

${displaystyle y_{L}+F_{1}cdot y_{F}+P_{1}cdot y_{P}geqslant S_{1}}$

(фермер должен получить не менее S₁ за единицу пшеницы)

${displaystyle y_{L}+F_{2}cdot y_{F}+P_{2}cdot y_{P}geqslant S_{2}}$

(фермер должен получить не менее S₂ за единицу ячменя)

${displaystyle y_{L},y_{F},y_{P}geqslant 0}$

(цены не могут быть отрицательными).

В матричной форме:

Минимизировать: ${displaystyle {begin{bmatrix}L&F&Pend{bmatrix}}{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}}$

при условиях: ${displaystyle {begin{bmatrix}1&F_{1}&P_{1}\1&F_{2}&P_{2}end{bmatrix}}{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}geqslant {begin{bmatrix}S_{1}\S_{2}end{bmatrix}},,{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}geqslant 0.}$

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

Каждой переменной в пространстве прямой задачи соответствует неравенство в пространстве двойственной задачи. Каждому неравенству в пространстве прямой задачи соответствует переменная в пространстве двойственной задачи.

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

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

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

Недопустимая задача[править | править код]

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

Если прямая задача является неограниченной, то двойственная задача недопустима;
Если двойственная задача является неограниченной, то прямая задача недопустима^[11].

Однако может быть, что обе задачи, как двойственная, так и прямая, недопустимы. Вот пример:

Приложения[править | править код]

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

Другие теоремы, связанные с графами, могут быть доказаны с помощью теоремы о сильной двойственности, в частности, теорема Кёнига^[12].

Теорема о минимаксе^[en] для игр с нулевой суммой может быть доказана с помощью теоремы о сильной двойственности^[13].

Альтернативный алгоритм[править | править код]

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

Минимизировать ${displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}}$

при условиях

${displaystyle sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}geqslant g_{j},1leqslant jleqslant n}$

${displaystyle f_{i}x_{i}+sum _{j=1}^{n}b_{ij}t_{j}geqslant h_{i},1leqslant ileqslant m}$

${displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n}$

Мы имеем условий и все переменные неотрицательны. Нам нужно определить двойственных переменных: y_j и s_i. Мы получаем:

Минимизировать ${displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}}$

при условиях

${displaystyle sum _{i=1}^{m}a_{ij}x_{i}cdot y_{j}+e_{j}t_{j}cdot y_{j}geqslant g_{j}cdot y_{j},1leqslant jleqslant n}$

${displaystyle f_{i}x_{i}cdot s_{i}+sum _{j=1}^{n}b_{ij}t_{j}cdot s_{i}geqslant h_{i}cdot s_{i},1leqslant ileqslant m}$

${displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n}$

${displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}$

Поскольку это задача минимизации, нам хотелось бы получить двойственную задачу, которая является нижней границей прямой задачи. Другими словами, нам хотелось бы, чтобы сумма всех правых частей ограничений была максимальной при условиях, что для каждой переменной прямой задачи сумма её коэффициентов не превосходит коэффициента в линейной функции. Например, x₁ появляется в n+1 ограничениях. Если мы суммируем коэффициенты ограничения, мы получим ${displaystyle a_{1,1}mathbf {y} _{1}+a_{1,2}mathbf {y} _{2}+dots +a_{1,n}mathbf {y} _{n}+f_{1}mathbf {s} _{1}}$ . Эта сумма должна не превосходить c₁. Как результат мы получаем:

Максимизировать ${displaystyle sum _{j=1}^{n}g_{j}y_{j}+sum _{i=1}^{m}h_{i}s_{i}}$

при ограничениях

${displaystyle sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}leqslant c_{i},1leqslant ileqslant m}$

${displaystyle e_{j}y_{j}+sum _{i=1}^{m}b_{ij}s_{i}leqslant d_{j},1leqslant jleqslant n}$

${displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}$

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

Интерпретации в реальной жизни[править | править код]

Теорема двойственности имеет экономическую интерпретацию. Если мы интерпретируем прямую задачу линейного программирования как классическую задачу «распределения ресурсов», её двойственную задачу можно интерпретировать как задачу «оценки ресурсов»^[14]. См. статью Теневая цена^ru_en. Об экономической интерпретации двойственной задачи можно почитать также в книге Лунгу^[15].

Теорема двойственности имеет и физическую интерпретацию^[16].

Примечания[править | править код]

↑ Иногда используется термин Сопряжённая задача, как, например, в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 149) или в книге Лунгу (Лунгу 2005, 67). Во второй книге прямая задача именуется также основной задачей.
↑ Gartner, Matousek, 2006, с. 81–104.
↑ Юдин, Гольштейн, 1969, с. 150-152 Пункт 5.2.
↑ Юдин, Гольштейн, 1969, с. 157-159 Пункт 5.5.
↑ Gartner, Matousek, 2006, с. 85.
↑ Доказательство очень близкого утверждения, из которого вытекает данная теорема можно найти в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 159, Лемма 5.1)
↑ Gartner, Matousek, 2006, с. 81–83.
↑ Доказательство можно найти в книге Юдина и Гольштейна, где она именуется «первой теоремой двойственности» (Юдин, Гольштейн 1969, 164, Теорема 6.1)
↑ Gartner, Matousek, 2006, с. 87–89.
↑ Gartner, Matousek, 2006, с. 81–94.
↑ Юдин, Гольштейн, 1969, с. 162, Лемма 5.3.
↑ A. A. Ahmadi Lecture 6: linear programming and matching. Princeton University (2016). Архивировано 21 сентября 2018 года.
↑ Gartner, Matousek, 2006, с. sub.8.1.
↑ В книге Юдина и Гольштейна для теневых цен используется термин предварительные оценки (факторов производства).
↑ Лунгу, 2005, с. 68 Пункт 5.4.
↑ Gartner, Matousek, 2006, с. 86–87.

Литература[править | править код]

Jiri Matousek, Bernd Gärtner. Understanding and Using Linear Programming. — Springer, 2006. — С. 81–104. — (Universitext).
Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). — Москва: «Наука», 1969.
Лунгу К.Н. Линейное программирование. Руководство к решению задач. — М.: ФИЗМАТЛИТ, 2005. — ISBN 5-9221-0631-7.

Источник

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

Краткая теория

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

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

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

Рассмотренная пара взаимно
двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько и
какой продукции

надо
произвести, чтобы при заданных объемах имеющихся ресурсов

и
нормах расходов

максимизировать
выпуск продукции в стоимостном выражении?

Двойственная задача: какова
должна быть оценка единицы каждого из ресурсов

, чтобы при заданных

минимизировать
общую оценку затрат на ресурсы?

Для построения двойственной
задачи необходимо пользоваться следующими правилами:

Основное неравенство теории двойственности

Для любых допустимых планов

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

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

и
любого допустимого вектора оценок ресурсов

общая
созданная стоимость не превосходит суммарной оценки ресурсов.

Критерий оптимальности Канторовича (достаточный признак оптимальности)

Если для некоторых
допустимых планов

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

, то

являются оптимальными планами
соответствующих задач. Экономический смысл критерия следующий: план
производства

и
вектор оценок ресурсов

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

Теорема существования оптимальных планов пары двойственных задач

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

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

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

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

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

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

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

и так далее.

Если прямая задача решается
на минимум, то:

и так далее.

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

Для того, чтобы планы

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

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

Экономически это означает,
что если по некоторому оптимальному плану

производства расход i-го ресурса строго меньше его запаса

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

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

Двойственные оценки
показывают приращение функции цели, вызванное малым изменением свободного члена
соответствующего ограничения ЗЛП, то есть:

Выясним экономическое
содержание третьей теоремы двойственности. Для этого в последнем выражении
дифференциалы заменим приращениями. Получим:

При

имеем

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

часто
называют скрытыми, теневыми или маргинальными оценками ресурсов.

Примеры решения задач

Задача 1

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

Решение

Воспользуемся правилами для
построения двойственной задачи.Заполним вспомогательную таблицу.

ДЗ/ПЗ				min	СП/ЦФ
	-18	7	-12		-2
	-12	16	-12		3
	-11	3	-7	=	-2
	0	13	-12		-1
max		=
ЦФ/СП	-18	1	-3

Двойственная задача будет
иметь следующий вид:

–любого
знака,

Задача 2

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

Решение

Приведем задачу к каноническому виду.

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

Двойственная задача будет иметь следующий вид:

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

Заполняем симплексную таблицу 0-й итерации.

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

ВКонтакте
WhatsApp
Telegram

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту СберБанка. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Переходим к таблице 1-й итерации:

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

Соответствие между переменными исходной и двойственной задачи:

На основании симплексной таблицы получено следующее решение
двойственной задачи линейного программирования:

Задача 3

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

Решение прямой задачи:

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

Решение

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

Найдем оптимальное решение
двойственной задачи:

Условия
дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов
двойственных задач имеют место соотношения:

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

Для
нахождения значений

, получаем:

Ответ

Решение двойственной задачи:

Источник

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

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

Содержание
1. Построение двойственной задачи к исходной задаче линейного программирования
2. Теория двойственности в задачах линейного программирования
3. Двойственные к разным формам задач линейного программирования
4. Условие дополняющей нежесткости

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

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

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

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

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

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

1. Упорядочивается запись исходной задачи ЛП: если целевая функция исследуется на максимум, то ограничения (1b), (1c) должны иметь знак или “=”, или “≤”, а если целевая функция исследуется на минимум, то ограничения (1b), (1c) должны иметь знак или “=” , или “≥”. Если в исходной задаче ЛП есть ограничения, не удовлетворяющие этим условиям, то это можно исправить, умножая данное ограничение на −1.

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

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

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

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

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

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

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

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

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

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

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

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

Исходная задача:

где ,,,,,,

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

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

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

где , , .

Имеем:

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

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

Действительно:

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

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

С другой стороны:

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

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

Из (9) и (13) получим:

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

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

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

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

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

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

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

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

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

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

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

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

Из (4с) и (5с) имеем:

Откуда:

Из (15) и (16) имеем:

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

Выразив, например, через остальные слагаемые из (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. Дана следующая задача ЛП:

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

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

где

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

Как видно из рисунка, область определения – это желтая область . Вектор целевой функции c={1;2}. Для нахождения оптимального плана нужно прямую, перпендикулярную вектору С перемешать по направлению вектора С , до предельного положения соприкосающаяся с областью определения (точка M). Таким образом точка M является оптимальным решением задачи линейного программирования. Как видно из рисунка, точка M находится на пересечении следующих прямых:

Решая систему линейных уравнений (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 является решением задачи ЛП.

Источник

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

1.Цель работы

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

2. Теоретические сведения

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

2.1

ПОСТРОЕНИЕ
ДВОЙСТВЕННОЙ ЗАДАЧИ

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

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

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

максимизировать

при
ограничениях:

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

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

На
примере задачи планирования товарооборота
двойственная задача
формулируется следующим образом:

определить
оценку (неявную стоимость) единицы
каждого вида ресурсов y_j
(i=1,m),
чтобы при заданных объемах ресурсов
b_i,
прибыли
c_j,
нормах
расхода ресурсов a_ij
минимизировать
оценку всех ресурсов торгового
предприятия, затраченных на организацию
торгового
процесса.

Запишем математическую
модель двойственной задачи:

Определить
вектор Y=
(у_ь
у₂,
…, у_т),
который
удовлетворяет ограничениям

обеспечивает
минимальное значение целевой функции

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

В
целом двойственная задача по отношению
к исходной составляется
согласно следующим правилам:

Число
переменных в двойственной задаче равно
числу ограничений
в прямой
задаче.
Матрица
коэффициентов системы ограничений
двойственной задачи
получается из матрицы коэффициентов
системы ограничений
прямой задачи путем транспонирования.
Система
ограничений двойственной задачи
записывается в виде неравенств
противоположного смысла неравенствам
системы ограничений
прямой задачи.
Свободными
членами системы ограничений двойственной
задачи
являются коэффициенты функции цели
прямой задачи.
Двойственная
задача решается на минимум, если целевая
функция
прямой задачи задается на максимум, и
наоборот.
Коэффициентами
функции цели двойственной задачи служат
свободные
члены системы ограничений прямой
задачи.
Если
переменная прямой задачи х_j
>=0, то j-е
условие системы ограничений
двойственной задачи является неравенством,
если x_j
— любое
число, то j-е
условие двойственной задачи представляет
собой уравнение.
Если
i-е
соотношение прямой задачи является
неравенством, то соответствующая
оценка i-го
ресурса — переменная y_i
>=0,
если i-е
соотношение представляет собой
уравнение, то переменная двойственной
задачи у_i
— любое число.

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

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

Установим
соответствие между переменными прямой
и двойственной
задач в симплексной таблице 1.

Таблица 1 –
Соотношения переменных

Переменные прямой
задачи (заголовок симплексной таблицы)

Переменные
двойственной задачи (их значения
расположены в индексной строке
оптимальной симплексной таблицы)

основные

x₁,
x₂,
…, x_n

дополнительные

y_m₊₁,
y_m₊₂,
…, y_m₊_n

дополнительные

x_n₊₁,
x_n₊₂,
…, x_n₊_m

основные

y₁,
y₂,
… , y_m

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

2.2
ПРИМЕР РЕШЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Условие
задачи. Коммерческое
предприятие, располагающее
материально-денежными ресурсами,
реализует три группы товаров А, В и С.
Плановые нормативы затрат ресурсов на
1 тыс. руб. товарооборота, доход от
продажи товаров на 1 тыс. руб. товарооборота,
а также объем ресурсов заданы в таблице
2.

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

Таблица 2– Плановые
нормативы

Виды материально-денежных ресурсов	Норма затрат материально-денежных ресурсов на 1 тыс руб товарооборота	Объем ресурсов b_i
Группа А	Группа В	Группа С
Рабочее время продавцов, чел-ч	0,1	0,2	0,4	1100
Площадь торговых залов, м²	0,05	0,02	0,02	120
Площадь складских помещений, м²	3	1	2	8000
Доход, тыс руб	3	5	4	Max

Решение.
Запишем
математическую модель задачи.

Определим
вектор X=
(x₁,
х₂,
х₃),
который удовлетворяет условиям

0,1х₁
+ 0,2х₂
+ 0,4*х₃<=1100

0,05х₁
+ 0,02х₂
+ 0,02х₃
<= 120

Зх₁
+х₂
+ 2х₃
<=
8000

х₁
> =0, х₂
> =0,
х₃
>=0

и обеспечивает
максимальное значение целевой функции

F(X)
=
3х₁
+ 5х₂
+ 4х₃
-> max.

Для
построения первого опорного плана
систему неравенств приведем к системе
уравнений путем введения дополнительных
переменных х₄,
х₅,
х₆:

0,1х₁
+ 0,2х₂
+ 0,4х₃
+ х₄
⁼
1100

0,05х₁
+ 0,02х₂
+ 0,02х₃+х₅=120

Зх₁
+ х₂
+ 2х₃
+ х₆
= 8000.

Решим систему
уравнений относительно базисных
переменных.

х₄
= 1100 – (0,1х₁
+ 0,2х₂
+ 0,4х₃),

х₅
= 120 – (0,05х₁
+ 0,02х₂
+ 0,02х₃),

х₆
= 8000 – (Зх₁
+ х₂
+3х₃).

Функцию цели
запишем в виде уравнения:

F(Х)
= 0 – (-Зх₁
– 5х₂
– 4х₃).

Полагая,
что свободные переменные х₁
= 0, х₂
= 0, х₃
= 0, получим первый опорный план X₁=
(0, 0, 0, 1100, 120, 8000), F(X₁)
=
0, в котором базисные переменные х₄
= 1100,х₅
= 120, х₆
=8000. Следовательно, товары не продаются,
доход равен нулю, а ресурсы не используются.
Полученный первый опорный план запишем
в симплексную таблицу 3.

Таблица
3 – Симплексная таблица

План	Базисные переменные	Значения базисных переменных	Значения коэффициентов при переменных	δ_i
Х₁	Х₂	Х₃	Х₄	Х₅	Х₆
I	Х₄ Х₅ Х₆	1100 120 8000	0,1 0,05 3	0,2 0,02 1	0,4 0,02 2	1 0 0	0 1 0	0 0 1	5500 6000 8000
Индексная строка	F(X₁)	0	-3	-5	-4	0	0	0
II	X₂ X₅ X₆	5500 10 2500	0,5 0,04 2,5	1 0 0	2 -0,02 0	5 -0,1 -5	0 1 0	0 0 1	11000 250 1000
Индексная строка	F(X₂)	27500	-0,5	0	6	25	0	0
III	Х₂ Х₁ Х₆	5375 250 1875	0 1 0	1 0 0	2,25 -0,5 1,25	6,25 -2,5 1,25	12,5 25 -62,5	0 0 1
Индексная строка	F(X₃)	27625	0	0	5,75	23,75	12,5	0

На
третьей итерации таблицы 2 получаем
план III,
который является оптимальным, так
как все коэффициенты в индексной строке
>=0.

Оптимальный план
можно записать так:

X
= (250,
5375, 0, 0, 0, 1875), F(Х)
=
27 625 тыс. руб.

Следовательно,
необходимо продавать товаров первой
группы А – 250 ед., а второй группы В —
5375 ед. При этом торговое предприятие
получает максимальный доход в размере
27 625 тыс. руб. Товары группы С не
реализуются.

В
оптимальном плане среди базисных
переменных находится дополнительная
переменная х₆.
Это указывает на то, что ресурсы третьего
вида (площадь складских помещений)
недоиспользована на 1875 м²,
так как переменная х₆
была введена в третье ограничение
задачи, характеризующее собой использование
складских помещений этого ресурса.

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

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

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

Х=(х₁,
х₂,
х₃)

при
0,1х₁+0,2х₂+0,4х₃<=1100

0,05х₁+0,02х₂+0,02х₃<=120

3х₁+х₂+2х₃<=8000

х₁,
х₂,
х₃>=0

F(X)=3x₁+5x₂+4x₃–>
max

Y=(y₁,
y₂,
y₃)

при
0,1у₁+0,05у₂+3у₃>=3

0,2у₁+0,02у₂+у₃>=5

0,4у₁+0,02у₂+2у₃>=4

у₁,
у₂,
у₃
>=0

Z(Y)=1100y₁+120y₂+8000y₃
–> min

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

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

X
= (250;
5375; 0; 0; 0; 1875); F(X)
= 27 625
тыс. руб.

Используя
последнюю итерацию прямой задачи (план
III
симплексной
таблицы 2), найдем оптимальный план
двойственной задачи.

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

Y= (23,75; 12,5; 0; 0; 0;
5,75); Z(Y) = 27 625.

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

0,1
* 250 + 0,2 * 5375 + 0,4 * 0 = 1100;

0.05 * 250 + 0,02 * 5375 +
0,02 * 0 = 120;

3 * 250 + 1 * 5375 + 2 * 0 <
8000.

Первое
и второе ограничение прямой задачи
выполняются как равенства.
Это означает, что ресурсы первого и
второго видов полностью используются
в оптимальном плане, являются дефицитными
и их оценки отличны от
нуля (у₁
>
0, у₂
> 0).
Третье ограничение выполняется как
строгое
неравенство, т. е. ресурс третьего вида
израсходован не полностью, остаток
его в оптимальном плане х₆*
= 1875. Значит, ресурс третьего вида не
является дефицитным и цены в оптимальном
плане
не имеет у₃=
0.

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

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

0,1
* 23,75 + 0,05 * 12,5 +3*0
= 3;

0,2
* 23,75 + 0,02 * 12,5 +1*0
= 5;

0,4 * 23,75 + 0,02 * 12,5 + 2
* 0 > 4.

Первое
и второе ограничения двойственной
задачи выполняются
как равенства. Это означает, что
двойственные оценки ресурсов,
используемых для реализации единицы
товаров первой и второй
групп, равны в точности доходам. Поэтому
продавать эти виды товаров
экономически целесообразно, а их
реализация предусмотрена
оптимальным планом прямой задачи (x₁>
0, х₂>
0).
Третье ограничение
двойственной задачи выполняется как
строгое неравенство.
Это означает, что двойственная оценка,
используемая при реализации единицы
товара третьей
группы, выше дохода от его продажи.
Следовательно, продавать товары третьей
группы невыгодно,
и в оптимальном плане прямой задачи х₃=
0.

Величина
двойственной оценки показывает, насколько
возрастает значение
целевой функции при увеличении дефицитного
ресурса на
единицу. Например, увеличение рабочего
времени на 1 чел.-ч приведет
к получению нового оптимального плана,
в котором прибыль
возрастает на 23,75 и станет равной

F(X)
= 27 625
+ у₁
=
27 625 + 23,75 = 27648,75 тыс. руб.

При
этом коэффициенты оптимальной симплексной
таблицы 2 столбца
х₄
показывают,
что указанное
увеличение прибыли достигается за счет
увеличения реализации
второй группы товара на величину 6,25
единиц, уменьшения
объема продажи первой группы товара на
величину 2,5 единиц
и уменьшения остатка ресурса третьего
вида на 62,5 м².

В
то же время ввод в продажу невыгодной
группы товаров уменьшает
размер дохода. Если х₃
= 1, то F(X)
=
27 625 – 5,75 = 27619,25 тыс. руб.

При
этом коэффициенты структурных сдвигов
оптимальной симплексной
таблицы 2 столбца х₃
показывают,
что указанное уменьшение
дохода происходит за счет уменьшения
объема продажи выгодного
товара второй группы на величину 2,25
единиц, увеличения продажи первой
группы товара на 0,5 единиц и уменьшения
остатка
ресурсов третьего вида на 1,25 м².

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

Соседние файлы в папке ММО

Источник

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

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

Построение двойственной задачи[править | править код]

Векторные формулировки[править | править код]

Теоремы двойственности[править | править код]

Слабая двойственность[править | править код]

Сильная двойственность[править | править код]

Теоретическое приложение[править | править код]

Примеры[править | править код]

Простой пример[править | править код]

Пример фермера[править | править код]

Недопустимая задача[править | править код]

Приложения[править | править код]

Альтернативный алгоритм[править | править код]

Интерпретации в реальной жизни[править | править код]

Примечания[править | править код]

Литература[править | править код]

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

Основное неравенство теории двойственности

Критерий оптимальности Канторовича (достаточный признак оптимальности)

Теорема существования оптимальных планов пары двойственных задач

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

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

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

Задача 1

Задача 2

Задача 3

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

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

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

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

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

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

1.Цель работы

2. Теоретические сведения

Вам также может понравиться

Как найти бух отчетность предприятия

Как найти работника вконтакте

Как найди длинну катета

Добавить комментарий Отменить ответ