Методы оптимальных решений

Компоненты оптимального решения  ПЗЛП
План производства			Остатки ресурсов, единиц
Превышение затрат на ресурсы над  ценой реализации (возможный убыток от производства продукции)			Объективно обусловленные оценки ресурсов (теневые, условные, скрытые  цены ресурсов)
Компоненты оптимального решения  ДЗЛП

 

Экономический смысл переменных:

x₁^*, x₂^*, x₃^* -основные переменные - оптимальный план производства;

x₄^*, x₅, x₆^* - дополнительные переменные - остатки ресурсов;

y₁, y₂, y₃ -основные переменные - скрытые цены;

y₄, y₅, y₆ -дополнительные переменны – превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции).

Наличие пары нулевых  переменных x₄^* = 0 и y₁ = 0 свидетельствует, что двойственная задача имеет альтернативные решения.

Анализ решения ПЗЛП

Подставим оптимальные  значения переменных x^* в исходную систему ограничений ПЗЛП:

1) 3×х₁ + х₂ + 2×х₃ £ 30

3×0 + 1.5 + 2×5 =10

10 < 30, следовательно, х₄ = 20, ресурс Р₁ не используется полностью;

2) 2×х₁ + 3×х₂ + 4х₃ £ 20

2×0 + 3×0 + 4×5 = 20

20=20, следовательно, х₅ = 0, ресурс Р₂ используется полностью;

3) х₁ + 2х₂ + 6×х₃ £ 52

0.1 + 2.5 + 6×0 =30

30<50, следовательно, х₆ = -5/2, ресурс Р₃ не используется полностью.

Анализ решения ДЗЛП

Подставим оптимальные  значения переменных у^* в исходную систему ограничений ПЗЛП:

1) 3×у₁ + 2×у₂ + у₃ ³ 4

3×0 + 2×2 + 0 = 4

4=4,  следовательно, у₄ = 0, убытки от производства первого вида продукции П₁, которая вошла в оптимальный план производства, , в случае ее производства будут составлять 0 ден. ед. с каждого изделия первого вида.

2) у₁ + 3.у₂ + у₃ ³ 6

3×0 + 3.2 + 1.0 = 6

6=6, следовательно, у₅ = 0, убытки от производства второго вида продукции П₂, которая вошла в оптимальный план производства отсутствуют;

3) 2×у₁ + 4у₂ + 6×у₃ ³ 1

2×0 + 4.2 +6.0= 8

8=8, следовательно, у₆ = 0, убытки от производства третьего вида продукции П₃, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 0 ден. ед. с каждого изделия третьего вида.

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

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

В рассматриваемом случае ресурс P1 используется полностью, следовательно, являются дефицитным, а ресурс P2 и ресурс P3 остаются – соответственно P2 и P3 недефицитными.

Для исследования границ изменения первого вида ресурса  Р₁ из последней симплекс-таблицы составляют систему неравенств для базисных переменных ПЗЛП, используя элементы из столбца свободных членов b_i и столбца, соответствующего переменной у₁. Коэффициенты из столбца «у₁» умножают на искомое изменение Db₁ запаса ресурса Р₁:

 Þ .

Учитывая, что b₁ = 30, допустимый интервал изменения границ первого вида ресурса составит .

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

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

В рассматриваемом случае х₂ = 0, х₆ = 22 недефицитных ресурсов.

Аналогично, определяем допустимый интервал изменения границ второго вида ресурса Р₂:

 Þ   .

Учитывая, что b₂ = 20, допустимый интервал изменения границ второго вида ресурса составит или .

Аналогично, определяем допустимый интервал изменения границ третьего вида ресурса Р₃:

 Þ    .

Учитывая, что b₃ =52, допустимый интервал изменения границ третьего вида ресурса составит или .

6. Расчет границ изменения цены изделия, попавших в оптимальный план производства, в пределах которых оптимальный план не изменится

В план производства вошли  первый и второй виды продукции П₂.

. Þ Þ .

