Пример 2. Решение транспортной задачи

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

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru      
           
Пример 2. Решение транспортной задачи - student2.ru      
           
Пример 2. Решение транспортной задачи - student2.ru      
           
Заявки:

Решение:

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

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru      
       
Пример 2. Решение транспортной задачи - student2.ru      
         
Пример 2. Решение транспортной задачи - student2.ru      
         
Заявки:

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

r = n + m – 1 = 3 + 3 – 1 = 5 ¹ 4

План получается вырожденный.

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru       40-e
    e  
Пример 2. Решение транспортной задачи - student2.ru      
         
Пример 2. Решение транспортной задачи - student2.ru       20+e
        20-e  
Заявки:

Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. Теперь:

r = 5,

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

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

L = 20×10 + 20×5 + 23×5 + 20×6 = 535.

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

2. Вычислим цену цикла для k = 4 свободных клеток.

Пример 2. Решение транспортной задачи - student2.ru

3. Вычислим максимальное количество груза, которое можно перенести по циклам с отрицательной ценой.

Пример 2. Решение транспортной задачи - student2.ru

4. Для свободных переменных с отрицательной ценой цикла вычислим характеристику Пример 2. Решение транспортной задачи - student2.ru .

(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 единиц, то есть:

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru       40-e
    e  
Пример 2. Решение транспортной задачи - student2.ru      
         
Пример 2. Решение транспортной задачи - student2.ru       20+e
        20-e  
Заявки:

В результате получим следующий (уже не вырожденный) план перевозок:

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru       40-e
      20+e  
Пример 2. Решение транспортной задачи - student2.ru      
       
Пример 2. Решение транспортной задачи - student2.ru       20+e
        20-e  
Заявки:

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

r = 5

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

L = 20×5 + 20×4 + 20×6 + 3×5 + 20×6 = 435

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

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

Пример 2. Решение транспортной задачи - student2.ru

3. Максимальное количество груза, которое можно перенести по циклу свободной переменной х32 = 20.

4. g32×max x32 = - 80.

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru       40-e
      20+e  
Пример 2. Решение транспортной задачи - student2.ru      
       
Пример 2. Решение транспортной задачи - student2.ru       20+e
        20-e  
Заявки:

5. Перенесем 20 единиц груза по циклу переменной x32, , уменьшив значение целевой функции на 80 единиц.

В результате получим следующий план перевозок:

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru       40-e
        40+e  
Пример 2. Решение транспортной задачи - student2.ru      
       
Пример 2. Решение транспортной задачи - student2.ru       20+e
      e  
Заявки:

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

r = 5

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

L = 40×4 + 20×6 + 3×5 + 20×3 = 355

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

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

Пример 2. Решение транспортной задачи - student2.ru

3. Максимальное количество груза, которое можно перенести по циклу единственной свободной переменной х22, имеющей отрицательную цену цикла, равно бесконечно малой величине e. Полагая e = 0, получим окончательный оптимальный план перевозок:

4.

Сток Исток Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Пример 2. Решение транспортной задачи - student2.ru Запасы:
Пример 2. Решение транспортной задачи - student2.ru      
         
Пример 2. Решение транспортной задачи - student2.ru      
       
Пример 2. Решение транспортной задачи - student2.ru      
         
Заявки:

стоимость которого равна:

L = 40×4 + 20×6+ 3×5 +20×3 =355

Примененный метод «ликвидации вырождения» путем изменений запасов на бесконечно малую величину e не всегда удобен, так как требует дополнительных действий с бесконечно малыми величинами e. Значительно проще было бы не изменять запасы, а вместо величины e поставить в базисной клетке нуль. Тогда базисная клетка будет тем отличаться от свободной, что в ней нуль поставлен, а в свободной нет.

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

Рассмотрим теперь другой метод решения транспортной задачи – метод потенциалов.

Наши рекомендации