Заключение

Рассмотренные нами методы далеко не исчерпывают всё многообразие методов дискретной оптимизации. Изложены лишь основные идеи и методы.

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

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

Общие рекомендации по применению методов оптимизации включают следующее:

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

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

Приложение 1.

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