Реферат: Принятие оптимальных решений в условиях неопределенности

Кыргызско – Российский Славянский Университет

Естественно-Технический Факультет

Кафедра Математики

Реферат

по предмету: “Теория Игр”

на тему

“Принятие оптимальных решений вусловиях неопределенности “

Выполнил: Алексеенко Н.С.

Проверил:: Жданов Н.В.

Бишкек-2001
1.1. Постановка задачи

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

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

·    неопределенностьцелей;

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

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

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

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

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

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

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

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

Пример 1.1. Лесопосадки

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

Пример 1.2. Проектирование лесныхмашин

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

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

1.   Принятиерешений в условиях риска

 

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

·    критерийожидаемого значения;

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

Рассмотрим более подробно применение этих критериев.

1. Критерий ожидаемого значения(КОЗ).

Использование КОЗ предполагает принятие решения,обуславливающего максимальную прибыль при имеющихся исходных данных овероятности полученного результата при том или другом решении. По существу, КОЗпредставляет собой выборочные средние значения случайной величины. Естественно,что достоверность получаемого решения при этом будет зависеть от объема выборки.Так, если обозначить

КОЗ — Е(x1,<sub/>x2,...,<sub/>xn), (1.1)

где

x1,<sub/>x2,...,<sub/>xn — принимаемые решения при ихколичестве, равном n, то

E(xi)  M(xi),(1.2)

где

M(xi)- математическое ожидание критерия.

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

Приведем пример использования этого критерия дляпринятия решения.

Пример 1.1.

Пусть мастерская имеет n станков, причем ремонтотказавшего станка производится индивидуально, а если станки не отказывают, точерез T интервалов времени производится профилактический ремонт всех станков.Задача заключается в определении оптимального значения T, при котором общиезатраты на ремонт будут минимальны. Очевидно, что задача может быть решена,если известна вероятность pt отказа одного станка в момент времениt. Эта неопределенность и представляет в данном случае элемент«риска».

КОЗ для данного случая запишется так:

E[C(T)]= (C1/>E(nt) + C2 n)/T, (1.3)

где

E[C(T)]- КОЗ затрат на ремонт станков за один интервал времени;

C1 — затраты на ремонт одного станка при внезапном отказе;

E(nt)- математическое ожидание вышедших из строя станков в момент t;

C2 — затраты на профилактический (плановый) ремонт одного станка.

Допустим, что nt имеет биноминальноераспределение, тогда

E(nt) = n ptи

E[C(T)] =[n (C1/>pt+ C2)]/T. (1.3а)

Необходимыеусловия оптимального значения T* имеют вид:

E[C(T*-1)]E[C(T*)] и E[C(T*+1)] E[C(T*)]. (1.4)

2.   Критерий«ожидаемого значения — дисперсия».

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

E(Z,  ) =E(Z)  k U(z), (1.5)

где

E(Z, ) — критерий «ожидаемого значения — дисперсия»;

k- постоянный коэффициент;

U(Z)= mZ/S — выборочный коэффициент вариации;

mZ — оценка математического ожидания;

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(ui)- ряд распределений случайной величины ui;

f(ui)- плотность распределения случайной величины u.

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

1.2.1. Постановка задачистохастического программирования

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

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

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

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

Случайны элементы вектора с (целевая функция).

При M-постановке целевая функция W записывается ввиде

/>, (1.8)

что означает оптимизацию математического ожиданияцелевой функции. От математического ожидания целевой функции можно перейти кматематическому ожиданию случайной величины cj

/>. (1.9)

При P- постановке имеем:

·    примаксимизации

/>  (1.10)

где

Wmin — предварительно заданное допустимое наихудшее (минимальное) значение целевойфункции.

·    приминимизации

/>  (1.11)

где

Wmax — предварительно заданное допустимое наихудшее (максимальное) значение целевойфункции.

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

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

/>  (1.12)

В тех случаях, когда по содержательным соображениямможно допустить, чтобы невязки в условиях не превышали заданных свероятностями, небольшими  i>0, говорят о стохастическихзадачах с вероятностными ограничениями:

