Введение к работе
Объект исследования. В диссертационной работе изучаются вырожденные, почти вырожденные и плохо обусловленные задачи линейного программирования и обобщенного линейного программирования.
Актуальность работы. Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода. В подавляющем большинстве работ того периода указывалось, что на практике случаи вырождения весьма редки, а зацикливания при решении практических задач никогда не наблюдается. Проблема построения примеров зацикливания представляла самостоятельный научный интерес, этому вопросу посвящались отдельные работы.
В дальнейшем с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, но на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление, получившее в литературе название "застревания"симплекс-метода, привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью.
Первым методом, позволяющим эффективно преодолевать вырожденность, был метод А.Чарнса. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожденности. Среди других методов борьбы с вырожденностью можно выделить метод П.Вольфа, основанный на случайном возмущении нулевых базисных переменных, соответствующем преобразовании правых частей ограничений и последующем решении полученной невырожденной задачи с измененным правилом выбора выводимой из базиса переменной. В результате решения такой невырожденной задачи в исходной задаче строится новый базис, соответствующий меньшему значению целевой функции, или делается вывод об оптимальности текущего базиса. Таким образом, метод Вольфа требует решения на каждой вырожденной итерации вспомогательной задачи линейного программирования, размерность которой равна размерности исходной задачи. В результате процесс поиска оптимального решения исходной задачи становится строго монотонным.
Другим методом, сходным с методом Вольфа по подходу к преодолению
вырожденности, но отличающимся по принципу построения вспомогательной задачи и по ее виду, является метод, предложенный Б.Ц.Бахшияном. В этом методе вспомогательная задача имеет размерность, равную числу нулевых компонент вектора базисных переменных, т.е. строго меньшую размерности исходной задачи. Это обстоятельство дало основание предполагать, что алгоритм Бахшияна окажется на практике более эффективным, чем алгоритм Вольфа. Однако ранее алгоритм Бахшияна не был программно реализован, что затрудняло его применение при решении практических задач.
Несмотря на то, что в задачах большой размерности вырожденность становится практически реальным явлением, гораздо чаще наблюдается так называемый случай почти вырожденности, когда в текущем базисном решении часть компонент оказывается близка к нулю. В этом случае изменение целевой функции при переходе от базиса к базису становится пренебрежимо мало по сравнению с ее текущим значением. При этом известные методы борьбы с вырожденностью, вообще говоря, неприменимы, так как малые компоненты базисного вектора все же отличны от нуля. Проблема почти вырожденности в настоящее время мало изучена несмотря на свою актуальность. Среди работ, в которых затрагивалась эта проблема, можно отметить работу М.Л.Лидова (1991), в которой оценивалось изменение целевой функции при обнулении малых компонент базисного решения. Решение проблемы почти вырожденности в задачах линейного программирования является основной темой настоящей работы.
Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств. Такие задачи получили название обобщенных (многопараметрических) задач линейного программирования. Методы решения обобщенных задач обсуждались в работах Дж.Данцига, Л.Лэсдона, М.Мину, М.Л.Лидова, Б.Ц.Бахшияна и др. Решение таких задач представляет собой реализацию в обобщенном линейном программировании так называемого метода генерации столбцов. Этот метод заключается в том, что задачу обобщенного линейного программирования трактуют как обычную задачу линейного программирования с бесконечным числом векторов условий и решают обычным симплекс-методом, выбирая на каждом шаге вводимый вектор сначала по каждому из соответствующих множеств, а затем выбирая наилучший вектор по всем множествам. При этом, в отличие от обычных задач линейного программирования, для обобщенных задач достаточные условия оптимальности текущего базисного решения могут
не выполняться в силу бесконечного числа векторов условий. Поэтому для прекращения вычислений используется понятие є-оптимальности, для проверки которой применяются оценки, позволяющие установить степень близости текущего значения целевой функции к оптимальному. Этот вопрос обсуждался в работах М.Л.Лидова, Б.Ц.Бахшияна.
В отличие от обычных задач линейного программирования, при решении обобщенных задач регулярным явлением становятся почти вырожденность текущего базисного решения и плохая обусловленность текущей базисной матрицы. Эти явления, близкие друг к другу по своей природе, связаны с тем, что с приближением значения целевой функции к оптимальному векторы базиса становятся близко расположенными друг к другу и к вектору правых частей ограничений. В результате базисная матрица становится плохо обусловленной, что в свою очередь приводит к резкому росту погрешности вычислений вплоть до получения неверного решения. Идеи метода преодоления вырожденности в обобщенной задаче рассматривались в работах Б.Ц.Бахшияна, однако практической реализации такого метода до сих пор не существовало.
Одной из областей, в которых особенно широко применяются методы линейного программирования, является математическая теория планирования эксперимента. Различные задачи теории планирования эксперимента рассматриваются в работах В.В.Федорова, С.М.Ермакова, А.А.Жиглявского, В.Б.Меласа, Ф.Пукельхейма, М.Л.Лидова, В.Н.Соловьева. Применение в теории планирования эксперимента методов линейного программирования рассматривается в работах Б.Ц.Бахшияна, Р.Р.Назирова, П.Е.Эльясберга, А.И.Матасова, М.И.Войсковского, В.Н.Соловьева. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится задача L-оптимального планирования эксперимента. К решению серии обобщенных задач линейного программирования может быть сведена задача MV^-опти-мального планирования. К обобщенным задачам линейного программирования более сложного вида сводятся задача ії-оптимального планирования эксперимента и задача робастного оценивания.
Цели и задачи работы.
1. Решение проблемы застревания симплекс-метода в задачах линейного программирования большой размерности, в которых часть базисных переменных близка к нулю.
Решение аналогичной проблемы для обобщенных задач линейного программирования.
Разработка на основе полученных теоретических результатов алгоритма решения почти вырожденных и обобщенных задач линейного программирования и его применение для решения практических задач оптимального оценивания и коррекции траектории.
Проведение сравнения алгоритма преодоления вырожденности в задачах линейного программирования, предложенного Б.Ц.Бахшияном, с другими аналогичными алгоритмами.
Методы исследования. Для исследования теоретических проблем использовались методы линейной алгебры, теории оптимизации, линейного программирования, теории планирования эксперимента. Для исследования прикладных задач использовались методы компьютерного моделирования.
Научная новизна работы.
Разработан и программно реализован метод решения почти вырожденных задач линейного программирования.
Разработан алгоритм решения обобщенных задач линейного программирования, позволяющий решать вырожденные, почти вырожденные и плохо обусловленные задачи.
3. Полученные теоретические результаты применены для решения
практических задач одноимпульсной линейной коррекции и L-оптимального
оценивания параметров движения.
4. Проведен сравнительный анализ различных алгоритмов преодоления
вырожденности в задачах линейного программирования, разработана и от
лажена программа, реализующая эти алгоритмы, проведены численные рас
четы.
Практическая значимость. Полученные результаты позволяют решать прикладные оптимизационные задачи в различных областях, в том числе в задачах управления космическим полетом, теории оценивания и теории планирования эксперимента.
Апробация работы. Результаты работы докладывались и обсуждались на:
Воронежской весенней математической школе "Современные методы в теории краевых задач"("Понтрягинские чтения - VIII")(Воронеж, 1997),
VI Международной конференции «Идентификация систем и задачи управления» SICPRO '07 (Москва, 2007),
научном семинаре "Управление и устойчивость "под руководством профессоров В.Н.Афанасьева, В.Б.Колмановского, В.Р.Носова, МИЭМ (Москва,
2007),
научном семинаре "Механика, управление и информатика"ИКИ РАН под руководством проф.Р.Р.Назирова (Москва, 2007),
IV Конференции молодых ученых «Фундаментальные и прикладные космические исследования» ИКИ РАН (Москва, 2007).
Публикации. Основные результаты работы изложены в двух статьях и трех тезисах докладов на научных конференциях.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы (36 источников). Объем диссертации - 70 м.п.с.
