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

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

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

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

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

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

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

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

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

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

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

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

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

Выручка предприятия от продажи сырья, расходуемого на единицу продукции П_i, составит: Σ 4 _i=1 a_ij y_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₃ и удовлетворяют ограничениям неравенствам

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) Метод искусственного базиса приводит к увеличению числа неизвестных задач, что нежелательно. Анализ задачи показывает, что число уравнений в системе ограничений больше числа переменных. Поэтому попытаемся применить принцип двойственности, т.е. вначале решим двойственную ЗЛП, а затем найдем решение исходной.

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

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

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

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

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

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 ) вычитаем левые части ограничений

γ₀ =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. В прямой задаче ищется максимум функции цели (линейной формы), а в двойственной задаче — минимум.
2. Коэффициенты при переменных в функции цели прямой задачи являются свободными членами системы ограничений двойственной задачи, и наоборот, свободные члены системы ограничений прямой задачи — коэффициентами при переменных в функции цели двойственной задачи.
3. В каждой задаче система ограничений задаётся в виде неравенств, причём все они одного смысла, а именно: при нахождении максимума функции цели (прямая задача) эти неравенства записываются со знаком «меньше или равно», а при нахождении минимума (двойственная задача) — со знаком «больше или равно».
4. Коэффициенты при переменных в системах ограничений описываются матрицами

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

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

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

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

1. Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла(то есть с одним и тем же знаком): если в исходной задаче ищется максимум функции цели (линейной формы) — они записываются со знаком «меньше или равно», если же минимум — со знаком «больше или равно». Для этого неравенства, в которых это требование не выполняется, умножают на минус единицу.
2. Выписывают матрицу A коэффициентов при переменных исходной задачи, полученых после преобразований, описанных в предыдущем пункте, и составляют матрицу A‘, транспонированную относительно матрицы A.
3. Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы A‘, а в качестве свободных членов — коэффициенты при переменных в функци цели исходной задачи и записывают неравенства противоположного смысла (то есть меняют знак) по сравнению с неравенствами, полученными в пункте 1.
4. Составляют функцию цели (линейную форму) двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в пункте 1.
5. Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум функции цели, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум.
6. Записывают условие неотрицательности переменных двойственной задачи.

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

Решение. Третье неравенство системы исходной задачи не удовлетворяет пункту 1 правил составления двойственной задачи. Поэтому умножим его на минус единицу:

Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей B, в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в функции цели, выделив для этой цели дополнительные столбец (отделён чертой) и строку (выделена красным цветом). Матрицу B транспонируем и, используя транспонированную матрицу B‘, составляем задачу, двойственную исходной. Матрицы B и B‘ имеют вид

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

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

1. Свободные члены в прямой задаче — коэффициенты функции цели в двойственной задаче.
2. Коэффициенты функции цели в прямой задаче — свободные члены в двойственной задаче.
3. Расширенная матрица в прямой задаче — транспонированная расширенная матрица в двойственной задаче.
4. j-й неизвестный в прямой задаче неотрицательный — j-е неравенство в двойственной задаче со знаком «больше или равно».
5. j-й неизвестный в прямой задаче без ограничения знака — j-е ограничение в двойственной задаче в виде уравнения.
6. j-й неизвестный в прямой задаче неположительный — j-е неравенство в двойственной задаче со знаком «меньше или равно».
7. i-е неравенство в прямой задаче со знаком «меньше или равно» — i-е неизвестный в двойственной задаче неотрицательный.
8. i-е ограничение в прямой задаче в виде уравнения — i-й неизвестный в двойственной задаче без ограничения знака.
9. i-е неравенство в прямой задаче со знаком «больше или равно» — i-й неизвестный в двойственной задаче неположительный.

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

Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, как и в предыдущем примере, произведём универсальное действие — составим матрицу B прямой задачи и транспонированную матрицу B‘ двойственной задачи:

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

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

Теория двойственности в линейном программировании строится на двух основных теоремах.

Теорема 1. Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. F max = Z min или F min = Z max . 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.

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

