🗊Презентация Двойственность в линейном программировании

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

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

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

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

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

Если переменная xj исходной задачи может принимать только неотрицательные значения, то j-е ограничение двойственной задачи является неравенством вида “”. Если переменная xj исходной задачи может принимать только неотрицательные значения, то j-е ограничение двойственной задачи является неравенством вида “”. Если переменная xj может принимать как положительные, так и отрицательные значения, то j-е ограничение двойственной задачи - уравнение. Аналогично, если i-е ограничение в системе исходной задачи является неравенством, то yi  0. Если же i-е ограничение есть уравнение, то переменная yi может принимать как положительные, так и отрицательные значения.

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

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

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

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

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

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

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

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

Свойства двойственных задач Теорема 1. Если исходная задача имеет оптимальный план, то и сопряженная к ней задача имеет оптимальный план, причем значение ЦФ при этих планах совпадают. Если ЦФ одной из двойственных задач не ограничена на множестве допустимых решений (для исходной – сверху, для сопряженной –снизу), то двойственная задача вообще не имеет плана.

Теорема 2 . Пара допустимых решений X* - в исходной задаче, Y* - в двойственной задаче будут оптимальными решениями тогда и только тогда, кода выполняются следующие соотношения: Теорема 2 . Пара допустимых решений X* - в исходной задаче, Y* - в двойственной задаче будут оптимальными решениями тогда и только тогда, кода выполняются следующие соотношения:

Связь исходной и двойственной задач Решение одной из них может быть получено из решения другой. Используя последнюю симплекс-таблицу, можно найти оптимальный план двойственной задачи. Компоненты оптимального плана двойственной задачи совпадают с элементами m+1-й строки столбцов единичных векторов первоначального базиса, если данный коэффициент cj=0, и равны сумме соответствующего элемента этой строки и cj, если cj>0.

Пример. Для производства трех видов изделий I, II, III используется 3 вида сырья. Запасы заданы в количестве, соответственно не большем 180, 210 и 244 кг.

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

Решение. Обозначим через x1 – количество изделий I, x2 – изделий II, x3 – изделий III, запланированных к производству. Тогда нужно решить задачу

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

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

Эти задачи образуют пару двойственных задач. Эти задачи образуют пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий I, II, III, Решение двойственной - оптимальную систему оценок сырья, используемого для производства этих изделий.

Найдем решение этой задачи симплекс-методом.

Из этой таблицы видно, что оптимальным планом производства изделий I, II, III является такой, при котором изготавливается 82 изделия II и 16 изделий III и остается не использованным 80 кг сырья B, Из этой таблицы видно, что оптимальным планом производства изделий I, II, III является такой, при котором изготавливается 82 изделия II и 16 изделий III и остается не использованным 80 кг сырья B, а общая стоимость изделий равна 1340 руб. Из этой таблицы также видно, что оптимальным решением двойственной задачи является

Положительную двойственную оценку имеют те виды сырья, которые полностью используются. Переменные y1 и y3 обозначают двойственные оценки сырья видов A и C. Эти оценки отличны от нуля, и сырье видов А и С используются полностью. Двойственная оценка сырья вида В y2=0. Этот вид сырья используется не полностью.

Вычислим значение целевой функции двойственной задачи

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

Подставим значения двойственных оценок в ограничения двойственной задачи Подставим значения двойственных оценок в ограничения двойственной задачи

Первое ограничение выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия типа I, выше цены этого изделия и, следовательно, выпускать изделие I невыгодно. Первое ограничение выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия типа I, выше цены этого изделия и, следовательно, выпускать изделие I невыгодно. Второе и третье ограничения являются равенствами. Это означает, что двойственные оценки сырья, используемого на производство единицы изделий II и III равны их ценам. Поэтому выпускать изделия этих двух видов экономически целесообразно.

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