Введение

Математические методы оптимизации, соответствующие алгоритмы и компьютерные программы можно рассматривать как эффективный элемент наукоёмких технологий, разработка которых в различных областях практики в настоящее время особенно актуальна.

Наибольший эффект в планировании производства, в проектировании различных объектов, в строительстве, в финансово-экономической деятельности и других областях может быть достигнут при переходе к выработке и принятию оптимальных решений (оптимальных планов, проектов, конструкций, технологий и т.д.)

В настоящее время для этого имеются достаточные вычислительные мощности, так как современные персональные компьютеры, на которых могут быть реализованы алгоритмы оптимизации, получили широкое распространение. Однако они в основном используются для других целей и область применения методов оптимизации может быть существенно расширена.

Основным препятствием на пути широкого использования в практической деятельности современных методов оптимизации является необходимость разработки математических моделей конкретных задач, то есть сведение практической задачи к математической задаче поиска оптимума. Для этого необходимы знания в соответствующей предметной области, понимание особенностей практической задачи и вместе с тем нужны знания современных методов оптимизации. Разработка сложных систем, в которых используются методы оптимизации, требует усилий различных специалистов и больших затрат времени. Поэтому в сложных системах компьютеры часто используются для автоматизации вспомогательных операций (вариантные расчёты, визуализация данных и промежуточных результатов и т.д.), но не для выработки оптимальных решений. При решении творческих задач принятия решений варианты этих решений задаёт человек, а компьютер в лучшем случае используется как вспомогательное средство для проверки приемлемости этих вариантов и их сравнения по тем или иным показателям. В тех областях деятельности, где число возможных вариантов решения конкретной практической задачи относительно невелико, и человек в состоянии при желании и достаточной квалификации путём перебора вариантов выбрать наилучший из них, нет особой надобности в применении сложных методов оптимизации, так как полный перебор - это самый универсальный и надёжный метод оптимизации. Однако при этом должна быть уверенность, что рассмотрены все допустимые в конкретных условиях варианты, а не только те, «которые видит специалист.» В задачах, где число вариантов принятия решения достаточно велико и специалист не в состоянии рассмотреть их все, перебор малого числа интуитивно назначаемых вариантов может привести к пропуску оптимального решения. В этих случаях наличие математической модели задачи и использование компьтера для выработки оптимального варианта с применением алгоритмов и программ оптимизации может быть более эффективно, несмотря на то, что математическая модель задачи творческого характера, как правило, не отражает «все детали и тонкости» и получаемое компьютерное решение только формально является оптимальным. Если эта модель отражает главное и используется обоснованный алгоритм оптимизации, то получаемый вариант должен быть по крайней мере принят во внимание. В худшем случае он должен рассматриваться как «дружеский совет» специалисту, принимающему решение. Чем качественнее математическая модель, алгоритм и программа оптимизации, тем более ценным оказывается такой совет (подсказка).

Ещё одним осложняющим обстоятельством в деле практического применения методов оптимизации является то, что в настоящее время методы оптимизации изучаются в основном будущими математиками, причём в основном в теоретическом плане, а для их практического применения нужны знания в предметной области. В то же время практическое применение современных методов оптимизации в значительной мере сдерживается именно отсутствием соответствующих математических знаний у действующих инженеров, специалистов в прикладных областях.

Данная работа - это попытка преодолеть образовавшийся разрыв путём изложения основных идей, методов и алгоритмов с привлечением ограниченного числа математических понятий, которые к тому же поясняются в тексте.