/>  (1.13)

т.е. вероятность выполнения каждого заданногоограничения должна быть не менее назначенной величины  i.Параметры  i предполагаются заданными или являются решениямизадачи более высокого уровня.

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

Принимаем, что aij, bi, cjподчинены нормальному закону распределения. В этом случае будет справедливаследующие детерминированные постановки:

·    P — постановка целевой функции, максимизация:

/>  (1.14)

где

/>и  j — математическое ожидание и среднее квадратическое отклонение случайной величиныcj.

·    P — постановка целевой функции, минимизация:

/>  (1.15)

·    Вероятностныеограничения:

/>

где

/> — соответственно, математическиеожидания и дисперсии случайных величин aij и bi;

/> — значение центрированной нормированнойслучайной величины в нормальном законе распределения, соответствующей заданномууровню вероятности соблюдения ограничений  i.

Сделаем несколько замечаний к приведеннымзависимостям:

·    задачастохастического программирования сведена к задаче нелинейной оптимизации иможет быть решена одним из рассматриваемых ранее методов;

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

/>, (1.16)

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

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

Пример 1.1. Распределениепосевной площади между лесными культурами.

Лесничество имеет вырубки площадью в 100 га вразличных почвенных условиях (три типа) и заинтересовано как можно болееэффективно использовать ее для создания лесных культур. Требуется распределитьплощадь под посевы лесных культур — сосны и ели. Имеются статистические данныепо издержкам и всхожести каждой культуры на единице площади с почвой каждоготипа. Кроме того, вышестоящей организацией задан минимально необходимый объемлесовосстановления по каждой культуре — 30 для сосны и 40 для ели. Издержки наобработку почвы и всхожесть лесных культур существенно зависят от погодныхусловий и являются случайными величинами с параметрами риска:

·     0,характеризующий риск превышения фактических издержек над запланированными;

 1 и 1, определяющие риск невыполнения плана по культуре i.

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

1. В качестве показателя эффективностицелесообразно взять издержки лесовосстановления.

2. В качестве управляемых переменных задачиследует взять:

x11 — площадь с 1 типом почвы, отводимойпод культуру сосны;

x12 — площадь с 1 типом почвы, отводимойпод культуру ели;

x21 — площадь с 2 типом почвы, отводимойпод культуру сосны;

x22 — площадь с 2 типом почвы, отводимойпод культуру ели;

x31 — площадь с 3 типом почвы, отводимойпод культуру сосны;

x32 — площадь с 3 типом почвы, отводимойпод культуру ели.

3. Целевая функция:

c11 x11+ c11 x12 + c11 x13 + c11x21 + c11 x22 + c11 x23 +c11 x31 + c11 x32 + c11x33 min,

где

c11 — удельные затраты площади с почвой типа1 для посадки сосны;

c12 — удельные затраты площади с почвойтипа 1 для посадки ели;

c21 — удельные затраты площади с почвойтипа 2 для посадки сосны;

c22 — удельные затраты площади с почвойтипа 2 для посадки ели;

c31 — удельные затраты площади с почвойтипа 3 для посадки сосны;

c32 — удельные затраты площади с почвойтипа 3 для посадки ели.

4. Ограничения:

4.1. По использованию земли, га:

/>

4.2. По бюджету, тыс. руб.:

/>

4.3. По обязательствам, га:

для сосны

/>

для ели

/>

4.4. Областные ограничения:

x11 0,..., x33  0.

Пример 1.2. Выбор составамашинно-тракторного парка.

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

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

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

2. В качестве управляемых переменных задачиследует взять:

x1 — количество плугов — покровасдирателей;

x2 — количество плугов лесных;

x3 — количество плугов лесных ПЛ;

x4 — количество тракторов ЛХТ-55А;

x5 — количество тракторов ТДТ-55А;

x6 — количество тракторов МТЗ.

3. Целевая функция:

c1 x1+ c2 x2 + c3 x3 + c4 x4+ c5 x5 + c6 x6  min,

где

c1 — приведенные затраты на плуг — покровасдиратель;

c2 — приведенные затраты на плуг лесной;

