Реферат: Распределение грузоперевозок - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

Распределение грузоперевозок

Рефераты по транспорту » Распределение грузоперевозок

1. Формулировка задачи и исходные данные


Имеется 5 поставщиков (отправителей) груза и 10получателей (потребителей) груза, с известным количеством груза у каждого из поставщиков и потребности в нём каждого получателя (Таблица 1.1 и 1.2). Определены также расстояния между ними (Таблица 1.3).

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


Таблица 1.1 – Объём отправления грузов

Наличие груза у грузоотправителя, т
Товарный склад №1 Товарный склад №2 КЖБИ №1 КЖБИ №2 ООО «Стройка»
A1 A2 A3 A4 A5
960 870 720 890 380

Таблица 1.2 – Объём потребления грузов, т

Грузополучатель Условное обозначение Потребность в грузе, т.
Объект №1 B1 530
Объект №2 B2 230
Объект №3 B3 190
Объект №4 B4 300
Объект №5 B5 100
Объект №6 B6 200
Объект №7 B7 140
Объект №8 B8 60
Объект №9 B9 150
Объект №10 B10 1920

Таблица 1.3 – Расстояния между отправителями и потребителями, км

Грузополучатель Грузоотправитель
A1 A2 A3 A4 A5
B1 6 6 7 8 3
B2 18 21 20 20 5
B3 2 15 14 15 4
B4 10 8 8 10 6
B5 6 9 8 8 8
B6 5 8 7 7 10
B7 6 6 7 8 15
B8 2 5 4 4 19
B9 17 3 5 6 6
B10 14 9 10 17 12

2. Решение транспортной задачи распределительным методом


Методика расчёта

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

Для проверки оптимальности полученного распределения определяем специальные индексы(потенциалы), которые проставляем в клетки вспомогательной строки и столбца. Индексы определяют по следующему правилу: вначале в клетке столбца строки В1 проставляем нуль, а остальные индексы рассчитываем исходя из того, что их сумма должна быть равна

расстоянию каждой загруженной клетки. Затем определяем потенциалы остальных столбцов и строк, исходя из того, что u+v=c, при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. В случае, если количество загруженных клеток окажется меньше числа m+n-1 (где m-число строк, n-число столбцов), то необходимо искусственно загрузить недостающее количество клеток, для этого в них проставляют нуль загрузки и после этого с такой клеткой оперируют как с загруженной. Целесообразно нуль ставить в такую клетку, для которой один из индексов уже определён, а также по возможности в клетку с наименьшим расстоянием.

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

Находим клетку с наибольшим потенциалом (это условие является необязательным). Для выбранной потенциальной клетки «строим» контур – замкнутую линию, состоящую из прямых горизонтальных и вертикальных линий, все вершины этой линии должны находиться в загруженных клетках, а также в выбранной потенциальной. Контур строим по правилу – от выбранной потенциальной клетки веду прямую горизонтальную или вертикальную линию до такой загруженной клетки, которой под прямым углом соответствует ещё одна загруженная клетка, и так до тех пор, пока линия не замкнётся в исходной потенциальной клетке.

После этого всем вершинам контура попеременно присваиваем знаки «-» и «+», начиная с выбранной потенциальной.

Из загрузок, обозначенных знаком «+», выбираем наименьшую.

Данную величину отнимаем от загрузок со знаком «+» и прибавляем к загрузкам со знаком «-».


Таблица 2.1 – Первоначальное распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Полученные новые значения загрузок записываем в другую таблицу(улучшенное значение). После этого снова рассчитываем

специальные индексы, строим контур и так до тех пор, пока не будет потенциальных клеток.


Таблица 2.2 – Второе распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Таблица 2.3 – Третье распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы


Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Таблица 2.4 – Четвёртое распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Таблица 2.5 – Пятое распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы


Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Таблица 2.6 – Шестое распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы


Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

Таблица 2.7 – Седьмое и окончательное распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексы


Поставщик

Пот-реб-ность

в грузе

A1 A2 A3 A4 A5

u

v






B1






B2






B3






B4






B5






B6






B7






B8






B9






B10






Наличие груза 960 870 720 890 380 3820

После получения окончательного распределения объёма перевозок между отправителями и потребителями груза определяем грузооборот по следующей зависимости:


n

Р=∑Qili, т-км

i=1


где Qi – объём i-ой перевозки груза, т; li – расстояние i-ой перевозки груза, км;


Р=380*8+150*3+230*5+190*2+300*10+60*8+40*6+200*5+140*6+

60*2+150*6+330*14+870*9+720*10=31250 т-км


3. Решение транспортной задачи с использованием MS Excel


Вначале подготавливаем необходимые таблицы на рабочем листе MS Excel.


Таблица 3.1 – Изменяемые в процессе решения ячейки


Поставщик A1 A2 A3 A4 A5
Потребитель





B1 5 1 1 1 1 1
B2 5 1 1 1 1 1
B3 5 1 1 1 1 1
B4 5 1 1 1 1 1
B5 5 1 1 1 1 1
B6 5 1 1 1 1 1
B7 5 1 1 1 1 1
B8 5 1 1 1 1 1
B9 5 1 1 1 1 1
B10 5 1 1 1 1 1

Факт 10 10 10 10 10

Таблица 3.2 – Исходные данные для решения транспортной задачи

Запросы

Поставщик A1 A2 A3 A4 A5
Потребитель
590 1040 1260 560 380
B1 530 6 6 7 8 3
B2 230 18 21 20 20 5
B3 190 2 15 14 15 4
B4 300 10 8 8 10 6
B5 100 6 9 8 8 8
B6 200 5 8 7 7 10
B7 140 6 6 7 8 15
B8 60 2 5 4 4 19
B9 150 17 3 5 6 6
B10 1920 14 9 10 17 12
Всего 457 86 90 90 103 88

После использования процедуры Поиск решения получаем следующие результаты:


Таблица 3.3 – Результаты поиска решения

Оптимизация транспортных потоков

Поставщик A1 A2 A3 A4 A5
Потребитель





B1 530 200 0 0 180 150
B2 230 0 0 0 0 230
B3 190 190 0 0 0 0
B4 300 0 0 0 300 0
B5 100 100 0 0 0 0
B6 200 0 0 0 200 0
B7 140 140 0 0 0 0
B8 60 0 0 0 60 0
B9 150 0 0 0 150 0
B10 1920 330 870 720 0 0

Факт 960 870 720 890 380

Запросы





Поставщик A1 A2 A3 A4 A5
Потребитель
590 1040 1260 560 380
B1 530 6 6 7 8 3
B2 230 18 21 20 20 5
B3 190 2 15 14 15 4
B4 300 10 8 8 10 6
B5 100 6 9 8 8 8
B6 200 5 8 7 7 10
B7 140 6 6 7 8 15
B8 60 2 5 4 4 19
B9 150 17 3 5 6 6
B10 1920 14 9 10 17 12
Всего 31250 7640 7830 7200 6980 1600

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