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

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

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

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

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

Переменные двоякой задачки yi именуют беспристрастно обусловленными оценками, либо двоякими оцен­ками, либо «ценами» ресурсов Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений, либо теневыми ценами.

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

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

1) мотивированная функция начальной задачки формули­руется на максимум, а мотивированная функция двоякой задачки— на минимум, при всем этом в задачке на максимум все неравенства в многофункциональных ограничениях имеют вид , в Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений задачке на минимум — вид ;

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

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

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

5) каждому ограничению одной задачки соответствует переменная другой задачки: номер переменной совпадает с номером Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений ограничения; при всем этом ограничению, записан­ному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функцио­нальное ограничение начальной задачки является равенст­вом, то соответственная переменная двойственнвой; задачки может принимать Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений как положительные, так и отрицательные значения

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





Модель двоякой задачки имеет вид:




Две приведенные задачки образуют пару симметричных двояких задач. Главные утверждения о Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений взаимно двояких задачках содержатся в 2-ух последующих аксиомах.

1-ая аксиома двойственности.

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

1. В прямой и двоякой задачках имеются рациональные реше­ния Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений, при всем этом значения мотивированных функций на хороших решениях совпадают: f(x) = g(y).

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

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

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


Экономический смысл первой аксиомы двойственности последующий. План производства Х и набор оценок ресурсов У оказываются Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений хорошими и тогда только тогда, когда прибыль от реализации продукции, определенная, при из­вестных заблаговременно ценах продукции равна затра­там на ресурсы по «внутренним» (определяемым только из решения задачки) ценам ресурсов yi. Для Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (либо равна) цены затраченных ресурсов:

f(X) < g(Y}, т. е. ценность всей выпущенной продукции не превосходит Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений суммарной оценки имеющихся ресурсов. Зна­чит величина g(Y) - f(X) охарактеризовывает производственные утраты зависимо от рассматриваемой производственной программки и избранных Оценок ресурсов.

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


2-ая аксиома двойственности

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

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

*

**


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

Из 2-ой аксиомы двойственности в этом случае следуют такие требования на лучшую производственную программку 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

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

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

5Х1 +8Х2 +4Х3 +3Х4480

2Х Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений1 +4Х2 +Х3 +8Х4130

Х1, Х2, Х3, Х40


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

Y1 – двоякая оценка ресурса труд, либо «цена» труда;

Y2 – двоякая оценка ресурса сырье, либо «цена» сырья;


Y3 – двоякая оценка ресурса оборудование, либо «цена» оборудования.

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

g = 80 Y1 + 480Y2 + 130Y3  min

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

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


7 Y Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений1 + 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.



Отчет по стойкости













Изменяемые ячейки

























Результ.

Нормир.

Мотивированной

Допустимое

Допустимое




Ячейка

Имя

Значение

Цена

Коэффициент

Повышение

Уменьшение




$B$3

Значение Х1

0

-7

3

7

1E+30




$C$3

Значение Х2

30

0

4

8

1




$D$3

Значение Х3

10

0

3

1

1.75




$E$3

Значение Х4

0

-9.667

1

9.667

1E+30

Ограничения

























Результ.

Теневая

Ограничение

Допустимое

Допустимое




Ячейка

Имя

Значение

Стоимость

Правая часть

Повышение

Уменьшение




$F$7

труд левая часть

80

1.333

80

150

15




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

сырье левая часть

280

0

480

1E+30

200




$F$9

Оборудование левая часть

130

0.333

130

30

90

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

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



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

7Х Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений1 +2Х2 +2Х3 +6Х4 80

2Х1 +4Х2 +Х3 +8Х4130

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

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

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

5Х1 +8Х2 +4Х3 +3Х4480

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), то в двояких оценках оно не убыточно, другими словами, цена Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений ресурсов, затраченных на создание единицы изделия равна его стоимости. Такие изделия эффективны, прибыльны исходя из убеждений принятого аспекта оптимальности. В нашей задачке это ковры второго и третьего видов.

Если цена Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений ресурсов, затраченных на создание 1-го изделия больше его цены, то это изделие не войдет в лучший план из-за его убыточности. В нашей задачке в план выпуска не вошли ковры первого и Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений 4-ого видов, так как издержки по ним превосходят стоимость на 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

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

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

Представим, что припас сырья ресурса «труд» поменялся на 12 единиц, т. е. сейчас он составляет 80 + 12 = 92 единиц. Из аксиомы об оценках, понятно, что колеба­ние величины bi приводит к повышению либо уменьшению f(X Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений). Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптималь­ном плане соответственной двоякой задачки остаются постоянными. В нашей задачке повышение припасов ресурса «труд» приведет к повышению значения мотивированной Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений функции на 16 тыс. руб.(f(x)=  b1 y1 =124/3 = 16). Для двояких оценок рационального плана очень существенное значение имеет их предельный нрав. Четкой мерой воздействия ограничений на функционал оцен­ки являются только Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений при малом приращении ограничения. Понятно, что оценки не меняют собственной величины, если не изменяется набор векторов, входящих в базис рационального плана, тогда как интенсивность этих векторов (значения неиз­вестных) в плане Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений могут изменяться.

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

Ограничение

