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

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

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

Очистить все ячейки?

Введите имя файла

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где ,,,,,,

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

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

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

где , , .

Имеем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда:

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

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

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

или

где

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

  2. Составить расширенную матрицу системы А1, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в целевой функции.

  3. Найти матрицу , транспортную к матрице А1.

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

Пример 1.

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

Решение

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

2. Составляем расширенную матрицу

3. Транспонируем матрицу

4. Формулируем двойственную задачу

Исходная (прямая) задача

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

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

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

    Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство f < z можно интерпретировать следующим образом:

Доход < Общая стоимость ресурсов

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

Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия  о дополняющей нежесткости.

            1. Если суммарная оценка  i-го ресурса положительна

                                                          

то этот ресурс в соответствии с оптимальным планом  х* используется полностью

                                  

            2. Если i-й ресурс используется не полностью

                                  

то его оптимальная оценка нулевая    и i-е ограничение несущественно.

            3. Если в соответствии с оптимальным планом х* j-я продукция производится

                                                

то это производство эффективно, так как цена единицы j-й продукции

                                                          

равна затратам на ее производство в единицах

                                  

                                  

            4. Если производство j-й продукции убыточно (приведенные издержки ненулевые

                                  

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

                                  

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

двойственность — Инструмент для получения двойной задачи из любой задачи линейной оптимизации (.lp)

спросил

Изменено 3 года, 1 месяц назад

Просмотрено 3к раз

$\begingroup$

Есть ли инструмент, который считывает любую задачу линейной оптимизации (например, файл . lp или .mps), преобразует ее в двойную задачу и печатает двойную задачу?

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

$\endgroup$

0

$\begingroup$

Рекомендую ознакомиться с последними разработками вокруг JuMP. В этом году они разработали два интересных пакета:

  • MathOptFormat.jl, который позволяет импортировать/экспортировать задачу оптимизации в MPS, LP, CBF и т.д…
  • Dualization.jl, который позволяет автоматически дуализировать любую оптимизационную задачу в конической форме

Здесь вы можете найти сценарий Julia, который принимает в качестве входных данных файл MPS и выводит двойную задачу в файл LP.

Однако у меня возникают некоторые проблемы с MathOptFormat, так как этот пакет еще не может импортировать LP-файлы… Я думаю, работа все еще продолжается!

$\endgroup$

1

$\begingroup$

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

$\endgroup$

2

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя электронную почту и пароль

Опубликовать как гость

Электронная почта

Требуется, но никогда не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie

.

Двойная проблема

Слабая двойственность > Двойная проблема | Геометрия | Минимаксное неравенство

Первичная проблема

Рассмотрим задачу условной оптимизации в стандартной форме:


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

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


для соответствующей матрицы и вектора.

Функция Лагранжа

Мы определяем функцию Лагранжа как функцию со значениями


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

Пример: Задача о минимальном расстоянии до многогранника выше допускает лагранжиан


Двойная функция

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

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


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


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

Имеем для любого , . Сопоставляя это с предыдущим неравенством, мы получаем


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


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

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

.

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


Двойная проблема

Поскольку нижняя граница верна для каждого , мы можем искать наилучшую, то есть самую большую нижнюю границу:


Задача нахождения наилучшей нижней границы:


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

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


Задачи с ограничениями равенства

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

Замечания

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

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

  • Даже если можно вычислить , максимизировать может быть непросто: выпуклые задачи не всегда легко решить.

  • Нижняя граница может не представлять большого практического интереса: часто нам нужно субоптимальное решение.

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

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