При решении симплекс-методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести m добавочных неотрицательных переменных (по числу неравенств в системе ограничений) x n+1 , x n+2 , . x n+i , . x n+m , где i = 1, 2, . m означает номер неравенства, в которое была введена добавочная переменная x n+i .

Система ограничений двойственной задачи состоит из n неравенств, содержащих m переменных. Если решать эту задачу симплекс-методом, то следует ввести n добавочных неотрицательных переменных y m+1 , y m+2 , . y m+j , . y m+n , где j = 1, 2, . n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная y m+j .

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

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

Иными словами, каждой первоначальной переменной исходной задачи x j ( j = 1, 2, . n ) ставится в соответствие добавочная переменная y m+j , введённая в j-е неравенство двойственной задачи, а каждой добавочной переменной x n+i исходной задачи ( i = 1, 2, . m ), введённой в i-е неравенство исходной задачи, — первоначальная переменная y i двойственной задачи.

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

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

Из теорем 1 и 2 следует, что если решить одну из взаимно двойственных задач линейного программирования, то есть найти её оптимальное решение и оптимум функции цели, то можно записать оптимальное решение и оптимум функции цели другой задачи. Теперь пример, который поможет разложить всё вышеизложенное по полочкам.

Пример 3. На основании решений прямой и двойственной задач линейного программирования из примера 1 убедиться в справедливости теорем 1 и 2.

В примере 1 была дана исходная задача: найти максимум функции при ограничениях

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

Для решения прямой задачи симплекс-методом система ограничений-неравенств сводится к системе уравнений путём введения добавочных неотрицательных переменных x 3 , x 4 , x 5 , x 6 :

Читатель может проверить, решив задачу симплекс-методом, что она имеет следующие решения:

а максимум целевой функции F max = 13 ,

при этом сама целевая функция выражается как

Система ограничений двойственной задачи сводится к системе уравнений путём введения добавочных переменных y 5 , y 6 :

Решение двойственной задачи симплекс-методом даёт следующий ответ:

а минимум целевой функции Z min = 13 ,

при этом сама целевая функция выражается как

Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причём Z min = F max = 13 .

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

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

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

Рассматривая коэффициенты при переменных y j в этой функции цели и учитывая их соответствие коэффициентам при переменных x i , получим решение (4; 1; 0; 5; 4; 0) , совпадающее с решением прямой задачи.

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

На основании теоремы 2, учитывая соответствие между переменными в прямой и двойственной задачах и взяв абсолютную величину коэффициентов при переменных, найдём оптимальное решение двойственной задачи (2/3; 0; 0; 7/3; 0; 0) . При этом Z min = F max = 13 .

Пример 4. Убедиться в том, что системы ограничений прямой задачи

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

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

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

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

Посмотрим ещё раз на прямую задачу линейного программирования и двойственную задачу рядом.

Прямая задача.
Максимизировать функцию

Двойственная задача.
Минимизировать функцию

В этих задачах a — расходы сырья определённого вида на производство одного вида продукции, b запасы сырья определённого вида, c — прибыль от реализации единицы продукции определённого вида. В прямой задаче x — количество единиц выпускаемой продукции определённого вида. А в двойственной задаче b — цены сырья соответствующего вида. А целевая функция Z — общие затраты на приобретение сырья, которые требуется минимизировать.

Предположим, мастерская выпускает столы и шкафы, расходую на эти цели определённые виды сырья (древесины). Допустим, мастерская решила не производить продукцию, а продать сырьё — древесину, желая при этом получить выручку, не меньшую максимальной прибыли от реализации продукции. По каким ценам нужно продавать каждый вид древесины?

Максимальную прибыль определяет решение прямой задачи. Путём же решения двойственной задачи линейного программирования находятся цены y, точнее говоря, объективно обусловленные оценки. Они являются компонентами оптимального решения двойственной задачи линейного программирования.

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

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

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

Запись

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

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

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

(1a)

(1b)

(1c)

(1d)

(1e)

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

(2a)

(2b)

