Распределение грузоперевозок

1. Формулировка задачи и исходные данные

Имеется 5 поставщиков (отправителей) груза и 10получателей (потребителей) груза, с известным количеством груза у каждого из поставщиков и потребности в нём каждого получателя (Таблица 1.1 и 1.2). Определены также расстояния между ними (Таблица 1.3).

Необходимо получить оптимальный вариант закрепления получателей за поставщиками таким образом, чтобы минимизировать грузооборот перевозок (то есть получение кратчайших расстояний доставки груза).

Таблица 1.1 тАУ Объём отправления грузов

Наличие груза у грузоотправителя, т
Товарный склад №1Товарный склад №2КЖБИ №1КЖБИ №2ООО ВлСтройкаВ»
A1A2A3A4A5
960870720890380

Таблица 1.2 тАУ Объём потребления грузов, т

ГрузополучательУсловное обозначениеПотребность в грузе, т.
Объект №1B1530
Объект №2B2230
Объект №3B3190
Объект №4B4300
Объект №5B5100
Объект №6B6200
Объект №7B7140
Объект №8B860
Объект №9B9150
Объект №10B101920

Таблица 1.3 тАУ Расстояния между отправителями и потребителями, км

ГрузополучательГрузоотправитель
A1A2A3A4A5
B166783
B2182120205
B321514154
B41088106
B569888
B6587710
B7667815
B8254419
B9173566
B10149101712

2. Решение транспортной задачи распределительным методом

Методика расчёта

1) Распределяем груз по каждому столбцов клетке с наименьшим расстоянием. После распределения такие клетки называются загруженными (Таблица 2.1).

2) Для проверки оптимальности полученного распределения определяем специальные индексы(потенциалы), которые проставляем в клетки вспомогательной строки и столбца. Индексы определяют по следующему правилу: вначале в клетке столбца строки В1 проставляем нуль, а остальные индексы рассчитываем исходя из того, что их сумма должна быть равна

расстоянию каждой загруженной клетки. Затем определяем потенциалы остальных столбцов и строк, исходя из того, что u+v=c, при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. В случае, если количество загруженных клеток окажется меньше числа m+n-1 (где m-число строк, n-число столбцов), то необходимо искусственно загрузить недостающее количество клеток, для этого в них проставляют нуль загрузки и после этого с такой клеткой оперируют как с загруженной. Целесообразно нуль ставить в такую клетку, для которой один из индексов уже определён, а также по возможности в клетку с наименьшим расстоянием.

3) После этого находим такие незагруженные клетки, в которых сумма индексов больше расстояния, указанного в соответствующих клетках тАУ такие клетки называются потенциальными. Цифру разности между суммой индексов и расстоянием называют потенциалом. Потенциал записываем в соответствующую незагруженную клетку в круглых скобках.

4) Находим клетку с наибольшим потенциалом (это условие является необязательным). Для выбранной потенциальной клетки ВлстроимВ» контур тАУ замкнутую линию, состоящую из прямых горизонтальных и вертикальных линий, все вершины этой линии должны находиться в загруженных клетках, а также в выбранной потенциальной. Контур строим по правилу тАУ от выбранной потенциальной клетки веду прямую горизонтальную или вертикальную линию до такой загруженной клетки, которой под прямым углом соответствует ещё одна загруженная клетка, и так до тех пор, пока линия не замкнётся в исходной потенциальной клетке.

5) После этого всем вершинам контура попеременно присваиваем знаки Вл-В» и Вл+В», начиная с выбранной потенциальной.

6) Из загрузок, обозначенных знаком Вл+В», выбираем наименьшую.

7) Данную величину отнимаем от загрузок со знаком Вл+В» и прибавляем к загрузкам со знаком Вл-В».

Таблица 2.1 тАУ Первоначальное распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексыПоставщик

Пот-реб-ность

в грузе

A1A2A3A4A5

Ваu

v

B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
Наличие груза9608707208903803820

8) Полученные новые значения загрузок записываем в другую таблицу(улучшенное значение). После этого снова рассчитываем

специальные индексы, строим контур и так до тех пор, пока не будет потенциальных клеток.

Таблица 2.2 тАУ Второе распределение объёма перевозок между отправителями и потребителями

Пот-ре-

би-тель

Ин-дексыПоставщик

Пот-реб-ность

в грузе

A1A2A3A4A5

Ваu

v

B1
B2
B3
B4
B5
B6
B7Вместе с этим смотрят:


Автоматизированная система оперативного управления перевозками


Автоматика и автоматизация на железнодорожном транспорте


Автомобильные дизельные топлива


Автомобильные эксплуатационные материалы


Автомобильный кран