c3 — приведенные затраты на плуг лесной;

c4 — приведенные затраты на тракторЛХТ-55А;

c5 — приведенные затраты на тракторТДТ-55А;

c6 — приведенные затраты на трактор МТЗ.

4. Ограничения:

4.1. По условию обеспечения необходимой комплекснойработы агрегатов:

/>,

где

hij= 1, если плуг j типа работает с трактором i типа;

hij= 0, в противном случае.

4.2. По обязательствам выполнения требуемых работ,га:

/>

где

akj, k = 1,2,...,m, j = 1,..., 3 — производительность плуга j типа на работе k типа;

bk, — объем работ k вида, подлежащихвыполнению.

4.3. Областные ограничения:

x1 0,..., x6  0.

1.2.3. Метод статистическогомоделирования

Приведенные формулы (1.6) и (1.7) могут бытьиспользованы для систем независимых случайных величин. Однако для техническихсистем, как правило, случайные параметры являются зависимыми. Причем эта зависимостьне функциональная, а корреляционная. Поэтому для анализа случайных факторов,заданных распределением, широкое применение нашли теория марковских процессов иметод статистического моделирования (метод Монте-Карло).

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

1.3. Учет неопределенныхпассивных условий

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

В соответствии с критерием Вальда в качествеоптимальной выбирается стратегия, гарантирующая выигрыш не меньший, чем«нижняя цена игры с природой»:

/>. (1.17)

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

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

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

·    о вероятностипоявления состояния Vj ничего не известно;

с появлением состояния Vj необходимо считаться; реализуется лишь малое количество решений; не допускается никакой риск.

Критерий Байеса-Лапласа в отличие от критерия Вальда,учитывает каждое из возможных следствий всех вариантов решений:

/>. (1.18)

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

Критерий Байеса-Лапласа предъявляет к ситуации, вкоторой принимается решение, следующие требования:

·    вероятностьпоявления состояния Vj известна и не зависит от времени;

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

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

/>  (1.19)

Здесь величину W можно трактовать как максимальныйдополнительный выигрыш, который достигается, если в состоянии Vjвместо варианта Ui выбрать другой, оптимальный для этого внешнегосостояния, вариант.

Соответствующее критерию Сэвиджа правило выбораследующее: каждый элемент матрицы решений [Wij] вычитается изнаибольшего результата max Wij соответствующего столбца. Разностиобразуют матрицу остатков. Эта матрица пополняется столбцом наибольшихразностей Wir. Выбирается тот вариант, в строке которого стоитнаименьшее значение.

Согласно критерию Гурвица выбирается такаястратегия, которая занимает некоторое промежуточное положение между крайнимпессимизмом и оптимизмом:

/>  (1.20)

где

- коэффициент пессимизма, выбираемый в интервале [0,1].

Правило выбора согласно этому критерию следующее:матрица решений [Wij] дополняется столбцом, содержащим средниевзвешенные наименьшего и наибольшего результатов для каждой строки (2.6). Выбираетсятот вариант, в строках которого стоят наибольшие элементы Wir этогостолбца.

При  =1 критерий Гурвица превращается вкритерий Вальда (пессимиста), а при  =0 — в критерий азартного игрока.Отсюда ясно, какое значение имеет весовой множитель . В техническихприложениях правильно выбрать этот множитель бывает так же трудно, какправильно выбрать критерий. Поэтому чаще всего весовой множитель  =0.5принимается в качестве средней точки зрения.

Критерий Гурвица предъявляет к ситуации, в которойпринимается решение, следующие требования:

·    о вероятностипоявления состояния Vj ничего не известно;

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

Критерий Ходжа-Лемана базируется одновременно накритериях Вальда и Байеса-Лапласа:

/>. (1.20)

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

При z=1 критерий преобразуется в критерийБайеса-Лапласа, а при z=0 превращается в критерий Вальда. Таким образом, выборпараметра z подвержен влиянию субъективизма. Кроме того, без внимания остаетсяи число реализаций. Поэтому этот критерий редко применяется при принятиитехнических решений.

Критерий Ходжа-Лемана предъявляет к ситуации, вкоторой принимается решение, следующие требования:

·    о вероятностипоявления состояния Vj ничего не известно, но некоторыепредположения о распределении вероятностей возможны;

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

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

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

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

Пример 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 uxR =<250, 230, 210, 300>т и выбираем минимальное значение 210.Таким образом, при данных условиях рациональным решением будет x=3, R=10, min uxR= 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 uxR = <50, 70, 120, 150>т.Максиминное значение равно 150. Таким образом, при данных условиях рациональнымрешением будет: x=2, R=10, max uxR = 150.

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

/>.

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

W1 = 0.25 (50+100+180+250) = 145;

W2 = 0.25 (80+70+80+230) = 115;

W3 = 0.25 (210+180+120+210) = 180;

W4= 0.25 (300+220+190+150) = 215.

Такимобразом наилучшим решением будет x=4, минимум потерь (наибольший выигрыш) равен115.

3.Критерий Сэвиджа. В этом случае составляется новая матрица, элементы которойсоставляются по правилу:

/>

Составимматрицу W(xi, Rj) — матрицу сожалений для случая, когда uij — потери, используя предыдущие данные. Соответствующая матрица получаетсяпутем вычисления значений min(xi, Rj), равных 50, 70, 80и 150 из столбцов 1, 2, 3, 4, соответственно

max W(xi, Rj)

30 100 100 100

W(xi, Rj)=

30

80

160 110 40 60 160 250 150 110 250

Такимобразом, минимальные потери будут при x=2, когда max W(xi, Rj)=80.Отметим, что независимо от того, является функцией сожаления, определяющаяпотери. Поэтому здесь можно применить только минимаксный критерий.

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

/>

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

Таблица 1.4

min u(xi, Rj)

max u(xi, Rj)

 min u(xi, Rj) +

 max u(xi, Rj)

5 50 250

15

4 70 230

15

3 120 210 165 2 150 300 225

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

x1 = 5, x2 = 4 при одинаковыхзначениях W1 = W2 = 15.

1.4. Учет активных условий

Как правило, решение практических задач, связанных соценкой качества и надежности изделий лесного машиностроения, зависит не толькоот оперирующей стороны (допустим, конструктора), но и от действий другихсубъектов системы (например, технолога-лесозаготовителя). Каждая из сторонпреследует собственные цели, не всегда совпадающие друг с другом. Неопределенностьтакого рода при принятии решений относят к классу поведенческихнеопределенностей. Теоретической основой нахождения оптимального решения вусловиях неопределенности и конфликтных ситуаций является теория игр. Игра — это математическая модель процесса функционирования конфликтующих элементовсистем, в котором действия игроков происходят по определенным правилам,называемых стратегиями. Ее широкому распространению в последнее времяспособствовало как развитие ЭВМ, так и создание аналитического аппарата,позволяющего находить аналитические решения для широкого класса задач. Основнойпостулат теории игр — любой субъект системы по меньшей мере так же разумен, каки оперирующая сторона и делает все возможное, чтобы достигнуть своих целей. Отреального конфликта игра (математическая модель конфликта) отличается тем, чтоона ведется по определенным правилам, которые устанавливают порядок иочередность действий субъектов системы, их информированность, порядок обменаинформацией, формирование результата игры.

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

·    антагонистические(игры со строгим соперничеством) и неантогонистические. В первом случае целиигроков противоположны, во — втором — могут совпадать;

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

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

< U,V, W1, W2, R1, R2 >,

где

U- множество стратегий оперирующей стороны (конструктора);

V- множество стратегий оппонирующей стороны (технолог и природа);

W1и W2 — показатели качества игроков;

R1и R2 — системы предпочтения игроков.

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

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

Второй принцип гласит, что рациональным выборомлюбого игрока считается такая стратегия u$ (или v$), длякоторой ситуация (u$, v$) обоюдовыгодна: любое отклонениеот данной ситуации игры не является выгодным ни для одного из игроков.

