2018-02-13
657
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Им. Н.И. ЛОБАЧЕВСКОГО
В.А. Рябинин
Послеоптимизационный анализ задач линейного программирования
Лабораторная работа №4
Вариант №18
Нижний Новгород
2005
1. Анализ чувствительности оптимального решения задачи к изменению свободных членов ограничений.
Фирма А выпускает изделия Х и поставляет их по договорным обязательствам фирме В ежемесячно в количестве 1000 шт. Каждое изделие состоит из двух деталей У и трех деталей Z. Детали У и Z можно купить в фирме С по цене соответственно 2 руб. и 1 руб. за шт. в объеме не более 800 и 1000 в месяц.
Детали можно также изготовить из заготовок U и V, закупаемых в фирме D по цене 4 и 7 руб. Из каждой заготовки U фирма Е за 2 руб. может изготовить 3 детали У и 1 деталь Z, а из заготовки V за 5 руб. – 3 детали У и 5 деталей Z, за 3 руб. – 5 деталей У и 2 детали Z.
Определить месячный план деятельности фирмы А, обеспечивающий выполнение договорных обязательств с минимальными затратами.
|
|
|
Обозначим за x1 - количество планируемых закупок деталей Y, в фирме C [шт] по 2 руб.
за x2 - количество планируемых закупок деталей Z, в фирме C [шт] по 1 руб.
за x3 - количество купленных деталей U, в фирме D [шт] по 4 руб. и преобразованные в 3Y и 1Z в фирме E за 2 руб.
за x4 - количество купленных деталей V, в фирме D [шт] по 7 руб. и преобразованные в 3Y и 5Z в фирме E за 5 руб.
за x5 - количество купленных деталей V, в фирме D [шт] по 7 руб. и преобразованные в 5Y и 2Z в фирме E за 3 руб.
Ограничения по закупкам в фирме C запишутся так:
x1≤800 (1)
x2≤1000 (2)
Ограничение по количеству необходимых деталей Y
x1+3*x3+3*x4+5*x5=2000 (3)
Ограничение по количеству необходимых деталей Z
x2+x3+5*x4+2*x5=3000 (4)
Запишем полученную систему:
 |
