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

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

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

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

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

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

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

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

Для наглядности, выпишем равенства (3) и (4) в развернутом виде:
(3.1)
(3.2)

(3.m)

Метод решения двойственной задачи

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

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

Если известно решение задачи (2), то аналогичным образом можно найти решение задачи (1).

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

Пример 1

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

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

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

Ее решение
;

Пример 2

Дана задача линейного программирования:
(П2.1.1) ;
(П2.1.2)
Найти решение этой задачи, решив двойственную задачу графическим методом.

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

Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи (П2.2).
;
;
.
Поскольку третья строка является строгим неравенством (не являются равенством), то
.

Источник

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

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

Рассмотрим задачу о планируемом выпуске продукции.

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

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

Итак, имеем исходную задачу I и ее оптимальное решение х * = (0, 40, 0, 100) и F(х*) = 700.

Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи II у* = (у₁, у₂, у₃), не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х *.

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

В силу соответствия и II теоремы двойственности переменные у₁, у₅, у₇ обязаны равняться 0, т.к. х₅, х₂, х₄>0 строго. А переменные у ₄, у ₂, у ₆, у ₃ принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х₁, х₆, х₃, х₇ = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

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

Теорема равновесия

Пример 3
Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия
x₁+3x₂≥12
5x₁+4x₂≥31
2x₁+3x₂≥18
x₁, x₂≥0
Z(x₁,x₂)=12000x₁+16000x₂→min
В разделе 1.5 было найдено решение исходной задачи средствами MS Excel: Zmin(3;4)=100000
Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.

Z(x₁,x₂)=12000x₁+16000x₂→min
Двойственная задача:

W(y₁, y₂, y₃)=12y₁+31y₂+18y₃ → max
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.
y₁(x₁+3x₂-12)=0
y₂(5x₁+4x₂-31)=0
y₃(2x₁+3x₂

Источник

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

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

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

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

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

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

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

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

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

Оптимальное решение прямой задачи программирования получается только при одном значении 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 с.

Источник

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

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

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

2.9.1 Экономическая интерпретация

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

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

.

Соотношение прямой и двойственной задач ЛП показано в таблице:

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

.

.

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

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

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

2.9.2 Двойственные задачи и их свойства

Рассмотрим двойственные задачи в общей форме.

,

.

.

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

1. Целевая функция исходной задачи задаётся на максимум, а в двойственной – на минимум.

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

.

3. Число переменных в двойственной задаче равно числу ограничений в исходной задаче (и наоборот).

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

Задача 7. Составить задачу, двойственную следующей задаче:

,

Поскольку прямая задача на максимум, то приведём все неравенства системы ограничений к виду «£» (обе части первого и четвёртого неравенства умножим на –1):

Составим расширенную матрицу системы:

.

.

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

,

.

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

Сначала сформулируем основное неравенство теории двойственности.

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

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

.

Теперь сформулируем достаточный признак оптимальности.

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

,

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

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

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

или .

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

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

План производства и набор цен ресурсов оптимальны тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах , равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам .

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

Пусть даны двойственные задачи.

,

.

,

.

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

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

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

,

.

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

Переменные прямой задачи

Первоначальные

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

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

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

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

Задача 8. Решив симплексным методом задачу

,

получим: , .

Перейдём к неравенствам типа “”:

.

,

Соответствие между переменными (см. табл. выше):

.

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

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

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

2.9.4 Объективно обусловленные оценки

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

Рассмотрим двойственные задачи об использовании ресурсов (из четырёх видов ресурсов можно изготовить два вида продукции или продать ресурсы).

. .

Решения: , ; , .

Связь между решениями прямой и двойственной задач иллюстрирует таблица:

Компоненты оптимального решения прямой задачи

Число единиц продукции

Остатки ресурсов, единиц

Превышение затрат на ресурсы

над ценой реализации

Объективно обусловленные оценки ресурсов

(условные цены ресурсов)

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

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

Ресурсы по оптимальному плану полностью использованы (), и объективно обусловленные оценки этих ресурсов ненулевые (). Ресурсы использованы в оптимальном плане не полностью () и объективно обусловленные оценки этих ресурсов нулевые ().

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

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

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

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

2. Дать экономическую интерпретацию пары взаимно-двойственных задач.

3. Сформулировать свойства пары взаимно-двойственных задач.

4. Сформулировать первую теорему двойственности и ее экономическое содержание.

5. Сформулировать вторую теорему двойственности и ее экономическое содержание.

5. Дать определение понятию объективно-обусловленные оценки.

Источник