Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания и коррекции траектории

Объект исследования. В диссертационной работе изучаются вырожденные, почти вырожденные и плохо обусловленные задачи линейного программирования и обобщенного линейного программирования.

Актуальность работы. Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода [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 м.п.с.

Заключение

.

К основным результатам диссертационной работы следует отнести следующие:

1. Разработка метода решения почти вырожденных и плохо обусловленных задач линейного программирования.

2. Распространение полученных результатов на случай обобщенных задач линейного программирования.

3. Применение разработанного метода для решения задач одноимпульс-ной линейной идеальной коррекции и задачи L-оптимального оценивания параметров движения.

4. Программная реализация метода Бахшияна преодоления вырожденных итераций в задачах линейного программирования и сравнение этого метода с методом Вольфа.

В заключение хочу выразить глубокую благодарность моему учителю и научному руководителю Борису Цолаковичу Бахшияну за постоянную поддержку и руководство данной работой.