Сток Исток |
|
|
|
| Запасы: | ||||
| 10 | 7 | 6 | 8 | 31 | ||||
31 | |||||||||
| 5 | 6 | 5 | 4 | 48 | ||||
22 | 3 | 3 | 20 | ||||||
| 8 | 7 | 6 | 7 | 38 | ||||
38 | |||||||||
Заявки: | 22 | 34 | 41 | 20 | 117 |
Полученный на этапе 5 первой итерации алгоритма новый план перевозок имеет шесть базисных клеток в соответствующей ему транспортной таблице (см. таблицу выше), что позволяет его использовать без модификаций для дальнейшего решения задачи.
r = 6
Стоимость найденного плана перевозок равна:
L = 31×7 + 22×5 + … = 668
Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:
2. Вычислим цену цикла для каждой свободной переменной:
3. Так как не существует циклов свободных переменных с отрицательной ценой, полученный план перевозок является оптимальным. Стоимость оптимального плана перевозок, как было посчитано ранее, составляет 668 единиц.
Рассмотрим еще один пример решения классической транспортной задачи методом циклических переносов. В следующем примере мы рассмотрим такую транспортную задачу, применение к которой метода «северо-западного» угла для нахождения опорного плана даст вырожденный опорный план. Таким образом, этот пример проиллюстрирует решение транспортной задачи с вырожденным планом перевозок.
Пример 2. Решение транспортной задачи.
Найти оптимальный план перевозок транспортной задачи, имеющей следующую таблицу издержек:
Сток Исток |
|
|
| Запасы: | |||
| 10 | 5 | 4 | 40 | |||
| 6 | 4 | 5 | 23 | |||
| 7 | 3 | 6 | 20 | |||
Заявки: | 20 | 20 | 43 | 83 |
Решение:
1. Методом «северо-западного» угла найдем опорный план перевозок:
Сток Исток |
|
|
| Запасы: | |||
| 10 | 5 | 4 | 40 | |||
20 | 20 | ||||||
| 6 | 4 | 5 | 23 | |||
23 | |||||||
| 7 | 3 | 6 | 20 | |||
20 | |||||||
Заявки: | 20 | 20 | 43 | 83 |
Полученный опорный план перевозок имеет четыре базисных клетки в соответствующей ему транспортной таблице (см. таблицу выше), что не позволяет использовать его напрямую без модификаций для дальнейшего решения задачи.
r = n + m – 1 = 3 + 3 – 1 = 5 ¹ 4
План получается вырожденный.
Сток Исток |
|
|
| Запасы: | |||
| 10 | 5 | 4 | 40-e | |||
20 | 20 | e | |||||
| 6 | 4 | 5 | 23 | |||
23 | |||||||
| 7 | 3 | 6 | 20+e | |||
20-e | |||||||
Заявки: | 20 | 20 | 43 | 83 |
Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. Теперь:
r = 5,
а найденный опорный план можно использовать в дальнейшем для решения задачи.
Стоимость найденного плана перевозок равна:
L = 20×10 + 20×5 + 23×5 + 20×6 = 535.
Попытаемся улучшить найденный опорный план перевозок методом циклических переносов.
2. Вычислим цену цикла для k = 4 свободных клеток.
3. Вычислим максимальное количество груза, которое можно перенести по циклам с отрицательной ценой.
4. Для свободных переменных с отрицательной ценой цикла вычислим характеристику 
.
(i, j) | 2,1 | 2,2 | 3,1 | 3,2 |
g | - 5 | - 2 | - 5 | - 4 |
g×max x | - 100 | - 40 | - 100 | - 80 |
5. Перенесем max x21 = 20 единиц груза по циклу свободной переменной х21, уменьшив значение целевой функции на 100 единиц, то есть:
Сток Исток |
|
|
| Запасы: | |||
| 10 | 5 | 4 | 40-e | |||
20 | 20 | e | |||||
| 6 | 4 | 5 | 23 | |||
23 | |||||||
| 7 | 3 | 6 | 20+e | |||
20-e | |||||||
Заявки: | 20 | 20 | 43 | 83 |
В результате получим следующий (уже не вырожденный) план перевозок:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Основные порталы (построено редакторами)