Диссертация (1137155), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Для задачисоставления расписаний известно время выполнения каждого задания(целевая функция (в некоторых частных постановках) – общаяпродолжительность расписания). Однако исходные данные задачи(2.30) – (2.33), соответствующие модели (2.9) не имеют подобныхсвойств.Значениелегкостиэлементарногопреобразованияопределяется конфигурацией промежуточного графаможетбытьпоставленовзависимостьниот(2.10), и непредыдущегопреобразования, ни от места преобразования в траектории. В своюочередь,конфигурациейпромежуточногографаопределяетсявыполненных ранее преобразований.Такимобразом,рассмотрениесходныхмассовыхзадачкомбинаторной оптимизации показывает, что, несмотря на подобие93постановки и формального представления пространства допустимыхрешений задачи (2.30) – (2.33) с задачами коммивояжера, составлениярасписаний и линейной задачи о назначениях, имеются значительныеразличия в структуре исходных данных, определяющих целевыефункции.

Следовательно, задача (2.30) – (2.33) не может быть сведенани к одной из стандартных задач комбинаторной оптимизации.3.2.Методы решения задач комбинаторной оптимизацииОбщеизвестно, что оптимизационные комбинаторные задачиявляются одними из наиболее трудных с вычислительной точкизрения [41]. Универсальный метод – полный перебор вариантов –применим практически только для задач малой размерности. Поэтомувозникла необходимость разрабатывать другие методы, как точные,так и приближенные, которые бы учитывали специфику целевой иограничительных функций и были бы практически применимы кзадачам большей размерности, чем метод полного перебора.

Точныеметоды обладают свойством гарантированно находить оптимальноерешение,однакопочтивсепрактическиважныезадачикомбинаторной оптимизации являются NP-полными [36]: для них неизвестнониодноготочногоалгоритмасполиномиальнойсложностью. Кроме того, постановки задач часто бывают с данными,которые имеют определенные погрешности, что окончательно делаетзначительные вычислительные затраты для нахождения точногорешениянеоправданными[44].Притом,чтосовременныеприближенные алгоритмы комбинаторной оптимизации позволяютполучатьрешения«высокогопрактической точки зрения) время.качества»заприемлемое(с94Точные методы.Для некоторых задач, с которыми в параграфе 3.1 сравниваетсязадача (2.30) – (2.33), разработаны точные методы решения.

Длязадачи о назначениях существует, например, венгерский алгоритм,для задачи коммивояжера – метод ветвей и границ (хотя егоприменение ограничено размерностью задачи). Для задач составлениярасписаний в настоящее время не существует универсальных точныхметодоврешениярасписаний[24],Математическая[6].охватывает[49]лишь(классическая)узкийкругтеорияхорошоформализуемых проблем, которые обычно сводятся к тем же самымзадачам коммивояжера, транспортной и т.п. Поэтому при решениипрактических задач, подобных задаче коммивояжера, и задачсоставления расписаний все чаще применяют приближенные методы.В целом, основная идея точных методов комбинаторнойоптимизациисостоитвиспользованииконечностимножествадопустимых решений и замене полного их перебора сокращенным(направленным перебором).

Если каким-либо образом удаетсяпоказать, что подмножествоне может содержать оптимальныхрешений, то в дальнейшем задача решается на множестве.Таким образом, главную роль в сокращении перебора играют оценка иотбрасывание подмножеств, заведомо не содержащих оптимальныхрешений [43].Наиболее типичным вычислительным методом сокращенияперебора является метод ветвей и границ. Метод ветвей и границ(branch and bound) принадлежит классу детерминированных методов иможет применяться для решения широкого круга задач. Этот методнельзя назвать алгоритмом, поскольку его основные блоки (и преждевсего, вычисление условий отсечения) зависят от конкретной задачи;скорее, это вычислительная схема. Эффективность же метода зависит95от конкретных данных задачи, и в «плохих» случаях привести к томуже полному перебору [25].Метод ветвей и границ отыскания оптимального вариантасостоит из ветвлений (разбиения множества решенийнепересекающиеся подмножестванав соответствии с принятымпринципом ветвления) и отсечений (исключения множеств вариантовиз рассмотрения).

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

От дерева полного перебора отсекаютсяветви с корнем в ней (отсекаются вершины и ребра, следующие заней).Отсечение производится с помощью оценочных функций.Оценочная функция – это функция, заданная навершинах дерева полного перебора, возможно, исключая корень, иравная в его конечных вершинах соответствующим значениямцелевой функции, а в остальных вершинахграницу значений функциимножестводающая нижнююдля вариантов множества, входящих в.Важно, что оценочная функция, дающая нижнюю границу, впроцессе разбиения множества на части не убывает, а дающаяверхнюю границу – не возрастает [25]. Кроме того, поскольку привычислении оценки в вершинах дерева полного перебора (кроме96конечных) в общем случае используются данные участка траектории,то оценочная функциядолжна быть определена на такихучастках.

Эти требования необходимо учитывать при рассмотренииприменимости метода ветвей и границ.Точныерешениядлядостаточноширокогоспектракомбинаторных задач могут быть получены методами удовлетворенияограничений (УО).МетодыУОпредлагаютудобныйаппаратипростуюформальную схему для представления и решения комбинаторныхзадач. Целью решения задачи УО является нахождение значенийпеременных,удовлетворяющихопределеннымограничениям.Парадигма УО является обобщением позициональной логики, вкоторой переменным могут быть присвоены значения из множествалюбого числа переменных, а не только «истина» и «ложь». Проблемасуществования решения задачи УО является NP-полной [55].МногиеизвестнаяклассическиетеоремакомбинаторныеФерма,задачазадачи,такиекак(SAT)извыполнимостипропозициональной логики, задача раскраски графа и задачаизоморфизма графов из теории графов, задача BANDWIDTH изисследования операций могут формулироваться в виде задач УО [55].Решение оптимизационной задачи может быть сведено крешениюпоследовательностизадачУОследующимобразом.Находится допустимое решение, после чего добавляется ограничение,соответствующее целевой функции, которое выражает условие, чтозначение целевой функции должно быть лучше, чем для этогорешения.Последовательныекорректировкиэтогопороговогозначения, производимые до тех пор, пока задача не станетнеразрешимой, позволяют найти оптимальное решение [55].97Для случая, когда используются дискретные переменные, задачаУО в общем виде определяется множеством дискретных переменных, для каждой из которых задана область определенияили{домен},иограничений.

Ограничением называется параотношение, определенное на диапазонерассматриваться как тройкапеременных,множеством, где–. Задача УО может, где– множество– множество доменов переменных,– множество ограничений. Решением задачи УОназываетсяприсвоениезначенийвсемпеременным,котороеудовлетворяет всем ограничениям. Целью решения задачи УО можетбыть нахождение одного или всех решений [55].При постановке задачи УО рассматриваются различные видыограничений. Простейшим типом ограничения является унарноеограничение, которое ограничивает значение одной переменной.Любоеунарноеограничениеможноустранить,выполняяпредварительную обработку области определения соответствующейпеременной, чтобы удалить значения, нарушающие это ограничение.Бинарное ограничение связывает между собой две переменные.Например, бинарным ограничением является.

Бинарной задачейУО называется задача, в которой имеется только бинарныеограничения; она может быть представлена в виде графа ограничений[55].Методы построения решения задачи УО могут быть разбиты натри класса [94]:1) Поиск с возвратами [62]. Эти алгоритмы строят решение спомощью расширения частичного решения шаг за шагом, используяразличные эвристики и применяя разумные стратегии возврата из98тупиковых вершин.

Снижение размера задачи позволяет уменьшитьпространство поиска.2) Алгоритмы распространения ограничений – построены наисключении некоторых элементов, не входящих в решение, изпространства поиска. В общем, эти алгоритмы не исключают всеэлементы, не входящие в решения, из пространства поиска и,следовательно, они не строят сами по себе решения, а используютсялибо для препроцессинга задачи до использования алгоритма другоготипа, либо перемежаются с шагами алгоритмов другого типа –например, поиска с возвратами для повышения производительностипоследнего.3) Структурные алгоритмы – используют информацию оструктуре первичного или двойственного графа ограничений задачи.Имеются различные алгоритмы для этого класса, при этом некоторыепроизводят декомпозицию исходной задачи УО на слабо связанныеподзадачи, которые могут быть решены с помощью методов изпредыдущих двух классов.Все алгоритмы из указанных выше трех классов систематическиисследуют пространство решений.

Эти алгоритмы: корректны, то есть они заканчивают работу с присвоениемзначений всем переменным, которое является решением; полны, т.е. они способны исследовать всё пространствопоиска и найти все решения.Однако алгоритмы распространения ограничений и структурныеалгоритмы имеют ограничения в применении, заключающиеся втребованиях к структуре исходных данных. Наиболее изученными внастоящее время являются алгоритмы поиска с возвратами.Алгоритмы поиска с возвратами выполняют поиск в глубину вдереве решений, в котором каждая вершина соответствует множеству99присвоений (рис.

Характеристики

Список файлов диссертации