Рис.1.1 - Идея метода множественных стрельб

Несмотря на значительный рост числа неизвестных в ММС, данная схема обладает рядом преимуществ :

1. Упрощается учёт априорной информации о переменных состояния, определяемой по значениям замеров, при выборе начального приближения.
2. Подходящий выбор начальной точки обычно позволяет избежать выхода на локальный минимум задачи.
3. Данный метод является численно устойчивым и позволяет решать задачу оценки параметров даже для нестабильных и хоатических систем.
4. Особая структура целевой функции позволяет упростить реализацию параллельных алгоритмов её подсчёта.

2. Алгоритмы оптимизации

2.1 Классификация алгоритмов оптимизации

Существует несколько альтернативных подходов к классификации локально-детерминистических алгоритмов оптимизации (рис.2.1).

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

1. алгоритмы безусловной оптимизации;
2. алгоритмы решения задачи оптимизации с прямыми ограничениями на переменные;
3. алгоритмы условной оптимизации для задач с ограничениями-равенствами;
4. алгоритмы условной оптимизации для задач со смешанными ограничениями;
5. алгоритмы нелинейных наименьших квадратов.

Второй подход основывается на учёте различных критериев, которые определяют характерные черты реализации алгоритмов . Согласно одному из таких критериев методы оптимизации делятся на активные (последовательные ) и пассивные . В пассивных методах все точки для дальнейшего анализа выбираются одновременно до начала вычислений. В активных методах точки выбираются последовательно, выбор каждой последующей точки зависит от значений предыдущих. Другим критерием классификации является информация о функции, которую требует алгоритм. Если для успешного выполнения алгоритма достаточно лишь информации о значение функции в точке, то такой алгоритм относится к алгоритмам нулевого порядка (метод Гаусса, симплексный метод Недлера-Мида, методы поворота системи координат Хука-Дживса, классический Розенброка, метод Пауэлла и т.д.). Если дополнительно требуется знание о градиенте, то алгоритм относится к алгоритмам первого порядка . Алгоритмы второго порядка кроме знания значение функции в точке и её градиента, нуждаются также в информации о матрице Гессе (метод Ньютона, классические SQP-схемы). Среди локально-детерминистических методов оптимизации наиболее представительную группу составляют методы спуска , которые в свою очередь базируются на двух моделях. Первую модель образуют методы линейного поиска , в которых на каждой итерации направление спуска определяется однозначно, а оцениванию подлежит длина шага. Вторую модель образуют методы доверительных областей (trust-region ), в которых наоборот на каждой итерации оценивается направление спуска. Среди методов спуска первого порядка можно выделить такие группы методов :

1. градиентные алгоритмы;
2. квазиньютоновские алгоритмы (ДФП, БФГШ, SR1);
3. методы сопрпяжённых направлений (метод Флетчера-Ривза, метод Полака-Рибьера);
4. специализированные алгоритмы минимизации квадратов нелинейных функций (метод Гаусса-Ньютона, метод Левенберга-Маркарда, ряд SQP-схем).

Рис.2.1 - Классификация алгоритмов, решающих задачу математического программирования

2.2 Обзор существующего оптимизационного ПО

На сегодняшний день разработано множество оптимизационных программ, реализующих локально детерминистические алгоритмы. Многие из этих кодов распространяется под лицензией GPL, часть напротив является платной либо частично платной. Условно всё оптимизационное ПО можно разбить на три группы (рис.2.2):

1. программные пакеты, ориентированные на решение задачи математического программирования (на рис. оттенки зелёного);
2. численные библиотеки, содержащие алгоритмы оптимизации (на рис. жёлтый цвет);
3. системы оптимизации и моделирующие среды (на рис. синий цвет).

Рис.2.2 - Классификация ПО, решающего задачу математического программирования

