3.7. Решение транспортных задач с ограничениями по пропускной способности

В некоторых случаях в условии транспортной задачи накладываются дополнительные ограничения на пропускную способность линии связи. Будем их обозначать . Тогда говорят о разновидности транспортных задач – транспортных задачах с ограничениями по пропускной способности. Все ограничения записываются в левом нижнем углу ячейки. Они означают, что больше чем записано в ячейку загрузить нельзя.

Решаются такие задачи обычным образом, но с дополнительными особенностями.

Алгоритм решения транспортных задач с ограничениями по пропускной способности:

1. Построение начального опорного плана можно осуществлять любым методом (правило северо-западного угла, минимального элемента, метод Фогеля). Лучше всего: по правилу минимального элемента. Особенность построения начального опорного плана заключается в следующем: в выбранную ячейку ставится минимальное из чисел ,и. Если было выбрано одно из чиселили, то говорят, что заполненная ячейка – базисная. Если же в ячейку записывается число, то ячейку назовем дополнительной. После заполнения распределительной таблицы для транспортной задачи с ограничениями по пропускной способности может остаться в некоторых столбцах и строках нераспределенный груз. В этом случае вводятся дополнительные строка и столбец, загрузка которых равна объему нераспределенного груза, а тарифы каждой ячейки, исключая (m+1, n+1), равны М. М – бесконечно большое, положительно число. В ячейке (m+1, n+1) тариф равен 0. В результате базисных переменных должно быть m+n-1.

2. Расчет потенциалов производится по базисным ячейкам. Расчет оценок свободных и дополнительных ячеек производится обычным образом. Однако, для оптимальности опорного плана необходимо, чтобы оценки дополнительных ячеек были неположительны. Для свободных ячеек оценки должны быть неотрицателтьны, а для базисных равны 0.

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

Пример: Решить транспортную задачу с ограничениями по пропускной способности:

520 520	80	140	90	130	80
220	5 + 10 БП	8 v	7 v 60	2 130 БП	1 – 80 БП	-2
140	6 70 БП	3 70 70 ДП	5 v	4 v 70	6 v	-1
160	7 – 0 БП	4 70 БП	2 90 БП	3 v	2 + v	0
	7	4	2	4	3

Базисных переменных: 5+3-1=7. Дополнительная переменная 1.

Сосчитаем оценки:

=8-(-2+4)=6>0 =5-(2-1)=4>0 =3-(4+0)=-1<0

=7-(-2+2)=7>0 =4-(4-1)=3>0 =2-(3+0)=-1<0

=3-(4-1)=0=0 =6-(3-1)=4>0

Получились две отрицательные оценки. Строим цикл.

520 520	80	140	90	130	80
220	5 10 БП	8 v	7 v 60	2 130 БП	1 80 БП	-1
140	6 70 БП	3 70 70 ДП	5 v	4 v 70	6 v	0
160	7 v	4 70 БП	2 90 БП	3 v	2 0 БП	0
	6	4	2	3	2

Базисных переменных: 5+3-1=7. Дополнительная переменная 1.

Сосчитаем оценки:

=8-(-1+4)=5>0 =5-(2+0)=3>0 =3-(3+0)=0=0

=7-(-1+2)=6>0 =4-(3+0)=1>0 =7-(6+0)=1>0

=3-(4+0)=-1<0 =6-(2+0)=4>0

Полученный план оптимален. Z=5*10+2*130+1*80+6*70+3*70+4*70+ +2*90+2*0=1480

Ответ: Z=1480.