Транспортные задачи

Пример 1.

Требуется решить транспортную задачу, условия которой, представлены в таблице X.

	Поставщики	Потребители				Запасы груза
		В1	В2	В3	В4
	А1	^2	^6	^3	^1	11
X=	А2	^3	^7	^8	^5	11
	А3	^9	^2	^4	^5	8
	Потребность в грузе	5	9	9	7	30

(Тарифы перевозок выделены синим)

Задача является сбалансированной, так как запасы груза и потребности равны.

1. Построение начального плана перевозок

Действуем по правилу северо-западного угла и получаем:

	ai	bj
		5	9	9	7
X=	11	^7 5Ю	^8 6 Я	^5	^3
	11	^2	^4 3Ю	^5 8 Я	^9
	8	^6	^3	^1 1Ю	^2 7

Находим критерий для начального плана перевозок:

(Количество распределяемого груза выделено красным)

2. Вычисляем потенциалы и оценки следующим образом:

Вводим потенциалы:

Ui - сопоставим пунктам отправления

Vj - сопоставим пунктам назначения

	ai		bj
			5	9	9	7
	U1	11	^7 5	^8 6	^5	^3
X=	U2	11	^2	^4 3	^5 8	^9
	U3	8	^6	^3	^1 1	^2 7
			V1	V2	V3	V4

Для базисных клеток выполняется равенство Vj-Ui=Cij, эта система содержит m+n-1 равенство. Первоначально любой из вершин U или V присваиваем любое значение, остальные U и V вычисляются из (1).

V₁-U₁=7 U₁=0;V₁=7; V₂-U₁=8 V₂=8;

V₂-U₂=4 U₂=4; V₃-U₂=5 V₃=9;

V₃-U₃=1 U₃=8; V₄-U₃=2 V₄=10;

Находим оценки для небазисных клеток:

D₁₃=V₃-U₁-C₁₃=9-0-5=4 D₁₄=V₄-U₁-C₁₄=10-0-3=7

D₂₁=V₁-U₂-C₂₁=7-4-2=1 D₂₄=V₄-U₂-C₂₄=10-4-9= -3

D₃₁=V₁-U₃-C₃₁=7-8-6= -7 D₃₂=V₂-U₃-C₃₂=8-8-3= -3

Строим матрицу оценок для начального плана перевозок D₁:

0	0	4	7
1	0	0	-3
-7	-3	0	0

Так как есть положительные оценки, то план не является оптимальным.

3. Строим цикл пересчета в матрице X на клетке kr.

Строим замкнутый цикл, вершины которого, принадлежат базисным клеткам. Строить начинаем из клетки kr, значение которой является максимальным в матрице D₁ , это будет значение 7 в клетке 1,4 (выделена зеленым). Нумерацию вершин производим так, чтобы выделенная клетка была четной.

(цепь выделена красным, первоначальная вершина *)

	ai	bj
		5	9	9	7
X=	11	^7 5	^8 6 Я	^5	^3 Ь*
	11	^2	^4 3Ю	^5 8 Я	^9
	8	^6	^3	^1 1Ю	^2 Э 7

Далее, двигаясь по циклу, посчитаем q₁=min(Xij ), XijОнечетным,

Получится q₁=min(6,8,7)=6.

4. Строим новую матрицу X из старой.

Двигаемся по циклу и прибавляем q₁ к четным вершинам и вычитаем из нечетных, получим:

	ai	bj
		5	9	9	7
X1=	11	^7 5	^8	^5	^3 6
	11	^2	^4 9	^5 2	^9
	8	^6	^3	^1 7	^2 1

Критерий L_k=L_k-1-q_k-1* maxDij;

L₁=150-6*7=108

5. Строим новую матрицу D путем преобразования из предыдущей:

1) Отмечаем элементы являющиеся базисными в новом решении, максимальный элемент выделяем особо.

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

3) К выделенным столбцам прибавляем выделенный элемент, из выделенных строк – вычитаем.

(базисные в новом X отмечены жирным курсивным шрифтом, красным отмечены выделенные строки и столбцы)

Итерация 2

	0	0	4	7	-7		0	-7	-3	0
D1=	1	0	0	-3		D2=	8	0	0	-3
	-7	-3	0	0			0	-3	0	0
	+7

Повторяем пункт 3:

	ai	bj
		5	9	9	7
X2=	11	^7 5Ю	^8	^5	^3 6 Я
	11	^2 Э ^*	^4 9	^5 Ь2	^9
	8	^6	^3	^1 Э 7	^2 Ь1

q₂=min(5,1,2)=1.

Повторяем пункт 4:

	ai	bj
		5	9	9	7
X2=	11	^7 4	^8	^5	^3 7
	11	^2 1	^4 9	^5 1	^9
	8	^6	^3	^1 8	^2

Критерий L₂=108-1*8=100

Далее повторяем пункты 5, 3, 4 до тех пор, пока все значения матрицы D будут не положительны.

Итерация 3

	0	-7	-3	0			0	1	5	0
D2=	8	0	0	-3	-8	D3=	0	0	0	-11
	0	-3	0	0			0	-3	0	-8
		+8	+8

	ai	bj
		5	9	9	7
X2=	11	^7 4 Я	^8	^5 Ь*	^3 7
	11	^2 1Ю	^4 9	^5 Э 1	^9
	8	^6	^3	^1 8	^2

q₃=min(4,1)=1

	ai	bj
		5	9	9	7
X2=	11	^7 3	^8	^5 1	^3 7
	11	^2 2	^4 9	^5	^9
	8	^6	^3	^1 8	^2