Часть из известных оптимизационных пакетов ориентирована на решение только одного класса оптимизационных задач, но некоторые пакеты способны эффективно решать несколько классов задач. Характерной чертой пакетов для решения задачи оптимизации с прямыми ограничениями на переменные является то, что они достаточно эффективно справляются с задачей безусловной оптимизации. Большинство оптимизационных пакетов реализованы на языке Fortran. Наиболее известными из них являются LANCELOT и MERLIN. Именно с эффективностью реализованных в них процедур обычно производится сравнение эффективности новых алгоритмов. LANCELOT является одной из наиболее мощных библиотек оптимизационных алгоритмов, ориентированных прежде всего на решение задач большой размерности. Язык реализации библиотеки - ANSI Fortran 77. Хотя недавно вышла адаптация пакета LANCELOT на Fortran 99. На данный момент LANCELOT разработкой занимается Council for the Central Laboratory of the Research Councils (CCLRC). Пакет MERLIN был разработан в университете г.Иоаннина (Греция) и первоначально предназначался для решения задачи оптимизации с прямыми ограничениями на переменные. Сейчас функциональность пакета значительно расширилась. Одним из наиболее известных пакетов для решения задач безусловной оптимизации и оптимизации с прямыми ограничениями на переменные на сегодня является пакет L-BFGS-B, разработанный в Северо-Западном университете (США). С недавнего времени начали появляться оптимизационные пакеты, реализованные на C++ (OptSolve++, OPT++, macopt). Часто такие пакеты уже содержат реализации параллельных алгоритмов оптимизации (OptSolve++, Bob++).

Численные библиотеки NAG, HSL и IMSL среди прочих неспециализированных численных библиотек выделяются наиболее развитой системой алгоритмов оптимизации. В библиотеке NAG алгоритмы оптимизации собраны в папку E04. Разработкой библиотеки занимается The Numerical Algorithms Group Ltd. На данный момент доступны реализации библиотеки на Fortran и C, в недавнем прошлом сушествовали только Fortran77 и Algol68 версии библиотеки. Библиотека является коммерческой. Библиотека HSL (Harwell Subroutine Library) разрабатывается CCLRC (в деревушке Харвел неподалёку от Оксфордшира). На данный моент библиотека HSL реализована только на ISO Fortran. Последний известный релиз библиотеки состоялся в сентябре 2004. Алгоритмы оптимизации библиотеки IMSL собраны в главу 8 её реализации на языке ANSI Fortran. Реализация библиотеки на C содержит только часть этих алгоритмов. Доступны также ограниченные реализации этой библиотеке на Java и C#.NET. Разработкой библиотеки занимается компания Visual Numerics Inc.

Системы оптимизации и моделирующие среды обычно представляют из себя развитый законченый продукт и имеют встроенный собственный (либо стандартизированный) язык моделирования, позволяющий достаточно просто формулировать оптимизационные задачи. Обычно такие системы и среды предоставляют интерфейс для подключения внешних пакетов, реализованных на Fortrn и C. Более того, моделирующая среда GAMS, разработанная GAMS Development Corporation, не имеет собственных оптимизационных кодов, а лишь предоставляет интерфейс для подключения пакета MINOS. Системы оптимизации Speakeasy также имеет интерфейс для подключения внешней библиотеки NAG, но в то же время в ней содержатся и "родные" пакеты, такие как EISPACK и FFTPACK. AMPL представляет из себя специализированный достаточно гибкий язык моделирования для постановки и решения задач математического программирования. Matlab является наиболее известной системой из вышеперечисленных. В данной системе реализованы квазиньютоновские алгоритмы, метод Недлера-Мида, метод Ньютона, метод Левенберга-Маркарда и т.д.

Существуют также пакеты, ориентированные на решение задачи оценки параметров. К ним следует отнести пакеты EASY-FIT, разработанный в университете г.Бейрут под руководством проф. К.Шитковского, и пакет PAREST, разработанный в Мюнхенском техническом университете. Причём в пакете PAREST реализован метод множественных стрельб.

К оптимизационному ПО стоит также отнести библиотеку тестовых оптимизационных задач CUTEr, разработанную Н.Гоулдом, Д.Орбаном и Ф.Тоинтом. Данная библиотека, по сути, является стандартом для тестирования алгоритмов оптимизации.

3. Обзор публиуаций по теме

Ежегодно появляются десяки публикаций, посвящённых оптимизационным задачам, возникающих при моделировании СДС, и в частности вопросам оценки параметров моделеи. Не смотря на то, что сушествует множество основательных трудов в области оценки параметров , метод множественных стрельб достаточно слабо освещён в литературе. Классические книги проф. Х.Бока, в которых проведено обоснование и доказательство практической ценности ММС, из-за малого тиража практически недоступны. Статей посвящённых ММС также относительно не много. В большинстве из них производится только обзор метода, а также способов его реализации. Анализ сходимости и другие важные вещи там отсутствуют.

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

Поскольку в данной работе в первую очередь планируется реализовать модификацию БФГШ-метода для решения задачи оптимизации с прямыми ограничениями на переменные, то в дальнейшем здесь будут рассматриваться только публикации, в которых описывается БФГШ-метод. Метод Бройдена-Флетчера-Голдфарба-Шэнно (БФГШ) был предложен в 1970 году как развитие общей идеи квазиньютоновских методов, предложенной Давидоном. На сегодняшний день этот метод является наиболее эффективным квазиньютоновским методом. В 1980 Дж.Ноцедалем была предложена модификация БФГШ-алгоритма, требующая небольших затрат оперативной памяти и известная под названием LBFGS-метода , а в 1991 году им же в соавторстве с Р.Бёрдом был предложен L-BFGS-B-метод, позволяющий решать не только задачи безусловной оптимизации, но и задачи оптимизации с прямыми ограничениями на переменные . В 1994 году появился пакет, реализующий LBFGS-B-алгоритм на языке Fortran. В 1994 году вышел последний релиз этого пакета. В дальнейшем публикации, касающиеся LBFGS появлялись ежегодно, но принципиально новых идей по модификацие LBFGS-алгоритма в них не было.

4. Краткое описание используемых алгоритмов

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

В качестве основного алгоритма оптимизации на данном этапе используется LBFGS-B-метод . Направление в данном методе ищется согласно формуле (4.1):

Для учёта ограничений в LBFGS-B-алгоритме используется схема, идентичная той, которая применяется в методе проекции градиента. Классический LBFGS-B-алгоритм использует при выборе длины шага процедуру "бэктрэкинга" ("backtracking"). В данной работе планируется несколько улучшить классическую схему LBFGS-B-метода путём использования в нём при выборе длины шага интерполяционной процедуры.

Рис.4.1 - Схема работы методов спуска

Выводы

В данной работе были кратко рассмотрены основные классы оптимизационных задач, выделены их особенности и рассмотрены подходы, позволяющие находить их решения. Также здесь приведен краткий обзор алгоритмов оптимизации, существующего оптимизационного ПО и литературы по данной тематике. На текущий момент в рамках работы разработаны и внедрены в моделирующую среду Diana интерфейсы основных оптимизационных задач и решателей данных задач. Был дополнительно реализован простой градиентный алгоритм алгоритм с модификацией Армихо , но в связи с тем, что данный алгоритм не справлялся с решением плохо масштабированных задач, от дальнейших исследований в данном направление пришлось отказаться. Вместо этого в моделирующую среду Diana мной был имплементирован код LBFGS-B-алгоритма, разработанный П.Лу .

В дальнейшем планируется на языке C++ реализовать модифицированный LBFGS-B-алгоритм и исследовать эффективность предложенной модификации на реальных моделях с использованием как подхода с оценкой начальной точки, так и ММС, а также исследовать один из алгоритмов минимизации квадратов нелинейных функций.

Список использованной литературы

1. Nocedal, Jorge; Wright, Stephen J. Numerical optimization. - New York, NY : Springer, Springer series in operations research, 1999. - 623 с.
2. Измаилов, А.Ф.; Солодов, М.В. Численные методы оптимизации. - М.: «ФИЗМАТЛИТ», 2003. - 304 с.
3. Бертсекас, Д. Условная оптимизация и методы множителей Лагранжа. - М.:Радио и связь, 1987. - 400 с.
4. Сухарев, А.Г.; Тимохов, А.В.; Фёдоров, В.В. Курс методов оптимизации. - М.: Наука, 1986. - 328 с.
5. More, Jorge J.; Wright, Stephen J. Optimization software guide. - Philadelphia, Pa.: SIAM Soc. for Industrial and Applied Mathematics, 1994. - 154 с.
6. Peifer, M.; Timmer, J. Parameter estimation in ordinary differential equations using the method of multiple shooting - a review. - Freiburg: Freiburg Centre for Data Analysis and Modelling, 2005
7. Byrd, Richard H.; Lu,P.; Nocedal, Jorge; Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization. - Northwest university, 1994
8. Horbelt, Werner Maximum likelihood estimation in dynamical systems. - Freiburg: Albert-Ludwigs-Universitaet Freiburg Fakultaet fuer Physik, 2001.
9. Polak, Elijah Optimization: algorithms and consistent approximations (Applied mathematical sciences; v.124). - New York, NY : Springer, 1997. - 779 с.
10. Censor, Yair; Zenios, Stavros Andrea Parallel optimization: theory, algorithms, and applications - New York, NY : Oxford Univ. Press, 1997. - 539 с.
11. Сеа, Ж. Оптимизация. Теория и алгоритмы. - М.: «Мир», 1973. - 244 с.
12. Retout, Sylvie; Mentre, France; Bruno, Rene Fisher information matrix for non-linear mixed-e ects models: evaluation and application for optimal design of enoxaparin population pharmacokinetics. - Sylvie Retout, INSERM U436, CHU Pitie Salpetriere, 91 bd de l Hopital, 75013 Paris, France, May 2001. - 15 с.
13. Bock, Hans Georg; Koerkel, Stefan; Kostina, Ekaterina; Schloeder, Johannes P. Methods of Design of Optimal Experiments with Application to Parameter Estimation in Enzyme Catalytic Processes. - Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Im Neuenheimer Feld 368, 69120 Heidelberg, Germany, October 2004. - 25 с.
14. Kutalik, Zoltan; Cho, Kwang-Hyun; Gordon, Steve V.; Wolkenhauer, Olaf Optimal Sampling Time Selection for Parameter Estimation in Dynamic Pathway Modelling. - Control Systems Centre, Department of Electrical Engineering and Electronics, UMIST, Manchester, UK, - 2003. - 22 с.
15. Broyden, C. G. Journal of the Institute of Mathematics and Its Applications.#6. - 1970. - 76-90 с.
16. Fletcher, R. Computer Journal.#13. - 1970. - 317 с.
17. Goldfarb, D. - 1970. - 23 с.
18. Shanno, D. F. Mathematics of Computation.#24. - 1970. - 647 с.
19. Walter, Eric ; Pronzato, Luc Identification of parametric models from experimental data. - London: Springer, 1997. - 403 с.
20. Schittkowski, Klaus Numerical data fitting in dynamical systems: a practical introduction with applications and software . - Dordrecht : Kluwer, 2002. - 392 с.
21. Nocedal, Jorge Mathematics of Computation.(Updating quesi-Newton matrices with limited storage.)#35 - 1980, - 773-782 с.

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

