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

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

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

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 ₁₁=10 и t ₄₁=11). Перечеркнем в табл.3.33. эти клетки.

В плане (табл. 3.34.) время окончания всех перевозок равно 8 и достигается оно в клетке (3,2). Попробуем улучшить план, запретив себе для дальнейшего использования все клетки, где время t_jj ≥ 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, оптимален и минимальное время перевозок равно T_min = 7.