Математика | ||||
Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 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 Предметный указатель........................ Цена: 500руб. |
||||