Наибольшую пользу может принести изучение того, как удалось построить математическую модель и применить тот или иной метод оптимизации для решения конкретной сложной задачи. Особенно это относится к применению метода динамического программирования, который в «компьютерную эпоху» получил широкое применение в самых различных областях практики. Этот мощный метод оптимизации далеко не универсальный. Известны безуспешные попытки его применения без должного анализа особенностей конкретной задачи оптимизации. Поэтому при изложении основных идей динамического программирования в книге основное внимание уделяется принципу оптимальности Р. Веллмана и области применимости его метода. Рассматриваются различные виды целевых функций и систем ограничений, при наличии которых имеются особенности в применении динамического программирования. Для некоторых известных задач, решаемых с помощью динамического программирования, приводятся новые, более эффективные алгоритмы. Это касается прежде всего задач, в которых множество состояний не задаётся изначально, например в виде регулярной сетки, а формируется в процессе поиска решения. При этом возможна не только отбраковка путей, приводящих в рассматриваемое состояние, но и отбраковка заведомо бесперспективных состояний, что существенно повышает эффективность метода.

В книге критически оцениваются опыт применения динамического программирования в различных областях практики и некоторые устоявшиеся суждения на этот счёт.

Автор не ставил своей целью изложение всех или хотя бы большинства математических методов оптимизации. Цель автора - оказать помощь в освоении основных идей дискретной оптимизации, на конкретных практических примерах из различных областей продемонстрировать эти идеи, соответствующие методы и алгоритмы, а также особенности их реализации в компьютерных программах.

Известно, что наибольшие трудности в решении практических задач вызывает построение адекватных математических моделей, выбор метода оптимизации и разработка соответствующих алгоритмов и программ решения конкретной задачи. В этой связи в книге для нескольких практических задач из различных областей приводятся математические модели, рассматриваются возможности использования различных методов оптимизации для решения одной и той же прикладной задачи, излагаются алгоритмы и даются сведения о программных реализациях.

Особое внимание уделяется использованию конкретных особенностей модели, что позволяет продемонстрировать на реальных практических задачах как использование этих особенностей приводит к резкому сокращению объёма вычислений и делает реальным решение задач большой размерности.

Необходимо отметить, что для широкого круга задач оптимизации имеются стандартные программные средства. Нужно просто уметь свести исходную практическую задачу к задаче оптимизации, то есть построить математическую модель и далее использовать готовую программу. Значительно сложнее решение задач большой размерности. Использование стандартных алгоритмов и программ без учёта специфических особенностей конкретной задачи в этом случае может оказаться нецелесообразным из-за неприемлемо большого времени счёта на доступных компьютерах. В книге на конкретных математических моделях различных прикладных задач показано как можно использовать их особенности и существенно упростить алгоритмы оптимизации, оставаясь в рамках математически корректных методов.

В частности применительно к динамическому программированию показано как в ряде случаев можно модифицировать математические модели, если они не позволяют применить этот метод. Кроме того, программная реализация метода с учётом конкретных особенностей задачи позволяет резко сократить время счёта. Естественно, что в этих случаях речь идёт не о применении стандартных программ, а о разработке специальных программных средств. В книге приводятся данные о решении конкретных прикладных задач оптимизации по специально разработанным программам, которые в дальнейшем были усовершенствованы именно с учётом особенностей задач, что привело к резкому повышению их эффективности.

На основе практического опыта решения прикладных задач оптимизации в книге последовательно проводится вывод о нецелесообразности различного рода «эвристических» поправок к математическим методам оптимизации. Лучше упростить модель задачи, имея возможность оценить последствия этих упрощений, чем применять какой-либо «эвристический» алгоритм поиска решения вместо математически обоснованных алгоритмов.

Принятый в книге порядок изложения материала - от простого к сложному. Вначале на простой задаче демонстрируется основная идея каждого метода, приводятся необходимые графические иллюстрации на задачах малой размерности, затем даются обобщения и математические формулировки, после чего разбираются конкретные практические задачи и алгоритмы, рассматриваются возможности их практической реализации для задач большой размерности, либо приводятся сведения об уже осуществлённых реализациях.

Автор сознательно избегает использования сложной математической символики, стремясь сделать изложение максимально доступным для широкого круга читателей.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >