Транспортная задача с ограничениями на пропускные способности: построение оптимального плана.
Транспортная задача линейного программирования с ограничениями на пропускные способности путей сообщения может быть сформулирована следующим образом. Необходимо минимизировать транспортные расходы
при ограничениях
,
где 
- стоимость перевозки единицы продукции из пункта i в пункт j; 
– планируемая величина перевозок из пункта i в пункт j (план перевозок 
– матрица размерности 
); 
- потребности в продукте в пункте j; 
- запасы в пункте i; 
– ограничение на величину планируемой перевозки из пункта i в пункт j.
Алгоритм состоит из 2-х этапов:
– определение опорного плана;
– определение оптимального плана методом потенциалов.
1. Пусть у нас есть опорный план. Для перевозок вида
, (1)
для определения потенциалов 
и 
соответствующих пунктов отправления и пунктов назначения составляется система уравнений
, (2)
и находятся потенциалы 
и 
.
2. Для остальных клеток транспортной таблицы вычисляются значения
. (3)
Если для 
, (4)
и для 
, (4)
то опорный план транспортной задачи оптимален.
Если эти условия не выполняются, то среди отрицательных чисел 
и 
выбираем наименьшее. Пусть это наименьшее из чисел соответствует перевозке с индексами 
и 
.
Возможно 2 варианта:
а) наименьшее из чисел соответствует 
;
б) наименьшее из чисел соответствует 
.
Начиная с перевозки 
, строим замкнутый цикл из базисных перевозок транспортной задачи (соответствующих (1)). В зависимости от случаев а) и б) дальнейшие действия отличаются.
а) В этом случае для улучшения плана мы должны ввести в базис перевозку 
. Пометим перевозки цикла, начиная с 
, 
, поочередно знаками + и – . (
помечаем знаком «+»)).
Определим для отрицательной полуцепи
,
для положительной полуцепи
и возьмем
.
Для получения более экономичного плана перевозки положительной полуцепи увеличиваем на q, а отрицательной – уменьшаем на q.
После этого переходим к п.1.
б) В этом случае помечаем перевозку 
помечаем знаком «–», а остальные перевозки цикла помечаем последовательно + и – .
Определим для отрицательной полуцепи
,
для положительной полуцепи
.
Определяем
.
Увеличиваем перевозки положительной полуцепи на q, а перевозки отрицательной полуцепи уменьшаем на q. Переходим к п.1.
