Методы оптимизации

Изложены основные математические модели, методы и алгоритмы линейного и целочисленного программирования. Представлен раздел специального линейного программирования (транспортные задачи линейного программирования). Рассмотрены математические модели, методы и алгоритмы нелинейного программирования, безусловной минимизации нулевого, первого и второго порядков, а также одномерной оптимизации. Даны примеры решения классических и современных задач вручную и программным способом с использованием различных программ, современных пакетов прикладных программ, Java Applets, математических пакетов. Показано решение задач линейного и нелинейного программирования и безусловной минимизации с использованием языка моделирования АМРL а также на основе удаленного доступа в сети Интернет.

Н.И. Федунец — д-р техн. наук, проф. кафедры «Автоматизированные системы управления» Московского государственного горного университета;

Ю.Г. Черников — канд. техн. наук, проф. кафедры «Автоматизированные системы управления» Московского государственного горного университета.

Для студентов, обучающихся по направлению «Информатика и вычислительная техника» по специальности «Автоматизированные системы обработки информации и управления».

1.1. Основные определения и допущения ЛП

1.2.Содержательная и математическая постановки задачи оптимального планирования производства продукции. Экономическая интерпретация

1.3. Математическая модель общей ЗЛП. Формы постановки ЗЛП

1.4. Симплексный метод решения ЗЛП

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

1.6. Решение задачи линейного программирования

1.7. Решение двухмерных ЗЛП с использованием Java Applet

1.8. Решение ЗЛП программным способом с использованием пакета МАТLАВ

1.9. Решение задачи линейного программирования с использованием программы GIPALS

1.10. Математическая постановка расширенной ЗЛП. Метод искусственного базиса

1.11. Двойственный симплексный метод

1.12. Методы внутренней точки

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

1.14. Модели дробно-линейного программирования 

1.15. Классы и примеры задач, решаемые методами ЛП

1.16. Связь матричных игр и линейного программирования. Переход от матричных игр к ЗЛП

2.1. Содержательная и математическая постановка задачи, двойственной к задаче оптимального планирования производства продукции. Экономическая интерпретация

2.2. Математическая постановка общей ДЗЛП. Правила перехода от прямой ЗЛП к двойственной ЗЛП

2.3. Составление двойственной модели

2.4. Решение двойственной ЗЛП в алгебраическом формате

3.1. Содержательная и математическая постановка транспортной ЗЛП. Экономическая интерпретация. Особенности ТЗЛП

3.2. Методы решения ТЗЛП

3.3. Метод потенциалов.

3.4. Открытая модель ТЗЛП

3.5. Математическая модель двойственной ТЗЛП

3.6. Решение тестовой ТЗЛП

3.7. Решение ТЗЛП с помощью пакета прикладных программ

3.8. Примеры ТЗЛП

4.1. Математическая постановка целочисленной задачи линейного программирования. Геометрическая интерпретация

4.2. Методы отсечения

4.3. Комбинаторные методы

4.3.1. Метод ветвей и границ

4.3.2. Алгоритм Лэнд и Дойг

4.4. Решение ЦЗЛП методом отсечения

4.5. Решение ЦЗЛП программным способом

4.6. Решение ЦЗЛП с булевыми переменными методом ветвей и границ пакетом Lindo

4.7. Решение задачи о выборе инвестиционного проекта

4.7.1. Содержательная постановка ЦЗЛП о выборе инвестиционного проекта

4.7.2. Решение ЦЗЛП программным способом

4.8. Решение задачи о назначении (выборе)

4.8.1. Содержательная постановка задачи о назначении (выборе)

4.8.2. Математическая модель задачи о назначении

4.8.3. Формирование файла исходных данных

4.9. Содержательная и математическая постановка задачи о коммивояжере

4.10. Задача о рюкзаке

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

1.1. Математическая модель общей задачи нелинейного программирования

1.2. Сравнение ЗНП с ЗЛП

1.3. Сепарабельное программирование. Метод кусочно-линейной аппроксимации

1.4. Решение задач сепарабельного программирования с использованием пакета прикладных программ

1.5. Выпуклые множества и выпуклые функции. Матрица Гессе

1.6. Квадратичные функции

1.7. Математическая модель общей задачи выпуклого программирования

1.8. Теорема Куна — Таккера — основополагающая теорема нелинейного программирования

1.9. Математическая модель задачи квадратичного программирования

1.10. Методы решения ЗКП

1.11. Решение ЗКП численным методом

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

1.11.2. Решение тестовой задачи

1.12. Решение тестовой ЗКП с использованием пакета прикладных программ

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

2.2. Классификация и характеристика методов внешних штрафных функций

2.3. Алгоритм метода внешних штрафных функций  

2.4. Решение тестовой задачи методом внешних штрафных функций 

