Транспортная задача по критерию времени.

В такой транспортной задаче решающую роль играет не стоимость перевозок, а время, которое затрачивается на доставку груза. Оптимальным планом считается план, который минимизирует время перевозок. Подобные задачи возникают при перевозках скоропортящихся продуктов и в военном деле, где зачастую стоимость перевозок играет второстепенную роль. Как и в предыдущей задаче имеется m пунктов отправления, с запасами однородного продукта , пунктов назначения с потребностями .

Задача закрытого типа, т.е.

Задана матрица , где – необходимое для перевозки груза из пункта i в пункт j.

Необходимо выбрать среди допустимых такой план, что

и грузы будут доставляться по этому плану за минимальное время .

Каждому допустимому плану соответствует некоторый набор , состоящий из элементов матрицы , соответствующих положительным компонентам плана . Т.е. включается в набор, если производится перевозка из пункта i в пункт j.

Время , необходимое для выполнения плана , определяется следующим образом

.

Тогда время, необходимое для реализации оптимального плана

.

Алгоритм отыскания оптимального решения

Данный алгоритм состоит из двух этапов:

1. Предварительный шаг.

Строим допустимый план по методу северо-западного угла или минимального элемента .

2. Общий шаг.

Просматриваем все , соответствующие положительным и выбираем из них наибольшее  

и вычеркиваем все клетки, для которых .

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

Первой клеткой отрицательной полуцепи берем клетку с , остальными клетками отрицательной полуцепи выбираем клетки с _­>0, клетками положительной полуцепи берем клетки с .

Затем перемещаем минимальный элемент отрицательной полуцепи в положительную. Если удается обратить в 0, то реализация нового плана потребует меньшего времени.

Общий шаг продолжаем повторять до тех пор, пока станет невозможным обращение в 0 всей перевозки из клетки с максимальным временем .