Курсовая работа: Экономико-математические методы и прикладные модели
постав-
щиков
140
Мощности потребителей
U i
18
15
32
45
30
30
10
7
14
8/5
7/25
0
40
12
8
10
8/40
15
0
25
6/18
10/2
10
12
14/5
-7
45
16
10/13
8/32
12
16
-7
Vj
-1
7
5
8
7
Суммарные затраты:
f(x) = 6´18+10´2+10´13+8´32+8´5+8´40+7´25+14´7=1119
Положим, U1=0 Þ V4=8, V5=7; V4=U2+8 Þ U2=0
V5 = U3+14 Þ U3= 7-14= -7; V1= -7+6= -1; V2= -7+10= +3
V2=U4+10 Þ U4=3-10= -7; v3= -7+8=1
9 4 13 0 0
(dij) = 13 5 9 0 8
2 0 2 -3 0
10 0 0 -3 2
Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,4).
Наименьшая поставка в клетке со знаком “-” равна 5. Произведем перераспределение поставок результаты представим в таблице 4.
|
Мощности постав- щиков 140 | Мощности потребителей | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 | 14 | 8 | 7/30 | 0 |
| 40 | 12 | 8 | 10 | 8/40 | 15 | 0 |
| 25 | 6/18 | 10/2 | 10 | 12/5 | 14 | -4 |
| 45 | 16 | 10/13 | 8/32 | 12 | 16 | -4 |
| Vj | 2 | +6 | 4 | 8 | 7 | |
Суммарные затраты:
f(x) = 7´30+8´40+6´18+10´2+12´5+10´13+8´32=1104
U1=0 Þ V5= 7; U2=0 Þ V4=8=U3+12 Þ U3=-4 Þ
V1= 6-4=2, V2=10-4=+6=U4+10; V3= -4+8= +4
8 1 10 0 0
(dij) = 10 2 6 0 8
0 0 2 0 3
10 0 0 0 5
Матрица оценок (dij) не содержат отрицательных величин Þ данный план является оптимальным, т.к. С34 = 0, а клетка (3,4) не является запятой, то данный план не является единственным. Стоимость перевозок по этому плану, как было рассчитано ранее, равна f(x) = 1104.
3.6. Симплекс-метод решения задач линейного программирования.
Симплекс-метод позволяет отказаться от метода перебора при решении задач линейной оптимизации, является основным численным методом решения задач линейного программирования и позволяет за меньшее число шагов, чем в методе перебора, получить решение.