Транспортная задача
Транспортная
задача
Вар 3
Никита
Пазенко
|
15
|
15
|
16
|
15
|
15
|
|
19
|
21
|
17
|
12
|
24
|
30
|
|
19
|
6
|
1
|
9
|
5
|
9
|
|
19
|
7
|
5
|
24
|
6
|
13
|
|
19
|
29
|
22
|
21
|
5
|
7
|
Потребителей 5, Поставщиков 4
Проверим ТЗ на замкнутость: 
.
, т.е. задача замкнутого типа.
Решением ТЗ будет служить
минимальное значение целевой функции и значения xij
|
B1=15
|
B2=15
|
B3=16
|
B4=15
|
B5=15
|
U
|
|
A1=19
|
21
15
|
17
- 4
|
12
+
|
24
|
30
|
U1=0
|
|
A2=19
|
6
|
1
+ 11
|
9
- 8
|
5
|
9
|
U2=-16
|
|
A3=19
|
7
|
5
|
24
8
|
6
11
|
13
|
U3= -1
|
|
A4=19
|
29
|
22
|
21
|
5
4
|
7
15
|
U4= -2
|
V1=21
|
V2=17
|
V3=25
|
V4=7
|
V5=9
|
|
|
|
1 =
21*15+4*17+11+72+24*8+66+20+7*15=315+68+11++72+192+86+105=849
Итерация 1
u1= 0
v1= 21
v2= 17
v3=25
u2= - 16
v4= 7
u3= - 1
u4= - 2
Проверим план на оптимальность.
Признак оптимальности:sij=
cij -(ui+vj)
≥ 0 
opt,
для всех i, j.
Определим значения оценок sij=
cij - (ui+vj)
≥ 0 для всех свободных клеток:
S13= -13= 17= 21= 1= 14= 16= 27= -
11= 5= 1042= 7
S43= - 2
План не оптимален. Наиболее потенциальной
является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей
«невязкой» ввожv перевозку,
выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (1,3), построим граф и запишем
цикл.
-23-22-12
+ - + -
Из клеток со знаком «-» выбираем клетку с
наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы,
прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со
знаком «-». В результате перемещения по циклу получим новый план.
|
B1=15
|
B2=15
|
B3=16
|
B4=15
|
B5=15
|
U
|
|
A1=19
|
21
- 15
|
17
|
12
+ 4
|
24
|
30
|
U1=0
|
|
A2=19
|
6
|
1
15
|
9
4
|
5
|
9
|
U2=-3
|
|
A3=19
|
7
+
|
5
|
24
- 8
|
6
11
|
13
|
U3=12
|
|
A4=19
|
29
|
22
|
21
|
5
4
|
7
15
|
U4=11
|
|
V
|
V1=21
|
V2=4
|
V3=12
|
V4= -6
|
V5=-4
|
|
|
L2=315+48+15+36+192+66+20+105=797
|
|
Итерация 2
u1= 0
v2= 4
v3=12
u2= - 3
v4= - 6
u3= 12
u4= 11
Проверим план на оптимальность.
Признак оптимальности:sij=
cij -(ui+vj)
≥ 0 opt,
для всех i, j.
Определим значения оценок sij=
cij - (ui+vj)
≥ 0 для всех свободных клеток:
S12= 13= 30= 34= -12= 14= 16= - 27=
- 11= 5= -342= 7
S43= -2
План не оптимален. Наиболее потенциальной
является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей
«невязкой» ввожv перевозку,
выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (3,1), построим граф и запишем
цикл.
-11-13-33
+ - + -
Из клеток со знаком «-» выбираем клетку с
наименьшей величиной груза. В нашем случае это клетка (3,3) с грузом 8.
Перемещаем по циклу груз величиной в 8 единицы,
прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со
знаком «-». В результате перемещения по циклу получим новый план.
|
B1=15
|
B2=15
|
B3=16
|
B4=15
|
B5=15
|
U
|
|
A1=19
|
21
- 7
|
17
|
12+
12
|
24
|
30
|
U1=0
|
|
A2=19
|
6
|
1
15
|
9-
4
|
5
+
|
9
|
U2= -3
|
|
A3=19
|
7
+ 8
|
5
|
24
|
6
- 11
|
13
|
U3=-14
|
|
A4=19
|
29
|
22
|
21
|
5
4
|
7
15
|
U4=- 15
|
|
V
|
V1=21
|
V2=4
|
V3=12
|
V4= 20
|
V5=22
|
|
=147+144+15+36+56+66+20+105=589
Итерация 3= 0= 21= 4=12= -3= 20= - 14= - 15
Проверим план на оптимальность.
Признак оптимальности: sij= cij -(ui+vj) ≥
0 opt, для всех i, j.
Определим значения оценок sij= cij - (ui+vj) ≥
0 для всех свободных клеток:
S12= 13= 4= 8=- 12= - 12= - 10= 15=
26=5= 23
S42= 33= 24
План не оптимален. Наиболее потенциальной
является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей
«невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (2,4), построим граф и запишем
цикл.
-34-31-11-13-23
+ - + - + -
Перемещаем по циклу груз величиной в 4 единицы,
прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со
знаком «-». В результате перемещения по циклу получим новый план.
|
B1=15
|
B2=15
|
B3=16
|
B4=15
|
B5=15
|
U
|
|
A1=19
|
21
3
|
17
|
12
16
|
24
|
30
|
U1=0
|
|
A2=19
|
6
|
1
15
|
9
|
5
4
|
9
|
U2= - 15
|
|
A3=19
|
7
12
|
5
|
24
|
6
7
|
13
|
U3=- 14
|
|
A4=19
|
29
|
22
|
21
|
5
4
|
7
15
|
U4=- 15
|
|
V
|
V1=21
|
V2=16
|
V3=12
|
V4=20
|
V5= 22
|
|
транспортный задача перевозка цикл
L4=63+192+15+20+84+42+20+105=541
Итерация 3
u1= 0
v1= 21
v2=16
v3=12
u2= - 15
v4= 20
u3= - 14
u4= - 15
v5= 22
Проверим план на оптимальность.
Признак оптимальности:sij=
cij -(ui+vj)
≥ 0 opt,
для всех i, j.
Определим значения оценок sij=
cij - (ui+vj)
≥ 0 для всех свободных клеток:
S12= 1= 4= 8= 0= 12= 2= 3= 26= 5=23=
21= 24
Ответ: L=541=3=1622=15
X24=4
X31=12
X34=7
X44=4
X45=15