«Метод ветвей и границ»
жүктеу/скачать 374,76 Kb.
|
Kurs rabota KMS Kogogin
| Поиск границ – нахождение верхнего и нижнего пределов для решения задачи на подмножества допустимых значений переменной. В качестве верхней оценки применяют значение целевой функции на определенном допустимом решении. Если оно дает наименьшую верхнюю оценку, то оно называется рекордом. Рекордом называется минимальная верхняя оценка допустимого решения.
Если нижняя оценка целевой функции на подмножестве не меньше верхней оценки, то изучаемое подмножество не имеет решения благоприятнее рекорда и может быть отброшено. Если значение ЦФ на очередном решении по сравнению с рекордным является наименьшим, то осуществляется смена рекорда. После того, как просмотрены все элементы разбиения, то алгоритм завершает работу и текущий рекорд представляет собой оптимальное решение. Если среди не просмотренных элементов разбиения выбор пал на множество, которое в определенном смысле перспективнее, то оно разбивается, то есть осуществляется процедура ветвления. Новые подмножества исследуются, и процесс продолжается до окончания просмотра всех элементов разбиения. Метод ветвей и границ является способом решения комбинаторных задач, таких как задача коммивояжёра и задача о ранце. Рассмотрим каждую по отдельности. Задача о ранце. Задача о ранце (о рюкзаке) представляет собой разновидность NP-полной задачи, применяемой в комбинаторной оптимизации. Эта задача именована от конечной цели, то есть уложить наибольшее количество ценных вещей в ранец при том, что вместимость этого ранца ограничена. Некоторые варианты задачи используются в учебном процессе студентов экономических специальностей, прикладной математики, криптографии и логистике. Общая формулировка задачи звучит следующим образом: из исходного множества различных предметов с признаками «стоимость» и «вес», отбирается то подмножество, которое имеет максимальную полную стоимость, при этом необходимо соблюдение ограничения на суммарный вес. Рис. 1 Пример задачи о ранце Оригинальный алгоритм реализации задачи о рюкзаке был предложен Питером Колесаром в 1967 году, который предлагает осуществить сортировку предметов по их удельной стоимости, и исходя из этого построить дерево полного перебора. Его усовершенствование основывается на том, что при построении дерева, для всех узлов мы даем оценку верхним границам ценности решения, и только для узла, который имеет максимальную оценку мы продолжаем строить дерево. Когда в листе дерева окажется максимальная верхняя граница, алгоритм завершает свою работу. Задача коммивояжёра Рассмотрим метод ветвей и границ для решения задачи коммивояжёра. Данный метод решения задачи коммивояжёра дает возможность найти более точное решение – «вручную» найти длины каждого возможного маршрута и выбрать оптимальный маршрут (с наименьшей длиной). Но даже для небольшого числа городов решать задачу этим способом практически невозможно. Для легкого варианта, симметричной задачи с n городами, имеется (n-1)!/2 определенных маршрутов, таким образом для 15 городов имеется 43 млрд. маршрутов, и для 18 городов 177 трлн. То, как быстро растет длительность вычислений, можно иллюстрировать на следующем примере. Если бы имело место приспособление для нахождения решения для 30 городов за час, то такое решение уже для двух дополнительных городов требовало в 1000 раз больше времени, то есть, более сорока суток. Методы дискретной оптимизации, а также ветвей и границ, дают возможность для нахождения оптимального или приблизительного решения для достаточно больших задач. Рис. 2 Пример задачи коммивояжёра для трех городов Рисунок иллюстрирует применение метода для задачи с тремя городами: красная пунктирная плоскость х1+х2+х3≥2 отсекает все недопустимые решения с максимум одним ребром. Все точки в красном политопе удовлетворяют этому неравенству, и единственная допустимая точка это (1, 1, 1). Пояснение: Три возможных ребра между вершинами равны бинарным переменным х1, х2 и х3. В этом случае имеется лишь один возможный маршрут, который проходит через три вершины. Он удовлетворяет неравенству х1+х2+х3≥2, утверждающее, что маршрут должен проходить через минимум две вершины. Кроме этого маршрута, который соответствует вектору (1,1,1), неравенству удовлетворяют также все точки в части этого неравенства, отмеченной красным цветом. Плоскости, которые проходят через красные линии, отбрасывают все углы несуществующих маршрутов с максимум одним ребром, то есть, ноль-вектор (0, 0, 0), единичные векторы (1, 0, 0), (0, 1, 0) и (0, 0, 1). Сильное неравенство х1+х2+х3≥3 отбрасывает от единичного куба все, кроме единственной допустимой точки (1, 1, 1). Чтобы определить допустимое ребро, имеющее наименьшую длину, необходимо решить комплекс задач линейной оптимизации, отбрасывающие секущими плоскостями лишние части единичного куба и попробовать разделить единичный куб на меньшие политопы методом ветвей и границ. Тем не менее этого метода для быстрого нахождения маршрутов обычно мало. Главный плюс этих методов – наличие необходимого времени, дает возможность найти самый короткий маршрут. При наличии нижнего придела для наиболее благоприятных решений, дают оценку отличию результирующего маршрута от оптимального. жүктеу/скачать 374,76 Kb. Достарыңызбен бөлісу:
|