Метод аппроксимации Фогеля

Пусть условия транспортной задачи заданы табл. 4

Таблица 4

На каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди разностей выбирают максимальную.

В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).

Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Так в строке A2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце B4 равна 6-2=4.

Общая стоимость перевозок S=1*50+2*110+4*120+5*20+2*30+3*140=1330.

Не нашли, что искали? Воспользуйтесь поиском: