Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.

Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

Клетка (i, j) таблицы соответствует коммуникации, связывающей i-го поставщика с j -м потребителем. Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:

а) число заполненных клеток было (m+n -1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);

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

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j - номер потребителя).

ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из a_i и потребности b_j.

x_ij = min{ a_i, b_j }

ШАГ З. Уменьшим запас a_i и потребность b_j на величину перевозки x_ij, т.е.

a_i = a_i - x_ij,

b_j =b_j -x_ij

ШАГ 4. При исчерпании запаса (a_i = 0) запрещаем к перевозке оставшиеся свободные клетки i -ой строки, а при исчерпании потребности

(b_j =0) запрещаем такие же клетки в j- ом столбце.

В случае одновременного исчерпания запасов потребностей (a_i =b_j = 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n- 1.

Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).