Многоэтапные процессы принятия решений

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

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

Основная идея, которая привела к созданию вычислительного метода, была сформулирована в начале 50-х годов прошлого века Р. Веллманом (R. Bellman), сделавшим самый большой вклад в развитие метода, который он назвал «динамическое программирование» , но который чаще называют просто методом Веллмана.

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

Реализация метода для каждого конкретного многошагового процесса принятия решений, как правило, требует разработки нового алгоритма. Многие практические задачи, которые можно решать с помощью этого метода, были рассмотрены его автором совместно с Дрейфусом (S. Dreyfus) .

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

Для изложения основной идеи метода рассмотрим сначала простую задачу поиска оптимального пути на двумерной прямоугольной сетке, в которой разрешены переходы из одного узла в другой только по горизонтали (вправо) или по вертикали (вверх). Заданы затраты на каждый из возможных переходов и требуется найти путь с минимальными суммарными затратами из левого нижнего угла сетки (рис. 2.1 точка А) в правый верхний угол (точка В). Такой путь называется оптимальным. Узлы сетки пронумерованы так, как показано на рис. 2.1, где шип задают соответственно вертикальный и горизонтальный размеры сетки (число шагов по вертикали и горизонтали соответственно).

Затраты на переход в узел i, j по горизонтали (из узла i, j-1) обозначим как gy ; а по вертикали (из узла i-1, j) - vy. В точке А соответствующие величины равны нулю. Таким образом, исходными данными в этой задаче являются: m, п и все шаговые затраты gy и vy (i = 0, 1,2, ..., m; j = 0, 1,2, ..., п). Всего n(m + 1) чисел gy и m(n + 1) чисел vy, то есть всего 2mn + m + п переходов и соответствующих им затрат.

Рис. 2.1.

При небольших размерах сетки можно попытаться решить задачу методом полного перебора вариантов возможных путей из точки А в точку В. Однако эта идея абсолютно бесперспективна уже при величинах шип порядка 10 из-за резкого роста числа вариантов возможных путей из точки А в точку В с увеличением размеров сетки. Действительно, каждому варианту пути из точки А в точку В соответствует ровно m шагов по вертикали и ровно п шагов по горизонтали, но последовательность этих шагов для каждого варианта своя. Если шагу по горизонтали поставить в соответствие 0, а шагу по вертикали 1, то очевидно, что вариант пути - это выбор размещения m единиц по m + п возможным местам (оставшиеся п мест займут нули). Для размещения первой единицы имеется m + п возможностей, для второй - m + n - I возможностей и т. д. В итоге получаем формулу для числа вариантов пути N.

Уже при m = п = 10 N = 184756.

