по метод.

Индивидуальное задание для выполнения курсовой работы
1.Нанести на оси координат ОXY расположение пунктов транспортной сети
2.Определить расстояния между пунктами транспортной сети
3.Решить транспортную задачу методом Фогеля, определить общий пробег, пробег с грузом и транспортную работу для маятниковых маршрутов
4.Составить маршруты движения транспортных средств с помощью методов Свира (количество пунктов, включаемых в один маршрут не более пяти) и «ветвей и границ»
5.Оценить интервал времени прибытия и отправления транспортных средств для каждого пункта маршрутов. Сделать вывод о соответствии графиков доставки и режимов работы пунктов
6.Произвести выбор транспортных средств, определить затраты на транспортировку (учитывая, что затраты на топливо составляют 30%)
Выводы
Список литературы

по метод.

Пункт разгрузки
Столбец разности
 
2
 
4
 
6
7
8
 
10
А
 
15
 
7
 
17
18
17
 
15
10
Б
 
12
 
7
 
11
16
9
 
6
10
Строка разности
3
6
2
8
9
 
Закрепляем десятого потребителя за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
 
2
 
4
 
6
7
8
 
 
А
 
15
 
7
 
17
18
17
 
 
10
Б
 
12
 
7
 
11
16
9
 
 
9
Строка разности
3
6
2
8
 
Пункт четыре закрепим за А.
Пункт погрузки
Пункт разгрузки
Столбец разности
 
2
 
 
 
6
7
8
 
 
А
 
15
 
 
 
17
18
17
 
 
3
Б
 
12
 
 
 
11
16
9
 
 
7
Строка разности
3
6
2
8
 
Пункт 9 закрепим за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
 
2
 
 
 
6
7
 
 
 
А
 
15
 
 
 
17
18
 
 
 
3
Б
 
12
 
 
 
11
16
 
 
 
5
Строка разности
3
6
2
 
Пункт 6 закрепим за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
 
2
 
 
 
 
7
 
 
 
А
 
15
 
 
 
 
18
 
 
 
3
Б
 
12
 
 
 
 
16
 
 
 
4
Строка разности
3
2
 
Пункт 2 закрепим за А.
Оставшийся пункт 7 закрепим за Б.
Получаем искомое закрепление потребителей за поставщиками, которое приведено в табл. 4.
Таблица 4
Оптимальное закрепление пунктов разгрузки за поставщиками
Пункт
погрузки
Расстояние до пункта разгрузки, км
Итого
1
2
3
4
5
6
7
8
9
10
А
5
 
1
7
 
 
 
 
5
 
18
Б
 
12
 
 
3
11
16
9
 
