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
| |