4.6. Алгоритм решения транспортной задачи методом потенциалов

приведемалгоритм метода потенциалов:

1. Условие задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас продукта с суммарным спросом и в случае нарушения равенства (18) вводят фиктивного поставщика (потребителя).

3. Строят начальный опорный план по одному из правил.

4. Вычисляют потенциалы поставщиков и потребителей u_iиv_j , решив систему уравнений типа (21).

5. Вычисляют оценки S_ij для всех свободных клеток по формуле (22). Если оценки всех свободных клеток неотрицательны, то исследуемый план является оптимальным, и остается подсчитать транспортные расходы. Если же среди оценок есть отрицательные, то выбирают клетку с наименьшей отрицательной оценкой и переходят к следующему пункту алгоритма.

6. Загружают выделенную в предыдущем пункте свободную клетку (пункт 4.5), получают новый опорный план и возвращаются к пункту 4 алгоритма.

Пример 8.Решить транспортную задачу методом потенциалов, для которой известно, чтоa_i– запас грузаi-го поставщика,b_j– потребностьj-го потребителя,C= (c_ij) – матрица затрат на перевозку одной единицы груза:

a1 = 12; a2 = 3; a3 = 10;

b1 = 14; b2 = 10; b3 = 6;

.

Решение

Поместим все данные задачи в табл. 14.

Таблица 14

bj	14	10	6
ai
	1	0	2
12
	3	4	1
3
	4	6	5
10

Проверим, сколько единиц однородного продукта содержат поставщики (12 + 3 + 10 = 25) и сколько единиц однородного продукта нужно доставить потребителям (14 + 10 + 6 = 30).

Так как 25 < 30, т. е. , то имеемоткрытую модельтранспортной задачи.

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

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

.

Все тарифы на доставку продукта фиктивным поставщиком равны нулю: .

Имеем ТЗ закрытого типа, которую решаем методом потенциалов (табл. 15).

Построим первоначальный (опорный) план методом “минимального элемента” (табл. 16).

Таблица 15

bj	14		10	6
ai
		1	0		2
12
		3	4		1
3
		4	6		5
10
		0	0		0
5

Таблица 16

bj	14		10		6
ai
		1		0		2
12		7		5
		3		4		1
3						3
		4		6		5
10		7				3
		0		0		0
5				5

В результате получаем матрицу перевозок

План X₁является невырожденным (m+n– 1 = 4 + 3 – 1 = 6). Общая стоимость перевозки грузов по этому плану составит

z₁= 17 + 05 + 13 + 47 + 53 + 05 = 53.

Потенциалы поставщиков и потребителей определены непосредственно на рис. 8.

	14	10	6
	1	0	2
12	7 –	5 +
	3	4	1
3			3
	4	6	5
10	7 +		3 –
	0	0	0
5		5 –	 +

Рис. 8

Имеют место следующие оценки свободных клеток:

S13 = 2 – (–3 + 5) = 0;	S32 = 6 – (0 + 3) = 3 > 0;
S21 = 3 – (– 4 + 4) = 3 > 0;	S41 = 0 – (–3+ 4) = –1 < 0;
S22 = 4 – (– 4 + 3) = 5 > 0;	S43 = 0 – (–3 + 5) = –2 < 0.

Так как S₄₁< 0 иS₄₃< 0, то план является неоптимальным. Наиболее потенциальной и перспективной является клетка (4; 3). Строим для клетки (4; 3) цикл непосредственно на рис. 8. В цикл войдут клетки (4; 3), (3; 3), (3; 1), (1; 1), (1; 2), (4; 2). Проставим знаки “+” и “–” в цикле поочередно, начиная со свободной клетки. Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, – . В результате смещения по циклу получим новый план (рис. 9).

Для этого плана определяем новые потенциалы и оценки свободных клеток:

S13 = 2 – (0 + 0) = 2 > 0;	S32 = 6 – (3 + 0) = 3 > 0;
S21 = 3 – (1 + 1) = 1 > 0;	S33 = 5 – (3 + 0) = 2 > 0;
S22 = 4 – (1 + 0) = 3 > 0;	S41 = 0 – (0 + 1) = –1 < 0.

	14	10	6
	1	0	2
12	4 –	8 +		u1 = 0
	3	4	1
3			3	u2 = 1
	4	6	5
10	10			u3 = 3
	0	0	0
5	+ 	2 –	3	u4 = 0
	v1 = 1	v2 = 0	v3 = 0

Рис. 9

Так как S₄₁< 0, то план является неоптимальным. Строим для клетки (4; 1) цикл непосредственно на рис. 9. В цикл войдут клетки (4; 1), (1; 1), (1; 2), (4; 2). Проставим знаки в цикле. В отрицательных вершинах построенного для клетки (4; 1) цикла наименьшее количество груза – .

После смещения по циклу 2 единиц груза получим новый план перевозок (рис. 10).

	14	10	6
	1	0	2
12	2	10		u1 = 0
	3	4	1
3			3	u2 = 0
	4	6	5
10	10			u3 = 3
	0	0	0
5	2		3	u4 = –1
	v1 = 1	v2 = 0	v3 = 1

Рис. 10

Как и для предыдущего плана перевозок, все потенциалы поставщиков и потребителей определены на рис. 10. Имеют место следующие оценки свободных клеток:

S13 = 2 – (0 + 1) = 1 > 0,	S32 = 6 – (3 + 0) = 3 > 0,
S21 = 3 – (0 + 1) = 2 > 0,	S33 = 5 – (3 + 1) = 1 > 0,
S22 = 4 – (0 + 0) = 4 > 0,	S42 = 0 – (–1 + 0) = 1 > 0.

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

.

значение целевой функции составит

(усл. ед.).

Загрузка x₄₁= 2 иx₄₃= 3 для фиктивного поставщика указывает на остаток нераспределенного груза в размере 5 ед. у потребителейB₁иB₃.

Ответ: усл. ед.