Скачать .docx |
Реферат: Распределение грузоперевозок
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. Решение транспортной задачи распределительным методом
Методика расчёта
1) Распределяем груз по каждому столбцов клетке с наименьшим расстоянием. После распределения такие клетки называются загруженными (Таблица 2.1).
2) Для проверки оптимальности полученного распределения определяем специальные индексы(потенциалы), которые проставляем в клетки вспомогательной строки и столбца. Индексы определяют по следующему правилу: вначале в клетке столбца строки В1 проставляем нуль, а остальные индексы рассчитываем исходя из того, что их сумма должна быть равна
расстоянию каждой загруженной клетки. Затем определяем потенциалы остальных столбцов и строк, исходя из того, что u+v=c, при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. В случае, если количество загруженных клеток окажется меньше числа m+n-1 (где m-число строк, n-число столбцов), то необходимо искусственно загрузить недостающее количество клеток, для этого в них проставляют нуль загрузки и после этого с такой клеткой оперируют как с загруженной. Целесообразно нуль ставить в такую клетку, для которой один из индексов уже определён, а также по возможности в клетку с наименьшим расстоянием.
3) После этого находим такие незагруженные клетки, в которых сумма индексов больше расстояния, указанного в соответствующих клетках – такие клетки называются потенциальными. Цифру разности между суммой индексов и расстоянием называют потенциалом. Потенциал записываем в соответствующую незагруженную клетку в круглых скобках.
4) Находим клетку с наибольшим потенциалом (это условие является необязательным). Для выбранной потенциальной клетки «строим» контур – замкнутую линию, состоящую из прямых горизонтальных и вертикальных линий, все вершины этой линии должны находиться в загруженных клетках, а также в выбранной потенциальной. Контур строим по правилу – от выбранной потенциальной клетки веду прямую горизонтальную или вертикальную линию до такой загруженной клетки, которой под прямым углом соответствует ещё одна загруженная клетка, и так до тех пор, пока линия не замкнётся в исходной потенциальной клетке.
5) После этого всем вершинам контура попеременно присваиваем знаки «-» и «+», начиная с выбранной потенциальной.
6) Из загрузок, обозначенных знаком «+», выбираем наименьшую.
7) Данную величину отнимаем от загрузок со знаком «+» и прибавляем к загрузкам со знаком «-».
Таблица 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 |
8) Полученные новые значения загрузок записываем в другую таблицу(улучшенное значение). После этого снова рассчитываем
специальные индексы, строим контур и так до тех пор, пока не будет потенциальных клеток.
Таблица 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 |
9) После получения окончательного распределения объёма перевозок между отправителями и потребителями груза определяем грузооборот по следующей зависимости:
n
Р=∑Qi li , т-км
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 |
Вывод: в итоге результаты первого и второго способов решений полностью совпадают, получен оптимальный вариант грузооборота перевозок.