Portanto, 13% do canal ficará ocioso por uma hora, o tempo ocioso é igual a t pr = 7,5 min.
A probabilidade de que o serviço:
canal 1 ocupado:
p 1 = ρ 1 /1! p0 = 2,1 1/1! 0,13 = 0,26
2 canais estão ocupados:
p 2 = ρ 2 /2! p 0 = 2,1 2 /2! 0,13 = 0,28
3 canais estão ocupados:
p 3 = ρ 3 /3! p0 = 2,1 3/3! 0,13 = 0,19
4 canais estão ocupados:
p 4 = ρ 4 /4! p 0 = 2,1 4/4! 0,13 = 0,1
5 canais estão ocupados:
p 5 = ρ 5 /5! p 0 = 2,1 5 /5! 0,13 = 0,0425 (probabilidade de todos os links estarem ocupados)
4. Proporção de pedidos rejeitados.
Isso significa que 4% dos pedidos recebidos não são aceitos para atendimento.
5. Probabilidade de atender solicitações recebidas.
Em sistemas com falhas, os eventos de falha e manutenção constituem um grupo completo de eventos, portanto:
p aberto + p obs = 1
Rendimento relativo: Q = p obs.
p obs \u003d 1 - p otk \u003d 1 - 0,0425 \u003d 0,96
Consequentemente, 96% dos pedidos recebidos serão atendidos. O nível de serviço aceitável deve estar acima de 90%.
6. Número médio de linhas de comunicação ocupadas
n z = ρ p obs = 2,1 0,96 = 2,01 linhas.
Canais ociosos médios.
n pr \u003d n - n z \u003d 5 - 2,01 \u003d 3 canais.
7. Taxa de ocupação do canal de atendimento.
K 3 \u003d n 3 / n \u003d 2,01 / 5 \u003d 0,4
Portanto, o sistema está 40% ocupado com manutenção.
8. Largura de banda absoluta.
A = p obs λ = 0,96 0,6 = 0,57 solicitações/min.
9. Tempo médio de inatividade do QS.
t pr \u003d potk t obs \u003d 0,0425 3,5 \u003d 0,15 min.
12. Número médio de solicitações atendidas.
L obs = ρ Q = 2,1 0,96 = 2,01 unidades
Para determinar o número ideal de linhas de comunicação, suficiente para garantir que a probabilidade de falha não exceda 0,04, usamos a fórmula:
Para nossos dados:
Onde 
Selecionando o número de linhas de conexão, descobrimos que em k = 6, popen = 0,0147< 0.04, p 0 = 0.12
Baixar solução
1. Uma empresa comercial exerce actividades de intermediação de venda de viaturas e realiza parte das negociações em 3 linhas telefónicas. Em média, são recebidas 75 chamadas por hora. O tempo médio de negociações preliminares de natureza de fundo é de 2 minutos.
2. A oficina de reparação de apartamentos funciona em modo de avaria e é constituída por duas equipas. A intensidade do fluxo de solicitações λ, a produtividade do ponto μ. Determine a probabilidade de que ambos os canais estejam livres, um canal esteja ocupado, ambos os canais estejam ocupados, a probabilidade de falha, os rendimentos relativos e absolutos, o número médio de equipes ocupadas.
3. O centro de informática de uso coletivo com três computadores recebe encomendas de empresas para trabalhos de informática. Se todos os três computadores estiverem funcionando, o novo pedido recebido não será aceito e a empresa será forçada a recorrer a outro centro de computação. O tempo médio de trabalho com um pedido é de 3 horas e a intensidade do fluxo de aplicações é de 0,25 (1/h). Encontre as probabilidades limitantes de estados e indicadores de desempenho do centro de computação.
2. Um fluxo de clientes entra no minimercado com intensidade de 6 clientes por 1 minuto, que são atendidos por três caixas controladores com intensidade de 2 clientes por 1 minuto. o comprimento da fila é limitado a 5 clientes.
3. Na base de frutas e legumes, em média, após 30 minutos. carros chegam com frutas e legumes. O tempo médio de descarga de um caminhão é de 1,5 horas, sendo a descarga realizada por duas equipes. No território da base no estágio de desembarque, não mais de 4 veículos podem estar na fila aguardando o descarregamento.
4. Uma média de 9 carros chegam ao lava-jato por hora, mas se já houver 4 carros na fila, os clientes recém-chegados, via de regra, não fazem fila, mas passam. O tempo médio de lavagem do carro é de 20 minutos, e há apenas dois locais de lavagem. O custo médio de uma lavagem de carro é de 70 rublos. Determinar valor médio perda de receita de lavagem de carros durante o dia.
5. A loja recebe hortaliças de estufas. Caminhões com carga chegam com intensidade λ carros por dia. Despensas permitem que você processe e armazene mercadorias trazidas m carros. Trabalhe na loja n embaladores, cada um dos quais, em média, pode processar mercadorias de uma máquina durante t serviço horas. A jornada de trabalho por turnos é de 12 horas. Determine a capacidade das salas de serviço para um determinado serviço de probabilidade P*. processamento completo de mercadorias.
6. Há um posto de gasolina com 2 colunas. Não pode haver mais de 3 carros na fila. A intensidade e o tempo médio de preenchimento são 2,1 e 0,55. Encontre a probabilidade de tempo de inatividade do sistema.
Solução:
A taxa de fluxo de serviço é μ = 1/0,55 = 1,82. Assim, a intensidade da carga será ρ = λ t obs = 2,1 0,55 = 1,16. Observe que a intensidade de carga ρ=1,16 mostra o grau de consistência entre os fluxos de entrada e saída das solicitações do canal de atendimento e determina a estabilidade do sistema de filas.
Desde 1.16<2, то процесс обслуживания будет стабилен.
A probabilidade de tempo de inatividade do sistema é expressa pela seguinte fórmula:
1. Construir dois modelos de um sistema de filas multicanal - com fila infinita e fila limitada. Calcule P 0 - a probabilidade de ociosidade de todos os canais de atendimento, n w - o número médio de clientes aguardando atendimento, t w - o tempo médio de espera por atendimento, W - a probabilidade de permanência obrigatória na fila.
2. Existem 3 caixas no terminal de checkout da loja de autoatendimento. a intensidade do fluxo de entrada é de 5 compradores por minuto. a intensidade de atendimento de cada controlador-caixa é de 2 clientes por minuto.
Recomendações para resolver o problema: aqui n = 3; λ = 5 unidades em minutos; µ = 2 unidades em min.
Conforme o número de pedidos na fila, você pode especificar, por exemplo, m = 4. Então será calculada a probabilidade correspondente do aparecimento desses pedidos.
3. A firma de auditoria recebe o fluxo mais simples de solicitações de serviço com intensidade de λ = 1,5 solicitações por dia. O tempo de serviço é distribuído de acordo com a lei exponencial e é igual a três dias em média. A firma de auditoria tem cinco contadores independentes que realizam auditorias (serviço de aplicação). A fila de aplicativos não é limitada. A disciplina de fila não é regulamentada. Determinar as características probabilísticas de uma firma de auditoria como sistema de filas operando em modo estacionário.
4. Existem n artesãos trabalhando em uma oficina de conserto de geladeiras. Em média, λ refrigeradores são recebidos para conserto durante o dia. O fluxo de pedidos é Poisson. O tempo de reparo está sujeito a uma lei de distribuição de probabilidade exponencial, em média, durante o dia com jornada de sete horas, cada um dos mestres conserta μ geladeiras.
É necessário determinar: 1) a probabilidade de que todos os mestres estejam livres de conserto de refrigeradores, 2) a probabilidade de que todos os mestres estejam ocupados com reparos, 3) o tempo médio de reparo para um refrigerador, 4) o tempo médio de espera para o início de reparos para cada refrigerador, 5) o comprimento médio da fila, que determina o espaço de armazenamento necessário para um refrigerador que precisa de reparo, 6) o número médio de mestres livres de trabalho.
Ao resolver tarefas de comando e controle, incluindo comando e controle de tropas, muitas vezes surgem várias tarefas do mesmo tipo:
Todas essas tarefas são do mesmo tipo no sentido de que têm uma demanda massiva de serviço. Um determinado conjunto de elementos está envolvido no atendimento dessa demanda, formando um sistema de filas (QS) (Fig. 2.9).
Os elementos da OCM são:
Fluxo de entradaé uma coleção de solicitações de serviço. Muitas vezes, o aplicativo é identificado com sua operadora. Por exemplo, o fluxo de equipamentos de rádio defeituosos que entram na oficina do sindicato é um fluxo de aplicações - requisitos para serviço neste QS.
Via de regra, na prática, tratam dos chamados fluxos recorrentes, fluxos que possuem as seguintes propriedades:
Definimos as duas primeiras propriedades anteriormente. Quanto ao efeito colateral limitado, reside no fato de que os intervalos entre as aplicações recebidas são variáveis aleatórias independentes.
Há muitos fluxos recorrentes. Cada lei de distribuição de intervalos gera seu próprio fluxo recorrente. Os fluxos recorrentes também são conhecidos como fluxos do Palm.
Um fluxo com ausência completa de efeito colateral, como já observado, é chamado de fluxo de Poisson estacionário. Seus intervalos aleatórios entre solicitações têm uma distribuição exponencial:
aqui é a intensidade do fluxo.
O nome do fluxo - Poisson - vem do fato de que para este probabilidade de fluxo o aparecimento de aplicações para o intervalo é determinado pela lei de Poisson:
Um fluxo desse tipo, como observado anteriormente, também é chamado de mais simples. É esse fluxo que os designers assumem ao desenvolver um QS. Isso se deve a três razões.
Primeiramente, um fluxo desse tipo na teoria das filas é semelhante à lei da distribuição normal na teoria das probabilidades no sentido de que a passagem ao limite para um fluxo que é a soma de fluxos com características arbitrárias com um aumento infinito em termos e uma diminuição em sua intensidade leva ao fluxo mais simples. Ou seja, a soma de fluxos independentes arbitrários (sem predominância) com intensidades é o fluxo mais simples com intensidade
Em segundo lugar, se os canais de atendimento (dispositivos) forem projetados para o fluxo de solicitações mais simples, o atendimento de outros tipos de fluxos (com a mesma intensidade) será fornecido com não menos eficiência.
Em terceiro lugar, é esse fluxo que determina o processo de Markov no sistema e, consequentemente, a simplicidade da análise analítica do sistema. Para outros fluxos, a análise do funcionamento do QS é complicada.
Muitas vezes existem sistemas em que o fluxo de solicitações de entrada depende do número de solicitações que estão em serviço. Esses SMOs são chamados fechado(por outro lado - abrir). Por exemplo, o trabalho de uma oficina de comunicação de uma associação pode ser representado por um modelo QS de malha fechada. Que esta oficina seja projetada para atender as estações de rádio que estão na associação. Cada um deles tem taxa de falha. O fluxo de entrada do equipamento com falha terá intensidade:
onde é o número de estações de rádio que já estão na oficina para reparos.
Os aplicativos podem ter direitos diferentes para iniciar o serviço. Neste caso, diz-se que as aplicações são heterogêneo. As vantagens de alguns fluxos de aplicativos sobre outros são dadas pela escala de prioridade.
Uma característica importante do fluxo de entrada é o coeficiente de variação:
onde é a esperança matemática do comprimento do intervalo;
Desvio padrão de uma variável aleatória (comprimento do intervalo).
Para o fluxo mais simples 
Para a maioria dos tópicos reais.
Quando o fluxo é regular, determinístico.
O coeficiente de variação- uma característica que reflete o grau de recebimento desigual dos pedidos.
Canais de atendimento (dispositivos). Um QS pode ter um ou mais dispositivos de serviço (canais). De acordo com este QS são chamados de canal único ou multicanal.
Multicanal O QS pode consistir no mesmo tipo ou em tipos diferentes de dispositivos. Os dispositivos de serviço podem ser:
A principal característica do canal é o tempo de atendimento. Como regra, o tempo de serviço é um valor aleatório.
Normalmente, os profissionais assumem que o tempo de serviço tem uma lei de distribuição exponencial:
onde - intensidade de serviço, ;
Expectativa matemática do tempo de serviço.
Ou seja, o processo de serviço é markoviano, e isso, como sabemos agora, proporciona uma conveniência significativa na modelagem matemática analítica.
Além da exponencial, existem a distribuição -Erlang, hiperexponencial, triangular e algumas outras. Isso não deve nos confundir, pois mostra-se que o valor dos critérios de eficiência QS não depende muito da forma da lei de distribuição de probabilidade de tempo de serviço.
No estudo de QS, a essência do serviço não é considerada, qualidade de serviço.
Os canais podem ser absolutamente confiável, ou seja, não falhe. Pelo contrário, pode ser aceito no estudo. Os canais podem ter confiabilidade final. Neste caso, o modelo QS é muito mais complicado.
Fila de aplicativos. Devido à natureza aleatória dos fluxos de solicitações e serviços, uma solicitação recebida pode encontrar o(s) canal(is) ocupado(s) atendendo a solicitação anterior. Nesse caso, ele deixará o QS sem atendimento, ou permanecerá no sistema, aguardando o início de seu serviço. Assim, há:
CMO com expectativa são caracterizados pela presença de filas. Uma fila pode ter uma capacidade limitada ou ilimitada: 
.
Os pesquisadores geralmente estão interessados nas seguintes características estatísticas associadas à permanência de aplicativos na fila:
Muitas vezes existem CMOs em que os aplicativos têm tempo limitado na fila independentemente de sua capacidade. Esses QSs também são chamados de QSs de tipo misto.
Fluxo de saídaé o fluxo de solicitações atendidas que saem do QS.
Há casos em que as aplicações passam por vários QS: conexão de trânsito, pipeline de produção, etc. Nesse caso, o fluxo de saída é recebido para o próximo QS. Um conjunto de QS interconectados sequencialmente é chamado QS multifásico ou Redes CMO.
O fluxo de entrada do primeiro QS, tendo passado pelo QS subsequente, é distorcido e isso dificulta a modelagem. No entanto, deve-se ter em mente que com o fluxo de entrada mais simples e serviço exponencial (ou seja, em sistemas de Markov), o fluxo de saída também é o mais simples. Se o tempo de serviço tiver uma distribuição não exponencial, o fluxo de saída não é apenas simples, mas também não recorrente.
Observe que os intervalos entre as solicitações de saída não são os mesmos que os intervalos de serviço. Afinal, pode acontecer que após o término do próximo serviço, o QS fique ocioso por algum tempo devido à falta de aplicativos. Nesse caso
É necessário para resolver os problemas 1-3. Os dados iniciais são dados na tabela. 2–4.
Algumas notações usadas na teoria das filas para fórmulas:
n é o número de canais no QS;
λ é a intensidade do fluxo de entrada das aplicações P in;
v é a intensidade do fluxo de saída das aplicações P out;
μ é a intensidade do fluxo de serviço P sobre;
ρ é o indicador de carga do sistema (tráfego);
m é o número máximo de lugares na fila, o que limita o comprimento da fila de pedidos;
i é o número de fontes de solicitação;
p k é a probabilidade do k-ésimo estado do sistema;
p o - a probabilidade de downtime de todo o sistema, ou seja, a probabilidade de todos os canais estarem livres;
p syst é a probabilidade de aceitar uma aplicação no sistema;
p ref - a probabilidade de rejeição do pedido na sua aceitação no sistema;
р sobre - a probabilidade de que o aplicativo será atendido;
A é a taxa de transferência absoluta do sistema;
Q é o rendimento relativo do sistema;
Och - o número médio de aplicativos na fila;
Sobre - o número médio de aplicativos em serviço;
Sist - o número médio de aplicativos no sistema;
Och - tempo médio de espera de uma aplicação na fila;
Tb - tempo médio de atendimento da solicitação, referente apenas às solicitações atendidas;
Sis é o tempo médio de permanência de uma aplicação no sistema;
Ozh - o tempo médio que limita a espera por um aplicativo na fila;
é o número médio de canais ocupados.
A taxa de transferência absoluta do QS A é o número médio de aplicativos que o sistema pode atender por unidade de tempo.
A taxa de transferência QS relativa Q é a razão entre o número médio de solicitações atendidas pelo sistema por unidade de tempo e o número médio de solicitações recebidas durante esse período.
Ao resolver problemas de filas, é necessário seguir a seguinte sequência:
1) determinação do tipo de QS conforme Tabela. 4.1;
2) a escolha das fórmulas de acordo com o tipo de QS;
3) resolução de problemas;
4) formulação de conclusões sobre o problema.
1. Esquema de morte e reprodução. Sabemos que, dado um gráfico de estado rotulado, podemos facilmente escrever as equações de Kolmogorov para probabilidades de estado, e também escrever e resolver equações algébricas para as probabilidades finais. Para alguns casos, as últimas equações são bem-sucedidas
decidir com antecedência, literalmente. Em particular, isso pode ser feito se o gráfico de estado do sistema for o chamado "esquema de morte e reprodução".
O gráfico de estado para o esquema de morte e reprodução tem a forma mostrada na Fig. 19.1. A peculiaridade deste gráfico é que todos os estados do sistema podem ser desenhados em uma cadeia, na qual cada um dos estados médios ( S 1 , S 2 ,…,S n-1) está conectado por uma seta para frente e para trás com cada um dos estados vizinhos - direita e esquerda, e os estados extremos (S 0 , S n) - com apenas um estado vizinho. O termo "esquema de morte e reprodução" origina-se de problemas biológicos, onde uma mudança no tamanho de uma população é descrita por tal esquema.
O esquema de morte e reprodução é frequentemente encontrado em vários problemas da prática, em particular - na teoria das filas, portanto, é útil, de uma vez por todas, encontrar as probabilidades finais dos estados para isso.
Vamos supor que todos os fluxos de eventos que transferem o sistema ao longo das setas do grafo sejam os mais simples (para abreviar, também chamaremos o sistema S e o processo que ocorre nele - o mais simples).
Usando o gráfico da Fig. 19.1, compomos e resolvemos equações algébricas para as probabilidades finais do estado), a existência decorre do fato de que de cada estado você pode ir para todos os outros, o número de estados é finito). Para o primeiro estado S 0 temos:
(19.1)
Para o segundo estado S1:
Devido a (19.1), a última igualdade é reduzida à forma
Onde k pega todos os valores de 0 a P. Então as probabilidades finais p0, p1,..., p n satisfaz as equações
(19.2)
além disso, devemos levar em conta a condição de normalização
p 0 + p 1 + p 2 +…+ p n=1. (19.3)
Vamos resolver este sistema de equações. Da primeira equação (19.2) expressamos p 1 a R 0 :
p 1 = p 0. (19.4)
Da segunda, levando em conta (19.4), obtemos:
(19.5)
A partir do terceiro, tendo em conta (19,5),
(19.6)
e, em geral, para qualquer k(de 1 a n):
(19.7)
Prestemos atenção à fórmula (19.7). O numerador é o produto de todas as intensidades nas setas que vão da esquerda para a direita (do início até o estado dado S k), e no denominador - o produto de todas as intensidades nas setas que levam da direita para a esquerda (do início ao Sk).
Assim, todas as probabilidades de estado R 0 , p 1 , ..., r expressa através de um deles ( R 0). Vamos substituir essas expressões na condição de normalização (19.3). Obtemos entre parênteses R 0:
daí obtemos a expressão para R 0 :
(elevamos o parêntese à potência de -1 para não escrever frações de dois andares). Todas as outras probabilidades são expressas em termos de R 0 (ver fórmulas (19.4) - (19.7)). Observe que os coeficientes de R 0 em cada um deles nada mais são do que membros sucessivos da série após a unidade na fórmula (19.8). Então, calculando R 0 , já encontramos todos esses coeficientes.
As fórmulas obtidas são muito úteis na resolução dos problemas mais simples da teoria das filas.
^ 2. Pequena fórmula. Agora derivamos uma importante fórmula relacionando (para o regime estacionário limitante) o número médio de aplicações eu syst, localizado no sistema de filas (ou seja, atendido ou na fila), e o tempo médio de residência do aplicativo no sistema C sist.
Consideremos qualquer QS (monocanal, multicanal, Markoviano, não Markoviano, com fila ilimitada ou limitada) e dois fluxos de eventos associados a ele: o fluxo de clientes que chegam ao QS e o fluxo de clientes que saem do QS. QS. Se um regime estacionário limitante foi estabelecido no sistema, então o número médio de pedidos que chegam ao QS por unidade de tempo é igual ao número médio de pedidos que saem dele: ambos os fluxos têm a mesma intensidade λ.
Indicar: X(t)- o número de pedidos que chegaram ao CMO antes do momento t. S(t) - o número de pedidos que deixaram o CMO
até o momento t. Ambas as funções são aleatórias e mudam abruptamente (aumentam em um) no momento da chegada das requisições (X(t)) e saídas de pedidos (S(t)). Tipo de funções X(t) e Y(t) mostrado na fig. 19,2; ambas as linhas são escalonadas, a superior é X(t), mais baixo- Y(t). Obviamente, para qualquer momento t a diferença deles Z(t)= X(t) - Y(t) nada mais é do que o número de aplicações no QS. Quando as linhas X(t) e Y(t) merge, não há solicitações no sistema.
Considere um período de tempo muito longo T(continuando mentalmente o gráfico muito além do desenho) e calcule para isso o número médio de aplicações no QS. Será igual à integral da função Z(t) neste intervalo dividido pelo comprimento do intervalo T:
eu sist. = . (19,9) o
Mas essa integral nada mais é do que a área da figura sombreada na Fig. 19.2. Vamos dar uma boa olhada neste desenho. A figura é composta por retângulos, cada um com uma altura igual a um, e uma base igual ao tempo de residência no sistema da ordem correspondente (primeiro, segundo, etc.). Vamos marcar esses tempos t1, t2,... Verdade, no final do intervalo T alguns retângulos entrarão na figura sombreada não completamente, mas parcialmente, mas com um tamanho suficientemente grande T essas pequenas coisas não importam. Assim, pode-se considerar que
(19.10)
em que o montante se aplica a todos os pedidos recebidos durante o período T.
Divida os lados direito e esquerdo (.19.10) pelo comprimento do intervalo T. Obtemos, levando em conta (19.9),
eu sist. = . (19.11)
Dividimos e multiplicamos o lado direito de (19.11) pela intensidade X:
eu sist. = .
Mas a grandeza Tλ nada mais é do que o número médio de solicitações recebidas durante o período ^ T. Se dividirmos a soma de todos os tempos eu no número médio de aplicativos, então obtemos o tempo médio de permanência do aplicativo no sistema C sist. Então,
eu sist. = λ C sist. ,
C sist. = . (19.12)
Esta é a fórmula maravilhosa de Little: para qualquer QS, para qualquer natureza do fluxo de aplicações, para qualquer distribuição de tempo de serviço, para qualquer disciplina de serviço o tempo médio de permanência de um pedido no sistema é igual ao número médio de pedidos no sistema dividido pela intensidade do fluxo de pedidos.
Exatamente da mesma forma, deriva-se a segunda fórmula de Little, que relaciona o tempo médio que o aplicativo fica na fila ^ O que e o número médio de aplicativos na fila eu oh:
C oh = . (19.13)
Para a saída, é suficiente em vez da linha de fundo na Fig. 19.2 tomar uma função U(t)- o número de aplicativos que restam até o momento t não do sistema, mas da fila (se um aplicativo que entrou no sistema não entra na fila, mas imediatamente entra em serviço, ainda podemos considerar que ele entra na fila, mas permanece nela por tempo zero) .
As fórmulas de Little (19.12) e (19.13) desempenham um papel importante na teoria das filas. Infelizmente, na maioria dos manuais existentes, essas fórmulas (comprovadas de forma geral há relativamente pouco tempo) não são fornecidas 1).
§ 20. Os sistemas de filas mais simples e suas características
Nesta seção, consideraremos alguns dos QS mais simples e derivaremos expressões para suas características (indicadores de desempenho). Ao mesmo tempo, demonstraremos as principais técnicas metodológicas características da teoria elementar de filas “markoviana”. Não buscaremos o número de amostras QS para as quais as expressões finais das características serão derivadas; este livro não é um guia para a teoria das filas (essa função é muito melhor desempenhada por manuais especiais). Nosso objetivo é apresentar ao leitor alguns "truques" para facilitar o caminho através da teoria das filas, que em vários livros disponíveis (mesmo alegando ser populares) pode parecer uma coleção desconexa de exemplos.
Todos os fluxos de eventos que transferem QS de estado para estado, nesta seção, consideraremos os mais simples (sem estipular isso a cada vez especificamente). Entre eles estará o chamado "fluxo de atendimento". Significa o fluxo de solicitações atendidas por um canal continuamente ocupado. Neste fluxo, o intervalo entre eventos, como sempre no fluxo mais simples, tem uma distribuição exponencial (muitos manuais dizem em vez disso: "tempo de serviço é exponencial", nós mesmos usaremos esse termo no futuro).
1) Em um livro popular, é dada uma derivação um pouco diferente da fórmula de Little, comparada à anterior. Em geral, o conhecimento deste livro (“Segunda Conversa”) é útil para um conhecimento inicial da teoria das filas.
Nesta seção, a distribuição exponencial do tempo de serviço será tida como certa, como sempre para o sistema "mais simples".
Apresentaremos as características de eficiência do QS em consideração no decorrer da apresentação.
^ 1. P-canal QS com falhas(problema Erlang). Aqui consideramos um dos primeiros problemas "clássicos" da teoria das filas;
este problema surgiu das necessidades práticas da telefonia e foi resolvido no início do nosso século pelo matemático dinamarquês Erlant. A tarefa é definida da seguinte forma: há P canais (linhas de comunicação), que recebem um fluxo de aplicações com intensidade λ. O fluxo de serviço tem uma intensidade μ (o recíproco do tempo médio de serviço t cerca de). Encontre as probabilidades finais dos estados QS, bem como as características de sua eficiência:
^ A- rendimento absoluto, ou seja, o número médio de aplicativos atendidos por unidade de tempo;
Q- taxa de transferência relativa, ou seja, a participação média de solicitações de entrada atendidas pelo sistema;
^ R otk- a probabilidade de falha, ou seja, o fato de que o aplicativo deixará o QS sem atendimento;
k- número médio de canais ocupados.
Solução. Estados do sistema ^S(QS) será numerado de acordo com o número de requisições no sistema (neste caso, coincide com o número de canais ocupados):
S 0 - não há aplicações na OCM,
S 1 - há um pedido no QS (um canal está ocupado, o resto está livre),
Sk- no SMO é k formulários ( k canais estão ocupados, o resto está livre),
S n - no SMO é P aplicativos (todos n canais estão ocupados).
O gráfico de estado QS corresponde ao esquema de morte na reprodução (Fig. 20.1). Vamos marcar este gráfico - anote a intensidade dos fluxos de eventos perto das setas. A partir de S 0 em S1 o sistema é transferido por um fluxo de requisições com intensidade λ (assim que chega uma requisição, o sistema salta de S0 dentro S1). O mesmo fluxo de aplicações traduz
Um sistema de qualquer estado esquerdo para um estado direito adjacente (veja as setas superiores na Figura 20.1).
Vamos diminuir a intensidade das setas inferiores. Seja o sistema no estado ^S 1 (um canal funciona). Produz μ serviços por unidade de tempo. Nós colocamos na flecha S 1 →S 0 intensidade µ. Agora imagine que o sistema está no estado S2(dois canais funcionam). Para ela ir S1,é necessário que o primeiro canal ou o segundo terminem de atender; a intensidade total de seus fluxos de serviço é de 2μ; coloque-o na seta correspondente. O fluxo total de serviço dado pelos três canais tem uma intensidade de 3μ, k canais - km. Colocamos essas intensidades nas setas inferiores na Fig. 20.1.
E agora, conhecendo todas as intensidades, usaremos as fórmulas prontas (19.7), (19.8) para as probabilidades finais no esquema de morte e reprodução. Pela fórmula (19.8) obtemos:
Termos de decomposição 
serão os coeficientes p 0 em expressões para p1
Observe que as fórmulas (20.1), (20.2) não incluem as intensidades λ e μ separadamente, mas apenas como a razão λ/μ. Indicar
λ/μ = ρ (20,3)
E chamaremos o valor de p "a intensidade reduzida do fluxo de aplicações". Seu significado é o número médio de solicitações que chegam para o tempo médio de atendimento de uma solicitação. Usando essa notação, reescrevemos as fórmulas (20.1), (20.2) na forma:
As fórmulas (20.4), (20.5) para as probabilidades de estado final são chamadas de fórmulas Erlang - em homenagem ao fundador da teoria das filas. A maioria das outras fórmulas desta teoria (hoje há mais do que cogumelos na floresta) não tem nenhum nome especial.
Assim, as probabilidades finais são encontradas. Com base neles, calcularemos as características de eficiência do QS. Primeiro encontramos ^ R otk. - a probabilidade de que a solicitação recebida seja recusada (não será atendida). Para isso é necessário que todos P os canais estavam ocupados, então
R ok = R n = . (20,6)
A partir daqui, encontramos a taxa de transferência relativa - a probabilidade de que o aplicativo seja atendido:
Q = 1 - P abrir = 1 - (20,7)
Obtemos o throughput absoluto multiplicando a intensidade do fluxo de solicitações λ por P:
A = λQ = λ . (20.8)
Resta apenas encontrar o número médio de canais ocupados k. Este valor pode ser encontrado "diretamente", como a expectativa matemática de uma variável aleatória discreta com valores possíveis 0, 1, ..., P e as probabilidades desses valores p 0 p 1 , ..., p n:
k = 0 · p 0 + 1 · p 1 + 2 · p 2 + ... + n · p.n.
Substituindo aqui as expressões (20.5) por R k, (k = 0, 1, ..., P) e realizando as transformações apropriadas, eventualmente obteríamos a fórmula correta para k. Mas vamos derivar muito mais fácil (aqui está, um dos "pequenos truques"!) De fato, sabemos o rendimento absoluto MAS. Isso nada mais é do que a intensidade do fluxo de aplicativos atendidos pelo sistema. Cada i.shal empregado por unidade de tempo atende a uma média de |l solicitações. Assim, o número médio de canais ocupados é
k = A/μ, (20.9)
ou, dado (20,8),
k = 
(20.10)
Encorajamos o leitor a resolver o exemplo por conta própria. Existe uma estação de comunicação com três canais ( n= 3), a intensidade do fluxo de aplicações λ = 1,5 (aplicações por minuto); tempo médio de atendimento por solicitação t v = 2 (min.), todos os fluxos de eventos (como neste parágrafo inteiro) são os mais simples. Encontre as probabilidades do estado final e as características de desempenho do QS: A, Q, P ok, k. Apenas no caso, aqui estão as respostas: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, página 3 = 9/26 ≈ 0,346,
MAS≈ 0,981, Q ≈ 0,654, P aberto ≈ 0,346, k ≈ 1,96.
Pode-se perceber pelas respostas, aliás, que nosso QS está bastante sobrecarregado: de três canais, em média, cerca de dois estão ocupados e cerca de 35% das aplicações recebidas permanecem sem atendimento. Convidamos o leitor, se for curioso e não preguiçoso, a descobrir: quantos canais serão necessários para satisfazer pelo menos 80% dos pedidos recebidos? E qual parte dos canais ficará ociosa ao mesmo tempo?
Já existe alguma dica de otimização. De fato, o conteúdo de cada canal por unidade de tempo custa uma certa quantia. Ao mesmo tempo, cada aplicativo atendido traz alguma receita. Multiplicando esta receita pelo número médio de aplicações MAS, atendidos por unidade de tempo, obteremos a receita média do CMO por unidade de tempo. Naturalmente, com o aumento do número de canais, essa receita cresce, mas também crescem os custos associados à manutenção dos canais. O que vai superar - um aumento nas receitas ou despesas? Depende das condições da operação, da "taxa de serviço do aplicativo" e do custo de manutenção do canal. Conhecendo esses valores, você pode encontrar o número ideal de canais, o mais econômico. Não vamos resolver tal problema, deixando o mesmo “leitor não preguiçoso e curioso” para dar um exemplo e resolvê-lo. Em geral, inventar problemas desenvolve mais do que resolver aqueles já estabelecidos por alguém.
^ 2. QS de canal único com fila ilimitada. Na prática, QS de um canal com fila é bastante comum (um médico atendendo pacientes; um telefone público com uma cabine; um computador atendendo pedidos de usuários). Na teoria das filas, QS de canal único com uma fila também ocupa um lugar especial (a maioria das fórmulas analíticas obtidas até agora para sistemas não Markovianos pertencem a tais QS). Portanto, daremos atenção especial ao QS de canal único com uma fila.
Seja um QS de canal único com uma fila na qual não são impostas restrições (nem no comprimento da fila, nem no tempo de espera). Este QS recebe um fluxo de requisições com intensidade λ ; o fluxo de atendimento tem intensidade μ inversa ao tempo médio de atendimento da requisição t cerca de. É necessário encontrar as probabilidades finais dos estados QS, bem como as características de sua eficiência:
eu sist. - número médio de aplicações no sistema,
C sist. - tempo médio de permanência da aplicação no sistema,
^ L och- o número médio de pedidos na fila,
C oh - o tempo médio que um aplicativo passa na fila,
P zan - a probabilidade de que o canal esteja ocupado (o grau de carregamento do canal).
Quanto ao rendimento absoluto MAS e relativo Q, então não há necessidade de calculá-los:
devido ao fato de que a fila é ilimitada, cada aplicação será atendida mais cedo ou mais tarde, portanto A \u003d λ, pela mesma razão Q= 1.
Solução. Os estados do sistema, como antes, serão numerados de acordo com o número de aplicações no QS:
S 0 - o canal é gratuito
S 1 - o canal está ocupado (atende a solicitação), não há fila,
S 2 - o canal está ocupado, um pedido está na fila,
S k - o canal está ocupado, k- 1 aplicativos estão na fila,
Teoricamente, o número de estados não é limitado por nada (infinitamente). O gráfico de estado tem a forma mostrada na Fig. 20.2. Este é um esquema de morte e reprodução, mas com um número infinito de estados. De acordo com todas as setas, o fluxo de solicitações com intensidade λ transfere o sistema da esquerda para a direita e da direita para a esquerda - o fluxo de atendimento com intensidade μ.
Em primeiro lugar, perguntemo-nos: existem probabilidades finais neste caso? Afinal, o número de estados do sistema é infinito e, em princípio, em t → ∞ a fila pode crescer indefinidamente! Sim, é verdade: as probabilidades finais para tal QS nem sempre existem, mas apenas quando o sistema não está sobrecarregado. Pode-se provar que se ρ for estritamente menor que um (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ cresce indefinidamente. Este fato parece especialmente “incompreensível” para ρ = 1. Parece que não há requisitos impossíveis para o sistema: durante o atendimento de um aplicativo, em média, um aplicativo chega e tudo deve estar em ordem, mas na realidade não é. Para ρ = 1, o QS atende ao fluxo de requisições somente se este fluxo for regular, e o tempo de atendimento também não for aleatório, igual ao intervalo entre as requisições. Nesse caso "ideal", não haverá fila no QS, o canal estará continuamente ocupado e emitirá regularmente solicitações atendidas. Mas assim que o fluxo de requisições ou o fluxo de atendimento se tornar pelo menos um pouco aleatório, a fila já crescerá indefinidamente. Na prática, isso não acontece apenas porque "um número infinito de aplicativos na fila" é uma abstração. Esses são os erros grosseiros que a substituição de variáveis aleatórias por suas expectativas matemáticas pode levar!
Mas voltemos ao nosso QS de canal único com fila ilimitada. A rigor, as fórmulas para as probabilidades finais no esquema de morte e reprodução foram derivadas por nós apenas para o caso de um número finito de estados, mas tomemos liberdades - vamos usá-las para um número infinito de estados. Vamos calcular as probabilidades finais dos estados de acordo com as fórmulas (19.8), (19.7). No nosso caso, o número de termos na fórmula (19.8) será infinito. Obtemos uma expressão para p 0:
p 0 = -1 =
\u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)
A série na fórmula (20.11) é uma progressão geométrica. Sabemos que para ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... existe apenas para r<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 - pág. (20.12)
Probabilidades p 1 , p 2 , ..., p k ,... pode ser encontrado pelas fórmulas:
p1 = ρ 0, 2= ρ2 p0,…,pk = ρ p0, ...,
Daí, levando em conta (20.12), finalmente encontramos:
p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , pk =ρ k(1 - p), . . .(20.13)
Como você pode ver, as probabilidades p0, p1, ..., pk,... forme uma progressão geométrica com o denominador p. Curiosamente, o maior deles p 0 - a probabilidade de que o canal seja totalmente livre. Não importa quão carregado o sistema com a fila esteja, se ele puder lidar com o fluxo de aplicativos (ρ<1), самое вероятное число заявок в системе будет 0.
Encontre o número médio de aplicativos no QS ^L sistema. . Aqui você tem que mexer um pouco. Valor aleatório Z- número de solicitações no sistema - tem valores possíveis 0, 1, 2, .... k,... com probabilidades p0, p 1 , p 2 , ..., p k , ... Sua esperança matemática é
eu sistema = 0 p 0 + 1 · p 1 + 2 p 2 +…+k · p k +…= (20,14)
(a soma é tomada não de 0 a ∞, mas de 1 a ∞, pois o termo zero é igual a zero).
Substituímos na fórmula (20.14) a expressão para pk (20.13):
eu sist. = 
Agora tiramos o sinal da soma ρ (1-ρ):
eu sist. = ρ(1-ρ)
Aqui aplicamos novamente o “pequeno truque”: kρ k-1 nada mais é que a derivada em relação a ρ da expressão ρ k; significa,
eu sist. = ρ(1-ρ)
Trocando as operações de diferenciação e soma, obtemos:
eu sist. = ρ (1-ρ) (20,15)
Mas a soma na fórmula (20.15) nada mais é do que a soma de uma progressão geométrica infinitamente decrescente com o primeiro termo ρ e o denominador ρ; esta quantidade
igual a , e sua derivada . Substituindo esta expressão em (20.15), obtemos:
eu sist = . (20.16)
Bem, agora vamos aplicar a fórmula de Little (19.12) e encontrar o tempo médio de residência de uma aplicação no sistema:
C sistema = (20,17)
Encontre o número médio de aplicativos na fila eu oh. Vamos argumentar da seguinte forma: o número de pedidos na fila é igual ao número de pedidos no sistema menos o número de pedidos em serviço. Então (de acordo com a regra de adição de expectativas matemáticas), o número médio de pedidos na fila eu pt é igual ao número médio de aplicações no sistema eu syst menos o número médio de solicitações em serviço. O número de solicitações em serviço pode ser zero (se o canal estiver livre) ou um (se estiver ocupado). A expectativa matemática de tal variável aleatória é igual à probabilidade de que o canal esteja ocupado (denotamos R zan). Obviamente, R zan é igual a um menos a probabilidade p 0 que o canal é gratuito:
R zan = 1 - R 0 = pág. (20.18)
Portanto, o número médio de solicitações em atendimento é igual a
^ L sobre= ρ, (20,19)
eu oh = eu sistema – ρ =
e finalmente
eu pt = (20,20)
Usando a fórmula de Little (19.13), encontramos o tempo médio que o aplicativo passa na fila:
(20.21)
Assim, todas as características de eficiência do QS foram encontradas.
Vamos sugerir ao leitor que resolva um exemplo por conta própria: um QS de canal único é um pátio de triagem ferroviária, que recebe o fluxo mais simples de trens com intensidade de λ = 2 (trens por hora). Serviço (dissolução)
composição dura um tempo aleatório (demonstrativo) com um valor médio t sobre = 20(mín.). No parque de desembarque da estação, há duas pistas nas quais os trens que chegam podem esperar pelo serviço; se ambos os trilhos estiverem ocupados, os trens são forçados a esperar nos trilhos externos. É necessário encontrar (para o modo de operação limitante e estacionário da estação): média, número de trens eu sistema relacionado à estação, tempo médio C sistema de permanência do trem na estação (nas vias internas, nas vias externas e em manutenção), número médio eu pts de trens esperando na fila para desmantelamento (não importa em quais trilhos), tempo médio C Pts ficam composição na lista de espera. Além disso, tente encontrar o número médio de trens esperando para serem desfeitos nos trilhos externos. eu externo e o tempo médio dessa espera C externo (as duas últimas quantidades estão relacionadas pela fórmula de Little). Finalmente, encontre a multa diária total W, que a estação terá que pagar por sobreestadia de trens em trilhos externos, se a estação pagar multa a (rublos) por uma hora de sobreestadia de um trem. Apenas no caso, aqui estão as respostas: eu sist. = 2 (composição), C sist. = 1 (hora), eu pontos = 4/3 (composição), C pt = 2/3 (horas), eu externo = 16/27 (composição), C externo = 8/27 ≈ 0,297 (horas). A multa diária média W por espera de trens em vias externas é obtida multiplicando-se o número médio de trens que chegam à estação por dia, o tempo médio de espera de trens em vias externas e a multa horária uma: W ≈ 14,2 uma.
^ 3. Recanalize QS com fila ilimitada. Completamente semelhante ao problema 2, mas um pouco mais complicado, o problema da n-canal QS com fila ilimitada. A numeração dos estados é novamente de acordo com o número de aplicações no sistema:
S0- não há aplicativos no CMO (todos os canais são gratuitos),
S 1 - um canal está ocupado, o resto está livre,
S2- dois canais estão ocupados, o resto está livre,
S k- ocupado k canais, o resto é grátis,
S n- todos estão ocupados P canais (sem fila),
Sn+1- todos estão ocupados n canais, um aplicativo está na fila,
S n + r - peso ocupado P canais, r os aplicativos estão na fila
O gráfico de estado é mostrado na fig. 20.3. Convidamos o leitor a considerar e justificar os valores das intensidades indicadas pelas setas. Gráfico fig. 20,3
λ λ λ λ λ λ λ λ λ
μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ
há um esquema de morte e reprodução, mas com um número infinito de estados. Vamos enunciar sem prova a condição natural para a existência de probabilidades finais: ρ/ n<1. Если ρ/n≥ 1, a fila cresce até o infinito.
Suponhamos que a condição ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 haverá uma série de termos contendo fatoriais, mais a soma de uma progressão geométrica infinitamente decrescente com o denominador ρ/ n. Resumindo, encontramos
(20.22)
Agora vamos encontrar as características da eficiência QS. Destes, é mais fácil encontrar o número médio de canais ocupados k== λ/μ, = ρ (isso geralmente é verdade para qualquer QS com fila ilimitada). Encontre o número médio de aplicativos no sistema eu sistema e o número médio de pedidos na fila eu oh. Destes, é mais fácil calcular o segundo, de acordo com a fórmula
eu oh =
realizando as transformações correspondentes de acordo com a amostra do problema 2
(com a diferenciação da série), temos:
eu oh = 
(20.23)
Somando-se a ele o número médio de aplicativos em serviço (é também o número médio de canais ocupados) k =ρ, obtemos:
eu sistema = eu och + ρ. (20,24)
Dividindo expressões para eu oh e eu sistema em λ , usando a fórmula de Little, obtemos o tempo médio de permanência de uma aplicação na fila e no sistema:
(20.25)
Agora vamos resolver um exemplo interessante. Uma bilheteria ferroviária com duas janelas é um QS de dois canais com uma fila ilimitada que é estabelecida imediatamente para duas janelas (se uma janela estiver livre, o próximo passageiro da fila a levará). A bilheteria vende ingressos em dois pontos: A e NO. A intensidade do fluxo de pedidos (passageiros que querem comprar passagem) para ambos os pontos A e Bé o mesmo: λ A = λ B = 0,45 (passageiros por minuto), e no total formam um fluxo geral de aplicações com intensidade de λ A + λB = 0,9. Um caixa gasta em média dois minutos atendendo um passageiro. A experiência mostra que as filas se acumulam na bilheteria, os passageiros reclamam da lentidão do atendimento. MAS e em NO, criar duas bilheterias especializadas (uma janela em cada), vendendo ingressos uma - apenas até o ponto MAS, o outro - apenas ao ponto NO. A solidez desta proposta é controversa - alguns argumentam que as filas permanecerão as mesmas. É necessário verificar a utilidade da proposta por cálculo. Como podemos calcular as características apenas para o QS mais simples, vamos supor que todos os fluxos de eventos sejam os mais simples (isso não afetará o lado qualitativo das conclusões).
Bem, então, vamos ao que interessa. Vamos considerar duas opções para organizar a venda de ingressos - a existente e a proposta.
Opção I (existente). Um QS de dois canais recebe um fluxo de aplicações com intensidade λ = 0,9; intensidade do fluxo de manutenção μ = 1/2 = 0,5; ρ = λ/μ = l,8. Como ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. A média, o número de pedidos na fila é encontrada pela fórmula (20,23): L och ≈ 7,68; o tempo médio gasto pelo cliente na fila (de acordo com a primeira das fórmulas (20,25)), é igual a C pts ≈ 8,54 (min.).
Opção II (proposta). É necessário considerar dois QS de canal único (duas janelas especializadas); cada um recebe um fluxo de requisições com intensidade λ = 0,45; μ . ainda igual a 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) eu och = 8,1.
Aqui está um para você! O comprimento da fila, ao que parece, não apenas não diminuiu, mas aumentou! Talvez o tempo médio de espera na fila tenha diminuído? Vamos ver. Délia eu pontos em λ = 0,45, obtemos C pts ≈ 18 (minutos).
Essa é a racionalização! Em vez de diminuir, tanto o comprimento médio da fila quanto o tempo médio de espera aumentaram!
Vamos tentar adivinhar por que isso aconteceu? Pensando em nossos cérebros, chegamos à conclusão: isso aconteceu porque na primeira variante (QS de dois canais) a fração média de tempo que cada um dos dois caixas está ocioso é menor: se ele não estiver ocupado atendendo um passageiro que compra uma passagem para o MAS, ele pode cuidar do passageiro que compra uma passagem para o ponto NO, e vice versa. Na segunda variante, não existe essa intercambialidade: um caixa desocupado apenas fica de braços cruzados...
Nós iremos , ok, - o leitor está pronto para concordar, - o aumento pode ser explicado, mas por que é tão significativo? Há um erro de cálculo aqui?
E vamos responder a esta pergunta. Não há erro. O fato , que em nosso exemplo, ambos os QSs estão trabalhando no limite de suas capacidades; se você aumentar um pouco o tempo de serviço (ou seja, reduzir μ), eles não poderão mais lidar com o fluxo de passageiros e a fila começará a crescer indefinidamente. E o "tempo extra de inatividade" do caixa de certa forma equivale a uma diminuição em sua produtividade μ.
Assim, o resultado dos cálculos, que a princípio parecem paradoxais (ou mesmo simplesmente incorretos), acaba sendo correto e explicável.
Esse tipo de conclusão paradoxal, cuja razão não é óbvia, é rica na teoria das filas. O próprio autor repetidamente teve que se "surpreender" com os resultados dos cálculos, que mais tarde se mostraram corretos.
Refletindo sobre a última tarefa, o leitor pode colocar a questão da seguinte forma: afinal, se a bilheteria vende ingressos para apenas um ponto, então, naturalmente, o tempo de atendimento deve diminuir, bem, não pela metade, mas pelo menos um pouco, mas achamos que ainda era a média é 2 (min.). Convidamos o leitor tão exigente a responder à pergunta: quanto deve ser reduzido para que a “proposta de racionalização” se torne lucrativa? Novamente, encontramos, embora elementar, mas ainda um problema de otimização. Com a ajuda de cálculos aproximados, mesmo nos modelos mais simples de Markov, é possível esclarecer o lado qualitativo do fenômeno - como é lucrativo agir e como não é lucrativo. Na próxima seção, apresentaremos alguns modelos não markovianos elementares que expandirão ainda mais nossas possibilidades.
Depois que o leitor se familiarizar com os métodos para calcular as probabilidades do estado final e as características de desempenho para o QS mais simples (ele dominou o esquema de morte e reprodução e a fórmula de Little), ele pode receber mais dois QS simples para consideração independente.
^ 4. QS de canal único com fila limitada. O problema difere do Problema 2 apenas porque o número de solicitações na fila é limitado (não pode exceder alguns t). Se uma nova solicitação chegar no momento em que todos os lugares da fila estiverem ocupados, ela deixará o QS sem atendimento (rejeitado).
É necessário encontrar as probabilidades finais dos estados (a propósito, eles existem neste problema para qualquer ρ - afinal, o número de estados é finito), a probabilidade de falha R otk, largura de banda absoluta MAS, a probabilidade de o canal estar ocupado R zan, comprimento médio da fila eu och, o número médio de pedidos na OCM eu sistema , tempo médio de espera na fila C oh , tempo médio de residência de um pedido na OCM C sist. Ao calcular as características da fila, você pode usar a mesma técnica que usamos no Problema 2, com a diferença de que é necessário resumir não uma progressão infinita, mas finita.
^ 5. QS de malha fechada com um canal e m fontes de aplicativos. Para concretude, vamos definir a tarefa da seguinte forma: um trabalhador serve t máquinas, cada uma das quais requer ajuste (correção) de tempos em tempos. A intensidade do fluxo de demanda de cada máquina de trabalho é igual a λ . Se a máquina estiver fora de serviço no momento em que o trabalhador estiver livre, ele imediatamente vai ao serviço. Se ele está fora de serviço no momento em que o trabalhador está ocupado, ele faz fila e espera que o trabalhador fique livre. Tempo médio de configuração t rev = 1/µ. A intensidade do fluxo de solicitações que chegam ao trabalhador depende de quantas máquinas estão funcionando. Se isso funcionar k máquinas-ferramentas, é igual a kλ. Encontre as probabilidades de estado final, o número médio de máquinas em funcionamento e a probabilidade de que o trabalhador esteja ocupado.
Observe que neste QS, as probabilidades finais
existirá para quaisquer valores de λ e μ = 1/ t o, pois o número de estados do sistema é finito.
Breve teoria
Como indicadores da eficácia do QS com falhas, consideraremos:
A taxa de transferência absoluta do QS, ou seja, o número médio de pedidos atendidos por unidade de tempo;
Rendimento relativo, ou seja, a participação média de solicitações recebidas atendidas pelo sistema;
Probabilidade de falha, ou seja, o fato de que o pedido deixará a OCM sem atendimento;
Número médio de canais ocupados.
Considere o problema clássico de Erlang.
Existem canais que recebem um fluxo de aplicações com intensidade. O fluxo de serviços tem uma intensidade de . Encontre as probabilidades limitantes dos estados do sistema e indicadores de sua eficiência.
O sistema (QS) tem os seguintes estados (nós os numeramos de acordo com o número de clientes no sistema):
O gráfico do estado QS corresponde ao processo de morte e reprodução e é mostrado na figura.
O fluxo de requisições transfere sequencialmente o sistema de qualquer estado da esquerda para o vizinho direito com a mesma intensidade. A intensidade do fluxo de serviços que transferem o sistema de qualquer estado direito para um estado vizinho esquerdo muda constantemente dependendo do estado. De fato, se o QS está no estado (dois canais ocupados), então ele pode ir para o estado (um canal está ocupado) quando o primeiro ou o segundo canal termina o serviço, ou seja, a intensidade total de seus fluxos de serviço vai ser . Da mesma forma, o fluxo total de serviços que transfere o QS do estado (três canais estão ocupados) para terá intensidade , ou seja, qualquer um dos três canais pode ficar livre, e assim por diante.
Para o esquema de morte e reprodução, obtemos para a probabilidade limite do estado:
onde os termos da expansão serão os coeficientes a nas expressões para as probabilidades limitantes. Valor
é chamada de intensidade reduzida do fluxo de solicitações ou intensidade da carga do canal. Expressa o número médio de solicitações que chegam para o tempo médio de atendimento de uma solicitação. Agora:
As últimas fórmulas para probabilidades marginais são chamadas de fórmulas Erlang em homenagem ao fundador da teoria das filas.
A probabilidade de falha QS é a probabilidade marginal de que todos os canais do sistema estejam ocupados, ou seja:
Taxa de transferência relativa - a probabilidade de o aplicativo ser atendido:
Largura de banda absoluta:
O número médio de canais ocupados é a expectativa matemática do número de canais ocupados:
onde estão as probabilidades limitantes dos estados
No entanto, o número médio de canais ocupados pode ser encontrado de forma mais simples se levarmos em conta que o throughput absoluto do sistema nada mais é do que a intensidade do fluxo de requisições atendidas pelo sistema (por unidade de tempo). Como cada canal ocupado atende solicitações em média (por unidade de tempo), o número médio de canais ocupados é:
Exemplo de solução de problema
O controle do produto acabado da empresa é realizado por três controladores. Se um produto for enviado para inspeção quando todos os inspetores estiverem ocupados verificando os produtos acabados, ele permanecerá desmarcado. A quantidade média de produtos produzidos pela empresa é de 20 itens/hora. O tempo médio para verificar um produto é de 7 minutos.
Determinar os indicadores de desempenho do departamento de controle técnico. Quantos controladores precisam ser instalados para que a probabilidade de atendimento seja de pelo menos 97%?
Chegou a esta página ao tentar resolver um problema em um exame ou teste? Se você ainda não conseguiu passar no exame, da próxima vez concorde com antecedência no site sobre Ajuda online sobre métodos de solução ideais.
O Control é um sistema de filas multicanal aberto com negação de serviço.
Vamos tomar a hora como unidade de tempo. Assumimos que o controle opera em regime permanente. De acordo com a tarefa
– número de canais de atendimento
Produtos por hora - a intensidade do fluxo de aplicações
Itens por hora - taxa de fluxo de serviço
Vamos calcular as intensidades relativas das transições de estado para estado:
Vamos calcular:
Probabilidade de falha:
Probabilidade de serviço
Largura de banda absoluta do sistema:
é o número médio de aplicativos atendidos pelo sistema por unidade de tempo.
O número médio de canais ocupados pelo serviço de aplicativos:
Vamos calcular quantos controladores precisam ser instalados para que a probabilidade de atendimento seja de pelo menos 97%:
Assim, para que a probabilidade de atendimento seja de pelo menos 97%, é necessário ter 6 controladores.
Médio o custo de resolver o trabalho de controle é de 700 a 1200 rublos (mas não inferior a 300 rublos para todo o pedido). O preço é fortemente influenciado pela urgência da decisão (de dias a várias horas). O custo da ajuda on-line no exame / teste - a partir de 1000 rublos. para a solução de bilhetes.
O aplicativo pode ser deixado diretamente no chat, tendo previamente descartado a condição das tarefas e informando os prazos para resolvê-lo. O tempo de resposta é de vários minutos.
Exemplos de tarefas relacionadas
CMO com fila ilimitada
São fornecidas as informações teóricas necessárias e uma solução de amostra do problema no tópico "Sistema de filas multicanal com fila ilimitada", os indicadores de um sistema de filas multicanal (QS) com espera de serviço são considerados em detalhes - o número médio de canais ocupados atendendo a um aplicativo, comprimento da fila, probabilidade de formação de fila, estado livre de probabilidade do sistema, tempo médio de espera na fila.
O problema da alocação ótima de recursos
Os principais princípios da programação dinâmica (escalonamento dinâmico) são brevemente apresentados, as equações de Bellman são consideradas. O problema da distribuição ótima de recursos entre empresas é resolvido em detalhes.
Método do multiplicador de Lagrange
A página considera encontrar um extremo condicional usando o método dos multiplicadores de Lagrange. A construção da função de Lagrange é mostrada no exemplo de resolução de um problema de programação não linear. O problema resolvido é precedido por uma breve teoria.
Vetor de consumo final e vetor de produção bruta
No exemplo de solução do problema, considera-se o modelo intersetorial de Leontiev. Apresenta-se o cálculo da matriz de coeficientes de custos diretos de materiais, a matriz “input-output”, a matriz de coeficientes de custos indiretos, os vetores de consumo final e produção bruta.