Допустимое

Допустимое

правая часть

Повышение

уменьшение

80

150

15

480

1E+30

200

130

30

90


После роста припаса ресурса труд до 92 чел/ часов было получено новое решение задачки. Изменение припасов ресурсов в границах интервалов стойкости двояких оценок привело не Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений только лишь к изменению значения мотивированной функции на 16 тыс. руб., да и к изменению плана выпуска. При всем этом структура плана не поменялась - изделия, которые были убыточны не вошли Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений и в новый план выпуска, т.к. цены на ресурсы не поменялись. Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей цены продукции на 16 тыс. руб. (24-8=16) получено за счет уменьшения Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений на 2 единицы ковров второго вида по стоимости 4 тыс. руб. (4 тыс. руб.(28-30)= -8 тыс. руб.) и роста на 8 единиц ковров третьего вида по стоимости 3 тыс. руб. (3 тыс. руб.(18-10)= 24 тыс. руб.).


^ Отчет по стойкости 2













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

























Результ.

Нормир.

Мотивированной

Допустимое

Допустимое




Ячейка

Имя

значение

Цена

коэффициент

повышение

уменьшение




$B$3

значение Х1

0

-7

3

7

1E+30




$C$3

значение Х2

28

0

4

8

1




$D$3

значение Х3

18

0

3

1

1.75




$E$3

значение Х4

0

-9.667

1

9.667

1E+30

Ограничения

























Результ.

Теневая

Ограничение

Допустимое

Допустимое




Ячейка

Имя

значение

стоимость

правая часть

повышение

уменьшение




$F$7

труд левая часть

92

1.333

92

138

27




$F$8

сырье левая часть

296

0

480

1E+30

184




$F$9

оборудование левая часть

130

0.333

130

54

84


Задачка 5.

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

в планируемом периоде нужно обеспечить создание 300 тыс. однородных новых изделий, которые могут выпускаться на 4 филиалах предприятия. Для освоения этого нового вида изделий выделены серьезные вложения в размере 18 млн. руб Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений.. Разработанные для каждого филиала предприятия проекты освоения нового вида изделия характеризуются величинами удельных серьезных вложений и себестоимостью единицы продукции в согласовании с таблицей.

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

Таблица

Показатель

Филиал предприятия




1

2

3

4

Себестоимость производства изделия, руб.

83

89

95

98

Удельные финансовложения, руб.

120

80

90

40


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

Филиал предприятия

1

2

3

4

0

100 тыс. штук

200 тыс. штук

0


Требуется:

  1. Сконструировать экономико-математическую модель прямой и двоякой задачки.

  2. Отыскать лучший план двоякой задачки, используя аксиомы двойственности.



Решение
1) Экономико-математическая модель начальной задачки.

Xi - объем выпускаемой продукции на i Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений-м филиале предприятия.

= 83X1+89X2+95X3+98X4 -> min,

Ограничения

X1+X2+X3+X4  300 (тыс. штук)

120X1+80X2+50X3+40X4  18 (млн.руб.),

X1,2,3,4 0.





83

89

95

98




Y1

1

1

1

1

300000

Y2

120

80

50

40

18000000


^ Экономико-математическая модель двоякой задачки.


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

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

g =300000 Y1+18000000 Y2 -> mах

1 Y1+120Y2  83

1 Y1+ 80Y2  89

1 Y1+ 50Y2  95

1 Y1+ 40Y2  98


2) для определения рационального Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений плана двоякой задачки воспользуемся соотношениями 2-ой аксиомы двойственности. Если какое-либо ограничение начальной задачки производится как серьезное неравенство, то соответственная двоякая оценка равна нулю

().

0+100000+200000+0 = 300000

1200+80100000+50200000+40 = 18000000

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

).

В нашей задачке Х2=100000>0 и Х3=200000>0, потому 2-ое и третье ограничения двоякой задачки обращаются в уравнения, решая которые найдем Y1и Y2 .

1 Y Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений1+ 50Y2 = 95 Y1= 105 - средняя стоимость изделия

1 Y1+ 80Y2 = 89 Y2 = - 0.2 - двоякая оценка серьезных вложений.


105 =95 +50 0.2 = 105

105 =89+ 800.2 = 105

На втором и 3-ем филиалах выпускать новые изделия целенаправлено потому что издержки на его освоение и выпуск Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений не превосходят стоимость изделия.

Проверим выполнение первой аксиомы двойственности.

g =300000 Y1+18000000 Y2 = 300000 105+18000000(–0.2) = 279 000 000

= 83X1+89X2+95X3+98X4 =830+89100000+95200000+980 = 279 000 000.

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

1 Y1+ 120Y2 = 83 Y1= 105 105+ 120(-0.2) < 95 105< 95+24 = 119

1 Y1+ 40Y2 = 98 Y2 = - 0.2 105+ 40(-0.2) < 89 105<98+8 = 106.



dvorcovie-perevoroti-osnovnie-geroi-dati-i-sobitiya.html
dvorcovo-parkovie-prigorodi-sankt-peterburga-raspolozheni-na-yuzhnom-poberezhe-finskogo-zaliva.html
dvorec-carya-sargona-ii-v-dur-sharrukine-shedu.html