Тема 13. Операционный анализ. Одномерные задачи оптимизации. Линейное программирование. Математическое программирование. Динамическое программирование. Неопределённость целей.

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

С математической точки зрения одномерная задача оптимизации формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции f(x), заданной на множестве X, т.е. определить значение переменной x X, прикотором она принимает своё экстремальное значение. Такие задачи в аналитической формулировке изучаются в школьном курсе математики и на первых курсах вузов. Однако в реальных условиях вид функции f(x) зачастую неизвестен, значения функции могут быть известны лишь в нескольких точках или значения функции находятся в результате сложных вычислений по некоторому алгоритму. Таким образом, в реальных условиях постановку одномерной задачи оптимизации можно определить следующим образом: по известным значениям непрерывной функции f(x) в некотором конечном числе точек отрезка [a,b] нужно приближённо найти её наименьшее (или наибольшее) значение на этом отрезке.

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

f =

при условии, что:

(i = 1, 2,…,m);

>= 0 (j = 1, 2,…,n);

>= 0 (i = 1, 2,…,m).

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

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

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

f(x₁, x₂,… x_n) = ,

причём все ограничения по-прежнему линейны и сохраняются условия неотрицательности.

Особенность квадратичной целевой функции состоит в том, что она определённо обладает единственным минимумом или максимумом.

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

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

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

Тема 14.Численные методы решения задач операционного анализа. Метод случайного поиска с нелинейной тактикой. Метод случайного поиска с линейной тактикой. Эволюционный бионический алгоритм. Генетический алгоритм.

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

Рис. 1.1. Случайный поиск с нелинейной тактикой

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

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

Суть метода: вероятность удачи в ранее удачном шаге больше, чем в случайном, т.е. целесообразно повторять удачные шаги, а при неудаче делать новый случайный шаг. Линейность такого алгоритма заключается в линейном повторении удачного шага (рис. 1.2).

Рис. 1.2. Случайный поиск с линейной тактикой

Идея эволюционного метода базируется на том, что на начальном этапе имеем N произвольных точек, моделирующих отдельные особи. Среди N точек выбираем лучшую точку N^*. Степень приспособленности каждой из точек определяется значением функции Y(x): чем меньше значение функции, тем больше приспособлена особь и имеет больше шансов на выживание. N^* лучших точек дают потомство, т.е. генерируются точки, отличающиеся от родителя случайным образом:

где K_j – количество точек, сгенерированных вокруг, j-ой точки;

ξ_ij – случайные отклонения, моделирующие отличие i-го потомка от j-го родителя в силу случайных мутаций (скачкообразное изменение или появления нового признака у потомка).

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

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

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

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

Основная идея ГА состоит в создании популяции особей (индивидов), каждая из которых представляется в виде хромосомы. Любая хромосома есть возможное решение рассматриваемой оптимизационной задачи. Для поиска лучших решений необходимо только значение целевой функции, или функции приспособленности. Значение функции приспособленности особи показывает, насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи. Хромосома состоит из конечного числа генов, представляя генотип объекта, т.е. совокупность его наследственных признаков. Процесс эволюционного поиска ведется только на уровне генотипа. К популяции применяются основные биологические операторы. В процессе эволюции действует известный принцип "выживает сильнейший". Популяция постоянно обновляется при помощи генерации новых особей и уничтожения старых, и каждая новая популяция становится лучше и зависит только от предыдущей.