Лекционный курс от Русакова (1087061), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Но из–за случайных характеристик потока заявок иногда работаютстанок (одновременно все три станка (), отсюда 9 % отказов.Возможные постановки задач оптимизации n – канальных СМО сотказами1. Определить оптимальное число каналов, обеспечивающее минимумзатрат на систему, при условии достижения требуемого уровня еебезотказной работы.. Целевая функция (затраты наПример. ПустьСМО) запишется:Решение:, где. Найти:.или.По другому можно записать:.Последнее равенство начинает выполняться при, т.к.;;;.2. Определить оптимальное число каналов, обеспечивающее максимумприбыли от эксплуатации СМО в единицу времени.Содержание каждого канала в единицу времени обходится в какую–то сумму.Чем больше каналов, тем больше затраты на эксплуатацию СМО. Вместе с тем, чембольше каналов (при и), тем больше доля обслуживаемых заявок.

Акаждая обслуженная заявка дает определенный (пусть постоянный) доход вединицу времени. При увеличении числа каналов растут доходы D, но растут ирасходы на эксплуатацию СМО – R. Чтобы решить эту задачу, необходимо найти, обеспечивающее максимум целевой функцииоптимальное число каналов, т.е. нужно максимизировать прибыль в единицу времени.Сетевые модели (N-схемы). Сети Петри1.

Теоретические основы сетей Петри: принципы построения, алгоритмыповедения.Сети Петри были разработаны и используются для моделирования систем,которые содержат взаимодействующие параллельные компоненты, напримераппаратное и программное обеспечение ЭВМ, гибкие производственныесистемы, а также социальные и биологические системы. Впервые сети Петрипредложил Карл Адам Петри в своей докторской диссертации "Связьавтоматов" в 1962 году.

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

Сети Петри делаютвозможным моделирование системы математическим представлением ее в видесети Петри. Математическим аппаратом сетей Петри является теориякомплектов. Теория комплектов представляет собой естественное расширениетеории множеств. Как и множество, комплект является набором элементов изнекоторой области.

Однако в отличие от множества комплекты допускаютналичие нескольких экземпляров одного и того же элемента. В отличие отмножества, где элемент либо является элементом множества, либо нет, вкомплект элемент может входить заданное число раз. Пусть областьпредставляет собой {a,b,c,d}, тогда комплекты над этой областью будут иметьвид:B1={a,b,c} B2={a}B3={a,b,c,c}B4={a,a,a} B5={b,c,b,c} B6={c,c,b,b}B7={a,a,a,a,a,a,b,b,b,b,b,c,d,d,d,d,d}Основным понятием теории комплектов является функция числа экземпляров.Обозначение #(x,B) число х в В т.е.

число экземпляров элемента х в В. Еслиограничить число элементов в комплекте так, что 0 <= #(x,B) <= 1, то получимтеорию множеств.Элемент х является членом комплекта В, если #(x,B) > 0. Аналогично, если#(x,B) = 0 то х не принадлежит В.Определим пустой комплект 0, не имеющий членов ( для всех х : #(x,0) = 0 ).Под мощностью |В| комплекта В понимается общее число экземпляров вкомплекте |B| = x #(x,B).Комплект А является подкомплектом комплекта В (обозначается АВ ), есликаждый элемент А является элементом В по крайней мере не больше число раз,т.е. АВ тогда и только тогда, когда #(x,A) <= #(x,B) для всех х.Два комплекта равны (А = В), если #(x,A) = #(x,B).Комплект А строго включен в комплект В (АВ), если АВ и А не равно В.Над комплектами определены 4 операции.

Операции для двух комплектов А иВ:1 объединение АВ: #(x,AB) = max (#(x,A),#(x,B));2 пересечение А В: #(x,A B) = min (#(x,A),#(x,B));3 сумма А + В: #(x,A + B) = #(x,A)+#(x,B);4 разность А - В: #(x,A - B) = #(x,A) - #(x,B);Назовем множество элементов, из которых составляются комплекты, областьюD. Пространство комплектов Dn есть множество всех таких комплектов, чтоэлементы их принадлежат D и ни один из элементов не входит в комплект болееn раз. Иначе говоря, для любого В  Dn :а) из х  В следует х  D;б) для любого х #(x,B) <= n.Множество D есть множество всех комплектов над областью D, без какоголибо ограничения на число экземпляров элемента в комплекте.1.2 Структура сети Петри.Сеть Петри состоит из 4 компонентов, которые и определяют ее структуру:- множество позиций Р,- множество переходов Т,- входная функция I,- выходная функция О.Входная и выходная функции связаны с переходами и позициями.

Входнаяфункция I отображает переход tj в множество позиций I(tj), называемыхвходными позициями перехода. Выходная функция О отображает переход tj вмножество позиций О(tj), называемых выходными позициями перехода. Т.е.( I : T -> P)(O : T -> P).Определение 1. Сеть Петри С является четверкой С = (P,T,I,O) гдеР={p1,p2,...,pn} конечное множество позиций, n>=0.T={t1,t2,...,tm} конечное множество переходов, m>=0.Множества позиций и переходов не пересекаются.I : T -> P является входной функцией отображением из переходов в комплекты позиций.O : T -> P выходная функция - отображение из переходов вкомплекты позиций.Мощность множества Р есть число n, а мощность множества Т есть число m.Произвольный элемент Р обозначается символом pi, i=1...n; а произвольныйэлемент Т - символом tj, j=1...m.Pitjрис.

1Позиция pi является входной позицией перехода tj, в том случае, если pi  I(tj);pi является выходной позицией перехода, если pi  O(tj).tjPiрис. 2Входы и выходы переходов представляют комплекты позиций. Кратностьвходной позиции для перехода tj есть число появлений позиции во входномкомплекте перехода #(pi,I(tj)). Аналогично, кратность выходной позиции pi дляперехода tj есть число появлений позиции в выходном комплекте перехода#(pi,O(tj)).Определим, что переход tj является входом позиции pi, если pi есть выход tj(рис.

2). Переход tj есть выход позиции pi, если pi есть вход tj (рис. 1).Определение 2. Определим расширенную входную функцию I и выходнуюфункцию О таким образом, что #(tj,I(pi)) = #(pi,O(tj)); #(tj,O(pi)) = #(pi,I(tj));1.3 Графы сетей Петри.Для иллюстрации понятий теории сетей Петри гораздо более удобнографическое представление сети Петри. Теоретико - графовым представлениемсети Петри является двудольный ориентированный мультиграф.

