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

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

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

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

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

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

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

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

	+ 10 БП	v	v	БП	– 80 БП	-2
	БП	70ДП	v	v	v	-1
	– 0 БП	БП	БП	v	+ v

Базисных переменных: 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

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

	БП	v	v	БП	БП	-1
	БП	70ДП	v	v	v
	v	БП	БП	v	БП

Базисных переменных: 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.