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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Область возможных состояний системы - это совокупность состояний, в которые может переходить система. Например, в случае а - это ось ОЛ" или ее участок, а управление - это закон движения точки из состояния х° -» х к.

Рис. 4.5.

Постановка задачи

Пусть состояние некоторого объекта описывается вектором фазового пространства х - (х, х 2 ,..., х я) е R„. Будем считать, что процесс является /V-шаговым, т. е. его эволюция происходит за N шагов по схеме

Переход между состояниями на к -м шаге осуществляется в соответствии с уравнением состояния

где й к е R"" - ш-мерный вектор управления на к -м шаге; J" k (x,Ti) - «-мерная векторная функция аргументов х , й.

Распишем компоненты вектора х к - /Дх*~", х*“",х к ~", и к, и к, н*). Таким образом, предполагается, что в результате к-vo шага система переходит в состояние х к, которое определяется только начальным состоянием этого шага х к ~" и выбранным на нем вектором управления й к и не зависит от предыстории процесса х°, х 1П, х (*~ 2) , н"’,..., н (*~ |) .

Показателем эффективности к -го шага является заданная числовая характеристика (целевая функция) этого шага:

А эффективность всего процесса складывается из этапных целевых функций

На фазовые траектории х и управления й наложены ограничения:

Множества Х к а U к заданы в пространствах R", R"".

Кроме того, заданы начальные и конечные условия:

Часто множества Х 0 и X N содержат по одной точке, определяющей начало и конец фазовой траектории.

Общую задачу многошаговой оптимизации можно записать следующим образом:

Требуется среди всех управлений ueU выбрать такое й" =(«*", м’ Л), для которого целевая функция (4.18) принимает экстремальное значение (минимальное или максимальное).

Пример 1. Сформулировать следующую оптимизационную задачу в виде многошаговой задачи оптимизации.

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

A V = F(y,z),

где у - масса, разгоняемая этой ступенью; z - масса самой ступени.

Найти такое распределение массы ракеты (М) между ее ступенями, при котором конечная скорость ракеты максимальна.

Пусть й к (k = ,N ) - масса к -й ступени, начиная от межпланетной станции, т. е. на старте работает ступень массой г/ Л, в конце - и".

Обозначим х к (к = О...Л0 сумму масс межпланетной станции и к ступеней, примыкающих к ней.

Теория многошаговых оптимизационных задач разработана в 50-х годах американским математиком Р. Веллманом. Метод решения такой задачи носит название метода динамического протраммирования и основан он на принципе оптимальности Веллмана.

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

Чтобы спланировать к -й шаг, надо знать состояние системы на (/: - 1) шаге. Если состояние на (к - 1) шаге неизвестно, то делают различные предположения о возможных состояниях системы на этом шаге. Для каждого предположения выбирают оптимальное управление на последнем к -м шаге. Такое оптимальное управление называют условно оптимальным.

Рассмотрим ^-шаговый процесс (рис. 4.6). Сделаем ряд предположений о возможных состояниях процесса на (к - 1) шаге. Обозначим эти состояния S k _i , S k _ ] 2 ,..., S k ^ r . На последнем найдем для каждого из этих состояний условно оптимальное управление и к, (x t _,), и к 2 (х А._,),..., и к г (х 4 _, г).

Таким образом, к -й шаг спланирован. Действительно, какое бы состояние система ни принимала на (к - 1) шаге, уже известно как следует поступить на &-м.

Аналогично поступаем на (к - 1) шаге, только условно оптимальные управления необходимо выбирать, учитывая уже выбранные условно-оптимальные на к -м шаге. В итоге, выполнив все переходы, получим координату х°.

Для первого шага предположений не делаем, т. к. значение х° задано, далее находим оптимальные управления, учитывая все уже найденные. Проходя от х°к х*, получаем искомое оптимальное управление для всего процесса. Используя принцип оптимальности, найдем необходимые условия, которым должна удовлетворять оптимально управляемая последовательность и,..., м v _,.

Рис. 4.6.

