Условие задачи
Имеются пункты A1, A2, … поставки однородного груза и пункты B1, B2, … потребления этого груза. На пунктах находится груз соответственно в количестве a1, a2 … тонн. В пункты B1, B2, … требуется доставить соответственно b1, b2, … тонн груза. Цены перевозок (стоимости провоза единицы груза) в условных единицах между пунктами поставки и пунктами потребления приведены в следующей матрице-таблице C:
Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.
Изобразить оптимальный план перевозок в виде графа.
Ответ
Исходные данные (запасы, потребности и цены)
Проверим, является ли задача закрытой:
= 200 +250 + 140 = 590;
b = 190 + 100 + 120 + 110 = 520.
b Транспортная задача является открытой, так как запас груза больше потребностей на 70 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B5.
Находим начальный базисный план методом минимальной стоимости.
x32 = min(140,100) = 100; ...
