Пример решения задачи распределительным методом

Пусть условие задачи и найденный по способу ми­нимального элемента первоначальный план записаны в табл. 20.

Таблица 20

Распределительный метод, цикл для клетки (2,3)

2. Включаем свободную клетку в набор, строим на ней цикл, означиваем его, и находим алгебраическую сумму тарифов. В табл. 20 показан цикл, построенный для клетки (2, 3). Нужная нам сумма

.

3. Делаем действия из пункта два для каждой свободной клетки. Чтобы не перегружать таблицу, другие циклы в ней не показаны, только в каждой свободной клетке результат пере­счета записан в левом верхнем углу (жирный курсив).

4. Среди найденных чисел имеются отрицательные, следовательно, оптимальное решение не достигнуто.

5. Включаем клетку с наибольшей по модулю отрицательной суммой в набор, выделяем нужный цикл, полу­чаем θ = х33 = 80 и делаем сдвиг на это число. Перевозка из клетки (3,3) переходит в клетку (1,3), а в клетке (1,2) пишем ноль, чтобы не изменилось количество базисных клеток. В результате приходим к новому плану (табл. 21).

Таблица 21

Сдвиг по циклу на 10

Считаем алгебраические суммы тарифов для всех свободных клеток. Среди найденных значений есть отрицательные, значит план не оптимален, поэтому включаем клетку с наибольшей по модулю отрицательной суммой в набор (клетка (3,1)), выделяем нужный цикл и делаем сдвиг по циклу на величину θ = х11 =10. В результате приходим к новому плану (табл. 22).

 

 

Таблица 22

Сдвиг по циклу на 90

Считаем алгебраические суммы тарифов для всех свободных клеток. Среди найденных значений есть одно отрицательное (клетка (2,2)), значит план не оптимален, поэтому включаем эту клетку в набор, выделяем цикл и делаем сдвиг по нему на величину θ = х32 =90. В результате приходим к новому плану (табл. 23).

Таблица 23

Оптимальный план, полученный распределительным методом

Пункты назначения Пункты отправления B1 B2 B3 B4 Запасы груза
A1 0 2 – 5 10 –
А2 2 7 – 0 4 –
A3 2 8 – 5 13 –
Потребности в грузе

Произведя пересчет алгебраических сумм тарифов, убеждаемся, что все суммы неотрицательны. Значит, записанный в таблице план — опти­мальный. Стоимость перевозок по нему наименьшая:

Замечание. Этаже задача, решенная методом потенциалов в прошлой лекции дала тот же результат, значит решение верно.

 

Лекция 5.