Федяев Константин Сергеевич Институт космических исследований РАН Решение плохо обусловленных задач линейного программирования большой размерности. - презентация

1 Федяев Константин Сергеевич Институт космических исследований РАН Решение плохо обусловленных задач линейного программирования большой размерности

2 Постановка задачи Векторная форма записи:

3 Задача линейного программирования Симплекс-метод

4 b a1a1 a2a2 a3a3 Базис: a 1, a 2 a 1, a 3 a4a4 a5a5

5 ba1a1 a2a2 a3a3 a4a4 anan

6 Вырожденность Вспомогательная задача (Бахшиян, 1989): - вырожденная итерация

7 Построение нового базиса в основной задаче

8 ba1a1 a2a2 a3a3 a4a4 h3h3 Обычный алгоритм: Алгоритм Бахшияна: anan

9 b a1a1 a2a2 a3a3 a4a4 a0a0 anan

10 Почти вырожденные задачи

11 Лемма 1. Вектор y является вырожденным допустимым базисным решением расширенной задачи (РЗ), имеющим порядок вырожден- ности не меньший чем |I 0 |. Вектору y в задаче (РЗ) соответствует то же значение целевой функции, что и вектору x в основной задаче (ОЗ). Лемма 2. Вектор является допустимым решением основной задачи (ОЗ), причем ему соответствует то же значение целевой функции, что и вектору y в расширенной задаче (РЗ). Лемма 3. Если вектор y является оптимальным решением расширенной задачи (РЗ), то вектор является оптимальным решением основной задачи (ОЗ).

12 b a1a1 a3a3 a2a2 a0a0

13 Определение параметров движения космического объекта (астероид Апофис) Модель измерений: - оцениваемый параметр, Условие несмещенности: Задачасводится к задаче