Нахождение исходного опорного решения

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

Рассмотрим способ нахождения исходного опорного решения, который называется методом минимального тарифа. Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок c_ij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учётом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+ n – 1 (вырожденная задача). В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

Нулевые поставки помещают в незанятые клетки с учётом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке.

Определение эффективного варианта