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

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

Суммарный объем производства больше потребления - может быть введен фиктивный пункт потребления В_n+1 с объемом потребления

b_{n+1 =} b_n+1 – суммарный объем нереализованного продукта.

Размеры остатков в разных пунктах производства можно регулировать введением штрафа за единицу нереализованного продукта А_i.

Суммарный объем производства меньше потребления, то полное удовлетворение всех пунктов потребления невозможно. В этом случае необходимо организовать перевозки всего произведенного продукта так, чтобы наиболее важные пункты удовлетворялись полнее, и при этом суммарные транспортные расходы должны быть минимальны – вводится величина ущерба r_j при неудовлетворении пункта В_j.

Требуется минимизировать суммарные затраты

при условиях

, , x_ij > 0, y_j = b_j - , где

y_j – разность между потребностями пункта В_j и поставками в него.

Перевозки с резервированием.

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

I_к – совокупность номеров i-го пункта производства в к-ом районе.

Требуется организовать перевозки таким образом, чтобы в к-ом районе (к=1,…,s) сохранилось не менее V_к единиц продукта.

- V_к , .

Общее число продуктов, вывезенных из всех пунктов производства к-го района должно быть не менее, чем на V_к (величину заданного резерва) меньше суммарного количества продукта, произведенного в этом районе.

Задача сводится к задаче транспортного типа

При условиях

- удовлетворение спроса каждого пункта потребления;

из каждого пункта потребления не может быть вывезено продукта

больше, чем производится;

- V_к , - условие резервирования;

x_ij ≥ 0 , - объем перевозок неотрицательные числа (перевозки запрещены из пунктов потребления в пункты производства).

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

Ограничения на пропускные способности магистралей (в ограниченный промежуток времени) не позволят реализовать оптимальный план перевозок, полученный без учета этих ограничений.

В этом случае в транспортной задаче условие xij ≥ 0 , заменяется неравенством вида 0 ≤ хij ≤ dij, где dij – пропускная способность магистрали (ij), т.е. максимальный объем продукции, который может быть перевезен по этой магистрали за рассматриваемый промежуток времени. Такая задача может быть вообще неразрешимой (когда пропускная способность всех магистралей, ведущих к j-му потребителю меньше объема его потребностей).

Перевозки с промежуточной обработкой.

Задача может быть осложнена наличием промежуточных транспортных узлов, в которых производится обработка груза (перевалка на другой вид транспорта, доработка полуфабриката перед поступлением его в пункт потребления).

А₁,…, А_m – пункты производства с объемами производства а₁, …, а_m

В₁,…, В_n – пункты потребления с объемами потребления b₁,…, b_n

С₁,…, С_к – пункты промежуточной обработки.

Возможности пункта промежуточной обработки С_λ ограничены d_λ единицами продукта.

Стоимости перевозки единицы полуфабриката продукта из А_i в С_λ составляет С_iλ‘, стоимость перевозки единицы полуфабриката продукта из С_λ в В_j составляет С_λj“.

Составить такой план перевозок, при котором весь полуфабрикат вывозится, полностью обрабатывается, потребности всех пунктов потребления удовлетворяются и при этом транспортные расходы минимальны.

Математическая модель.

Z_iλj – количество продукта, доставляемое из пункта А_i в В_j через С_λ.

Транспортная таблица.

	B1	B2	…	Bn	Bn+1	Bn+2	…	Bn+k-1	Bn+k
А1	M	M		M	c’11	c’12		c’1,k-1	c’1k	a1
А2	M	M		M	c’21	c’21		c’2,k-1	c’2k	a2
...				…						…
Аm	M	M		M	c’m1	c’m2		c’m?k-1	c’mk	am
Аm+1	c”11	c”12		c”1n	0	M		M	M	d1
Аm+2	c”21	c”21		c”2n	M	0		M	M	d2
…										…
Аm+k-1	c”k-1,1	c”k-1,2		c”k-1,n	M	M	…	0	M	dk-1
Аm+k	c”k1	c”k2		c”kn	M	M		M	0	dk
	b1	B2	…	Bn	d1	d2	…	dk-1	dk

Определить план перевозок {Z_iλj}, на котором достигается минимум линейной формы

( С_iλ‘ + С_λj“) Z_iλj → min

при условиях

Z_iλj = а_i

Z_iλj = b_j

Z_iλj ≤ d_λ

Z_iλj ≥ 0, , ,

Необходимое и достаточное условие разрешимости задачи

а_i = b_j ≤ d_λ

Преобразуем, введя новые переменные

x_i,n+λ – количество полуфабриката, поступающее из пункта производства А_i в пункт обработки С_λ.

x_m+λ,j - количество полуфабриката, поступающее из пункта обработки С_λ в пункт потребления В_j.

x_i,n+λ = Z_{iλj ,} , .

x_m+λ,j = Z_iλj, , .

В новых переменных задача формулируется так: требуется минимизировать

С_iλ‘x_i,n+λ + С_λj“ x_m+λ,j

при условиях

x_i,n+λ = а_i , ,

x_m+λ,j = b_j ,

x_i,n+λ = x_m+λ,j ≤ d_λ

x_i,n+λ ≥ 0, x_m+λ,j ≥ 0, , , .