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

Найти оптимальный план перевозок транспортной задачи, имеющей следующую таблицу издержек:

 

Сток Исток					Запасы:
Заявки:

 

Решение:

Методом «северо-западного» угла найдем опорный план перевозок:

 

Сток Исток					Запасы:
Заявки:

 

1. Составленный с помощью метода «северо-западного угла» опорный план имеет шесть базисных клеток в соответствующей ему транспортной таблице, что позволяет его использовать без модификаций для дальнейшего решения задачи.

r = n + m – 1 = 4 + 3 – 1 = 6

Посчитаем теперь стоимость найденного опорного плана:

L = 22×10 + 9×7 + … = 796

Попытаемся улучшить найденный опорный план перевозок методом циклических переносов.

2. Вычислим цену цикла для каждой свободной клетки. Количество свободных клеток в транспортной таблице данного опорного плана равно: k = 3×2 = 6.

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

4. Теперь для всех свободных переменных с отрицательной ценой циклов вычислим характеристику . Полученные значения будем использовать при выборе конкретного цикла пересчета на данной итерации алгоритма.

 

ij	2,1	2,4
g	- 4	- 2	- 2
x
gx	- 88	- 40	- 36

 

5. Выберем ту свободную переменную, которой соответствует наименьшее значение величины и перенесем единиц груза по циклу, соответствующему выбранной переменной: (ij) = (2,1); g₂₁ = - 4; .

 

Сток Исток					Запасы:
Заявки:

 

Таким образом, мы уменьшим значение целевой функции L – стоимость плана перевозок – на 88 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

Сток Исток					Запасы:
Заявки:

 

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

r = 6

Стоимость найденного плана перевозок равна:

L = 31×7 + 22×5 + … = 708

Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

 

2. Вычислим цену цикла для каждой свободной переменной:

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

.

4. Для единственной свободной переменной рассчитаем значение критерия :

.

 

 

Сток Исток					Запасы:
Заявки:

 

Перенесем единиц груза по циклу
(2,4)⁺, (3,4)^-, (3,3)⁺, (2,3)^-, уменьшив этим значение целевой функции на 40 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

Сток Исток					Запасы:
Заявки:

 

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

r = 6

Стоимость найденного плана перевозок равна:

L = 31×7 + 22×5 + … = 668

Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

 

2. Вычислим цену цикла для каждой свободной переменной:

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

 

Рассмотрим еще один пример решения классической транспортной задачи методом циклических переносов. В следующем примере мы рассмотрим такую транспортную задачу, применение к которой метода «северо-западного» угла для нахождения опорного плана даст вырожденный опорный план. Таким образом, этот пример проиллюстрирует решение транспортной задачи с вырожденным планом перевозок.