Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ.— М.: Мир, 1986.—000 с., ил. Монография известных американских специалистов посвящена прикладным аспектам теории математического программирования. Рассматриваются методы линейного, целочисленного и нелинейного программирования, используемые для решения задач оптимизации технических систем, а также вопросы реализации соответствующих алгоритмов с помощью ЭВМ. Изложение иллюстрируется многочисленными примерами решения конкретных инженерных задач оптимизации. В русском переводе выходит в двух книгах. Для инженеров-конструкторов, специалистов в области проектирования технических систем и устройств, а также преподавателей, аспирантов и студентов технических вузов. Предисловие к русскому изданию
Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности. Особенно значительные успехи достигнуты при проектировании и анализе больших технических систем. Ускоренные темпы внедрения теоретических разработок в инженерную практику в существенной степени обусловлены широким распространением и интенсивным совершенствованием средств вычислительной техники.
В настоящее время для инженера знание методов оптимизации является столь же необходимым, как знание основ математического анализа, физики, химии, теории сопротивления материалов, радиоэлектроники и ряда других дисциплин, ставших традиционными. Однако большинство публикаций, посвященных теоретическим и прикладным аспектам математического программирования, как правило, охватывают узкий круг вопросов и требуют от читателя фундаментальной математической подготовки.
Издание на русском языке книги Г. Реклейтиса, А. Рейвиндрана и К. Рэгсдела окажет несомненную помощь инженерам при изучении методов оптимизации и их практическом использовании. В монографии последовательно излагаются методологические и вычислительные основы построения нелинейных оптимизационных моделей технических систем. Авторам удалось четко систематизировать разнообразные приемы и методы, используемые для решения задач нелинейного программирования, раскрыть их специфические особенности, сопоставить достоинства и недостатки. Отличительной чертой книги является ее практическая направленность. С большим педагогическим мастерством описаны обязательные этапы оптимизационного исследования, которые, как правило, не рассматриваются в обычных курсах нелинейного программирования: определение границ моделируемой технической системы, выбор приемлемого уровня моделирования, построение целевой функции и модели в целом, интерпретация оптимального решения и др. Значительный интерес представляет сравнительный обзор алгоритмов условной оптимизации в соответствии с критериями вычислительной эффективности и робастности [гл. 12].
Следует отметить, что многочисленные рекомендации по изучению дополнительной литературы содержат в основном ссылки на работы зарубежных авторов. Однако советские математики внесли
существенный вклад в развитие теории нелинейного программирования. Из недавно вышедших в свет книг читателю можно рекомендовать следующие работы: Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации.— М.: Наука, 1979; Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. Математическое программирование.— М.: Высшая школа, 1980; Поляк Б.Т. Введение в оптимизацию.— М.: Наука, 1983.
Книга может быть использована как учебное пособие и практическое руководство по применению методов оптимизации. Она будет доступна и полезна широкому кругу читателей: инженерам, экономистам, специалистам по математическому обеспечению ЭВМ, преподавателям, аспирантам и студентам высших технических учебных заведений.
Канд. техн. наук В, Я- Алтаев, В. И. Моторин
Предисловие
Эта книга посвящена вопросам практического применения методов оптимизации. Основное внимание уделяется методам и алгоритмам, используемым в инженерных приложениях при проектировании, эксплуатации и анализе функционирования технических объектов. Главным образом рассматриваются методы оптимизации, ориентированные на решение задач с непрерывными переменными, ограничениями, содержащими действительные функции, и единственной действительной целевой функцией, т. е. математические методы, часто объединяемые в рамках теории нелинейного программирования. При этом дается обзор всех наиболее важных типов методоз оптимизации, начиная от методов минимизации функции однол переменной и кончая методами, применяемыми для решения нелинейных задач условной оптимизации большой размерности. Рассматриваются не только классические методы, значение которых определяется причинами исторического характера и ролью в дальнейшем развитии оптимизации, но также и перспективные новые методы, примером которых может служить метод решения последовательности задач квадратичного программирования.
Авторы стремились к тому, чтобы читатель получил ясное представление о логической структуре излагаемых методов и о важнейших предположениях, на основе которых они разработаны, а также об их сравнительных преимуществах и недостатках. Доказательства и математические выкладки приводятся только в тех случаях, когда они служат для пояснения основных шагов или свойств рассматриваемых алгоритмов. Как правило, при отсутствии доказательства дается ссылка на соответствующий источник, а объем книги используется для обоснования и разъяснения ключевых аспектов построения различных математических схем. Таким образом, наша главная цель заключается в том, чтобы информировать инженера о прикладных возможностях методов оптимизации, а не в том, чтобы подготовить специалиста по математическому обеспечению ЭВМ. Поэтому значительное внимание уделено таким практически важным вопросам, как построение модели, ее реализация, подготовка к решению, выбор первого приближения к экстремальной точке, выбор стратегии оптимизации и т. д. Одна из основных глав (гл. 13) посвящена методике проведения оптимизационных исследований, в другой главе (гл. 12) приведены результаты сравнительного анализа из-
вестных программ решения оптимизационных задач на ЭВМ; в гл. 14 на трех конкретных примерах описан опыт практического применения методов оптимизации в технике. Значительная часть каждой главы отведена примерам использования этих методов авторами в области химической технологии, организации производства и машиностроения. Несмотря на то что имеется ряд полезных книг, содержащих подробное изложение теоретических и вычислительных аспектов нелинейного программирования, данная монография является, по-видимому, единственной в своем роде работой, которую отличают отмеченные выше особенности: достаточно полный обзор современных методов нелинейного программирования, неформальный подход к изложению материала и ориентация на изучение прикладных возможностей методов оптимизации в технике.
Работа над книгой продолжалась в течение восьми лет. За это время материал книги использовался при чтении курса лекций по оптимизации в технике для студентов последнего и аспирантов первого годов обучения в Университете Пурдью. Этот курс читался в течение одного семестра; для большей части слушателей он оказался первым последовательным изложением методов оптимизации. Математическая подготовка студентов основывалась на университетских курсах математического анализа и линейной алгебры. Таким образом, от читателя не требуется каких-либо иных знаний в области математики. Существенное влияние на структуру книги и методику изложения материала оказал опыт авторов, приобретенный при чтении телевизионного цикла лекций по оптимизации в технике, который передавался по местной телевизионной сети для студентов-иностранцев и дипломированных инженеров. Поэтому есть основания полагать, что книга может служить учебным пособием как для обычных лекционных курсов, так и для телевизионных циклов лекций, краткосрочных курсов повышения квалификации, а также для самостоятельной работы.
Занятия по изучению материала книги были организованы в соответствии с двумя различными программами. Первая из них представляет собой обычный лекционный курс, рассчитанный на 45 пятидесятиминутных лекций в течение одного семестра. Вторая программа предусматривает 30 лекций и 15 семинарских занятий. В первом случае содержание книги можно излагать последовательно в порядке нумерации глав, за исключением гл. 14. Во втором случае гл. 1, 13 и 14, а также дополнительные практические.примеры рекомендуется обсуждать на семинарах, материал гл. 2—10 и гл. 12 — излагать в лекциях. При этом гл. 11 и разд. 8.3 и 9.4 приходится обычно опускать из-за недостатка лекционного времени. Домашние задания в обоих случаях должны включать ряд задач, приведенных в заключительной части каждой главы и предназначенных для решения как с помощью, так и без помощи ЭВМ. Решение задач на ЭВМ можно осуществлять, используя программы OPTLIB, ОРТ и BIAS, описание которых дано в гл. 12.
ПРЕДИСЛОВИЕ
Заметное влияние на подбор и структуру материала книги ока-аали советы и предложения наших коллег и наставников по соответствующим дисциплинам. Число таких сознательных или невольных' «участников» этой работы слишком велико, чтобы можно было упомянуть здесь каждого из них. Проф. Дон Филипс, работавший вместе с нами в Университете Пурдью, внес значительный вклад в первый вариант конспектов лекций, послуживших исходным материалом для написания книги. Курс лекций и их конспекты получили одобрение бывших деканов наших факультетов: Лоуэлла Б. Коппела, Уилбура Мейера, Р. У. Фокса и А. Г. Лефевра. Проф. Ф. Кейхан и проф. К. Нопф, д-р Ф. У. Арене, д-р Дж. А. Габриель, д-р Р. Рут, д-р Е. Сандгрен, д-р П. В. Сарма, Брэд Овертерф и Мохайндер Суд, а также П. К. Эсуаран, Дж. Поузи и Б. Нельсон внесли целый ряд поправок и улучшений. Мы признательны также нашим студентам, настойчиво проработавшим различные варианты рукописи, за многочисленные вопросы и просьбы о пояснении тех или иных результатов. Их подчас острые, но, как правило, справедливые критические высказывания служили отличным стимулом к совершенствованию материала книги. Наконец, хотелось бы выразить благодарность редактору книги Фрэнку Серра и его предшественнику Мейеру Кутцу за их настойчивость и терпение. Мы благодарны нашим женам и детям, позволившим нам тратить время на написание книги, за поддержку в течение всей работы.
Г. Реклейтис
А. Рейвиндран
К.. Рэгсдел
Уэст-Лафайетт, Индиана, лето 1983 года
ОГЛАВЛЕНИЕ
Предисловие к русскому изданию.................. 5
Предисловие............................ 7
Глава 1. Методологические основы оптимизации........... 10
1.1. Необходимые условия для применения оптимизационных методов 11
1.2. Применение методов оптимизации в инженерной практике ... 17
1.3. Структура оптимизационных задач............. 33
1.4. Некоторые замечания о книге в целом ........... 35
Литература........................... 36
Глава 2. Функции одной переменной.................. 37
2.1. Свойства функций одной переменной............. 37
2.2. Критерии оптимальности.................. 40
2.3. Методы исключения интервалов .............. 49
2.4. Полиномиальная аппроксимация и методы точечного оценивания 58
2.5. Методы с использованием производных........... 63
2.6. Сравнение методов..................... 71
2.7. Заключение......................... 73
Контрольные вопросы и задачи ................ 73
Литература........................... 78
Глава 3. Функции нескольких переменных ............. 79
3.1. Критерии оптимальности.................. 81
3.2. Методы прямого поиска................... 85
3.3. Градиентные методы.................... 109
3.4. Сравнение методов и результаты вычислительных экспериментов 132
3.5. Заключение........................ 138
Контрольные вопросы и задачи ................ 139
Литература.......................... 146
Глава 4. Линейное программирование ............... 150
4.1. Разработка моделей линейного программирования ...... 150
4.2. Графическое решение задачи линейного программирования с двумя переменными.................... 154
4.3. Задача линейного программирования в стандартной форме . . 158
4.4. Основы симплекс-метода................... 161
4.5. Решение задач ЛП на ЭВМ ................ 176
4.6. Анализ чувствительности в линейном программировании . . . 180
4.7. Приложения........................ 184
4.8. Развитие идей линейного программирования , ,...... 184
ОГЛАВЛЕНИЕ 34^
4.9. Заключение......................... 186-
Контрольные вопросы и задачи................. 186
Литература........................... '94
Глава 5. Критерии оптимальности в задачах с ограничениями .... 196
5.1. Задачи с ограничениями в виде равенств.......... 196-
5.2. Множители Лагранжа.................... 197
5.3. Экономическая интерпретация множителей Лагранжа..... 201
5.4. Условия Куна — Таккера.................. 202
5.5. Теоремы Куна — Таккера.................. 205
5.6. Условия существования седловой точки ........... 210
5.7. Условия оптимальности второго порядка .......... 213
5.8. Заключение......................... 220
Контрольные вопросы и задачи ................ 220
Литература........................... 224
Глава 6. Методы оптимизации на основе преобразования задачи .... 225
6.1. Понятие штрафной функции................. 226
6.2. Алгоритмы и программы ................. 244
6.3. Метод множителей..................... 246>
6.4. Заключение........................ 258
Контрольные вопросы и задачи ................ 259'
Литература.......................... 264
Глава 7. Методы прямого поиска в задачах условной оптимизации . . . 269
7.1. Подготовка задачи к решению ............... 269'
7.2. Использование методов поиска для решения задач безусловной оптимизации........................ 273
7.3. Методы случайного поиска ................ 284
7.4. Заключение . . . ,..................... 292:
Контрольные вопросы и задачи ................ 293
Литература.......................... 296
Глава 8. Методы линеаризации для задач условной оптимизации . . . 298
8.1. Непосредственное использование последовательности задач ЛП 299
8.2. Сепарабельное программирование.............. 317
8.3. Методы отсекающих плоскостей .............. 329
8.4. Заключение........................ 340
Контрольные вопросы и задачи................ 341
Литература ... , , , , ,.................. 346
9.1. Методы допустимых направлений.............. S
9.2. Обобщение симплекс-метода на задачи с линейными ограничениями ............................. 14
9.3. Обобщенный метод приведенного градиента.......... 30'
9.4. Методы проекций градиента................. 53
9.5. Приложение к проектированию................ 72
9.6. Заключение........................ 79-
Контрольные вопросы и задачи.................. 81
Литература.......................... 85
Глава 10. Методы квадратичной аппроксимации для задач с ограничениями 87
10.1. Непосредственное использование квадратичной аппроксимации 88
10.2. Квадратичная аппроксимация функции Лагранжа...... 93
10.3. Методы переменной метрики для задач условной оптимизации 100
10.4. Обсуждение........................ 105-
10.5. Заключение........................ 110
Контрольные вопросы и задачи.................. 111
Литература........................... 114
Глава 11. Задачи специальной структуры и методы их решения...... 116
11.1. Целочисленное программирование............. 116
11.2. Квадратичное программирование.............. 128
11.3. Задачи о дополнительности................. 134
11.4. Геометрическое программирование............. 141
11.5. Заключение........................ 164
Контрольные вопросы и задачи.................. 165-
Литература........................... 171
Глава 12. Сравнение методов условной оптимизации.......... 174
12.1. Принципы сравнения................... 174
12.2. Краткая история сравнительных экспериментов....... 176
12.3. Исследование Сандгрена.................. 179
12.4. Исследование Шитковского................ 189
12.5. Исследование Фэттлера по решению задач геометрического программирования ....................... 193
12.6. Сведения о программах................... 200
12.7. Заключение........................ 201
Литература........................... 202
Глава 13. Стратегии оптимизационного исследования.......... 206
13.1. Построение модели..................... 207
13.2. Реализация модели.................... 217
13.3. Оценка решения...................... 253
13.4. Заключение........................ 258
Контрольные вопросы и задачи.................. 259
Литература........................... 264
Глава 14. Примеры технических приложений.............. 266
14.1.Оптимизация размещения углеобогатительных фабрик с помощью
методов частично целочисленного программирования..... 266
14.2. Оптимизация процесса производства этиленгликоля и окиси этилена ..........,.................. 273
14.3. Оптимальное проектирование системы аккумулирования энергии сжатого воздуха.................... 283
14.4. Заключение......................... 295
Литература........................... 296
Приложение А. Элементы линейной алгебры............... 298
А. 1. Множества......................... 298
А. 2. Векторы.......................... 298
А. 3. Матрицы......................... 299
А. 4. Квадратичные формы.................... 304
А. 5. Выпуклые множества.................... 310
Приложение Б. Выпуклые и вогнутые функции............. 312
Приложение В. Метод последовательных исключений (метод Гаусса —
Жордана) . ..................... 315
Предметный указатель........................