Основы оптимизации перевозочного процесса. Методы маршрутизации перевозок грузов

Сентябрь 14, 2022

Главная
Математика
Основы оптимизации перевозочного процесса. Методы маршрутизации перевозок грузов

Содержание

2. Определение кратчайших расстояний между пунктами транспортной сети Транспортная сеть образуется вершинами и звеньями сети. Вершинами транспортной
3. Определение кратчайших расстояний между пунктами транспортной сети При определении кратчайших расстояний «методом потенциалов» используется следующий алгоритм:
4. Определение кратчайших расстояний между пунктами транспортной сети из всех полученных потенциалов выбирается наименьший, который проставляется у
5. Определение кратчайших расстояний между пунктами транспортной сети Для транспортной сети начальной точке А присваивается нулевой потенциал,
6. Определение кратчайших расстояний между пунктами транспортной сети Из вычисленных потенциалов наименьший имеет точка Д, поэтому ей
7. Транспортная задача и методы ее решения В пунктах А1, А2, … Аn имеется однородный груз в
8. Транспортная задача и методы ее решения Экономико-математическая модель транспортной задачи i - количество поставщиков; j -
9. Транспортная задача и методы ее решения где bj - ограничения по спросу; cij - элементы целевой
10. Транспортная задача и методы ее решения
11. Транспортная задача и методы ее решения составляется первый допустимый план перевозок. Ячейки содержащие объем перевозок называются
12. Транспортная задача и методы ее решения
13. Транспортная задача и методы ее решения определяются специальные цифровые индексы (потенциалы) Потенциалы загруженных ячеек Потенциалы незагруженных
14. Транспортная задача и методы ее решения
15. Транспортная задача и методы ее решения полученное решение (план перевозок) проверяется на оптимальность; При решении задачи
16. Транспортная задача и методы ее решения Если решается задача на максимум, то оптимальный вариант получается в
17. Транспортная задача и методы ее решения Перераспределение загрузок клеток начинается с определения наиболее потенциальной незагруженной ячейки.
18. Транспортная задача и методы ее решения
19. Транспортная задача и методы ее решения Количество перераспределяемого груза определяет наименьший объем груза, стоящий в углах
20. Транспортная задача и методы ее решения полученное новое решение проверяется на оптимальность. Если решение улучшить нельзя,
21. Транспортная задача с дополнительными условиями В случае, когда у грузоотправителей имеются излишки груза, которые никому не
22. Транспортная задача с дополнительными условиями поскольку излишек груза никуда не вывозится, то в углах клеток столбца
23. Транспортная задача с дополнительными условиями В случае, когда в силу каких-то причин невозможно удовлетворить спрос потребителя
24. Транспортная задача с дополнительными условиями Обязательная, или директивная, корреспонденция означает обязательность поставки из точки Аi в
26. Скачать презентацию

Слайд 2

Определение кратчайших расстояний между пунктами транспортной сети
Транспортная сеть образуется вершинами

и звеньями сети.
Вершинами транспортной сети являются точки на местности наиболее важные для определения расстояний или маршрутов движения автомобилей. Связь между вершинами с указанием расстояния между ними образуется звеньями сети.
Транспортная сеть считается заданной, если определены ее вершины, звенья и их длина.

Слайд 3

Определение кратчайших расстояний между пунктами транспортной сети
При определении кратчайших расстояний «методом

потенциалов» используется следующий алгоритм:
начальной точке сети, за которую может быть принята любая из точек, присваивается потенциал, равный нулю νi=0.
определяются потенциалы соседних с начальной точкой вершин сети

ℓij -длина звена, соединяющего вершины i и j.

где νi - потенциал предшествующей вершины;

Слайд 4

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

наименьший, который проставляется у соответствующей вершины, а звено (i – j) отмечается стрелкой;
решение продолжается до тех пор, пока всем вершинам сети не будут присвоены потенциалы.
Величина потенциалов у соответствующих вершин показывает кратчайшее расстояние от выбранного начального пункта до данного пункта. Звенья со стрелками образуют кратчайший маршрут движения от начального пункта до всех остальных.

Слайд 5

Определение кратчайших расстояний между пунктами транспортной сети
Для транспортной сети начальной точке

А присваивается нулевой потенциал, после чего определяются потенциалы соседних с ней точек З, Е, Д, Б:
νЗ = νА+ℓАЗ = 0+8=8;
νЕ = νА+ ℓАЕ = 0+11=11;
νД = νА+ ℓАД = 0+5=5;
νБ = νА+ ℓАБ = 0+6=6.

Слайд 6

Определение кратчайших расстояний между пунктами транспортной сети
Из вычисленных потенциалов наименьший имеет