Следующая идея состоит в том, чтобы из точки А идти в том направлении, которое требует минимальных затрат на первом шаге (первый ход), не думая о затратах на последующих шагах, и так в каждой точке. То есть рассматривать только затраты на данном шаге и выбирать тот переход, для которого на данном шаге затраты минимальны. Легко убедиться в ошибочности этой идеи даже при m = n = 1 (рис. 2.2).

Действительно, если первый шаг выбрать по вертикали в точку С (затраты 2 против 7), то в итоге после второго шага получим суммарные затраты, равные 12, а при выборе на первом шаге «неоптимального» решения (точка D) суммарные затраты равны всего лишь 8.

Рис. 2.2.

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

Поиск оптимального пути можно рассматривать как многошаговый процесс. На первом шаге находимся в точке А и имеем две возможности: пойти вверх или направо. Мы убедились на рассмотренном примере (рис. 2.2), что сделать выбор нельзя, так как нужно учитывать последствия этого выбора. При любом выборе попадем мы в точку (0, 1) или (1, 0), встанет та же задача выбора из двух возможностей и опять выбор сделать нельзя и т. д. Однако существуют точки, находясь в которых мы не имеем выбора. Эти точки С и D находятся в одном шаге от последней точки В и имеют координаты (m, n- 1) и (т- 1, п) (рис. 2.3).

Рис. 2.3.

Для каждой из этих точек запомним затраты на оставшийся до точки В путь и рассмотрим предпоследний шаг. В двух шагах от финиша мы можем быть в точках Е, F или G. В точках Е и G выбора нет, и мы просто запомним для каждой из них суммарные затраты на весь оставшийся путь. На рис. 2.3 это 10 для точки Е и 8 для точки G. А что делать, если мы в двух шагах от финиша окажемся в точке F? Ответ кажется простым: надо идти в точку С, а не в точку D, так как несмотря на то, что на предпоследнем шаге затраты больше (2 против 1), но с учетом затрат на оставшийся путь (4 против 7) суммарные затраты на путь до точки В окажутся меньше (6 против 8). Конечно, из точки F надо идти в точку С, но при одном непременном условии: ничто не может помешать нам это сделать, нет никакой связи с тем, как мы попали в данную точку, или, как говорят, нет «предыстории». В нашей задаче такой связи нет, но в более сложных задачах она вполне возможна. Например, могло быть задано дополнительное условие: суммарное количество изменений направления (поворотов) не больше заданного числа. Тогда мы, во-первых, должны знать, сколько было сделано поворотов до попадания в точку F и каким образом (по горизонтали или по вертикали) мы попали в эту точку, то есть должны знать предысторию. Может оказаться, что мы попали в точку F по горизонтали и уже исчерпали заданный «лимит» поворотов, тогда переход из точки F в точку С просто невозможен, так как это уже лишний поворот. Получается, что сделать оптимальный выбор в точке F нам может помешать предыстория.

Продолжим поиск оптимального пути в нашей задаче, в которой таких осложнений нет и предыстория не имеет значения. В точке F мы запомним затраты на весь оставшийся путь при условии, что выбран оптимальный вариант: переход в точку С. Сделав еще шаг назад, то есть оказавшись за три шага до финиша, мы увидим, что ситуация полностью аналогична предыдущей. Выбора или нет (точки на крайней верхней или крайней правой стороне сетки), или есть две возможности, но для каждой из них уже известны последствия выбора. Так, оказавшись в точке М, мы выберем не точку F, для которой затраты до конца пути равны 6, а казавшуюся бесперспективной точку Е, для которой эти затраты равны 10, но суммарные затраты на весь оставшийся путь меньше (13 против 14). При этом выборе мы решаем совсем простую задачу: суммируем затраты на каждый из возможных переходов на данном шаге (в точку Е или в точку F) с уже известными затратами на дальнейший путь по оптимальному для выбранной точки варианту. Поступая аналогичным образом, мы рано или поздно в своем обратном движении придем в начальную точку А (рис. 2.4). Но при этом уже будут известны последствия для каждого из вариантов выбора (пойти по вертикали в точку К или по горизонтали в точку L), так как для каждой из них уже вычислены и записаны затраты на весь оставшийся путь до точки В. Это ситуация аналогична той, что представлена на рис. 2.4.

Теперь ничто не мешает нам сделать выбор, куда идти из точки А. Просуммируем затраты из А в К с тем, что записано для точки К на весь оставшийся путь от К до В. Затем просуммируем затраты из А в L с тем, что записано для L на путь из Lb В, выберем наименьшую из сумм, которая и будет равна суммарным затратам по оптимальному пути. В примере на рис. 2.4 получаем для точки

Рис. 2.4.

К число 99, а для точки L 100, и, следовательно, теперь ясно, что идти надо в точку К. Но нам нужны не только эти минимальные из всех возможных затраты, но и сам оптимальный путь. Пока мы знаем, куда идти из точки А на первом шаге. А дальше? Дальше знаем только затраты на весь оставшийся путь. Чтобы не оказаться в такой ситуации неопределенности, при записи затрат на оставшийся путь в каждой из промежуточных точек (С, D, Е, F, G, М и т. д., рис. 2.3) нужно записывать и сделанный выбор: куда идти из этих точек. Если это сделано, то при выборе, куда идти из точки А: в точку К или L, в любой из них уже будет записано, куда идти дальше (по вертикали или по горизонтали, то есть 1 или 0) и т. д. Обратным разворотом мы дойдем до точки В и восстановим оптимальный путь.

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

В данной задаче мы исследовали многошаговый процесс от последнего шага к первому. Но ничто не мешает развернуть его и рассмотреть шаги в прямом направлении, то есть от точки А к точке В, ничего не меняя в методе Р. Веллмана по существу.

Применительно к рассматриваемой нами задаче поиска оптимального пути на двумерной сетке алгоритм примет следующий вид.

• 1. Из точки А делаем шаг в каждом из возможных направлений, запоминаем в точках К и L затраты и направление, по которому пришли в эту точку (0 по горизонтали и 1 - по вертикали). Соответственно для точки К запомним 12 и 1, а для точки L 5 и 0.
• 2. На втором и всех последующих шагах, кроме последнего, если в точку ведет один путь (шаги по левой и нижней сторонам сетки), то просто запоминаем суммарные затраты на путь от начала и направление, откуда пришли, а если в точке сходятся два варианта (на рис. 2.4 это точка Н, а на рис. 2.3 точки М, F и др.), то сравниваем две возможности: придти в эту точку по горизонтали или по вертикали. Для каждой из них вычисляем суммарные затраты на путь от начала до данной точки, выбираем тот вариант, для которого эти суммарные затраты минимальны, запоминаем их и соответствующее им направление. Таким образом, происходит отбраковка вариантов, сходящихся в точке: вариант с наибольшими затратами отбрасывается и все его продолжения далее не анализируются. Естественно, это можно сделать только в таких простых задачах «без предыстории», как наша, когда совпадают множества возможных продолжений сравниваемых вариантов и отбраковка варианта никак не влияет на возможности выбора в дальнейшем.
• 3. На последнем шаге в точку В ведут два направления, и по каждому из них все известно: для каждой точки (на рис. 2.3 это точки С и D) записаны затраты на весь путь от начала и направление, откуда пришли в эту точку. Снова суммируем затраты по вариантам, выбираем наименьшие, а затем обратным разворотом восстанавливаем оптимальный путь.

В реальных задачах многоэтапные процессы могут иметь не один исход (точку финиша) или начало (точку старта), а несколько. Однако это не мешает применить метод Р. Веллмана.

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

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

Наиболее приемлемый вариант решения, которое принимается на управленческом уровне относительно любого вопроса, принято считать оптимальным, а сам процесс его поиска - оптимизацией.

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

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

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

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

Сущность методов исследования операций

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

Перечень вопросов, которые играют существенную роль для непосредственных руководителей производства и которые разрешаются в ходе использования рассматриваемых методов:

• степень обоснованности выбранных вариантов решений;
• насколько они лучше альтернативных;
• степень учета определяющих факторов;
• каков критерий оптимальности выбранных решений.

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

Методы экспертных оценок

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

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

Рассматриваемые методы оптимизации ряда управленческих решений (экспертных оценок) эффективны в решении нижеперечисленных управленческих задач в сфере производства:

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

И это лишь некоторые методы оптимизации ряда управленческих решений (экспертной оценки).

Классификация рассматриваемых методов

Методы решения задач оптимизации, исходя из числа параметров, можно подразделить на:

• Методы оптимизации одномерной.
• Методы оптимизации многомерной.

Их еще называют "численные методы оптимизации". Если быть точным, это алгоритмы ее поиска.

В рамках применения производных методы бывают:

• прямые методы оптимизации (нулевого порядка);
• градиентные методы (1-го порядка);
• методы 2-го порядка и др.

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

Методы одномерной оптимизации

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

Существуют следующие методы решения задач оптимизации (одномерной):

• метод Фибоначчи;
• дихотомии;
• золотого сечения;
• удвоения шага.

Метод Фибоначчи

Для начала необходимо установить координаты т. x на промежутке в качестве числа, равного отношению разницы (x - a) к разнице (b - a). Следовательно, a имеет относительно промежутка координату 0, а b - 1, средняя точка - ½.

Если допустить, что F0 и F1 между собой равны и принимают значение 1, F2 будет равно 2, F3 - 3, …, то Fn = Fn-1 + Fn-2. Итак, Fn - числа Фибоначчи, а поиск Фибоначчи - это оптимальная стратегия так называемого последовательного поиска максимума ввиду того, что она довольно тесно связана с ними.

В рамках оптимальной стратегии принято выбирать xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. При любом из двух интервалов ( либо ), каждый из которых может выступать в качестве суженного интервала неопределенности, точка (унаследованная) относительно нового интервала будет иметь либо координаты , либо . Далее, в качестве xn - 2 принимается точка, которая имеет относительно нового промежутка одну из представленных координат. Если использовать F(xn - 2), значение функции, которое унаследовано от прежнего промежутка, становится возможным сокращение интервала неопределенности и передача в наследство одного значения функции.

На финишном шаге получится прейти к такому интервалу неопределенности, как , при этом средняя точка унаследована от предыдущего шага. В качестве x1 устанавливается точка, которая имеет относительную координату ½+ε, а окончательный интервал неопределенности будет или [½, 1] по отношению к .

На 1-м шаге длина данного интервала сократилась до Fn-1: Fn (с единицы). На финишных шагах сокращение длин соответствующих интервалов представляется числами Fn-2: Fn-1, Fn-3: Fn-2, …, F2: F3, F1: F2 (1 + 2ε). Итак, длина такого интервала, как окончательный вариант примет значение (1 + 2ε) : Fn.

Если пренебречь ε, то асимптотически 1: Fn будет равно rn, при этом n→∞, а r = (√5 - 1) : 2, что приблизительно равно 0,6180.

Стоит отметить, что асимптотически для значительных n каждый последующий шаг поиска Фибоначчи существенно сужает рассматриваемый интервал с вышеуказанном коэффициентом. Данный результат требуется сравнить с 0,5 (коэффициент сужения интервала неопределенности в рамках метода бисекции для поиска нуля функции).

Метод дихотомии

Если представить некую целевую функцию, то для начала потребуется найти ее экстремум на промежутке (a; b). Для этого ось абсцисс делится на четыре эквивалентные части, затем необходимо определить значение рассматриваемой функции в 5 точках. Далее выбирается минимум среди них. Экстремум функции должен лежать в пределах промежутка (a"; b"), который прилегает к точке минимума. Границы поиска сужаются в 2 раза. А если минимум расположен в т. a либо b, то он сужается во все четыре раза. Новый интервал также разделяется на четыре равных отрезка. В связи с тем, что значения данной функции в трех точках были определены на предыдущем этапе, далее требуется вычислить целевую функцию в двух точках.

Метод золотого сечения

Для существенных значений n координаты таких точек, как xn и xn-1 приближены к 1 - r, равное 0,3820, а r ≈ 0,6180. Толчок с данных значений весьма близок к искомой оптимальной стратегии.

Если предположить, что F(0,3820) > F(0,6180), то тогда очерчивается интервал . Однако ввиду того, что 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, то в данной точке F уже известна. Следовательно, на каждом этапе, начиная со 2-го, необходимо только одно вычисление целевой функции, при этом каждый шаг сокращает длину рассматриваемого интервала с коэффициентом 0,6180.

В отличие от поиска Фибоначчи, в данном методе не требуется фиксация числа n еще до начала поиска.

«Золотое сечение» участка (a; b) - сечение, при котором отношение его r длины к более крупной части (a; c) идентично отношению большей части r к меньшей, то есть (a; с) к (c; b). Нетрудно догадаться, что r определяется по вышерассмотренной формуле. Следовательно, при существенных n метод Фибоначчи переходит в данный.

Метод удвоения шага

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

Сначала определяем начальную координату M0 функции F(M), минимальное значение шага h0, направление поиска. Затем определяем функцию в т. M0. Далее совершаем шаг и находим значение данной функции в данной точке.

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

Методы многомерной оптимизации

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

Группу методов 1-го порядка еще называют градиентными, потому что для установления направления поиска применяют градиент данной функции - вектор, составляющими которого выступают частные производные минимизированной функции по соответствующим оптимизированным параметрам.

