Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Алгоритмы внутренних точек с приближенным решением вспомогательной задачи

Содержание

1939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод внутренних точек (Дикин).1984 – полиномиальный МВТ (Кармаркар).1990-е - 2007 – эффективные программные реализации. CPlex (http://maximal-usa.com), BPMPD (http://sztaki.hu), MOSEK (http://mosek.com), HOPDM (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html) Исторический экскурс
Алгоритмы внутренних точекс приближенным решениемвспомогательной задачиФилатов А.Ю.к.ф.-м.н., ИСЭМ СО РАН, ИГУ (Иркутск)Пержабинский 1939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод внутренних точек Основные классы алгоритмоввнутренних точек(1)(2)Пара взаимно-двойственных задачлинейного программирования Аффинно-масштабирующие алгоритмы. Алгоритмы центрального пути. Аффинно-масштабирующиеалгоритмы внутренних точекСтартовое приближение:Итеративный переход:Задача поиска направления корректировки:Шаг корректировки:(3)Способы выбора весовых коэффициентов:(4)(5)(6)(7) Алгоритмы центрального пути(имеют полиномиальные оценки)Логарифмическая барьерная функция:(8)Задача поиска направления корректировки:Комбинированные алгоритмы(используют параметризацию)(10)(9)Задача поиска направления корректировки: Решение вспомогательной задачиАффинно-масштабирующие алгоритмы:Алгоритмы центрального пути:Комбинированные алгоритмы:(11)(12)(13)(14)(17)(18)(15)(16) Методы решениявспомогательной задачи Метод Гаусса. Метод Халецкого (метод квадратного корня). Метод сопряженных Метод сопряженных направленийНаправление корректировки:Шаг, определяющий вариант метода:Итеративный переход:Шаг корректировки: Экспериментальное исследованиеЧисло итераций, необходимое для решения задач при n=1,2mЧисло итераций, необходимое для решения задач при n=1,5m Параметры управления алгоритмом Вариант приближенного метода.  – параметр в условии останова Спасибоза внимание!
Слайды презентации

Слайд 2 1939 – линейное программирование (Канторович).
1947 – симплекс-метод (Данциг).
1967

1939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод внутренних

– метод внутренних точек (Дикин).
1984 – полиномиальный МВТ (Кармаркар).
1990-е

- 2007 – эффективные программные реализации.

CPlex (http://maximal-usa.com), BPMPD (http://sztaki.hu), MOSEK (http://mosek.com),
HOPDM (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html)

Исторический экскурс

Слайд 3 Основные классы алгоритмов
внутренних точек
(1)

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

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

алгоритмы.
Алгоритмы центрального пути.
Алгоритмы скошенного пути.
Комбинированные алгоритмы.

Прямые алгоритмы.
Двойственные алгоритмы.
Прямо-двойственные алгоритмы.

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

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

корректировки:
(3)
Способы выбора весовых коэффициентов:
(4)
(5)
(6)
(7)

Слайд 5 Алгоритмы центрального пути
(имеют полиномиальные оценки)
Логарифмическая барьерная функция:
(8)
Задача поиска

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

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

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

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

Слайд 7 Методы решения
вспомогательной задачи
Метод Гаусса.
Метод Халецкого (метод

Методы решениявспомогательной задачи Метод Гаусса. Метод Халецкого (метод квадратного корня). Метод

квадратного корня).

Метод сопряженных направлений.
Метод Зейделя.
Другие приближенные

итеративные методы.

Предпосылки использования
приближенных итеративных методов

На первых итерациях достаточно искать приближенное
направление корректировки , используя вектор ,
для которого .

В финале вычислительного процесса, диагональная мат-
рица изменяется по итерациям очень незначительно,
имеется хорошее стартовое приближение .

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

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

корректировки:

Слайд 9 Экспериментальное исследование
Число итераций, необходимое для решения задач при

Экспериментальное исследованиеЧисло итераций, необходимое для решения задач при n=1,2mЧисло итераций, необходимое для решения задач при n=1,5m

n=1,2m
Число итераций, необходимое для решения задач при n=1,5m

Слайд 10 Параметры управления алгоритмом
Вариант приближенного метода.
 –

Параметры управления алгоритмом Вариант приближенного метода.  – параметр в условии

параметр в условии останова
δ – параметр в условие

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

– прогноз шага корректировки.

  • Имя файла: algoritmy-vnutrennih-tochek-s-priblizhennym-resheniem-vspomogatelnoy-zadachi.pptx
  • Количество просмотров: 95
  • Количество скачиваний: 0
- Предыдущая Квадратичная функция
Следующая - ГБПОУ НО Нижегородский медицинский колледжПрезентация по информатикеТема: Алгоритмы

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

Программа MS Office Access Программа MS Office Access 113
Искусство Древнего мира Искусство Древнего мира 26
Системы связи плезиохронной и синхронной цифровой иерархии Системы связи плезиохронной и синхронной цифровой иерархии 106
Способы общения в Интернете Способы общения в Интернете 138
Электронные таблицы Microsoft Excel Электронные таблицы Microsoft Excel 118
Дошколенок и Компьютер презентация по информатике Дошколенок и Компьютер презентация по информатике 125
Истина и ложь презентация к уроку по информатике (4 класс) по теме Истина и ложь презентация к уроку по информатике (4 класс) по теме 133
Демонстрация на тему Системный реестр Демонстрация на тему Системный реестр 106
Презентация по информатике на тему Хакеры: гении или злодеи? Презентация по информатике на тему Хакеры: гении или злодеи? 138
Информационная деятельность Информационная деятельность 175
Как безопасно проводить время в интернете Как безопасно проводить время в интернете 133
Презентация: по информатике на тему Информационная деятельность человека Презентация: по информатике на тему Информационная деятельность человека 143
Установка windows 7 на ноутбук с флеш накопителя Установка windows 7 на ноутбук с флеш накопителя 100
Презентация Microsoft Powerpoint Презентация Microsoft Powerpoint 116
Компьютерные вирусы, их виды. Антивирусы Компьютерные вирусы, их виды. Антивирусы 119
Алгоритмические структуры. Решение задач Алгоритмические структуры. Решение задач 169
Информатика в играх и задачах Информатика в играх и задачах 126
Презентация по информатике Моделирование как метод познания (9 класс) Презентация по информатике Моделирование как метод познания (9 класс) 177
Робот для траектории на основе Lego Mindstorms EV3 Робот для траектории на основе Lego Mindstorms EV3 137
Какая бывает информация? Какая бывает информация? 97
Примеры моделирования Примеры моделирования 148
Презентация по информатике на тему Информационное общество (9 класс) Презентация по информатике на тему Информационное общество (9 класс) 147
Числа в памяти компьютера Числа в памяти компьютера 125
Алгоритм и его формальное исполнение Алгоритм и его формальное исполнение 86
Презентация Мир без Интернета Презентация Мир без Интернета 213
Презентация по информатике: Реальна ли реальность Презентация по информатике: Реальна ли реальность 118
Основы передачи дискретных данных Основы передачи дискретных данных 109
Презентация по информатике на тему Cookie Презентация по информатике на тему Cookie 110
Файловая структура хранения информации Файловая структура хранения информации 98
Site Integration Unit (SIU). Quick Start Guide Site Integration Unit (SIU). Quick Start Guide 87