Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ShPORY_BD.docx
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

Тема 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(x1, x2,… xn) = ,

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

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

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

Динамическое программирование

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

Пусть мы располагаем некоторым ресурсом Z в условных единицах измерения. В начальный год мы продадим x единиц этого ресурса за f(x) денежных единиц. Оставшуюся часть y пустим в оборот, так что через год будем иметь cy единиц ресурса (c>1). Мы хотим, чтобы через N лет весь ресурс был продан. Задача состоит в следующем, какое количество ресурса надо продавать ежегодно, чтобы полный доход за N-летний период был максимальным. Этот пример является иллюстрацией одной из основных экономических проблем, какую часть наших доходов следует сохранять, а не тратить.

Год

Продано

Оставлено

Имеется на следующий год

1

x1

y1

c y1

2

x2

y2

c y2

…

…

…

…

N-1

xN-1

yN-1

c yN-1

N

xN

0

0

Можно составить следующую систему уравнений:

z = x1 + y1

cy1 = x2 + y2

cy2 = x3 + y3

…………….

c yN-2 = xN-1 + yN-1

cyN-1 = xN

Исключив из этих уравнений y1, y2, …, yN-1 , получим

zсN-1 = xN +cxN-1+…+cN-1x1

Полный доход за N лет составит

P = f(x1)+ f(x2)+…+ f(xN)

Какова должна быть политика ежегодных продаж за N-летний период, которая максимизировала бы P при ограничении zсN-1 = xN +cxN-1+…+cN-1x1 и условиях неотрицательности xi 0 для i = 1,2,…, N ?

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

Общая постановка задачи динамического программирования

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

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

- состояние системы после i-ого шага;

- начальное состояние системы (может быть элементом множества начальных состояний 0;

- конечное состояние системы (может быть элементом множества конечных состояний n;

= ( , ,…, ) - вектор управления на i-ом шаге может принимать любые значения (числа, векторы, функции и т.д.);

Под действием вектора управлений  система переходит из  в ; вектор переводит в и т.д. С переходом из  в связан выигрыш, определяемый критериемW.

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

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

Задачи динамического программирования решаются методом обратной прогонки и методом прямой прогонки.

Процесс нахождения решения разбивается да две стадии:

  • условная оптимизация;

  • безусловная оптимизация.

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

На стадии безусловной оптимизации строится оптимальное решение исходной задачи и определяется max (min) посредством прямой прогонки: от последнего шага к первому.

Примеры основных промышленных применений метода динамического программирования

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

Неопределённость целей

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

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

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

(1.1)

при x є X, где

X – множество допустимых значений переменных х;

n – число целевых функций (критериев);

Fi – значение i-го критерия (целевой функции);

“max” – означает, что данный критерий нужно максимизировать.

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

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

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

Численные методы решения задач операционного анализа

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

Метод случайного поиска с нелинейной тактикой

Данный алгоритм моделирует метод проб и ошибок и строится из двух операторов. Первый оператор случайного шага. Второй оператор – возврат.

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

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

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

Метод случайного поиска с линейной тактикой

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

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

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

Метод случайного поиска с линейной тактикой с предпочтением по расстоянию

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

Эволюционный бионический алгоритм

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

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

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

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

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

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

Генетический алгоритм

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

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

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

Репродукция состоит из четырех шагов:

селекции

скрещивание

мутация

инверсия

Скрещивание является наиболее важным генетическим оператором. Оно генерирует новую хромосому, объединяя генетический материал двух родительских. Существует несколько вариантов скрещивания. Наиболее простым_является_одноточечное_скрещивание. В этом варианте просто берутся две хромосомы, и “перерезаются” в случайно выбранной точке (рисунок2.5.1). Результирующая хромосома получается из начала одной и конца другой родительских хромосом.

Рисунок 2.5.1 – Одноточечное скрещивание

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

Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации ГА обходятся без данного генетического оператора.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]