В группе методов 2-го порядка применяются 2 производные (их использование достаточно ограничено ввиду наличия трудностей в их вычислении).

Перечень методов безусловной оптимизации

При использовании многомерного поиска без применения производных методы безусловной оптимизации следующие:

• Хука и Дживса (осуществление 2 видов поиска - по образцу и исследующий);
• минимизации по правильному симплексу (поиск точки минимума соответствующей функции посредством сравнения на каждой отдельной итерации ее значений в вершинах симплекса);
• циклического координатного спуска (использование в качестве ориентиров поиска координатных векторов);
• Розенброка (основан на применении одномерной минимизации);
• минимизации по деформированному симплексу (модификация метода минимизации по правильному симплексу: добавление процедуры сжатия, растяжения).

В ситуации использования производных в процессе многомерного поиска выделяют метод наискорейшего спуска (наиболее фундаментальная процедура минимизации дифференцируемой функции с несколькими переменными).

Также выделяют еще такие методы, которые используют сопряженные направления (Метод Дэвидона-Флетчера-Пауэлла). Его суть - преставление направлений поиска как Dj*grad(f(y)).

Классификация математических методов оптимизации

Условно, исходя из размерности функций (целевых), они бывают:

• с 1 переменной;
• многомерные.

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

По критерию применения производных математические методы оптимизации подразделяются на:

• методы вычисления 1 производной целевой функции;
• многомерные (1-я производная-векторная величина-градиент).

Исходя из эффективности вычисления, существуют:

• методы быстрого вычисления экстремума;
• упрощенного вычисления.

Это условная классификация рассматриваемых методов.

Оптимизация бизнес-процессов

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

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

Налоговая оптимизация: методы

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

Общие методы налоговой оптимизации следующие:

• проработка учетной политики компании с максимально возможным применением предоставленных российским законодательством возможностей (порядок списания МБП, выбор метода расчета выручки от реализации товара и др.);
• оптимизация посредством договора (заключение льготированных сделок, четкое и грамотное использование формулировок и т. п.);
• применение разного рода льгот, налоговых освобождений.

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

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

В зависимости от природы процесса, от характера ма­тематической модели, от наличия информации о процес­се, от постановки задачи применяются различные ме­тоды оптимизации процессов (табл. 22.1).

При решении конкретной задачи исследователь дол­жен выбрать тот метод оптимизации, который при на­именьших затратах на вычисления давал бы наибольший объем информации об искомом процессе.

Таблица 22.1

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

Эти методы применяются для решения задач с из­вестным аналитическим выражением критерия оптималь­ности, Приравнивая нулю производные и решая конеч­ную систему уравнений, определяют экстремальные значения параметра оптимизации.

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

Методы вариационного исчисления обычно применяют для решения задач с критерием оптимальности в виде функционалов. Вариационными методами решение зада­чи сводится к интегрированию системы дифферен­циальных уравнений Эйлера второго порядка с гра­ничными условиями. Число уравнений системы равно числу неизвестных функций.

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

Принцип максимума Понтрягина применяется для оптимизации процессов, описываемых системами диффе­ренциальных уравнений. Оптимальное решение находит­ся путем интегрирования системы дифференциальных уравнений процесса и системы вспомогательных функ­ций с ограничением на обоих концах интервала инте­грирования.

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

Методы нелинейного (динамического) программирова­ния применяют для решения задач оптимизации с нели­нейными функциями параметра оптимизации с огра­ничениями и без ограничений на независимые пере­менные.

Для оптимизации стохастических процес­сов используются экспериментально-статистические ме­тоды. Различают пассивный и активный эксперимент. Пассивный эксперимент, или, как его часто назьюают, пас­сивное наблюдение, использует методы математической статистики для обработки информации с целью изучения закономерностей технологического процесса. При этом сбор исходных данных проводится на действующем объекте без введения в процесс искусственных изменений. Обработка данных с целью получения математической модели процесса проводится в основном методами классического регрессионного и корреляционного методов ана­лиза.

Активный эксперимент основан на применении плани­рования эксперимента. Планирование эксперимента - это проведение эксперимента по заранее составленному пла­ну (матрице), обладающему оптимальными свойствами. При планировании учитываются одновременно все фак­торы, влияющие на процесс, что позволяет выявить сразу и силу взаимодействия факторов, и резко сократить об­щее число опытов для определения оптимальных параме­тров. Как в пассивном, так и в активном эксперименте математической моделью является функция отклика, связывающая параметр оптимизации с факторами, влияющими на процесс.