x1≤800
x2≤1000 (5)
x1+3*x3+3*x4+5*x5=2000
x2+x3+5*x4+2*x5=3000
xi≥0, i=1..5
Оптимизационным критерием F будут затраты, которые необходимо минимизировать:
F=2*x1+x2+6*x3+12*x4+10*x5→min (6)
Тогда решением будет вектор x*(x1,x2, x3,x4,x5), если на нем достигается минимальное значение критерия F.
Запишем систему (5) в каноническом виде:
x1+x6=800
x2+x7=1000 (7)
x1+3*x3+3*x4+5*x5=2000
x2+x3+5*x4+2*x5=3000
xi≥0, i=1..7
Решим задачу методом искусственного базиса. Для этого составим вспомогательную задачу:
F=x8+x9→min
x1+x6=800
x2+x7=1000 (8)
x1+3*x3+3*x4+5*x5+x8=2000
x2+x3+5*x4+2*x5+x9=3000
xi≥0, i=1..9
Решим методом искусственного базиса:
Оптимальная симплекс таблица:
|
| 2 | 1 | 6 | 12 | 10 | M | M | ||||
| Cb | БП | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | b |
| 0 1 10 12 | x6 x2 x5 x4 | 1 0 0.2631 -0.105 | 0 1 0 0 | 0 0 0.6315 -0.052 | 0 0 0 1 | 0 0 1 0 | 1 0 0 0 | 0 1 0.1578 -0.263 | 0 0 0.2631 -0.105 | 0 0 -0.157 0.2631 | 800 1000 210.526 315.789 |
| ƒ | -0.631 | 0 | -0.315 | 0 | 0 | 0 | -0.578 | 1.368 -M | 1.578 -M | 6894.73 | |
|
|
|
Экономическая интерпретация:
Необходимо купить 1000 деталей Z в фирме C по 1 руб.;
315.789 деталей V в фирме D по 7 руб. и изготовить из каждой по 3 детали Y и 5 детали Z за 5 руб. в фирме E;
210.516 деталей V в фирме D по 7 руб. и изготовить из каждой по 5 деталей Y и 2 детали Z за 3 руб. в фирме E;
Минимальные затраты:
1000[шт]*1[руб]+315.789[шт]*12[руб]+ 210.516 шт]*10[руб]= =6894.73[руб]
Двойственные оценки:
y*=(0; 0.578947; 1.36842; 1.57894)
Теперь найдём устойчивости двойственных оценок – область, в которой при изменении свободных членов ограничений двойственные оценки не меняются. Неизменность двойственных оценок говорит о том, что не меняют своих номеров базисные и свободные переменные в решении.
Изначально мы учитывали изменение знаков неравенств (1) и (2), но знаки самих неравенств не меняли. Сейчас мы также не будем менять знаки первого и второго неравенств, но примем во внимание обратный знак Δb1,2 при расчёте конкретных значений.
Пусть свободные члены ограничений изменились на Δb1, Δb2, Δb3, Δb4 соответственно. Тогда оптимальное решение новой задачи будет находиться так:
X’B=B-1*b’=B-1*b+B-1*Δb=XB+B-1*Δb
Базисное решение вычисляется через матрицу, обратную к базисной, и свободные члены ограничений. Из оптимальной симплекс-таблицы получим матрицу, обратную к базисной, и оптимальное решение (базисные компоненты):
| 800 |
| 1000 |
| 210.526 |
| 315.789 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0.1578 | 0.2631 | -0.157 |
| 0 | -0.263 | -0.105 | 0.2631 |
| Δb1 |
| Δb2 |
| Δb3 |
| Δb4 |
|
|
X6=800+Δb1>0
X2=1000+ Δb2>0 (9)
X5=210.526+ 0.1578*Δb2+0.2631* Δb3-0.157* Δb4>0
X4=315.789- 0.2631*Δb2-0.105* Δb3+0.2631* Δb4>0
Все элементы решения должны быть неотрицательны, иначе решение будет недопустимым, т.е. базисное решение остаётся оптимальным до тех пор, пока оно допустимое. Область устойчивости следующая:
800+Δb1>0
1000+ Δb2>0 (10)
210.526+ 0.1578*Δb2+0.2631* Δb3-0.157* Δb4>0
315.789- 0.2631*Δb2-0.105* Δb3+0.2631* Δb4>0
Интервалы устойчивости:
1) Δb1≠0; Δb2= Δb3= Δb4=0
800+Δb1>0
1000>0 => Δb1Є[-800;∞] b1Є[0;∞]
210.526 >0
315.789 >0
2) Δb2≠0; Δb1= Δb3= Δb4=0
800>0
1000+ Δb2>0 => Δb2Є[-1000;1200,2623]
210.526+ 0.1578*Δb2 >0 b2Є[0;2200,2623]
315.789- 0.2631*Δb2 >0
3) Δb3≠0; Δb1= Δb2= Δb4=0
800>0
1000>0 => Δb3Є[-800,1748;3007,5143]
210.526+ 0.2631* Δb3 >0 b3Є[1199,8252; 5007,5143]
315.789-0.105* Δb3 >0
4) Δb4≠0; Δb1= Δb2= Δb3=0
800 >0
1000 >0 => Δb4Є[-1200,2623;1340,9299]
210.526 -0.157* Δb4>0 b4Є[1799,7377; 4340,9299]
315.789+0.2631* Δb4>0
Экономический смысл:
При данных изменениях ресурсов двойственные оценки не изменятся, а значит и номера базисных переменных также не изменятся:
1) При изменении количества запасов деталей Y в фирме С от 0 до бесконечно больших запасов.
2) При изменении запасов фирмы C деталей Z от 0 до 2200,2623
3) При изменении норм производства одной детали X из от 1,1998 до 5,0075 деталей Y и от 1,7997 до 4,3409 деталей Z
4) Изменение обязательств перед фирмой B от 599,9126 до 1446,9766 деталей X
Изобразим область устойчивости двойственных оценок к изменению свободных членов ограничений графически. Для этого, исходя из экономических соображений и наглядности графика, построим его в координатах Δb1, Δb2, т.е. Δb3= Δb4=0
800+Δb1>0 (11)
1000+ Δb2>0 (12)
210.526+ 0.1578*Δb2 >0 (13)
315.789- 0.2631*Δb2 >0 (14)
Пример практического применения интервалов устойчивости.
Изменим условие задачи:
