Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




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

 

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

 

Решение:

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

 

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

 

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

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

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

 

Сток Исток Запасы:
            40-e
        e  
             
           
            20+e
        20-e  
Заявки:        

 

Чтобы избежать этого, нарушаем баланс запасов и заявок на 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 единиц, то есть:

 

Сток Исток Запасы:
            40-e
        e  
             
           
            20+e
        20-e  
Заявки:        

 

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

 

Сток Исток Запасы:
            40-e
        20+e  
             
           
            20+e
        20-e  
Заявки:        

 

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

r = 5

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

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

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

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

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

4. g32×max x32 = - 80.

 

Сток Исток Запасы:
            40-e
        20+e  
             
           
            20+e
        20-e  
Заявки:        

 

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

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

 

Сток Исток Запасы:
            40-e
        40+e  
             
           
            20+e
        e  
Заявки:        

 

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

r = 5

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

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

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

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

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


4.

 

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

 

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

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

 

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

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

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





Поделиться с друзьями:


Дата добавления: 2015-09-20; Мы поможем в написании ваших работ!; просмотров: 455 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Что разум человека может постигнуть и во что он может поверить, того он способен достичь © Наполеон Хилл
==> читать все изречения...

2543 - | 2356 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.014 с.