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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



Решение транспортных задач с неправильным балансом

Транспортные задачи с неправильным балансом могут быть двух типов.

1-й тип - сумма запасов в ПО превышает сумму поданных заявок:

, т.е. имеет место транспортная задача с избытком запасов.

2-й тип - сумма поданных заявок ПН превышает наличные запасы

 

, т.е. имеет место транспортная задача с избытком заявок.

 

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

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

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

Рассмотрим решение транспортных задач с неправильным балансом на примере.

Таблица 3.28

ПН ПО В 1 В 2 В 3 Запасы аi
А 1        
А 2        
А 3        
Заявки bj        

 

Решение

Разница между запасами и заявками равна:

.

 

Введением фиктивного ПН В Ф с заявкой b Ф=38 сводим задачу к ТЗ с правильным балансом.

Таблица 3.29

ПН ПО В 1 В 2 В 3 В Ф Запасы аi Платежи α j
А 1 5 5 7 7 6 - 6 11 1 + 0    
А 2 4 6   6 6   5 + 5 0 - 0   -1
А 3 4 8   6 4   5 5   0 0   -1
Заявки bj            
Платежи β j            

Таблица 3.30

ПН ПО В 1 В 2 В 3 В Ф Запасы аi Платежи α j
А 1 5 5 7 - 7 21 5 6   0 + 0    
А 2 5 6   7 6   5 5 0 0    
А 3 5 8   7 + 4   5 5   0 - 0    
Заявки bj            
Платежи β j            

Таблица 3.31

ПН ПО В 1 В 2 В 3 В Ф Запасы аi Платежи α j
А 1 5 5 7 - 7 1 5 6   0 + 0    
А 2 5 6   7 + 6   5 5 0 - 0    

Таблица 3.31 (продолжение)

ПН ПО В 1 В 2 В 3 В Ф Запасы аi Платежи α j
А 3 2 8   4 4 2 5   3 0     -3
Заявки bj            
Платежи β j            

Таблица 3.32

ПН ПО В 1 В 2 В 3 В Ф Запасы аi Платежи α j
А 1            
А 2            
А 3           -2
Заявки bj            
Платежи β j            

 

План представленный в таблице 3.32 ляется оптимальным, т.к. во всех свободных клетках псевдостоимости не превосходят стоимостей. Согласно этому плану, из 50 единиц груза, имеющихся в пункте А 1, не перевозятся 32, а остальные 18 направляются в пункт В 1, из 40 единиц, имеющихся в пункте А 2: 6 не перевозятся, 1 отправляется в пункт В 2 и 33 – в пункт В 3. Все 20 единиц, имеющиеся в пункте А 3, направляются в пункт В 2.

Метод запрещенных клеток

1. При составлении опорного плана перевозок «запретить себе» ставить отличные от нуля перевозки в клетки транспортной таблицы где стоят самые большие времена перевозок из ПО в ПН.

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

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

4. Если циклических перестановок в очередной транспортной таблице для улучшения плана перевозок сделать не удается, то базисная клетка с наибольшим временем перевозки определяет минимально-необходимое время для осуществления всех перевозок с ПО в ПН.

Рассмотрим пример.

Условия ТЗ по критерию времени (запасы, заявки и времена перевозок) даны в табл.3.33. Требуется найти план перевозок, укладывающихся в минимальное время, и указать это время.

Таблица 3.33

ПН ПО В 1 В 2 В 3 В 4 В 5 Запасы аi
А 1          
А 2            
А 3            
А 4          
Заявки bj            

 

Решение

Начальный план перевозок можно было бы, как мы и делали раньше составить способом северо-западного угла, но мы видим, что при этом получится (за счет клетки (1,1)) очень большое время Т =10. Попытаемся этого избежать, «запретив» себе ставить отличные от нуля перевозки в клетки (1,1) и (4,1), где стоят самые большие времена в таблице (t 11=10 и t 41=11). Перечеркнем в табл.3.33. эти клетки.

В плане (табл. 3.34.) время окончания всех перевозок равно 8 и достигается оно в клетке (3,2). Попробуем улучшить план, запретив себе для дальнейшего использования все клетки, где время tjj ≥ 8, и перечеркнув эти клетки. Перенесем 14 единиц груза по циклу, указанному в табл. 3.34, этим мы устраним перевозки со временем 8, получится план, приведенный в табл. 3.35, со временем окончания Т =7, клетка (3,3).

Чтобы еще улучшить этот план, нам нужно устранить перевозки из клетки (3,3), запретив кроме того, перенос в клетку (1,5), содержащую то же время. 7 из 13 единиц, стоящих в клетке (3,3), устраняем переносом по циклу, показанному в табл. 3.35. Новый план приведен в табл. 3.36.

Таблица 3.34

ПН ПО В 1 В 2 В 3 В 4 В 5 Запасы аi
А 1        
А 2 - +      
А 3 + - 14      
А 4      
Заявки bj            

Таблица 3.35

ПН ПО В1 В2 В3 В4 В5 Запасы аi
А1        
А2 - 5   + 6    
А3 + 4 - 7    
А4      
Заявки bj            

Таблица 3.36

ПН ПО В 1 В 2 В 3 В 4 В 5 Запасы аi
А 1            
А 2            
А 3            
А 4            
Заявки bj            

Попробуем избавиться от оставшихся 6 единиц в клетке (3,3) путем их циклического переноса. Для этого испробуем все возможные переносы из этой клетки, начинающиеся горизонтально или вертикально. Горизонтальный перенос в клетку (3,5) исключен, так как столбец 5 не содержит не запрещенных клеток. Горизонтальный перенос в клетку (3,1) также исключен, так как для этого пришлось бы уменьшить перевозки в клетке (2,1), что невозможно. Вертикальный перенос непосредственно, как можно убедиться, также не дает ни одного цикла, уменьшающего время перевозок. Из этого мы делаем заключение, что план перевозок, полученный в табл. 3.36, оптимален и минимальное время перевозок равно Tmin = 7.

 



Поделиться:


Последнее изменение этой страницы: 2017-02-08; просмотров: 1105; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.238.138.162 (0.013 с.)