Задача II

Решить ТЗ с открытой моделью, если дана матрица планирования перевозок:

Решение:

а). Установим характер задачи:

, итак

> Þ

модель задачи открытая, значит, вводим фиктивный пункт отправления А5 с запасами груза a5= - = 120 - 115=5, а тарифы перевозки этого груза будут С51=С52=С53=С54= С55=0.

Составляем распределительную таблицу по методу " минимального элемента":

Итак, получили план X1. Суммарные расходы на перевозку зерна составляют:

Z(X1) =24× 6+11× 30+14× 29+26× 21+4× 5+20× 28+1× 1+15× 14+5× 0 =

= 144+330+406+546+20+560+1+210=2217 руб.

б). Построение нового улучшенного опорного плана по методу потенциалов.

Рассмотрим опорный план, найденный по методу “минимального элемента”.

	B1	B2	B3	B4	B5	ai	ui
A1		- 30 25	+ 25
A2	+ 5 19		- 21				- 4
A3							- 20
A4							- 6
A5	- 0	+ 0					- 9
bj
uj

Проверяем условие m+n-1=5+5-1=9, число занятых клеток удовлетворяет этому условию.

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

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

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

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

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

S52 - наименьшая оценка.

С вершиной в клетке (5;

2) строим замкнутый цикл.

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

	B1	B2	B3	B4	B5	ai	ui
A1
A2			- 21 11	+ 4			- 4
A3							- 20
A4			+ 8	- 2			- 6
A5							- 30
bj
uj

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

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 -		- 25
A2	- 5		-	+ 4			- 15
A3							- 20
A4			+ 8	- 2			- 17
A5							- 30
bj
uj

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

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		- 25
A2	- 5		-		+ 13		- 1
A3			+ 5		- 1		- 20
A4							- 17
A5							- 30
bj
uj

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

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.

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

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 рубля.

Тестовая база