Постановка транспортной задачи
Аналогично, при 
<
, вводят фиктивный (m+1)-й пункт отправления с запасом груза am+1=- и соответствующие тарифы считают равными нулю: cm+1j=0 (j=1,n). Этим задача сводится к транспортной задаче с закрытой моделью, из оптимального плана которой получается оптимальный план исходной задачи. Поэтому в дальнейшем мы будем рассматривать только закрытую модель транспортной задачи.
Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системе ограничений равно n+m. Так как предполагается, что выполняется условие закрытости, то число линейно-независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным
, а если меньше - то вырожденным
. Для определения опорного плана существует несколько методов. Ниже рассматриваются два из них - метод северо-западного угла, метод минимального элемента.
Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.
Определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.