Решается парная матричная игра (проектируемоеизделие — меры и средства противодействия) с нулевой суммой (выигрыш однойстороны равен проигрышу другой) на основе рассмотрения платежной матрицы,которая представляет собой совокупность значений U и V (пара стратегий (u,v) Ux V называетсяситуацией игры) а также выигрышей Wij припарном сочетании всевозможных стратегий сторон.

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

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

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

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

Стратегии Стратегии 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<n>=<p1, p2,..., pn> — для игрока A, где />;

Q<m>=<q1, q2,..., qn> — для игрока B, где />.

При этом игрок A выбирает стратегию в соответствии спринципом максимина по выражению:

/>,

а игра B по принципу минимакса

/>.

Рассмотрим пример: пусть рассматривается принятиерешения в игре 2x2, где игрок A знает вероятность стратегии 1, то есть p1,тогда очевидно вероятность стратегии 2 будет 1-p, соответственно стратегииигрока B будут q1 и 1-q1. Платежная матрица будет иметьвид:

B

q1

1-q1

A

p1

a11

a12

1-p1

a21

a22

На основании матрицы и приведенных выше выраженийсоставляется таблица:

Чистые стратегии игрока B Ожидаемые выигрыши игрока A 1

(a11-a21)p1 + a21

2

(a12-a22)p1 + a22

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

<p*1,p*2>,

то есть игроку A выгодно применять стратегию 1 счастотой (вероятностью) — p1, а стратегию 2 с частотой p2.

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

·    длядальнейшего проектирования выбирается тот вариант, который гарантируетмаксимальное качество (выбор по максиминной стратегии аналогично критериюВальда);

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

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

Для анализа конфликтной ситуации требуется на основематематической модели операции построить платежную матрицу [Wmn] =[Wij],где Wij характеризует качество изделия при выборе i-го вариантапроектируемого изделия и при j-м варианте противодействия противника.

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

/>, (1.21)

где левая часть выражения — нижняя цена игры, правая- верхняя цена игры.

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

Решение в смешанных стратегиях состоит в реализациичистых стратегий с различными вероятностями, задаваемыми распределением:

для проектируемого изделия в виде вектора-столбца

G = {gi},где i = 1,2 ...m; />;

для противодействия в виде вектора-строки

F = {fj},где j = 1,2 ...n; />,

где

gi — вероятность выбора стратегии ui;

fj — вероятность выбора стратегии vj.

Платежную функцию запишем в следующем виде:

/>  (1.22)

где индексом «т» обозначена процедуратранспонирования.

Платежная функция W(G,F) всегда имеет седловуюточку, т.е. всегда существует решение матричной игры. Это утверждениесоответствует основной теореме теории матричных игр: каждая матричная игра снулевой суммой имеет, по крайней мере, одно решение в чистых или смешанныхстратегиях.

Последовательность решения игры следующая:

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

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

Пример 1.4. Обоснование стратегииэксплуатации

Предположим, что техническая система (агрегат)состоит из 5 блоков, отказ одного из которых ведет к отказу всей системы. Дляпредупреждения простоя системы можно провести перед началом ее работы проверкуи замену неисправного блока. Если проверен не тот блок, то система простаивает,что приводит к убытку Ri (в таблице), который существенно превышаетрасходы на профилактику и замену (т.е. Rij = 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

-2x1 + 4

-x1 +3

x1 + 2

-7x1 + 6

Далее оптимальное решение — максимин находитсяграфоаналитическим методом. Значение игры в данном случае равно 5/2.

Литература:

Андреев В.Н., Герасимов Ю.Ю. Принятие оптимальных решений: Теория и применение в лесном деле. Йоэнсуу: Из-во ун-та Йоэнсуу, 1999. 200 с. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969. 120 с. Вентцель Е.С. Элементы динамического программирования. М.: Наука, 1964. 176 с. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1988. Юдин Д.Б. Задачи и методы стохастического программирования. М.: Сов. радио, 1979. 392 с. Davis L.S., Johnson K.N. Forest management. New York: McGraw-Hill Book Company, 1987. 790 p. Моисеев Н.Н., Математические методы системного анализа М. Наука 1981 487 с. www.petrsu.ru/Faculties/Forest/courses/decision/decis_a.htm