точка Д, поэтому ей присваивается потенциал 5, который проставляется около вершины в квадрате, а ветвь АД отмечается стрелкой. Вершина Д из дальнейшего рассмотрения исключается, поэтому соответствующие потенциалы зачеркиваются.
На следующем этапе определяются потенциалы вершин, соседних с вершиной Д:
νЕ = νД+ℓДЕ = 5+8=13;
νЖ = νД+ℓДЖ = 0+11=11;
νГ = νД+ℓДГ = 0+8=8.
Из всех рассчитанных потенциалов наименьший имеет вершина Б; ей присваивается потенциал 6 и стрелкой отмечается наименьшее расстояния от вершины А. Вершина Б из дальнейшего рассмотрения исключается, поэтому соответствующие потенциалы зачеркиваются.

Слайд 7

Транспортная задача и методы ее решения
В пунктах А1, А2,

… Аn имеется однородный груз в объемах аi единиц. Этот груз необходимо доставить в пункты потребления В1, В2, … Вm в количестве bj единиц. Известны расстояния (стоимость) перевозок сij между всеми пунктами отправления и получения груза.
Требуется построить такой план перевозок, при котором потребность в грузе всех пунктов потребления будет удовлетворена, весь груз из пунктов отправления будет вывезен и при этом будет обеспечен минимум транспортной работы, что соответствует достижению наименьшего среднего расстояния перевозок груза.

Слайд 8

Транспортная задача и методы ее решения
Экономико-математическая модель транспортной задачи
i -

количество поставщиков;
j - количество потребителей;
ai - ограничения по предложению;

Слайд 9

Транспортная задача и методы ее решения
где bj - ограничения по спросу;
cij

- элементы целевой матрицы;
xij - объем корреспонденции между пунктами i и j.
При решении транспортной задачи распределительным методом используется следующая методика:
на основании исходных данных составляется матрица распределительного метода;

Слайд 10

Транспортная задача и методы ее решения

Слайд 11

Транспортная задача и методы ее решения
составляется первый допустимый план перевозок. Ячейки

содержащие объем перевозок называются загруженными. Количество загруженных клеток всегда должно равняться величине i+j-1. Если количество загруженных клеток менее чем i+j-1, то недостающее количество клеток получается путем загрузки соответствующего количества свободных клеток нулями (нулевые загрузки). Клетка, в которой проставлена нулевая загрузка, считается загруженной.

Слайд 12

Транспортная задача и методы ее решения

Слайд 13

Транспортная задача и методы ее решения
определяются специальные цифровые индексы (потенциалы)
Потенциалы загруженных

ячеек

Потенциалы незагруженных ячеек

Слайд 14

Транспортная задача и методы ее решения

Слайд 15

Транспортная задача и методы ее решения
полученное решение (план перевозок) проверяется на

оптимальность;
При решении задачи на минимум оптимальный вариант получается в том случае, когда во всех загруженных клетках стоят нулевые потенциалы, а потенциалы всех свободных клеток являются положительными величинами. Наличие свободных клеток с отрицательными значениями потенциалов говорит об имеющихся резервах, использовав которые можно получить лучший вариант решения.

Слайд 16

Транспортная задача и методы ее решения
Если решается задача на максимум, то

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

Слайд 17

Транспортная задача и методы ее решения
Перераспределение загрузок клеток начинается с определения

наиболее потенциальной незагруженной ячейки. Для этой клетки строится ″контур″ − замкнутая ломаная линия, состоящая из прямых горизонтальных и вертикальных отрезков, пересекающихся под прямым углом, соединяющих эту клетку с другими загруженными клетками. После этого всем узлам контура попеременно, начиная с выбранной незагруженной ячейки, присваивается положительный (+) и отрицательный (−) знаки.

Слайд 18

Транспортная задача и методы ее решения

Слайд 19

Транспортная задача и методы ее решения
Количество перераспределяемого груза определяет наименьший объем

груза, стоящий в углах контура с отрицательным знаком. Количество груза, указанное в этой ячейке, отнимается из всех клеток со знаком минус и прибавляется во все клетки со знаком плюс. При этом общая сумма в столбцах остается прежней, а изменяется лишь перераспределение груза среди потребителей.

Слайд 20

Транспортная задача и методы ее решения
полученное новое решение проверяется на оптимальность.

Если решение улучшить нельзя, оно считается оптимальным.

Слайд 21

Транспортная задача с дополнительными условиями
В случае, когда у грузоотправителей имеются излишки

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

Слайд 22

Транспортная задача с дополнительными условиями
поскольку излишек груза никуда не вывозится, то

