Дополнительные ограничения в транспортной задаче

В силу определенных обстоятельств пропускная способность некоторых клеток в транспортной задаче может быть ограничена или транспортировка в некоторых клетках вообще невозможна. Это приводит к тому, что в транспортную задачу вводятся дополнительные ограничения (как правило сверху) на Х_ij.

В 1-м случае при решении задачи нужно иметь в виду, что клетки, загруженные до верхнего предела, не участвуют в определении величины потенциалов, а условие c_ij = v_j + u_i на них не распространяется.

Во 2-м случае значения c_ij клетки, транспортировка через которую невозможна, приравнивается к величине М, достаточно большому положительному числу. Это приводит к тому, что при решении задачи на минимум указанная клетка останется свободной.

На практике чаще всего 1-й случай сводят ко 2-му, путем введения дополнительных потребителей.

Если X_i*j*X, то спрос j* -го поставщика разделяется на две части a_j* = X и a_j*= a_j* - X. Коэффициенты c_ij* = c_ij, c_ij*= c_ij, кроме с_i*j*= M.

Пример. На 2-х складах имеется 20 и 10 т удобрений. Необходимо перевезти их в 3 хозяйства: 1 - е – 5 т, 2 - е - 7 т, 3 – е - 10 т. Издержки на транспортировку приведены в таблице 18.

Таблица 18 – Издержки на транспортировку

Склад	Хозяйство
А	Б	В

Дорога между 2-м складом и хозяйством А непроходима. По дороге от склада 1 к хозяйству В можно перевезти не более 3 т удобрений. Требуется решить задачу с учетом ограничений на пропускную способность дороги.

Решение задачи приведено в таблице 19.

Таблица 19 – Решение задачи с ограничением перевозок

Склад	Хозяйство	Фиктивный потребитель	ui
А	Б	В
5 х	7 х	3 х	7 х
	20 13 8 5 х	8)	7)	15) 3)	М	0)
	10 3 х	М			40)	0)
vj

Дата добавления: 2014-01-05