Нахождение первоначального базисного распределения поставок

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

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

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

На складах А₁, А₂, А₃, имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант перевозки, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (ден. ед): .

Решение. Проверим, является ли данная транспортная задача закрытой.

,

.

,

следовательно, данная транспортная задача закрытая. Найдем исходное опорное решение по методу минимальной стоимости.

Число занятых клеток в таблице равно 5, m + n – 1 = 3 + 3 – 1 = 5, т.е. условие невырожденности выполнено. Получено исходное опорное решение, которое запишем в виде матрицы:

.

Стоимость перевозки при исходном опорном решении составляет:

L(X) = 90×2 + 300×1 + 100×5 + 50×3 + 60×8 = 1610 ден. ед.