Методы линейного программирования для решения транспортной задачи

 

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

i j	1		2		3		4		5		6		7
1	М		7		8		10		3		14		20
2	7		М		4		10		9		15		21
3	8		4		М		6		5		11		17
4	10		10		6		М		7		8		14
5	3		8		5		7		М		6		12
6	14		14		11		8		6		М		6
7	20		20		17		14		12		6		М

 

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

i j		1		2		3		4		5	6	7
1		М		4		5		7		0	11	17		3
2		3		М		0		6		5	11	17		4
3		4		0		М		2		1	7	13		4
4		4		4		0		М		1	2	8		6
5		0		5		2		4		М	3	9		3
6		8		8		5		2		0	М	0		6
7		14		14		11		8		6	0	М		6

 

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

i j 1 2 3 4 5 6 7 1 М 4 5 5 0 11 17 2 3 М 0 4 5 11 17 3 4 0 М 0 1 7 13 4 4 4 0 М 1 2 8 5 0 5 2 2 М 3 9 6 8 8 5 0 0 М 0 7 14 14 11 6 6 0 М   0 0 0 2 0 0 0

 

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

Сумма констант приведения определяет нижнюю границу H:

H = ∑ + ∑ = 3+4+4+6+3+6+6+0+0+0+2+0+0+0 = 34

Шаг №1

Определяем ребро ветвления  и разобьем все множество маршрутов  относительно этого ребра на два  подмножества (i,j) и (i*,j*).

Для каждого нулевого элемента рассчитаем значение , равное сумме наименьшего элемента i строки и наименьшего элемента j столбца.

i j	1		2		3		4		5	6		7
1	М		4		5		5		0(4)	11		17	4
2	3		М		0(3)		4		5	11		17	3
3	4		0(4)		М		0(0)		1	7		13	0
4	4		4		0(1)		М		1	2		8	1
5	0(2)		5		2		2		М	3		9	2
6	8		8		5		0		0(0)	М		0(8)	0
7	14		14		11		6		6	0(8)		М	6
	3		4		0		0		0	2		8

 

Из этой таблицы видно, что наибольшая сумма констант приведения равна  8 для ребра (6,7). Это означает, что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.

Следовательно, множество разбивается на два подмножества (6,7) и (6*,7*). Нижняя граница гамильтоновых циклов этого подмножества:

H(6*,7*) = 34 + 8 = 42

Удалим из матрицы строку 6 и столбец 7, в которой присвоим элементу (7,6) значение бесконечности (М), чтобы избежать преждевременного замыкания контура (для исключения образования негамильтонова цикла).

В результате получим другую сокращенную матрицу (6 x 6), которая подлежит операции приведения.

i j	1		2		3		4		5		6
1	М		4		5		5		0		11		0
2	3		М		0		4		5		11		0
3	4		0		М		0		1		7		0
4	4		4		0		М		1		2		0
5	0		5		2		2		М		3		0
7	14		14		11		6		6		М		6
	0		0		0		0		0		2		8

 

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 2+6 = 8

Нижняя граница подмножества (6,7) равна:

H(1,6) = 34 + 8 = 42 

42 =  42

Ребро (6,7) в любом случае должно быть включено в маршрут, так  как только через пункт 6 можно  добраться в пункт 7 и обратно.

 

Шаг №2

Найдем минимальные элементы в каждой строке и в столбце новой матрицы  и сразу вычтем их из остальных элементов строки и столбцов.

Получим матрицу представленную ниже.

i j		1		2		3		4		5		6
1		М		4		5		5		0		9
2		3		М		0		4		5		9
3		4		0		М		0		1		5
4		4		4		0		М		1		0
5		0		5		2		2		М		1
7		8		8		5		0		0		М

Определяем ребро ветвления  и разобьем все множество маршрутов  относительно этого ребра на два  подмножества (i,j) и (i*,j*).

Для каждого нулевого элемента рассчитаем значение , равное сумме наименьшего элемента i строки и наименьшего элемента j столбца.

ij		1	2		3		4		5		6
1		М	4		5		5		0(4)		9	4
2		3	М		0(3)		4		5		9	3
3		4	0(4)		М		0(0)		1		5	0
4		4	4		0(0)		М		1		0(1)	0
5		0(4)	5		2		2		М		1	1
7		8	8		5		0(0)		0(0)		М	0
		3	4		0		0		0		1

 

В результате сравнения мы получили 3 одинаковых максимальных Г=4 для ребер (1,5), (3,2) и (5,1). Это означает, что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Для начала рассмотрим ребро (1,5).

Следовательно, множество разбивается на два подмножества (1,5) и (1*,5*). Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,5*) = 42 + 4 = 46

Удалим из матрицы строку 1 и столбец 5, в которой присвоим элементу (5,1) значение бесконечности (М), чтобы избежать преждевременного замыкания контура (для исключения образования негамильтонова цикла).

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.

 

i j		1		2			3			4			6
2		3		М			0			4			9		0
3		4		0			M			0			5		0
4		4		4			0			M			0		0
5		M		5			2			2			1		1
7		8		8			5			0			M		0
		3		0			0			0			0		4

 

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1+3 = 4

Нижняя граница подмножества (1,5) равна:

H(1,5) = 42 + 4 = 46 

46 =  46

Ребро (1,5) включаем в маршрут, так как подмножество (1,5) не превысило подмножество (1*,5*).

 

Шаг №3

Найдем минимальные элементы в каждой строке и в столбце новой матрицы  и сразу вычтем их из остальных элементов строки и столбцов.

Получим матрицу представленную ниже.

ij		1	2		3		4		6
2		0	M		0		4		9
3		1	0		M		0		5
4		1	4		0		M		0
5		M	4		1		1		0
7		5	8		5		0		M