- •Содержание
- •Глава 1. Постановка транспортных задач 6
- •Глава 2. Определение оптимального плана транспортных задач 28
- •Введение
- •Глава 1.Постановка транспортных задач
- •1.1.Однопродуктовая транспортная модель
- •1.2.Многопродуктовая транспортная модель
- •1.3.Модель производства с запасами
- •1.4. Методы построения опорного плана
- •1.4.1. Метод северо-западного угла
- •1.4.2.Метод минимальной стоимости
- •1.4.3.Метод двойного предпочтения
- •1.4.4.Приближенный метод Фогеля
- •Глава 2.Определение оптимального плана транспортных задач
- •2.1.Решение транспортной задачи методом моди
- •2.2.Дельта-метод решения транспортной задачи
- •2.3.Решение задач закрепления потребителей за поставщиками и клиентуры за автотранспортными предприятиями с учетом дополнительных требований
- •2.3.1.Ограничения в поставках
- •2.3.2.Несбалансированное наличие и потребности
- •2.3.3.Задача закрепления при учете взаимозаменяемости автомобилей
- •2.3.4.Задача на минимизацию времени доставки груза
- •Глава 3.Задача о назначениях
- •3.1.Постановка задачи о назначениях
- •3.2.Венгерский метод решения задачи о назначениях
- •3.3.Применение задачи о назначениях к решению экономических проблем
- •Глава 4.Оптимальное планирование грузооборота
- •4.1.Транспортная сеть и характеристика перевозимых грузов
- •Объёмы потребления грузов
- •Объёмы производства песка
- •4.2.Оптимальное планирование грузоперевозок
- •4.3.Маршрутизация перевозок грузов при помашинных отправках
- •4.4.Составление кольцевых и маятниковых маршрутов
- •Глава 5.Оптимальное планирование работы автобусного парка
- •5.1.Постановка задачи
- •5.2.Двойственная задача линейного программирования
- •5.3. Примеры формулировок двойственных задач
- •5.4. Симметричная и несимметричная двойственные пары. Основы теории двойственности
- •Основная теорема теории двойственности
- •5.5. Условия равновесия в симметричной паре. Экономическая интерпретация
- •5.6.Решение задачи оптимального планирования работы автопарка
- •Глава 6.Область применения сетевых транспортных задач
- •6.1.Примеры применения модели о кратчайшем пути
- •6.2.Алгоритмы нахождения кратчайшего пути
- •6.2.1.Алгоритм для сетей без циклов
- •6.2.2.Алгоритм для сетей с циклами
- •6.2.3.Алгоритм Флойда
- •6.3.Алгоритм нахождения максимального потока в сети
- •6.4.Представление сетевых задач как задач линейного программирования
- •Глава 7.Применение сетевых моделей в транспортировке грузов
- •7.1. Определение кратчайших расстояний между пунктами транспортной сети
- •7.2. Решение задачи коммивояжера методом "ветвей и границ"
- •7.3. Определение развозочных маршрутов для перевозки мелких партий грузов
- •7.3.1. Нахождение кратчайшей связывающей все пункты сети и набор пунктов в маршруты
- •7.3.2. Определение очередности объезда пунктов маршрута
- •Матрица кратчайших расстояний 2-го маршрута
- •7.4. Определение развозочных маршрутов для мелких партий грузов методом Кларка Райта
- •Список литературы
Объёмы производства песка
Поставщик (песок) |
Объём производства, т |
Д |
140 |
К |
110 |
Таблица 67
Объём потребления песка
Потребитель (песок) |
Объём потребителя, т |
Е |
250 |
4.2.Оптимальное планирование грузоперевозок
Цель работы заключается в построении такого плана перевозок щебня, который обеспечивал бы минимальное значение транспортной работы (грузооборота):
,
где i,j - текущий индекс соответственно поставщика и потребителя;
Р - грузооборот, т км;
- объем перевозок между i-ым поставщиком j-ым потребителем, т;
- расстояние между i-ым поставщиком и j-ым потребителем, км.
В этом случае следует задавать не матрицу удельных стоимостей с перевозки единицы груза, а матрицу расстояний между поставщиками и потребителями.
Исходные данные для транспортной сети представлены на рис. 4.1.
Рис. 4.6. Транспортная сеть
Объемы перевозимых грузов приведены в табл. 64, в табл. 65 заданы объемы потребления грузов. Расстояния между соответствующими поставщиком и потребителем, проставляют в правом верхнем углу каждой клетки табл. 68.
Проверим сбалансированность задачи.
Суммарный объём предлагаемого щебня: 140+210+80+210=640 т.
Суммарный объём потребляемого щебня: 170+180+150+130+10=640 т.
Так как объемы предлагаемого и потребляемого щебня одинаковы ( ), то задача является сбалансированной.
Таблица 68
Поставщики |
Ui
Vj |
Потребители |
ai |
|||||||||
В |
И |
Л |
Ж |
З |
||||||||
V1=4 |
V2=2 |
V3=13 |
V4=13 |
V5=6 |
||||||||
А |
U1=-2 |
VV |
2 |
V |
9 |
V |
10 |
V |
11 |
V |
4 |
140 |
140 |
|
|
|
|
||||||||
|
|
9 |
|
-1 |
|
0 |
|
0 |
|
|||
Б |
U2=0 |
V |
4 |
|
11 |
Ө
|
13 |
|
13 |
|
6 |
210 |
30 |
|
150 |
20 |
10 |
||||||||
|
|
9 |
|
|
|
|
|
|
|
|||
Г |
U3=3 |
V |
7 |
|
14 |
|
16 |
|
16 |
|
9 |
80 |
|
|
|
80 |
|
||||||||
0 |
|
9 |
|
0 |
|
|
|
0 |
|
|||
Н |
U4=7 |
|
16 |
VV |
9 |
|
18 |
Ө
|
20 |
|
14 |
210 |
|
180 |
|
30 |
|
||||||||
5 |
|
|
|
-2 |
|
|
|
1 |
|
|||
bj |
170 |
180 |
150 |
130 |
10 |
640 |
Найдём начальный план методом двойного предпочтения. Пометим галочкой в каждой строке и в каждом столбце клетку таблицы c минимальным расстоянием. В начале делаем закрепления в клетки с двумя галочками.
, , вычёркиваем 1-ю строку (А)
, =0 вычёркиваем столбец (И)
Далее делаем назначение в невычеркнутые клетки, помеченные «V».
, =0, вычёркиваем столбец В.
В оставшиеся клетки делаем назначение по методу минимальной стоимости (расстояния).
, клетка БЗ.
, =0, вычёркиваем столбец З.
клетка БЛ.
, =0, вычёркиваем столбец Л.
клетка БЖ.
, =0 , вычёркиваем строку Б.
клетка ГЖ.
, =0 , вычёркиваем строку Г.
Подсчитаем для полученного мерного плана значение грузооборота.
=1402+304+15013+2013+106+8016+1809+3020=6170 т∙км.
Проверим план на оптимальность, для этого рассчитаем потенциалы для загруженных клеток по формуле (4.1).
|
(4.15) |
За свободный можно принять любой потенциал, например, примем , тогда для загруженных клеток:
для БВ: ;
для БЛ: ;
для БЖ: ;
для БЗ: .
Зная можно найти : ;
Зная можно найти : ;
Зная можно найти : ;
Зная можно найти : .
Рассчитаем значение для свободных клеток по формуле (4.2).
|
(4.16) |
Параметр будем записывать в левом нижнем углу клетки.
|
|
Среди есть отрицательные, значит, план не является оптимальным.
Составим специальный контур (цепочку) перемещений, начнём её с клетки НЛ , для неё имеет наибольшее по модулю отрицательное значение.
Данную переменную следует ввести в базис, т.е. увеличить (нагрузить). Контур строим по двум базисным (загруженным) переменным в строке и в столбце. Получим контур . Обход контура возможен как по часовой, так и против часовой стрелки. Найдём величину , т.е. величина совпадает с наименьшим значением переменной, помеченной знаком «−». , , значит переменную следует удалить из базиса т.к. при вычитании , она обратиться в ноль, клетка стоит не нагруженной.
Теперь прибавляем к переменным, помеченным знаком «+», вычитаем из переменных, помеченных знаком «−». В результате получаем новый план (табл. 69).
Таблица 69
Поставщики |
Ui
Vj |
Потребители |
|||||||||
В |
И |
Л |
Ж |
З |
|||||||
V1=4 |
V2=4 |
V3=13 |
V4=13 |
V5=6 |
|||||||
А |
U1=-2 |
Ө
|
2 |
|
9 |
|
10 |
|
11 |
|
4 |
140 |
|
|
|
|
|||||||
|
|
7 |
|
-1 |
|
0 |
|
0 |
|
||
Б |
U2=0 |
|
4 |
|
11 |
Ө
|
13 |
|
13 |
|
6 |
30 |
|
120 |
50 |
10 |
|||||||
|
|
7 |
|
|
|
|
|
|
|
||
Г |
U3=3 |
|
7 |
|
14 |
|
16 |
|
16 |
|
9 |
|
|
|
80 |
|
|||||||
0 |
|
7 |
|
0 |
|
|
|
0 |
|
||
Н |
U4=5 |
|
16 |
|
9 |
|
18 |
|
20 |
|
14 |
|
180 |
30 |
|
|
|||||||
7 |
|
|
|
|
|
2 |
|
3 |
|
Полагаем , находим все потенциалы по формуле (4.1) для загруженных клеток:
для БВ: ;
для БЛ: ;
для БЖ: ;
для БЗ: .
Зная можно найти : ;
Зная можно найти : ;
Зная можно найти : ;
Зная можно найти : .
Рассчитаем значение для свободных клеток по формуле (4.2).
|
|
Есть отрицательные оценки , значит план не оптимальный, в базис вводится переменная , соответствующая отрицательной оценке -1. Помечаем клетку знаком «+». Строим контур: , Вычитаем из клеток, помеченных «−», прибавляем к клеткам, помеченным «+». В результате станет равной нулю, её исключаем из базиса.
Таблица 70
Поставщики |
Ui
Vj |
Потребители |
|||||||||
В |
И |
Л |
Ж |
З |
|||||||
V1=4 |
V2=3 |
V3=12 |
V4=13 |
V5=6 |
|||||||
А |
U1=-2 |
|
2 |
|
9 |
|
10 |
|
11 |
|
4 |
20 |
|
120 |
|
|
|||||||
|
|
8 |
|
|
|
0 |
|
0 |
|
||
Б |
U2=0 |
|
4 |
|
11 |
|
13 |
|
13 |
|
6 |
150 |
|
|
50 |
10 |
|||||||
|
|
8 |
|
1 |
|
|
|
|
|
||
Г |
U3=3 |
|
7 |
|
14 |
|
16 |
|
16 |
|
9 |
|
|
|
80 |
|
|||||||
0 |
|
8 |
|
1 |
|
|
|
0 |
|
||
Н |
U4=6 |
|
16 |
|
9 |
|
18 |
|
20 |
|
14 |
|
180 |
30 |
|
|
|||||||
6 |
|
|
|
|
|
1 |
|
3 |
|
Полагаем U2 = 0 находим потенциалы по загруженным клеткам по формуле (4.1).
для БВ: ;
для БЖ: ;
для БЗ: .
Зная можно найти : ;
Зная можно найти : ;
Зная можно найти : .
Зная можно найти : ;
Рассчитаем значение для свободных клеток по формуле (4.2).
|
|
Все оценки , значит план оптимальный. Минимальный грузооборот = 220 + 10120 + 4150 + 1350 + 610 + 1680 + 9180 + 1830= 5990(ткм). Выигрыш от оптимального плана перевозок составляет 6170 − 5990 = 180 (ткм)