Курс лекций по теме Управление в МИСО (1996) (1264200), страница 8

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

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

Нужно перебрать (n-1) вариантов. Эта задача близка к задаче по назначению, когда Xij = 1.Условия:1. Найти цикл на базе значения вектора состояния Xij.2. Xij = {0; 1}1 - переход из i в j;0 - отсутствие перехода.3. Условие перехода (критерий)max Cij XijCij - цена ребра.4. Система ограниченийi Xij = 1j Xij = 15. Решение задачи - замкнутый цикл.Для решения задачи используется целочисленное программирование,например, метод «ветвей и границ».

В нем различают:• исключение подциклов;• задание маршрутов;• алгоритм частичных циклов (Вагнер 2 том, стр. 274-283)Страница 41Рассмотрим 1-й алгоритм на основе применения метода «ветвей и границ»:Решаязадачу симплексным методом размещения, получим:X15 = X51 = X23 = X34 = X42 = 1C15 + C51 + C23 + C34 + C42 = 60ВИз123451234518141010910825102425251520271021015Решение не удовлетворяет условию 5, это не цикл, а 2 подцикла.

Применим метод ветвей и границ с исключение подциклов. Алгоритм состоит из kитераций. В начале каждой итерации известна верхняя граница значения целевой функции из предыдущей итерации XK0.На первой итерации в качестве X10 =Cij - достаточно большая сумма. Вначале каждой итерации известен список задач назначения (условие 14) с различными Cij = .На первой итерации список состоит из исходной задачи о назначении, акаждая k-ая итерация состоит из следующих шагов:шаг 1 прекратить вычисления, если основной список пуст.

Если не пуст, выбрать 1-ую задачу, вычеркнув ее из списка.шаг 2 решить выбранную задачу о назначении.Если I0  XK0, то принять XK+10 = XK0 и перейти к шагу 1.шаг 3 если полученное оптимальное решение является циклом, то зафиксировать его, принять XK+10 = I0 и вернуться к шагу 1 (чтобы получить ещеменьше I0).

Если решение ациклическое, то переходим к шагу 4.шаг 4 останавливаться в найденном оптимальном решении на подцикле с минимальным числом пунктов.Для каждого Xij = 1 этого подцикла можно поставить новую задачу оназначении, приняв Cij = , принимаем XK+10 = XK0 отсюда к шагу 1. Перераспределение исходной таблицы необходимо для разрушения подциклов.Пример.1 итерацияX10 = C12 + C23 + C34 + C45 + C51 = 65шаг 1 - основной список содержит 1 задачу (к = 1).шаг 2 - решаем эту задачу.I0 = 60 < X10 = 65шаг 3 - решение - не цикл, переходим к шагу 4.шаг 4 - нужный подцикл (с минимальным числом пунктов) X15 = X51, разрушимего: С15 = - задача 2 (вносим в список);С51 = - задача 3 (в список).Страница 422 итерацияшаг 1 - рассмотрим задачу 2 (к = 2).шаг 2 - решаем I0 = X10  X30 = 65.3 итерацияшаг 1 - задача 3шаг 2 - решаем задачу:I0 = 62 < X30шаг 3 - решение - цикл (X15 = X52 = X23 = X34 = X41 = 1) принимаем X30= I0 = 624 итерацияшаг 1 - задач больше нет (заполненный цикл - оптимальное решение задачи).Блок-схема решения:началоЗадача 1К=1X10 =65= 60С15 = С51 = Задача 2К=2X20 =65= 65Задача 3К=3X30 =62= 62остановкаЗадача выбора кратчайшего пути в сетях (сетевом графе).Данная задача отличается от предыдущей тем, что граф обладает единственной начальной точкой и единственной конечной и имеется множество путей перехода из начальной в конечную точку при наличии внутренних узлов.Математически задача содержат условия 1), 2), 3), где С - стоимость,время или расстояние на ребре, 5) - условия нет.4) Xk j −  Xikji 1 k =1=  0 1 k  n− 1 k = nЭта задача является частным случаем задачи о назначении.

Для ее решения имеется множество алгоритмов. Один из алгоритмов разберем на примере.Страница 43Пример.Рассмотрим графический вариант задачи:b233cf1d93ni45154385122ke3a42922546mh1. Проведем все ребра до последнего пункта, в который можно попасть непосредственно.2. Проведем сравнительный анализ прямого и непрямого пути к каждому узлу.Кратчайший путь → и его стоимость поставим над пунктом.3.

Добавить все узлы, в которые можно попасть непосредственно из узлов на 1ом шаге. Повторить пункты 1 и 2.4. Повторяем процедуры 1, 2, 3 пока не появляется последний узел.Элементы теории массового обслуживания.Определения СМО и ТМО.СМО - многомерная многоканальная система управления потоками входных сигналов (заявок). Эта система предназначена для эффективного выполнения операций массового обслуживания.Операция массового обслуживания - например организация с помощьюсистемы ПВО поражения потока бомбардировщиков противника или функционирование ЭВМ с множествам заявок и с 1 или несколькими процессорами.Каждое СМО состоит из некоторого числа обслуживающих единиц (каналов обслуживания). Например, это число процессоров в ЭВМ, число комплексов наведения ЗУР и т.д.СМО предназначается для обслуживания потока заявок.Заявки - это поток боевых групп противника, поток задач, решаемых ЭВМ.Каждое СМО обладает определенной пропускной способностью - среднеечисло заявок, которое СМО обслуживает в единицу времени.Страница 44Предметом теории массового обслуживания является исследование зависимостей между потоком заявок, числом каналов, правилами работы СМО, эффективностью обслуживания и т.д.

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