Учитывая цену первого  вида продукции с₂ = 6, интервал устойчивости изменения цен составит .

7. Определение величины ∆b_s ресурса Р_s, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства ∆b_r единиц ресурса Р_r

 

В рассматриваемом случае: r = 2; ∆b_r = 2; s = 3.

Для взаимозаменяемых ресурсов (коэффициент взаимозаменяемости >0, но отличен от бесконечности) количество ресурса ∆b_i вида i, необходимое для замены выбывающего количества ∆b_k ресурса k, определяется по формуле:

.

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

 8. Оценка целесообразности приобретения ∆b_k единиц ресурса Р_k по цене с_k за единицу

В рассматриваемом случае: ∆b_k = 0,5; k = 1, c_k = 12.

Поскольку < 12, то приобретение дополнительного количества ресурса не целесообразно.

9. Оценка целесообразности выпуска нового изделия П₄, на единицу которого ресурсы Р₁, Р₂, Р₃ расходуются в количествах a₁₄, a₂₄, a₃₄ единиц, а цена единицы изделия составляет с₄ денежных единиц

Расчет затрат осуществим по формуле

 ден. ед.

Учитывая, что затраты на ресурсы для производства продукции третьего вида меньше цены реализации с₄ = 60 ден. ед., то включение ее в план производства целесообразно.

 

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

 

 

 

 

\

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Б. Двойственный симплекс-метод

 

1. Выражение базисных  переменных ПЗЛП и ДЗЛП через  свободные.

Выразим базисные переменные ПЗЛП и ДЗЛП через свободные:

 

2.Определение исходного  решения прямой и двойственной  задач и проверка его на оптимальность.

Симплексная таблица  двойственного симплекс-метода имеет  следующий вид:

	yбаз	y4	y5	y6
yсв	xсв xбаз	- x1	- x2	- x3	bi
y1	x4	3          6	1           -1	2            2	30        70
y2	x5	2         2	“3”           1	4           4	20        20
y3	x6	1          -1	2          -2	6          10	52         116
cj		-4         0	-6        6	-8          0	0         120

 

= (0;0;0;70;20;116),  = 120.

= (0;0;0;0;6;0),   = 120.

 

 

	yбаз	y4	y2	y6
yсв	xсв xбаз	- x1	- x5	- x3	bi
y1	x4	2              -2	-1/3        -8/9	2/3       -20/9	70/3      100/9
y5	x2	“2/3”        1	1/3        1/3	4/3         4/3	20/3        20/3
y3	x6	-1/3        1/3	-2/3       -1/3	10/3       14/9	116/3      252/9
cj		0        0	2        4/3	0        0	40       80/3

= (0;20/3;0;100;0;252/9),  = 80/3.

          _{= (0;4/3;0;0;0;0),  = 80/3.}

 

 

	yбаз	y5	y2	y6
yсв	xсв xбаз	- x2	- x5	- x3	bi
y1	x4	-3	-4/3	-10/3	50/3
y4	x1	1/2	1/2	2	10
y3	x6	1/2	-1/2	7/3	42
cj		0	2	0	40

        

         _{= (10;0;0;50/3;0;42), = 40.}

          _{= (0;2;0;0;0;0),  = 40.}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Транспортная задача.

Имеется 4 оптовых склада и 4 магазина.

A₁, A₂, A₃ , A₄ – склады.

a₁ = 21, a₂ = 19, a₃ = 15, a₄ =25 – соответственно, запасы на складах.

 

B₁, B₂, B₃, B₄ – магазины.

b₁ = 15,  b₂ = 15, b₃ = 25,  b₄ = 25, - соответственно, потребности магазинов.

 

Bj

B1

B2

B3

B4

Ai

bj ai

b1=15

b2=15

b3=25

b4=25

A1

a1=21

x11

30

x12

24

x13

11

x14

12

A2

a2=19

x21

26

x22

4

x23

29

x24

20

A3

a3=15

x31

27

x32

14

x33

14

x34

10

A4

a4=25

x41

6

x42

14

x43

28

x44

8