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

• Автор: Федяев, Константин Сергеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 69 с. : ил.

Оглавление
Введение
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. Решение расширенной вырожденной задачи 6
2.5.1. Алгоритм для расширенной задачи
2.5.2. Об эффективности нового алгоритма и условиях прекращения вычислений.
3 Решение вырожденных обобщенных задач линейного программирования и практические приложения
3.1. Постановка задачи и алгоритм решения
3.2. Решение вырожденной обобщенной задачи.
3.3. Построение вырожденного базисного решения в обобщенной задаче линейного программирования.
3.4. Оптимальная задача линейной идеальной коррекции
3.4.1. Постановка задачи
3.4.2. Результаты расчетов для задачи одноимпульсной коррекции
3.5. Задача 1оптимального планирования и ее сведение к оптимальной задаче линейной коррекции
3.5.1. Постановка задачи и сведение к задаче идеальной коррекции
3.5.2. Решение задачи.
3.5.3. Построение вырожденной задачи и ее решение. . .
3.5.4. Построение начального базиса в Ьзадаче
3.5.5. Результаты расчетов для случая полиномиальной регрессии.
Заключение
Литература


Однако с развитием области применений линейного программирования и ростом размерности решаемых задач при практических расчетах все чаще стали возникать ситуации, когда зацикливания не происходило, однако на больших последовательностях итераций целевая функция не изменялась, или ее изменение было пренебрежимо мало. Это явление привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью. Указанные методы сводились либо к специальному выбору выводимого из базиса вектора (лексикографическое правило и правило случайного выбора []), либо к выбору вводимого в базис вектора (правило Данцига []), либо к одновременному выбору обоих этих векторов (правило Блэнда []). Разрабатывались также методы, основанные на применении теории двойственности []. Первым методом, позволяющим эффективно преодолевать вырожден-ность, был метод А. Чарнса []. Он сводился к модификации правила выбора выводимой из базиса переменной в случае возникновения вырожден-ности. Одним из наиболее эффективных методов борьбы с вырожденно-стью в настоящее время является метод Вольфа, предложенный впервые в [] и модифицированный в []. Этот метод основан на случайном возмущении нулевых базисных переменных, соответствующем преобразовании правых частей системы ограничений и последующем решении полученной таким образом невырожденной задачи с измененным правилом выбора выводимой из базиса переменной. В результате решения невырожденной задачи строится новый базис исходной вырожденной задачи, соответствующий меньшему значению целевой функции, или делается вывод об оптимальности текущего базиса вырожденной задачи. Таким образом, метод Вольфа требует решения на каждой вырожденной итерации вспомогательной задачи линейного программирования. В результате процесс поиска оптимального решения исходной задачи становится строго монотонным. Однако метод Вольфа имеет два недостатка. Во-первых, размерность вспомогательной задачи совпадает с размерностью исходной. Во-вторых, при решении вспомогательной задачи также могут возникнуть вырожденные итерации, что приводит к необходимости рекурсивного применения предложенной процедуры. Б.Ц. В методе Бахшияна вспомогательная задача имеет размерность строго меньшую размерности исходной задачи. Кроме того, вспомогательная задача с вероятностью 1 невырождена. Эти обстоятельства дают основание предполагать, что алгоритм Бахшияна окажется на практике более эффективным, чем алгоритм Вольфа. Однако до последнего времени алгоритм Бахшияна не был программно реализован, что не позволяло сделать окончательный вывод о целесообразности его применения и апробировать этот алгоритм на решении практических задач. Несмотря на то, что в задачах большой размерности вырожденность становится практически реальным явлением, гораздо чаще наблюдается так называемый случай почти вырожденности, когда в текущем базисном решении часть компонент оказывается близка к нулю. В этом случае изменение целевой функции при переходе от базиса к базису становится пренебрежимо мало по сравнению с ее текущим значением. В этом случае известные методы борьбы с вырожденностью, вообще говоря, неприменимы, так как малые компоненты базисного вектора все же отличны от нуля. Проблема почти вырожденности в настоящее время изучена крайне слабо несмотря на свою актуальность. Среди работ, в которых затрагивалась эта проблема, можно отметить работу [], в которой, в частности, обсуждались изменения в целевой функции, происходящие при обнулении малых компонент базисного решения. Решение проблемы почти вырожденности в задачах линейного программирования является основной темой настоящей работы. Ряд задач теории оценивания и планирования эксперимента сводится к задачам, которые получили в литературе название задач обобщенного линейного программирования [, , 4]. Эти задачи по виду напоминают задачи линейного программирования, однако в них векторы условий-равенств не фиксированы, но выбираются произвольно из некоторых заранее заданных множеств.