Материал из MachineLearning.

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

Курс читается студентам 5 курса кафедры «Интеллектуальные системы / проектирование и организация систем» ФУПМ МФТИ. Программа лекционного курса рассчитана на 33 часа (два семестра), предусмотрены практические (семинарские) занятия (28 часов).

Замечания для студентов

• На подстранице имеется перечень вопросов к устному экзамену.
• О найденных ошибках и опечатках сообщайте мне. — А.Н.Гнеушев 24 ноября 2024
• Короткая ссылка на эту страницу: http://bit.ly/ML_ISD_OptBigSys.
• Cсылка на курс Декомпозиция в оптимизации систем (9 семестр) на сайте МФТИ.
• Cсылка на курс Декомпозиция в оптимизации систем (10 семестр) на сайте МФТИ.
• Cсылка на курс Декомпозиция в оптимизации систем (11 семестр) на сайте МФТИ.

Содержание 1 Замечания для студентов 2 Программа курса 2.1 Общая постановка задачи оптимизации 2.2 Простейшее описание иерархических систем. Модели двухуровневого отраслевого планирования. 2.3 Горизонтальное разбиение матрицы в линейном программировании. Понятие координирующей задачи и независимых локальных задач. 2.4 Вертикальное разбиение матрицы. Принцип распределения ресурсов. Конкретные модели. Различные методы решения координирующей задачи. 2.5 Релаксация ограничений. Метод Бендерса в частично-целочисленном программировании. Элементы блочного целочисленного программирования. 2.6 Выявление параметров, которые определяют двухуровневые схемы. Метод Корнаи-Липтака как частный случай параметрической декомпозиции. 2.7 Агрегирование в леонтьевских системах межотраслевого баланса. Агрегирование переменных блоком. Системы с малым параметром. 2.8 Специальная модель оптимизации отраслевой системы. Веса агрегирования. Координатор - как задача в агрегированных переменных. 2.9 Настройка симплекс-метода на декомпозицию с учётом специфики исходной задачи. 2.10 Расщепление задач оптимизации при использовании градиентных методов. 2.11 Метод дробных шагов как процедура декомпозиции 3 Семинары 4 Литература 4.1 Основная литература 4.2 Дополнительная литература 5 См. также 6 Список подстраниц

Программа курса

Общая постановка задачи оптимизации

• Линейное программирование. Базисные решения.
• Симплекс-метод. Вырождение и критерий окончания итераций.
• Транспортная задача.
• Элементы теории двойственности.

Простейшее описание иерархических систем. Модели двухуровневого отраслевого планирования.

• Рассмотрение модулей отраслевого управления.
• Локальные ограничения. Связывающие ограничения. Лестничная структура связей.
• Нелинейные системы.
• Блочно-сепарабельные задачи.
• Перекрёстные связи.

Горизонтальное разбиение матрицы в линейном программировании. Понятие координирующей задачи и независимых локальных задач.

• Горизонтальное разбиение матрицы условий.
• Применения двойственного алгоритма метода улучшения плана.
• Формирование координирующей задачи. Построение локальных задач. Условие окончания итераций.
• Применение в блочном программировании. Оценки выигрыша по памяти ЭВМ.
• Построение различных схем координации.

Вертикальное разбиение матрицы. Принцип распределения ресурсов. Конкретные модели. Различные методы решения координирующей задачи.

• Вертикальное разложение матрицы условий.
• Проблема распределения ресурсов.
• Различные методы координации.
• Нелинейное разложение по ресурсам. Конкретные эвристические модели разложения по ресурсам.

Релаксация ограничений. Метод Бендерса в частично-целочисленном программировании. Элементы блочного целочисленного программирования.

• Выделение параметров системы, по которым ведётся координация.
• Методы релаксации, применение к нелинейным задачам. Смешанное программирование.
• Метод Бендерса. Двойственность к методу Данцига-Вулфа.

Выявление параметров, которые определяют двухуровневые схемы. Метод Корнаи-Липтака как частный случай параметрической декомпозиции.