Критерий L₃=100-1*5=95

Итерация 4

	0	1	5	0	-5		0	1	0	0
D3=	0	0	0	-11	-5	D4=	0	0	-5	-11
	0	-3	0	-8			-3	2	0	-3
	+5	+5		+5

+

	ai	bj
		5	9	9	7
X3=	11	^7 3Ю	^8	^5 1 Я	^3 7
	11	^2 Э 2	^4 Ь9	^5	^9
	8	^6	^3 Э *	^1 Ь8	^2

q₄=min(8,3,9)=3

	ai	bj
		5	9	9	7
X3=	11	^7	^8	^5 4	^3 7
	11	^2 5	^4 6	^5	^9
	8	^6	^3 3	^1 5	^2

Критерий L₄=95-3*2=89

Итерация 5

	0	1	0	0	-2		-2	-1	0	-2
D4=	0	0	-5	-11		D5=	0	0	-5	-11
	-3	2	0	-3	-2		-5	0	0	-5
			+2	+2

Все элементы матрицы D₅ неположительны, следовательно, на 4ой итерации получили искомое решение X_4.

Пример 2.

Требуется решить транспортную задачу, условия которой, представлены в таблице X.

	Поставщики	Потребители			Запасы груза
		В1	В2	В3
	А1	^5	^7	^6	50
X=	А2	^6	^6	^5	40
	А3	^8	^4	^5	20
	Потребность в грузе	18	21	33

Предыдущая задача была сбалансирована в ней

Эта же задача не сбалансирована, так как, в ней присутствует избыток запасов.

Как решать такую задачу ?

1. Находим разницу между запасами и заявками

.

2. Вводим фиктивный пункт отправления, которому припишем фиктивную заявку равную избытку запасов, а стоимости перевозок сделаем равными нулю, получим:

	Поставщики	Потребители				Запасы груза
		В1	В2	В3	В4
	А1	^5	^7	^6	^0	50
X=	А2	^6	^6	^5	^0	40
	А3	^8	^4	^5	^0	20
	Потребность в грузе	18	21	33	38	110

3. Так как мы свели задачу к сбалансированной, далее решаем, как и предыдущую:

Итерация 1

	ai	bj
		18	21	33	38
X=	50	^5 18Ю	^7 21Ю	^6 11 Я	^0
	40	^6	^6	^5 22Ю	^0 18 Я
	20	^8	^4	^5	^0 20

Вычисляем потенциалы:

V₁-U₁=5 U₁=0;V₁=5 V₂-U₁=7 V₂=7+U₁=7

V₃-U₁=6 V₃=6+U₁=6 V₃-U₂=5 U₂=V₃-5=1

V₄-U₂=0 V₄=0+1=1 V₄-U₃=0 U₃=V₄-0=1

Находим оценки для небазисных вершин:

D₁₄=V₄-U₁-C₁₄=1-0-0=1 D₂₁=V₁-U₂-C₂₁=5-1-6= -2

D₂₂=V₂-U₂-C₂₂=7-1-6=0 D₃₁=V₁-U₃-C₃₁=5-1-8= -4

D₃₂=V₂-U₃-C₃₂=7-1-4=2 D₃₃=V₃-U₃-C₃₃=6-1-5=0

Матрица D₁ имеет вид:

0	0	0	1
-2	0	0	0
-4	2	0	0

Построим цикл пересчета:

	ai	bj
		18	21	33	38
X=	50	^5 18	^7 20Ю	^6 11 Я	^0
	40	^6	^6	^5 22Ю	^0 18 Я
	20	^8	^4 Э *	^5	^0 Ь20

q₁=min(21,22,20)=20.

	ai	bj
		18	21	33	38
X1=	50	^5 18	^7 1	^6 31	^0
	40	^6	^6	^5 2	^0 38
	20	^8	^4 20	^5

Итерация 2

Строим новую матрицу D:

	0	0	0	1			0	0	0	1
D1=	-2	0	0	0		D2=	-2	0	0	0
	-4	2	0	0	-2		-6	0	-2	-2

	ai	bj
		18	21	33	38
X1=	50	^5 18	^7 1	^6 31 Я	^0 Ь*
	40	^6	^6	^5 2Ю	^0 Э 38
	20	^8	^4 20	^5

q₂=min(31,38)=31

	ai	bj
		18	21	33	38
X2=	50	^5 18	^7 1	^6	^0 31
	40	^6	^6	^5 33	^0 7
	20	^8	^4 20	^5

Итерация 3

	0	0	0	1	-1		0	0	-1	0
D2=	-2	0	0	0		D3=	-1	1	0	0
	-6	0	-2	-2	-1		-6	0	-3	-3
	+1	+1

	ai	bj
		18	21	33	38
X2=	50	^5 18	^7 1Ю	^6	^0 31 Я
	40	^6	^6 Э *	^5 33	^0 Ь7
	20	^8	^4 20	^5

q₃=min(1,7)=1

	ai	bj
		18	21	33	38
X3=	50	^5 18	^7	^6	^0 32
	40	^6	^6 1	^5 33	^0 6
	20	^8	^4 20	^5

Итерация 4

	0	0	-1	0	-1		0	-1	-2	0
D3=	-1	1	0	0	-1	D4=	-1	0	-1	0
	-6	0	-3	-3	-1		-6	-1	-4	-3
	+1			+1

Все элементы матрицы D₄ неположительны, следовательно, на 4ой итерации получили искомое решение X_3.