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

Презентация:



Advertisements
Похожие презентации
Б.Ц.Бахшиян АЛГОРИТМ РЕШЕНИЯ ПОЧТИ ВЫРОЖДЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО ПРИМЕНЕНИЕ В ЗАДАЧАХ КОСМИЧЕСКОЙ НАВИГАЦИИ.
Advertisements

Задача линейного программирования. Матричный симплекс-метод.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 17. Тема: Графический метод и симплекс-метод задачи.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 16. Тема: Линейное программирование. Цель: Ознакомиться.
Просмотр Теоретического материала Гирич СН 1 Ввод задачи Гирич СН 3 Пользователь Отчет решения задачи Теоретический материал Целевая функция; система неравенств.
Симплекс-метод Лекции 6, 7. Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором.
Линейное программирование Двойственность в линейном программировании.
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
Часть 2 Двойственные задачи Правила построения двойственных задач.
Задача линейного программирования. Табличный симплекс-метод.
Этапы моделирования. Определение цели моделирования, выделение существенных для исследования параметров объекта. I. Построение описательной информационной.
3. Понятие линейной зависимости и независимости. Базис Пусть L – линейное пространство над F, a 1,a 2, …, a k L. ОПРЕДЕЛЕНИЕ. Говорят, что векторы a 1,a.
Лекция 2 Часть I: Многомерное нормальное распределение, его свойства; условные распределения Часть II: Парная линейная регрессия, основные положения.
Решение задачи линейного программирования методом последовательного улучшения плана ( Симплексный методом )
ЭКОНОМИКО- МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.
Задача линейного программирования. Табличный симплекс-метод. Использование искусственных переменных.
Основная задача линейного программирования Симплекс-метод.
Математика Экономико-математические методы Векслер В.А., к.п.н.
Прямая и двойственная задачи и их решение симплекс-методом Лекции 8, 9.
алгоритм решения оптимизационной задачи л инейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.оптимизационнойл.
Транксрипт:

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

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

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

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

ba1a1 a2a2 a3a3 a4a4 anan

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

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

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

b a1a1 a2a2 a3a3 a4a4 a0a0 anan

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

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

b a1a1 a3a3 a2a2 a0a0

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