Автор работы: Пользователь скрыл имя, 09 Сентября 2013 в 13:32, контрольная работа
Цели минимизации в каждом конкретном случае могут быть различными. При маршрутизации автомобильного транспорта в зависимости от поставленных целей решаются следующие задачи: определение числа ездок для заданного времени пребывания автомобиля в наряде, при котором обеспечивается минимум потерь рабочего времени; закрепление потребителей за поставщиками однотипной продукции, при котором обеспечивается минимум холостых пробегов; увязка ездок отдельных автомобилей с целью обеспечения минимума холостых пробегов; определение последовательности объезда при составлении развозочного и сборочного маршрутов, которая обеспечивает минимум пробега в процессе этого объезда; распределение автомобилей и средств механизации погрузки и выгрузки по рабочим маршрутам, которое обеспечивает максимальное использование этих автомобилей и соответствующих средств механизации.
Введение 4
1.Характеристика расположение пунктов транспортной сети на оси координат ОXY 5
2.Определение расстояния между пунктами транспортной сети 6
3.Решение транспортной задачи методом Фогеля, определение общего пробега, пробега с грузом и транспортной работы для маятниковых маршрутов 8
4.Формирование маршрутов движения транспортных средств с помощью методов Свира и «ветвей и границ» 12
1. Метод Свира 12
2. Метод «ветвей и границ» 14
5.Определение интервалов времени прибытия и отправления транспортных средств для каждого пункта маршрутов 29
6. Определение затрат на транспортировку для выбранного транспортного средства 50
7. Общие выводы 54
Список использованной литературы 56
Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5):
где hi, hj – константы приведения соответственно по строкам и столбцам.
= 33+3 =36
Для нулевых элементов матрицы, приведенной в табл. 15.3, определим оценки Qij, которые проставим в правом нижнем углу соответствующей ячейки.
при условии: 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
Четвертое ветвление «дерева решений» для метода «ветвей и границ»
(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 |