в углах клеток столбца ставятся нули;
дальше задача решается обычным путем по алгоритму распределительного метода, рассматривая фиктивный столбец, как еще один потребитель груза.
Аналогично решается задача, в случае когда спрос превышает предложение. Для недостающего объема груза вводится фиктивная строка.

Слайд 23

Транспортная задача с дополнительными условиями
В случае, когда в силу каких-то причин

невозможно удовлетворить спрос потребителя Вj поставками из Аi, то есть на корреспонденцию из Аi в Вj налагается запрет – запрещение корреспонденции.
Чтобы решить задачу, достаточно вместо реального элемента целевой матрицы, стоящего в клетке АiВj, поставить очень большую величину М, которая больше любого элемента целевой матрицы, имеющегося в данной задаче.

Слайд 24

Транспортная задача с дополнительными условиями
Обязательная, или директивная, корреспонденция означает обязательность поставки

из точки Аi в точку Вj части или всего объема материалов, имеющихся в Аi. В этом случае величина обязательной поставки вычитается из суммы спроса Вj и суммы ограничения Аi и при решении задачи не учитывается.
При подсчете окончательного значения грузооборота обязательный объем прибавляется к полученному оптимальному объему грузооборота.

Основы оптимизации перевозочного процесса. Методы маршрутизации перевозок грузов

Содержание

Определение кратчайших расстояний между пунктами транспортной сети Транспортная сеть образуется вершинами

Определение кратчайших расстояний между пунктами транспортной сетиПри определении кратчайших расстояний «методом

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

Определение кратчайших расстояний между пунктами транспортной сетиДля транспортной сети начальной точке

Определение кратчайших расстояний между пунктами транспортной сетиИз вычисленных потенциалов наименьший имеет

Транспортная задача и методы ее решения В пунктах А1, А2,

Транспортная задача и методы ее решенияЭкономико-математическая модель транспортной задачи i -

Транспортная задача и методы ее решениягде bj - ограничения по спросу;cij

Транспортная задача и методы ее решения

Транспортная задача и методы ее решениясоставляется первый допустимый план перевозок. Ячейки

Транспортная задача и методы ее решения

Транспортная задача и методы ее решенияопределяются специальные цифровые индексы (потенциалы)Потенциалы загруженных

Транспортная задача и методы ее решения

Транспортная задача и методы ее решенияполученное решение (план перевозок) проверяется на

Транспортная задача и методы ее решенияЕсли решается задача на максимум, то

Транспортная задача и методы ее решенияПерераспределение загрузок клеток начинается с определения

Транспортная задача и методы ее решения

Транспортная задача и методы ее решенияКоличество перераспределяемого груза определяет наименьший объем

Транспортная задача и методы ее решенияполученное новое решение проверяется на оптимальность.

Транспортная задача с дополнительными условиямиВ случае, когда у грузоотправителей имеются излишки

Транспортная задача с дополнительными условиямипоскольку излишек груза никуда не вывозится, то

Транспортная задача с дополнительными условиямиВ случае, когда в силу каких-то причин

Транспортная задача с дополнительными условиямиОбязательная, или директивная, корреспонденция означает обязательность поставки

Похожие презентации

Определение кратчайших расстояний между пунктами транспортной сети
Транспортная сеть образуется вершинами

Определение кратчайших расстояний между пунктами транспортной сети
При определении кратчайших расстояний «методом

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

Определение кратчайших расстояний между пунктами транспортной сети
Для транспортной сети начальной точке

Определение кратчайших расстояний между пунктами транспортной сети
Из вычисленных потенциалов наименьший имеет

Транспортная задача и методы ее решения
В пунктах А1, А2,

Транспортная задача и методы ее решения
Экономико-математическая модель транспортной задачи
i -

Транспортная задача и методы ее решения
где bj - ограничения по спросу;
cij

Транспортная задача и методы ее решения
составляется первый допустимый план перевозок. Ячейки

Транспортная задача и методы ее решения
определяются специальные цифровые индексы (потенциалы)
Потенциалы загруженных

Транспортная задача и методы ее решения
полученное решение (план перевозок) проверяется на

Транспортная задача и методы ее решения
Если решается задача на максимум, то

Транспортная задача и методы ее решения
Перераспределение загрузок клеток начинается с определения

Транспортная задача и методы ее решения
Количество перераспределяемого груза определяет наименьший объем

Транспортная задача и методы ее решения
полученное новое решение проверяется на оптимальность.

Транспортная задача с дополнительными условиями
В случае, когда у грузоотправителей имеются излишки

Транспортная задача с дополнительными условиями
поскольку излишек груза никуда не вывозится, то

Транспортная задача с дополнительными условиями
В случае, когда в силу каких-то причин

Транспортная задача с дополнительными условиями
Обязательная, или директивная, корреспонденция означает обязательность поставки