Главная » 2014 » Август » 17 » Скачать Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания бесплатно
7:09 AM
Скачать Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания бесплатно
Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания и коррекции траектории
Диссертация
Автор: Федяев, Константин Сергеевич
Название: Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания и коррекции траектории
Справка: Федяев, Константин Сергеевич. Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания и коррекции траектории : диссертация кандидата технических наук : 05.13.01 / Федяев Константин Сергеевич; [Место защиты: ГОУВПО "Московский государственный институт электроники и математики (технический университет)"] - Москва, 2007 - Количество страниц: 70 с. Москва, 2007 70 c. :
Объем: 70 стр.
Информация: Москва, 2007
Содержание:
Введение
1 Основные сведения из теории линейного программирования Вырожденность, методы ее преодоления
11 Постановка задачи и алгоритм симплекс-метода
12 Построение допустимого базисного решения
13 Проблема вырожденности Формальное описание
14 Алгоритм Вольфа
15 Алгоритм Бахшияна
16 Сведение задачи 3 к задаче 5
17 Сравнение алгоритмов Вольфа и Бахшияна на примере решения задачи большой размерности
2 Почти вырожденные задачи линейного программирования и методы их решения
21 Введение
22 Постановка задачи
23 Демонстрация основных идей на примерах
231 Об алгоритме решения строго вырожденной задачи
232 Идеи алгоритма в случаях почти вырожденной или плохо обусловленной задач линейного программирования
24 Конструирование расширенной задачи в общем случае
25 Решение расширенной вырожденной задачи
251 Алгоритм для расширенной задачи
252 Об эффективности нового алгоритма и условиях прекращения вычислений
3 Решение вырожденных обобщенных задач линейного программирования и практические приложения
31 Постановка задачи и алгоритм решения
32 Решение вырожденной обобщенной задачи
33 Построение вырожденного базисного решения в обобщенной задаче линейного программирования
34 Оптимальная задача линейной идеальной коррекции
341 Постановка задачи
342 Результаты расчетов для задачи одноимпульсной коррекции
35 Задача L-оптимального планирования и ее сведение к оптимальной задаче линейной коррекции
351 Постановка задачи и сведение к задаче идеальной коррекции
352 Решение L-задачи
353 Построение вырожденной L-задачи и ее решение
354 Построение начального базиса в L-задаче
355 Результаты расчетов для случая полиномиальной регрессии
Введение:
Объект исследования. В диссертационной работе изучаются вырожденные, почти вырожденные и плохо обусловленные задачи линейного программирования и обобщенного линейного программирования.
Актуальность работы. Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода [12, 25]. В подавляющем большинстве работ того периода указывалось, что на практике случаи вырождения весьма редки, а зацикливания при решении практических задач никогда не наблюдается (см., например, [25]). Проблема построения примеров зацикливания представляла самостоятельный научный интерес, этому вопросу посвящались отдельные работы как в начале развития теории линейного программирования (см. [27]), так и в дальнейшем (см., например, [31, 36]).
Однако с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, однако на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью. Однако большинство классических методов теории вырожденного линейного программирования по-прежнему было посвящено лишь борьбе с зацикливанием, избежать вырожденных итераций при использовании таких методов не удавалось. Указанные методы сводились либо к специальному выбору выводимого из базиса вектора (лексикографическое правило и правило случайного выбора [12]), либо к выбору вводимого в базис вектора (правило Данцига [30]), либо к одновременному выбору обоих этих векторов (правило Блэнда [28]). Разрабатывались также методы, основанные на применении теории двойственности [26].
Первым методом, позволяющим эффективно преодолевать вырожденность, был метод А.Чарнса [29]. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожденности. Одним из наиболее эффективных методов борьбы с вырожденностью в настоящее время является метод Вольфа, предложенный впервые в [35] и модифицированный в [34]. Этот метод основан на случайном возмущении нулевых базисных переменных, соответствующем преобразовании правых частей системы ограничений и последующем решении полученной таким образом невырожденной задачи с измененным правилом выбора выводимой из базиса переменной. В результате решения невырожденной задачи строится новый базис исходной вырожденной задачи, соответствующий меньшему значению целевой функции, или делается вывод об оптимальности текущего базиса вырожденной задачи. Таким образом, метод Вольфа требует решения на каждой вырожденной итерации вспомогательной задачи линейного программирования. В результате процесс поиска оптимального решения исходной задачи становится строго монотонным. Однако метод Вольфа имеет два недостатка. Во-первых, размерность вспомогательной задачи совпадает с размерностью исходной. Во-вторых, при решении вспомогательной задачи также могут возникнуть вырожденные итерации, что приводит к необходимости рекурсивного применения предложенной процедуры.
В.Ц.Бахшияном в работе [1] был предложен другой алгоритм, сходный с арлгоритмом Вольфа по подходу к преодолению вырожденности, но отличающийся по принципу построения вспомогательной задачи и по ее виду. В методе Бахшияна вспомогательная задача имеет размерность строго меныпую размерности исходной задачи. Кроме того, вспомогательная задача с вероятностью 1 невырождена. Эти обстоятельства дают основание предполагать, что алгоритм Бахшияна окажется на практике более эффективным, чем алгоритм Вольфа. Однако до последнего времени алгоритм Бахшияна не был программно реализован, что не позволяло сделать окончательный вывод о целесообразности его применения и апробировать этот алгоритм на решении практических задач.
Несмотря на то, что в задачах большой размерности вырожденность становится практически реальным явлением, гораздо чаще наблюдается так называемый случай почти вырожденности, когда в текущем базисном решении часть компонент оказывается близка к нулю. В этом случае изменение целевой функции при переходе от базиса к базису становится пренебрежимо мало по сравнению с ее текущим значением. В этом случае известные методы борьбы с вырожденностью, вообще говоря, неприменимы, так как малые компоненты базисного вектора все же отличны от нуля. Проблема почти вырожденности в настоящее время изучена крайне слабо несмотря на свою актуальность. Среди работ, в которых затрагивалась эта проблема, можно отметить работу [16], в которой, в частности, обсуждались изменения в целевой функции, происходящие при обнулении малых компонент базисного решения. Решение проблемы почти вырожденности в задачах линейного программирования является основной темой настоящей работы.
Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые получили в литературе название задач обобщенного линейного программирования [12, 20, 4]. Эти задачи по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств. Такие задачи иногда также называют многопараметрическими задачами линейного программирования. Методы решения обобщенных задач обсуждались в работах Дж.Данцига, Л.Лэсдона, М.Мину, М.Л.Лидова, Б.Ц.Бахшияна и др. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится также задача L-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена также задача MV^-оптимального планирования [9]. К обобщенным задачам линейного программирования более сложного вида сводятся задача ^-оптимального планирования эксперимента [10] и задача робастного оценивания [2].
Задачи обобщенного линейного программирования, впервые рассмотренные в [12], обсуждались затем в работах [18, 4,14, 1, 17]. Алгоритм решения обобщенной задачи линейного программирования представляет собой реализацию так называемого метода генерации столбцов в обобщенном линейном программировании [12, 20]. Метод генерации столбцов заключается в том, что задачу обобщенного линейного программирования трактуют как обычную задачу линейного программирования с бесконечным числом векторов условий и решают обычным симплекс-методом, выбирая вводимый вектор из соответствующего множества. Однако в отличие от обычных задач линейного программирования, для обобщенных задач достаточные условия оптимальности текущего базисного решения могут не выполняться в силу бесконечного числа векторов условий. Поэтому для прекращения вычислений используется понятие ^-оптимальности, для проверки которой применяются оценки, позволяющие установить степень близости текущего значения целевой функции к оптимальному. Примеры таких оценок для целевых функций специального вида можно найти в работах [14, 1].
В отличие от обычных задач линейного программирования, при решении обобщенных задач регулярным явлением становятся почти вырожденность текущего базисного решения и плохая обусловленность текущей базисной матрицы [17]. Эти явления, близкие друг к другу по своей природе, связаны с тем, что с приближением значения целевой функции к оптимальному векторы базиса становятся близко расположенными друг к другу и к вектору правых частей ограничений. В результате базисная матрица становится плохо обусловленной, что в свою очередь приводит к резкому росту погрешности вычислений вплоть до получения неверного решения. В работе [1] приводится идея алгоритма преодоления вырожденности в обобщенной задаче, однако практической реализации этой идеи до сих пор не существовало.
Одной из областей, в которых особенно широко применяются методы линейного программирования, является математическая теория планирования эксперимента. Различные задачи теории планирования эксперимента рассматриваются в работах [23, 13, 19, 33, 15, 5]. Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах [4, 3, 9, 10, 5]. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится задача L-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена задача MVS-оптимального планирования [9]. К обобщенным задачам линейного программирования более сложного вида сводятся задача ^-оптимального планирования эксперимента и задача робастного оценивания [10, 2].
Цели и задачи работы.
1. Решение проблемы застревания симплекс-метода в задачах линейного программирования большой размерности, в которых часть базисных переменных близка к нулю.
2. Решение аналогичной проблемы для обобщенных задач линейного программирования.
3. Разработка на основе полученных теоретических результатов алгоритма решения почти вырожденных и обобщенных задач линейного программирования и его применение для решения практических задач оптималыгого оценивания и коррекции траектории.
4. Проведение сравнения алгоритма преодоления вырожденности в задачах линейного программирования, предложенного Б.Ц.Бахшияном, с другими аналогичными алгоритмами.
Методы исследования. Для исследования теоретических проблем использовались методы линейной алгебры, теории оптимизации, линейного программирования, теории планирования эксперимента. Для исследования прикладных задач использовались методы компьютерного моделирования.
Научная новизна работы.
1. Разработан и программно реализован метод решения почти вырожденных задач линейного программирования.
2. Разработан алгоритм решения обобщенных задач линейного программирования, позволяющий решать вырожденные, почти вырожденные и плохо обусловленные задачи.
3. Полученные теоретические результаты применены для решения практических задач одноимпульсной линейной коррекции и L-оптималь-ного оценивания параметров движения.
4. Проведен сравнительный анализ различных алгоритмов преодоления вырожденности в задачах линейного программирования, разработана и отлажена программа, реализующая эти алгоритмы, проведены численные расчеты.
Практическая значимость. Полученные результаты позволяют решать прикладные оптимизационные задачи в различных областях, в том числе в задачах управления космическим полетом, теории оценивания и теории планирования эксперимента.
Апробация работы. Результаты работы докладывались и обсуждались на
• Воронежской весенней математической школе "Современные методы в теории краевых задач"("Понтрягинские чтения - VIII")(Воронеж, 1997),
• VI Международной конференции «Идентификация систем и задачи управления» SICPRO '07 (Москва, 2007),
• научном семинаре "Управление и устойчивость "под руководством профессоров В.Н.Афанасьева, В.Б.Колмановского, В.Р.Носова, МИЭМ (Москва, 2007),
• научном семинаре "Механика, управление и информатика"ИКИ РАН под руководством проф.Р.Р.Назирова (Москва, 2007),
• IV Конференции молодых ученых «Фундаментальные и прикладные космические исследования» ИКИ РАН (Москва, 2007).
Публикации. Основные результаты работы изложены в двух статьях [3, 6] и трех тезисах докладов на научных конференциях [7, 8, 24].
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы (36 источников). Объем диссертации - 69 м.п.с.
