Расчет потенциалов

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения (9.8) U_i + V_J = C_ij, просматривая все загруженные клетки. Результаты сводим в таблицу 9.7

U₁ = 0;

V₄= C_1,4 – U₁ = 6; U₃= C_3,4 – V₄ = 12; U₄= C_4,4 – V₄ = 16

V₂= C_4,2 – U₄ = -2; U₅= C_5,2 –V₂ = 14; V₁= C_3,1 - U₃ = 4

U₂= C_2,1 – V₁ = 8; V₃= C_2,3 – U₂ = -3

Проверяем план на оптимальность (9.9) по незагруженным клеткам Sij = Cij – (Ui + Vj): S_1,1= 11; S_1,2= 17; S_1,3= 13; S_2,2= 16; S_2,4=- 1; S_3,2= 12; S_3,3= 8;

S_4,1= 1; S_4,3=- 7; S_5,1= 0; S_5,3=- 1; S_5,4=- 2

Наиболее потенциальной является клетка (4,3).

Таблица 9.7

Поставщики	Вспомогат	Потребители	Запасы груза, т.
В1	В2	В3	В4
	-2	-3
А1								**
А2		*				**
А3		*
А4						*
А5				*		*
Потребность в грузе,т.

Строим контур (таблица 9.8)

Таблица 9.8

Поставщики	Вспомогат	Потребители	Запасы груза, т.
В1	В2	В3	В4
	-2	-3
А1
А2		+				-
А3		-						+
А4						+		-
А5
Потребность в грузе,т.

В данном контуре наименее загруженные клетки с отрицательными знаками – это клетки (3,1) и (4,4) с величиной груза в 25 единиц, прибавляем эту величину к грузу в клетках со знаком «+» и отнимаем ее от груза в клетках со знаком «-». В результате перемещения получим новый план и отразим его в таблице 9.9.

Таблица 9.9

Поставщики	Вспомогат	Потребители	Запасы груза, т.
В1	В2	В3	В4
А1						-		+
А2	-5	-				+
А3		+						-
А4	-4
А5	-6
Потребность в грузе,т.

Суммарная транспортная работа составит:

Z=25·6+100·12+50·5+100·18+150·14+25·6+150·12=7450 т.км. Как видим целевая функция уменьшилась на 175 т.км.

Проверим полученный план на оптимальность. Как видно из таблицы 9.9

этот план является вырожденным, так как занятых клеток меньше (7), чем необходимо (m+n-1=8). Сделаем его невырожденным поместив нуль в клетку (1,3).

Определяем потенциалы при U₁=0 для всех занятых клеток, результаты заносим в таблицу 9.9.

V₃=C_1,3 – U₁ = 10; V₄=C_1,4 – U₁ = 6; U₂=C_2,3 – V₃ = -5

U₃=C_3,4 – V₄ = 12; U₄=C_4,3 – V₃ = -4; V₂=C_4,2 – U₄ = 18

U₅=C_2,2 – V₂ = -6; V₁=C_2,1 – U₂ = 17

Проверяем план на оптимальность по незагруженным клеткам: S_1,1=- 2; S_1,2=- 3; S_2,2= 9; S_2,4= 12; S_3,1=- 13; S_3,2=- 8; S_3,3=- 5; S_4,1= 8; S_4,4= 20; S_5,1= 7; S_5,3= 6; S_5,4= 18. Наиболее потенциальная клетка (3,1), строим для нее контур в таблице 9.9, перемещаем по контуру груз величиной 0 единиц. В результате получаем новый план, заносим его в таблицу 9.10.

Таблица 9.10

Поставщики	Вспомогат	Потребители	Запасы груза, т.
В1	В2	В3	В4
		-3
А1
А2		-	12					+	13
А3		+	16					-
А4
А5
Потребность в грузе,т.

Суммарная транспортная работа останется такая же Z = 7450 т.км. Полагая U1=0, определяем остальные потенциалы:

V4= C1,4 – U1 = 6

U3= C3,4 – V4 = 12

V1= C3,1 – U3 = 4

U2= C2,1 – V1 = 8

V3= C2,3 – U2 = -3

U4= C3,3 – V3 = 9

V2= C4,2 – U4 = 5

U5= C5,2 – V2 = 7

Проверяем план на оптимальность по незагруженным клеткам: S_1,1= 11; S_1,2= 10; S_1,3= 13; S_2,2= 9; S_2,4=- 1; S_3,2= 5; S_3,3= 8; S_4,1= 8; S_4,4= 7; S_5,1= 7; S_5,3= 6; S_5,4= 5

Наиболее потенциальной является клетка (2,4), строим для нее контур в таблице 9.10. Перемещая по контуру груз величиной в 100 единиц, получаем новый план и отражаем его в таблице 9.11.

Суммарная транспортная работа по новому плану составит:

Z = 25·6 + 50·5 + 100·13 + 100·16 + 150·14 + 25·6 + 150·12 = 7350 т·км

Значение целевой функции уменьшилось на 100 т.км. Как видно из таблицы 9.11 опорный план является вырожденным, так как N =7. Сделаем его невырожденным поместив нуль в клетку (2,1).

Полагая потенциал U₁=0, определим остальные потенциалы:

Таблица 9.11

Поставщики	Вспомогат	Потребители	Запасы груза, т.
В1	В2	В3	В4
		-2
А1
А2			12						13
А3			16
А4
А5
Потребность в грузе,т.

V4= C1,4 – U1 = 6

U2= C2,4 – V4 = 7

V1= C2,1 – U2 = 5

U3= C3,1 – V1 = 11

V3= C2,3 – U2 = -2

U4= C4,3 – V3 = 8

V2= C4,2 – U4 = 6

U5= C5,2 – V2 = 6

Определяем значение S_i,j : S_1,1= 10; S_1,2= 9; S_1,3= 12; S_2,2= 9; S_3,2= 5; S_3,3= 8; S_3,4= 1; S_4,1= 8; S_4,4= 8; S_5,1= 7; S_5,3= 6; S_5,4= 6.

Так как выполняется условие S_i,j ≥ 0, то полученный план является оптимальным. Транспортная задача решена.