Задание

На складах а₁, а₂, а₃, а₄ и а₅ имеются запасы продукции в соответствующих количествах. Найти такой вариант поставки продукции от поставщиков в торговые точки в₁, в₂, в₃, в₄ и в₅ соответственно, чтобы сумма затрат на перевозку (с_ij) была минимальна. Для решения использовать метод Вогеля.

Таблица 1

Решение

 Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке табл. 2. Например, в строке В₁ минимальный тариф равен 2, а следующий за ним – 3. Разность составляет 3–2=1. Записываем это значение в дополнительный столбец. 

Таблица 2

Наибольшая разница между элементами составляет 2 и соответствует нескольким строкам и столбцам. Например, выберем строку В₃. Минимальный тариф в этой строке (2) находится на пересечении со столбцом А₂. Заполним эту клетку – х₃₂=200. Запасы пункта А₂ распределены, и столбец А₂ исключается из расчетов. Потребности пункта В₃ составляют 300–200=100.

Снова находим разницы между минимальными тарифами, исключив из расчетов столбец А₂. Наибольшая разница между тарифами снова равна 2. Выбираем столбец А₃, минимальный тариф в этом столбце находится на пересечении со строкой В₂ и составляет 2. Заполняем клетку х₂₃=200, столбец А₃ и строка В₂ исключены из расчетов.

Находим разницу между тарифами, наибольшая разница составляет 3 и находится в строке В₄. Заполняем клетку х₄₁=100 и исключаем столбец А₁ и строку В₄ из дальнейших расчетов.

Наибольшая разница между тарифами теперь составляет 9 и находится в строке В₅. Заполняем клетку х₅₄=200. Строка В₅ исключается из расчетов, а запасы в пункте А₄ равны 300–200=100.

Следующая итерация: максимальная разница между тарифами 3 (столбец А₅). Заполняется клетка х₆₅=100, строка В₆ исключается из расчетов,  запасы в пункте А₅ составляют 200–100=100.

Следующая итерация: максимальная разница между тарифами 3 (столбец А₄). Заполняем клетку х₁₄=100, строка В₁ и столбец А₄ исключаются из расчетов.

Заполняем оставшуюся клетку х₃₅=100.

Стоимость перевозок при полученном опорном плане составляет:

2*200 + 2*200 + 6*100 + 1*100 + 6*200 + 0*100 = 2900 д.е.