Транспортная задача (стр. 2 из 2)

B1	B2	B3	B4	B5	ai	ui
A1	6	30 20	25 15	7	15	35	0
A2	5 24	29	- 21 11	+ 4 5	13	40	- 4
A3	18	22	5 4	28	1 21	25	- 20
A4	19	23	+ 8	- 2 15	14	15	- 6
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
uj	9	30	25	8	21

Определяем потенциалы и находим оценки свободных клеток:

S11=-3 S25=-4 S41=16 S51=21

S14=-1 S31=29 S42=-1 S53=5

S15=-6 S32=12 S43=-11 S54=22

S22=3 S34=40 S45=-1 S55=9

S43 - наименьшая оценка. С вершиной в клетке (4;

3) строим замкнутый цикл. Найдем l=min(11; 15) =11, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

B1	B2	B3	B4	B5	ai	ui
A1	+ 6 -	30 20	- 25 15	7	15	35	0
A2	- 5 24	29	21 -	+ 4 16	13	40	- 15
A3	18	22	5 4	28	1 21	25	- 20
A4	19	23	+ 8 11	- 2 4	14	15	- 17
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
uj	20	30	25	19	21

Определяем потенциалы и находим оценки свободных клеток:

S11=-14 S23=11 S34=29 S51=10

S14=-12 S25=7 S41=16 S53=5

S15=-6 S31=18 S42=10 S54=11

S22=14 S32=12 S45=10 S55=9

S11 - наименьшая оценка. С вершиной в клетке (1;

1) строим замкнутый цикл. Найдем l=min(24; 15;

4) =4.

B1	B2	B3	B4	B5	ai	ui
A1	+ 6 4	30 20	- 25 11	7	15	35	0
A2	- 5 20	29	21 -	4 20	+ 13	40	- 1
A3	18	22	+ 5 4	28	- 1 21	25	- 20
A4	19	23	8 15	2	14	15	- 17
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
uj	6	30	25	5	21

Определяем потенциалы и находим оценки свободных клеток:

S14=2 S25=-7 S41=30 S51=24

S15=-6 S31=32 S42=10 S53=5

S22=0 S32=12 S44=14 S54=25

S23=-3 S34=43 S45=10 S55=9

S25 - наименьшая оценка. С вершиной в клетке (2;

5) строим замкнутый цикл. Найдем l=min(20; 11; 21) =11.

B1	B2	B3	B4	B5	ai	ui
A1	6 15	30 20	25	7	15	35	0
A2	5 9	29	21	4 20	13 11	40	- 1
A3	18	22	5 15	28	1 10	25	- 13
A4	19	23	8 15	2	14	15	- 10
A5	0	0 5	0	0	0	5	- 30
bj	24	25	30	20	21	120 120
uj	6	30	18	5	14

Определяем потенциалы и находим оценки свободных клеток:

S13=7 S23=4 S41=23 S51=24

S14=2 S31=25 S42=3 S53=12

S15=1 S32=39 S44=7 S54=25

S22=0 S34=36 S45=10 S55=16

Так как все Sij>0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:

min Z=15×6+20×30+9×5+20×4+11×13+15×5+10×1+15×8+5×0=

=90+600+45+80+143+75+10+120+0=1163 руб.

Ответ: затраты на перевозки по оптимальному плану составляют 1163 рубля.