|
Распределение грузоперевозокРаспределение грузоперевозок1. Формулировка задачи и исходные данные Имеется 5 поставщиков (отправителей) груза и 10получателей (потребителей) груза, с известным количеством груза у каждого из поставщиков и потребности в нём каждого получателя (Таблица 1.1 и 1.2). Определены также расстояния между ними (Таблица 1.3). Необходимо получить оптимальный вариант закрепления получателей за поставщиками таким образом, чтобы минимизировать грузооборот перевозок (то есть получение кратчайших расстояний доставки груза). Таблица 1.1 - Объём отправления грузов
Таблица 1.2 - Объём потребления грузов, т
Таблица 1.3 - Расстояния между отправителями и потребителями, км
2. Решение транспортной задачи распределительным методом Методика расчёта 1) Распределяем груз по каждому столбцов клетке с наименьшим расстоянием. После распределения такие клетки называются загруженными (Таблица 2.1). 2) Для проверки оптимальности полученного распределения определяем специальные индексы(потенциалы), которые проставляем в клетки вспомогательной строки и столбца. Индексы определяют по следующему правилу: вначале в клетке столбца строки В1 проставляем нуль, а остальные индексы рассчитываем исходя из того, что их сумма должна быть равна расстоянию каждой загруженной клетки. Затем определяем потенциалы остальных столбцов и строк, исходя из того, что u+v=c, при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. В случае, если количество загруженных клеток окажется меньше числа m+n-1 (где m-число строк, n-число столбцов), то необходимо искусственно загрузить недостающее количество клеток, для этого в них проставляют нуль загрузки и после этого с такой клеткой оперируют как с загруженной. Целесообразно нуль ставить в такую клетку, для которой один из индексов уже определён, а также по возможности в клетку с наименьшим расстоянием. 3) После этого находим такие незагруженные клетки, в которых сумма индексов больше расстояния, указанного в соответствующих клетках - такие клетки называются потенциальными. Цифру разности между суммой индексов и расстоянием называют потенциалом. Потенциал записываем в соответствующую незагруженную клетку в круглых скобках. 4) Находим клетку с наибольшим потенциалом (это условие является необязательным). Для выбранной потенциальной клетки «строим» контур - замкнутую линию, состоящую из прямых горизонтальных и вертикальных линий, все вершины этой линии должны находиться в загруженных клетках, а также в выбранной потенциальной. Контур строим по правилу - от выбранной потенциальной клетки веду прямую горизонтальную или вертикальную линию до такой загруженной клетки, которой под прямым углом соответствует ещё одна загруженная клетка, и так до тех пор, пока линия не замкнётся в исходной потенциальной клетке. 5) После этого всем вершинам контура попеременно присваиваем знаки «-» и «+», начиная с выбранной потенциальной. 6) Из загрузок, обозначенных знаком «+», выбираем наименьшую. 7) Данную величину отнимаем от загрузок со знаком «+» и прибавляем к загрузкам со знаком «-». Таблица 2.1 - Первоначальное распределение объёма перевозок между отправителями и потребителями
8) Полученные новые значения загрузок записываем в другую таблицу(улучшенное значение). После этого снова рассчитываем специальные индексы, строим контур и так до тех пор, пока не будет потенциальных клеток. Таблица 2.2 - Второе распределение объёма перевозок между отправителями и потребителями
Таблица 2.3 - Третье распределение объёма перевозок между отправителями и потребителями
Таблица 2.4 - Четвёртое распределение объёма перевозок между отправителями и потребителями
Таблица 2.5 - Пятое распределение объёма перевозок между отправителями и потребителями
Таблица 2.6 - Шестое распределение объёма перевозок между отправителями и потребителями
Таблица 2.7 - Седьмое и окончательное распределение объёма перевозок между отправителями и потребителями
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 - Изменяемые в процессе решения ячейки
Таблица 3.2 - Исходные данные для решения транспортной задачи
После использования процедуры Поиск решения получаем следующие результаты: Таблица 3.3 - Результаты поиска решения
Вывод: в итоге результаты первого и второго способов решений полностью совпадают, получен оптимальный вариант грузооборота перевозок. |
|