• Декомпозиция на основе введения специальных переменных.
• Построение формальной схемы. применения к случаям матриц с квазиблочной структурой.

Агрегирование в леонтьевских системах межотраслевого баланса. Агрегирование переменных блоком. Системы с малым параметром.

• Агрегирование в линейных уравнениях типа отраслевого баланса. Построение взвешенных сумм.
• Агрегирование компонент из единых блоков. Понятие присоединённой задачи.
• Дезагрегированные решения.
• Агрегирование в задачах со слабыми связями.

Специальная модель оптимизации отраслевой системы. Веса агрегирования. Координатор - как задача в агрегированных переменных.

• Анализ двухуровневой системы отраслевого планирования.
• Агрегированная задача как координатор. Решение её двойственной.
• Формирование локальных задач.
• Монотонность по функционалу итеративного процесса. Анализ вырождения.

Настройка симплекс-метода на декомпозицию с учётом специфики исходной задачи.

• Запись задачи линейного программирования в виде сумм подматриц. Построение вычислительного процесса.
• Сведение к независимым блокам.

Расщепление задач оптимизации при использовании градиентных методов.

• Построение вычислительных процедур. Расщепление на независимы задачи при использовании градиентных методов.
• Использование покомпонентного спуска.

Метод дробных шагов как процедура декомпозиции

• Метод дробных шагов в разностных схемах.
• Расщепление разностных формул. Применение к конкретным задачам математической физики.

Семинары

1. Линейное программирование. Симплекс-метод. Транспортная задача. Элементы теории двойственности.
2. Простейшее описание иерархических систем. Модели двухуровневого отраслевого планирования.
3. Горизонтальное разбиение матрицы в линейном программировании. Понятие координирующей задачи и независимых локальных задач.
4. Вертикальное разбиение матрицы. Принцип распределения ресурсов. Конкретные модели. Различные методы решения координирующей задачи.
5. Релаксация ограничений. Метод Бендерса в частично-целочисленном программировании. Элементы блочного целочисленного программирования.
6. Выявление параметров, которые определяют двухуровневые схемы. Метод Корнаи-Липтака как частный случай параметрической декомпозиции.
7. Агрегирование в леонтьевских системах межотраслевого баланса. Агрегирование переменных блоком. Системы с малым параметром.
8. Специальная модель оптимизации отраслевой системы. Веса агрегирования. Координатор - как задача в агрегированных переменных.
9. Настройка симплекс-метода на декомпозицию с учётом специфики исходной задачи.
10. Расщепление задач оптимизации при использовании градиентных методов.
11. Метод дробных шагов как процедура декомпозиции

Литература

Основная литература

1. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях М.: Либроком, 2009 - 288 стр.
2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учебное пособие для вузов М.:Дрофа, 2006 - 208 стр.
3. Васин А.А., Краснощеков П.С., Морозов В.В. Исследование операций М.: Академия, 2008 - 464 стр.
4. Ширяев В.И. Исследование операций и численные методы оптимизации М.: КомКнига, 2007 - 216 стр.
5. Протасов И.Д. Теория игр и исследование операций М.: Гелиос АРВ, 2006 - 368 стр.
6. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование М.: Факториал Пресс, 2003 - 352 стр.
7. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). 2 изд. М.: Едиториал УРСС, 2003 - 192 стр.

Дополнительная литература

1. Лэсдон Л.С. Оптимизация больших систем. - М.: Наука, 1975.
2. Цурков В.И. Декомпозиция в задачах большой размерности. - М.: Наука, 1981.
3. Первозванский А.А., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. - М.: Наука, 1975.
4. Танаев В.С. Декомпозиция и агрегирование в задачах математического программирования. - Минск

Программу составил
В.И.Цурков, профессор, д.ф.–м.н.

См. также

• Кафедра «Интеллектуальные системы» ФУПМ МФТИ
• Специализация «Проектирование и организация систем» кафедры «Интеллектуальные системы» ФУПМ МФТИ
• Расписание специализации «Проектирование и организация систем»

Список подстраниц

Декомпозиция в оптимизации систем (курс лекций, В.И.Цурков)/Вопросы