Алгоритмы внутренних точек с приближенным решением вспомогательной задачи Филатов А.Ю. к.ф.-м.н., ИСЭМ СО РАН, ИГУ (Иркутск) Пержабинский С.М. ИСЭМ СО.

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

Advertisements

Похожие презентации

Матрица Гильберта при размерности n много большей 1 метод Гаусса не эффективен.

Advertisements

Магистерская диссертация 2009 Журак И.К. 1 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра информационного.

Модель ценовой олигополии с дифференцированным продуктом Филатов А.Ю. к.ф.-м.н., с.н.с. ИСЭМ СО РАН, доцент ИГУ, каф. математической экономики Работа выполнена.

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

1.Точное предписание для выполнения команд 2.Исполнителя, 3.Приводящее за конечное число шагов 4.К конечному результату 1.Точное предписание для выполнения.

Численные методы линейной алгебры. Методы решений нелинейных уравнений и систем. Лекция 3:

Стратегическое взаимодействие фирм, действующих по Курно, и ценополучателей Филатов А.Ю. Иркутский государственный университет, Институт систем энергетики.

Глава 2 МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ 2.1. Общая характеристика методов решения систем линейных уравнений.

Численные методы в оптике кафедра прикладной и компьютерной оптики Аппроксимация.

ОСНОВЫ ПРОГРАММИРОВАНИЯ Раздел 2. Математические основы программирования Численные алгоритмы Старший преподаватель Кафедры ВС, к.т.н. Поляков Артем Юрьевич.

Найди недостающее слагаемое

1 3 o 5 Оценка эффективности инвестиций 6 Определение затрат.

Линейное программирование Задача о покрытии. Задача «Покрытие» Дано: Совокупность U из n элементов, и набор подмножеств U, Ω = {S 1,…, S k }, и веса(стоимости)

Решение квадратных уравнений. Квадратным уравнением называют уравнение вида … … Ответ: ax² + bx + c = 0.

Донецкий Национальный Технический Университет Научно-производственное предприятие ОРАКУЛ СЗАО «Молдавский металлургический завод» представляют: (

Многометодные процедуры оптимального управления Архитектура и реализация программного комплекса Исследовательский Центр процессов управления Работа выполнена.

Лекция 6 по дисциплине «Информационные технологии» на тему: «Решение уравнений и неравенств и системы уравненийв MathCAD» Мамонова Татьяна Егоровна

Двойственность линейного программирования. Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной.

Научный руководитель: доц., к.т.н. Восков Л.С. Аспирант 2-го года обучения Комаров Михаил Михайлович Разработка и исследование метода энергетической балансировки.

Квадратные уравнения Способы решения квадратных уравнений.

Транксрипт:

Алгоритмы внутренних точек с приближенным решением вспомогательной задачи Филатов А.Ю. к.ф.-м.н., ИСЭМ СО РАН, ИГУ (Иркутск) Пержабинский С.М. ИСЭМ СО РАН (Иркутск) Работа выполнена при финансовой поддержке РФФИ (проект а)

Множество оптимальных решений Множество допустимых решений Множество оптимальных решений Множество допустимых решений Траектория симплекс-методаТраектория методов внутренних точек 1939 – линейное программирование (Канторович) – симплекс-метод (Данциг) – метод внутренних точек (Дикин) – полиномиальный МВТ (Кармаркар) е – эффективные программные реализации. CPlex ( BPMPD ( MOSEK ( HOPDM ( Исторический экскурс

Основные классы алгоритмов внутренних точек (1) (2) Пара взаимно-двойственных задач линейного программирования Аффинно-масштабирующие алгоритмы. Алгоритмы центрального пути. Алгоритмы скошенного пути. Комбинированные алгоритмы. Прямые алгоритмы. Двойственные алгоритмы. Прямо-двойственные алгоритмы.

Аффинно-масштабирующие алгоритмы внутренних точек Стартовое приближение: Итеративный переход: Задача поиска направления корректировки: Шаг корректировки: (3) Способы выбора весовых коэффициентов: (4) (5) (6) (7)

Алгоритмы центрального пути (имеют полиномиальные оценки) Логарифмическая барьерная функция: (8) Задача поиска направления корректировки: Комбинированные алгоритмы (используют параметризацию) (10) (9) Задача поиска направления корректировки:

Решение вспомогательной задачи Аффинно-масштабирующие алгоритмы: Алгоритмы центрального пути: Комбинированные алгоритмы: (11) (12) (13) (14) (17) (18) (15) (16)

Методы решения вспомогательной задачи Метод Гаусса. Метод Халецкого (метод квадратного корня). Метод сопряженных направлений. Метод Зейделя. Другие приближенные итеративные методы. Предпосылки использования приближенных итеративных методов На первых итерациях достаточно искать приближенное направление корректировки, используя вектор, для которого. В финале вычислительного процесса, диагональная мат- рица изменяется по итерациям очень незначительно, имеется хорошее стартовое приближение.

Метод сопряженных направлений Направление корректировки: Шаг, определяющий вариант метода: Итеративный переход: Шаг корректировки:

Размерность m Число итераций Минимал. Максимал. Среднее Среднекв. отклонение ,786, ,985, ,064, ,4814,04 Экспериментальное исследование Число итераций, необходимое для решения задач при n=1,2m Размерность m Число итераций Минимал. Максимал. Среднее Среднекв. отклонение ,042, ,261, ,141, ,542,35 Число итераций, необходимое для решения задач при n=1,5m

Параметры управления алгоритмом Вариант приближенного метода. – параметр в условии останова δ – параметр в условие перехода с точного на приближенный метод K – максимальное число выполняемых подряд итераций приближенного метода. t – число внутренних итераций приближенного метода. Процедуры корректировки формул (3), (10) и формул вычисления максимального шага на фазе 1. – прогноз шага корректировки.

Спасибо за внимание!