admin / 08.05.2018

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

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

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

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

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

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

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

Построение двойственной задачи (pdf, 63 Кб)

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

Построение двойственной задачи линейного программирования (pdf, 50 Кб)

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

Решение прямой и двойственной задачи ЛП (pdf, 79 Кб)

Примеры решений ЗЛП онлайн

Цели

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

Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые пере­менные могут принимать только два значения: 0 или 1. Такие пе­ременные носят название булевых.

Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. Они разработаны в на­чале 60-х годов XX века и затем неоднократно усовершенствова­лись и модифицировались. Решения примеров и задач, приводи­мых в этой главе, получены с помощью метода ветвей и границ и являются точными.

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

• неделимость;

• целочисленная задача;

• целочисленная и булева переменные;

• взаимоисключение и взаимообусловленность.

Модели

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

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

Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремаль­ным комбинаторным задачам, для решения которых приходится вводить булевы переменные, носящие логический характер (Х = 1 или Х = 0).

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

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

Итак, можно выделить следующие основные классы задач дис­кретного программирования:

1) транспортная задача (см. главу 5) и ее варианты;

2) задачи с неделимостями;

3) экстремальные комбинаторные задачи;

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

5) задачи на неклассических областях (см. модель оптимального размера заказа с количественными скидками в главе 12).

Целочисленная задача линейного программирования (задача с неделимостями). К данному классу принадлежат Задачи распре­деления капиталовложении и Задачи планирования производства.

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

(1)

При условиях

(2)

Где J — некоторое подмножество множества индексов N = ={1,2,…,N}.

Если J = N (T.

e. требование целочисленности наложено на все переменные), то задачу называют Полностью целочисленной; если же J ¹N, она называется Частично целочисленной.

Модель (1)—(4) естественно интерпретировать, например, в следующих терминах. Пусть через I = 1,…, Т обозначены произ­водственные факторы, через J = 1, …, П — виды конечной про­дукции.

Обозначим далее:

Aij — количество факторов I, необходимое для производства единицы продукта J;

Bi — наличные ресурсы фактора I;

СI — прибыль, получаемая от единицы продукта J.

Пусть продукты J для JÎJ являются неделимыми, т. е. физи­ческий смысл имеет лишь их целое неотрицательное количество («штуки»). Предположим, что требуется составить производствен­ную программу, обеспечивающую максимум суммарной прибы­ли и не выводящую за пределы данных ресурсов. Обозначая через Xj искомые объемы выпуска продукции, мы сводим эту задачу к мо­дели (1)-(4).

Задача с булевыми переменными. Логическая взаимосвязь:

1) Взаимоисключение. Пусть Xj = 1, если реализуется проект АJ, И ХJ = 0 в противном случае. Запись AjÚAk означает, что в план может быть включен либо проект АJ, либо проект АK. Вместе они включены быть не могут. С помощью этой записи выражается от­ношение взаимоисключения между проектами.

В этих обозначениях взаимоисключение Aj Ú АK выражается неравенством ХJ + ХK £ 1;

2) Взаимообусловленность. Запись АK ® Aj («проект АK влечет за собой проект АJ») означает, что проект АK может быть включен в план только в том случае, если в план включен и проект Aj. С по­мощью этой записи выражается отношение между обусловлива­ющими друг друга проектами, например когда проект Ak — резуль­тат тиражирования проекта Aj на другом объекте или когда АK ба­зируется на результатах реализации проекта Aj.

В принятых обозначениях взаимообусловленность АK ® АJ вы­ражается неравенством ХK £ ХJ.

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

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

Пусть ХIj = 1, если коммивояжер переезжает из города I непо­средственно в город J, и Xij = 0 в противном случае. Обозначим через СIj расстояние между городами I и J (чтобы избежать бессмыс­ленных значений ХIj = 1, предполагается, что СIi равны достаточно большому числу).

Тогда формальная модель имеет вид

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

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

Это ограничения вида

Где на переменные Zi и Zj не требуется накладывать никаких огра­ничений.

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

Один из представителей задач данного типа — так называемая Задача о ранце. Имеется П предметов. Предмет J (J = 1, …, П) об­ладает весом Wj и полезностью СJ. Пусть B — общий максимально допустимый вес предметов, которые можно положить в ранец. Требуется выбрать предметы таким образом, чтобы их общий вес не превышал максимально допустимый и при этом суммарная по­лезность (ценность) содержимого ранца была максимальной. Пусть ХJ = 1, если предмет положен в ранец, и ХJ = 0 в противном случае. Математическая формулировка задачи имеет вид

