Задача 3

Определить оптимальное решение транспортной задачи при следующих начальных условиях (вариант 14) [3, стр. 42].

Таблица 8

Пункты отправления	Пункты назначения										Запасы (ai)
	B1		B2		B3		B4		B5
A1	45		60		40		60		95		90
A2	35		30		55		30		40		50
A3	50		40		35		30		100		30
Потребности (bj)	15		45		45		50		15		170

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

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

(28)

Для определения опорного плана воспользуемся методом северо-западного угла [2, стр. 134]. Результат представлен в таблице 9.

Таблица 9

Пункты отправления	Пункты назначения										Запасы (ai)
	B1		B2		B3		B4		B5
A1	45		60		40		60		95		90
		15		45		30
A2	35		30		55		30		40		50
						15		35
A3	50		40		35		30		100		30
								15		15
Потребности (bj)	15		45		45		50		15		170

Правильность данного плана можно проверить, сложив количество перевозок по строкам и столбцам. При этом для каждой i-ой строки это сумма должна быть равна запасам A_i пункта отправления, а для каждого j-го столбца сумма должна быть равна потребностям B_j пункта отправления.

Общая стоимость перевозок для данного опорного плана равна

(29)

где с_{i j} – стоимость перевозки единицы продукции из i-го пункта отправления в j-ый пункт назначения;

Q_{i j} – объем перевозок из i-го пункта отправления в j-ый пункт назначения.

Узнать о том, является ли этот план оптимальным, можно воспользовавшись методом потенциалов [2, стр. 141].

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

Рассчитаем потенциалы для всех пустых ячеек плана таблицы 9. Для этого сначала составим систему уравнений [2, стр. 144]. Каждое уравнение системы составляется для ячейки с ненулевым объемом перевозки и имеет общий вид

(30)

Число уравнений системы, если опорный план невырожден, всегда равно . Так для опорного плана система примет вид

(31)

Приняв ₁= 0, остальные неизвестные значения системы будут равны

(32)

Теперь рассчитаем потенциал для каждой ячейки с нулевым объемом перевозок по следующей формуле

(33)

Значения  и  берутся из решения (32). Таким образом, потенциалы распределятся так

(34)

Расставив потенциалы (34) по своим позициям в таблице 9, получим таблицу 10.

Таблица 10

Пункты отправления	Пункты назначения										Запасы (ai)
	B1		B2		B3		B4		B5
A1	45		60		40		60	-45	95	-10	90
		15		45		30
A2	35	25	30	45	55		30		40	60	50
						15	-	35	+
A3	50	10	40	35	35	20	30		100		30
							+	15	-	15
Потребности (bj)	15		45		45		50		15		170

В таблице 10 находим ячейку с самым большим положительным потенциалом (это ячейка на пересечении A₂ и B₅). Для данной ячейки необходимо составить цикл – замкнутую ломаную линию, начинающуюся и заканчивающуюся в выбранной нами ячейке и проходящей по заполненным ячейкам. Для выбранной нами ячейки возможен единственный цикл, показанный жирной линией в таблице 10. Данный цикл можно обозначить в координатах так: (2, 5)-(2, 4)-(3, 4)-(3, 5).

Расставим знаки на вершинах цикла. Так на вершине (2, 5) знак плюс, на вершине (2, 4) – знак минус и так далее чередуя знаки. Затем делаем перестановку внутри цикла. Для этого необходимо выбрать минимальную перевозку внутри цикла (это число 15 для нашего цикла) и прибавить или отнять его (зависит от знака ячейки) от объема перевозки каждой ячейки цикла. Проделав эту работу для цикла таблицы 10, переходим к новому опорному плану (таблица 11).

Таблица 11

Пункты отправления	Пункты назначения										Запасы (ai)
	B1		B2		B3		B4		B5
A1	45		60		40		60	-45	95	-70	90
		15	-	45	+	30
A2	35	25	30	45	55		30		40		50
			+		-	15		20		15
A3	50	10	40	35	35	20	30		100	-60	30
								30
Потребности (bj)	15		45		45		50		15		170

Снова пересчитаем потенциалы пустых ячеек. Однако, можно не производить расчеты (32) и (34) второй раз, а только пересчитать ₅. Видно, что исчез один положительный потенциал, однако, новый опорный план тоже не оптимален. Выбираем новый самый большой положительный потенциал (ячейка на пересечении A₂ и B₂). Составив новый цикл и сделав пересчет по циклу, получим опорный план, представленный в таблице 12.

Таблица 12

Пункты отправления	Пункты назначения										Запасы (ai)
	B1		B2		B3		B4		B5
A1	45		60		40		60	0	95	-25	90
		15		30		45
A2	35	-20	30		55	-45	30		40		50
				15				20		15
A3	50	-35	40	-10	35	-25	30		100	-60	30
								30
Потребности (bj)	15		45		45		50		15		170

Пересчитав снова все потенциалы для таблицы 12 по вышеописанной методике, можно обнаружить, что все положительные потенциалы исчезли. Это означает, что мы достигли оптимального решения.

Общая стоимость перевозок для плана таблицы 12 составит

(35)

Отметим, что общая стоимость перевозки уменьшилась на 18,75%.