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

 

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

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

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

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
	7 – 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.

 

Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении

 

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

Дискретное программирование также называется целочисленным.

Задача о контейнерных перевозках (о рюкзаке или о бомбардировщике).

Контейнер оборудован m отсеками, вместимостью (). Для перевозки n видов продукции. Виды продукции характеризуются свойствами неделимости. Пусть – расход i-того отсека для перевозки j-той продукции. Обозначим через полезность единицы j-й продукции. Требуется найти план перевозки, при котором прибыль от перевозки максимизируется:

при

Задача о назначении (проблема выбора, о женихах и невестах).

Имеется n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-той работы (i,j= ). Нужно так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплён только один исполнитель.

Для составления математической модели задачи обозначим через – факт назначения или не назначения i-того исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения 1 или 0. Такие переменные называются булевыми.

Так как нужно найти план назначения , который максимизирует суммарную полезность назначения

при

а) каждый исполнитель назначается только на одну работу:

б) на каждую работу назначается только один исполнитель:

, - ограничение неотрицательности и целочисленности.

Мы рассмотрели только два примера, можно еще рассмотреть задачу коммивояжера, транспортную задачу с фиксированными доплатами.