В соответствиис этим граф сети Петри обладает двумя типами узлов:кружок O является позицией,планка | является переходом.Ориентированные дуги соединяют позиции и переходы. Дуга направленная отпозиции pi к переходу tj определяет позицию, которая является входом переходаtj. Кратные входы в переход указываются кратными дугами из входных позицийв переход. Выданая позиция указывается дугой от перехода к позиции. Кратныевходы также представлены кратными дугами.Определение 3.

Граф G сети Петри есть двудольный ориентированныймультиграф G=(V,A) гдеV = {v1,V2,...,vs} - множество вершинА = {a1,a2,...,ar} - комплект направленных дуг,ai={vj,vk} где vj,vk  V.Множество V может быть разбито на 2 непересекающихся подмножества Р и Т,таких что P T = 0, и если ai = (vj,vk), тогда либо vj  P и vk  T, либо vj T и vk P.Сеть Петри есть мультиграф, т.к. он допускает существование кратных дуг отодной вершины к другой. Т.к. дуги направлены, то это ориентированныймультиграф.

Граф является двудольным, т.к. он допускает существованиевершин двух типов: позиций и переходов.1.4 Пример. Представление сети Петри в виде графа и в виде структурысети Петри.Пусть задана следующая структура сети Петри: C = (P,T,I,O), n=5, m=4P = {p1,p2,p3,p4,p5}I(t1)={p1}I(t2)={p2,p3,p5}I(t3)={p3}I(t4)={p4}T = {t1,t2,t3,t4}O(t1)={p2,p3,p5}O(t2)={p5}O(t3)={p4}O(t4)={p2,p3}Для сети, изображенной на рис.

3 расширенными входной и выходнойфункциями являются:P2P1t1t4P5 t2P4t3P3I(p1)={}I(p2)={t1,t4}I(p3)={t1,t4}I(p4)={t3}I(p5)={t1,t2}рис. 3O(p1)={t1}O(p2)={t2}O(p3)={t2,t3}O(p4)={t4}O(p5)={t2}Пример 2. Пусть задана следующая структура сети Петри: C = (P,T,I,O)P={p1,p2,p3,p4,p5,p6} T={t1,t2,t3,t4,t5} n=6, m=5.I(t1)={p1}O(t1)={p2,p3}I(t2)={p3}O(t2)={p3,p5,p5}I(t3)={p2,p3}O(t3)={p2,p4}I(t4)={p4,p5,p5,p5} O(t4)={p4}I(t5)={p2}O(t5)={p6}P2t5P6P1 t1P4P3t2t3P5t4рис.

4Заметим, что оба представления сети Петри - в виде структуры и в виде графа эквивалентны. Их можно преобразовать друг в друга.1.4 Маркировка сетей Петри.Маркировка  есть присвоение фишек позициям сети Петри. Фишка - это однаиз компонент сети Петри (подобно позициям и переходам). Фишкиприсваиваются позициям. Их количество при выполнении сети можетизменяться. Фишки используются для отображения динамики системы.Маркированная сеть Петри есть совокупность структуры сети Петри C =(P,T,I,O) и маркировки  и может быть записана в виде M = (P,T,I,O, ).

Характеристики

Список файлов лекций