Разработка элементов, организации перевозок груза

 

         В клетке вспомогательного столбца, соответствующей первой строке,

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

,

где - индекс в клетке вспомогательной строки; - индекс в клетке вспомогательного столбца; - расстояние, проставленное в правом верхнем углу загруженной клетки.

          Для нахождения всех числовых  значений индексов необходимо, чтобы  число загруженных клеток в  матрице равнялось числу

,

где m- число столбцов в матрице; n - число строк в матрице.

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

незагруженную клетку матрицы, в которой имеется  минимальное расстояние

(из  числа незагруженных клеток) и  один индекс для нее известен.

После определения вспомогательных индексов находим в матрице потенциальные  клетки.

         Потенциальной называется незагруженная клетка, у которой сумма цифровых индексов вспомогательной строки и столбца больше проставленного в ней расстояния, т.е.

где - расстояние в незагруженной клетке.

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

       В связи с тем, что непосредственное перемещение загрузок из занятых клеток в потенциальные нарушило бы итоги по строкам и столбцам, применяется специальный способ перемещения загрузок. Он заключается в составлении контура возможных перемещений и определении величин загрузок, подлежащих перемещению.

       Контур строится следующим образом. От выбранной потенциальной клетки (если величины потенциалов разные, то началом контура является клетка с наибольшим по величине потенциалом) ведется прямая линия по строке или столбцу до загруженной клетки, которой, в свою очередь, должна соответствовать еще одна загруженная клетка под прямым углом, и так до тех пор, пока линия не замкнется в исходной клетке. Движение при построении контура совершается строго под прямым углом. Вершины контура обозначаются попеременно знаками "+" и "-", начиная с потенциальной клетки, которой присваивается знак "-". Потом из всех клеток, обозначенных знаком "+", выбирается наименьшая цифра загрузки. Это количество груза  вычитается из загрузки, указанной в клетках со знаком "+", и заносится в каждую клетку со знаком "-" .

        Полученные цифры записывают в новую матрицу, куда без изменений переносят загрузки тех клеток, которые не являлись вершинами контура.

Улучшенный  план вновь проверяют на оптимальность, повторяя ранее изложенные действия.

Таблица 4

Матрица промежуточных вычислений

 

Таблица 5

Матрица промежуточных вычислений

 

             При промежуточном вычислении  находим потенциальную клетку  А₂Б₁Б₁А₂  равную 2. 
 
 
 
 
 

Таблица 6

Оптимальный план возврата порожних автомобилей 

 

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

4. Маршрутизация перевозок массовых грузов 

      Рассмотрим решение задачи маршрутизации методом совмещенных планов.

      Процедура решения задачи маршрутизации состоит из двух этапов:

решение задачи на минимум холостых пробегов;

формирование  набора рациональных маршрутов.

Таблица 7

Матрица совмещённых планов