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

• Автор: Горяинов, Александр Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 96 с. : ил.

Оглавление
Введение

0.1. Основные сведения из теории линейного программирования

0.1.1. Постановка задачи. Симплекс-метод

0.1.2. Вырожденность решения

0.2. Обобщенные задачи линейного программирования

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

0.2.2. О сходимости алгоритма генерации столбцов

0.3. Цели и структура работы

1. Скелетный алгоритм решения задачи линейного программирования

1.1. Теоретические основы алгоритма

1.1.1. Расширенная и вспомогательная задачи
1.1.2. Построение серии вспомогательных задач
1.1.3. Основные теоремы
1.2. Описание итераций
1.2.1. Решение одномерной задачи
1.2.2. Подъем и спуск
1.3. Пошаговое описание алгоритма
2. Модификация скелетного алгоритма для обобщенной задачи линейного программирования

2.1. Модификация полученных результатов для случая обобщенной задачи
2.2. Пошаговое описание алгоритма
2.3. О сходимости скелетного алгоритма
3. Применение скелетного алгоритма
3.1. Преодоление проблемы вырожденных итераций
3.1.1. Случай вырожденного решения
3.1.2. Случай почти вырожденного решения
3.2. Нахождение выпуклой оболочки конечного числа векторов .
3.2.1. Численные эксперименты
3.3. Минимаксная задача оценивания в предположении, что ошибки ограничены по модулю
3.3.1. Постановка задачи и ее сведение к обобщенной задаче линейного программирования
3.3.2. Численные эксперименты
3.4. Задача оптимальной идеальной линейной импульсной коррекции траектории
3.4.1. Постановка задачи и ее сведение к обобщенной задаче линейного программирования
3.4.2. Численные эксперименты
3.5. Задача ^-оптимального планирования эксперимента
3.5.1. Постановка задачи и сведение к обобщенной задаче линейного программирования
3.5.2. Численные эксперименты
Заключение
Литература
Введение
Объектом исследования в диссертационной работе являются два типа задач условной оптимизации: обычные и обобщенные задачи линейного программирования, а также алгоритмы решения этих задач.
К задачам линейного программирования сводится множество практических задач, встречающихся в разных областях экономики и техники. Теоретическая и практическая сторона решения задачи линейного программирования на сегодняшний день хорошо разработана (см., например, [34,41]), однако отдельные вопросы, связанные с так называемой проблемой вырожденное были разрешены не так давно [4, 12, 15]. Полученные в рамках борьбы с вырожденностью результаты представляют самостоятельный интерес и являются основой для предлагаемого в настоящей работе нового алгоритма.
Методы обобщенного линейного программирования особенно широко применяются при решении оптимальных задач определения и коррекции движения системы. Обе эти задачи тесно связаны между собой, являясь составными частями так называемого дискретного управления движением, при котором управляющие воздействия подаются не непрерывно, а в виде дискретных корректирующих импульсов, скачкообразно изменяющих характер движения управляемой системы. При этом каждой коррекции предшествует определение фактического движения, па основе которого вычисляется требуемое значение корректирующего импульса. Классическим примером подобного управления может служить коррекция орбиты косми-
следует в этом случае соотношение вида (1.6):
з і о Г1
ар — а рГ І а
= а а0,
где р1г

— °/(1) — прообраз вектора а() в пространстве
Далее в зависимости от знака а проделываем действия, аналогичные

описанным выше для двумерной задачи. Если су > 0, то вводим в базис
трехмерной задачи векторы ар, ріг

/(!)> Р*
од2), переходим К

эквивалентной расширенной задаче, вводя аопеи] и с0пеи), и вычисляем новые 2 1
значения ^ и с$. Если а < 0, то переходим к рассмотрению соотношений
для четырехмерной задачи.
Процедура подъема и спуска в общем случае
Основываясь на изложенном выше, опишем теперь процедуры подъема и спуска в общем случае.
Пусть одномерная задача неразрешима. Записывая выражения вида (1.6),
2 3 3-І _ 3-І
последовательно находим из них а, а,..., а . Если а < 0, то при переходе
от (у — 1)-мерной задачи к у-мерной мы, согласно утверждению 1.2, получаем уравнение:
ар — а рб
Возможны два случая. з

1 ' 1 ■ з-1 , 1-і' з і
Ц() — ... — а рЬ ао = а «о
(1.18)
1) Величина а < 0. Тогда ^'-мерная задача не имеет решения и мы, снова воспользовавшись утверждением 1.2, переходим к аналогичному соотношению для (у + 1)-мерной задачи:

1+11+1 = а а0 .
Тем самым осуществляется подъем к (_? + 1)-мерной задаче.