2.3 Выбор и обоснование метода решения задачи

1) Решение ТЗЛП состоит из двух этапов: этап 1 – нахождение опорного (первоначального) плана (это решение можно находить, используя метод "северо-западного угла" или метод "минимального элемента"); этап 2- нахождение оптимального плана (метод потенциалов). Для решения транспортной задачи были выбраны методы «северо-западного угла» и потенциалов как наиболее простые и эффективные методы.

Нахождение опорного плана. Метод «северо-западного угла».

В начале определяется элемент , равный . При этом возможны три случая:

- если , то , следовательно

- если , то , следовательно

- если , то , все элементы 1-й строки и первого столбца

Нахождение оптимального плана. Метод потенциалов

1 этап. ПРЕДВАРИТЕЛЬНЫЙ.

Шаг 1. Составляется первоначальный опорный план.

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

Каждому пункту , приписываются значения , численные величины которых определяют из системы (m+n-1) уравнений: (для занятых клеток в транспортной таблице). Так как количество неизвестных на единицу превышает число уравнений, то одно из неизвестных полагаем равным произвольному числу, например =0.

Шаг 3. Полученная система потенциалов исследуется на оптимальность.

Критерий оптимальности: чтобы некоторый допустимы план Х ТЗЛП был оптимальным необходимо и достаточно, чтобы ему соответствовала система из (m+n-1) чисел удовлетворяющих условию:

, для > 0 (для занятых клеток)

, для =0 (для незанятых клеток).

Данное условие называется условием потенциальности. Для того чтобы план ТЗЛП был оптимальным, необходимо и достаточно чтобы он был потенциальным.

Если для некоторых незанятых клеток имеем или , то система потенциалов непотенциальна, то переход к этапу 2.

2 этап. УЛУЧШЕНИЕ ОПОРНОГО ПЛАНА.

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

Цикл – ломаная линия, вершины которой расположены в занятых клетках транспортной таблицы, а звенья отрезки параллельные строкам или столбцам.

В каждой вершине цикла встречается ровно 2 звена, одно из которых находится в строке, а другое – в столбце (знаки вершин «+» и «-» чередуются)

Звенья могут совершать поворот на только в занятых клетках и пересекать пустые.

Перенос (переброска) какого-нибудь количества груза по циклу означает увеличение перевозок, стоящих в «+» вершине цикла и уменьшение перевозок, но то же количество груза в «-» вершинах.

В отрицательных вершинах цикла находят наименьшую из перевозок . Которую и перебрасывают.

Шаг 2. Исправление системы потенциалов.

(аналогично шаг 2 этап 1)

Шаг 3. Проверка на потенциальность новой системы .

Общий этап повторяется пока не будет получен оптимальный план ТЗЛП, после чего вычисляется целевая функция: .

2) Для решения задачи о коммивояжере можно применить различные методы. Если количество городов невелико: ( ), то решение может быть получено с использованием простого метода перебора. С ростом размерности задачи ( ) целесообразно использовать метод ветвей и границ. Другое название этого же метода – метод поиска по дереву решений. Для задач большей размерности ( ) метод ветвей и границ становится неприемлемым. В этом случае наиболее эффективным оказывается метод имитации отжига, основанный на аналогии с физическими эффектами, возникающими при охлаждении расплавленных металлов. В некоторых случаях для задач большей размерности ( ) достаточно эффективным оказывается приближенный, так называемый «хитро-жадный» метод. Этот метод является «усеченным» вариантом метода ветвей и границ. В ряде случаев при большой размерности задачи ( ) эффективными оказываются популярные в настоящее время адаптивно поисковые алгоритмы, основанные на эволюционных факторах получения решения, по другому – генетические алгоритмы.

В нашем случае размерность будет больше 15, по этому принято решение остановиться на методе имитации отжига.

Метод имитации отжига.

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

Алгоритм метода имитации отжига применительно к задаче коммивояжера состоит в построении последовательности укорачивающихся допустимых маршрутов с использованием локализованных мутаций, затрагивающих ровно два произвольно взятых пункта объезда. Пусть ( ) – некоторый допустимый маршрут протяженности . Мутация, затрагивающая пункты и , заключается в том, что и меняются местами в последовательности объезда. Она приводит к новому маршруту протяженности . Обозначим . В соответствии с алгоритмом метода имитации отжига результат мутации безоговорочно принимается, если она привела к сокращению протяженности маршрута: . Результат мутации принимается с некоторой вероятностью , если в результате мутации протяженность маршрута не уменьшилась: . Если мутация принята, то новый маршрут используется в качестве нового допустимого маршрута. Если же мутация отвергается, то допустимый маршрут остается прежним. Построение последовательности маршрутов продолжается до тех пор, пока протяженности маршрутов уменьшаются. Имитация отжига заключается в том, что значение параметра , играющего роль температуры, от мутации к мутации уменьшается и стремится к нулю. Подбирая подходящую скорость уменьшения температуры, можно добиться того, что последовательность допустимых маршрутов будет стремиться к оптимальному маршруту.