6
57
Объем груза, т
4,67
2,69
4,57
0,7
2,02
3,81
5,37
3,11
3,98
4,82
По формулам (2) – (4) находим значения:
км
км
км
4. Составить маршруты движения транспортных средств с помощью методов Свира (количество пунктов, включаемых в один маршрут не более пяти) и «ветвей и границ»
Решение задачи коммивояжера, то есть определение оптимального порядка объезда пунктов развозочного маршрута, производится методом «ветвей и границ», который состоит из следующих этапов:
производится приведение матрицы кратчайших расстояний и определение нижней границы (x) для множества "все маршруты" (вершины дерева решений):
(5)
где hi, hj – константы приведения соответственно по строкам и столбцам.
hi = min( lij), i = 1, 2, …, n; (6)
lij' = lij – hi, i, j = 1, 2, …, n (7)
где lij' – элемент новой матрицы приведенной по строкам;
hj = min (lij'), j = 1, 2, …, n; (8)
lij'' = lij' – hj, I, j = 1, 2, …, n (9)
где lij'' – элемент новой матрицы после следующего приведения исходной матрицы по столбцам;
определяются оценки Qij для клеток с нулевыми элементами lij = 0 в новой матрице L':
при условии: k  j; s  i; k, s = 1, 2, …, n,
где l'ik – наименьшее значение элемента в строке i;
l''sj – наименьшее значение элемента в столбце j.
определяются пары (ks) с максимальной оценкой, то есть:
(10)
От начальной вершины "все решения" проводят ответвление вершин ks и с нижними границами:
(11)
где ks – маршруты подмножества, включающего пункты k и s;
- маршруты подмножества, не включающего пункты k и s.
из матрицы исключаются строка k и столбец s. Элементу, находящемуся на пересечении строки s и столбца k, присваивается значение бесконечности (), то есть накладывается запрет на его включение в маршрут или блокирование.
после блокировки операция приведения повторяется, но уже для новой матрицы L' с вычеркнутой строкой k и столбцом s и заблокированными необходимыми элементами lij. Для ветвления выбирают следующую вершину, имеющую наименьшую нижнюю границу, и так до получения матрицы размером два на два. В этой матрице пары, включенные в маршрут, определяются однозначно, и в результате формируется оптимальный развозочный маршрут.
Таблица 6
Матрица кратчайших расстояний для первого маршрута
(грузоотправитель А)
Пункты маршрута
А
1
3
4
9
А
5
1
7
4
1
5
5
2
7
3
1
5
7
5
4
7
2
7
9
9
4
6
5
9
В каждой строке выбираем минимальный элемент и по формуле 7 приводим матрицу к виду (табл.7)
Таблица 7
Матрица кратчайших расстояний, приведенная по строкам
Пункты маршрута
А
1
3
4
9
hij
А
-
4
6
3
1
1
4
-
3
5
2
3
4
-
6
4
1
4
6
5
-
7
2
9
2
5
-
4
Итого: 10
Таблица 8
Матрица кратчайших расстояний, приведенная по столбцам
Пункты маршрута
А
1
3
4
9
 
А
-
4
3
1
 
1
3
-
1
 
3
3
-
2
 
4
5
2
-
3
 
9
-
ИТОГО
hij
1
1
3
4
3
13
Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5) и равна:
= 11 + 13 = 24
Для нулевых элементов матрицы, приведенной в табл. 8, определим оценки Qij, которые проставим в правом нижнем углу соответствующей ячейки.
Результаты расчета оценок представлены в табл. 9.
Таблица 9
Расчет оценок для нулевых элементов
Пункты маршрута
А
1
3
4
9
А
-
5
0+1=1
3
1
1
3
-
0+0=0
0+0=0
1
3
0+0=0
3
-
2
0+1=1
4
5
0+2=2
2
-
3
9
0+0=0
0+0=0
-
В табл. 9 получили максимальную оценку, равную 2.
Таким образом, получаем маршрут – А-3-1-4-9.
Рассчитаем аналогично маршрут Б.
Пункты маршрута
Б
2
5
6
7
8
10
Б
12
3
11
16
9
6
2
12
11
5
4
6
9
5
3
11
11
14
10
8
6
11
5
11
7
1
6
7
16
4
14
7
8
12
8
9
6
10
1
8
4
10
6
9
8
6
12
4
Приведенная матрица по строкам:
Пункты маршрута
Б
2
5
6
7
8
10
hij
Б
-
9
8
13
6
3
3
2
8
-
7
1
2
5
4
5
8
-
8
11
7
5
3
6
10
4
10
-
6
5
1
7
12
10
3
-
4
8
4
8
8
5
9
7
-
3
1
10
2
5
4
2
8
-
4
ИТОГО
20
Приведенная матрица по столбцам:
Пункты маршрута
Б
2
5
6
7
8
10
Б
-
5
7
7
4
 
2
6
-
3
2
 
5
4
-
7
5
5
2
 
6
8
6
-
2
 
7
10
6
2
-
2
5
 
8
6
1
5
1
-
 
10
1
1
2
-
ИТОГО
hij
2
4
4
1
6
2
3
22
Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5) и равна:
= 20 + 22 =42
Проведем оценку нулевых элементов
Пункты маршрута
Б
2
5
6
7
8
10
Б
-
5
7
7
4
2
6
-
3
2
5
4
4
-
7
5
5
2
6
8
6
-
2
7
10
2
6
2
-
2
5
8
6
1
5
1
1
-
10
1
1
2
-
Получим маршрут: Б-5-2-6-8-10-7
Решим задачу методом ветвей и границ:
Маршрут А:
Пункты маршрута
А
1
3
4
9
А
5
1
7
4
1
5
5
2
7
3
1
5
7