Пример 2. На двух складах имеется по 90 т горючего, которое нужно доставить в 3 пункта

На двух складах имеется по 90 т горючего, которое нужно доставить в 3 пункта. Каждому пункту необходимо по 60 т горючего. Стоимость доставки тонны горючего из первого склада в пункт 1 равна 1ден.ед, в пункт 2 – 3 ден.ед, в пункт 3 – 5 ден.ед. Стоимость доставки из второго склада – 2,5 и 4 ден.ед. соответственно. Определить оптимальный план, минимизирующий стоимость доставки.

Решение. Построим опорный план для рассмотренной выше задачи. В начале построим исходную транспортную таблицу и заполним ее с помощью метода "минимального элемента ":

Проверим оптимальность полученного опорного плана. Для этого, используя заполненные клетки таблицы, рассчитаем потенциалы U2, V1, V2, V3. Потенциалу U1 присвоим значение 0. Используя клетку 11, получаем U1+V1 =1 -> V1=1; V2 находим из соотношения V2+U1=3, справедливого для клетки 12, составляя аналогичные соотношения для всех заполненных клеток, получаем U1=0; U2=2; V1=1; V2=3; V3=2.

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

для клетки 13: V3+U1=2<С13=5; для клетки 21: V1+U2=3>С21=2. Следовательно, построенный план не оптимален, и может быть улучшен, если мы перераспределим перевозки таким образом, чтобы заполнить клетку 21.

Построим цикл, включающий эту клетку, этот цикл будет содержать клетки 21-11-12-22.

Присвоим единственной пустой клетке 21 знак +, а затем присвоим знаки остальным клеткам цикла последовательно чередуя + и -. Получим клетки 12 и 21 имеют знак +, а клетки 11 и 22 знак -. Из «минусовых» клеток выберем клетку с минимальным объемом перевозок; в нашем случае это клетка 22 с объемом перевозок, равным 30. Перераспределим перевозки по циклу следующим образом: из «минусовых» клеток вычтем, а к «плюсовым» клеткам добавим по 30, получим новый план:

Теперь незаполненной осталась ячейка 22.

Проверим оптимальность полученного плана. Рассчитаем потенциалы, используя заполненные клетки: U1=0, U2=1, V1=1, V2=3, V3=3. Проверим соотношения оптимальности для незаполненных клеток 13 и 22: для клетки 13 – U1+V3=3<5; для клетки 22 – U2+V2=4<5. Условия оптимальности выполнены, мы получили оптимальный план перевозок. Стоимость перевозок при этом равна С= 30*1+60*3+30*2+60*4= 520.