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

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

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

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

Рассмотрим нахождение исходного опорного решения тра­нспортной задачи на конкретном примере.

< Предыдущая		Следующая >