Характеристика расположения пунктов транспортной сети на оси координат OXY

Автор: Пользователь скрыл имя, 02 Февраля 2013 в 03:31, курсовая работа

Краткое описание

Целью выполнения курсовой работы является закрепление знаний, полученных при изучении дисциплины, и приобретение навыков решения задач по формированию маршрутов доставки груза при внутригородских перевозках на основе принципов «точно во время» и «от двери до двери», а также в оценке времени доставки груза на основании статистических закономерностей и расчете основной статьи себестоимости – затрат на топливо.

Оглавление

Введение 3
1. Характеристика расположения пунктов транспортной
сети на оси координат OXY 4
2. Определение расстояния между пунктами
транспортной сети 5
3. Решение транспортной задачи методом Фогеля, определение
общего пробега, пробега с грузом и транспортной работы
для маятниковых маршрутов 6
4. Формирование маршрутов движения транспортных средств
с помощью методов Свира и «ветвей и границ» 8
5. Определение интервалов времени прибытия и отправления транспортных средств для каждого пункта маршрутов 24
6. Определение затрат на транспортировку для выбранного транспортного средства 42
7. Общие выводы 44
Список литературы 46

Файлы: 1 файл

К1.docx

— 393.69 Кб (Скачать)

 

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

                                         (7)

и равна:

= 10+4+4+8+1= 26;

Для нулевых элементов матрицы, приведенной в табл. 20, определим оценки Qij. Так для нулевого элемента, находящегося на пересечении строки Б и столбца 1, оценка QБ-7 = 1 + 4 = 5 (минимальное значение по строке – 1, а по столбцу – 4). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

Результаты расчета оценок представлены в табл. 21.

Таблица 21

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

 

Б

1

6

7

Б

1

2

0

5

1

5

0

6

4

6

6

0

6

8

7

0

5

0

0

4


 

В табл. 21 получили две максимальные оценки равные 6. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 1-6. На пересечении строки 6 и столбца 1 ставим знак “∞“.

Таблица 22

Матрица кратчайших расстояний, после исключения строки 6, столбца 1

 

Б

1

7

Б

1

0

6

6

8

7

0

0


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

Таблица 23

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

 

Б

1

7

hi

Б

1

0

0

6

0

2

6

7

0

0

0

hj

0

0

0


 

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

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

Следующее усечение матрицы представлено в табл. 24

Таблица 24

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

 

Б

1

7

Б

1

0

3

6

0

2

2

7

0

0

0

1


 

Наибольшее искомое значение получаем 3, выбираем на пересечении столбца Б и строки 7. Исключаем из дальнейшего рассмотрения указанные строку и столбец. Получаем матрицу 2 х 2, в которой однозначно представлены две последние «ветки» маршрута (табл. 25).

Таблица 25

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

 

Б

1

6

0

7

0

0


 

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

Анализируя полученные участки (ветви), имеем следующий маршрут: Б 7 1 6 Б, длина которого составляет 32 км.

 

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

Проверим, правильно ли была определена нижняя граница, для чего просуммируем соответствующие расстояния между пунктами маршрута: 4 + 9 + 8 + 11 = 32 км.

Для второго маршрута (2,9,10) грузоотправителя Б построим матрицу кратчайших расстояний (Табл. 26).

 

 

 

Таблица 26

Матрица кратчайших расстояний для второго маршрута от Б

 

Б

2

9

10

Б

9

10

8

2

9

5

9

9

10

5

6

10

8

9

6


 

В каждой строке находим  минимальный элемент hi и выполним приведение матрицы по строкам (Табл. 27).

Таблица 27

Матрица кратчайших расстояний, приведенная по строкам

 

Б

2

9

10

hi

Б

1

2

0

8

2

4

0

4

5

9

5

0

1

5

10

2

3

0

6


 

Далее, полученную в табл. 27 матрицу необходимо привести по столбцам. Результат приведения представлен в табл. 28.

Таблица 28

Матрица кратчайших расстояний, приведенная по столбцам

 

Б

2

9

10

Б

1

2

0

2

2

0

4

9

3

0

1

10

0

3

0

hj

2

0

0

0


 

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

                                         (8)

и равна:

= 8+5+5+6+2= 26;

Для нулевых элементов матрицы, приведенной в табл. 28, определим оценки Qij. Так для нулевого элемента, находящегося на пересечении строки Б и столбца 10, оценка QБ-10 = 1 + 1 = 2 (минимальное значение по строке – 1, а по столбцу – 1). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

Результаты расчета оценок представлены в табл. 29.

Таблица 29

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

 

Б

2

9

10

Б

1

2

0

2

2

2

0

2

4

9

3

0

2

1

10

0

2

3

0

0


 

В табл. 29 получили четыри максимальные оценки равные 2. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет Б-10. На пересечении строки 10 и столбца Б ставим знак “∞“.

Таблица 30

Матрица кратчайших расстояний, после исключения строки Б столбца 10

 

Б

2

9

2

2

0

9

3

0

10

3

0


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

Таблица 31

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

 

Б

2

9

hi

2

0

0

0

9

1

0

0

10

3

0

0

hj

2

0

0


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

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

Следующее усечение матрицы представлено в табл. 32

Таблица 32

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

 

Б

2

9

2

0

1

0

0

9

1

0

4

10

3

0

3


 

Наибольшее искомое значение получаем 4, выбираем на пересечении столбца 2 и строки 9. Исключаем из дальнейшего рассмотрения указанные строку и столбец. Получаем матрицу 2 х 2, в которой однозначно представлены две последние «ветки» маршрута (табл. 33).

 

Таблица 33

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

 

Б

9

2

0

10

0


 

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

Анализируя полученные участки (ветви), имеем следующий маршрут: Б 10 9 2 Б, длина которого составляет 28 км.

Информация о работе Характеристика расположения пунктов транспортной сети на оси координат OXY