Системы с отказом (заявка поступила в СМО, каналы заняты...).2. Системы с ожиданием• с неограниченным;• с ограниченным;II.По числу каналов:1. одноканальные;2. многоканальные;III. По характеру моделей:1. марковские СМО (потоки событий, заявок, пуассоновские потоки);2.

немарковские СМО;IV. По характеру связей между каналами:1. несвязанные;2. многосвязные.2. Марковские СМО с отказом.А. ОдноканальныеS0S1S0 - канал свободен;S1 - канал занят и заявке отказано.,() - интенсивность (обслуживания) потока заявок.Найдем относительную q и A абсолютную пропускную способность: q =А - среднее число обслуживания заявок.Страница 45A, где•p 0 = −   p 0 +   p1•p =   p −   p01 1p0 + p1 = 1p1 =  + p =  0  + решение p0 = q, т.к. частотный смысл обоих совпадает.

Тогда А = q  A =++Вероятность отказа p отк = p1 =++1p1p0tМы получили простейший набор показателей, которые полностью определяются характеристиками СМО.Б. МногоканальныеИмеется n каналов обслуживания.S0 - все каналы свободны;S1 - 1 занят, (n-1) свободны;…Sn - все заняты.S0S12nSnТипичная схема гибели - размножения.Используя известную схему управления, получим:( /  )k1pk =p0 =p0p0 =  2n k!( /  ) ( /  )2( /  ) n1++++1!2!n!=  - число заявок, пришедших в систему за время обслуживания 1 заявки(1/ - время обслуживания 1 заявки).1Apk = k p0; p0 =p ОТК = p n = n p 0 ; q = 1 − p ОТК = ; A = q;n ;k!n!1 + ++1!n!Среднее число занятых каналов (вычислено как дискретное матожидание):Z = 0p0 + 1p1 + … + npn = (1-pn)3. Марковские СМО с неограниченным ожиданием в очереди.А. ОдноканальныеИмеется n каналов обслуживания.S0S1Sm+1S1 - канал занят, очередь пуста;S2 - занят, 1 заявка в очереди;…Sm+1 - m заявок в очереди.Опять имеем схему гибели - размножения.Страница 46Очередь ограничена (число мест), а время ожидания - не ограничено. p1 =   p 0 =   p 0  11 p0 = = 1  p0 =m +12m +21 + 0 +  ++p m +1 =  m +1  p 0 p ОТК = p m +1 =  m +1p 0 ;r = 1p2 + 2p3 +…+ mpm+1k =r + = 0p0 + 1(1-p0)tОЖ = r /Пример.q = 1 − p ОТК ;A = q = q (1- p ОТК )- средняя длина очереди:- среднее число заявок в системе:- среднее число заявок на обслуживание.- среднее время ожидания в очереди.Элементарная система ПВО - это система СМО с 1 каналом обслуживания.

Стартовая позиция допускает пребывание в очереди на обслуживание (наподлете) не более 3-х целей. 4-я цель в очереди обслуживаться не будет. = 1 мин.PОТК; q;Дано:Найти: = 1/ t обслk;t обсл = 1.25 мин.A;r;t ОЖ; = 0.8 = 1/ 0.8 = 1.25PОТК = p4 = 0.297q = 1- PОТК = 0.703p0 = 0.122p1 = 0.152p2 = 0.191p3 = 0.238p4 = 0.237r = 1.56k = r +  = 2.44t ОЖ = r / = 1.56 мин.Б. МногоканальныеS0S12nSnnnn - число каналов;m - длина очереди.S0 - каналы свободны;S1 - занят 1, очередь пуста;…Sn - все каналы заняты, очереди нет;…Sm+n - m заявок в очереди.kpk =p ;k! 0k = 0 nn +kpk = k p0;nk = n + 1 n + mДля этой цепи можно аналогично посчитать А, q,r,k ...Страница 47Sm+n4. Марковские СМО с ограниченным ожиданием.Марковские цепи с ограниченным ожиданием характеризуются тем, чтозаявка, пробыв некоторое время в очереди, покидает ее и время пребывания вочереди есть некоторая случайная величина Т. Тогда среднее время ухода изочереди tух = M(T);  = 1/ tух - интенсивность ухода.Граф многоканальных СМО с очередью и ограниченным ожиданием:S0S12nSnn+Sn+1n+2n+mSm+nИнтенсивность продвижения в очереди увеличивается из-за появившейсяинтенсивности ухода: частный случай, когда m → PОТК = 0; q = 1 – PОТК = 1; q = A/; A =  и т.д.5.

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

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