Контрольная работа: Транспортная задача
Транспортная задача
Транспортная задача
Вар 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