Книга: Федунец Н. И., Черников Ю. Г. «Методы оптимизации»

Изложены основные математические модели, методы и алгоритмы линейного и целочисленного программирования. Представлен раздел специального линейного программирования (транспортные задачи линейного программирования). Рассмотрены математические модели, методы и алгоритмы нелинейного программирования, безусловной минимизации нулевого, первого и второго порядков, а также одномерной оптимизации. Даны примеры решения классических и современных задач вручную и программным способом с использованием различных программ, современных пакетов прикладных программ, Java Applets, математических пакетов. Показано решение задач линейного и нелинейного программирования и безусловной минимизации с использованием языка моделирования AMPL, а также на основе удаленного доступа в сети Интернет.
Н. И. Федунец — д-р техн. наук, проф. кафедры «Автоматизированные системы управления» Московского государственного горного университета; Ю. Г. Черников — канд. техн. наук, проф. кафедры «Автоматизированные системы управления» Московского государственного горного университета.
Для студентов, обучающихся по направлению «Информатика и вычислительная техника» по специальности «Автоматизированные системы обработки информации и управления».

Содержание:

Введение...... 5 Часть 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ...... 9 1. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ...... 11 1. 1. Основные определения и допущения ЛП...... 11 1. 2. Содержательная и математическая постановки задачи оптимального планирования производства продукции. Экономическая интерпретация...... 12 1. 3. Математическая модель общей ЗЛП. Формы постановки ЗЛП...... 14 1. 4. Симплексный метод решения ЗЛП...... 17 1. 5. Математическая модель тестовой задачи линейного программирования...... 26 1. 6. Решение задачи линейного программирования...... 27 1. 7. Решение двухмерных ЗЛП с использованием Java Applet...... 35 1. 8. Решение ЗЛП программным способом с использованием пакета MATLAB...... 41 1. 9. Решение задачи линейного программирования с использованием программы GIPALS...... 46 1. 10. Математическая постановка расширенной ЗЛП. Метод искусственного базиса...... 61 1. 11. Двойственный симплексный метод...... 64 1. 12. Методы внутренней точки...... 64 1. 13. Модели параметрического линейного программирования...... 73 1. 14. Модели дробно-линейного программирования...... 75 1. 15. Классы и примеры задач, решаемые методами ЛП...... 75 1. 16. Связь матричных игр и линейного программирования. Переход от матричных игр к ЗЛП...... 79 2. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ...... 86 2. 1. Содержательная и математическая постановка задачи, двойственной к задаче оптимального планирования производства продукции. Экономическая интерпретация...... 86 2. 2. Математическая постановка общей ДЗЛП. Правила перехода от прямой ЗЛП к двойственной ЗЛП...... 87 2. 3. Составление двойственной модели...... 89 2. 4. Решение двойственной ЗЛП в алгебраическом формате...... 92 3. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ...... 95 3. 1. Содержательная и математическая постановка транспортной ЗЛП. Экономическая интерпретация. Особенности ТЗЛП...... 95 3. 2. Методы решения ТЗЛП...... 99 3. 3. Метод потенциалов...... 100 3. 4. Открытая модель ТЗЛП...... 102 3. 5. Математическая модель двойственной ТЗЛП...... 104 3. 6. Решение тестовой ТЗЛП...... 105 3. 7. Решение ТЗЛП с помощью пакета прикладных программ...... 117 3. 8. Примеры ТЗЛП...... 121 4. ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ...... 124 4. 1. Математическая постановка целочисленной задачи линейного программирования. Геометрическая интерпретация...... 125 4. 2. Методы отсечения...... 128 4. 3. Комбинаторные методы...... 131 4. 3. 1. Метод ветвей и границ...... 132 4. 3. 2. Алгоритм Лэнд и Дойг...... 133 4. 4. Решение ЦЗЛП методом отсечения...... 134 4. 5. Решение ЦЗЛП программным способом...... 139 4. 6. Решение ЦЗЛП с булевыми переменными методом ветвей и границ пакетом Lindo...... 145 4. 7. Решение задачи о выборе инвестиционного проекта...... 146 4. 7. 1. Содержательная постановка ЦЗЛП о выборе инвестиционного проекта...... 146 4. 7. 2. Решение ЦЗЛП программным способом...... 147 4. 8. Решение задачи о назначении (выборе)...... 149 4. 8. 1. Содержательная постановка задачи о назначении (выборе)...... 149 4. 8. 2. Математическая модель задачи о назначении...... 149 4. 8. 3. Формирование файла исходных данных...... 150 4. 9. Содержательная и математическая постановка задачи о коммивояжере...... 151 4. 10. Задача о рюкзаке...... 152 4. 11. Примеры содержательной постановки задач, решаемых методами целочисленного программирования...... 154 Часть 2. МОДЕЛИ И МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (УСЛОВНАЯ ОПТИМИЗАЦИЯ)...... 159 1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ...... 161 1. 1. Математическая модель общей задачи нелинейного программирования...... 161 1. 2. Сравнение ЗНП с ЗЛП...... 162 1. 3. Сепарабельное программирование. Метод кусочно-линейной аппроксимации...... 163 1. 4. Решение задач сепарабельного программирования с использованием пакета прикладных программ...... 166 1. 5. Выпуклые множества и выпуклые функции. Матрица Гессе...... 170 1. 6. Квадратичные функции...... 174 1. 7. Математическая модель общей задачи выпуклого программирования...... 178 1. 8. Теорема Куна — Таккера — основополагающая теорема нелинейного программирования...... 179 1. 9. Математическая модель задачи квадратичного программирования...... 180 1. 10. Методы решения ЗКП...... 181 1. 11. Решение ЗКП численным методом...... 184 1. 11. 1. Математическая модель тестовой задачи квадратичного программирования 1...... 84 1. 11. 2. Решение тестовой задачи...... 184 1. 12. Решение тестовой ЗКП с использованием пакета прикладных программ...... 190 2. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ...... 192 2. 1. Математическая модель задачи определения условного экстремума (с смешанными ограничениями)...... 192 2. 2. Классификация и характеристика методов внешних штрафных функций...... 192 2. 3. Алгоритм метода внешних штрафных функций [7]...... 194 2. 4. Решение тестовой задачи методом внешних штрафных функций [24]...... 194 2. 5. Математическая модель ЗНП, решаемой методом внутренних (барьерных) штрафных функций...... 196 2. 6. Метод внутренних (барьерных) штрафных функций...... 196 2. 7. Алгоритм метода внутренних штрафных функций...... 198 2. 8. Решение тестовой задачи методом внутренних штрафных функций...... 199 2. 9. Математическая модель задачи квадратичного (выпуклого) программирования...... 201 2. 10. Метод Франка — Вулфа...... 202 2. 11. Геометрическое программирование...... 203 Часть 3. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ (ОПТИМИЗАЦИИ) ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ...... 207 1. ОБЩИЕ ПОЛОЖЕНИЯ...... 209 1. 1. Математическая постановка задачи безусловной минимизации (оптимизации)...... 209 1. 2. Основные понятия и определения методов безусловной минимизации. Необходимые и достаточные условия экстремума...... 210 1. 3. Краткая характеристика и классификация методов безусловной минимизации...... 212 2. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ НУЛЕВОГО ПОРЯДКА ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ...... 216 2. 1. Краткая характеристика и классификация методов нулевого порядка...... 216 2. 2. Метод конфигураций (Хука — Дживса)...... 217 2. 2. 1. Алгоритм метода конфигураций...... 218 2. 3. Метод деформируемого многогранника (Нелдера — Мида)...... 220 2. 3. 1. Алгоритм метода деформируемого многогранника...... 222 2. 3. 2. Решение задачи безусловной минимизации методом деформируемого многогранника...... 225 2. 3. 3. Решение задач безусловной минимизации методом деформируемого многогранника с использованием Java Applet...... 227 2. 4. Метод Розенброка...... 232 2. 5. Метод Пауэлла...... 232 2. 6. Метод покоординатного спуска...... 233 3. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ПЕРВОГО ПОРЯДКА...... 237 3. 1. Классификация и характеристика методов первого порядка...... 237 3. 2. Методы градиентного спуска...... 239 3. 3. Градиентные методы...... 244 3. 3. 1. Метод градиентного спуска с постоянным шагом...... 244 3. 3. 2. Метод градиентного спуска с дроблением шага...... 245 3. 3. 3. Метод наискорейшего спуска...... 246 3. 3. 4. Алгоритм метода наискорейшего градиентного спуска...... 248 3. 4. Эффект оврагов...... 250 3. 5. Решение задачи безусловной минимизации методом наискорейшего спуска...... 252 3. 6. Метод покоординатного спуска...... 255 3. 7. Метод сопряженных градиентов...... 256 3. 7. 1. Метод Флетчера — Ривса...... 259 3. 7. 2. Алгоритм метода Флетчера — Ривса...... 260 3. 8. Минимизация неквадратичных функций...... 261 3. 9. Решение задач безусловной минимизации методом сопряженных градиентов с использованием системы MathCAD...... 262 3. 10. Метод Дэвидона — Флетчера — Пауэлла (ДФП)...... 264 3. 10. 1. Алгоритм ДФП...... 266 4. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ВТОРОГО ПОРЯДКА...... 270 4. 1. Метод Ньютона...... 270 4. 2. Алгоритм метода Ньютона...... 276 4. 3. Метод с регулировкой шага (Ньютона — Рафсона)...... 276 4. 4. Модификации метода Ньютона...... 278 4. 5. Решение задачи безусловной минимизации методом Ньютона...... 281 4. 6. Алгоритм метода Ньютона — Рафсона...... 284 4. 7. Решение задач безусловной минимизации квазиньютоновским методом с использованием системы MathCAD...... 285 5. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ...... 289 5. 1. Математическая постановка задачи минимизации функции одной переменной...... 289 5. 2. Краткая характеристика и классификация методов одномерной минимизации (оптимизации)...... 289 5. 3. Метод дихотомического поиска...... 290 5. 3. 1. Алгоритм дихотомического поиска...... 291 5. 4. Метод Фибоначчи...... 292 5. 4. 1. Алгоритм метода Фибоначчи...... 294 5. 4. 2. Решение задачи методом Фибоначчи...... 295 5. 4. 3. Решение одномерной задачи методом Фибоначчи с использованием апплета...... 296 5. 5. Метод золотого сечения...... 301 5. 5. 1. Алгоритм метода золотого сечения...... 301 5. 5. 2. Решение задачи методом золотого сечения...... 302 5. 5. 3. Программное решение задачи методом золотого сечения с использованием MS Excel...... 304 5. 6. Метод равномерного поиска...... 305 Часть 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧ УСЛОВНОЙ И БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ...... 307 1. ПРОГРАММНЫЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ И БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ...... 309 1. 1. Решение задач нелинейного программирования (условная оптимизация)...... 310 1. 1. 1. Решение ЗКП на локальном компьютере с использованием языка моделирования AMPL...... 310 1. 1. 1. 1. Математическая постановка тестовой задачи квадратичного программирования...... 310 1. 1. 1. 2. Составление модели нелинейного программирования с использованием языка моделирования AMPL...... 310 1. 1. 1. 3. Решение задачи программой LOQO...... 311 1. 1. 2. Решение задач нелинейного программирования методом множителей Лагранжа с использованием пакета Maple 8...... 314 1. 2. Решение задач безусловной минимизации (оптимизации)...... 320 1. 2. 1. Решение задач безусловной минимизации с использованием языка моделирования AMPL...... 320 1. 2. 1. 1. Постановка задачи безусловной минимизации...... 320 1. 2. 1. 2. Составление модели задачи минимизации па языке моделирования AMPL...... 321 1. 2. 1. 3. Решение задачи программой LOQO...... 322 1. 2. 2. Решение задач минимизации функции двух переменных с помощью пакета Maple 8...... 324 1. 2. 3. Решение задач безусловной минимизации с использованием удаленного доступа в сети Интернет...... 328 1. 3. Решение задач нелинейного программирования с помощью системы NIMBUS...... 334 1. 3. 1. Краткая характеристика системы NIMBUS...... 334 1. 3. 2. Методика решения задач оптимизации...... 336 1. 4. Решение задач нелинейного программирования с помощью программы HIRON...... 348 1. 4. 1. Краткая характеристика программы HIRON...... 348 1. 4. 2. Решение задач безусловной минимизации с помощью программы HIRON...... 350 Список литературы...... 362

Издательство: "Горная книга" (2009)

ISBN: 9785741805572