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

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

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

Решение транспортной задачи и построение начального опорного плана методом минимальной стоимости рассмотрим на примере следующей задачи.

Задача. Торгово-промышленная компания на трех фабриках и еженедельно изготавливает 150, 60 и 80 тысяч единиц продукции. Компания заключила договоры поставок с четырьмя заказчиками и , еженедельные потребности которых составляют 110, 40, 60 и 80 тысяч единиц продукции соответственно. Запасы, потребности и стоимость транспортировки 1000 единиц продукции заказчикам с каждой фабрики приведены в распределительной таблице 7.

Таблица 7. Матрица планирования

Поставщики	Потребители				Запасы
	4	4	2	5	150
	5	3	1	2	60
	2	1	4	2	80
Потребности			60

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

Решение.

Пусть - количество продукции, которая перевозится с -ой фабрики -му потребителю.

1. Запишем математическую модель поставленной задачи.

,

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

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

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

По условию, данная задача является сбалансированной или закрытой

.