автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы решения почти вырожденных задач линейного программирования и их применение в задачах оценивания и коррекции траектории

Введение

1 Основные сведения из теории линейного программирования. Вырожденность, методы ее преодоления

1.1. Постановка задачи и алгоритм симплекс-метода.

1.2. Построение допустимого базисного решения

1.3. Проблема вырожденности. Формальное описание

1.4. Алгоритм Вольфа.

1.5. Алгоритм Бахшияна.

1.6. Сведение задачи 3 к задаче 5.

1.7. Сравнение алгоритмов Вольфа и Бахшияна на примере решения задачи большой размерности.

2 Почти вырожденные задачи линейного программирования и методы их решения

2.1. Введение.

2.2. Постановка задачи.

2.3. Демонстрация основных идей на примерах.

2.3.1. Об алгоритме решения строго вырожденной задачи.

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

2.4. Конструирование расширенной задачи в общем случае

2.5. Решение расширенной вырожденной задачи

2.5.1. Алгоритм для расширенной задачи.

2.5.2. Об эффективности нового алгоритма и условиях прекращения вычислений.

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

3.1. Постановка задачи и алгоритм решения.

3.2. Решение вырожденной обобщенной задачи.

3.3. Построение вырожденного базисного решения в обобщенной задаче линейного программирования.

3.4. Оптимальная задача линейной идеальной коррекции

3.4.1. Постановка задачи.

3.4.2. Результаты расчетов для задачи одноимпульсной коррекции.

3.5. Задача L-оптимального планирования и ее сведение к оптимальной задаче линейной коррекции

3.5.1. Постановка задачи и сведение к задаче идеальной коррекции.

3.5.2. Решение L-задачи.

3.5.3. Построение вырожденной L-задачи и ее решение.

3.5.4. Построение начального базиса в L-задаче.

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

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

Актуальность работы. Вырожденные задачи линейного программирования стали объектом изучения фактически сразу после возникновения линейного программирования как самостоятельной научной дисциплины. Однако в первое время вырожденность рассматривалась исключительно в контексте проблемы зацикливания симплекс-метода [12, 25]. В подавляющем большинстве работ того периода указывалось, что на практике случаи вырождения весьма редки, а зацикливания при решении практических задач никогда не наблюдается (см., например, [25]). Проблема построения примеров зацикливания представляла самостоятельный научный интерес, этому вопросу посвящались отдельные работы как в начале развития теории линейного программирования (см. [27]), так и в дальнейшем (см., например, [31, 36]).

Однако с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, однако на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью. Однако большинство классических методов теории вырожденного линейного программирования по-прежнему было посвящено лишь борьбе с зацикливанием, избежать вырожденных итераций при использовании таких методов не удавалось. Указанные методы сводились либо к специальному выбору выводимого из базиса вектора (лексикографическое правило и правило случайного выбора [12]), либо к выбору вводимого в базис вектора (правило Данцига [30]), либо к одновременному выбору обоих этих векторов (правило Блэнда [28]). Разрабатывались также методы, основанные на применении теории двойственности [26].

Первым методом, позволяющим эффективно преодолевать вырожденность, был метод А.Чарнса [29]. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожденности. Одним из наиболее эффективных методов борьбы с вырожденностью в настоящее время является метод Вольфа, предложенный впервые в [35] и модифицированный в [34]. Этот метод основан на случайном возмущении нулевых базисных переменных, соответствующем преобразовании правых частей системы ограничений и последующем решении полученной таким образом невырожденной задачи с измененным правилом выбора выводимой из базиса переменной. В результате решения невырожденной задачи строится новый базис исходной вырожденной задачи, соответствующий меньшему значению целевой функции, или делается вывод об оптимальности текущего базиса вырожденной задачи. Таким образом, метод Вольфа требует решения на каждой вырожденной итерации вспомогательной задачи линейного программирования. В результате процесс поиска оптимального решения исходной задачи становится строго монотонным. Однако метод Вольфа имеет два недостатка. Во-первых, размерность вспомогательной задачи совпадает с размерностью исходной. Во-вторых, при решении вспомогательной задачи также могут возникнуть вырожденные итерации, что приводит к необходимости рекурсивного применения предложенной процедуры.

Б.Ц.Бахшияном в работе [1] был предложен другой алгоритм, сходный с арлгоритмом Вольфа по подходу к преодолению вырожденности, но отличающийся по принципу построения вспомогательной задачи и по ее виду. В методе Бахшияна вспомогательная задача имеет размерность строго меньшую размерности исходной задачи. Кроме того, вспомогательная задача с вероятностью 1 невырождена. Эти обстоятельства дают основание предполагать, что алгоритм Бахшияна окажется на практике более эффективным, чем алгоритм Вольфа. Однако до последнего времени алгоритм Бахшияна не был программно реализован, что не позволяло сделать окончательный вывод о целесообразности его применения и апробировать этот алгоритм на решении практических задач.

