Методы решения транспортных задач

Составляется таблица, в ячейки которой заносят количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij:

Затем решение задачи разбивается на два этапа:

1. Определение опорного плана

2. Нахождение оптимального решения, путем последовательных перераспределений перевозок

Для определения начального опорного плана используется метод наименьшего элемента. Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям.

Для нахождения оптимального плана перевозок последовательно используют метод потенциалов. Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному придают любое число (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.