|
|
транспортная задача. Решение Рассмотрим неравенство 1 системы ограничений. 3 x 1 2 x 2 6 Построим прямую 3 x 1 2 x 2 6
ШАГ №1.
Выберем ячейку A5B5, ее оценка отрицательная
Поставщик
|
Потребитель
|
Запас
|
B1
|
B2
|
B3
|
B4
|
B5
|
A1
|
13
|
23
8
|
12
|
9
|
10
|
23
|
A2
|
12
3
|
13
|
13
|
11
|
29
2
|
41
|
A3
|
15
|
7
|
13
|
28
6
|
7
|
28
|
A4
|
18
6
|
10
|
19
10
|
14
|
6
|
37
|
A5
|
7
|
22
9
|
13
12
|
6
10
|
-3
4
|
41
|
Потребность
|
30
|
45
|
32
|
34
|
29
|
|
13 = min { 13, 18, 29 }
Поставщик
|
Потребитель
|
Запас
|
|
B 1
|
B 2
|
B 3
|
B 4
|
B 5
|
|
A1
|
13
|
23
8
|
12
|
9
|
10
|
23
|
|
A2
|
12
3
|
13
|
13
|
11
|
29
2
|
41
|
|
A3
|
15
|
7
|
13
|
28
6
|
7
|
28
|
|
A 4
|
18
6
|
10
|
19
10
|
14
|
6
|
37
|
|
A 5
|
7
|
22
9
|
13
12
|
6
10
|
-3
4
|
41
|
|
Потребность
|
30
|
45
|
32
|
34
|
29
|
|
|
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
4 * 13 - 12 * 13 + 10 * 13 - 6 * 13 + 3 * 13 - 2 * 13 = ( 4 - 12 + 10 - 6 + 3 - 2 ) * 13 = -3 * 13 ден. ед.
Поставщик
|
Потребитель
|
Запас
|
B 1
|
B 2
|
B 3
|
B 4
|
B 5
|
A 1
|
13
|
23
8
|
12
|
9
|
10
|
23
|
A 2
|
12 + 13
3
|
13
|
13
|
11
|
29 - 13
2
|
41
|
A 3
|
15
|
7
|
13
|
28
6
|
7
|
28
|
A 4
|
18 - 13
6
|
10
|
19 + 13
10
|
14
|
6
|
37
|
A 5
|
7
|
22
9
|
13 - 13
12
|
6
10
|
+13
-3
4
|
41
|
Потребность
|
30
|
45
|
32
|
34
|
29
|
|
Получили новое решение. ?
Поставщик
|
Потребитель
|
Запас
|
B 1
|
B 2
|
B 3
|
B 4
|
B 5
|
A 1
|
13
|
23
8
|
12
|
9
|
10
|
23
|
A 2
|
25
3
|
13
|
13
|
11
|
16
2
|
41
|
A 3
|
15
|
7
|
13
|
28
6
|
7
|
28
|
A 4
|
5
6
|
10
|
32
10
|
14
|
6
|
37
|
A 5
|
7
|
22
9
|
12
|
6
10
|
13
4
|
41
|
Потребность
|
30
|
45
|
32
|
34
|
29
|
|
S=1158+Δ55*13=1158-3*13=1119 ден. Ед
Проверим на оптимальность
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u5 = 0.
A5B2 :
|
v2+ u5= 9
|
v2 = 9 - 0 = 9
|
A5B4 :
|
v4 + u5 = 10
|
v4 = 10 - 0 = 10
|
A5B5 :
|
v5 + u5 = 4
|
v5 = 4 - 0 = 4
|
A1B2 :
|
v2 + u1 = 8
|
u1 = 8 - 9 = -1
|
A2B5 :
|
v5 + u2 = 2
|
u2 = 2 - 4 = -2
|
A3B4 :
|
v4 + u3 = 6
|
u3 = 6 - 10 = -4
|
A2B1 :
|
v1 + u2 = 3
|
v1 = 3 - (-2) = 5
|
A4B1 :
|
v1 + u4 = 6
|
u4 = 6 - 5 = 1
|
A4B3 :
|
v3+ u4=10
|
v3 =10-1=9
| | |
|
|
Скачать 71.47 Kb.