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

При этом в некоторых случаях исходное решение очевидно или его определение  не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или  равно» (тогда нулевой вектор совершенно точно является допустимым решением [17-18].

 

 

3. Метод ветвей и границ

 

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений. Вершина (i, j) соответствует подмножеству всех маршрутов, содержащих ребро (i,j), а вершина (i*,j*) — подмножеству всех маршрутов, где это ребро отсутствует.  
Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ. Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность метода ветвей и границ состоит в том, что от корня дерева ветвятся не все вершины [19].

 

4. Венгерский метод

Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях [20].

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

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время [22].

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

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

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

в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов. Если построенное назначение полное, то оно является оптимальным.  
          Если некоторые нули остались не вычеркнутыми, то можно попытаться найти полное назначение. Если нельзя найти полного назначения, то необходима дальнейшая модификация матрицы стоимостей, т.е. перейти к шагу3.  
           Шаг 3. (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей: 

а) Вычислить число нулей в каждой не вычеркнутой строке и каждом не вычеркнутом столбце. 

 б) Вычеркнуть строку или столбец с максимальным числом нулей. 

 в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули. 

г) Из всех не вычеркнутых элементов вычесть минимальный не вычеркнутый элемент и прибавить его к каждому элементу, расположенному на пересечении двух линий. Перейти к шагу 2 [23-24].  
          Замечания: 
1 Если число линий, необходимое, для того чтобы вычеркнуть нулевые элементы, равно числу строк (столбцов), то существует полное назначение.  
2 Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации [25-26].

 

5. Метод Литтла.

 

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

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 3.3).

Шаг 1. Проверяют выполнение условия  баланса. Если условие баланса не выполняется, т.е. задача открытая, то ее сводят к закрытому типу.

Шаг 2. Создают таблицу плана  перевозок (табл. 3.4), в которой заполнены  только объемы производства и объемы потребления. Выбирают клетку таблицы, которой соответствует минимальная  стоимость перевозки единицы  продукции от производителя к  потребителю [28]. В выбранную клетку аналогично методу северо-западного угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на запасы и заявки. После этого, если предложение производителя исчерпано, остальные клетки соответствующей строки заполняют нулями; если спрос удовлетворен, остальные клетки соответствующего столбца заполняют нулями. Процесс продолжается до тех пор, пока не заполнены все клетки таблицы перевозок [29-30].

 

6. Метод Мака.

 

1 Помечаем минимальный элемент строки отметкой *. Если минимальных элементов несколько, помечаем любой из них.

2  Действия п. 1 повторяем для всех строк матрицы расходов.

3  Если строка имеет еще один минимальный элемент, просматриваем столбец, к которому этот элемент принадлежит. Возможные случаи:i) Столбец не имеет обозначенных элементов;ii) Столбец имеет по крайней мере один обозначенный элемент.

4  В случае i) помечаем минимальный элемент строки отметкой *. Все другие отметки в этой строке снимаются. В случае ii) помечаем минимальный элемент строки отметкой ^, если элемент этой строки с отметкой * не является единственным обозначенным элементом в своем столбце.

5  Действия п.п. 3 и 4 повторяем последовательно для всех строк, которые имеют больше одного минимального элемента.

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

7  Помечаем (отметкой &) столбцы, которые имеют больше одного обозначенного элемента. Они образуют множествоВ, другие столбцы матрицы расходов образуют множество А.

8  Просматриваем последовательно строки матрицы расходов, начиная с первого, и находим строку, в которой элемент с отметкой * принадлежит множеству В.

9  Находим для строки минимальную разницу между элементами множества. Но и элементом с отметкой *.

10 Действия п.п. 8 и 9 повторяем последовательно для всех строк, которые имеют свойства, которые указаны в п. 8.

11  Выбираем наименьшую из минимальных разниц.

12  Добавляем это число к каждому элементу множества В.

13  Возвращаемся к п. 3 [31].

Проведем  классификацию объекта исследования – моделей и методов оптимизации маршрутов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисуно

 

 

Рисунок  4 – Классификация объекта исследования

 

2   АНАЛИЗ И ВЫБОР МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ОПТИМИЗАЦИИ МАРШРУТОВ ПРИ РЕШЕНИИ ЛОГИСТИЧЕСКИХ ЗАДАЧ

 

Рассмотрим  с точки зрения параметров целевой функции представленные методы  в таблице 7.

Таблица 7 – Методы оптимизации маршрутов с точки зрения параметров       целевой функции