К классу экстремальных комбинаторных задач принадлежит также линейный и нелинейный варианты Задача о назначениях (ли­нейный вариант такой задачи рассмотрен в главе 6).

Большинство целочисленных и комбинаторных типов задач, таких, как задача с неделимостями, задача коммивояжера, задача календарного планирования, принадлежит к разряду так называ­емых Трудно решаемых. Это означает, что вычислительная слож­ность алгоритма их точного решения — зависимость числа элемен­тарных операций (операций сложения или сравнения), необходи­мых для получения точного решения, от размерности задачи я — является Экспоненциальной (порядка 2N), т. е. сравнимой по тру­доемкости с полным перебором вариантов. В качестве П, например, для задачи с неделимостями служит число целочисленных перемен­ных и число ограничений, для задачи коммивояжера — число горо­дов (или узлов графа маршрутов), для задачи календарного плани­рования — число деталей и число станков. Такие задачи называют еще NP-трудными или NP-Полными. Получение их точного ре­шения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Примером таких задач служит задача о ранце с булевыми пере­менными.

Задачи с вычислительной сложностью, определяемой Полино­миальной зависимостью от П, называются Эффективно решаемы­ми. К такого типа задачам принадлежат задачи транспортного типа и линейные задачи о назначениях.

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

1) симплекс-метод (для транспортных задач, задач о назначениях);

2) метод отсечения (метод Гомори);

3) метод ветвей и границ (в общем случае не обеспечивает получения точного решения);

4) эвристические методы (не обеспечивают получения точно­го решения).

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

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

Предыдущая1234567891011Следующая

 

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

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

Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками, или "ценами" ресурсов, или теневыми ценами.

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

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

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум – вид ³;

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

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче;

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

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства £, соответствует переменная, связанная условием неотрицательности.

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

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

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

 

 

Модель двойственной задачи имеет вид:

 

 

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

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

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

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

 

f(x) = g(y).

 

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

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

4. Обе из рассматриваемых задач имеют пустые допустимые множества.

Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции равна затратам на ресурсы по "внутренним" (определяемым только из решения задачи) ценам ресурсов yi. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов: f(X) < g(Y), т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит величина g(Y) – f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

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

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

Пусть X=(x1,x2,…xn) – допустимое решение прямой задачи, а Y= (y1,y2,…ym) – допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

 

*

**

 

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

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,…,Xn) и оптимальный вектор оценок Y=(Y1,Y2,…,Ym):

 

(4)

(5)

 

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках.

Значения переменных Yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

 

 

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

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

Пример.Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

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

 

f(x) = 3Х1 +4Х2 +3Х3 +1Х4

Ограничения по ресурсам

 


1 +2Х2 +2Х3 +6Х4 80

1 +8Х2 +4Х3 +3Х4 480

1 +4Х23 +8Х4 130

Х1, Х2, Х3, Х4 0

 

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

Y1 – двойственная оценка ресурса труд, или "цена" труда; Y2 – двойственная оценка ресурса сырье, или "цена" сырья; Y3 – двойственная оценка ресурса оборудование, или "цена" оборудования.

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

g = 80 ´Y1 + 480´Y2 + 130´Y3 ® min

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

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

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

 


7 ´Y1 + 5´Y2 + 2´Y3 ³ 3

2 ´Y1 + 8´Y2 + 4´Y3 ³ 4

2 ´Y1 + 4´Y2 + 1´Y3 ³ 3

6 ´Y1 + 3´Y2 + 8´Y3 ³ 1

Y1, Y2, Y3 ³ 0

 

Решение двойственной задачи можно найти в отчете Поиска решений. Отчет по устойчивости.

Теневые цены ресурсов труд, сырье и оборудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях 1.3333, 0, 0.3333.

 

 

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

1) Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений второй теоремы двойственности.

 

 

Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и 1/3 – эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции.

Правые части этих ограничений равны левым частям.

 

1 +2Х2 +2Х3 +6Х4 80

1 +4Х23 +8Х4 130

7´0 +2´30 +2´10 +6´0=80=80

2´0 +4´30 +1´10 +8´0=130=130

Ресурс сырье используется не полностью (280<480), поэтому имеет нулевую двойственную оценку (Y2=0).

 

