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

Двухэтапную транспортную задачу легко свести к классической транспортной задаче. Для этого базы будем считать одновременно поставщиками и потребителями. Для каждой базы в расширенной матрице (поставщики+базы) — (потребители+базы) отведем строку и столбец. Тогда матрица тарифов будет состоять из четырех блоков

(табл. 5).

В первом — левом верхнем блоке будем отражать связи поставщиков с базами, в четвертом — связи баз с потребителями. Второй — правый верхний блок показывает связи поставщиков с потребителями. Поскольку по условию задачи непосредственные перевозки от поставщиков к потребителям запрещены, то в этом блоке все тарифы считают равными М (где М — большое число). Третий — левый нижний блок образуется по строкам и столбцам базами, имеет форму квадрата. Так как перевозки между базами запрещаются, то соответствующие показатели также считают равными М. В клетках третьего квадрата, в которых отражаются связи базы с самой собой, тарифы равны нулю. Поставки в этих клетках показывают величину неиспользованной мощности базы. Диагональ из нулевых тарифов, отражающая связи базы с самой собой, называется фиктивной.

								Таблица 5
	Поставщики				Потребители и их объемы
		Мощности	D1	…	Dp	B1	…	Bn
			d1	…	d p	b1	…	bn
	A1	a1		I			II
	M	M					М
				(cik )m×p
	Am	am
	D1	d1	0	III	М		IV
	M	M	M	…	M		(ckj ) p×n
			М	…	0
	Dp	d p

10

Решение двухэтапной транспортной задачи имеет некоторые особенности. Основная из них — некоторое изменение нахождения базисного решения. Вначале необходимо распределить поставки в одном из. блоков (первом или четвертом). Затем заполняется фиктивная диагональ, и только потом распределяются поставки в другом блоке (четвертом или первом). Вторая особенность заключается в том, что если цикл пересчета проходит через фиктивную диагональ, то он обязательно проходит через нее дважды; одна вершина цикла, находящаяся на диагонали, будет всегда положительной, а другая — отрицательной.

Пример 1.2. В некотором районе имеется два маслодельных завода A1 , A2 . Сливочное масло поступает сначала в холодильники

D1, D2 , D3 , а из них — в пункты потребления B1 , B2 , B3 , B4 .

Возможности маслодельных заводов, мощность холодильников, запросы потребителей и соответствующие тарифы представлены в табл. 6.

				Таблица 6
Поставки	Объем	Пропускная	Тариф cik	Тариф ckj
производства	потребления	способность
ai , т	b j , т	ППП dk , т
350	150	240	20, 23, 16	17, 22, 20, 13
450	250	500	15, 10, 24	20, 25, 24, 22
	175
	225	260		16, 21, 25, 11

	m	n
Решение.	Так как ∑ai = ∑bj =800 ,		то	можно	решать
	i=1	j=1
				m	n
двухэтапную	транспортную	задачу (табл.	7).	(При ∑ai ≠ ∑b j
				i=1	j=1

следует ввести фиктивного поставщика или фиктивного потребителя.)

11

Таблица 7

	Поставщик	Мощности			Поставщики и их объемы
			D1	D2	D3	B1	B2	B3	B4
			240	500	260	150	250	175	225
	A1	350	20	23	16	М	М	М	М
			75	50	225
	A2	450	15	10	24	М	М	М	М
				450
	D1	240	0	М	М	12	19	20	13
			165				75
	D2	500	М	0	М	10	15	14	12
						150	175	175
	D3	260	М	М	0	16	21	25	11
					35				225

Начальный опорный план, приведенный в табл. 7, найден способом минимального элемента, причем распределение начато с четвертого блока. Затем заполнялась фиктивная диагональ и, наконец, первый блок. Оптимальный план (не единственный) представлен в табл. 8: zmin =10600+10425=21025 руб. Интересно отметить, что если

решать задачу в два этапа, т. е. находить сначала оптимальный план прикрепления поставщиков к холодильникам, а затем задачу оптимального прикрепления холодильников к потребителям, то суммарные потери составят zmin =10460+14810=25350 руб., т. е.

возрастут, хотя на первом этапе издержки уменьшатся.

Таблица 8

Поставщик	Мощности	Поставщики и их объемы

		D1	D2	D3	B1	B2	B3	B4
		240	500	260	150	250	175	225
A1	350	20	23	16	М	М	М	М
		125		225
A2	450	15	10	24	М	М	М	М
			450
D1	240	0	М	М	12	19	20	13
		115			125

12