(2c)

(2d)

(2e)

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

Отметим, что если задача ЛП (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), соответственно, то

.

(3)

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

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

(4a)

(4b)

(4c)

(4d)

где ,,,,,,

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

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

, ,

(5a)

(5b)

(5c)

(5d)

где , , .

(6)

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

,

(7)

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

(8)

(9)

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

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

(9)

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

(10)

(11)

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

(12)

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

(13)

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

(14)

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

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

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

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

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

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

.

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

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

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

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

(15)

,

(16)

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

.

(17)

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

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

, .

(18)

,

(19)

.

(20)

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

.

(21)

,

(22)

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

,

(23)

,

(24)

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

.

(25)

А Запись (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. Дана следующая задача ЛП:

(26a)

(26b)

(26c)

(26d)

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

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

, , , .

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

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

(27)

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

(28)

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

(29)

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

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

(30a)

(30b)

(30c)

(30d)

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

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

,

(31)

.

(32)

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

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

.

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

.

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

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

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

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

(33a)

(33b)

(33c)

(33d)

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

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

, , , .

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

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

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

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

(34a)

(34b)

(34c)

(34d)

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

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

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

.

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

.

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

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

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

Предприятие выпускает n видов продукции (P 1, P2, …, Pn) используя для производства m видов ресурсов (S 1, S2, …, Sm). Известны данные о нормах расхода ресурсов на единицу продукции каждого вида и их запасах на предприятии, т.е.

: – норма расхода ресурса Si для производства единицы продукции Pj; – запас ресурса Si на предприятии.

Цена единицы продукции Pj составляет .

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

Обозначим через – объем продукции Pj, запланированный к производству – искомые величины. Тогда математическая модель данной задачи будет иметь следующий вид:

Полученная задача, является задачей линейного программирования, записанной в стандартной форме. Для удобства задачу (8.1)–(8.3) можно представить в компактной форме:

В итоге математическая модель задачи планирования производства может быть сформулирована следующим образом: составить такой план производства продукции X=(x1, x2, …, xn), удовлетворяющий системе ограничений (8.4), условию (8.5), при котором целевая функция (8.6) принимает наибольшее значение.

Предположим, что некоторая организация решила закупить у предприятия ресурсы S1, S 2, …, Sm и ей необходимо определить оптимальные цены на эти ресурсы y1, y2, …, ym, исходя из следующих условий:

1) общая стоимость ресурсов для закупающей организации должна быть минимальной;

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

Исходя из условия 1 покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b 1, b2, …, bm по ценам соответственно y1, y 2, …, ym были минимальными, т.е.

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

По свой сущности переменные yi не отрицательные, т.е.
. (8.9)

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

Сравним математические модели (8.1) – (8.3) и (8.7) – (8.9):

1) число неизвестных одной задачи равно числу ограничений другой;

2) матрица коэффициентов системы ограничений одной задачи получается путем транспонирования матрицы коэффициентов системы ограничений другой задачи;

3) неравенства в системах ограничений имеют противоположный смысл;

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

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

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

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

Правила построения двойственной пары:

1) Знаки неравенств в системе ограничений исходной задачи приводятся в соответствие с ее целевой функцией, т.е. если она минимизируется, то неравенства должны иметь вид «?», а если максимизируется, то «?». Данный принцип распространяется и на двойственную задачу.

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

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

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

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

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

6) Записывается система ограничений двойственной задачи, причем вид каждого ограничения определяется исходя из следующего правила:

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

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

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

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

В соответствии с правилом 2 вводим две переменные y 1 и y2, причем, исходя из правила 3, y1 ? 0, а переменная y2 не ограничена по знаку.

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

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

Запишем систему ограничений двойственной задачи:

Первое и второе ограничение имеют вид неравенства в силу того, что переменные x1 и x2 удовлетворяют условию неотрицательности, а знак «?» определяется правилами 1 и 7. Переменные x3 и x4 не ограничены по знаку, поэтому третье и четвертое ограничения двойственной задачи записаны в виде уравнений.