Содержание к диссертации
Введение
1 Задачи оптимального размещения предприятий и методы их решения 11
1.1 Постановки задач 11
1.2 Вычислительная сложность и методы решения . 18
1.3 Схема декомпозиции Бендерса 26
2 Исследование декомпозиционных алгоритмов . 32
2.1 Декомпозиционные алгоритмы решения задачи о р-медиане 32
2.2 Оценки числа итераций для алгоритмов с отсечениями Бендерса 35
2.3 Анализ некоторых релаксационных алгоритмов целочисленного программирования 42
2.4 Вопросы устойчивости декомпозиционных алгоритмов 49
3 Разработка алгоритмов и их экспериментальное исследование 55
3.1 Алгоритмы поиска "перспективных" производственных планов 56
3.2 Оптимизация выбора значений двойственных оценок при построении отсечений Бендерса 66
3.3 Гибридный алгоритм для решения задачи о р-медиане на максимум 71
3.4 Результаты вычислительного эксперимента 76
Заключение 80
Литература 82
- Вычислительная сложность и методы решения
- Декомпозиционные алгоритмы решения задачи о р-медиане
- Оценки числа итераций для алгоритмов с отсечениями Бендерса
- Алгоритмы поиска "перспективных" производственных планов
Введение к работе
Задачи оптимального размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях [3,4,10,15,50,51,84]. Значительный интерес к таким задачам связан также со сложностью многих из них. Поэтому для исследования и решения рассматриваемых задач требуется применение методов системного анализа и оптимизации.
В настоящее время исследования задач размещения предприятий ведутся в следующих основных направлениях. Анализируется структура и вычислительная сложность задач, выделяются полиномиально разрешимые случаи и семейства трудных задач, разрабатываются и изучаются методы решения [16,22,26,34,91]. Интенсивно развивается область, связанная с эволюционными алгоритмами, алгоритмами муравьиной колонии и другими метаэвристиками [29,52, 62]. Большое внимание уделяется простейшей задаче размещения (ПЗР) [28,46,51,54], задаче о р-медиане [29,40,44,49,80,93], задачам с ограничениями на объемы производства [27], динамическим задачам размещения предприятий [4,37]. В работах [3,10] и других исследуются многопродуктовые и многоуровневые задачи размещения.
В общих чертах многие задачи оптимального размещения предприятий могут быть сформулированы следующим образом. Даны пункты возможного размещения предприятий и множество клиентов, которые
должны быть ими обслужены. Требуется открыть предприятия в некоторых из указанных пунктов, прикрепить к ним клиентов и выполнить обслуживание таким образом, чтобы полученное решение было оптимальным в определенном смысле. Под обслуживанием может пониматься, например, транспортировка продукции от поставщиков к ее потребителям. Задачи различаются между собой имеющимися ограничениями, в частности, возможностями предприятий по обслуживанию клиентов, числом открываемых предприятий, затратами на их открытие, и т.п. Многие из рассматриваемых задач являются АГР-трудными [1,9,67].
Для исследования и решения задач оптимального размещения предприятий широко используется аппарат целочисленного линейного программирования (ЦЛП) [4,44,51,54]. Значительная часть известных точных алгоритмов решения основаны на методе ветвей и границ и различных схемах перебора допустимых решений [40,49]. Часто при этом исходная задача сводится к последовательности более простых, которые могут быть решены методами непрерывной оптимизации. Для построения оценок значений целевой функции используется решение соответствующей задачи линейного программирования (ЛП) или двойственной к ней задачи. С целью исключения просмотренных и "неперспективных" решений применяются отсечения. В частности, достаточно эффективными оказались фасетные неравенства, порождаемые выпуклой оболочкой множества целочисленных решений [55].
Во многих задачах размещения предприятий, в том числе в задачах о р-медиане и ПЗР, переменные соответствующей модели ЦЛП естественным образом делятся на две группы: целочисленные и непрерывные. Ввиду этого для их решения применяются декомпозиционные алгоритмы с отсечениями Бендерса [3,22,51], в которых решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных (непрерывных) подзадач.
Для построения производственных подзадач используются дополнительные неравенства (отсечения Бендерса).
Основное направление исследований метода Бендерса - разработка и экспериментальное исследование декомпозиционных алгоритмов для различных задач частично целочисленного программирования [57, 59, 90,92]. С теоретической точки зрения указанные алгоритмы исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач, устойчивости алгоритмов при малых колебаниях исходных данных.
При построении неравенств Бендерса выбор оптимальных значений двойственных оценок в общем случае неоднозначен и существенно влияет на эффективность алгоритмов. Исследования в этом направлении позволяют разрабатывать способы получения более сильных отсечений.
В области целочисленного программирования (ЦП) получил развитие предложенный А.А.Колоколовым подход, основанный на регулярных разбиениях евклидова пространства [17,70]. Применение такого подхода позволило изучить структуру некоторых задач ЦП, ввести и исследовать новые классы отсечений, построить оценки числа итераций (отсечений) для ряда алгоритмов. Многие результаты получены на основе использования элементов L-разбиения, называемых L-классами. В работах [22,69] алгоритм перебора L-классов в сочетании с декомпозицией Бендерса применяется для решения задач размещения предприятий.
Важное место в дискретной оптимизации занимают вопросы устойчивости задач и алгоритмов ЦП [11,30,33,53]. На практике исходные данные задачи могут быть неточными, и даже в случае их достаточно малых колебаний оптимальное решение задачи может сильно изменяться. Задачи, решение которых при этом остается прежним, либо меняется незначительно, называются устойчивыми в том или ином смысле. Но и при сохранении оптимального решения число итераций алгоритма
может существенно возрасти, и его естественно считать неустойчивым. Некоторые последние результаты по устойчивости задач и алгоритмов получены с использованием L-разбиения [18,53]. Представляет интерес исследование устойчивости декомпозиционных алгоритмов с отсечениями Бендерса.
Цель диссертации — разработка, теоретическое и экспериментальное исследование декомпозиционных алгоритмов с отсечениями Бендерса для решения задачи о р-медиане (на максимум и минимум) и простейшей задачи размещения.
Исследуемые в работе декомпозиционные алгоритмы отличаются от классической схемы тем, что в них не требуется решать задачу целочисленного программирования при нахождении очередного производственного плана. Нами построены оценки числа итераций этих алгоритмов для достаточно широкого класса задач. Установлено, что эффективность алгоритма существенно зависит от значений двойственных оценок, используемых при вычислении коэффициентов неравенств Бендерса. Предложены эвристические правила для получения более сильных отсечений. Проведенный вычислительный эксперимент показал перспективность данного подхода.
Выделено семейство трудных задач для известных релаксационных алгоритмов ЦЛП: прямо-двойственного алгоритма перебора L-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Построены оценки числа итераций этих алгоритмов при решении задач из указанного семейства.
Кроме того, для точного решения задачи о р-медиане на максимум предложен гибридный декомпозиционный алгоритм, в котором осуществляется лексикографический перебор допустимых решений в сочетании с релаксацией Лагранжа и отсечениями Бендерса. Сравнение полученных результатов с показателями других программных комплексов для решения задач ЦЛП подтверждают эффективность алгоритма.
Диссертация состоит из введения, трех глав, заключения и списка литературы.
В первой главе приводятся постановки основных задач размещения предприятий и близких к ним задач. Рассматриваются вопросы сложности задач, описываются полиномиально разрешимые случаи простейшей задачи размещения и задачи о р-медиане. Дается краткий обзор алгоритмов решения задач размещения предприятий. Приводятся известные оценки погрешности для ряда приближенных алгоритмов. В этой же главе описывается схема декомпозиции Бендерса для общей задачи ЦЛП и основанные на ней алгоритмы.
Вычислительная сложность и методы решения
В данном разделе излагаются сведения о вычислительной сложности задач размещения предприятий. Дается краткий обзор основных результатов, полученных в области построения точных и приближенных алгоритмов решения указанных задач.
О сложности задач размещения предприятий Задача о р-медиане принадлежит к классу JVP-трудных проблем [9, 67]. К ней сводится задача о минимальном доминирующем множестве. Множество вершин V графа G = V, Е называется доминирующим, если каждая вершина v G V\V соединена ребром по крайней мере с одной вершиной из V. Задача о минимальном доминирующем множестве состоит в нахождении для заданного графа G доминирующего множества минимального веса. Для нахождения ]9-медианы на дереве известен полиномиальный алгоритм, основанный на методе динамического программирования [67]. Его трудоемкость равна 0(р2т2).
Простейшая задача размещения также является iVP-трудной. В работе [51] к ПЗР сводится задача о вершинно-реберном покрытии, которая состоит в определении минимального числа вершин заданного графа G = V, Е , которые покрывают все ребра из Е. Кроме того, известны сведения к ПЗР задачи о покрытии множества [78], задачи о минимизации полинома от булевых переменных с неотрицательными коэффициентами при нелинейных членах [4].
Выделены следующие полиномиально разрешимые случаи простейшей задачи размещения:
Клиенты и предприятия располагаются в вершинах дерева, ребра которого имеют положительную длину, а коэффициенты затрат йц равны длине пути между вершинами г и j. В [68] предложен алгоритм решения данной задачи трудоемкости 0(г3), где г - число вершин дерева. Там же показано, что ЛП-релаксация простейшей задачи размещения имеет при указанных условиях целочисленное решение.
В работе [42] приведен полиномиальный алгоритм для задачи разбиения дерева, обобщающей два предыдущих случая.
Некоторые полиномиально разрешимые случаи задач размещения на сетях выделены в работах [5,36].
Естественно, что задачи, являющиеся обобщениями задачи о р-медиане или ПЗР - р-простейшая задача размещения, многопродуктовая задача о р-медиане, задача размещения с ограничениями на объемы производства - также являются iVP-трудными.
В связи с этим особую важность имеет разработка новых и усовершенствование известных алгоритмов решения задачи, как приближенных, так и точных. В следующем разделе будут описаны основные результаты, полученные в этом направлении.
Методы решения задачи о р-медиане
Для приближенного решения задачи о р-медиане широко применяются алгоритмы градиентного типа [94,95]. Среди них можно выделить алгоритмы градиентного подъема (жадный алгоритм подъема), градиентного спуска (жадный алгоритм спуска) и заменяющую эвристику.
Важной характеристикой приближенного алгоритма является оценка точности аппроксимации. В работе [50] показано, что решение, найденное жадным алгоритмом подъема, отличается от оптимального не более, чем в ( ) 0,86 раза для любой индивидуальной задачи о р-медиане на максимум. Для других алгоритмов жадного типа и для заменяющей эвристики также известны оценки точности, не улучшающие однако приведенную выше [50,88].
Таким образом, для задачи на максимум существуют аппроксимацион-ные алгоритмы с константной оценкой точности. Необходимо отметить, что из факта существования такого алгоритма для задачи о р-медиане на минимум будет следовать V = MV. В случае метрической задачи о р-медиане на минимум известны полиномиальные алгоритмы, обеспечивающие точность аппроксимации б, 4 и 6 [46,47,66].
Некоторое преимущество над традиционными схемами имеют рандомизированные градиентные алгоритмы, в которых на каждом шаге выбирается не строго определенный элемент, а случайным образом элемент из некоторого множества [7,8,26]. Хорошие результаты показывают эвристические алгоритмы в [62,91].
В последнее время широкую известность и популярность приобрели алгоритмы, построенные на аналогиях с процессами, происходящими в природе. Интенсивно развиваются направления, связанные с исследованием и построением генетических алгоритмов, поиска с запретами, имитации отжига, алгоритмов муравьиной колонии [48,52,64,93].
Генетические алгоритмы построены на идее моделирования эволюции природы. Схема алгоритма представляет собой имитацию развития популяции живых организмов. Популяция особей представляет собой набор решений оптимизационной задачи, а "качество" решения определяется функцией пригодности. Отдельная особь характеризуется набором генов - генотипом. Генотип хранит всю необходимую информацию о соответствующем решении. На каждой итерации создаются новые особи, замещающие в популяции менее "пригодные". Для построения новой особи выбираются родители с помощью вероятностного оператора селекции. Гены новой особи получаются в результате воздействия на гены родительских особей операторов скрещивания и мутации. Алгоритм заканчивает свою работу после заданного числа итераций. Результатом работы генетического алгоритма считается лучшее найденное решение.
Толчком для создания алгоритмов муравьиной колонии послужили исследования поведения живых муравьев, в ходе которых было установ лено, что муравьи при движении оставляют на земле след из специального пахнущего вещества - феромона. Следующий муравей, проходя по помеченному пути, прокладывает свой след, усиливая запах. Вероятность того, что новый муравей выберет некоторый путь, возрастает с числом муравьев, уже прошедших по нему. Поведение искусственного муравья моделируется с помощью вероятностного алгоритма, использующего статистическую информацию. На каждой итерации искусственные муравьи строят подмножество решений. Из найденных решений выбираются лучшие. Качество решения определяется с помощью специального показателя, хранящего статистическую информацию о предыдущих решениях. У выбранных решений значение "показателя качества" увеличивается. На следующих шагах эти решения будут выбираться с большей вероятностью. Процесс продолжается до тех пор, пока не достигнется верхняя граница "показателя" или не будет выполнено заданное число итераций.
Для решения задачи о р-медиане хорошо зарекомендовало себя применение релаксации Лагранжа [44,50,56,86]. Получаемое решение двойственной лагранжевой задачи может быть использовано как для построения оценок значения целевой функции в методах ветвей и границ [49], так и для получения достаточно хорошего допустимого решения в различного рода эвристических алгоритмах [31]. В работе [80] предложен вариант лагранжевой релаксации как альтернатива традиционной схеме. Он отличается более устойчивым поведением и высокой скоростью сходимости.
Декомпозиционные алгоритмы решения задачи о р-медиане
В данном разделе будет рассматриваться задача о р-медиане (1.1)-(1.5) в изложенной в разделе 1.1 постановке. Формально можно считать целочисленными только переменные Z(, і Є I, так как известно, что для любого булевого вектора z существует и легко находится целочисленный вектор x(z), обеспечивающий максимальный доход (или минимальные затраты в случае задачи на минимум) при данном наборе открытых предприятий. Введем обозначение f(z) = f(z,x(z)), подчеркивая тем самым, что оптимальное прикрепление клиентов при фиксированном z легко вычисляется. Вектор z = (zi,...,zm) при этом будем называть производственным планом, если он удовлетворяет условиям (1.2) и (1.5) Благодаря данному свойству, для решения задачи Vmax может быть применен декомпозиционный алгоритм, схема которого для общей задачи ЦЛП приведена в п. 1.3. Опишем его, учитывая специфику задачи. Пусть Q - множество всех производственных планов. Процесс V Положим Ф) = ft, F ) = -оо. Итерация к (к 1) Шаг 1. Находим z = lexmaxQ(fc). Если такой точки не существует, то процесс завершается: решение, на котором достигается рекорд F \ является оптимальным. Шаг 2. Формулируем задачу прикрепления клиентов T(z ) для вектора z \ У j У j CjjXjj max iGljeJ E% = i, і e J, (2.1) ІЄІ О Xij zf\ ІЄІ, j Є J, Решая ее, находим х - оптимальное прикрепление клиентов и f{z k ) зз оптимальное значение целевой функции задачи T{z k ). Вычисляем рекорд для просмотренных точек F = max{f(z ),F k }. Шаг 3. Строим по некоторому правилу линейное неравенство (отсечение): 7 , + ... + 7 - (2.2) Добавляем неравенство (2.2) к системе ограничений многогранника и, обозначив получившуюся область через fi( +i) переходим к следующей итерации (на шаг 1). Используя булевость переменных Zi, мы можем заменить в (2.5) знак на , добавив к правой части некоторое достаточно малое число є 0. Например, если все коэффициенты сц (і Є I,j Є J) целочисленные, то можно взять є = 1. Правила построения неравенства (2.2) должны гарантировать, что: a) ему не удовлетворяет точка z k\ b) оно не исключает никакую точку z Є Q[k\ для которой f(z ) F k\ Свойство "а" позволяет гарантировать конечность процесса V, а свойство "Ь" — оптимальность найденного им решения. Примером неравенств, удовлетворяющих условиям "а" и "b", могут служить неравенства вида 5 1, (2-3) где IQ = {і; Є І : z\ = 0}. По своей форме они напоминают вполне регулярные отсечения для задач булева программирования [17]. Легко заметить, что неравенство (2.3) исключает из wk только точку z k\ В качестве отсечений (2.2) на шаге 3 процесса V могут быть использованы отсечения Бендерса. Опишем способ их построения. Для полученной на шаге 1 точки z формулируется задача прикреп ления клиентов T(z ). Двойственная к ней задача имеет вид: Е щ + Е Е му ! ) - min jeJ ieijeJ Uj + Wij Cij, і Є I, j Є J, v2,4) W{j О, г Є I, j Є J. Решая ее, находим оптимальные значения двойственных переменных vS ,w\j , і Є I, j Є J. Отсечение Бендерса, построенное по точке z и (к) (к) двойственным оценкам щ ,wh- имеет вид С увеличением числа итераций растет количество накопленных отсечений и процесс нахождения очередного плана z замедляется. Чтобы избежать этого, зафиксируем максимальное число неравенств, которое может содержать система ограничений множества №к\ Если количество имеющихся отсечений превышает данный порог, то при добавлении нового мы будем отбрасывать одно из имеющихся, например, самое "старое" или выбранное случайным образом. При этом возможна потеря информации о ранее исключенных точках. Чтобы предотвратить зацикливание алгоритма, на шаге 1 процесса V будем требовать дополнительно z(k) , z(fc-i)_ gT0 исключит возможность повторного получения уже просмотренных точек. Будем называть такой алгоритм процессом V с отбрасыванием отсечений.
Далее в этом разделе рассматривается описанный выше процесс V с отсечениями Бендерса. Очевидно, что чем больше точек исключает каждое отсечение, тем быстрее задача будет решена. Как уже было сказано, неравенство (2.3) отсекает только текущую точку z k\ поэтому число итераций процесса V, использующего такие отсечения, равно С .
Определение 2.1 Глубиной отсечения (2.2) называется количество целочисленных точек, исключаемых им из множества &к\
Таким образом, глубина отсечений (2.3) равна 1. В общем случае вычисление глубины отсечения может быть достаточно трудоемким и потому нецелесообразным, однако определенное представление о ней можно получить, рассматривая так называемые соседние решения для z k\
Из свойств матрицы целевой функции задачи Ртах. следует, что F рМ + (т - р)ас и f(z ) рМ, откуда F(fc) - f(z ) (т - р)ас. Значит, для выполнения условия (2.10) необходимо, чтобы имело место (т — р)ас М — ас, что справедливо для Ртах по построению. Так как индекс t выбирался произвольно, то теорема доказана. Прямым следствием данной леммы является следующая Теорема 2.1 Для решения задачи "Pmax потребуется C итераций процесса V.
Таким образом, в зависимости от значений двойственных оценок, используемых при построении отсечений Бендерса, глубина отсечений может колебаться от 1 до С , а число итераций алгоритма, использующего данные отсечения, - от Ст до 1 соответственно. Поэтому интерес представляет вопрос о выборе наилучшего оптимального решения двойственной задачи для построения отсечения. В разделе 3.2 описан вычислительный эксперимент с различными правилами построения отсечений. Его результаты указывают на эффективность использования различных эвристических процедур для определения наилучшего отсечения.
Рассмотрим вопрос о вычислительной сложности задачи Рта,х- После анализа семейства задач (2.8) могло создаться впечатление, что данная задача тоже легко решается, например, процессом V с отсечениями Бендерса, при построении которых двойственные оценки выбираются согласно (2.11).
Оценки числа итераций для алгоритмов с отсечениями Бендерса
В п. 2.2 было показано, что глубина отсечений Бендерса, а следовательно, и скорость работы алгоритма, в котором они используются, зависит от выбора двойственных оценок при построении отсечений. Однако на практике для разных классов задач предпочтительнее могут оказаться те или иные способы вычисления двойственных оценок. Более того, для одной задачи в зависимости от текущего решения эффективнее могут быть разные типы отсечений. В работе [81] при построении отсечения вычисляются оптимальные по Парето значения двойственных переменных: отсечение, построенное с использованием этих значений, не домипируется никакой другим неравенством Бепдерса, построенным по данной точке. Для выбора наилучших двойственных оценок могут быть использованы также эвристические методы. Например, для выбора лучших двойственных оценок среди (2.7) и (2.11) нами использовалось следующее правило: случайным образом выбиралось заранее фиксированное число соседних для z k точек, предпочтение отдавалось отсечению, запрещающему больше решений среди порожденных. Кроме того, в качестве запрещающего неравенства можно использовать отсечение, представляющее собой сумму нескольких неравенств Бендерса.
Для решения задачи о р-медиане на максимум был разработан декомпозиционный алгоритм, ключевыми компонентами которого являются лексикографический перебор допустимых решений задачи, релаксация Лагранжа и отсечения Бендерса [35]. В процессе работы производится переупорядочение координат, позволяющее ускорить алгоритм. Рассмотрим схему алгоритма более подробно.
Данный процесс останавливается, если величина \f[ — f]rl\ на протяжении двух итераций подряд не превышает заданной величины е.
В ходе экспериментов было установлено, что выбор значений L, Ао, Л и є существенно влияет на скорость сходимости субградиентного алгоритма. Об используемых нами величинах этих параметров будет сказано при изложении основного алгоритма.
Существенного ускорения при решении задачи Лагранжа позволило добиться сохранение значений множителей Лагранжа, полученных на предыдущей итерации: они использовались в качестве стартовой точки для субградиентного алгоритма.
Начальное значение рекорда находится с помощью известного эвристического алгоритма GRASP [91]. Исходные тексты реализации данного алгоритма на C++ выложены авторами в Интернет по адресу http://www.research.att.com/ mgcr/popstar/.
Шаг 4. Добавление нового отсечения Бендерса. Строим отсечение Бендерса по точке z k\ значения двойственных оценок при этом выбираются по правилу BEST, изложенному в п. 3. Добавляем его в систему ограничений множества Q(k\ Если количество имеющихся отсечений превышает К, то выбрасываем одно из старых ограничений, выбранное случайным образом. Переходим на шаг 1 следующей итерации.
Как видно из приведенных в таблицах 3.5, 3.6, 3.7 данных, разработанный алгоритм является эффективным для решения задач о р-медиане при небольших значениях р. Для больших р данный подход годится лишь в случае достаточно "легких" задач. В то же время необходимо отметить, что алгоритм Л хорошо показал себя при решении задач из библиотеки ИМ СО РАН, обладающих большим разрывом двойственности и большим количеством локальных оптимумов. Преимущество над пакетом CPLEX в среднем было более, чем трехратным. Кроме того, благодаря низким требованиям алгоритма Л к объему оперативной памяти, была решена задача Н5934 из TSPLIB (при значениях р равных 5 и 10), содержащая 5934 производственные переменные, чего не удалось сделать авторам алгоритма ASV из-за переполнения памяти. Более того, в своей работе [40] они сообщают, что оптимальное решение задачи ГІ5934 им не известно ни для каких значений р (за исключением тривиальных случаев).
Обобщая вышесказанное, можно сделать вывод о том, что разработанный алгоритм Л позволяет эффективно решать задачи о р-медиане достаточно большой размерности и поэтому может быть использован для прикладных задач.
В работе проведено исследование декомпозиционных алгоритмов с отсечениями Бендерса и некоторых алгоритмов целочисленного программирования при решении классических задач оптимального размещения предприятий — задачи о р-медиане (на минимум и на максимум) и простейшей задачи размещения. Разработаны новые декомпозиционные алгоритмы для решения задачи о р-медиане на максимум, проведены их экспериментальные исследования.
Основные результаты диссертации заключаются в следующем:
1. Построены семейства задач о р-медиане, на основе которых получены оценки числа итераций для декомпозиционных алгоритмов с отсечениями Бендерса, алгоритма перебора L-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Некоторые из этих оценок перенесены на достаточно широкий подкласс задач о р-медиане.
2. Предложены способы повышения эффективности декомпозиционных алгоритмов с отсечениями Бендерса для задачи о р-медиане на максимум путем оптимизации выбора двойственных оценок при построении отсечений и использования эвристических алгоритмов нахождения целочисленного решения текущей системы неравенств.
3. Показано, что рассматриваемые декомпозиционные алгоритмы с отсечениями Бендерса при малых колебаниях коэффициентов целевой функции не являются устойчивыми для ряда известных правил вы бора значений двойственных оценок. Предложены модификации алгоритмов, обладающие свойством устойчивости.
4. Разработан гибридный декомпозиционный алгоритм решения задачи о р-медиане на максимум с использованием релаксации Лагранжа и отсечений Бендерса. Проведены вычислительные эксперименты, показавшие его эффективность.
Предложенный гибридный алгоритм применим для решения прикладных задач достаточно большой размерности. Построенные семейства задач могут быть использованы при тестировании алгоритмов. Кроме того, полученные результаты включены в учебный процесс на математическом факультете ОмГУ.
Алгоритмы поиска "перспективных" производственных планов
В данном разделе рассматривается декомпозиционный алгоритм V с отсечениями Бендерса, описанный в п. 2.1. Для нахождения производственного плана z(k Є №к\ удовлетворяющего текущей системе ограничений Бендерса, может быть использован алгоритм перебора L-классов. Данный алгоритм основан на идее последовательного просмотра элементов L-разбиения релаксационного множества задачи в порядке лексикографического убывания (для задачи на максимум). Опишем его применительно к нашей задаче.
Окончание процесса решения в обоих случаях означает, что задача ЦЛП не имеет допустимых решений.
Отметим, что трудоемкость алгоритма перебора L-классов существенно зависит от эффективности решения задач Л П. Ввиду этого, можно предложить несколько способов повышения эффективности алгоритма перебора L-классов. Рассмотрим некоторые из них. При использовании лексикографического двойственного симплекс-метода (ЛДСМ) на каждой его итерации известна верхняя оценка значения целевой функции. Если останавливать алгоритм как только эта оценка станет меньше 1 и полагать в этом случае zq = О, то можно получить выигрыш во времени за счет оставшихся итераций ЛДСМ. Опишем такой вариант алгоритма.
Шаг 1. С помощью ЛДСМ решаем задачу zq —» max при ограничениях (3.1) и фиксированных значениях переменных zi,..., zq-\. Работа симплекс-метода прерывается, если на какой-то его итерации выполняется одно из следующих условий: получено оптимальное решение задачи, установлена ее неразрешимость либо оценка целевой функции прямой задачи находится в интервале [0,1). Переходим на шаг 2.
Шаг 2. В зависимости от причины остановки ЛДСМ на предыдущем шаге выполняем следующие действия: 1. Получено оптимальное решение z задачи ЛП или оценка целевой функции прямой задачи находится в интервале [0,1). Полагаем zq = [z \ и переходим на шаг 3. 2. Задача неразрешима. a) q 1. Находим максимальный номер tp q — 1, такой, что z = 1. Если он существует, то полагаем z — 0, q = ср+1 и переходим на шаг 1. Если такого номера (р нет, алгоритм заканчивает работу. b) q = 1. Алгоритм заканчивает работу. Окончание процесса решения в обоих случаях означает, что задача ЦЛП не имеет допустимых решений. Шаг 3. В зависимости от полученного значения zq возможны следующие случаи: 1. Если zq = 1 и Y zi = р, полагаем z\ = Z{ (і = 1,...,g), достав ці (к) (к) ляем оставшиеся координаты нулями: z = ... = % = 0, — и останавливаем алгоритм. я 2. Если zq = 1 и 2 Zi р, увеличиваем значение q на 1 и переходим на г=1 шаг 1. 3. Если zq = 0 и т — q р — Zi, то находим максимальный номер г=1 (f q — l такой, что = 1. Полагаем 2 = 0, q = р + 1 и переходим на шаг 1. Если такого номера не существует, то задача нахождения z(k) — lexinaxfi(fc) неразрешима. Алгоритм заканчивает свою работу. 4. Если zq = 0 и т — q р — ]Г) Zi, то увеличиваем значение q на 1 и г=1 переходим на шаг 1. Процесс Р, использующий алгоритм LAs Для нахождения очередной точки z будем обозначать Vs. Замечание. Процессы V и T s порождают одинаковые последовательности точек { }. Чтобы убедиться в этом, докажем, что в результате работы алгоритма LAs не будет построена целочисленная точка, не удовлетворяющая имеющейся системе отсечений Бендерса. Действительно, алгоритм заканчивает свою работу построением целочисленной точки в п. 1 шага 3. При этом было найдено оптимальное решение текущей задачи ЛП z = 1. Это значит, что построенная точка z является решением системы (3.1). Если количество сохраняемых отсечений К мало по сравнению с количеством переменных т, то существенного повышения скорости работы алгоритма LAs позволяет добиться удаление из задачи (3.1) ограничений Zi 1, і Є L Однако при этом полученные значения z q могут оказаться больше 1, что необходимо учитывать. Опишем этот алгоритм. Алгоритм LAJJ. Шаг 0. Совпадает с шагом 0 алгоритма LAs-Шаг 1. Совпадает с шагом 1 алгоритма LAs Шаг 2. В зависимости от причины остановки ЛДСМ на предыдущем шаге выполняем следующие действия: 1. Получено оптимальное решение z задачи ЛП или оценка целевой функции прямой задачи находится в интервале [0,1). Полагаем zq = 0, если [z \ 1 и zq = 1, если [z \ 1. Переходим на шаг 3. 2. Совпадает с п. 2 шага 2 алгоритма LAg. Шаг 3. Совпадает с шагом 3 алгоритма LAs.
Процесс V, использующий алгоритм ЬАц для нахождения очередной точки z k будем обозначать Т ц.
Замечание. Процессы V и Т ц порождают одинаковые последовательности точек { }. Рассуждения, показывающие это, аналогичны приведенным выше для алгоритма LAs- Необходимо добавить только, что m в последней решенной задачи ЛП будет ограничение Zi = 1, поэтому Z = 1 q Lt Наконец, для решения задачи zq — max может быть использован эвристический алгоритм, который при фиксированном zq — 1 по найденному решению двойственной задачи определяет, разрешима или нет система ограничений Бендерса для оставшихся переменных. В зависимости от этого либо оставляем zq = 1, либо присваиваем zq = 0. Будем обозначать ЬАн - алгоритм, использующий такую эвристику, а Т н - декомпозиционный процесс, в котором очередная целочисленная точка z находится с помощью алгоритма ЬАц. Алгоритм LAH Шаг 0. Начинаем с точки z = z k l\ Находим q = тах{г : z\ — ІЄІ 1} + 1, полагаем zq-\ = 0 и переходим на шаг 1. Шаг 1. Исследуем задачу zq — max при ограничениях (3.1) и фиксированных значениях переменных zi,...,zq-i. Для этого сначала полагаем zq = 1 и с помощью описанной ниже эвристики Н проверяем целевую функцию двойственной задачи на неограниченность убывания. Если это имеет место, то прямая задача неразрешима при zq = 1, полагаем zq = 0. Если неограниченность целевой функции двойственной задачи установить не удалось, оставляем zq = 1. Переходим на шаг 2. Шаг 2. В зависимости от полученного значения zq возможны следующие случаи. 5 (&) 1. Если zq = 1 и 22 zi — Р, полагаем z\ = Z\ (і = 1,..., g), доставляєм (к) (к) п оставшиеся координаты нулями: zWx = ... = zm = U — и останавливаем алгоритм. я 2. Если zq = 1 и Yl Zi ф р, увеличиваем значение q на 1 и переходим на г =1 шаг 1. q 3. Если zq = 0 и т — q р — 2 Zi, то находим максимальный номер г=1 ip q — 1 такой, что z = 1. Полагаем = 0, q = р + 1и переходим на шаг 1. Если такого номера не существует, то задача нахождения z(k) _ jexmax Q(k) неразрешима. Алгоритм заканчивает работу. q 4. Если zq — 0 и т — q р — Y zd Т0 увеличиваем значение q на 1 и г=1 переходим на шаг 1. Рассмотрим более подробно эвристику Н, используемую на шаге 1 алгоритма ЬАн. Для этого заметим, что при фиксированных значениях zi,...,zq получается система ограничений, аналогичная (3.1): (b\z ) bl (Ь2, ) & (ьк, ) $, (3-2) ІЄІ 0 2 { 1, і = 1,...,т , Q где р = р - J] Zi, т = m-qu q 4 = %+і, К = аі- і, Ц = аІ+і, і = 1,...,т , j=l,...,K. г =1 Будем рассматривать задачу ЛП с целевой функцией z[ — max и системой ограничений (3.2). Двойственная к ней задача выглядит следующим образом: т К . p t + Y Ui-Y; Kvj - min »=1 i=l -(6i,v) + + ui l, -(ЬІ, и) +1 + «i 0, і = 2,..., m , (3,3) Vj 0, j = l,...,K, Щ 0, і = 1,... ,m!. Здесь bi = (b\,...,bf), і = 1,...,m . Основное назначение эвристики H состоит в нахождении допустимого решения (щ, Vj, t), на котором целевая функции задачи (3.3) принимала бы значение меньше нуля. Отсюда сразу же будет следовать неразрешимость прямой задачи, что в свою очередь влечет zq = 0.
Похожие диссертации на Разработка и анализ декомпозиционных алгоритмов для задач оптимального размещения предприятий