Рассмотрим конечный участок траектории - интервал . И допустим, что для интервалов найдены оптимальные управления и оптимальная траектория, включая х к. Остается найти управление н А,...,м у на конечном участке. Из принципа оптимальности следует, что {w A ,...,w v } определяется только состоянием х к _ { и целью поиска экстремума, которая для [ к , N] имеет вид

при х-х ч, й = и ч целевая функция Z k имеет оптимальное значение (максимум или минимум). Обозначим его

Аналогично

Из принципа оптимальности можно записать следующие рекуррентные выражения:

Соотношения (4.19)-(4.20) позволяют последовательно найти функции Веллмана.

В„ (х Л -|), B N _ { {x N - 2),..., 5, (х°) - уравнения Веллмана.

Находя В к (х к ~"), к = N, N -мы одновременно находим управления ы,*(дг*’ 1), которые называются условно-оптимальными управлениями, а процесс их нахождения - условной оптимизацией.

Управление м.*(х*~"), найденное из уравнения (4.20), удовлетворяет принципу оптимальности: т. е. в зависимости от начального состояния х к ~" управления и к учитывает оптимизацию не только к-го шага, но и следующих за ним (N - к) шагов.

Итак, в результате условной оптимизации находят В к (х к ~") и и к (х к ~"), к = N, N- 1,..., 1. Теперь можно осуществить безусловную оптимизацию задачи (4.18), т. е. найти искомые оптимальные управления и = (ии ?) и оптимальную фазовую траекторию х = (х,°,..., х? ).

Т. к. значение B t (x°) равно оптимальному значению целевой функции всех N шагов, то

если х 0 - первая точка траектории, то х,° = х°.

Алгоритм метода динамического программирования

Этан I. Условная оптимизация.

Шаг 1. Находим условно-оптимальные управления г/*(х ЛЧ) и функцию Веллмана B N (x N ~") в соответствии с соотношением (4.19).

Шаг 2. Находим ^"""(х* -2) и /? v _,(x v ~ 2).

Шаг N. Находим м"(х°)и 5,(х°).

Этап II. Безусловная оптимизация.

Шаг 0. Находим х.° в соответствии с (4.21).

Шаг 1. Находим и 1 . и х по формулам (4.22).

Шаг N. Находим w. v и x. v .

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

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

Этап I. Условная оптимизация.

Найдем уравнения Веллмана по формуле (4.19).

Шаг 1. Я,(х 2) = шах

Диапазон и 3 найден из следующих соображений: так как

Учитывая, что х г е, получаем диапазон изменения м 3:

Функция - при всех значениях х является возрастающей аргу-

мента и поэтому ее максимум

Шаг 2. С учетом формулы (4.20)

Находим стационарную точку из условия -^-:

ШагЗ. B,(x°)= max (2 , -1 + -).

Введение

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

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

Целью выполнения данной работы является описание алгоритма культурного обмена и проведение экспериментального исследования средней трудоемкости алгоритма случайного поиска версии 3.20.

К работе прилагаются три приложения А, Б и В. В них приведены данные эксперимента в виде таблиц, а также графики зависимости функции качества(Fэ) от генотипа(N).

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

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

В пункте 3 - проведено экспериментальное исследование средней трудоемкости алгоритма.

Постановка задачи

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

Способ кодирования решения в генотипе: двоичное представление параметра, точность представления параметра (аргумента) функции принимается, если не задана для функции специально, равной = 0.01;

Длина генотипа: определяется способом кодирования решения.

Размер популяции: 120 индивидуумов;

Доля родителей от размера популяции: 1.0, т.е. количество родителей, участвующих в кроссовере равно 120.

Кроссовер: равномерно распределенный 2-х точечный. Т.е. хромосома разбивается в двух точках, причем положения точек разбиения не фиксировано, а равномерно распределены по генотипу.

Мутация: применяется к каждому новому индивидууму, к каждому гену.

Отбор в следующее поколение: элитный отбор.

Необходимо провести экспериментальное исследование средней трудоемкости алгоритма

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

Описание алгоритма оптимизации

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

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

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

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

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

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

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

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

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

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

Признание Функция культуры Алгоритм - все люди используются для обновления ограничений знаний культурныхх алгоритмов. Похожие рейтинг 20% (видный человек) являются использование используются методы обновления от нормативного знания использовать помехи для корректировки правил активных клеток. Недостатки Сообщение осуществимо протокола и невозможно Алгоритм полу-возможные общие черты Подходит Проблемы адаптации иерархическая структура, основанная на вышеупомянутое сообщение Протоколы сплит полу-возможно клеток на более мелкие ячейки, когда число вложении Другие лица становится слишком высокой Будущие направления слиянии невозможно детей в первоначальном родителей;

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

Население культурных моделей, используемых алгоритмов - генетических алгоритмов. Похожие методы англ. Недостатки Сообщение Эволюция стратегий (Робот играет в футбол) и Протокол Алгоритм Memetic моделей (Развитие сельского хозяйства) Общие черты агент на основе моделирования (Эволюция состояния окружающей среды Подходит Проблемы коммуникации воздействия)

Вариации культуры Алгоритм - генетических алгоритмов. Похожие методы англ. и космической руководствуясь генетические алгоритмы (VGA)

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

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

Рисунок 1.Алгоритм культурного обмена.

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

Данный раздел включает в себя следующие пункты.

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

Обзор методов оптимизации

Методы оптимизации используются для того, что бы найти некий набор параметров х={x 1 , х 2 , … х n } которые в некотором смысле могут быть определены как оптимальными. В узком смысле это может быть поиск минимума или максимума некой функции как параметра от х={x 1 , х 2 , … х n }. В более широком смысле эта формулировка представляет собой минимизацию или максимизацию целевой функции, f(x) , при наличии ограничений в форме

Равенств

или неравенств

а также и/или ограничений,

на пределы изменения параметров.

Общая формулировка (GP) задачи параметрической оптимизации представляется следующим образом: следует найти вектор х={x 1 , х 2 , … х n }, обеспечивающий

при условии

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

Эффективность и точность решений данной задачи зависит как от числа параметров и ограничений, так и от вида целевой функции. При линейных ограничениях и линейной целевой функции приведенная задача оптимизации называется задачей линейного программирования (LP). Задача квадратичного программирования (QP) представляет собой минимизацию или максимизацию квадратичной (по аргументам) целевой функции при наличии ограничений линейного вида. Постановки задач типа (LP) и (QP) представляют собой достаточно реалистически достижимыми задачами. Более сложной является обобщающая задача нелинейного программирования (NP), когда целевая функция и ограничения представляют собой некие нелинейные функции от исходных аргументов. (NP), в общем случае, решается с помощью итерационных методов с коррекцией направления поиска на каждой итерации. Такая постановка задачи обычно решается через решение отдельных промежуточных задач (LP) и (QP)/

Оптимизация без наличия ограничений

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

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

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

Минимальное значение данной функции, как нетрудно видеть, равно нулю при . Графическое представление изолиний данной функции приведено на Рис. 3, где также представлено траектория продвижения по направлению к точке минимума согласно метолу наискорейшего спуска из начальной точки [-1.9,2].

Рис. 3-1: Метод наискорейшего спуска для функции Розенброка (уравнение 3-2).

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