Транспортна задача

 

Таблица 2.6 Таблица весов нулевых  элементов

Звено (i,j)	(1,7)	(2,3)	(2,8)	(3,2)	(4,3)	(4,8)	(5,8)	(6,7)	(7,1)	(7,6)
Фi=Ai+Bi	55	35	40	10	35	40	65	55	40	40
Звено (i,j)	(8,2)	(8,4)	(8,5)
Фi=Ai+Bi	35	35	35

 

Самый тяжёлый нуль стоит в ячейке (5, 8), следовательно, множество решений  разбивается на и .

Заменим элемент (8, 5) на ∞ и удалим из таблицы строку с номером 5 и столбец 8.

 

Таблица 2.7 Преобразованная матрица

lij	1	2	3	4	5	6	7
1	∞	75	∞	∞	∞	5	0
2	90	∞	0	5	∞	∞	55
3	∞	0	∞	5	∞	∞	∞
4	∞	5	0	∞	40	∞	∞
6	5	∞	∞	∞	50	∞	0
7	0	40	∞	∞	40	0	∞
8	∞	0	∞	0	∞	∞	50

 

Вторая итерация

Выполним редукцию Столбцов, так  как редукцию строк проводить  не имеет смысла:

Таблица 2.8 Редукция столбцов во второй итерации

lij	1	2	3	4	5	6	7	ci
1	∞	75	∞	∞	∞	5	0	0
2	90	∞	0	5	∞	∞	55	0
3	∞	0	∞	5	∞	∞	∞	0
4	∞	5	0	∞	0	∞	∞	0
6	5	∞	∞	∞	50	∞	0	0
7	0	40	∞	∞	0	0	∞	0
8	∞	0	∞	0	∞	∞	50	0
qj	0	0	0	0	40	0	0	H=40

 

Проверка:

Решение не оптимально, поэтому потребуется  ещё одна итерация.

` Выберем следующее звено.

 

Таблица 2.9 Редуцированная матрица с ячейками под вторичные штрафы

lij	1	2	3	4	5	6	7	ci	Ai
1	∞	75	∞	∞	∞	5	0	0	5
2	90	∞	0	5	∞	∞	55	0	5
3	∞	0	∞	5	∞	∞	∞	0	5
4	∞	5	0	∞	0	∞	∞	0	5
6	5	∞	∞	∞	50	∞	0	0	5
7	0	40	∞	∞	0	0	∞	0	40
8	∞	0	∞	0	∞	∞	50	0	50
qj	0	0	0	0	40	0	0	H=40	-
Bj	5	5	0	5	50	0	50	-	-

 

Таблица 2.10 Таблица весов нулевых  элементов

Звено (i,j)		(1,7)			(2,3)		(3,2)		(4,5)		(6,7)	(7,1)	(7,5)
Фi=Ai+Bi		55			5		10		55		55	45	90
Звено (i,j)	(7,6)		(8,2)	(8,4)		(4,3)		(7,6)
Фi=Ai+Bi	40		55	55		5		40

Самый тяжёлый нуль находится в  ячейке (7, 5), следовательно, подмножество решений (5, 8) разбивается на и .

Удалим из таблицы строку с номером 7 и столбец 5.

Таблица 2.11 Преобразованная матрица

lij	1	2	3	4	6	7
1	∞	75	∞	∞	5	0
2	90	∞	0	5	∞	55
3	∞	0	∞	5	∞	∞
4	∞	5	0	∞	∞	∞
6	5	∞	∞	∞	∞	0
8	∞	0	∞	0	∞	50

 

 

Третья итерация

Выполним редукцию столбцов, так как редукцию строк проводить не имеет смысла:

Таблица 2.12 Редукция столбцов в третьей  итерации

lij	1	2	3	4	6	7	ci
1	∞	75	∞	∞	0	0	0
2	85	∞	0	5	∞	55	0
3	∞	0	∞	5	∞	∞	0
4	∞	5	0	∞	∞	∞	0
6	0	∞	∞	∞	∞	0	0
8	∞	0	∞	0	∞	50	0
qj	5	0	0	0	5	0	H=10

 

Проверка:

Решение не оптимально, поэтому потребуется  ещё одна итерация.

` Выберем следующее звено.

Таблица 2.13 Редуцированная матрица  с ячейками под вторичные штрафы

lij	1	2	3	4	6	7	ci	Ai
1	∞	75	∞	∞	0	0	0	75
2	85	∞	0	5	∞	55	0	55
3	∞	0	∞	5	∞	∞	0	5
4	∞	5	0	∞	∞	∞	0	5
6	0	∞	∞	∞	∞	0	0	0
8	∞	0	∞	0	∞	50	0	50
qj	5	0	0	0	5	0	H=10	-
Bj	85	5	0	5	0	50	-	-

 

Таблица 2.14 Таблица весов нулевых  элементов

Звено (i,j)		(1,6)			(1,7)	(2,3)	(3,2)	(4,3)	(6,1)	(6,7)
Фi=Ai+Bi		75			125	55	10	5	85	50
Звено (i,j)	(8,2)		(8,4)
Фi=Ai+Bi	80		55