Множества Скачать
презентацию
<<  Дискретная математика Элементы множества  >>
Алгоритмы внутренних точек с приближенным решением вспомогательной
Алгоритмы внутренних точек с приближенным решением вспомогательной
Исторический экскурс
Исторический экскурс
Пара взаимно-двойственных задач линейного программирования
Пара взаимно-двойственных задач линейного программирования
Аффинно-масштабирующие алгоритмы внутренних точек
Аффинно-масштабирующие алгоритмы внутренних точек
Алгоритмы центрального пути (имеют полиномиальные оценки)
Алгоритмы центрального пути (имеют полиномиальные оценки)
Решение вспомогательной задачи
Решение вспомогательной задачи
Методы решения вспомогательной задачи
Методы решения вспомогательной задачи
Метод сопряженных направлений
Метод сопряженных направлений
Экспериментальное исследование
Экспериментальное исследование
Параметры управления алгоритмом
Параметры управления алгоритмом
Спасибо за внимание
Спасибо за внимание
Слайды из презентации «Решение алгоритмов» к уроку математики на тему «Множества»

Автор: Alexander. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Алгоритм.ppt» бесплатно в zip-архиве размером 43 КБ.

Скачать презентацию

Решение алгоритмов

содержание презентации «Алгоритм.ppt»
СлайдТекст
1 Алгоритмы внутренних точек с приближенным решением вспомогательной

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

задачи.

Филатов А.Ю. к.ф.-м.н., ИСЭМ СО РАН, ИГУ (Иркутск) Пержабинский С.М. ИСЭМ СО РАН (Иркутск)

http://polnolunie.baikal.ru/me/mat_prog.htm, http://matec.isu.ru

Работа выполнена при финансовой поддержке РФФИ (проект 05-01-00587а)

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

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

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)

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

4 Аффинно-масштабирующие алгоритмы внутренних точек

Аффинно-масштабирующие алгоритмы внутренних точек

Стартовое приближение:

Итеративный переход:

Задача поиска направления корректировки:

Шаг корректировки:

Способы выбора весовых коэффициентов:

(3)

(4)

(5)

(6)

(7)

5 Алгоритмы центрального пути (имеют полиномиальные оценки)

Алгоритмы центрального пути (имеют полиномиальные оценки)

Комбинированные алгоритмы (используют параметризацию)

Логарифмическая барьерная функция:

Задача поиска направления корректировки:

Задача поиска направления корректировки:

(8)

(9)

(10)

6 Решение вспомогательной задачи

Решение вспомогательной задачи

Аффинно-масштабирующие алгоритмы:

Алгоритмы центрального пути:

Комбинированные алгоритмы:

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

7 Методы решения вспомогательной задачи

Методы решения вспомогательной задачи

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

Метод Гаусса. Метод Халецкого (метод квадратного корня). Метод сопряженных направлений. Метод Зейделя. Другие приближенные итеративные методы.

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

8 Метод сопряженных направлений

Метод сопряженных направлений

Итеративный переход:

Направление корректировки:

Шаг, определяющий вариант метода:

Шаг корректировки:

9 Экспериментальное исследование

Экспериментальное исследование

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

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

10 Параметры управления алгоритмом

Параметры управления алгоритмом

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

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

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

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

«Решение алгоритмов»
http://900igr.net/prezentatsii/matematika/Algoritm/Reshenie-algoritmov.html
cсылка на страницу
Урок

Математика

67 тем
Слайды
Презентация: Решение алгоритмов | Файл: Алгоритм.ppt | Тема: Множества | Урок: Математика | Вид: Слайды