Исследование методов и информационных моделей для оптимизации маршрутов при решении логистических задач

Продолжение таблицы 1

1.3 Классификация методов оптимизации маршрутов при решении логистических задач

Существует  достаточно большое разнообразие в  подходах к оптимизации маршрутов. Модели оптимизации маршрутов можно  разделить на следующие  виды:

1 Классическая транспортная задача. Она представляет собой математическую задачу линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. То есть  задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени [3-4].

         2 Задача коммивояжера. Заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов [5].

          3 Задача о назначениях.  Задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между множествами работ и исполнителей. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительностей исполнителей. Производительность каждого исполнителя при выполнении каждой из имеющихся работ задается заранее. Задача о назначениях представляет собой частный случай транспортной задачи. Наиболее эффективным методом ее решения является венгерский метод, по которому исходя из частичного плана перевозок, за конечное числа итераций можно построить оптимальный план перевозок [6-7-8].

      Методы решения для моделей оптимизации маршрутов:

1 Метод потенциалов

Теорема. Если для некоторого опорного плана Х = { x_ij} транспортной задачи можно подобрать систему изm + n чисел u₁, u₂, …, u_m, v₁, v₂, … v_n, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия:

1   для всех x_ij > 0                                                      (1)

2   для всех i = 1,m, j = 1,n                                         (2)

где (c_ij) – матрица стоимостей перевозок [9].

Итерация  метода потенциалов состоит из трех шагов:

I шаг (вычисление потенциалов).  
          Условие (1) представляет собой систему из ( m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.

II шаг (проверка плана на оптимальность).  
         Для проверки плана на оптимальность необходимо проверить условие (2). Для занятых клеток это условие выполняется, именно на них достигается равенство. Остается посчитать суммы u_i + v_j для свободных клеток. Если 

u_i + v_j ≤ с_ij, то, по теореме, план является оптимальным и задача решена.

III шаг (улучшение плана).  
        Для проведения операции улучшения плана нам понадобится понятие цикла.  Циклом будем называть набор клеток матрицы перевозок, в котором две и ровно две соседние клетки расположены в одной строке или в одном столбце, и первая и последняя клетки набора лежат тоже в одной строке или столбце [10].  
       Графически нетрудно представить цикл в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену [11].  
Примеры:  
 

Рисунок 2– Цикл метода потенциалов

С понятием цикла связаны важные свойства планов:

1. допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла;
2. если имеем опорный план, то для каждой свободной клетки можно образовать единственный цикл, содержащий данную клетку и некоторые из занятых.

Улучшение плана производится по следующей  схеме. В подчеркнутых клетках табл. 2 находим клетку с наибольшей разностью u_i + v_j – c_ij, т.е. где условие (2) нарушается максимально. Затем для этой клетки, согласно утверждению 2, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке.  
Начиная с клетки (1, 1), где условие (2) нарушено максимально, строим цикл. Клетку (1, 1) помечаем знаком «+» [12]. Цикл единственен, у нас все занятые клетки вошли в цикл, но это необязательно. Строим новый планхⁿ по правилу:

Рисунок 3 –  Правила построения цикла метода потенциалов

Замечание. Если транспортная задача является задачей открытого типа, в которой условие баланса не выполняется, а именно сумма запасов больше суммы потребностей, то решить такую задачу можно по предложенной схеме методом потенциалов, введя дополнительного потребителя, с потребностью равной разности балансов и нулевыми стоимостями перевозок от каждого поставщика к этому потребителю [13-14].

2 Симплекс  метод

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства  ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника [16]. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

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