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 |
Вывод: в итоге результаты первого и второго способов решений полностью совпадают, получен оптимальный вариант грузооборота перевозок.