Несмотря на то, что в задачах большой размерности вырожденность становится практически реальным явлением, гораздо чаще наблюдается так называемый случай почти вырожденности, когда в текущем базисном решении часть компонент оказывается близка к нулю. В этом случае изменение целевой функции при переходе от базиса к базису становится пренебрежимо мало по сравнению с ее текущим значением. В этом случае известные методы борьбы с вырожденностью, вообще говоря, неприменимы, так как малые компоненты базисного вектора все же отличны от нуля. Проблема почти вырожденности в настоящее время изучена крайне слабо несмотря на свою актуальность. Среди работ, в которых затрагивалась эта проблема, можно отметить работу [16], в которой, в частности, обсуждались изменения в целевой функции, происходящие при обнулении малых компонент базисного решения. Решение проблемы почти вырожденности в задачах линейного программирования является основной темой настоящей работы.

Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые получили в литературе название задач обобщенного линейного программирования [12, 20, 4]. Эти задачи по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств. Такие задачи иногда также называют многопараметрическими задачами линейного программирования. Методы решения обобщенных задач обсуждались в работах Дж.Данцига, Л.Лэсдона, М.Мину, М.Л.Лидова, Б.Ц.Бахшияна и др. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится также задача L-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена также задача МУ5-оптимального планирования [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]. К задачам обобщенного линейного программирования сводится, например, задача идеальной линейной импульсной коррекции. К задаче оптимальной линейной импульсной коррекции со специально построенными матрицами условий (а, следовательно, и к задаче обобщенного линейного программирования) сводится задача .^-оптимального планирования эксперимента [5]. К решению серии обобщенных задач линейного программирования может быть сведена задача MV^-оптимального планирования [9]. К обобщенным задачам линейного программирования более сложного вида сводятся задача ^-оптимального планирования эксперимента и задача робастного оценивания [10, 2].

Цели и задачи работы.

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

- 82. Решение аналогичной проблемы для обобщенных задач линейного программирования.

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

4. Проведение сравнения алгоритма преодоления вырожденности в задачах линейного программирования, предложенного Б.Ц.Бахшияном, с другими аналогичными алгоритмами.

Методы исследования. Для исследования теоретических проблем использовались методы линейной алгебры, теории оптимизации, линейного программирования, теории планирования эксперимента. Для исследования прикладных задач использовались методы компьютерного моделирования.

Научная новизна работы.

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

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

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

4. Проведен сравнительный анализ различных алгоритмов преодоления вырожденности в задачах линейного программирования, разработана и отлажена программа, реализующая эти алгоритмы, проведены численные расчеты.

Практическая значимость. Полученные результаты позволяют решать прикладные оптимизационные задачи в различных областях, в том числе в задачах управления космическим полетом, теории оценивания и теории планирования эксперимента.

Апробация работы. Результаты работы докладывались и обсуждались на

- Воронежской весенней математической школе "Современные методы в теории краевых задач"("Понтрягинские чтения - УШ")(Воронеж, 1997),

- VI Международной конференции «Идентификация систем и задачи управления» SICPRO '07 (Москва, 2007),

- научном семинаре "Управление и устойчивость "под руководством профессоров В.Н.Афанасьева, В.Б.Колмановского, В.Р.Носова, МИЭМ (Москва, 2007),

- научном семинаре "Механика, управление и информатика"ИКИ РАН под руководством проф.Р.Р.Назирова (Москва, 2007),

- IV Конференции молодых ученых «Фундаментальные и прикладные космические исследования» ИКИ РАН (Москва, 2007).

Публикации. Основные результаты работы изложены в двух статьях [3, 6] и трех тезисах докладов на научных конференциях [7, 8, 24].

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы (36 источников). Объем диссертации - 69 м.п.с.

Заключение

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

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

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

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

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

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

1. Бахшиян Б.Ц. Критерии оптимальности и алгоритмы решения вырожденной и обобщенной задач линейного программирования // Экономика и математические методы, т.ХХУ, вып.2, 1989. С.314-324.

2. Б.Ц.Бахшиян, М.И.Бойсковский. О возможности эффективного решения задачи оценивания при линейных ограничениях на оцениваемый вектор // Известия РАН. Теория и системы управления. 2003. №4.

3. Бахшиян Б.Ц., Матасов А.И., Федяев К. С. О решении вырожденных задач линейного программирования. Автоматика и телемеханика. 2000. № 1. С.105-117.

4. Бахшиян Б.Ц., Назиров P.P., Эльясберг П.Е. Определение и коррекция движения. М: Наука, 1980.

5. Бахшиян Б.Ц., Соловьев Б.Н. Теория и алгоритмы решения задач L-и MV-оптимального планирования эксперимента. Автоматика и телемеханика. 1998. № 8. С.80-96

