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

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

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

 

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

В некоторых случаях анализ дает больше информации для принятия решения, чем само решение.

Задача 3.47 стр 95 Для изготовления обуви 4-х моделей на фабрике используется два сорта кожи. Ресурсы рабочей силы и материала, затраты труда и материала для изготовления каждой пары обуви, а также прибыль от реализации единицы продукции приведены в таблице. Составить план выпуска обуви, максимизируюший прибыль.

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

Пусть х1, х2, х3, х4 – количество пар обуви 1,2,3,4 моделей соответственно, которые нужно изготовить.

         f = 2х1+ 40х2 +10х3 +15х4 mах

х1 + 2х2+ 2х3 + х4 ≤ 1000

2х1+  х2  ≤ 5000                   

х2+ 4х3 + х4 ≤ 1200.

              хj 0, (j=

 

БП	1	СП
		- х1	- х2	- х3	- х4
х5 =	1000	1	2	2	1
х6 =	5000	2	1	0	0
х7 =	1200	0	1	4	1
f =	0	-2	-40	-10	-15

БП	1	СП
		- х1	- х5	- х3	- х4
х2 =	500	½	½	1	½
х6 =	4500	3/2	-1/2	-1	-1/2
х7 =	700	-1/2	-1/2	3	½
f =	20000	18	20	30	5

 

 

 

 

 

 

   ………

 

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

Базисные переменные = остаток ресурсов = запас – расходы.

Ответ: X* (0;500;0;0;0;4500;700), fmax = 20000 д.ед.  Максимальная прибыль составляет 20000 д.ед. Необходимо изготавливать 500 пар обуви модели №2, а обувь других моделей изготавливать не нужно. При этом ресурс (кожа 2-го сорта) останется в объеме 700 единиц, кожа первого сорта в объеме 4500 единиц, а рабочее время  израсходовано полностью.

 

Составим двойственную задачу к исходной ЗЛП.

φ= 1000у1  + 5000у2 + 1200у3→min     (условие минимальной стоимости всех запасов                 

у1 +2у2 ≥ 2                                            ресурсов)

2у1 + у2 + у3 ≥ 40

2у1 +4 у3 ≥ 10 оценка ресурсов, затраченных на выпуск единицы готовой

у1  + у3 ≥ 15 продукции, не меньше оценки единицы готовой продукции.

уi 0, (i=

у1, у2, у3 – оценки ресурсов, теневые цены.

Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

Основная теорема двойственности Т.к. исходная задача разрешима, то и двойственная задача будет иметь оптимальный план (находящийся в последней симплексной таблице решенной задачи). При этом экстремальные значения целевых функций совпадают, т.е. fmax=φmin.

Составим соответствие между переменными для канонической формы записи

СП (количество)	БП (остатки ресурсов)
х1    х2    х3    х4            у4      у5    у6    у7	х5    х6    х7                  у1  у2      у3
БП (мера убыточности продукции)	СП (оценки ресурсов)

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

                             φmin=20000,       * (20;0;0;18;0;30;5)

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

Второе свойство двойственных оценок: (степень дефицитности ресурсов)

 

* (20;0;0;18;0;30;5)

Дефицитные ресурсы                                  Избыточные ресурсы

(будут израсходованы  полностью)                       (будут израсходованы не полностью)

 

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

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

Используя, т. о дополняющей нежёсткости: Если какая-то переменная хj* оптимального плана положительна, то j-е ограничение двойственной задачи ее оптимальным планом обращается в строгое равенство. Если оптимальное решение исходной задачи обращает какое-то i-тое ограничение в строгое неравенство, то в оптимальном плане двойственной задачи переменная  yi =0.

 

Подставим оптимальные двойственные оценки в систему ограничений:

 

        20>2   - затраты выше стоимости продукции (теневая цена > рыночной)

        40=40 - внутренние затраты на производство продукции поглощены  в стоимости г.пр

        40>10

        20>15 -   затраты выше стоимости готовой  продукции

 

(18, 0, 30, 5) – мера  убыточности данной продукции, которая  показывает величину изменения  целевой функции при введении  дополнительной единицы хi.

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

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

у

(i= ),       = 1*20=20.

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

 

Пределы чувствительности

                       Нахождение интервалов устойчивости  двойственных оценок.

 

 

 – нижний предел уменьшения

 – верхний  предел увеличения.

 

dij берутся из матрицы, которая находится в последней симплексной таблице ( столбцы базисных переменных).

 

Рассчитаем пределы устойчивости для первого ресурса:

 – нижний предел уменьшения = 1000

 – верхний  предел увеличения = 1400

Таким образом, 1-ый запас может быть уменьшен на 1000 или увеличен на 1400. Интервал изменения [0; 2400].

Второй и третий ресурс не имеют верхних границ, так как используются не полностью.