Д. Химмельблау APPLIED NONLINEAR PROGRAMMING David M. Himmelblau ПРИКЛАДНОЕ НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ The University of Texas, Austin, Texas Перевод с английского И. M. БЫХОВСКОЙ и Б. Т. ВАВИЛОВА Под редакцией M, Л. БЫХОВСКОГО McGraw-HilI Book Company 1972 ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1975 УДК 51.380.115 Книга посвящена методам оптимального управления системами с нелинейными целевыми функциями. Описаны методы нелинейного программирования как при отсутствии ограничений на управляю- щие переменные, так и при наличии ограничений. Рассматриваются такие вопросы, как возможность получения решения, время оптими- зации, точность решения и т. д. Для наиболее важных методов при- водятся программы решения на языке ФОРТРАН. Каждая глава содержит много примеров, не 'юлько поясняющих теорию, но и иллю- стрирующих необходимые вычислительные процедуры и используе- мые программы. Книга представляет интерес для специалистов по автоматическо- му управлению; вычислительной технике и прикладной математике. Редакция литературы по новой технике (С) Перевод на русский язык, «Мир», 1974 _ 3314-429 U41 (01)-75 148-74 ПРЕДИСЛОВИЕ Цель этой книги состоит в том, чтобы в доступной форме изложить некото- рые из наиболее эффективных методов нелинейного программирования и дать сравнительную оценку этих методов Для решения общей задачи нелинейного про- граммирования было предложено довольно много алгоритмов, однако лишь не- многие из них оказались эффективными для задач большой размерности. Ни один из этих алгоритмов не имеет по отношению к другим таких преимуществ, чтобы его можно было считать универсальным средством решения любых задач не- линейного программирования, В данной книге описанию используемых методов уделяется больше внима- ния, чем математическим доказательствам сходимости алгоритмов нелинейного программирования для определенных типов задач. Такие доказательства, разу- меется, важны; однако они применимы только к весьма узким категориям задач и*могут служить лишь как дополнительная информация для исследователя, при- меняющего тот или иной алгоритм. В отличие от линейного программирования при решении задачи нелинейного программирования выбранный алгоритм может оказаться эффективным, даже если не удается доказать его сходимость. Справед- ливо и обратное утверждение, а именно: наличие доказательства сходимости алго- ритма в частных случаях может не означать, что он окажется удовлетвопитель- ным для более сложных задач. В книге подробно описаны те алгоритмы нелинейного программирования, которые оказались достаточно эффективными на практике. При сравнении алго- ритмов были использованы следующие критерии: 1) надежность; 2) скорость решения; 3) время подготовки задачи для решения; 4) точность решения; 5) степень выполнения ограничивающих условий. Рассматриваемые методы предназначены для оптимизации значения некоторой нелинейной функции при ограничениях в виде равенств и (или) неравенств, содержащих функции большого числа переменных. Все эти переменные являются детерминированными (в отличие от случайных, или стохастических, переменных). Описанные методы могут быть практически реализованы лишь при помощи совре- менных цифровых или гибридных ЭВМ. Использование аналоговых вычислитель- ных машин не рассматривается. Не рассматриваются также ни целочисленное (или дискретное) программирование, ни методы поиска оптимального решения динами- ческих задач, т. е. задач, в которых время является одним из параметров. В этой книге мы не стремимся раскрыть отдельные тонкости методов оптими- зации, однако здесь приведены все необходимые подробности, позволяющие чи- тателю проследить существенные этапы каждого из рассматриваемых методов. Нередко оказывается, что детали программирования некоторого алгоритма, особенно в часто повторяемых процедурах, заметно влияют на качество работы ал- горитма в целом.-Подробно рассмотренные примеры в конце каждого раздела пояс- няют вычислительные аспекты алгоритмов; для иллюстрации логической струк- туры алгоритмов приведено большое количество блок-схем. Приложение Б содер- жит нееколько машинных программ для наиболее удачных алгоритмов. Благодаря Предисловие тому что для всех алгоритмов используются одни и те же обозначения, можно глуб- же понять их структурные связи друг с другом и общие свойства. Книга состоит из трех частей. Первая часть содержит две главы. Глава 1 пред- ставляет собой краткое введение; в гл. 2 формулируется общая задача нелинейного программирования, рассматривается связь нелинейного программирования с дру- гими видами математического программирования и, наконец, устанавливаются необходимые и достаточные условия существования оптимального решения. Во второй части рассматриваются алгоритмы нелинейного программирования при отсутствии ограничений. В гл. 3 описывается градиентный метод, метод вто- рых производных и другие связанные с ними стратегии, в которых используются производные. Глава 4 посвящена рассмотрению стратегий поиска. В гл. 5 дается оценка различных алгоритмов оптимизации при отсутствии ограничений. В третьей части описываются алгоритмы оптимизации при наличии ограни- чений. Глава 6 посвящена рассмотрению методов линеаризации. В гл. 7 изло- жены методы штрафных функций, а в гл. 8 описан метод скользящего допуска. Оценки алгоритмов оптимизации при наличии ограничений приводятся в гл. 9. Приложение А содержит ряд упражнений с соответствующими решениями. Кроме того, в каждой главе (за исключением первой) приводятся дополнительные задачи, предлагаемые читателю для решения. Для понимания описанных в книге алгоритмов необходимо знание основ ма- тематического анализа, некоторое умение обращаться с матрицами и векторами, а также знакомство с методами решения задач линейного программирования. В приложении В приводятся основные сведения из матричной алгебры. Для чтения машинных программ необходимо знание основ программирования на ФОРТРАНе. Однако эти программы снабжены необходимыми инструкциями, так что их можно использовать, владея лишь методикой перфорирования Такого рода «механиче- ский» подход к использованию программ иногда оказывается вполне приемлемым. однако при отсутствии должной осторожности он может привести к ошибкам. Д. М. Химмельблау Часть I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ В первой части книги сформулирована задача нелинейного программирования, показана ее связь с реальными физическими задачами, а также приведена терминология, связанная с нелиней- ным программированием. Кроме того, здесь описаны методы, с по- мощью которых можно определить, действительно ли предполага- емое оптимальное решение является оптимальным, Глава 1 ВВЕДЕНИЕ На протяжении всей своей истории люди при необходимости принимать решения прибегали к сложным ритуалам. Они устраивали торжественные церемонии, приносили в жертву животных, гадали по звездам и следили за полетом птиц. Они полагались на народные приметы и старались следовать примитивным правилам, облегчаю- щим им трудную задачу принятия решений. В настоящее время для принятия решения используют новый и, по-видимому, более научный «ритуал», основанный на применении электронно-вычисли- тельной машины. Без современных технических средств человече- ский ум, вероятно, не может учесть многочисленные и разно- образные факторы, с которыми сталкиваются при управлении пред- приятием, конструировании ракеты или регулировании движения транспорта. Существующие в настоящее время многочисленные мате- матические методы оптимизации уже достаточно развиты, что по- зволяет эффективно использовать возможности цифровых, и гиб- ридных вычислительных машин. Одним из этих методов является математическое программирование, включающее в себя как частный случай нелинейное программирование. Термин «математическое программирование» предложен Робер- том Дорфманом приблизительно в 1950 г.; теперь он объединяет линейное программирование, целочисленное программирование, вы- пуклое программирование, нелинейное программирование и програм- мирование при наличии неопределенности. Нелинейное програм- мирование имеет дело с оптимизацией нелинейных функций при линейных и (или) нелинейных ограничениях. Типичными областями его применения являются прогнозирование, планирование промыш- ленного производства, управление товарными ресурсами, контроль качества выпускаемой продукции, планирование обслуживания и ремонта, проектирование технологических линий (процессов), учет и планирование капиталовложений. Пока еще не существует общего метода решения нелинейных задач оптимизации, такого, как, например, симплексный алгоритм, разработанный для задач линей- ного программирования. Нелинейное программирование при реше- нии задач включает в себя элементы экспериментирования. Его развитие до сих пор сводилось к предложениям частных алгоритмов, Введение программированию их, проверке результатов применения этих алгорит- мов в конкретных задачах, представляющих практический интерес, и построению лучших алгоритмов на основе приобретенного опыта. Последние двадцать лет в области математического програм- мирования значительные усилия были сконцентрированы на линей- ном программировании. Полученные результаты столь значительны, что достигнутый здесь уровень позволяет решать большинство практических задач. Что же касается нелинейного программи- рования, то, хотя здесь и было предложено большое число различных стратегий поиска решений, успешное применение нашли лишь не- многие алгоритмы. Область применения разработанных алгоритмов нелинейного программирования весьма ограничена. В связи с даль- нейшим развитием ЭВМ и растущей необходимостью более точно решать задачи, представляющие практический интерес, возникает необходимость в методах решения задач нелинейного программи- рования с более широкой областью применимости. Большинство практических задач имеет несколько (а некоторые, возможно, даже бесконечное число) решений. Целью оптимизации является нахождение наилучшего решения среди многих потенци- ально возможных в соответствии с некоторым критерием эффектив- ности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных анали- тических и численных математических процедур и кончая разумным применением простой арифметики. Предполагая, что подлежащая оптимизации задача некоторым образом определена (не обязательно математически), можно классифицировать общие методы оптими- зации следующим сбразом: 1. Аналитические методы, использующие классические методы дифференциального и вариационного исчислений. Эти методы заклю- чаются в определении экстремума функции / (х) путем нахождения тех значений х, которые обращают в нуль производные / (х) по х. В случае поиска экстремума f (х) при наличии ограничений приме- няются такие методы, как метод множителей Лагранжа и метод ограниченных вариаций. При использовании аналитических методов задача оптимизации должна быть сформулирована математически с тем, чтобы можно было обращаться со всеми фигурирующими в ней функциями и переменными при помощи известных правил. Для решения больших существенно нелинейных задач аналитические методы оказываются непригодными, и поэтому в данной книге они не рассматриваются. 2. Численные методы, использующие предшествующую инфор- мацию для построения улучшенных решений задачи при помощи итерационных процедур. Численные методы применяются для решения задач, которые не могут быть решены аналитически, и, поскольку практические задачи поддаются решению численными 10 Глава 1 методами, именно эти методы нелинейного программирования явля- ются предметом обсуждения в данной книге. К другим общим методам, которые эффективно применяются при решении задач оптимизации, но которые здесь не рассматрива- ются, относятся следующие: 3. Графические методы, основанные на графическом изображе- нии функции, подлежащей максимизации или минимизации, в зависимости от одной или нескольких переменных. Экстремум функции в этом случае получают непосредственно путем анализа ее графика. Преимущество графических методов состоит в том, что они просты и сразу показывают, существует решение или нет. С другой стороны, они применимы в тех случаях, когда критерий качества является функцией одной или максимум двух независи- мых переменных. 4. Экспериментальные методы. Экстремум функции можно иногда найти, экспериментируя непосредственно с реальными переменными вместо того, чтобы исследовать соответствующую мате- матическую модель. Результаты одного эксперимента используют- ся для планирования следующего эксперимента, позволяющего получить улучшенные результаты. 5. Методы исследования различных вариантов. Эти методы осно- ваны на анализе нескольких возможных решений одной и той же задачи с целью выбора наилучшего. Таким образом, «наилучшее» решение, полученное методом исследования различных вариантов, будет скорее всего лишь субоптимальным. При выборе наиболее подходящего способа описания реальных процессов приходится сталкиваться с рядом трудностей, которые для удобства обсуждения можно подразделить на две группы. Одна группа связана с построением математической модели про- цесса, а другая — с численными методами решения. В этой книге мы можем только отметить эти трудности и, где возможно, указать пути их устранения при описании того или иного конкретного ал- горитма. Математическая модель содержит функции, участвующие в про- цедуре оптимизации. Очевидно, для того чтобы искомый экстремум имел физический смысл, выбранная модель должна адекватно отра- жать существенные черты реального процесса. Но даже если это требование выполнено, при построении модели встречаются следу- ющие типичные затруднения: 1. Оптимизируемый критерий может быть нечувствительным к изменениям независимых (оптимизируемых) переменных и по- этому не удается определить четко выраженный экстремум. 2. Оптимизируемый критерий или некоторые из ограничений могут принимать в области поиска решения неограниченные зна- чения; значения частных производных в математической модели также могут стать неограниченными. Особенно подвержены этой опасности Введение 11 модели с полиномами в знаменателе. Так, например, значения функции у= ьo+l:'lx:^ ЬгЧ + ЬцХг и ее первой частной производной по х^ ду _ — &о&2 + &1&з^ дх! ~ ФЛ + Ь^ХУ обращаются в бесконечность при Ь^ = —Ь^. Эту трудность можно преодолеть, ограничив области допустимых значений неза- висимых переменных путем введения дополнительных ограничений в задачу, или же изменив формулировку самой математической модели. 3. Переменные могут быть плохо масштабированы. Трудности масштабирования могут возникнуть, например, когда один из членов в выражении для критерия имеет существенно иной порядок величины, чем другой. При этом критерий становится нечувстви- тельным к изменениям значений переменных в меньшем члене. Например, значение целевой функции