1 +8Х2 +4Х3 +3Х4 480

5´0 +8´30 +4´10 +3´0=280<480

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

Общая стоимость используемых ресурсов при выпуске 30 ковров второго вида и 10 ковров третьего вида составит 150 тыс. руб.

 

g = 80 ´Y1 + 480´Y2 + 130´Y3 =80 ´4/3 +480´0+130´1/3 =150 тыс. руб.

 

По условию (4) не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его не дефицитности. Ресурс не дефицитен не из-за его неограниченных запасов (они ограничены величиной bi), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f(X).

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

2) Анализ эффективности отдельных вариантов плана выполняется на основе соотношений из 2 теоремы двойственности.

 

 

Если изделие вошло в оптимальный план (Xj >0), то в двойственных оценках оно не убыточно, то есть, стоимость ресурсов, затраченных на производство единицы изделия равна его цене.

Такие изделия эффективны, выгодны с точки зрения принятого критерия оптимальности. В нашей задаче это ковры второго и третьего видов.

Если стоимость ресурсов, затраченных на производство одного изделия больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7 (10-3) тыс. руб. и 9.666 (10.666-1) тыс. руб. соответственно. Это можно подтвердить, подставив в ограничения двойственной задачи оптимальные значения вектора Y.

7 ´4/3 + 5´0+ 2´1/3=30/3=10 >3

2 ´4/3 + 8´0+ 4´1/3=12/3= 4= 4

2 ´4/3 + 4´0+ 1´1/3= 9/3= 3= 3

6´4/3 + 3´0+ 8´1/3=32/3= 10.666 > 1

Разницу между правыми и левыми частями ограничений двойственной задачи можно найти в Отчете по устойчивости в столбце Нормируемая стоимость.

2) Анализ влияния изменения правых частей ограничений на значения целевой функции (Чувствительность решения к изменению запасов сырья).

Предположим, что запас сырья ресурса "труд" изменился на 12 единиц, т.

е. теперь он составляет 80 + 12 = 92 единиц. Из теоремы об оценках, известно, что колебание величины bi приводит к увеличению или уменьшению f(X). Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптимальном плане соответствующей двойственной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса "труд" приведет к увеличению значения целевой функции на 16 тыс. руб.(Df(x)= Db1´ y1 =12´4/3 = 16).Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться.

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

 

 

Ограничение правая часть Допустимое увеличение Допустимое уменьшение
1E+30

 

После увеличения запаса ресурса труд до 92 чел/ часов было получено новое решение задачи. Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась – изделия, которые были убыточны не вошли и в новый план выпуска, т.к. цены на ресурсы не изменились.

Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24-8=16) получено за счет уменьшения на 2 единицы ковров второго вида по цене 4 тыс. руб. (4 тыс. руб.´(28-30)= -8 тыс. руб.) и увеличения на 8 единиц ковров третьего вида по цене 3 тыс. руб. (3 тыс. руб.´(18-10)= 24 тыс. руб.).

 

Предыдущая1234567891011Следующая

Date: 2015-07-25; view: 410; Нарушение авторских прав

Понравилась страница?

Лайкни для друзей:

ПОНЯТИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

1. Если на переменную xi прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

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

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

На нашем сайте вы также можете:

Решение онлайн

Для ввода исходных данных необходимо указать количество переменных в функции:

и количество ограничений:

      НазадОглавлениеВперед

.
Условие производственной задачи:
,

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

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

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

Требуется вычислить оптимальные цены на ресурсы.

Для производства продукции первого типа требуется 6 единиц ресурсов первого типа, 2 единицы ресурса второго типа и 1 единица ресурса третьего типа (об этом говорят элементы первого столбца матрицы).

При установленных ценах затраты на единицу продукции первого типа составят:
денежных единиц.

Но за единицу продукции первого типа при продаже можно получить 48 дн.ед. Т.е. продажа ресурсов не должна быть убыточнее производства изделия и продажи его.
.

Составим аналогичные неравенства для продукции остальных типов.

При этом за все имеющиеся ресурсы можно выручить

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

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

Ранее было найдено, что



Система примет вид

Учтем, что третий ресурс был избыточным, т.к. , то . Система уравнений приняла вид:

Решим эту систему уравнений:

Итог:
Общая минимальная оценка .

Понравилась статья?

      НазадОглавлениеВперед

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*