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

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

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

Коммивояжер пробует найти кратчайший маршрут для разового посещения п городов. (В задачке коммивояжера замкнутый маршрут, проходящий через каждый пункт только один раз, именуется циклом Применение метода ветвей и границ для решения задачи коммивояжера; цикл, проходящий через все пункты, именуется полным, в неприятном случае — частичным либо подциклом.) В задачке коммивояжера с 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.

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

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

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

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

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

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

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

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

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

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

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

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

“ > “– лучше

“ < “– ужаснее

“ = “ – равные

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

“ > “– 3 б

“ < “– 1 б

“ = “ – 2 б

5. Расчет коэффициентов оценки символов отношений меж аспектами

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

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

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

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

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


primenenie-regressionnogo-analiza-dlya-sostavleniya-reklamnih-byudzhetov.html
primenenie-rezistorov-v-elektricheskih-shemah.html
primenenie-semeni-kunzhuta-v-kulinarii.html