Решение задачи развозки мелкопартионных

грузов методом «ветвей и границ»

Метод ветвей и границ впервые был использован для решение задачи «странствующего коммивояжера»,которая заключается в том, что коммивояжер выезжает из одного пункта транспортной сети и, посещая все е1 вершины только один возвращается в начальный пункт

Составление исходной матрицы

Расстояние равно 30

3 3

2 20

1 3 2 10 4 1

13

6 4

Граф транспортной сети Оптимальный маршрут движения

Рис.2.1

Решим задачу транспортной сети из пяти пунктов показной на рис.2.1.Требуется доставить груз в каждый пункт, чтобы общий пробег был наименьшим. Исходная матрица расстояний приведена в таблице 2.1.Расчёт производим в табличной форме в несколько этапов.

Таблица 2.1

№

Первый этап вычисления начнём с получение приведенной матрицы в таблице 2.3матрицы по минимальному расстоянию. Для этого из каждой элемента строки вычитаем наименьший элемент(табл 2.2).Далее в полученной новой матрице вычитаем из каждого элемента столбца его наименьший элемент(табл 2.3)За пределами табл.3.3 справа указаны вычитаемые минимальные элементы строки, а внизу минимальные элементы столбца.

Таблица 2.2 Таблица 2.3

№

№

2 2

3 3

2 2

4 4

4 4

На втором этапе производится оценка всех полученных нулевых элементов в таблице 2.3.Она равна сумме наименьших величин в строке и в столбце, на пересечение которых находится 0.Оценка проводится в правом верхнем углу ячейки.

На третьем этапе вычёркиваем нулевой элемент с наибольшей оценкой; он в включается в маршрут.(таблица 2.4)

Вычёркиваем элемент 1-3.Потомучто максимальная оценка элемента 1-3

После вычёркивания элемента с наибольшей оценкой получена новая матрица которая приведена в таблице 2.5

На четвертом этапе в новой матрице вычитаем наименьшей элемент строки и столбца. Наименьшие элементы строк 0, а наименьшие элементы столбцов указаны снизу таблицы 2.5.Далеее проводим оценку нулевых элементов. Оценка нулевых элементов показана в таблице 2.5.Намбольшая оценка Элемента 3-2.Вычёркиваем ветвь 3-2 которая показана в таблице 2.6

Таблица 2.4 Таблица 2.5

№			3
1

№

Таблица 2.6 Таблица 2.7

№		2
3

№

На шестом этапе после вычёркивание ветви 3-2 получена новая матрица (таблица 2.7) выполняем оценку элементов. Вычитание наименьших строк и столбцов нету так как наименьшими элементами строк и столбцов являются 0.Оценка элементов показана в таблице 2.7.Так как наибольшая оценка элемента 4-5 то тогда вычёркиваем ветвь 4-5.(табл2.8)

Таблица 2.8 Таблица2.9

№			5
4

№

На седьмом этапе после вычёркивание ветви 4-5 получена новая матрица (таблица 2.9) выполняем оценку элементов. Вычитание наименьших строк и столбцов нету так как наименьшими элементами строк и столбцов являются 0.Оценка элементов показана в таблице 2.9.После проведение операции приведение и оценки новой матрица очевидно видно что вычёркиваем ветви 2-4 и 5-1(таблица 2.10)

Таблица 2.10

№

Оптимальный маршрут движения длиной 30 км получаем путём склеивания вычеркнутых ветвей по совпадающим цифрам их начала и конца 1-3 3-2 2-4 4-5 5-1

Дата добавления: 2015-07-20