Основы теории Стохастических систем (лекции). Основы теории стохастических систем
 Скачать 18.19 Mb.
|
|
Лекция 11 Особенности решения одноэтапных задач стохастического программирования  1. Моделирование систем массового обслуживанияДостаточно часто при анализе вычислительных систем приходится решать т.н. задачи массового обслуживания, возникающие в следующей ситуации. Пусть анализируется вычислительная система (ВС) обслуживания заявок, состоящая из некоторого количества ЭВМ. В ВС могут возникать, по крайней мере, две типичных ситуации: число заявок слишком велико для данной вычислительной мощности ВС, возникают очереди и за задержки в обслуживании приходится платить; в ВС поступает слишком мало заявок и теперь уже приходится учитывать потери, вызванные простоем ЭВМ ВС. Ясно, что цель системного анализа в данном случае заключается в определении некоторого соотношения между потерями доходов по причине очередей и потерями по причине простоя ЭВМ в ВС, такого соотношения, при котором математическое ожидание суммарных потерь окажется минимальным. Так вот, специальный раздел теории систем — теория массового обслуживания, позволяет: использовать методику определения средней длины очереди и среднего времени ожидания заявок в тех случаях, когда скорость поступления заявок и время их выполнения заданы; найти оптимальное соотношение между издержками по причине ожидания в очереди и издержками простоя ЭВМ в ВС; установить оптимальные стратегии обслуживания. Обратим внимание на главную особенность такого подхода к задаче системного анализа — явную зависимость результатов анализа и получаемых рекомендаций от двух внешних факторов: частоты поступления и сложности заявок (а значит — времени их обслуживания). Но это уже связи нашей системы с внешним миром и без учета этого факта нам не обойтись. Потребуется провести исследования потоков заявок по их численности и сложности, найти статистические показатели этих величин, выдвинуть и оценить достоверность гипотез о законах их распределения. Лишь после этого можно пытаться анализировать — а как будет вести себя система при таких внешних воздействиях, как будут меняться ее показатели (значение суммарных издержек) при разных управляющих воздействиях или стратегиях управления. Очень редко при этом используется сама система для проведения натурального эксперимент над ней. Чаще всего такой эксперимент связан с риском потерь заказчиков или неоправданными затратами на приобретение дополнительных ЭВМ для вычислительной системы. Поэтому следует знать о таком особом подходе к вопросу моделирования систем как метод статистических испытаний или метод Монте Карло. Вернемся к примеру с анализом работы вычислительной системы (ВС). Пусть у нас всего лишь одна ЭВМ и заранее известны: - — средняя скорость поступления заявок и - — средняя скорость выполнения заявок (штук в единицу времени), и таким образом задана величина = / — интенсивность нагрузки ЭВМ. Уже по этим данным оказывается возможным построить простейшую модель системы. Будем обозначать X число заявок, находящихся в очереди на обслуживании в единицу времени, и попытаемся построить схему случайных событий для определения вероятности P(X). Событие — в очереди находятся точно X заявок, может наблюдаться в одной из четырех ситуаций: - В очереди было X заявок (A1), за это время не поступило ни одной новой заявки (A2) и за это же время не был выполнена ни одна заявка из находящихся в очереди (A3). - В очереди было X - 1 заявок (B1), за это время поступила одна новая заявка (B2) и за это же время не была выполнена ни одна заявка из находящихся в очереди (B3). - В очереди было X + 1 заявок (C1), за это время не поступило ни одной новой заявки (C2) и за это же время был выполнена одна заявка из находящихся в очереди (C3). - В очереди было X заявок (D1), за это время поступила одна новая заявка (D2) и за это же время был выполнена одна заявка из находящихся в очереди (D3). Такая схема событий предполагает особое свойство "технологии" нашей системы — вероятность поступления более одной заявки за рассматриваемую единицу времени и вероятность выполнения более одной заявки за то же время считаются равными 0. Это не такое уж "вольное" допущение — длительность отрезка времени всегда можно уменьшить до необходимых пределов. А далее все очень просто. Перемножая вероятности событий A1..3, B1..3, C1..3, D1..3, мы определим вероятности каждого из вариантов интересующего нас события — в течение заданного нами интервала времени длина очереди не поменялась. Несложные преобразования суммы вероятностей всех четырех вариантов такого события приведут нас к выражению для вероятности длины очереди в х заявок: P(х) = x (1-), {1} а также для математического ожидания длины очереди: Mх = / (1-). {2} Оценить полезность такого моделирования позволят простые примеры. Пусть мы решили иметь всего лишь 50%-ю интенсивность нагрузки ВС, то есть вдвое "завысили" ее пропускную способность по отношению к потоку заявок. Тогда для = 0.5 имеем следующие данные: Таблица 1
Обобщим полученные результаты: очередь в 4 и более заявок практически невероятна; Наше право (если мы и есть ЛПР!) — принять такую интенсивность или отказаться от нее, но все же у нас есть определенные показатели последствий такого решения. Полезно проанализировать ситуации с другими значениями интенсивности нагрузки ВС. Таблица 2
Обратим теперь внимание еще на одно обстоятельство — мы полагали известной информацию только о средней скорости (ее математического ожидания) выполнения заявок. Иными словами, мы считали время выполнения очередной заявки независящей ни от его "содержания" (объема, сложности и др.), ни от числа заявок, "стоящих в очереди". В реальной жизни это далеко не всегда так и хотелось бы хоть как-то учесть такую зависимость. И здесь теория приходит на помощь (тому, кто понимает ее возможности). Если нам представляется возможность установить не только само (среднюю или ожидаемую скорость обработки заявки), но и разброс этой величины D (дисперсию), то можно будет оценить среднее число заявок в очереди более надежно (именно так — не точнее, а надежнее!): MX =   0.5  . (3)2. Основы теории статистических решений. Статистические игры Специфическим видом игры, имеющим большое значение при анализе практических ситуаций, являются статистические игры, в которых в качестве одного из игроков выступает природа [10]. Природа не имеет злого умысла по отношению к игроку (человеку). Она развивается и действует по своим законам. Во многих случаях человек не знает законы природы или знает недостаточно полно. Платой за попытку получить решение в условиях неполной информации о законе природы является возможность принять ошибочные решения. Правда у человека есть возможность изучить природу посредством постановки эксперимента. Но проведение эксперимента требует времени и затрата средств. Поэтому важной задачей является принятие решения о том, нужно ли проводить эксперимент и какие действия предпринять после окончания эксперимента. Пространство стратегий природы. Понимается полная совокупность внешних условий, в которых приходится принимать решения. Эту совокупность называют состоянием природы. Пространство стратегий природы Θ=(ν1, ν2, ν3, …. ν m), где νi – чистые стратегии природы. Если бы знали заранее, какую из своих чистых стратегий примет природа в каждом конкретном случае, то принимали бы решение на основе полного знания о природе. Однако бывает известен только перечень чистых стратегий и априорное распределение вероятностей на пространстве состояний природы Θ: ε(ν). Θ – это смешенная стратегия природы. Пространство стратегий статистика (ЛПР) и функции потерь. Задача статистика состоит в принятии какого-либо решения из совокупности решений. Чистые стратегии статистика, это его действия по выбору а1, а2, а3, .. аl. Совершая действия статистик может потерпеть убыток, описываемый функцией потерь L(ν, a), которая заранее должна быть определена для всех возможных комбинаций a € A и ν € Θ и представлена матрицей потерь: Q=||qij||, (4) где qij=L(νi,aj). Знание функции потерь позволяет статистику предпринять действия, которые являются наилучшими в условиях имеющейся у него информации. Статистику бывает известна смешенная стратегия природы, т.е априорное распределение вероятностей ε(ν) на пространстве стратегий природы Θ. Знание этой информации позволяет определить средние потери, которые несет статистик выполняя те или иные действия: Средние потери статистика: L(ε, a) = ∑L(ν,a) ε(ν). (5) ν€Θ Наилучшим действием статистика является байесовское действие a*, при котором средние потери будут минимальными: R*(ε) = L(ε, a*) = min L(ε, a) (6) a€A Статистик не обязательно должен ограничиваться использованием только чистых стратегий. Он может использовать смесь чистых стратегий в соответствии с некоторым вероятностным законом распределений – смешанную стратегию. Статистик с вероятностями η(a)=(η1, η2, η3, … ηl) может использовать чистые стратегии a1,a2,a3, …al . В общем случае он располагает некоторым набором смешанных стратегий H={η1(a), … ην(a)}, образующих пространство смешанных стратегий статистика. Если статистик принимает смешанную стратегию η(a), а природа смешанную стратегию ε(ν), то средние потери статистика составят: L(ε, ν) = ∑L(ν, a)ε(ν)η(a) (7) ν,a В этом случае задача статиста состоит в том, чтобы выбирать такую смешанную стратегию η*(a)€H, при котором его средние потери L(ε, η*) будут минимальными: L(ε, η*) = min L(ε, η) (8) η€H В рассматриваем случае статистик определяет наилучшую стратегию действий только на основании имеющейся априорной информации о состоянии природы. Данный тип статистической игры называется статистической игрой без эксперимента. Пример. Задача о замене оборудования. Установленные на ВЦ предприятия ЭВМ после К лет эксплуатации могут оказаться в следующем состоянии: υ1 – ЭВМ вполне работоспособно и требует только небольшого текущего ремонта; υ2 – некоторые устройства значительно износились и требуют серьезного ремонта или замены; υ3 – основные устройства износились настолько, что дальнейшая эксплуатация ЭВМ невозможна. Прошлый опыт эксплуатации технических средств ВЦ показывает, что 20% случаев оно может находиться в состоянии υ1, в 50% случаев в состоянии υ2 и в 30% случаев - υ3. Для предприятия возможны три различных способа действия: а1 – оставить ЭВМ в работе еще на год, проведя незначительный ремонт своими силами; а2 – провести капитальный ремонт технических средств ВЦ с вызовом сторонних специалистов; а3 – заменить технические средства ВЦ новыми. Априорные вероятности состояний природы (технических средств ВЦ) и потери в задаче о замене оборудования приведены в таблице 1. Таблица 1.
В величину потерь входят стоимость ремонта или замены технических средств (ТС) ВЦ, а также убытки, связанные с неисправностями в ТС. В этой же таблице приведены априорные вероятности различных состояний ТС ВЦ (природы), т.е. смешенная стратегия природы ε(ν). Для заданной смешанной стратегии ε(ν) средние потери при различных способах действия составят (5): L(ε, a1) = ∑L(ν,a) ε(ν)=1*0,2+5*0,5+7*0,3=4,8; ν L(ε, a2)=3,4; L(ε, a3)=3,9. Необходимо выбрать чистую стратегию а2 , при которой средние потери минимальны. Контрольные вопросы 1. Модели систем массового обслуживания. Область применения. 2. Определение вероятности длины очереди заявок и математического ожидания длины очереди. 3. Особенности статистических игр, в каких практических ситуациях они используются, приведите примеры. 4. Понятия чистой и смешанной стратегий статиста. Определение наилучшей стратегии действий. Лекция 12 Введение в теорию нечетких множеств. Выбор при нечеткой исходной информации  1. Введение в теорию нечетких множеств Для начала дадим определение нечеткого множества, чтобы определить тот объект, с которым мы будем работать на протяжении всех лекций. В математике давно используется понятие множества – совокупности объектов, выделенных по некоторому признаку. Это понятие является базовым в современной математике и потому не определяется строго, формально. Так, если задано некоторое базовое множество X (конечное или бесконечное), то его подмножеством (четким подмножеством) A называется любое множество, содержащее в себе только элементы множества X (хотя, может быть, и не все его элементы). Любое подмножество A множества X можно описать его функцией принадлежности μA: X →{0; 1}, значение которой для элемента x€X равно единице в том случае, еслиэтот элемент принадлежит множеству A, и нулю – в противном случае. Соответствие между подмножествами множества X и всевозможными функциями принадлежности μ : X →{0; 1}является взаимно однозначным, то есть, определив некоторое подмножество, мы можем определить его функцию принадлежности, и обратно, задание функции μA: X →{0; 1}задает и подмножество множества X. В четком множестве любой элемент может или принадлежать ему, или не принадлежать, поэтому функция принадлежности принимает лишь два возможных значения ноль или единица. В нечетком же множестве (точнее, в нечетком подмножестве базового множества X) любой элемент x € X может принадлежать множеству с некоторой степенью достоверности, принимающей значения от нуля (элемент достоверно не принадлежит множеству) до единицы (элемент достоверно принадлежит множеству). Соответственно и функция принадлежности нечеткого множества может принимать любое значение из отрезка [0; 1]. Мы определим понятие нечеткого множества через его функцию принадлежности. Пусть X – некоторое обыкновенное (четкое) множество. В дальнейшем мы будем рассматривать его нечеткие подмножества. Определение 1. Нечетким множеством A в X называется функция μA: X →{0; 1}, которая каждому из элементов множества X ставит в соответствие степень его принадлежности нечеткому множеству A . Нечеткое множество A называется нормальным, если sup μ A (х) x X В противном случае оно называется субнормальным. Носителем supp A нечеткого множества A называется обычное множество supp A := {x€ X : μ A (x) > 0} . Пример 1. Пусть множество X – это множество всех действительных чисел. Множество A чисел, больших нуля, будет его четким подмножеством с функцией принадлежности x μA(x) 0, x  Мы можем определить нечеткое множество A чисел, «много больших нуля», задав его функцию принадлежности μ A , например, следующим образом: x μA (x)x 0,5- 0,5cos(πx/100) , 0 Действительно, числа, меньшие нуля, достоверно не являются много большими нуля, поэтому функция принадлежности в этих точка равна нулю. (Далее нечеткие объекты (множества, отношения и т.д.) будут обычно обозначаться волной). Числа, большие ста, в большинстве приложений (будем считать, что и в нашем случае), достоверно считаются много большими нуля, поэтому функция принадлежности для таких чисел равна единице. По поводу же чисел в интервале между 0 и 100 достоверно сказать, что они являются много большими нуля, нельзя, поэтому функция принадлежности на этом интервале принимает значения между нулем и единицей. В то же время понятно, что чем больше число, тем больше у нас оснований считать его много большим нуля. Поэтому на интервале от нуля до ста функция принадлежности монотонно возрастает. Носителем нечеткого множества A является интервал (0; + ∞) . Функции принадлежности множеств A и A приведены на рисунке 1.  A 1,0       A 0,0 x   100 Рисунок 1. Сравнение функций принадлежности четких и нечетких множеств Теория нечетких множеств была впервые предложена американским математиком Лотфи Заде в 1965 г. и предназначалась для преодоления трудностей представления нечетких понятий, анализа и моделирования систем, в которых участвует человек [11]. Подходы на основе нечетких множеств имеют три основные отличительные черты: 1) вместо и в дополнение к числовым переменным используются нечеткие величины и так называемые «лингвистические» переменные; 2) простое отношение между переменными описывается с помощью нечетких высказываний; 3) сложные отношения описываются нечеткими алгоритмами. Такой подход дает приближенный, но в то же время эффективные способы описания поведения системы, настолько сложных и плохо определенных, что они не поддаются точному математическому анализу. Пример 2. В теории принятия решений часто приходится оценивать различные величины, имеющиеся в распоряжении лица, принимающего решение (ЛПР): ресурсы, параметры внешней среды и др. Рассмотрим, например, коммерческую фирму, которая рассматривает возможность проведения рекламной кампании своей продукции. Для того чтобы принять обоснованное решение, фирме необходимо предсказать, как проведение кампании скажется на продажах. Таким образом, руководству фирмы необходимо оценить изменение суммы продаж в результате проведения рекламной кампании. Если фирма имеет обширный опыт подобной деятельности, у нее могла накопиться статистика динамики продаж в зависимости от проводимых рекламных акций. В этом случае можно считать увеличение продаж случайной величиной и положить в основу оценки ее вероятностное распределение [12]. Однако понятно, что статистика, необходимая для построения диаграммы распределения, огромна. Стоит также учитывать, что каждая рекламная кампания уникальна – меняется товар, изменяются конкуренты, вкусы и доходы потребителей, и для принятия обоснованного решения необходимо учитывать существующую в данный момент комбинацию этих факторов, которая даже в фирмах-долгожителях раньше встречалось не более нескольких раз. Таким образом, использование методов теории вероятностей при принятии подобного решения является необоснованным – информации слишком мало. Достоверность  1,00     0 100000 300000 Рисунок 2. Функция принадлежности нечеткого множества «увеличение продаж» Тем не менее, даже «бедная» статистика в сочетании с экспертными оценками позволяет сформулировать прогноз динамики продаж в терминах нечетких множеств. Пусть, например, эксперты считают, что текущие рыночные условия примерно соответствуют одной из проводимых ранее кампаний, в результате которой продажи поднялись на $100000. Таким образом, достоверно известно, что результатом кампании может быть увеличение прибыли на $100000, и, следовательно, степень принадлежности точки $100000 нечеткому множеству «увеличение продаж» равна единице. Также эксперты считают, что, с одной стороны, кампания не приведет к уменьшению продаж, с другой же стороны, не стоит рассчитывать на увеличение прибыли более $300000. Нечеткое множество «увеличение продаж» тогда могло бы выглядеть так, как показано на рисунке 2. 2. Задача достижения нечеткой цели Задача формулируется так. Есть множество X возможных действий ЛПР и множество Y состояний управляемой системы. ЛПР в различной степени устраивают различные состояния системы – он стремится достичь своей цели, задаваемой нечетким подмножеством G € Y . Для достижения своей цели ЛПР выбирает действия так, чтобы удовлетворить ограничениям на действия, задаваемым нечетким подмножеством C € X . Состояние, в которое переходит система в зависимости от действия ЛПР, описывается нечетким отображением f: X→Y. Задача ЛПР состоит в том, чтобы определить действие (возможно, нечеткое), которое позволило бы ему одновременно достичь цели G и удовлетворить ограничениям C . Предположим, что отображение f – тождественное, и множество действий совпадает с множеством результатов. В этом случае и цель и ограничения являются подмножествами одного и того же множества X, а нечеткое множество D действий, которые одновременно и достигают цели, и удовлетворяют ограничениям, равно пересечению (Аналогично тому, как пересечение множества синих автомобилей и множества автомобилей марки «Лада» дает «множество синих автомобилей марки «Лада») нечетких множеств цели и ограничений, D =G ∩C . Тогда множество D и является решением задачи достижения нечеткой цели. Пример 3. Рассмотрим задачу, с которой периодически сталкивается каждый студент – задачу подготовки к экзамену. Пусть множество X = {1; 2; 3; 4; 5} задает возможные уровни подготовки к экзамену (большее значение соответствует более интенсивной подготовке), а множество Y = {1; 2; 3; 4; 5} описывает возможные исходы экзамена (оценки). Пусть студента одинаково устраивает как оценка 4, так и 5 (наш студент не гонится за отличной оценкой), но категорически не устраивают оценки 1 или 2. Оценка 3 студента устраивает лишь частично. Тогда цель студента можно описать нечетким множеством G , функция принадлежности которого приведена в следующей таблице.
В то же время (в связи с недостатком времени или способностей) студент ограничен в возможностях подготовки к экзамену, и если возможность подготовки на уровне 1 и 2 не вызывает сомнений, то большие уровни подготовленности уже более сомнительны. В следующей таблице приведена функция принадлежности нечеткого множества ограничений C .
Предположим, что отображение, переводящее действия в результат, тождественное, то есть уровень подготовки однозначно определяет оценку на экзамене – уровень подготовки 1 приводит к оценке 1, уровень подготовки 2 – к оценке 2 и так далее. Тогда задача выбора действия, достигающего цели с учетом ограничений, сводится к нахождению пересечения D =G ∩C множеств цели и ограничений. Функция принадлежности множества D приведена ниже.
Таким образом, решение задачи достижения нечеткой цели само оказывается нечетким. Эта нечеткость является прямым следствием нечеткости в постановке задачи и может интерпретироваться как нечеткая рекомендация вида «готовиться примерно на 4». Но ведь в реальности то принимается единственное решение! И отдельного рассмотрения требует вопрос о конкретном действии, выбираемом на основе нечеткой рекомендации. Часто в качестве четкого решения задачи достижения нечеткой цели предлагается выбор действия, имеющего максимальную степень принадлежности нечеткому решению – множеству D . Так, в рассмотренном примере четкая рекомендация состоит в том, чтобы готовиться «на четверку». Однако более осторожным и обоснованным представляется подход, в котором ЛПР предоставляется сама нечеткая инструкция, как результат решения нечетко формализованной задачи и дальнейший выбор действия на основе этой рекомендации ЛПР осуществляет самостоятельно, основываясь, возможно, на информации, не нашедшей отражения в модели. Однако каким образом искать решение задачи в том случае, когда отображение f не является тождественным? В этом случае нечеткие подмножества ограничений C и цели G непосредственно не сравнимы, так как являются подмножествами разных пространств, X и Y соответственно. Однако мы можем отобразить множество цели G во множество действий, найдя его прообраз g при отображении f – нечеткое множество действий, приводящих к заданной нечеткой цели без учета ограничений. Тогда, аналогично рассмотренному выше случаю, решением задачи будет пересечение g ∩C прообраза цели с множеством ограничений. В заключение следует отметить, что различие между нечеткостью и случайностью приводит к тому, что математические методы нечетких множеств совершенно не похожи на методы теории вероятностей. Они во многом отношении проще вследствие того, что понятию вероятностной меры в теории вероятностей соответствует более простое понятие функции принадлежности в теории нечетких множеств. По этой причине даже в тех случаях, когда неопределенность в процессе принятия решения может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами теории нечетких множеств без привлечения аппарата теории вероятностей. Контрольные вопросы 1. Определение четкого и нечеткого множеств. 2. Сравните функции принадлежности четких и нечетких множеств. 3. Формулирование задачи достижения нечеткой цели. 4. Понятия нечеткой цели, нечетких ограничений, нечеткого множества действий. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||