Распределение грузоперевозок
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
|
3820
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9)
После
получения окончательного распределения объёма перевозок между отправителями и
потребителями груза определяем грузооборот по следующей зависимости:
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
|
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
|
Вывод: в
итоге результаты первого и второго способов решений полностью совпадают,
получен оптимальный вариант грузооборота перевозок.