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

Помещаем в клетку (1,1) меньшее из чисел A₁^*=370 и B₁^*=300 Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (1,2) меньшее из чисел A₁^*=70 и B₂^*=280 Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A₂^*=450 и B₂^*=210 Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A₂^*=240 и B₃^*=330 Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A₃^*=480 и B₃^*=90 Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A₃^*=390 и B₄^*=290 Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем в клетку (3,5) меньшее из чисел A₃^*=100 и B₅^*=100

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

370 A2

210

240

450 A3

290

100

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

Целевая функция F=11320

Решаем задачу методом потенциалов:

Этап 1

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы U_i, V_j: U₁=0 V₁=C_1,1-U₁= 14 V₂=C_1,2-U₁= 8 U₂=C_2,2-V₂= 2 V₃=C_2,3-U₂= 5 U₃=C_3,3-V₃= 3 V₄=C_3,4-U₃= 1 V₅=C_3,5-U₃= 6 Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток (неоптимальные выделены красным цветом) S_1,3 = c_1,3 - (u₁ + v₃) = 12. S_1,4 = c_1,4 - (u₁ + v₄) = 4. S_1,5 = c_1,5 - (u₁ + v₅) = -3. S_2,1 = c_2,1 - (u₂ + v₁) = 5. S_2,4 = c_2,4 - (u₂ + v₄) = 8. S_2,5 = c_2,5 - (u₂ + v₅) = -2.S_3,1 = c_3,1 - (u₃ + v₁) = -14.S_3,2 = c_3,2 - (u₃ + v₂) = -6. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,1). Для нее оценка равна -14. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

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

+	8
70

370 A2

-	10
210

+	7
240

450 A3

-	8
90

290

100

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

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

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

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

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы U_i, V_j: U₁=0 V₁=C_1,1-U₁= 14 V₂=C_1,2-U₁= 8 U₃=C_1,3-V₁= -11 U₂=C_2,2-V₂= 2 V₃=C_2,3-U₂= 5 V₄=C_3,4-U₃= 15 V₅=C_3,5-U₃= 20 Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток (неоптимальные выделены красным цветом) S_1,3 = c_1,3 - (u₁ + v₃) = 12. S_1,4 = c_1,4 - (u₁ + v₄) = -10.S_1,5 = c_1,5 - (u₁ + v₅) = -17. S_2,1 = c_2,1 - (u₂ + v₁) = 5. S_2,4 = c_2,4 - (u₂ + v₄) = -6.S_2,5 = c_2,5 - (u₂ + v₅) = -16.S_3,2 = c_3,2 - (u₃ + v₂) = 8. S_3,3 = c_3,3 - (u₃ + v₃) = 14. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,5). Для нее оценка равна -17. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".