6. Бахшиян Б.Ц., Федяев К. С. О решении почти вырожденных и плохо обусловленных задач линейного программирования, возникающих при управлении системой. // Известия РАН. Теория и системы управления. 2005. № 6. С.77-88.

7. Бахшиян Б.Ц., Федяев К. С. О решении почти вырожденных и плохо обусловленных задач навигации методами линейного программирования // Труды VI Международной конференции "Идентификация систем и задачи управления"81СР110'07 М., 2007.

8. М.И.Войсковский. Симплексный алгоритм решения задачи MV-оптимального планирования эксперимента. Препринт № 1979. М.: Ин-т космических исследований РАН, 1998.

9. Войсковский М.И. Симплексный алгоритм поиска Е-оптимальных планов // Известия РАН. Теория и системы управления. 2001. №2.

10. И. В.А.Гамулин. Решение MV-задачи оптимального планирования эксперимента для полиномиальной и тригонометрической моделей измерений // Известия РАН. Теория и системы управления. 2003. №3. С.97102

11. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. (G.B.Dantzig. Linear Programming and Extensions. Princeton U.P., 1963.)

12. Ермаков C.M., Жиглявский А.А. Математическая теория оптимального эксперимента. М., Наука, 1987.

13. JIudoe M.JI. Математическая аналогия между некоторыми оптимальными задачами коррекции траекторий и выбора состава измерений и алгоритмы их решения // Космические исследования. 1971. Т.9. № 5.

14. Лидов М.Л. Эффективный алгоритм решения задачи о выборе оптимальной программы измерений // Космические исследования. 1985. Т.23. т. С. 499

15. JIudoe M.JI. О модификации симплекс-метода линейного программирования в случае вырождения // Космические исследования. 1991. Т.29. № 4. С.499-508.

16. М.Л.Лидов, Б.Ц.Бахшиян, А.И.Матасов. Об одном направлении в проблеме гарантирующего оценивания // Космические исследования. 1991. Т.29. Вып.5. С.659-684.

17. Лэсдон Л. С. Оптимизация больших систем. М: Наука, 1975.

18. Мелас В. Б. Одна теорема двойственности и Е-оптимальность// Заводская лаборатория. Т.82. №3. С. 48-50.

19. Мину М. Математическое программирование. Теория и алгоритмы: пер. с фр. М., Наука, 1989.

20. Муртаф Б. Современное линейное программирование. М.: Мир. 1984. (A.Murtagh. Advanced Linear Programming: Computation and Practice. McGraw-Hill International Book Company, 1981.)

21. Рокафеллар P. Выпуклый анализ. M.: Мир, 1973.

22. Федоров В. В. Активные регрессионные эксперименты // Математические методы планирования эксперимента. Новосибирск: Наука, 1983. С.19.

23. Федяев К. С. Применение алгоритма преодоления вырожденных итераций при решении задачи L-оптимального оценивания параметров системы: Тез. докл. IV Конф. молодых ученых «Фундаментальные и прикладные космические исследования» М.: ИКИ РАН, 2007.

24. Юдин Д.Б., Голъштейн Е.Г. Линейное программирование. Теория, методы и приложения. М., Наука, 1969.

25. E.Barnes, V.Chen, B.Gopalakrishnan, E.L.Johnson. A least-squares primal-dual algorithm for solving linear program ming problems // Operation Research Letters. 2002. V. 30. P. 289-294.

26. Beale E.M.L Cycling in the dual simplex algorithm. Nav.Res.Logist.Quart, 1955, v.2, p.269-275.

27. Bland R.G. New finite pivot rules for simplex method // Math.Oper.Res. 1977. V.2. P. 103-107.

28. Charnes A. Optimality and degeneracy in linear programming // Econometrica, 1952, V.20, P. 160-170.

29. Dantzig G.B. Making progress during a stall in the simplex algorithm // Linear Algebra and its Applications. 1989. V.114/115. P. 251-259.

30. S.I.Gass, S.Vinjamuri. Cycling in linear programming problems // Computers к Operations Research. 2004. No 31. P. 303-311

31. Kotiun T.C. Т., Steinberg D.I. On the possibility cycling with the simplex method // Oper.Res. 1984. V. 26. No. 2. P. 374-376.

32. Pukelsheim F. Optimal design of experiments. New York: J.Wiley and Sons, 1993.

33. Ryan D.M., Osborne M.R. On the solution of higly degenerate linear programmes // Mathematical Programming, v.41, 1988. P.385-392.

34. Wolfe P. A technique for resolving degeneracy in linear programming // Journal Soc. Indust. Appl. Math., v. 11, 1963. P.205-211.

35. P.Zdrnig. Systematic construction of examples for cycling in the simplex method // Computers к Operations Research. 2006. No 33. P.2247-2262.