Транспортировка в логистике

 

Нижняя  граница, то есть минимально возможная  длина маршрута, определяется по формуле (5):

                                (5)

где  hi, hj – константы приведения соответственно по строкам и столбцам.

= 33+3 =36

Для нулевых  элементов матрицы, приведенной в табл. 15.3, определим оценки Q_ij, которые проставим в правом нижнем углу соответствующей ячейки.

 при условии: k ¹ j; s ¹ i; k, s = 1, 2, …, n,

где  l'_ik – наименьшее значение элемента в строке i;

l''_sj – наименьшее значение элемента в столбце j.

Таблица 15.4

Расчет  оценок для нулевых элементов

	Б	1	3	4	5	7
Б	∞	13	3	5	0(0)	0(0)
1	13	∞	4	4	9	0(4)
3	3	4	∞	2	1	0(1)
4	5	4	2	∞	0(0)	0(0)
5	0(0)	9	1	0(0)	∞	4
7	0(0)	0(4)	0(0)	0(0)	4	∞

 

В табл.15.4 получили 2 максимальные оценки равные 4. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 1-7. Таким образом, исключаем из дальнейшего рассмотрения строку k = 2 и столбец s = 7.

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

 

Таблица 15.5

Приведение  матрицы, усеченной на строку 2 и столбец 7

	Б	1	3	4	5	hi
Б	∞	13	3	5	0(0)	0
3	3	4	∞	2	1	1
4	5	4	2	∞	0(0)	0
5	0(0)	9	1	0(0)	∞	0
7	0(0)	∞	0(0)	0(0)	4	0
hj	0	3	0	0	0	∑ = 4

 

От начальной  вершины проводим ответвление вершин ks и   _{с нижними границами:}

Графическое изображение полученного решения приведено на рис. 3.1.

_{Рисунок 3.1}

Первое  ветвление «дерева решений» для  метода «ветвей и границ»

                   (40)             1-7 (40)

 

Далее производим приведение матрицы по строкам и столбцам и находим оценки для нулевых элементов, (табл.15.6):

Таблица 15.6

Определение оценок нулевых элементов для  усеченной матрицы

	Б	1	3	4	5
Б	∞	13	3	5	0(3)
3	2	0(1)	∞	1	0(0)
4	5	1	2	∞	0(0)
5	0(0)	6	1	0(0)	∞
7	0(0)	∞	0(1)	0(0)	4

В табл.15.6 получили максимальную оценку равную 3. Ветвь маршрута будет 3-5. Таким образом, исключаем из дальнейшего рассмотрения строку k = Б и столбец s = 5.

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

Таблица 15.7

Приведение  матрицы, усеченной на строку 3 и столбец 5

	Б	1	3	4	hi
3	2	0(1)	∞	1	0
4	5	1	2	∞	1
5	∞	6	1	0(0)	0
7	0(0)	∞	0(1)	0(0)	0
					∑ = 1

 

Таким образом, от вершины (1 – 7) проводим ответвление вершин ks и   _{с нижними границами:}

Графическое изображение полученного решения приведено на рис. 3.2

_{Рисунок 3.2}

Второе  ветвление «дерева решений» для  метода «ветвей и границ»

                   (40)            1 – 7 (40)

                           (43)          Б – 5 (41)

 

Далее производим приведение матрицы по строкам и столбцам и находим оценки для нулевых элементов, (табл.15.8):

 

Таблица 15.8

Определение оценок нулевых элементов для  усеченной матрицы

	Б	1	3	4
3	2	0(1)	∞	1
4	4	0(1)	1	∞
5	∞	6	1	0(1)
7	0(2)	∞	0(1)	0(0)

 

В табл.15.8 получили максимальную оценку равную 2. Ветвь маршрута будет 7 – Б. Таким образом, исключаем из дальнейшего рассмотрения строку k = 7 и столбец s = Б.

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

Таблица 15.9

Приведение  матрицы, усеченной на строку 7 и  столбец Б

	1	3	4
3	0(1)	∞	1
4	0(1)	1	∞
5	6	1	0(1)
hj		1		∑ = 1

 

От вершины (Б – 5) проводим ответвление вершин ks и   _{с нижними границами:}

Графическое изображение полученного решения приведено на рис. 3.3

 

 

 

 

_{Рисунок 3.3}

Третье  ветвление «дерева решений» для  метода «ветвей и границ»

                   (40)            1 – 7 (40)

                             (43)       Б – 5 (41)

                                  (43)             7 – Б (42)

 

Далее производим приведение матрицы по строкам и  столбцам и находим оценки для нулевых элементов, (табл.15.10):

Таблица 15.10

Определение оценок нулевых элементов для  усеченной матрицы

	1	3	4
3	0(1)	∞	1
4	0(0)	0(0)	∞
5	6	0(0)	0(1)

 

В табл. 15.10 получили 2 максимальные оценки равные 1. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 5–4. Таким образом, исключаем из дальнейшего рассмотрения строку k = 5 и столбец s = 4.

От вершины (7 – Б) проводим ответвление вершин ks и     с нижними границами:

Графическое изображение полученного решения  приведено на рис. 3.4

 

Рисунок 3.4

Четвертое ветвление «дерева решений» для  метода «ветвей и границ»

(40)           1 – 7 (40)

         (43)           Б – 5 (41)

                  (43)            7 – Б (42)

                            (43)           5 – 4 (42)

 

Получаем  матрицу 2х2, в которой однозначно представлены две последние «ветки» маршрута, (табл.15.11):

Таблица 15.11

Матрица 2х2 для метода «ветвей и границ»

	1	3
3	0(1)	∞
4	∞	0(0)

 

При этом «дерево решений» примет окончательный  вид, который проиллюстрирован на рис. 3.5.

 

Рисунок 3.5

«Дерево решений» для грузоотправителя Б на маршруте Б1

 

 

 

 

 

 

 

 

 

 

Маршрут Б1: Б – 5 – 4 – 3 – 1 – 7 – Б

Протяженность маршрута: 5+7+10+10+5+5 = 42 (км)

 

Маршрут «Б2»

Для грузоотправителя Б построим матрицу кратчайших расстояний (табл. 16.1), используя предварительно рассчитанные расстояния между пунктами (табл.1):

Таблица 16.1

Матрица кратчайших расстояний для маршрута «Б2»,приведенная по строкам

	Б	8	9	10	hi
Б	∞	9	11	13	9
8	9	∞	2	6	2
9	11	2	∞	4	2
10	13	6	4	∞	4
					∑ = 17