Л.Р. №6. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
Задание:
Составить двойственную задачу на основе исходной задач (см. лабораторную работу № 1.
Решить двойственную задачу симплекс-методом.
Решить двойственную задачу на компьютере.
Сравнить оптимальные решения, полученные на компьютере и симплекс — методом.
Сделать выводы.
Теория:
ПОНЯТИЕ ДВОЙСТВЕННОСТИ.
Описанные выше методы оценки чувствительности оптимального решения носят узкий характер, т. е. позволяют решать лишь частные задачи анализа на чувствительность моделей линейного программирования.
Понятие двойственности в теории линейного программирования возволяет унифицированным
Для тех, кто не знаком
с линейным программированием, понятие
двойственности может показаться абстрактным и, следовательно, весьма непривычным.
Только со временем это впечатление
уступает месть пониманию исключительной
важности и
полезности этого понятия.Мы рассмотрим двойственные задачи, оценки и их экономическую интерпретацию.
ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОСТИ.
С каждой задачей линейного программирования можно связать некоторую другую задачу, называемую двойственной. Первоначальную задачу при этом называют исходной. Рассмотрим двойственную задачу в общей постановке.
Пусть ограничения исходной задачи имеют вид:
На множестве решений этой системы требуется максимизировать функцию
Двойственной для этой задачи будет задача с ограничениями
и минимизируется целевая функция
Сравнивая две задачи, нетрудно заметить, что:
а) матрица из коэффициентов при переменных в исходной задаче имеет вид:
и аналогичная матрица в двойственной задаче имеет вид:
Как видно из сравнения, А/ есть транспонированная матрица А, то есть i-я строка матрицы А является i-м столбцом матрицы А/ и наоборот;
б) в исходной задаче n переменных xj и m ограничений, в двойственной – m переменных yi и n ограничений;
в) в правых частях систем ограничений каждой из задач стоят коэффициенты целевой функции, взятые из другой задачи;
г) в систему
ограничений исходной задачи входят
неравенства типа ≤ , причем в задаче
требуется максимизировать целевую функцию F.
В систему ограничений двойственной
задачи входят неравенства типа ≥ ,
причем в двойственной задаче требуется минимизировать целевую функцию.
Исходная и двойственная ей задачи образуют пару задач, называемую в линейном программировании двойственной парой.
Замечание 1: за исходную задачу можно взять любую задачу из этой пары, для дальнейшего решения это несущественно.
Понятие о двойственной задаче позволит нам рассмотреть алгоритм решения транспортной задачи, как частный случай симплексного метода.
Грубо говоря, двойственная задача – это на 90° повернутая исходная задача.Определение: Две задачи линейного программирования, удовлетворяющие указанным выше условиям, называются симметричными взаимно двойственными задачами.
Таким образом,
каждой задаче линейного программирования
можно поставить в соответствие
двойственную задачу.
Замечание 2. Следует уточнить тип знака ограничений двойственной задачи. А именно, если xj≥0, т.е. на j-ю переменную задачи наложено ограничение неотрицательности, то ограничение двойственной задачи имеет тип ≥.
Замечание 3. Если в исходной задаче ограничение имеет вид равенства, то на соответствующую этому ограничению переменную yi в двойственной задаче не накладывается условие неотрицательности .
Если же ограничение имеет вид неравенства «≤», то соответствующая переменная yi в двойственной задаче неотрицательна .
Рассмотрим эти утверждения на примере:
Прямая задача.
Найти
При
Введем переменные двойственной задачи y1, y2, y3, y4 (их столько, сколько ограничений в прямой задаче).
- Запишем целевую функцию двойственной задачи:
Записываем систему ограничений двойственной задачи:
4. Вводим условия неотрицательности для переменных двойственной задачи:
— произвольные, т. к. в первых двух ограничениях стоят знаки «=«;
т. к. в третьем и четвертом ограничениях исходной задачи стоят знаки «≤«.
Замечание 4. В случае смешанных неравенств (≤ ≥) следует их привести к однородной форме (умножением соответствующих неравенств на –1).
СВОЙСТВА ДВОЙСТВЕННЫХ ЗАДАЧ (ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ)
Будем называть
прямую (исходную) задачу Х-задачей, а
двойственную к ней – Y-задачей.
Теорема 1 (Достаточный признак оптимальности)
Если есть допустимое решение Х-задачи, а есть допустимое решение Y-задачи и при этом , то есть оптимальное решение Х-задачи, а есть оптимальное решение Y-задачи.
Равенство целевых функций прямой и двойственной задач есть достаточное условие оптимальности двух допустимых решений пары симметричных двойственных задач.
Теорема 2 (Основная теорема двойственности)
а) Если одна из двойственных задач имеет оптимальное решение, то вторая также имеет оптимальное решение с тем же значением целевой функции.
Вместо доказательства теоремы убедимся в ее справедливости на примере, который решим графическим методом.
Х – задача: найти
Y
– задача:Таким образом
б) Если одна из
пары двойственных задач не
имеет оптимального решения из-за неограниченности
целевой функции
,
то система ограничений второй задачи
несовместна (пустое
множество).
Пример:
Х – задача: найти
Множество решений является пустым, то есть система ограничений несовместна. Умножим второе неравенство на –1:
Y – задача:
Здесь целевая функция не ограничена, т. е. , что доказывает утверждение теоремы.
Теорема 3 (Теорема о дополнительной нежесткости)
Пусть есть оптимальное решение Х-задачи. В этом случае должны выполняться условия дополнительной нежесткости:
На
основании теоремы 2, оптимальное решение
Х-задачи однозначно определяет оптимальное
решение Y-задачи.
При этом симплексный алгоритм, примененнный
к Х-задаче задает новый алгоритм
преобрзований коээфициентов Y-задачи,
который можно выписать в явном виде и
применять для решения исходной задачи
линейного программирования. Этот
алгоритм называется двойственным
симплекс-методом.
Двойственная задача — Энциклопедия по экономике
Можно найти ее решение (это легко сделать графически). Оптимальной является вершина v = 3/7, ill]. При этом значение критерия равно 10/7, т. е. совпадает с оптимальным в исходной задаче. Легко проверить, что решение прямой задачи х = 6/7, 4/7 и решение двойственной задачи и = 3/7, 1/7 удовлетворяют условиям максимума для этой задачи, выписанным в конце предыдущего пункта данного параграфа. [c.55]На совпадении условий (4.25) — (4.3Q) и (4.34) — (4.39) основываются теоремы о связи исходной и двойственной задач. Прежде всего обратим внимание па тот важный факт, что любой допустимый вектор х прямой задачи и любой допустимый вектор v двойственной задачи удовлетворяют соотношению [c.55]
Из утверждения (4.40) легко получить первую теорему двойственности если прямая и двойственная задачи имеют допустимые решения, то обе они имеют и оптимальные решения х и [c.55]
Таким образом, значения оптимального решения двойственной задачи характеризуют устойчивость по отношению к изменениям правых частей ограничений.
Это определяет их важную роль в экономическом исследовании при анализе последствий изменения правых частей задачи. Поскольку величины v- (j = = 1,. .., иг) оценивают существенность изменения критерия при изменении соответственного ограниченного ресурса, их часто называют объективно обусловленными оценками данного ресурса (а также оптимальными или двойственными оценками). Как мы увидим в заключительной главе книги, объективно обусловленные оценки могут использоваться и при решении задач ценообразования.
[c.56]
Для анализа полученных соотношений (1.23), (1.24) сформулируем задачу линейного программирования, двойственную к (1.21) (см. 4 гл. 1). Как видно, ограничения двойственной задачи совпадают с (1.23) — (1.24), а критерием ее является [c.349]
Двойственная задача линейного программирования 54, 347 [c.391]
Существует много методов оценки напряженности заданий коэффициентный метод оценки напряженности плана по темпам роста к предыдущему периоду метод оценки напряженности плана с точки зрения нормативного использования производственных ресурсов метод применения апостериорного статистического критерия качества планирования.
Для этих же целей широко применяются методы линейного программирования, объективно обусловленные оценки В. Новожилова, вытекающие из процедуры решения двойственных задач линейного программирования. В последние годы для оценки напряженности плана разработаны специальные методики, базирующиеся на методах теории статистических распределений, компонентного анализа, современного факторного анализа, других математико-статистических методах.
[c.236]
Существуют и специальные методы, алгоритмы и программы для решения двойственных задач ЛП и получения двойственных оценок. [c.73]
Примеры такого рода могут быть преобразованы в задачи максимизации с последующим применением методов, описанных в предыдущем разделе. Если имеется задача минимизации, тогда соответствующая задача максимизации называется двойственной. Процесс решения двойственной задачи показан на последующих примерах. [c.285]
Двойственную задачу по отношению к прямой составляют согласно правилам [c.124]
Если целевая функция прямой задачи задается на max, тогда целевая функция двойственной задачи — на min, и наоборот.
[c.124]
Число переменных в двойственной задаче (т) равно числу соотношений (ограничений) в прямой задаче, а число ограничений двойственной задаче (п) — числу переменных в прямой задаче. [c.124]
Коэффициенты при неизвестных в целевой функции прямой задачи — это свободные члены (bt), а правые части в ограничениях двойственной задачи (с/) — это коэффициенты при неизвестных в целевой функции прямой задачи. [c.124]
Если переменная Xj прямой задачи может принимать только положительные значения (Xj > 0), то j-e условие двойственной задачи — условие неравенства вида > . Если i-e соотношение в прямой задаче — неравенство, то i-я переменная двойственной задачи гг > 0. [c.124]
Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причем max (min)Li = = min (max)L2. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары обычно решают ту, которая проще. Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи.
[c.124]
Решение. Обозначим через х искомый план производства изделий А, через KZ — В, Хз — С, а через z двойственную оценку дефицитности первого вида ресурса, через z2 — второго, z3 — третьего. Тогда прямая и двойственная задачи формулируются [c.125]
Прямая задача Двойственная задача [c.125]
Решение прямой задачи дает оптимальный план производства изделий А, В, С, а решение двойственной задачи — оптимальную систему оценок ресурсов, используемых для производства этих изделий [c.125]
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем [c.125]
При одновременном изменении ресурсов всех видов на величину Аи, (г = 1. … .. т) можно оценить их суммарное влияние на значение целевой функции (при условии неизменности двойственных оценок в новой двойственной задаче относительно оценок в первоначальной двойственной задаче) [c.126]
Таким образом, чтобы найти решение данной игры по матрице А, нужно составить следующую пару двойственных задач и найти их решение.
[c.157]
Решение. Пара двойственных задач [c.158]
При известных решениях прямой и двойственной задач (yk и pk) коэффициенты гиперплоскости вычисляются по формуле [c.23]
Пусть в этой двойственной задаче t-ro этапа планового периода элементы матрицы А (и ) и составляющие вектора 6f( of) являются независимыми друг от друга нормально распределенными случайными величинами [c.82]
В тех случаях, когда задачи АСУ решаются с использованием дисковой операционной системы ДОС ЕС, программное обеспечение задачи планирования строится на основе пакета LPS-360 [30]. Эта система позволяет при объеме оперативной памяти свыше 64 К эффективно решать задачи, системы ограничений которых включают до 1500 строк. Пакет осуществляет решение прямой и двойственной задачи линейного программирования, выдает информацию о значениях ошибок, позволяет создавать контрольные точки, объединять блоки, вносить изменения и дополнения в систему ограничений и целевую функцию. Разработанные с целью привязки пакета к задачам планирования нефтеперерабатывающих производств Генератор модели» и Интерпретатор» обеспечивают автоматическое построение модели планирования НПП на основе исходных данных о структуре производства, технологических агрегатов и установок, а также представление результатов решения в виде выходных документов, используемых планово-экономическими службами завода.
[c.179]
Модель — в форме пары двойственных задач [37] линейного [c.33]
Для построения двойственной задачи обратимся к методу множителей Лагранжа, который хотя и не эффективен при решении задач линейного программирования, но полезен для их качественного анализа. Функция Лаграижа для задачи (4.22) — (4.24) имеет вид [c.53]
Обратим также внимание на следующий факт, имеющий интересную экономическую интерпретацию (так называемая вторая теорема двойственности) для того чтобы допустимые векторы х и v являлись решениями прямой и двойственной задач соответственно, необходимо и достаточно, чтобы они удовлетворяли условиям дополняющей нежесткости (4.36), (4.37). Доказательство этого факта основано на том, что из (4.36), (4.37) [c.56]
Наличие пары двойственных задач позволяет разработать различные алгоритмы решения задач линейного программиро- [c.56]
Для нахождения этой двойственной задачи мы взаимно переставим ряды и колонки и одновременно поменяем знаки , то есть показатели х дадут нам двойственное условие 4Х + 1У+ 20Z [c.
286]
Пусть пара двойственных задач линейного программирова- [c.38]
Линейное программирование: как написать двойную задачу с резервными переменными
Когда вы добавляете резервные переменные, двойная программа не затрагивается.
В исходной основной программе есть две переменные $x_1, x_2$, соответствующие двум ограничениям в двойственной программе; есть два ограничения, соответствующие двум двойным переменным, которые мы назовем $u_1$ и $u_2$. Поскольку ограничения представляют собой неравенства, $u_1$ и $u_2$ будут неотрицательными переменными. Вот первично-двойственная пара: \begin{массив}{rrll rrll} \text{максимум} & 6x_1 + 10x_2 & & & \text{минимизация} & 60u_1 + 45u_2 \\ & 2x_1 + 8x_2 & \le 60 & (u_1) & & 2u_1 + 3u_2 & \ge 6 & (x_1) \\ & 3x_1 + 5x_2 & \le 45 & (u_2) & & 8u_1 + 5 u_2 & \ge 10 & (x_2) \\ & x_1, x_2 & \ge 0 & & & u_1, u_2 & \ge 0 \конец{массив}
Когда мы добавляем переменные slack в primal, меняются две вещи. Во-первых, ограничения становятся уравнениями, что означает, что $u_1, u_2$ теперь являются неограниченными переменными (без ограничений неотрицательности).
Во-вторых, теперь есть еще два двойных ограничения, соответствующие переменным резерва $s_1$ и $s_2$. Эти двойные ограничения оказываются в точности теми ограничениями $u_1 \ge 0$ и $u_2 \ge 0$, которые мы потеряли при первом изменении. Получаем идентичный дуал:
\begin{array}{rrll rrll}
\text{максимум} & 6x_1 + 10x_2 & & & \text{минимизация} & 60u_1 + 45u_2 \\
& 2x_1 + 8x_2 + s_1 & = 60 & (u_1) & & 2u_1 + 3u_2 & \ge 6 & (x_1) \\
& 3x_1 + 5x_2 + s_2 & = 45 & (u_2) & & 8u_1 + 5 u_2 & \ge 10 & (x_2) \\
& x_1, x_2, s_1, s_2 & \ge 0 & & & u_1 & \ge 0 & (s_1) \\
& & & & & u_2 & \ge 0 & (s_2)
\конец{массив} 9{\mathsf Т}$. Это дает нам
$$
\begin{bmatrix}u_1 и u_2\end{bmatrix} \begin{bmatrix}2 и 3 \\ 8 и 5\end{bmatrix} \ge \begin{bmatrix}6 и 10 \end{bmatrix}
$$
в первом дуале и
$$
\begin{bmatrix}u_1 & u_2\end{bmatrix} \begin{bmatrix}2 & 3 & 1 & 0 \\ 8 & 5 & 0 & 1\end{bmatrix} \ge \begin{bmatrix}6 & 10 & 0 & 0\end{bmatrix}
$$
во втором двойнике. Изменение связано с тем, что в первом двойственном случае мы думаем о $u_1 \ge 0$ и $u_2 \ge 0$ как об ограничениях неотрицательности (рассматриваемых как особый случай), а во втором двойственном — просто о двух линейных ограничениях.
как и любые другие.
Обычно мы не добавляем переменные slack к двойному, но если бы мы это сделали, это имело бы идентичный (но немного более глупый) эффект для primal.
Я думаю, что самый простой способ сделать это — добавить неположительную переменную slack: превратить $2u_1 + 3u_2 \ge 6$ в $2u_1 + 3u_2 + w_1 = 6$, где $w_1 \le 0$. Неположительная слабая переменная в двойственном случае будет соответствовать ограничению $\ge$ в простом, которое заменит ограничение неотрицательности на $x_1$. Мы получим: \begin{массив}{rrll rrll} \text{максимум} & 6x_1 + 10x_2 & & & \text{минимизация} & 60u_1 + 45u_2 \\ & 2x_1 + 8x_2 + s_1 & = 60 & (u_1) & & 2u_1 + 3u_2 + w_1 & = 6 & (x_1) \\ & 3x_1 + 5x_2 + s_2 & = 45 & (u_2) & & 8u_1 + 5 u_2 + w_2 & = 10 & (x_2) \\ & x_1 & \ge 0 & (w_1) & & u_1 & \ge 0 & (s_1) \\ & x_2 & \ge 0 & (w_2) & & u_2 & \ge 0 & (s_2) \\ & s_1, s_2 & \ge 0 & & & w_1, w_2 & \le 0 \конец{массив}
Обратите внимание, что $s_1, s_2$ по-прежнему имеют специальные ограничения неотрицательности, точно так же, как $w_1, w_2$ все еще имеют специальные ограничения неотрицательности.
Если бы мы действительно хотели делать ужасные, неестественные вещи с нашей парой перво-двойственности, мы могли бы добавить переменные slack к ограничениям $x_1 \ge 0, x_2 \ge 0, u_1 \ge 0, u_2 \ge 0$. Это превратит ограничения неотрицательности на $s_1, s_2$ и ограничения неположительности на $w_1, w_2$ в обычные ограничения, сделает матрицу еще больше и добавит больше переменных в обе программы. Вы можете продолжать так бесконечно, создавая раздутые первично-двойственные пары, которые в конечном счете эквивалентны оригиналу.
Элементы задачи линейного программирования (LPP) | by ARIMITRA MAITI
Photo by Ivan Aleksic on UnsplashЛинейное программирование рассматривается как революционная разработка, дающая человеку возможность формулировать общие цели и находить с помощью симплекс-метода оптимальные политические решения для широкого класса практических задач. большой сложности. В реальном мире планирование имеет тенденцию быть случайным из-за множества групп с особыми интересами, преследующих множество целей.
~ Джордж Данциг
~ Джордж ДанцигТехника LPP была впервые представлена в 1930 году русским математиком Леонидом Канторовичем в области производственных графиков и американским экономистом Василием Леонтьевым в области экономики. Спустя десятилетие во время Второй мировой войны эти методы широко использовались для решения проблем, связанных с транспортировкой, планированием, распределением ресурсов и т. Д. В 1950 году американский математик Джордж Данциг создал первый алгоритм симплекс-метода для LPP.
Элементы базового LPP
Переменные решения: это неизвестные величины, которые, как ожидается, будут оценены как результат решения LPP.
Целевая функция: все задачи линейного программирования направлены на максимизацию или минимизацию некоторого числового значения, представляющего прибыль, затраты, объем производства и т. д. Он оценивает сумму, на которую каждая переменная решения будет вносить вклад в чистую текущую стоимость проекта или деятельности.
.
Коэффициент целевой функции: Величина, на которую значение целевой функции изменится при изменении одной единицы переменной решения, определяется соответствующим коэффициентом целевой функции.
Ограничения: Ограничения или ограничения на общую сумму определенного ресурса, необходимого для выполнения действий, которые определяют уровень достижений в переменных решения. В стандартной форме задачи линейного программирования все ограничения представлены в виде уравнений.
Неотрицательные ограничения: Каждая переменная решения в любой модели линейного программирования должна быть положительной независимо от того, является ли целевая функция максимизацией или минимизацией чистой приведенной стоимости деятельности. Это критическое ограничение.
Двумя другими элементами являются доступность ресурсов и технологические коэффициенты, которые можно лучше обсудить на примере ниже. Допустимое решение задачи линейного программирования должно удовлетворять ограничениям и ограничениям неотрицательности.
Допустимое решение ЗЛП с задачей максимизации становится оптимальным решением, когда значение целевой функции наибольшее (максимальное). Точно так же допустимое решение ЛПП с задачей минимизации становится оптимальным решением, когда значение целевой функции является наименьшим (минимальным).
Любая LPP предполагает, что переменные решения всегда имеют степень единицы, т. е. они не возводятся ни в какую степень больше или меньше единицы.
Двойственное представление LPP
Любая задача LPP может быть преобразована в соответствующую пару, также известную как двойственная, которая может дать такое же допустимое решение целевой функции. Если primal — это проблема максимизации , то все ограничения, связанные с целевой функцией, должны иметь ограничения «меньше, чем равные» с доступностью ресурсов, если только конкретное ограничение не является неограниченным (в основном представлено ограничением «равно»).
Если какое-либо ограничение имеет какое-либо ограничение «больше, чем равно» с доступностью ресурсов, то primal рекомендуется преобразовать в каноническую форму (умножив на «минус»), чтобы ограничение задачи максимизации преобразовалось в «меньше, чем равно». .
Аналогично, если основная задача является задачей минимизации , то все ограничения, связанные с целевой функцией, должны иметь ограничения «больше, чем равно» с доступностью ресурсов, если конкретное ограничение не является неограниченным (в основном представлено ограничением «равно» ). Если какое-либо ограничение имеет какое-либо ограничение «меньше, чем равно» с доступностью ресурсов, то рекомендуется преобразовать primal в каноническую форму (умножив на «минус»), чтобы ограничение 9Задача минимизации 0050 трансформируется в задачу «больше равно» .
Вышеупомянутые шаги канонической формы необходимы только тогда, когда требуется вручную переписать первичный LPP в его соответствующую двойную форму.
В общем, назначенное программное обеспечение способно решить проблему неявным образом.
Необходимыми условиями для применения LPP являются определенная целевая функция, ограниченный запас доступности ресурсов и неотрицательные и взаимосвязанные переменные решения.
Если переменные решения неположительны (т.е. «меньше нуля» вместо «больше нуля»), то перед двойным упражнением их необходимо преобразовать в каноническую форму.
Primal-Dual LPP Пример-6 , Источник изображения: (Изображение от автора)Графическое решение
Графическое решение Primal LPP, Пример-1, Источник изображения: (Изображение от автора), Workbook LinkГрафическое решение Dual LPP , Пример 1, Источник изображения: (Изображение от автора), Ссылка на книгу.
Мы видим, что значение целевой функции как для основного, так и для двойного LPP остается одинаковым и составляет 1288,9. Изначально цель состояла в том, чтобы максимизировать, из-за чего никакая другая точка, кроме точки-C (X1=51,1, X2=52,2), не может дать более высокое значение целевой функции (15*X1 + 10*X2). Следовательно, хотя возможная область — это заштрихованная область внутри точек A, B, C и D, оптимальное решение достигается в точке C. В первичном случае желательны любые точки ниже линий ограничения 1 и 2, потому что мы хотим максимизировать целевую функцию для заданных ограниченных ограничений, имеющих ограниченную доступность.
Однако в двойственном случае желательны любые точки над линиями ограничений 1 и 2, потому что мы хотим минимизировать целевую функцию для заданных ограничений, которых много. Цель состояла в том, чтобы минимизировать, из-за чего никакая другая точка, кроме Точки-B (Y1=4,4, Y2=11,1), не может давать меньшее значение целевой функции (65*Y1 + 90*Y2).
Следовательно, для задачи максимизации оптимальная точка удаляется от начала координат, а для задачи минимизации оптимальная точка приближается к началу координат.
Ограничение этой графической иллюстрации заключается в том, что в случаях более чем 2 переменных решения нам потребуется более 2 осей, и поэтому представление становится трудным. Следовательно, оптимальная точка все еще может быть проверена в случаях, когда у нас есть 2 переменных решения и 2 или более ограничений основной задачи, однако соответствующая двойная, имеющая более 2 переменных решения, становится неудобной для построения.
Линейное программирование не имеет ничего общего с компьютерным программированием. Использование слова «программирование» здесь означает «выбор курса действий». Линейное программирование предполагает выбор образа действий, когда математическая модель задачи содержит только линейные функции. ~ AWSCCFO
Сноски
Эта статья представляет собой введение в элементы задачи линейного программирования (LPP).