Как по исходной задаче составит двойственную

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

Двойственность является важным понятием в линейном программировании, имеющим экономическое (практическое) применение. Например, для задачи оптимального распределения ресурсов для производства некоторых видов товаров пара прямой и двойственной задачи принимает следующий экономический смысл:
Прямая задача: Сколько и какой продукции xj необходимо производить, чтобы при заданных доходах Cj и объемах ресурсов bi максимизировать доход от продажи продукции?
Двойственная задача: Какова должна быть «теневая» цена каждого ресурса yi, чтобы при заданных количествах bi и доходах Cj минимизировать затраты?

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

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

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

Задача 1. Записать математическую модель двойственной ЗЛП по заданной прямой:

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

Задача 3. Решить задачу линейного программирования; составить задачу, двойственную данной, и также найти ее решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оптимальный план 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 γ_i y_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 единицы. Это значение с противоположным знаком записано в той же таблице.

Литература

С
каждой ЗЛП связана другая линейная
задача, которая называется двойственной(первоначальная задача называетсяисходной).

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

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

Свойства двойственных задач

1. Если целевая функция исходной задачи
   формулируется на максимум, а целевая
   функция двойственной задачи – на
   минимум, при этом в задаче на максимум
   все неравенства в ограничениях приводят
   к виду “”,
   а в задаче на минимум – вид “”.

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

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

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

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

6. Предполагается, что переменные в обеих
   задачах являются неотрицательными.

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

Замечание.

Двойственная задача к двойственной будет исходной.

Замечание.

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

Между взаимно двойственными ЗЛП имеет
место взаимосвязь, которая следует из
теорем двойственности.

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

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

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

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

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

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

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

Пример 2.4.1. Записать двойственную
задачу для ЗЛП (2.2.1), (2.2.2). Выписать
решение двойственной задачи.

Решение.Поскольку исходная задача
на максимум, то во всех ограничениях
системы (2.2.1) должен быть знак “”.
Для этого обе части третьего неравенства
умножаем на (–1) и меняем знак неравенства
на противоположный. Таким образом,
получим:

(2.4.1)

max z=x₁+ 4x₂(2.4.2)

Для задачи (2.4.1), (2.4.2) запишем двойственную.
Для этого:

Выпишем матрицу коэффициентов при
неизвестных в системе ограничений
(2.4.1)

и транспонируем ее (т.е. поменяем местами
строки и столбцы):

.

На основе транспонированной матрицы
составим систему ограничений двойственной
задачи, причем в неравенствах ограничений
будет знак “”
и в правой части этих неравенств будут
стоять коэффициенты целевой функции
(2.4.2), т.е. 1 и 4:

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

min f= – 5y₁+ 6y₂ –
7y₃.

Итак, двойственная задача имеет вид
(2.4.3), (2.4.4):

(2.4.3)

min f= – 5y₁+ 6y₂ –
7y₃. (2.4.4)

Исходная и двойственная ЗЛП имеют разный
экономический смысл. Решая одну задачу
можно не решать другую, а сразу выписать
ее решение. Решение двойственной задачи
y₁,y₂,y₃находится вz-строке последней
симплексной таблицы в дополнительных
столбцах (а именно, в столбцахр₃,р₄,р₅). Нужно помнить,
что решение выписывается с учетом
неотрицательности переменных. В нашем
случае решение следующее:

y₁ = 0,y₂ = 9/2,y₃
= 1/2.

При подстановке этого решения в целевую
функцию двойственной задачи (4.4) должно
получится число, стоящее в z-строке
последней симплексной таблицы в столбцер₀. Проверим:

min f=maxz.

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

min z= -7x₁+ 3x₂.

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

Целевая функция при этом остается
прежней, а именно: min z=-7x₁+3x₂.
Выпишем матрицу, состоящую из коэффициентов
при неизвестных в системе ограниченийи транспонируем:.

На основе
составим систему ограничений для
двойственной задачи, причем в ограничениях
будет знак “”
и в правой части неравенств будут стоять
коэффициенты из целевой функции исходной
задачи. Целевая функция будет
максимизироваться и состоять из
коэффициентов, стоящих в правой части
неравенств исходной задачи. Таким
образом, двойственная задача будет
иметь вид:

max f=y₁– 5y₂ + 6y₃.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

Правило3. Если
знаки неравенств в ограничениях исходной
задачи «», то целевая функция,
а если «», то.

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

Правило5.
Целевая функция двойственной задачи
имеет вид

,

где

–
свободные члены в ограничениях исходной
задачи.

Правило6.
Целевая функциядолжна оптимизироваться противоположным
по сравнению собразом.

Правило7.
Каждому неизвестномух_j
, j = 1, 2, …,nисходной задачи соответствует ограничение
в двойственной задаче. Совокупность
этихnограничений
(вместе с условиями неотрицательности
неизвестныхy_i
, соответствующих ограничениям-неравенствам
исходной задачи) образует систему
ограничений двойственной задачи. Все
ограничения двойственной задачи имеют
вид неравенств, свободные члены которых
находятся в правых частях, а члены с
неизвестнымиy₁,y₂, …,– в левых.

Все знаки неравенств
имеют вид «
», если,
и «», то.

6.2. Одновременное решение прямой и двойственной задач

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

— обе задачи из
пары двойственных имеют оптимальные
решения;

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

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

Из этой теоремы
вытекает следующее

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

Теорема
6.2.2 (2-я теорема двойственности).Пусть
имеется симметричная пара двойственных
задач

,
,(6.2.1)

,
;,.

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

, ; (6.2.2)

, . (6.2.3)

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

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

,
.

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

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

, ; , ; ;

Рис. 6

.

Подставим оптимальное
решение
в систему ограничений. Получим, что
ограничения (1) и (4) выполняются как
строгие неравенства:

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

__________________

;

=7,
=1;.

Ответ:
102 при.

Соседние файлы в папке математика_2

• #
• #

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

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

---

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

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

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

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

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

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

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

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

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

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

 и

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

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

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

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

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

 и

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

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

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

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

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

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

 и

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

, то

 и

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

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

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

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

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

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

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

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

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

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

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

и так далее.

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

и так далее.

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

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

 и

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

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

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

производства расход 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-е ограничения выполняются
как неравенство, то

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

 и

, получаем:

Ответ

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