Среди тарифов находится наименьший

Клетку с выбранным тарифом заполняем максимально возможным объемом груза с учетом ограничений по строке и столбцу, при этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует.

Из оставшихся тарифов вновь находим наилучший, и процесс продолжается до тех пор, пока не будет распределен весь груз.

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

Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов.

и) План транспортной задачи будет являться оптимальным, если существует система m+n чисел называемых потенциалами, удовлетворяющая условиям:

- для занятых клеток, где >0

для свободных клеток, где =0

при решении задачи на минимум, а при решении задачи на максимум:

для занятых клеток, где >0

для свободных клеток, где =0,

Потенциалы и являются переменными двойственной транспортной задачи и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Введем обозначение оценки свободной клетки таблицы:

Если среди оценок нет отрицательная (задача поставлена на минимум), то опорный план является оптимальным и все сво­бодные клетки потенциальны.