Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 2

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

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

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

в ирилонгении в книне главы. Гл. 3. Задачи оптимизации конечное число шагов. Этот алгоритм основывается на идее улучшения стоимости путем перехода от вершины к вершине в многограннике. Тридцать лет совершенствования привели к формам симплекс-алгоритма, которые в целом считаются очень эффективными— для них решение задачи с сотнями переменных и тысячами ограничений не вызывает никаких затруднений. Однако справедливо также, что имеются специально придуманные задачи, при увеличении размерности которых число шагов симплекс-алгоритма растет экспонендиально.

Советские математики относительно недавно изобрели алгоритм эллипсоидов для линейного программирования, который гарантирует нахождение оптимального решения за число шагов, растущее Рнс. !.1 Классы задач, рассматриваемые в дан. ной книге, н порядок нх рассмотренна по главам. как полинам от «размера» задачи — такое положение дел мы будем рассматривать в этой книге как очень благоприятное. Пока еще не ясно, позволят ли конкурировать усовершенствования, аналогичные усовершенствованиям симплекс-алгоритма, алгоритму эллипсоидов с симплекс-алгоритмом.

На рис. !.1 указано, как соотносятся друг с другом упомянутые выше задачи общего нелинейного, выпуклого и линейного программирования. Некоторые задачи линейного программирования, именно задачи о потоках и парооочетаниях, решаются намного эффективнее общих задач линейного программирования. С другой стороны, эти задачи тесно связаны с задачами, которые явно трудноразрешимы! Например, задача о кратчайшем пути из вершины в вершину в графе лежит в нашем классе задач о потоках и паросочетаииях, и для ее ре- д2.

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

Как и в случае задач линейного программирования, для решения таких задач имеется конечный алгоритм. Од. пако на этом сходство кончается: общая задача целочисленного линейного программирования йР-полна. Полностью положение дел представлено на рис. 1.1, где, кроме того, указан общий путь, который будет проделан в данной книге по указанным классам задач. Мы начнем с наиболее фундаментальных и доступных фактов о задачах выпуклого программирования. Затем серьезно займемся линейным программированием, изучая симплекс-алгоритм, его геометрию и алгоритмические следствия двойственности.

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

1.2 Задачи оптимизации Задачи оптимизации естественным образом разделяются на два класса: задачи с непрерывными переменными и задачи с дискретными переменными, которые будем называть комбинаторными. В непрерывных задачах ооычно отыскивается множество действительных чисел или даже некоторая функция; в комбинаторных задачах— некоторый объект из конечного или возможно бесконечного счетного множества. Такими объектами обычнобывают целое число, множество, перестановка или граф. Эти два рода задач обычно совершенно различны по характеру, и методы их решения резко разделились. Комбинаторную оптимизацию мы начнем изучать(в некотором смысле) с пограничной зоны на стыке с непрерывной оптимизацией. Гл, 1, Задачи оптимизации В теории оптимизации особая роль отводится линейному программироваиию: с одной стороны — это непрерывная оптимизациоииая задача, с другой, как упомянуто выше,— ее можно рассматривать также как комбииаториую по природе, и иа самом деле оиа служит основой для изучения многих чисто комбииаториых задач.

Поэтому дадим определение задачи оптимизации достаточно общим, чтобы охватить линейное программирование (и почти любую другую 'задачу оптимизации). Определеиие 1.1. Индивидуальная задача оптимизации — это пара (Р, с), где Р— произвольное множество, область допустимых точек, а с — функция стоимости, осуществляющая отображение с: Р-» )«'. Требуется найти точку )Е Р, для которой с(Г)(с(у) для всех уЕР.

Такая точка Г' называется глобально оптимальным решеиием для даииой иидияидуальиой задачи, или, когда ие может возникнуть иедоразумеиий, просто оптимальным решением. (З Во многих примерах функция стоимости будет принимать только иеотрицательиые целочисленные значения. Определеиие !.2. Задача оптимизации — это множество ( ии. дивидуальиых задач оптимизации. (З Мы четко различаем задачу и индивидуальную задачу. Если говорить неформально, то в индивидуальной задаче даны «входиые данные» и имеется достаточно информации для получения решения, в то время как задача — это набор индивидуальных задач, обычно порождаемых одинаковым способом. Так, в следующем примере, если речь идет об индивидуальной задаче коммивояжера, то матрица расстояний задана; если же мы говорим о задаче коммивояжера в це лом, то имеется в виду набор всех иидивидуальиых задач, соответст.

вующих всем матрицам расстояиий. Пример 1.1 (задача коммивояжера (ЗК)). В иидивидуальиой ЗК даны целое число п»0 и расстояния между всеми парами из и городов в виде (пхп)-матрицы ЫИ1, где дыЕ2+. Обход — это эамкиутый маршрут, проходящий через каждый город ровно один раз. Задача состоит в иахождеиии обхода с минимальной общей длиной. Можно взять Р=(все циклические перестановки и из и объектов). Циклическая перестановка ч представляет собой обход, если ии. терпретироватьп(/) как город, посещаемый после города ), /=1,...

..., и. Тогда стоимость с отображает ч в ч~""г,д;„„,. (З Пример 1.2 (мииимальиое остовиое дерево (МчОД)). Как и выше, даны целое число п)0 и симметричная (п~п)-матрица расстояний (ды!, где дн Е 2+. Задача состоит в нахождении остовиого дерева иа и вершинах, имеющего наименьшую суммарную длину ребер. В соответствии с определением индивидуальной задачи опти. мизации положим Р=(все остовиые деревья (г', Е), где «'=(1, 2, ..., и)), с: (1/, Е) Х д;. и, п«а !3 Л2. Задачи оашимиаации (Под остоино!а! деревом понимается неориентированный, связный, ациклический граф (ь', Е). См. приложение в конце главы.) ( ) Пример 1.3 (задача линейного программирования (ЛП)).

Пусть и, п — положительные целые числа, Ь ~ Я'", с ~ ои и А есть ха хх Рис, !.2. Допустимое множество Р для индиви- дуальной задачи ЛП. 3 ! ет О =«3 хз =' =О Хт ! О ! 3 ! 3 Рис. !.3. Три вершины и три остовных дерева иа них, рассматриваемые как ~очки в 3-мерном пространстве. (тХп)-матрица с элементами а!тЕЛ. Индивидуальная задача ЛП определяется следующим образом: Г=(х: хай", Ах=Ь, х)0), гл х с'х.

Сформулированная таким образом задача линейного программн. рования является непрерывной задачей оптимизации фактически с Га. д Задачи оптимизаяии 14 несчетным числом допустимых точек х~ г. Чтобы понять, почему ее можно все же считать комбинаториой по природе, рассмотрим простой пример с параметрами я=1, л=З и А=(1 1 1), Ь=(2). На рис, 1.2 показано допустимое множество г для данного примера, представляющее собой перехг сечение некоторой плоскости с первым октаитом в Й'. Задача состоит в отыскаиии минимального значения линейной функции с'х=с,х,+ +с,х,+с,х, иа этом треугольнике.

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

Список файлов книги