1.1. Постановка задачи
Как пра вило , большинст во реальных инженерных зада ч содержит в том или ином виде неопре деленность . Можно даже утверждать , что решение задач с учетом разного вида неопределенн остей является общим случаем , а принятие решений без их у чета - частным . Однако , из-за концептуальных и м етодических т рудностей в настоящее время не существует единого методологического подхода к решению таких задач . Тем не менее , накоплено дос таточно большое число методов формализации по становки и принятия решений с учетом неоп ределенностей . При использован и и этих методов следует иметь в виду , что все они носят рекомендательный характер и выбо р окончательного решения всегда остается за человеком (ЛПР ).
Как уже указывалось , при решении конкр етных задач с учетом неопределенностей инжене р сталкивается с разными их типами . В исследовании операций принято различать три типа неопределенностей :
· неопределенность це лей ;
· неопределенность наших знаний об окр ужающей обстановке и действующих в данном явлении факторах (неопределенность природы );
· неопределенность дей ствий активного или пассивного партнера или противника .
В приведенной выше классификации тип неопределенностей рассматривается с позици й того или иного элемента математической модели . Так , например , неопределенность целей о тражается при постановке задачи на выбор е либо отдельных критериев , либо всего век тора полезного эффекта.
С другой стороны , два другие типа н еопределенностей влияют , в основном , на состав ление целевой функции уравнений ограничений и метода принятия решения . Конечно , приведенное выше утве рждение является достаточно условным , как , впрочем , и любая классификация . Мы приводим его лишь с целью выделить еще некоторые особенности неопределенностей , которые надо иметь в виду в процессе принятия решений.
Дело в том , что кроме рассмотренной выше кл ассификации неопределенностей надо учитывать их тип (или "род ") с точки зрения отношения к случайности .
По этому признаку можно различать стохастическую (вероятностн ую ) неопределенность , когда неизвестные факторы статистически устойчивы и поэтому представл яют собой обы чные объекты теории вероятностей - случайные в еличины (или случайные функции , события и т.д .). При этом должны быть известны или определены при постановке задачи все необх одимые статистический характеристики (законы расп ределения и их парамет р ы ).
Примером таких задач могут быть , в частности , система технического обслуживания и ремонта любого вида техники , система органи зации рубок ухода и т.д.
Другим крайним случаем может быть неоп ределенность нестохастического вида (по выражению Е.С.Вентцель - "дурная неопределенность "), при которой ни каких предположений о стохастической устойчивост и не существует . Наконец , можно говорить о промежуточном типе неопределенности , когда р ешение принимается на основании каких-либо ги потез о законах распределения слу ч айных величин . При этом ЛПР должен иметь в виду опасность несовпадения его резуль татов с реальными условиями . Эта опасность несовпадения формализуется с помощью коэффицие нтов риска .
Рассмотрим примеры и методы принятия р ешений с учетом указанных выше типов неопределенностей.
Пример 1.1. Лесопосадки
Допустим , что ставится задача наиболее эффективного выращивания саженцев при лесопосадках путем внесения в почву опреде ленного количества удобрений (или создания на иболее эффективной системы гидромелиорации ). При этом , как правило , используются стратеги и , максимизирующие доход (например , прирост дре весины ), или минимизирующие расход (стоимость у добрений или затрат на мелиорацию ). При эт ом , очевидно , что обе цели противоречат др уг другу и с точки зрения строго нау ч ной постановки задача не имеет решения , ибо минимум затрат - нуль , а с нулевыми затратами добиться какого-либо эффекта теоретически невозможно.
Пример 1.2. Проектирование лесных м ашин
Другим очень распространенным пр имером является создание любой машины . В частности , при создании лесной машины ставятся задачи получения максимальной произво дительности , минимального влияния на окружающую среду , высокой надежности и минимальной себ естоимости . Противоречивость целей здесь налицо и реальная конструкция всегда б у дет каким-то компромиссом , достигаемым путем о пределенных уступок по каким-либо качествам . С обственно , в получении таких компромиссных ре шений и заключается основная проблема.
Таким образом , неопределенность целей треб ует привлечения каких-либо гипотез , по могаю щих получению однозначных решений . В данном случае учет фактора неопределенности цели , как уже указывалось , приводит к необходимости рассмотрения другой проблемы , которая формул ируется в виде проблемы принятия оптимальных многоцелевых решений , котор а я подр обно рассматривается авторами в главе 7. В этой же главе мы рассмотрим указанные выш е другие типы неопределенностей.
1. Принятие решений в условиях риска
Как указывалось выше , с точки зрения знаний об исходных данных в п роцессе принятия решений можно представить два крайних случая : определенность и неоп ределенность . В некоторых случаях неопределенност ь знаний является как бы "неполной " и д ополняется некоторыми сведениями о действующих факторах , в частности , знанием законов распр еделения описываю щ их их случайных величин . Этот промежуточный случай соответствует ситуации риска . Принятие решений в условиях риска может б ыть основано на одном из следующих критер иев :
· критерий ожидаемого значения ;
· комбинации ожидаемого значения и дис персии ;
· извест ного преде льного уровня ;
· наиболее вероятного события в будущем .
Рассмотрим более подробно применение этих критериев .
1. Критерий ожидаемого значения (КОЗ ).
Использование КОЗ предполагает п ринятие решения , обуславливающего максимальную пр ибыль при имею щихся исходных данных о вероятности полученного результата при том или другом решении . По существу , КОЗ п редставляет собой выборочные средние значения случайной величины . Естественно , что достоверно сть получаемого решения при этом будет за висеть от объема выборки . Так , если обозначить
КОЗ - Е (x 1 , x 2 ,..., x n ), (1.1)
где
x 1 , x 2 ,..., x n - принима емые решения при их количестве , равном n, то
E ( x i ) яяя M ( x i ), (1.2)
где
M(x i ) - математическое ожидание кр итерия.
Таким образом , КОЗ может применяться , когда однотипн ые решения в сходных ситуациях приходится принимать большое число раз.
Приведем пример использования этого крите рия для принятия решения.
Пример 1.1.
Пусть мастерская имеет n станков , причем ремонт отказавшего станка производится индивидуально , а если стан ки не от казывают , то через T интервалов времени произво дится профилактический ремонт всех станков . З адача заключается в определении оптимального значения T, при котором общие затраты на ре монт будут минимальны . Очевидно , что задача может быть решена , если известна вероятность p t отказа одного станка в момент времени t. Эта неопределенность и представляет в данном случ ае элемент "риска ".
КОЗ для данного случая запишется так :
E[C(T)] = (C 1 E(n t ) + C 2 n)/T, (1.3)
где
E[C(T)] - КОЗ затр ат на ремонт станков за один интервал времени ;
C 1 - затраты н а ремонт одного станка при внезапном отка зе ;
E(n t ) - математическ ое ожидание вышедших из строя станков в момент t;
C 2 - затраты н а профилактический (плановый ) ремонт одного ст анка.
Допустим , что n t имеет биноминально е распределение , тогда
E(n t ) = n p t и
E[C(T)] =[n (C 1 p t + C 2 )]/T. (1.3а )
Необходимые у словия оптимального значения T * имеют вид :
E[C(T * -1)] я E[C(T * )] и E[C(T * +1)] я E[C(T * )]. (1.4)
2. Критерий "ожидаемо го значения - дисперсия ".
Как указывалос ь выше , КОЗ имеет область применения , огра ниченную значительным числом однотипных решений , принимаемых в аналогичных ситуациях . Этот недостаток можно устранить , ес ли применя ть комбинацию КОЗ и выборочной дисперсии s 2 . Возможным критер ием при этом является минимум выражения
E(Z, я ) = E(Z) я k я U(z), (1.5)
где
E(Z, я ) - критерий "ожидаемого значения - дисперсия ";
k - постоянный коэффициент ;
U(Z) = m Z /S - выборочный коэффициент вариации ;
m Z - оценка ма тематического ожидания ;
S - оценка среднего квадратического ожидания.
Знак "минус " ставится в случае оценки прибыли , знак "плюс " - в случае затрат.
Из зависимости (1.5) видно , что в данном случае точность предсказания р езультата повышается за сче т учета возможного разброса значений E(Z), то есть введения своеобразной "страховки ". При это м степень учета этой страховки регулируется коэффициентом k, который как бы управляет степенью учета возможных отклонений . Так , напр име р , если для ЛПР имеет большое значение ожидаемые потери прибыли , то k>>1 и при этом существенно увеличивается роль отклонений от ожидаемого значения прибыли E(Z) з а счет дисперсии.
3. Критерий предельн ого уровня .
Этот критерий не имеет четко выраженной мат ематичес кой формулировки и основан в значительной степени на интуиции и опыте ЛПР . При этом ЛПР на основании субъективных соображ ений определяет наиболее приемлемый способ де йствий . Критерий предельного уровня обычно не используется , когда нет полного пре д ставления о множестве возможных альтернат ив . Учет ситуации риска при этом может производиться за счет введения законов рас пределений случайных факторов для известных а льтернатив .
Несмотря на отсутствие формализации крите рием предельного уровня пользуются довольно часто , задаваясь их значениями на основан ии экспертных или опытных данных.
4. Критерий наиболее вероятного исхода .
Этот критерий предполагает замену случайной ситуации детер минированной путем замены случайной величины прибыли (или затрат ) единств енным значением , имеющим наибольшую вероятность реализации . Использование данного критерия , также как и в предыдущем случ ае в значительной степени опирается на оп ыт и интуицию . При этом необходимо учитыва ть два обстоятельства , затрудняющие применение этого критерия :
· критерий нельзя использовать , если наибольшая ве роятность события недопустимо мала ;
· применение критерия невозможно , если несколько значений вероятностей возможного исход а равны между собой .
5. Учет неопределенных факторов , заданных закон ом распределения.
Случай , когда неопределенные факт оры заданы распределением , соответствует ситуации риска . Этот случай может учитываться двум я путями . Первый - анализом адаптивных возможно стей , позволяющих реагировать на конкретные и сходы ; второй - методи чески , при сопоставлен ии эффективности технических решений . Суть пе рвого подхода заключается в том , что закон ы распределения отдельных параметров на этапе проектирования могут быть определены с д остаточной степенью приближения на основе соп оставления с ан а логами , из физическ их соображений или на базе статистических данных и данных прогнозов.
Методический учет случайных факторов , зада нных распределением , может быть выполнен двум я приемами : заменой случайных параметров их математическими ожиданиями (сведением стохасти ческой задачи к детерминированной ) и "взвешива нием " показателя качества по вероятности (этот прием иногда называют "оптимизация в сред нем ").
Первый прием предусматривает определение математического ожидания случайной величины v - M(v) и определени е зависимости W(M(v)), которая в дальнейшем оптимизируется по u. Однако сведение к детерминированной схеме может быть осуще ствлено в тех случаях , когда диапазон изме нения параметра u невелик или когда зависимост ь W(u) линейна или близка к ней.
Второй прием предусматривает определение W в соответствии с зависимостями соответствен но для дискретных и непрерывных величин :
; (1.6)
, (1.7)
где
P(u i ) - ряд распределений слу чайной величины u i ;
f(u i ) - плотность распределения случайной величины u.
При описании дискретных случайных величин наиболее часто используют распределения Пуассона , биноминальное . Для непрерывных величин основными распределени ями являются нормальное , равномерное и эк споненциальное.
1.2.1. Постановка задачи стохастическо го программирования
При перспективном и оперативном планировании работы лесопромышленного предприят ия возникает необходимость в учете ряда с лучайных факторов , существенно влияющих на п роцесс производства . К таким факторам относятся спрос , который не всегда может б ыть предсказуем , непредусмотренные сбои в пос туплении сырья , энергии , рабочей силы , неисправ ности и аварии оборудования . Еще больше сл учайных факторов необходимо учитывать при планировании лесохозяйственного производства , эффективность которого зависит от климатических условий , урожайности и т.д . Поэтому задачи планирования лесного производства целесообразно ставить и исследовать в терминах и п онятиях стохастического программир о вания , когда элементы задачи линейного программирован ия (матрица коэффициентов A, вектора ресурсов b, в ектора оценок c) часто оказываются случайными . П одобного типа задачи ЛП принято классифициров ать как задачи стохастического программирования (СП ).
Подход ы к постановке и анализу стохастических задач существенно различаются в зависимости от последовательности получения ин формации - в один прием или по частям . При построении стохастической модели важно та кже знать , необходимо ли принять единственное решение, не подлежащее корректировке , ил и можно по мере накопления информации оди н или несколько раз корректировать решение . В соответствии с этим в стохастическом программировании исследуются одноэтапные , двухэтап ные и многоэтапные задачи.
В одноэтапных задачах р ешение принимается один раз и не корректируется . Они различаются по показателям качества решения (по целевым фу нкциям ), по характеру ограничений и по вид у решения .
Задача СП может быть сформулирована в M- и P- постановках по отношению к записи целевой фун кции и ограничений.
Случайны элементы вектора с (целевая функция ).
При M-постановке целевая функция W записывае тся в виде
, (1.8)
что означает оптимизацию математического ожидания целевой ф ункции . От математического ожидания целевой ф ункции можно перейти к математическому ожидан ию случайной величины c j
. (1.9)
При P- постановк е имеем :
· при максимизации
(1.10)
где
W min - предварительно заданное д опустимое наихудшее (минимальное ) значение целевой функции.
· при минимизации
(1.11)
где
W max - предварительно заданное д опустимое наихудшее (максимальное ) зн ачение целевой функции.
Суть P-постановк и заключается в том , что необходимо найти такие значения x j , при которых максимизируется вероятность того , что целевая функция будет не хуже предельно допустимого значения.
Ограничения задачи , которые должны выполня т ься при всех реализациях параметров у словий задачи , называются жесткими ограничениями . Часто возникают ситуации , в которы х постановка задачи позволяет заменить жестки е ограничения их усреднением по распределению случайных параметров . Такие ограничения назы вают статистическими :
(1.12)
В тех случ аях , когда по содержательным соображени ям можно допустить , чтобы невязки в условиях не превышали заданных с вероятностями , не большими я i >0, говорят о стохастических задачах с вероятностными огранич ениями :
(1.13)
т.е . вероятность выполнения каждого заданного ограничения дол жна быть не менее назначенной величины я i . Пар аметры я i предполагаются заданными или являются реш е ниями задачи более высокого уровня.
Представленные задачи как в M-, так и в P- постановках непосредственно решены быть не могут . Возможным методом решения этих задач является переход к их детерминированным эквивалентам . В основе этого перехода леж ит исполь зование закона распределения слу чайной величины . В инженерной практике наибол ее часто используется нормальный закон распре деления , поэтому дальнейшие зависимости приведем для этого случая.
Принимаем , что a ij , b i , c j подчинены нормальному зако ну распределен ия . В этом случае будет справедлива следующие детерминированные постано вки :
· P - постановка целе вой функции , максимизация :
(1.14)
где
и я j - математическое о жидание и среднее квадратическое отклонен ие случайной величины c j .
· P - постановка целе вой функции , минимизация :
(1.15)
· Вероятностные ограничения :
где
- соответственно , математические ожидания и дисперсии случайных величин a ij и b i ;
- значение центрированной нормирован ной случайной величины в нормальном законе р аспределения , соответствующей заданному ур овню вероятности соблюдения ограничений я i .
Сделаем несколько замечаний к приведенным зависимостям :
· задача стохастичес кого программирования сведена к задаче нелине йной оптимизации и может быть решена одни м из ра ссматриваемых ранее методов ;
· сравнение ограничения ресурса в стох астическом программировании и аналогичным ограни чением в задаче линейного программирования по казывает , что учет случайного характера велич ин a ij и b i приводит к уменьшению располагаемого р есурса на величину
, (1.16)
т.е . к необ ходимости в дополнительном ресурсе . Одна ко этот дополнительный ресурс может оказаться неиспользованным , но для гарантированного вы полнения плана его иметь необходимо.
2. Применение стохастического программирования в лесном деле
Пример 1.1. Распределение посевной пл ощади между лесными культур ами .
Лесничество имеет вырубки площад ью в 100 га в различных почвенных условиях (три типа ) и заинтересовано как можно бо лее эффективно использовать ее для создания лесных культур . Требуется распределить площа дь под посевы лесных культур - сосны и ели . Имею тся статистические данные по издержкам и всхожести каждой культуры на единице площади с почвой каждого типа . Кро ме того , вышестоящей организацией задан миним ально необходимый объем лесовосстановления по каждой культуре - 30 для сосны и 40 для ели . Издержк и на обработку почвы и всхожесть лесных культур существенно зависят от погодных условий и являются случайными величинами с параметрами риска :
· я 0 , характеризующий риск превыш ения фактических издержек над запланированными ;
· я 1 и я 1 , определяющие риск н евыполнения плана по культуре i.
Постановка задачи.
1. В качестве пок азателя эффективности целесообразно взять издержки лесовосстановления.
2. В качестве управляемых переменных задачи следует взять :
x 11 - площадь с 1 типом почвы , отводимой под культуру со сны ;
x 12 - площадь с 1 типом почвы , отводимой под культуру ели ;
x 21 - площадь с 2 типом почвы , отводимой под культуру сос ны ;
x 22 - площадь с 2 типом почвы , отводимой под культуру ели ;
x 31 - площадь с 3 типом почвы , отводимой под культуру сос ны ;
x 32 - площа дь с 3 типом почвы , отводимой под культуру ели.
3. Целевая функция :
c 11 x 11 + c 11 x 12 + c 11 x 13 + c 11 x 21 + c 11 x 22 + c 11 x 23 + c 11 x 31 + c 11 x 32 + c 11 x 33 яяя min,
где
c 11 - удельные затраты площади с почвой типа 1 для посадк и сосны ;
c 12 - удельные затра ты площади с почвой типа 1 для посадки ели ;
c 21 - удельные затраты площади с почвой типа 2 для посадк и сосны ;
c 22 - удельные затраты площади с почвой типа 2 для посадк и ели ;
c 31 - удельные затраты площади с почвой типа 3 для посадк и сосны ;
c 32 - удельные з атраты площади с почвой типа 3 для посадки ели.
4. Ограничения :
4.1. По использованию земли , га :
4.2. По бюджету , тыс . руб .:
4.3. По обяза тельствам , га :
для сосны
для ели
4.4. Областные о граничения :
x 11 я 0,..., x 33 я 0.
Пример 1.2. Выб ор состава машинно-тракторного парка .
Выбор структуры техничес кого оснащения является необходимым элементом лес охозяйственного планирования . Машины различных ма рок , предназначенные для одних и тех же работ , обладают разными конструктивными парамет рами и характеризуются неодинаковой эффективност ью . Для каждого конкре т ного хозяйст ва требуется подобрать состав машинно-тракторного парка , наиболее полно отвечающий его особ енностям . Рациональный подбор техники должен минимизировать приведенные затраты на производст во заданных работ в требуемые сроки . Объем ы работ , производ и тельность агрегатов и приведенные затраты зависят от сложивших ся погодных условий и множества других не предсказуемых факторов . Поэтому выбор структуры машинно-тракторного парка следует связать с решением стохастической задачи.
Постановка задачи.
1. В качес тве показателя эффективности целесо образно взять суммарные приведенные издержки на приобретение , обслуживание и эксплуатацию техники.
2. В качестве управляемых переменных задачи следует взять :
x 1 - количество плугов - покровасдирателей ;
x 2 - количество плу гов лесных ;
x 3 - количество плугов лесных ПЛ ;
x 4 - количество тракторов ЛХТ -55А ;
x 5 - количество тракторов ТДТ -55А ;
x 6 - количество тракторов МТЗ.
3. Целевая функция :
c 1 x 1 + c 2 x 2 + c 3 x 3 + c 4 x 4 + c 5 x 5 + c 6 x 6 яяя min,
где
c 1 - приведенные затраты на плуг - покровасдиратель ;
c 2 - приведенные затраты на плуг лесной ;
c 3 - приведенные затраты на плуг лесной ;
c 4 - приведенные затраты на трактор ЛХТ -55А ;
c 5 - приведенные затраты на трактор ТДТ -55А ;
c 6 - приведенные затраты на трактор МТЗ.
4. Ограничения :
4.1. По условию обеспечения необходимой ком плексной работы агрегатов :
,
где
h ij = 1, если плуг j типа работа ет с трактором i типа ;
h ij = 0, в против ном случае.
4.2. По обязател ьствам выполнения требуемых работ , га :
где
a kj , k = 1,2,...,m, j = 1,..., 3 - произ водительность плуга j типа на работе k типа ;
b k , - объем ра бот k вида , подлежащих выполнению.
4.3. Областные ограничения :
x 1 я 0,..., x 6 я 0.
1.2.3. Мето д статистического моделирования
Приведенные формулы (1.6) и (1.7) могут быть использованы для систем независимых с лучайных величин . Однако для технических сист ем , как правило , случайные параметры являются зависимыми . Причем эта зависимость не фун кциональна я , а корреляционная . Поэтому для анализа случайных факторов , заданных распред елением , широкое применение нашли теория марк овских процессов и метод статистического моде лирования (метод Монте-Карло ).
В задачах принятия оптимальных решений широкое применение получил метод Монте-Кар ло . Основными особенностями этого метода , осно ванного на многократном повторении одного и того же алгоритма для каждой случайной реализации , являются : универсальность (метод не накладывает практически никаких ограничений на исследуе м ые параметры , на вид законов распределения ); простота расчетного алг оритма ; необходимость большого числа реализаций для достижения хорошей точности ; возможность реализации на его основе процедуры поиска оптимальных параметров проектирования . Отметим основ н ые факторы , определившие приме нение метода статистического моделирования в задачах исследования качества при проектировании : метод применим для задач , формализация к оторых другими методами затруднена или даже невозможна ; возможно применение этого метода д л я машинного эксперимента над не созданной в натуре системы , когда на турный эксперимент затруднен , требует больших затрат времени и средств или вообще не допустим по другим соображениям.
1.3. Учет неопределенных пассивных условий
Неопределенные факторы , зак он распределения которых неизвестен , являются н аиболее характерными при исследовании качества адаптивных систем . Именно на этот случай следует ориентироваться при выборе гибких конструкторских решений . Методический учет таких факторов базируется на формир о ван ии специальных критериев , на основе которых принимаются решения . Критерии Вальда , Сэвиджа , Гурвица и Лапласа уже давно и прочно вошли в теорию принятия решений.
В соответствии с критерием Вальда в качестве оптимальной выбирается стратегия , гарантирующая выигрыш не меньший , чем "нижняя цена игры с природой ":
. (1.17)
Правило выбора решения в соответствии с критерием Вальда можно интерпретировать следующим образом : матрица решений [W ir ] дополняется еще одним столбцом из н аименьших результатов W ir каждой строки . Выбрать надлежит тот вариант , в строке которого стоит наибольшее значение W ir этого столбца.
Выбранное таким образом решение полностью исключает риск . Это означает , что принима ющий решение не может столкнуться с худши м результатом , чем тот , на который он о риентируется . Какие бы условия V j не встретились , соответству ющий результа т не может оказаться ниже W. Это свойство заставляет считать критерий Вальда одним из фундаментальных . Поэтому в технических задачах он применяется чаще всего как сознательно , так и неосознанно . Однако в практических ситуациях излишний песс имизм этого кри т ерия может оказать ся очень невыгодным.
Применение этого критерия может быть о правдано , если ситуация , в которой принимается решение , характеризуется следующими обстоятельст вами :
· о вероятности п оявления состояния V j ничего не известно ;
· с появлением сос тояния V j необходимо считаться ;
· реализуется лишь мал ое количество решений ;
· не допускается никак ой риск .
Критерий Байеса-Лапласа в отличие от критерия Вальда , учитывает каждое из возможных следствий всех вариант ов решений :
. (1.18)
Соответствующее правило выбора можно интерпретировать следующи м образом : матрица решений [W ij ] допо лняется еще одним с толбцом , содержащим математическое ожидание значе ний каждой из строк . Выбирается тот вариан т , в строках которого стоит наибольшее зна чение W ir этого ст олбца.
Критерий Байеса-Лапласа предъявляет к ситу ации , в которой принимается решение , след ующие требования :
· вероятность появле ния состояния V j и звестна и не зависит от времени ;
· принятое решение теоретически допускает бесконечно большое
· количество реализаций ;
· допускается некоторый риск при малых числах реализаций .
В соответствии с критерием Сэвиджа в качестве оптимальной выбирается такая стратегия , при которой величина риска принимает наименьшее значение в самой неблагополучной ситуации :
(1.19)
Здесь величину W можно трактовать как максимальный дополните льный выигрыш , который достигается , если в состоянии V j вместо варианта U i выбрать другой , оптимальный дл я этого внешнег о состояния , вариант.
Соответствующее критерию Сэвиджа правило выбора следующее : каждый элемент матрицы реше ний [W ij ] вычитается из наибольшего результата max W ij соответствующего столбца . Разности образуют матрицу остатков . Эта матрица попо лняется столбцом наибольших разностей W ir . Выбирается тот ва риант , в строке которого стоит наименьшее значение.
Согласно критерию Гурвица выбирается такая стратегия , котора я занимает некоторое промежуточное положение между крайним пессимизмом и оптимизмом :
(1.20)
где
я - коэф фициент пессимизма , выбираемый в интервале [0,1].
Правило в ыбора согласно этому критерию следующее : матрица решений [W ij ] дополняется столбцом , содержащим средние взвешенные наименьшего и наибольшего результат ов для каждой строки (2.6). Выбирается тот вар иант , в строках которого стоят наибольшие элементы W ir этого столбца.
При я =1 критерий Гурвица превра щается в критерий Вальда (пессимиста ), а пр и я =0 - в критерий азартного игрока . Отсюда ясно , какое значение имеет весово й множитель я . В технических прило жениях правильно выбрать этот множитель бывае т так же труд но , как правильно выбр ать критерий . Поэтому чаще всего весовой м ножитель я =0.5 принимается в качестве средней точки зрения.
Критерий Гурвица предъявляет к ситуации , в которой принимается решение , следующие тр ебования :
· о вероятности п оявления состояния V j ничего не известно ;
· с появлением состояния V j необходимо считаться ;
· реализуется лишь мал ое количество решений ;
· допускается некоторый риск .
Критерий Ходжа-Лемана базируется одновременно на критериях Вальда и Байеса-Лапласа :
. (1.20)
Правило выбора , соответствующее этому критерию , формулируется следующим образом : матрица реше ний [W ij ] дополняется столбцом , составленным из средних взвешенных (с по стоянными весами ) математического ожидания и наименьшего результата каждой строки . Отбирается тот вариант решения , в строке которого стоит наибольшее значение этого столбца.
При z=1 кр итерий преобразуется в крит ерий Байеса-Лапласа , а при z=0 превращается в критерий Вальда . Таким образом , выбор параметр а z подвержен влиянию субъективизма . Кроме того , без внимания остается и число реализаций . Поэтому этот критерий редко применяется при п р инятии технических решений.
Критерий Ходжа-Лемана предъявляет к ситуац ии , в которой принимается решение , следующие требования :
· о вероятности п оявления состояния V j ничего не известно , но некоторые пре дположения о распределении вероятностей возможны ;
· п ринятое решение теоретически до пускает бесконечно большое количество реализаций ; допускается некоторый риск при малых чис лах реализаций .
Общие рекомендаций по выбору тог о или иного критерия дать затруднительно . Однако отметим следующее : если в отдельных с итуациях не допустим даже минимальный риск , то следует применять критерий Вальд а ; если определенный риск вполне приемлем , то можно воспользоваться критерием Сэвиджа . М ожно рекомендовать одновременно применять поочер едно различные критерии . После этого сре д и нескольких вариантов , отобранных таким образом в качестве оптимальных , прихо дится волевым решением выделять некоторое око нчательное решение.
Такой подход позволяет , во-первых , лучше проникнуть во все внутренние связи проблем ы принятия решений и , во-вторы х , ослабля ет влияние субъективного фактора . Кроме того , в области технических задач различные кр итерии часто приводят к одному результату.
Применение данных критериев с методическо й точки зрения удобно продемонстрировать на примере одной задачи.
Пример 1.3 . Обоснование состав а ремонтной бригады.
На предприятии решается вопрос о создании ремонтной бригады . Основываясь н а применениии критериев Вальда , Лапласа , Сэвид жа и Гурвица , определить наиболее целесообраз ное число членов бригады . Исходные данные сведены в табл . 1.1, в ячейках которой за несены доходы при разных вариантах (стратегия х ). Под стратегией понимается x -число членов бригады и R - количество станков , требующих ре монта.
Таблица 1.1
x\R 40 30 20 10 5 50 100 180 250 4 80 70 80 230 3 210 180 120 210 2 300 220 190 150 1. Критерий Вальда . Как указывалось выше критерий Вальда выр ажается в двухь формах , зависящих от вида исходных данных .
· Если исходными данными являются потери при различных стратег иях , то критерий выбирается в форме минима кса (мин имальные потери из минимально возможных ), то есть критерий (2.6) имеет вид
.
Та ким образом , справа дописывается столбец максимумов по строкам .
Таблица 1.3
x\R 40 30 20 10 max 5 50 100 180 250 250 4 80 70 80 230 230 3 210 180 120 210 210 2 300 220 190 150 300 Для удобства за пишем его в виде транспонированного вектора max u xR = <250, 230, 210, 300> т и выбираем минималь ное значение 210. Таким образом , при данных у словиях рациональным решением будет x=3, R=10, min u xR = 210.
· Если в таблице фигурируют доходы при различных стратегиях , то критерий Вальда принимает форму макси мина (максимум из минимумов ), то есть критерий (2.6) имеет вид
.
Таким образом , справ а дописывается столбец минимумов по строкам .
Таблица 1.3
x\R 40 30 20 10 Min 5 50 100 180 250 50 4 80 70 80 230 70 3 210 180 120 210 120 2 300 220 190 150 150 Тогда решающий столбец имеет вид max u xR = <50, 70, 120, 150> т . Максими нное значение равно 150. Таким образом , при данных условиях рациональным решением будет : x=2, R=10, max u xR = 150.
2. Критерий Лапласа . Как известно , критерий Лапласа предполагает , что все состояния с истемы равновероятны и рациональные решения в ыбираются по критерию :
.
При данных предыдущего примера в случае , если в та блице записаны потери при том или ин ом варианте , значение критериев подсчитывается так :
W 1 = 0.25 (50+100+180+250) = 145;
W 2 = 0.25 (80+70+80+230) = 115 ;
W 3 = 0.25 (210+180+120+210) = 180;
W 4 = 0.25 (300+220+190+150) = 215.
Таким образом наилучшим решением будет x=4, минимум потерь (на ибольший выигрыш ) равен 115.
3. Критерий Сэвиджа . В этом случае сос тавляется новая матрица , элементы которой сос тавляются по правилу :
Составим матрицу W(x i , R j ) - матрицу сожалений для случая , когда u ij - потери , используя предыдущие да нные . Соответствующая матрица получается путем вычисления значений min(x i , R j ), равных 50, 70, 80 и 150 из столбцов 1, 2, 3, 4, соответственно
max W(x i , R j ) 0 30 100 100 100 W(x i , R j )= 30 0 0 0 80 160 110 40 60 160 250 150 110 0 250 Таким образом , м инимальные потери будут при x=2, когда max W(x i , R j )=80. Отметим , что независимо от т ого , является функцией сожаления , определяю щая потери . Поэтому здесь можно применить только минимаксный критерий.
4. Критерий Гурвица . В отличие от прим ененных выше "жестких " критериев , критерий Гурв ица является "гибким ", так как позволяет ва рьировать "сте пень оптимизма-пессимизма ". Таким образом , этот критерий устанавливает баланс между случаями крайнего оптимизма или пе ссимизма , путем введения коэффициента веса я . Как указывалось выше , критерий записывается в виде :
Применим данный критерий к нашим исход ным данным , полагая я =0.5. Матрица зна чений W будет выглядеть следующим образом :
Таблица 1.4
min u(x i , R j ) max u(x i , R j ) я min u(x i , R j ) +
я max u(x i , R j ) 5 50 250 15 4 70 230 15 3 120 210 165 2 150 300 225 Таким образом , в результате применени я этого критерия получилось , что существуют два равнозначных варианта :
x 1 = 5, x 2 = 4 при одинаковых значениях W 1 = W 2 = 15.
1.4. Учет активных условий
Как правило , решение практических задач , связанных с оценкой качества и надежности изделий лесного машиностроения , зави сит не только от оперирующей стороны (допу стим , конструктора ), н о и от действий других субъектов системы (например , технолога-ле созаготовителя ). Каждая из сторон преследует с обственные цели , не всегда совпадающие друг с другом . Неопределенность такого рода при принятии решений относят к классу поведе нческих неопределе н ностей . Теоретической основой нахождения оптимального решения в условиях неопределенности и конфликтных ситуаций является теория игр . Игра - это математиче ская модель процесса функционирования конфликтую щих элементов систем , в котором действия и гроков про и сходят по определенным правилам , называемых стратегиями . Ее широкому распространению в п оследнее время способствовало как развитие ЭВ М , так и создание аналитического аппарата , позволяющего находить аналитические решения для широкого класса задач . Основной постулат теории игр - любой субъект системы по меньшей мере так же разумен , как и опе рирующая сторона и делает все возможное , ч тобы достигнуть своих целей . От реального конфликта игра (математическая модель конфликта ) отличается тем , что она ведется по оп р еделенным правилам , которые устанавлив ают порядок и очередность действий субъектов системы , их информированность , порядок обмена информацией , формирование результата игры.
Существует много классов игр , различающихс я по количеству игроков , числу ходов , хара ктеру функций выигрыша и т.д . Выделим следующие основные классы игр :
· антагонистические ( игры со строгим соперничеством ) и неантогонис тические . В первом случае цели игроков про тивоположны , во - втором - могут совпадать ;
· стратегические и нестратегически е (в первых субъект системы действует независ имо от остальных , преследуя свои цели , во-в торых субъекты выбирают единую для всех с тратегию );
· парные игры и иг ры для N-лиц ;
· коалиционные и беско алиционные ;
· кооперативные и неко оперативные (в первых воз можен обмен и нформацией о возможных стратегиях игроков );
· конечные и бесконечн ые (в первых - конечное число стратегий ).
Наибольшее распространение в техниче ских приложениях имеют парные стратегические бескоалиционные конечные некооперативные игры . Мо дел ь проблемной ситуации в этом случае имеет вид :
< U , V , W 1 , W 2 , R 1 , R 2 >,
где
U - множество стратегий оперирующей стороны (конструктора );
V - множество стратегий оппонирующей стороны (технолог и природа );
W 1 и W 2 - показатели качества игроков ;
R 1 и R 2 - си стемы предпочте ния игроков.
Системы предпо чтения игроков , в свою очередь , основываются на двух ведущих принципах рационального по ведения : принципе наибольшего гарантированного ре зультата и принципе равновесия.
Первый основан на том , что рациональны м выборо м одного из игроков должен считаться такой , при котором он рассчитывае т на самую неблагоприятную для него реакц ию со стороны другого игрока.
Второй принцип гласит , что рациональным выбором любого игрока считается такая стра тегия u $ (или v $ ), для которой си туация (u $ , v $ ) обоюдовыгодна : любое отклонение от данной ситуации игры не является выгодным ни для одного из игр оков.
Решается парная матричная игра (проектируе мое изделие - меры и средства противодействия ) с нулевой суммой (выигрыш одной стороны равен пр оигрышу другой ) на основе рассмотрения платежной матрицы , которая представл яет собой совокупность значений U и V (пара с тратегий (u,v) U x V называется ситуацией игры ) а также выигрышей W ij при парном сочетании всевозможных стратегий сторон.
Решение парной матричной игры может быть в чистых стратегиях , когда для к аждой из сторон может быть определена еди нственная оптимальная стратегия , отклонение от которой невыгодно обоим игрокам . Если выгод но использовать несколько стратегий с определ енной частотой их че р едования , то решение находится в смешанных стратегиях.
Основные особенности использования методов теории заключаются в следующем . В качестве возможных стратегий со стороны проектируемой системы рассматриваются возможные варианты е е строения , из которых сле дует выбрать наиболее рациональный . В качестве стратегий противника рассматриваются возможные варианты его противодействия , стратегии их применения.
Необходимо отметить , что при рассмотрении игр с использованием адаптивной системы число ее стратегий может быть существенн о расширено благодаря реализации "гибких " конс трукторских решений . Анализ игровых ситуаций в этом случае может быть направлен не только на выбор рационального варианта про ектируемого изделия , но и на определение а лгоритмов рационального при м енения сис темы в конфликтной ситуации.
Другая особенность применения методов тео рии игр заключается в выборе решений , полу чаемых на основе анализа конфликтной ситуации . В теории игр доказывается теорема о том , что оптимальная стратегия для каждого из игрок ов является оптимальной и д ля другого . Так , если решение игры получен о в чистых стратегиях (имеется седловая то чка ), то выбор решения однозначен . Например , если для парной антагонистической игры 3x4 со ставить матрицу , где элементами u ij будут выигрыши (про и грыши ) игроков , то седловая точка находится на пересечении максимина строк и минимакса столбцов
Стратегии Стратегии B Min A 1 2 3 4 строк 1 8 2 9 5 2 2 6 5 7 18 5 3 7 3 -4 10 -4 max
столбцов 8 5 9 18 Оптимальными страте гиями будут для A - 2, для B - 2. Цена игры рав на 5. Отметим , что в случае наличия седловой точки ни один из игроков не может улучшить стратегию и стратегии называются чистыми . Отметим , ч то игра с чистыми стратегиями может сущес твовать только при наличии полной информации о действи ях противника.
Если же решение игры получено в см ешанных стратегиях , то это эквивалентно созда нию множества вариантов проектируемого компонент а и использованию их с оптимальными часто там , соответствующими оптимальной смешанной страт егии . В случаях , когда н е имеется п олной информации о действиях противника , ввод ятся вероятности применения той или иной стратегии в виде векторов
P
= - для игр ока A, где ;
Q = - для игр ока B, где .
При этом игрок A выбирает стратегию в соответствии с принципом максимина по выра жению :
,
а игра B по принципу минимакса
.
Рассмотрим при мер : пусть рассматривается принятие решения в игре 2x2, где игрок A знает вероятность страт егии 1, то есть p 1 , тогда очевидно вероятность стратегии 2 будет 1-p, соответственно стратегии игрока B будут q 1 и 1-q 1 . Платежная матрица будет иметь вид :
B q 1 1-q 1 A p 1 a 11 a 12 1-p 1 a 21 a 22 На основании матрицы и приведенных выше выражений составляется таблица :
Чистые стратегии игрока B Ожидаемые в ыигрыши игрока A 1 (a 11 -a 21 )p 1 + a 21 2 (a 12 -a 22 )p 1 + a 22 Из таблицы видн о , что ожидаемый выигрыш игрока A линейно з ависит от вероятности p 1 (в данном случае задача может б ыть решена графоаналитически ). Тогда смешанная стратегия игрока А будет иметь вид
,
то есть иг року A выгодно применять ст ратегию 1 с ча стотой (вероятностью ) - p 1 , а стратегию 2 с частотой p 2 .
Очевидно , что разработка нескольких вариан тов изделия сопряжена с большими затратами , не всегда реализуема и затрудняет использо вание системы . Поэтому при получении решения в смешанных стратегиях рекомендуются сл едующие случаи принятия окончательного решения :
· для дальнейшего проектирования выбирается тот вариант , который гарантирует максимальное качество (выбор по максиминной стратегии аналогично критерию Ва льда );
· выбирается тот ва риант , который в смешанной стратегии должен использоваться с максимальной вероятностью ;
· реализуется несколько вариантов изделия с частотами , соответствующими смешанной стратегии (создание адаптивно-модульных конструкций ).
Важное значение в задачах иссл едования качества адаптивных систем имеет не только решение игры , но и анализ платежной матрицы . Это особенно важно в тех случаях , когда решение в смешанных стратегиях не реализуется . Этот анализ может проводиться на основе : оценки возможных п отерь эффект и вности в случае реали зации чистой стратегии ; определения дополнительны х затрат на их компенсацию с помощью " гибких " конструкторских решений ; оценки достоверно сти рассмотренных стратегий противодействия ; опре деления возможности реализации компромиссных вар и антов и т.д.
Для анализа конфликтной ситуации требуетс я на основе математической модели операции построить платежную матрицу [W mn ] =[W ij ], где W ij характеризует качество изделия при выборе i-го варианта проектируемого изделия и при j-м варианте противодейс твия противника.
Решение может быть получено в чистых стратегиях , когда есть седловая точка . Ус ловие седловой точки имеет вид
, (1.21)
где левая часть выражения - нижняя цена игры , правая - верхняя цена игры.
Если условие (1.8) не выполняется , то седло вая точка отсутствует и требуется реализация смешанной стратегии.
Решение в смешанны х стратегиях сос тоит в реализации чистых стратегий с разл ичными вероятностями , задаваемыми распределением :
для проектируемого изделия в виде вект ора-столбца
G = g i , где i = 1,2 ...m; ;
для противодей ствия в виде вектора-строки
F = f j , где j = 1,2 ...n; ,
где
g i - вероятность выбора стратег ии u i ;
f j - вероятность выбора стратегии v j .
Платежную функ цию запишем в следующем виде :
(1.22)
где индексом "т " обозначена процедура транспонирования.
Платежная функция W(G,F) всегда имеет седловую то чку , т.е . всегда существует решение матричной игры . Это утверждение соответствует основной теореме теории матричных игр : ка ждая матричная игра с нулевой суммой имее т , по крайней мере , одно решение в чист ых или смешанных стратегиях.
Последовательность решен ия игры следую щая :
1. Анализируется плат ежная матрица на предмет исключения заведомо невыгодных и дублирующих стратегий .
1. Проверяется наличие седловой точки п о условию (1.21).
2. Если решение в чисты х стратегиях отсутствует , то ищется решение в смешанн ых стратегиях с помощью м етодов линейного программирования или методом Монте-Карло .
Пример 1.4. Обоснование стратегии экс плуатации
Предположим , что техническая сист ема (агрегат ) состоит из 5 блоков , отказ одно го из которых ведет к отказу всей сис темы . Для предупреждения простоя системы можно провести перед началом ее работы пр оверку и замену неисправного блока . Если п роверен не тот блок , то система простаивае т , что приводит к убытку R i (в таблице ), который существенно превышает расходы на профилактику и за мену (т.е . R ij = 0). Требуется выбрать оптимальную стратегию из условия минимума убытка.
Пусть матрица расходов в зависимости о т стратегий имеет вид :
Отказ блока (стратегии природы ) Проверка 1 2 3 4 5 max строки и 1 8 2 9 5 6 9 замена 2 6 5 17 18 7 18 (стра- 3 7 3 14 10 8 14 тегии 4 4 6 16 9 19 19 эксплуа- 5 12 4 15 8 10 15 тации ) min столбца 6 2 9 5 6 Ответ : Имее тся седловая точка - необходимо во всех сл учаях проверять первый блок.
Пример 1.5. Зимняя эксплуатация лес овозной дороги
Предположим , что при заготов ке леса зимой стоит выбор делать или не делать предварительную расчистку дороги . П ри этом известны предполагаемые высоты снежно го покрова и матрица доходов при применен ии той или иной стратегии . В данном сл учае можно реализовать себя как иг р ока A, а природу , как игроке B:
B 20 мм 40 мм 60 мм 100 мм A не делать 2 2 3 -1 делать 4 3 2 6 Решение : Имеем и гру 2x4. Эта игра не имеет седловой точки . Ожидаемые выигрыши игрока A, соответствующие чис тым стратегиям B представлены в таблице
Чист ые стратегии B Ожидаемые выигр ыши A 1
2
3
4 -2x 1 + 4
-x 1 +3
x 1 + 2
-7x 1 + 6 Далее оптимальное решение - максимин находится графоаналитическим методом . Значение игры в данном случае равно 5/2.
Литература :
1. Андреев В.Н ., Герасимов Ю.Ю . Принятие оптима льных решений : Теория и применени е в лесном деле . Йоэнсуу : Из-во ун-та Йо энсуу , 1999. 200 с.
2. Беллман Р ., Калаба Р . Динамическое программирование и сов ременная теория управления . М .: Наука , 1969. 120 с.
3. Вентцель Е.С . Элементы динамического программи рования . М .: Наука , 1964. 176 с.
4. Вентцель Е.С . Исследование операций : задачи , принципы , методол огия . М .: Наука , 1988.
5. Юдин Д.Б . З адачи и методы стохастического программирования . М .: Сов . радио , 1979. 392 с .
6. Davis L.S., Johnson K.N. Forest manag ement. New York: McGraw-Hill Book Company, 1987. 790 p.
7. Моисеев Н.Н ., Математические методы системного анализа М . Наука 1981 487 с.
8. http://www.petrsu.ru/Faculties/Forest/courses/decision/decis_a.htm