2.5. Математическая модель ЗНП, решаемой методом внутренних (барьерных) штрафных функций

2.6. Метод внутренних (барьерных) штрафных функций

2.7. Алгоритм метода внутренних штрафных функций

2.8. Решение тестовой задачи методом внутренних штрафных функций

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

2.10. Метод Франка — Вулфа

2.11. Геометрическое программирование

1.1. Математическая постановка задачи безусловной минимизации (оптимизации)

1.2. Основные понятия и определения методов безусловной минимизации. Необходимые и достаточные условия экстремума

1.3. Краткая характеристика и классификация методов безусловной минимизации

2.1. Краткая характеристика и классификация методов нулевого порядка 

2.2. Метод конфигураций (Хука — Дживса)

2.2.1. Алгоритм метода конфигураций

2.3. Метод деформируемого многогранника (Нелдера — Мида)

2.3.1. Алгоритм метода деформируемого многогранника

2.3.2. Решение задачи безусловной минимизации методом деформируемого многогранника

2.3.3. Решение задач безусловной минимизации методом деформируемого многогранника с использованием Java Applet

2.4. Метод Розенброка

2.5. Метод Пауэлла

2.6. Метод покоординатного спуска

3.1. Классификация и характеристика методов первого порядка

3.2. Методы градиентного спуска

3.3. Градиентные методы

3.3.1. Метод градиентного спуска с постоянным шагом

3.3.2. Метод градиентного спуска с дроблением шага

3.3.3. Метод наискорейшего спуска

3.3.4. Алгоритм метода наискорейшего градиентного спуска

3.4. Эффект оврагов

3.5. Решение задачи безусловной минимизации методом наискорейшего спуска

3.6. Метод покоординатного спуска

3.7. Метод сопряженных градиентов

3.7.1. Метод Флетчера — Ривса

3.7.2. Алгоритм метода Флетчера — Ривса

3.8. Минимизация не квадратичных функций

3.9. Решение задач безусловной минимизации методом сопряженных градиентов с использованием системы МаthCAD

3.10. Метод Дэвидона — Флетчера — Пауэлла (ДФП)

3.10.1. Алгоритм ДФП

4.1. Метод Ньютона

4.2. Алгоритм метода Ньютона

4.3. Метод с регулировкой шага (Ньютона — Рафсона)

4.4. Модификации метода Ньютона

4.5. Решение задачи безусловной минимизации методом Ньютона

4.6. Алгоритм метода Ньютона — Рафсона

4.7. Решение задач безусловной минимизации квазиньютоновским методом с использованием системы МаthCAD

5.1. Математическая постановка задачи минимизации функции одной переменной

5.2. Краткая характеристика и классификация методов одномерной минимизации (оптимизации)

5.3. Метод дихотомического поиска

5.3.1. Алгоритм дихотомического поиска

5.4. Метод Фибоначчи

5.4.1. Алгоритм метода Фибоначчи

5.4.2. Решение задачи методом Фибоначчи

5.4.3. Решение одномерной задачи методом Фибоначчи с использованием апплета

5.5. Метод золотого сечения

5.5.1. Алгоритм метода золотого сечения

5.5.2. Решение задачи методом золотого сечения

5.5.3. Программное решение задачи методом золотого сечения с использованием  МS Ехсеl

5.6. Метод равномерного поиска

1.1. Решение задач нелинейного программирования (условная оптимизация)

1.1.1. Решение ЗКП на локальном компьютере с использованием языка моделирования АМРL

1.1.1.1. Математическая постановка тестовой задачи квадратичного программирования

1.1.1.2. Составление модели нелинейного программирования с использованием языка моделирования АМРL

1.1.1.3. Решение задачи программой LOQO

1.1.2. Решение задач нелинейного программирования методом множителей Лагранжа с использованием пакета Марlе 8

1.2. Решение задач безусловной минимизации (оптимизации)

1.2.1. Решение задач безусловной минимизации с использованием языка моделирования АМРL

1.2.1.1. Постановка задачи безусловной минимизации

1.2.1.2. Составление модели задачи минимизации на языке моделирования АМРL

1.2.1.3. Решение задачи программой LOQO

1.2.2. Решение задач минимизации функции двух переменных с помощью пакета Марle 8

1.2.3. Решение задач безусловной минимизации с использованием удаленного доступа в сети Интернет

1.3. Решение задач нелинейного программирования с помощью системы NIMBUS

1.3.1. Краткая характеристика системы NIMBUS

1.3.2. Методика решения задач оптимизации

1.4. Решение задач нелинейного программирования с помощью программы HIRON

1.4.1. Краткая характеристика программы HIRON

1.4.2. Решение задач безусловной минимизации с помощью программы HIRON