Применение метода ветвей и границ для решения задачи коммивояжера

Задача линейного целочисленного программирования – задача о коммивояжере (с кольцевыми маршрутами). Алгоритм решения задачи о коммивояжере методом ветвей и границ – расчет кольцевой схемы сети связи минимальной длины.

Коммивояжер пытается определить кратчайший маршрут для одноразового посещения п городов. (В задаче коммивояжера замкнутый маршрут, проходящий через каждый пункт только один раз, называется циклом; цикл, проходящий через все пункты, называется полным, в противном случае — частичным или подциклом.) В задаче коммивояжера с n городами можно определить такие переменные:

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

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

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

28. Задача целевого программирования, характеристика методов решения (метод весовых коэффициентов, метод приоритетов), понятие компромиссного решения, варианты поиска решения задачи целевого программирования.

Метод весовых коэффициентов

Предположим, что модель целевого программирования имеет п целей следующего вида.

Применение метода ветвей и границ для решения задачи коммивояжера

Метод приоритетов

В методе приоритетов п частных целевых функций ранжируются в порядке их важности, так как их оценивает специалист по принятию решений, т.е.

Применение метода ветвей и границ для решения задачи коммивояжера

более высокого приоритета. Этот метод использует правило исключения столбцов, которое применяется для удаления из оптимальной симплекс-таблицы задачи с целевой функцией Gk небазисной переменной х} с zt — cj * 0 до начала решения задачи с целевой функцией Gk+l. Это правило распознает, что небазисная переменная х}, если она получит ненулевое значение, может ухудшить (но никогда не улучшит) оптимальное значение задачи с целевой функцией, имеющей более высокий приоритет.

К сожалению, этот метод изменения симплекс-таблиц требует более сложных вычислений, чем необходимо на самом деле. Мы покажем, что такого же результата можно достичь более простым способом.

Применение метода ветвей и границ для решения задачи коммивояжера

Этап 0. Определяем частные целевые функции задачи и ранжируем их в порядке приоритетов: G, = рх — G2 = рг у . .. — Gn = рп. Положим i = 1.

Этап L Решаем i-ю задачу ЛП с целевой функцией G,. Обозначим через р’ полученное оптимальное значение отклоняющей переменной рг

Если i = n, вычисления заканчиваются, поскольку решена последняя п-я задача. В противном случае вводим в задачу новое ограничение pt = р*, тогда значение pt не сможет измениться при решении последующих задач. Полагаем i = i + 1 и повторяем этап L

Последовательное введение дополнительных ограничений вида pt = p* теоретически не так элегантно, как правило исключения столбцов. Однако это приводит точно к такому же результату. Кроме того, обоснование введения дополнительных ограничений совершенно очевидно и понятно.

Определенным аргументом в пользу правила исключения столбцов может служить то, что при использовании этого правила происходит удаление переменной, т.е. уменьшается размерность задачи. В то же время описанная выше процедура увеличивает размерность задачи при добавлении новых ограничений. Но если повнимательнее присмотреться к этим ограничениям (вида pt = р*), то легко изменить вычисления таким образом, чтобы это ограничение учитывалось непосредственно путем подстановки значения р’ вместо переменной pt, что также уменьшает количество переменных в задаче. (Можно также использовать метод решения задач ЛП с ограниченными переменными из раздела 7.3 для выполнения замены pt = р*, предполагая при этом ограничение вида pt p’.) С этой точки зрения правило исключения столбцов, если отвлечься от его теоретической привлекательности, не имеет особых вычислительных преимуществ по сравнению с описанной выше процедурой. Но ради объективности мы продемонстрируем, как работает правило исключения столбцов в примере 8.2.3.

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

МРП – экспертный метод, для сравнения важно, чтобы суждения экспертов были достаточно адекватны, для чего предварительно проводят оценку группы экспертов одним из методов. Численность группы экспертов – не более 7 человек. Объектами сравнения могут быть проекты, конструкции, процессы, поставщики, продукция и т.д.

Основные этапы МРП включают:

1. Выбор объектов для сравнения

Объекты для сравнения должны быть однородными, т.е. относиться к одному классу, типоразмеру, виду и т.д.

2. Выбор критериев для сравнения

Чем больше критериев сравнения, тем объективнее и точнее будут результаты, но трудоемкость метода возрастает. С другой стороны необходимо выбрать наиболее значимые критерии.

3. Составление матрицы исходных данных

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

4. Составление матриц парных сравнений для определения рангов вариантов по каждому критерию

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

В этой матрицы рассматривают, какой вариант лучше по данному критерию, используя знаки отношений:

“ “– лучше

“ “– хуже

“ = “ – равные

Знакам отношений присваивают числовые значения в баллах, например:

“ “– 3 б

“ “– 1 б

“ = “ – 2 б

5. Расчет коэффициентов оценки знаков отношений между критериями

6. Составление матрицы оценки важности критериев

Сравнение критериев по важности – это наиболее ответственный этап расчетов, т.к. на данном этапе многое зависит от адекватности суждений экспертов и именно на данном этапе закладывается некоторая погрешность результата.

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

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

Задача целевого программирования – преобразование целей исходной задачи в «гибкую» частную задачу. Реализация метода весовых коэффициентов при оптимизации «гибкой» задачи.

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода ветвей и границ для решения задачи коммивояжера

Лекция 12: Задача коммивояжера (часть 1)


Похожие статьи.

Понравилась статья? Поделиться с друзьями: