1.2.1 Метод северо-западного угла

Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла.

При этом методе на каждом шаге построения первого опорного плана левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблице начинается с клетки неизвестного и заканчивается в клетке неизвестного, то есть идёт по диагонали таблицы перевозок.

Заполнение таблицы начинается с её северо-западного угла, допустим, что первая база может полностью удовлетворить потребность первого заказчика. В первую клетку вписываем число равное потребности первого заказчика и исключаем из рассмотрения первый столбец. Далее находим северо-западный угол, уже не учитывая первый столбец. Сравниваем остаток первый базы с потребностями второго заказчика, если удовлетворяет, то пишем число равное потребности второго заказчика, а если нет, то берём в рассмотрение вторую базу. Если сумма остатка первой и второй баз удовлетворяет потребностям второго заказчика, то пишем в клетку число равное потребности второго заказчика и исключаем из рассмотрения первую строку . Тем же способом находим остальные базисные переменные.[2]

1.2.2 Метод минимальной стоимости

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(cij).

Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.

1.2.3 Метод потенциалов

Метод потенциалов этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

Общий принцип определения оптимального пла­на транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала на­ходят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.