Методы решения почти вырожденных и плохо обусловленных задач линейного программирования и их применение в задачах оценивания и коррекции траектории
Диссертация
Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые получили в литературе название задач обобщенного линейного программирования. Эти задачи по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств. Такие задачи иногда также называют… Читать ещё >
Содержание
- 1. Основные сведения из теории линейного программирования. Вырожденность, методы ее преодоления
- 1. 1. Постановка задачи и алгоритм симплекс-метода
- 1. 2. Построение допустимого базисного решения
- 1. 3. Проблема вырожденности. Формальное описание
- 1. 4. Алгоритм Вольфа
- 1. 5. Алгоритм Бахшияна
- 1. 6. Сведение задачи 3 к задаче
- 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. 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. Результаты расчетов для случая полиномиальной регрессии
Список литературы
- Бахшиян Б.Ц. Критерии оптимальности и алгоритмы решения вырожденной и обобщенной задач линейного программирования // Экономика и математические методы, t. XXV, вып.2, 1989. С.314−324.
- Б.Ц.Бахшиян, М. И. Войсковский. О возможности эффективного решения задачи оценивания при линейных ограничениях на оцениваемый вектор // Известия РАН. Теория и системы управления. 2003. № 4.
- Бахшиян Б.Ц., Матасов А. И., Федяев К. С. О решении вырожденных задач линейного программирования. Автоматика и телемеханика. 2000. № 1. С.105−117.
- Бахшиян Б.Ц., Назиров P.P., Эльясберг П. Е. Определение и коррекция движения. М: Наука, 1980.
- Бахшиян Б.Ц., Соловьев В. Н. Теория и алгоритмы решения задач L-и MV-оптимального планирования эксперимента. Автоматика и телемеханика. 1998. № 8. С.80−96
- Бахшиян Б.Ц., Федяев К. С. О решении почти вырожденных и плохо обусловленных задач линейного программирования, возникающих при управлении системой. // Известия РАН. Теория и системы управления. 2005. № 6. С.77−88.
- Бахшиян Б.Ц., Федяев К. С. О решении почти вырожденных и плохо обусловленных задач навигации методами линейного программирования // Труды VI Международной конференции «Идентификация систем и задачи управления «SICPRO'07 М., 2007.
- М.И.Войсковский. Симплексный алгоритм решения задачи МУ-оптимального планирования эксперимента. Препринт № 1979. М.: Ин-т космических исследований РАН, 1998.
- Войсковский М.И. Симплексный алгоритм поиска Е-оптимальных планов // Известия РАН. Теория и системы управления. 2001. № 2.
- В.А.Гамулин. Решение МУ-задачи оптимального планирования эксперимента для полиномиальной и тригонометрической моделей измерений // Известия РАН. Теория и системы управления. 2003. № 3. С.97−102
- Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. (G.B.Dantzig. Linear Programming and Extensions. Princeton U.P., 1963.)
- Ермаков C.M., Жиглявский А. А. Математическая теория оптимального эксперимента. М., Наука, 1987.
- JIudoe M.JI. Математическая аналогия между некоторыми оптимальными задачами коррекции траекторий и выбора состава измерений и алгоритмы их решения // Космические исследования. 1971. Т.9. № 5.
- JIudoe M.JI. Эффективный алгоритм решения задачи о выборе оптимальной программы измерений // Космические исследования. 1985. Т.23. № 4. С. 499
- JIudoe M.JI. О модификации симплекс-метода линейного программирования в случае вырождения // Космические исследования. 1991. Т.29. № 4. С.499−508.
- M.JI.JIudoe, Б. Ц. Бахшиян, А. И. Матасов. Об одном направлении в проблеме гарантирующего оценивания // Космические исследования. 1991. Т.29. Вып.5. С.659−684.
- Лэсдон Л. С. Оптимизация больших систем. М: Наука, 1975.
- Мелас В.Б. Одна теорема двойственности и Е-оптимальность// Заводская лаборатория. Т.82. № 3. С. 48−50.
- Мину М. Математическое программирование. Теория и алгоритмы: пер. с фр. М., Наука, 1989.
- Муртаф Б. Современное линейное программирование. М.: Мир. 1984. (A.Murtagh. Advanced Linear Programming: Computation and Practice. McGraw-Hill International Book Company, 1981.)4
- Рокафеллар P. Выпуклый анализ. M.: Мир, 1973.
- Федоров В. В. Активные регрессионные эксперименты // Математические методы планирования эксперимента. Новосибирск: Наука, 1983. С. 19.
- Федяев К. С. Применение алгоритма преодоления вырожденных итераций при решении задачи L-оптимального оценивания параметров системы: Тез. докл. IV Конф. молодых ученых «Фундаментальные и прикладные космические исследования» М.: ИКИ РАН, 2007.
- Юдин Д.В., Голъштейн Е. Г. Линейное программирование. Теория, методы и приложения. М., Наука, 1969.
- 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. .
- Beale E.M.L Cycling in the dual simplex algorithm. Nav.Res.Logist.Quart, 1955, v.2, p.269−275.
- Bland R. G. New finite pivot rules for simplex method // Math.Oper.Res. 1977. V.2. P.103−107.
- Charnes A. Optimality and degeneracy in linear programming // Econometrica, 1952, V.20, P. 160−170.
- Dantzig G.B. Making progress during a stall in the simplex algorithm // Linear Algebra and its Applications. 1989. V.114/115. P. 251−259.
- S.I. Gass, S.Vinjamuri. Cycling in linear programming problems // Computers к Operations Research. 2004. No 31. P. 303−311
- Kotiun T.C. Т., Steinberg D.I. On the possibility cycling with the simplex method // Oper.Res. 1984. V. 26. No. 2. P. 374−376. -
- Pukelsheim F. Optimal design of experiments. New York: J. Wiley and1. Sons, 1993. •i i
- Ryan D.M., Osborne M.R. On the solution of higly degenerate linear programmes // Mathematical Programming, v.41, 1988. P.385−392.
- Wolfe P. A technique for resolving degeneracy in linear programming / / Journal Soc. Indust. Appl. Math., v. ll, 1963. P.205−211.
- P.Zornig. Systematic construction of examples for cycling in the simplex method // Computers к Operations Research. 2006. No 33. P.2247−2262.