Пиши Дома Нужные Работы

Обратная связь

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

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

Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов.
Ранее рассмотрена задача об использовании ресурсов (экономико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1). В приведенной модели bi (i = 1, 2, ..., m) обозначает запас ресурса Si , aij - число единиц ресурса Si потребляемого при производстве единицы продукции Pj(j = 1, 2, ..., n); Cj - прибыль (выручка) от реализации единицы продукции Pj (или цена продукции Pj).
Предположим, что некоторая организация решила закупить ресурсы S1, S2, ..., Sm предприятия и необходимо установить оптимальные цены на эти ресурсы у1, у2, ..., ym
Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b1, b2, ..., bm по ценам соответственно у1, у2, ..., ymбыли минимальны, т.е
Z=b1у1 + b2 у2 +...+ bm уm min .
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции Р1 расходуется a11 единиц ресурса S1, a21 единиц ресурса S2, ..., ai1единиц ресурса Si ..., аm1 единиц ресурса Sm по цене соответственно у1, у2, ..., уi ..., ym. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции Р1 должны быть не менее ее цены c1, т.е. a11 у1+ a21 у2+:+am1 уm>=c1
Аналогично можно составить ограничения в виде неравенств по каждому виду продукции Р1, Р2, ..., Рm. Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи II приведены в правой части табл. 6.1.



Задача I (исходная) Задача II (двойственная)
F=c1x1+c2x 2+...+cnxn max (6.1) при ограничениях a11x1 + a12x2+...+ a1nxn <= b1 a21x1 + a22x2+...+ a 2nxn <= b2 (6.2) am1x1 + am2x2+...+ amnxn <= bm и условии неотрицательности x1>= 0; x2>= 0;: xn>= 0 Составить такой план выпуска продукции Х = 1, х2, ..., хn), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов. Z=b1y1+b2y2+...+bm ym min (6.4) при ограничениях a11у1 + a21у2+...+ am1уm >= c1 a12у1 + a22у2+...+ am2уm >= c2 (6.5) a1nу1 + a2nу2+...+ amnуm >= cn и условии неотрицательности. y1>= 0; y2>= 0;: ym>= 0 Найти такой набор цен (оценок) ресурсов Y = 1, y2, ..., уm), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

Цены ресурсов у1, у2, ..., уm в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что этоусловные, "ненастоящие" цены. В отличие от "внешних" цен c1, с2, ..., cn на продукцию, известных, как правило, до начала производства, цены ресурсов у1, у2, ..., уnявляются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

 

 

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

Математические модели этих задач имеют следующий вид.

 

прямая задача: Zmax= , где i =1, 2, …, m, j =1, 2, …, n, xi ≥ 0   двойственная задача: Zmin= , где i =1, 2, …, m, j =1, 2, …, n, xi ≥ 0

 

 

Эти задачи экономически могут быть сформулированы следующим образом.

 

Прямая задача:сколько и какой продукции хi(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.

Двойственная задача:какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аij минимизировать общую оценку затрат на все ресурсы.

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

1.Если прямая задача решается на максимум, то двойственная задача решается на минимум; если прямая задача решается на минимум то двойственная на максимум;

2.В задаче на максимум ограничения неравенства имеют вид – ≤, а в задаче на минимум – ³;

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

4.Матрица системы ограничений двойственной задачей получается из матрицы из матрицы систем ограничений прямой задачи транспонированием;

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

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

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

 

 

Пример:

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

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

Взаимосвязь решений прямой и двойственной задач находится из трех теорем двойственности.

 

3. 3 Теоремы двойственности.

 

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

Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

 

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

 

 

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

Вторая теорема двойственности:

 

Для того чтобы план Х* и Y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

 

 

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

 

 

если < bj, то ;

 

если > 0, то .

 

Аналогично,

если > ;

если >0 то .

 

Экономически это означает, что если по некоторому оптимальному плану X*= производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.

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

 

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

 

В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:

,

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

 

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

геометрическим методом

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

 

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

 

Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор gradZ на плоскости Х2ОХ2 .

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2019 pdnr.ru Все права принадлежат авторам размещенных материалов.