Методы решения транспортных задач (стр. 4 из 7)

Значение целевой функции изменилось на 320 единиц по сравнению с предыдущим этапом.

Этап 5

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1-c_1,4+c_3,4-c_3,1 = 10 S_1,2 = c_1,2-c_1,4+c_3,4-c_3,2 = 2 S_1,3 = c_1,3-c_1,4+c_3,4-c_3,2+c_2,2-c_2,3 = 14 S_2,1 = c_2,1-c_2,2+c_3,2-c_3,1 = 13 S_2,4 = c_2,4-c_2,2+c_3,2-c_3,4 = 2 S_2,5 = c_2,5-c_2,2+c_3,2-c_3,4+c_1,4-c_1,5 = -1 S_3,3 = c_3,3-c_3,2+c_2,2-c_2,3 = 6 S_3,5 = c_3,5-c_3,4+c_1,4-c_1,5 = 7

B1	B2	B3	B4	B5
A1	10	2	14
A2	13	2	-1
A3	6	7

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее перспективной является клетка (2,5). Для нее оценка равна -1. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик	Потребитель					Запасы груза
	B1	B2	B3	B4	B5
A1

8

17

+	5
270

-	3
100

370 A2

21

-	10
120

7

330

11

+

6

450 A3

3

300

+	5
160

8

-	4
20

9

480 Потребность 300 280 330 290 100

Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Поставщик	Потребитель					Запасы груза
	B1	B2	B3	B4	B5
A1