Декомпозиция в оптимизации систем (курс лекций, В.И.Цурков)
Материал из MachineLearning.
(Различия между версиями)
(Новая: В курсе рассматриваются основные подходы в декомпозиции оптимизационных задач большой размерности, ...) |
м (→Замечания для студентов) |
||
Строка 9: | Строка 9: | ||
* О найденных ошибках и опечатках [[Служебная:EmailUser/Algneushev|сообщайте мне]]. — ''[[Участник:Algneushev|А.Н.Гнеушев]] {{дата}}'' | * О найденных ошибках и опечатках [[Служебная:EmailUser/Algneushev|сообщайте мне]]. — ''[[Участник:Algneushev|А.Н.Гнеушев]] {{дата}}'' | ||
* Короткая ссылка на эту страницу: [http://bit.ly/ML_ISD_OptBigSys http://bit.ly/ML_ISD_OptBigSys]. | * Короткая ссылка на эту страницу: [http://bit.ly/ML_ISD_OptBigSys http://bit.ly/ML_ISD_OptBigSys]. | ||
- | + | * Cсылка на курс [https://lms.mipt.ru/course/view.php?id=2687 Декомпозиция в оптимизации систем (9 семестр)] на сайте МФТИ. | |
+ | * Cсылка на курс [https://lms.mipt.ru/course/edit.php?id=2686 Декомпозиция в оптимизации систем (10 семестр)] на сайте МФТИ. | ||
+ | * Cсылка на курс [https://lms.mipt.ru/course/view.php?id=1722 Декомпозиция в оптимизации систем (11 семестр)] на сайте МФТИ. | ||
__TOC__ | __TOC__ |
Версия 21:06, 18 апреля 2020
В курсе рассматриваются основные подходы в декомпозиции оптимизационных задач большой размерности, принципы Данцига-Вулфа и Корнаи-Липтака в оптимизации больших систем, понятие агрегированных переменных как основной подход к понижению размерности.
Курс читается студентам 5 курса кафедры «Интеллектуальные системы / проектирование и организация систем» ФУПМ МФТИ. Программа лекционного курса рассчитана на 33 часа (два семестра), предусмотрены практические (семинарские) занятия (28 часов).
Замечания для студентов
- На подстранице имеется перечень вопросов к устному экзамену.
- О найденных ошибках и опечатках сообщайте мне. — А.Н.Гнеушев 12 сентября 2024
- Короткая ссылка на эту страницу: http://bit.ly/ML_ISD_OptBigSys.
- Cсылка на курс Декомпозиция в оптимизации систем (9 семестр) на сайте МФТИ.
- Cсылка на курс Декомпозиция в оптимизации систем (10 семестр) на сайте МФТИ.
- Cсылка на курс Декомпозиция в оптимизации систем (11 семестр) на сайте МФТИ.
Программа курса
Общая постановка задачи оптимизации
- Линейное программирование. Базисные решения.
- Симплекс-метод. Вырождение и критерий окончания итераций.
- Транспортная задача.
- Элементы теории двойственности.
Простейшее описание иерархических систем. Модели двухуровневого отраслевого планирования.
- Рассмотрение модулей отраслевого управления.
- Локальные ограничения. Связывающие ограничения. Лестничная структура связей.
- Нелинейные системы.
- Блочно-сепарабельные задачи.
- Перекрёстные связи.
Горизонтальное разбиение матрицы в линейном программировании. Понятие координирующей задачи и независимых локальных задач.
- Горизонтальное разбиение матрицы условий.
- Применения двойственного алгоритма метода улучшения плана.
- Формирование координирующей задачи. Построение локальных задач. Условие окончания итераций.
- Применение в блочном программировании. Оценки выигрыша по памяти ЭВМ.
- Построение различных схем координации.
Вертикальное разбиение матрицы. Принцип распределения ресурсов. Конкретные модели. Различные методы решения координирующей задачи.
- Вертикальное разложение матрицы условий.
- Проблема распределения ресурсов.
- Различные методы координации.
- Нелинейное разложение по ресурсам. Конкретные эвристические модели разложения по ресурсам.
Релаксация ограничений. Метод Бендерса в частично-целочисленном программировании. Элементы блочного целочисленного программирования.
- Выделение параметров системы, по которым ведётся координация.
- Методы релаксации, применение к нелинейным задачам. Смешанное программирование.
- Метод Бендерса. Двойственность к методу Данцига-Вулфа.
Выявление параметров, которые определяют двухуровневые схемы. Метод Корнаи-Липтака как частный случай параметрической декомпозиции.
- Декомпозиция на основе введения специальных переменных.
- Построение формальной схемы. применения к случаям матриц с квазиблочной структурой.
Агрегирование в леонтьевских системах межотраслевого баланса. Агрегирование переменных блоком. Системы с малым параметром.
- Агрегирование в линейных уравнениях типа отраслевого баланса. Построение взвешенных сумм.
- Агрегирование компонент из единых блоков. Понятие присоединённой задачи.
- Дезагрегированные решения.
- Агрегирование в задачах со слабыми связями.
Специальная модель оптимизации отраслевой системы. Веса агрегирования. Координатор - как задача в агрегированных переменных.
- Анализ двухуровневой системы отраслевого планирования.
- Агрегированная задача как координатор. Решение её двойственной.
- Формирование локальных задач.
- Монотонность по функционалу итеративного процесса. Анализ вырождения.
Настройка симплекс-метода на декомпозицию с учётом специфики исходной задачи.
- Запись задачи линейного программирования в виде сумм подматриц. Построение вычислительного процесса.
- Сведение к независимым блокам.
Расщепление задач оптимизации при использовании градиентных методов.
- Построение вычислительных процедур. Расщепление на независимы задачи при использовании градиентных методов.
- Использование покомпонентного спуска.
Метод дробных шагов как процедура декомпозиции
- Метод дробных шагов в разностных схемах.
- Расщепление разностных формул. Применение к конкретным задачам математической физики.
Семинары
- Линейное программирование. Симплекс-метод. Транспортная задача. Элементы теории двойственности.
- Простейшее описание иерархических систем. Модели двухуровневого отраслевого планирования.
- Горизонтальное разбиение матрицы в линейном программировании. Понятие координирующей задачи и независимых локальных задач.
- Вертикальное разбиение матрицы. Принцип распределения ресурсов. Конкретные модели. Различные методы решения координирующей задачи.
- Релаксация ограничений. Метод Бендерса в частично-целочисленном программировании. Элементы блочного целочисленного программирования.
- Выявление параметров, которые определяют двухуровневые схемы. Метод Корнаи-Липтака как частный случай параметрической декомпозиции.
- Агрегирование в леонтьевских системах межотраслевого баланса. Агрегирование переменных блоком. Системы с малым параметром.
- Специальная модель оптимизации отраслевой системы. Веса агрегирования. Координатор - как задача в агрегированных переменных.
- Настройка симплекс-метода на декомпозицию с учётом специфики исходной задачи.
- Расщепление задач оптимизации при использовании градиентных методов.
- Метод дробных шагов как процедура декомпозиции
Литература
Основная литература
- Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях М.: Либроком, 2009 - 288 стр.
- Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учебное пособие для вузов М.:Дрофа, 2006 - 208 стр.
- Васин А.А., Краснощеков П.С., Морозов В.В. Исследование операций М.: Академия, 2008 - 464 стр.
- Ширяев В.И. Исследование операций и численные методы оптимизации М.: КомКнига, 2007 - 216 стр.
- Протасов И.Д. Теория игр и исследование операций М.: Гелиос АРВ, 2006 - 368 стр.
- Васильев Ф.П., Иваницкий А.Ю. Линейное программирование М.: Факториал Пресс, 2003 - 352 стр.
- Ковалев М.М. Дискретная оптимизация (целочисленное программирование). 2 изд. М.: Едиториал УРСС, 2003 - 192 стр.
Дополнительная литература
- Лэсдон Л.С. Оптимизация больших систем. - М.: Наука, 1975.
- Цурков В.И. Декомпозиция в задачах большой размерности. - М.: Наука, 1981.
- Первозванский А.А., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. - М.: Наука, 1975.
- Танаев В.С. Декомпозиция и агрегирование в задачах математического программирования. - Минск
Программу составил
В.И.Цурков, профессор, д.ф.–м.н.
См. также
- Кафедра «Интеллектуальные системы» ФУПМ МФТИ
- Специализация «Проектирование и организация систем» кафедры «Интеллектуальные системы» ФУПМ МФТИ
- Расписание специализации «Проектирование и организация систем»
Список подстраниц
Декомпозиция в оптимизации систем (курс лекций, В.И.Цурков)/Вопросы |