Что такое 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
  • Количество просмотров: 109
  • Количество скачиваний: 0
- Предыдущая Квадратичная функция
Следующая - ГБПОУ НО Нижегородский медицинский колледжПрезентация по информатикеТема: Алгоритмы

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

Повторение темы _Основы логики Повторение темы _Основы логики 205
Текстовой редактор 6 класс Текстовой редактор 6 класс 189
Презентация по информатике на тему мултимедийне технология Презентация по информатике на тему мултимедийне технология 129
Элементы теоретического программирования Элементы теоретического программирования 153
Процессор, системная плата Процессор, системная плата 127
Интернешка Интернешка 162
История развития вычислительной техники История развития вычислительной техники 140
Создание компьютерных тестов Создание компьютерных тестов 154
Printer and scanner Printer and scanner 110
makros 1 makros 1 133
Особенности Общения в сети Интернет Особенности Общения в сети Интернет 124
Введение в предмет информатики Введение в предмет информатики 141
Презентация по информатике на тему Устройство компьютера Презентация по информатике на тему Устройство компьютера 184
Внедрение ИКТ в образовательный процесс Внедрение ИКТ в образовательный процесс 132
Информационное обеспечение АСУП Информационное обеспечение АСУП 149
Презентация по информатике на тему Построение графиков и диаграмм в электронных таблицах Презентация по информатике на тему Построение графиков и диаграмм в электронных таблицах 139
Исследовательская работа по информатике на темуКомпьютерная зависимость студентов ХМ ТПК Исследовательская работа по информатике на темуКомпьютерная зависимость студентов ХМ ТПК 231
Компьютерные презентации 2 Компьютерные презентации 2 117
Алгоритмы. Прошлое, настоящее, будущее Алгоритмы. Прошлое, настоящее, будущее 145
Внешний носитель памяти Внешний носитель памяти 131
Логические законы Логические законы 120
Дискретное (цифровое) представление текстовой, графической, звуковой информации и видеоинформации Дискретное (цифровое) представление текстовой, графической, звуковой информации и видеоинформации 206
Графика в Паскале Графика в Паскале 197
Обобщение опыта работы по теме: Отбор эффективных методов и приемов для реализации интегративного характера курса информатики Обобщение опыта работы по теме: Отбор эффективных методов и приемов для реализации интегративного характера курса информатики 139
ICT for 10 grade ICT for 10 grade 157
Презентация по информатике на тему Программирование Презентация по информатике на тему Программирование 146
Компьютерные вирусы. Антивирусные программы Компьютерные вирусы. Антивирусные программы 136
Защита информации,антивирусная защита Защита информации,антивирусная защита 147
Логические функции Логические функции 142
HTML. Оформление списков HTML. Оформление списков 149