Pertanto, il 13% del canale sarà inattivo per un'ora, il tempo di inattività è pari a t pr = 7,5 min.
La probabilità che il servizio:
canale 1 occupato:
p 1 = ρ 1 /1! p 0 = 2.1 1 /1! 0,13 = 0,26
2 canali sono occupati:
p 2 = ρ 2 /2! p 0 = 2.1 2 /2! 0,13 = 0,28
3 canali sono occupati:
p 3 = ρ 3 /3! p 0 = 2.1 3 /3! 0,13 = 0,19
4 canali sono occupati:
p 4 = ρ 4 /4! p 0 = 2.1 4 /4! 0,13 = 0,1
5 canali sono occupati:
p 5 = ρ 5 /5! p 0 = 2.1 5 /5! 0,13 = 0,0425 (probabilità che tutti i collegamenti siano occupati)
4. Percentuale di domande respinte.
Ciò significa che il 4% delle domande pervenute non viene accettato per il servizio.
5. Probabilità di soddisfare le richieste in arrivo.
Nei sistemi con guasti, gli eventi di guasto e manutenzione costituiscono un gruppo completo di eventi, quindi:
p aperto + p obs = 1
Produttività relativa: Q = p obs.
p obs \u003d 1 - p otk \u003d 1 - 0,0425 \u003d 0,96
Di conseguenza, il 96% delle domande pervenute sarà servito. Il livello di servizio accettabile deve essere superiore al 90%.
6. Numero medio di linee di comunicazione occupate
n z = ρ p obs = 2.1 0.96 = 2.01 righe.
Canali inattivi medi.
n pr \u003d n - n z \u003d 5 - 2.01 \u003d 3 canali.
7. Tasso di occupazione del canale di servizio.
K 3 \u003d n 3 / n \u003d 2.01 / 5 \u003d 0.4
Pertanto, il sistema è impegnato al 40% con la manutenzione.
8. Larghezza di banda assoluta.
A = p obs λ = 0.96 0.6 = 0.57 richieste/min.
9. Tempo di inattività QS medio.
t pr \u003d p otk t obs \u003d 0,0425 3,5 \u003d 0,15 min.
12. Numero medio di richieste servite.
L obs = ρ Q = 2.1 0.96 = 2.01 unità
Per determinare il numero ottimale di linee di comunicazione, sufficiente a garantire che la probabilità di guasto non superi 0,04, utilizziamo la formula:
Per i nostri dati:
dove 
Selezionando il numero di linee di connessione, troviamo che a k=6, popen = 0.0147< 0.04, p 0 = 0.12
Scarica la soluzione
1. Un'impresa commerciale svolge attività di intermediazione per la vendita di autoveicoli e svolge parte delle trattative su 3 linee telefoniche. In media vengono ricevute 75 chiamate all'ora. Il tempo medio delle trattative istruttorie di carattere retrospettivo è di 2 minuti.
2. La stazione di riparazione dell'appartamento funziona in modalità guasto ed è composta da due squadre. L'intensità del flusso di richieste λ, la produttività del punto μ. Determinare la probabilità che entrambi i canali siano liberi, un canale sia occupato, entrambi i canali siano occupati, la probabilità di guasto, il throughput relativo e assoluto, il numero medio di squadre impegnate.
3. Il centro informatico per uso collettivo con tre computer riceve ordini dalle imprese per lavori informatici. Se tutti e tre i computer funzionano, il nuovo ordine in arrivo non viene accettato e l'azienda è costretta a rivolgersi a un altro centro di calcolo. Il tempo medio di lavoro con un ordine è di 3 ore L'intensità del flusso di domande è di 0,25 (1/h). Trova le probabilità limite degli stati e gli indicatori di prestazione del centro di calcolo.
2. Un flusso di clienti entra nel minimarket con un'intensità di 6 clienti al minuto, serviti da tre controllori di cassa con un'intensità di 2 clienti al minuto. la lunghezza della coda è limitata a 5 clienti.
3. Sulla base di frutta e verdura, in media, dopo 30 minuti. arrivano macchine con frutta e verdura. Il tempo medio di scarico per un camion è di 1,5 ore e lo scarico viene effettuato da due squadre. Sul territorio della base all'imbarcadero non possono essere in fila più di 4 veicoli in attesa di scarico.
4. All'autolavaggio arrivano in media 9 auto all'ora, ma se ci sono già 4 auto in coda, i clienti appena arrivati, di norma, non fanno la fila, ma passano. Il tempo medio di lavaggio dell'auto è di 20 minuti e ci sono solo due posti di lavaggio. Il costo medio di un autolavaggio è di 70 rubli. Determinare valore medio perdita di entrate dell'autolavaggio durante il giorno.
5. Il negozio riceve verdure dalle serre. I camion con il carico arrivano con intensità λ auto al giorno. I locali tecnici consentono di elaborare e conservare le merci portate m macchine. Lavora in negozio n imballatori, ciascuno dei quali, in media, può elaborare merci da una macchina durante t servizio ore. La giornata lavorativa per il lavoro a turni è di 12 ore. Determinare la capienza dei locali tecnici per un dato servizio di probabilità P*. lavorazione completa della merce.
6. C'è una stazione di servizio con 2 colonne. Non ci possono essere più di 3 auto in coda. L'intensità e il tempo medio di riempimento sono 2,1 e 0,55. Trova la probabilità di inattività del sistema.
Soluzione:
La portata di servizio è μ = 1/0,55 = 1,82. Quindi, l'intensità del carico sarà ρ = λ t obs = 2.1 0.55 = 1.16. Si noti che l'intensità di carico ρ=1.16 mostra il grado di coerenza tra i flussi in ingresso e in uscita delle richieste del canale di servizio e determina la stabilità del sistema di accodamento.
Dal 16.1<2, то процесс обслуживания будет стабилен.
La probabilità di fermo impianto è espressa dalla seguente formula:
1. Costruisci due modelli di un sistema di accodamento multicanale, con una coda infinita e una limitata. Calcola P 0 - la probabilità di inattività di tutti i canali di servizio, n w - il numero medio di clienti in attesa del servizio, t w - il tempo medio di attesa per il servizio, W - la probabilità di permanenza obbligatoria in coda.
2. Ci sono 3 casse nel nodo cassa del negozio self-service. l'intensità del flusso in ingresso è di 5 buyer al minuto. l'intensità del servizio di ciascun controllore-cassiere è di 2 clienti al minuto.
Raccomandazioni per risolvere il problema: qui n = 3; λ = 5 unità in minuti; μ = 2 unità in min.
Come numero di richieste in coda, è possibile specificare, ad esempio, m = 4. Quindi verrà calcolata la probabilità corrispondente della comparsa di queste richieste.
3. La società di revisione riceve il flusso più semplice di richieste di servizi con un'intensità di λ = 1,5 richieste al giorno. Il tempo di servizio è distribuito secondo la legge esponenziale ed è pari mediamente a tre giorni. La società di revisione dispone di cinque commercialisti indipendenti che eseguono audit (serving applicativo). La coda delle domande non è limitata. La disciplina della coda non è regolamentata. Determinare le caratteristiche probabilistiche di una società di revisione come sistema di accodamento operante in modalità stazionaria.
4. Ci sono n artigiani che lavorano in un'officina di riparazione di frigoriferi. In media, λ frigoriferi vengono ricevuti per la riparazione durante il giorno. Il flusso degli ordini è Poisson. Il tempo di riparazione è soggetto a una legge di distribuzione di probabilità esponenziale, in media, durante il giorno con una giornata lavorativa di sette ore, ciascuno dei maestri ripara μ frigoriferi.
È necessario determinare: 1) la probabilità che tutti i master siano liberi dalla riparazione dei frigoriferi, 2) la probabilità che tutti i master siano impegnati nelle riparazioni, 3) il tempo medio di riparazione per un frigorifero, 4) il tempo medio di attesa per l'avvio di riparazioni per ciascun frigorifero, 5) la lunghezza media della coda, che determina lo spazio di stoccaggio necessario per un frigorifero da riparare, 6) il numero medio di maestri liberi dal lavoro.
Quando si risolvono compiti di comando e controllo, incluso il comando e il controllo delle truppe, spesso sorgono una serie di compiti dello stesso tipo:
Tutti questi compiti sono dello stesso tipo, nel senso che hanno una massiccia richiesta di servizio. Un certo insieme di elementi è coinvolto nel soddisfare questa domanda, formando un sistema di accodamento (QS) (Fig. 2.9).
Gli elementi dell'OCM sono:
Flusso in arrivoè una raccolta di richieste di servizio. Spesso l'applicazione è identificata con il suo vettore. Ad esempio, il flusso di apparecchiature radio difettose che entrano nell'officina sindacale è un flusso di domande - requisiti per il servizio in questo QS.
Di norma, in pratica, si tratta dei cosiddetti flussi ricorrenti, flussi che hanno le seguenti proprietà:
Abbiamo definito le prime due proprietà in precedenza. Per quanto riguarda l'effetto collaterale limitato, sta nel fatto che gli intervalli tra le applicazioni in arrivo sono variabili casuali indipendenti.
Ci sono molti flussi ricorrenti. Ogni legge di distribuzione degli intervalli genera il proprio flusso ricorrente. I flussi ricorrenti sono altrimenti noti come flussi Palm.
Un flusso con una completa assenza di effetti collaterali, come già notato, è chiamato flusso di Poisson stazionario. I suoi intervalli casuali tra le richieste hanno una distribuzione esponenziale:
ecco l'intensità del flusso.
Il nome del torrente - Poisson - deriva dal fatto che per questo probabilità di flusso l'aspetto delle applicazioni per l'intervallo è determinato dalla legge di Poisson:
Un flusso di questo tipo, come notato in precedenza, è anche chiamato il più semplice. È questo flusso che i progettisti assumono quando sviluppano un QS. Ciò è dovuto a tre motivi.
In primo luogo, un flusso di questo tipo in teoria delle code è simile alla legge della distribuzione normale in teoria della probabilità nel senso che il passaggio al limite per un flusso che è la somma di flussi con caratteristiche arbitrarie con un aumento infinito in termini e una diminuzione in la loro intensità porta al flusso più semplice. Cioè, la somma di flussi arbitrari indipendenti (senza predominanza) con intensità è il flusso più semplice con intensità
In secondo luogo, se i canali di servizio (dispositivi) sono progettati per il flusso di richieste più semplice, il servizio di altri tipi di flussi (con la stessa intensità) sarà fornito con non meno efficienza.
In terzo luogo, è questo flusso che determina il processo di Markov nel sistema e, di conseguenza, la semplicità dell'analisi analitica del sistema. Per altri flussi, l'analisi del funzionamento del QS è complicata.
Spesso esistono sistemi in cui il flusso delle richieste di input dipende dal numero di richieste in servizio. Tali SMO sono chiamati Chiuso(altrimenti - aprire). Ad esempio, il lavoro di un laboratorio di comunicazione di un'associazione può essere rappresentato da un modello QS a circuito chiuso. Lascia che questo seminario sia progettato per servire le stazioni radio che sono nell'associazione. Ognuno di loro ha tasso di fallimento. Il flusso di input dell'apparecchiatura guasta avrà intensità:
dov'è il numero di stazioni radio già in officina per riparazioni.
Le applicazioni possono disporre di diritti diversi per l'avvio del servizio. In questo caso, si dice che le applicazioni siano eterogeneo. I vantaggi di alcuni flussi applicativi rispetto ad altri sono dati dalla scala di priorità.
Una caratteristica importante del flusso di input è il coefficiente di variazione:
dove è l'aspettativa matematica della lunghezza dell'intervallo;
Deviazione standard di una variabile casuale (lunghezza dell'intervallo).
Per il flusso più semplice 
Per la maggior parte dei thread reali.
Quando il flusso è regolare, deterministico.
Il coefficiente di variazione- una caratteristica che riflette il grado di disparità di ricezione delle domande.
Canali di servizio (dispositivi). Un QS può avere uno o più dispositivi di servizio (canali). Secondo questo QS sono chiamati monocanale o multicanale.
Multicanale QS può essere costituito dallo stesso tipo o da tipi diversi di dispositivi. I dispositivi di servizio possono essere:
La caratteristica principale del canale è il tempo di servizio. Di norma, il tempo di servizio è un valore casuale.
Di solito, i professionisti presumono che il tempo di servizio abbia una legge di distribuzione esponenziale:
dove - intensità del servizio, ;
Aspettativa matematica del tempo di servizio.
Cioè, il processo di servizio è markoviano e questo, come ora sappiamo, fornisce una notevole comodità nella modellazione matematica analitica.
Oltre all'esponenziale, ci sono distribuzioni -Erlang, iperesponenziale, triangolare e alcune altre. Ciò non deve confonderci, poiché è dimostrato che il valore dei criteri di efficienza QS non dipende molto dalla forma della legge di distribuzione della probabilità del tempo di servizio.
Nello studio di QS, l'essenza del servizio non viene presa in considerazione, qualità del servizio.
I canali possono essere assolutamente affidabile, cioè non fallire. Piuttosto, può essere accettato nello studio. I canali possono avere massima affidabilità. In questo caso, il modello QS è molto più complicato.
Coda delle applicazioni. A causa della natura casuale dei flussi di richieste e servizi, una richiesta in arrivo può trovare il canale o i canali occupati a servire la richiesta precedente. In questo caso, lascerà il QS non servito o rimarrà nel sistema, in attesa dell'inizio del suo servizio. Di conseguenza, ci sono:
CMO con aspettativa sono caratterizzati dalla presenza di code. Una coda può avere una capacità limitata o illimitata: 
.
I ricercatori sono generalmente interessati alle seguenti caratteristiche statistiche associate alla permanenza delle domande in coda:
Spesso ci sono CMO in cui le applicazioni hanno tempo limitato in linea indipendentemente dalla sua capacità. Tali QS sono anche indicati come QS di tipo misto.
Flusso in uscitaè il flusso di richieste servite in uscita dal QS.
Ci sono casi in cui le applicazioni passano attraverso diversi QS: connessione di transito, pipeline di produzione, ecc. In questo caso, il flusso in uscita è in entrata per il prossimo QS. Viene chiamato un insieme di QS sequenzialmente interconnessi QS multifase o reti OCM.
Il flusso in entrata del primo QS, essendo passato attraverso il successivo QS, è distorto e questo rende difficile la modellazione. Tuttavia, va tenuto presente che con il flusso di input e il servizio esponenziale più semplici (ovvero nei sistemi di Markov), il flusso di output è anche il più semplice. Se il tempo di servizio ha una distribuzione non esponenziale, allora il flusso in uscita non solo non è semplice, ma anche non ricorrente.
Si noti che gli intervalli tra le richieste in uscita non sono gli stessi degli intervalli di servizio. Dopotutto, potrebbe risultare che dopo la fine del servizio successivo, QS sia inattivo per un po 'a causa della mancanza di applicazioni. In questo caso
È necessario per risolvere i problemi 1-3. I dati iniziali sono riportati in tabella. 2–4.
Alcune notazioni utilizzate nella teoria delle code per le formule:
n è il numero di canali nel QS;
λ è l'intensità del flusso in entrata delle applicazioni P in;
v è l'intensità del flusso in uscita delle domande P out;
μ è l'intensità del flusso di servizio P circa;
ρ è l'indicatore di carico del sistema (traffico);
m è il numero massimo di posti in coda, che limita la lunghezza della coda delle domande;
i è il numero di fonti di richiesta;
p k è la probabilità del k-esimo stato del sistema;
p o - la probabilità di inattività dell'intero sistema, ad es. la probabilità che tutti i canali siano liberi;
p syst è la probabilità di accettare una domanda nel sistema;
p ref - la probabilità di rifiuto della domanda nella sua accettazione nel sistema;
ð about - la probabilità che l'applicazione venga gestita;
A è il throughput assoluto del sistema;
Q è il throughput relativo del sistema;
Och - il numero medio di applicazioni in coda;
Informazioni: il numero medio di applicazioni in servizio;
Sist - il numero medio di applicazioni nel sistema;
Och - tempo medio di attesa per un'applicazione in coda;
Tb - tempo medio di evasione della richiesta, relativo alle sole richieste evase;
Sis è il tempo medio di permanenza di un'applicazione nel sistema;
Ozh - il tempo medio che limita l'attesa di un'applicazione in coda;
è il numero medio di canali occupati.
Il throughput assoluto di QS A è il numero medio di applicazioni che il sistema può servire per unità di tempo.
Il throughput QS relativo Q è il rapporto tra il numero medio di richieste servite dal sistema per unità di tempo e il numero medio di richieste ricevute durante questo periodo.
Quando si risolvono problemi di accodamento, è necessario rispettare la seguente sequenza:
1) determinazione del tipo di QS secondo Tabella. 4.1;
2) la scelta delle formule in funzione del tipo di QS;
3) risoluzione dei problemi;
4) formulazione di conclusioni sul problema.
1. Schema di morte e riproduzione. Sappiamo che, dato un grafico di stato etichettato, possiamo facilmente scrivere le equazioni di Kolmogorov per le probabilità di stato, e anche scrivere e risolvere equazioni algebriche per le probabilità finali. Per alcuni casi, le ultime equazioni riescono
decidere in anticipo, letteralmente. In particolare, ciò può essere fatto se il grafico di stato del sistema è il cosiddetto "schema di morte e riproduzione".
Il grafico di stato per lo schema di morte e riproduzione ha la forma mostrata in Fig. 19.1. La particolarità di questo grafico è che tutti gli stati del sistema possono essere inseriti in una catena, in cui ciascuno degli stati medi ( S 1 , S 2 ,…,S n-1) è collegato da una freccia avanti e indietro con ciascuno degli stati vicini: destra e sinistra e gli stati estremi (S 0 , S n) - con un solo stato confinante. Il termine "schema di morte e riproduzione" deriva da problemi biologici, in cui un cambiamento nella dimensione di una popolazione è descritto da un tale schema.
Lo schema della morte e della riproduzione si incontra molto spesso in vari problemi di pratica, in particolare - nella teoria dell'accodamento, quindi è utile, una volta per tutte, trovare le probabilità finali degli stati per esso.
Supponiamo che tutti i flussi di eventi che trasferiscono il sistema lungo le frecce del grafico siano i più semplici (per brevità chiameremo anche il sistema S e il processo che si svolge in esso - il più semplice).
Utilizzando il grafico in Fig. 19.1, componiamo e risolviamo equazioni algebriche per le probabilità finali dello stato), l'esistenza deriva dal fatto che da ogni stato si può passare a tutti gli altri, il numero di stati è finito). Per il primo stato S 0 abbiamo:
(19.1)
Per il secondo stato S1:
A causa della (19.1), l'ultima uguaglianza è ridotta alla forma
dove K prende tutti i valori da 0 a P. Quindi le probabilità finali p0, p1,..., p n soddisfa le equazioni
(19.2)
inoltre, dobbiamo tener conto della condizione di normalizzazione
p 0 + p 1 + p 2 +…+ p n=1. (19.3)
Risolviamo questo sistema di equazioni. Dalla prima equazione (19.2) esprimiamo p 1 attraverso R 0 :
p 1 = p 0. (19.4)
Dalla seconda, tenuto conto della (19.4), si ottiene:
(19.5)
Dalla terza, tenuto conto della (19.5),
(19.6)
e in generale, per qualsiasi K(da 1 a n):
(19.7)
Prestiamo attenzione alla formula (19.7). Il numeratore è il prodotto di tutte le intensità nelle frecce che portano da sinistra a destra (dall'inizio allo stato dato S k), e nel denominatore - il prodotto di tutte le intensità in piedi sulle frecce che portano da destra a sinistra (dall'inizio a Sk).
Quindi, tutte le probabilità di stato R 0 , p 1 , ..., n espresso attraverso uno di essi ( R 0). Sostituiamo queste espressioni nella condizione di normalizzazione (19.3). Otteniamo mettendo tra parentesi R 0:
quindi otteniamo l'espressione per R 0 :
(abbiamo elevato la parentesi alla potenza di -1 per non scrivere frazioni a due piani). Tutte le altre probabilità sono espresse in termini di R 0 (vedi formule (19.4) - (19.7)). Si noti che i coefficienti per R 0 in ciascuno di essi non sono altro che membri successivi della serie dopo l'unità nella formula (19.8). Quindi, calcolando R 0 , abbiamo già trovato tutti questi coefficienti.
Le formule ottenute sono molto utili per risolvere i problemi più semplici della teoria delle code.
^ 2. Piccola formula. Ora deriviamo un'importante formula che mette in relazione (per il regime stazionario limitante) il numero medio di applicazioni l syst, situato nel sistema di accodamento (ovvero servito o in fila), e il tempo medio di permanenza dell'applicazione nel sistema w syst.
Consideriamo un qualsiasi QS (monocanale, multicanale, markoviano, non markoviano, con coda illimitata o delimitata) e due flussi di eventi ad esso associati: il flusso dei clienti in arrivo nel QS e il flusso dei clienti in uscita dal QS D.S. Se nel sistema si è instaurato un regime stazionario limitante, allora il numero medio di domande in arrivo nel QS nell'unità di tempo è uguale al numero medio di domande in uscita: entrambi i flussi hanno la stessa intensità λ.
Denota: X(t) - il numero di domande pervenute all'OCM prima del momento t. Y(t) - il numero di domande che hanno lasciato l'OCM
fino al momento t. Entrambe le funzioni sono casuali e cambiano bruscamente (incremento di uno) al momento dell'arrivo delle richieste (X(t)) e partenze delle domande (Y(t)). Tipo di funzioni X(t) e Y(t) mostrato in fig. 19.2; entrambe le linee sono a gradini, quella superiore lo è X(t), minore- Y(t). Ovviamente, per qualsiasi momento t la loro differenza Z(t)= X(t) - Y(t) non è altro che il numero di domande nel QS. Quando le linee X(t) e S(t) merge, non ci sono richieste nel sistema.
Considera un periodo di tempo molto lungo T(proseguendo mentalmente il grafico ben oltre il disegno) e calcolare per esso il numero medio di domande nel QS. Sarà uguale all'integrale della funzione Z(t) su questo intervallo diviso per la lunghezza dell'intervallo T:
l syst. = . (19.9) o
Ma questo integrale non è altro che l'area della figura ombreggiata in Fig. 19.2. Osserviamo bene questo disegno. La figura è composta da rettangoli, ognuno dei quali ha altezza pari a uno, e base pari al tempo di permanenza nel sistema dell'ordine corrispondente (il primo, il secondo, ecc.). Segnamo questi tempi t1, t2,...È vero, alla fine dell'intervallo T alcuni rettangoli entreranno nella figura ombreggiata non completamente, ma parzialmente, ma con una dimensione sufficientemente ampia T queste piccole cose non avranno importanza. Quindi, può essere considerato tale
(19.10)
dove l'importo si applica a tutte le domande pervenute nel tempo T.
Dividi i lati destro e sinistro (.19.10) per la lunghezza dell'intervallo T. Otteniamo, tenendo conto della (19.9),
l syst. = . (19.11)
Dividiamo e moltiplichiamo il lato destro della (19.11) per l'intensità X:
l syst. = .
Ma la grandezza Tλ non è altro che il numero medio di domande pervenute nel tempo ^ t. Se dividiamo la somma di tutti i tempi t io sul numero medio di domande si ricava il tempo medio di permanenza della domanda nel sistema w syst. Così,
l syst. = λ w syst. ,
w syst. = . (19.12)
Questa è la meravigliosa formula di Little: per qualsiasi QS, per qualsiasi natura del flusso delle applicazioni, per qualsiasi distribuzione del tempo di servizio, per qualsiasi disciplina di servizio il tempo medio di permanenza di una richiesta nel sistema è pari al numero medio di richieste nel sistema diviso l'intensità del flusso di richieste.
Esattamente allo stesso modo, si ricava la seconda formula di Little, che mette in relazione il tempo medio che l'applicazione trascorre in coda ^ Wow e il numero medio di domande in coda l ah:
w ah = . (19.13)
Per l'output, è sufficiente invece della linea di fondo in Fig. 19.2 assumere una funzione U(t)- il numero di domande rimaste fino al momento t non dal sistema, ma dalla coda (se un'applicazione che è entrata nel sistema non entra in coda, ma va subito in servizio, possiamo comunque considerare che entra in coda, ma vi rimane per tempo zero) .
Le formule di Little (19.12) e (19.13) giocano un ruolo importante nella teoria delle code. Sfortunatamente, nella maggior parte dei manuali esistenti, queste formule (provate in una forma generale relativamente recente) non sono fornite 1).
§ 20. I sistemi di accodamento più semplici e le loro caratteristiche
In questa sezione considereremo alcuni dei QS più semplici e ricaveremo espressioni per le loro caratteristiche (indicatori di prestazione). Allo stesso tempo, dimostreremo le principali tecniche metodologiche caratteristiche della teoria elementare, "markoviana", delle code. Non perseguiremo il numero di campioni QS per i quali verranno derivate le espressioni finali delle caratteristiche; questo libro non è una guida alla teoria dell'accodamento (tale ruolo è svolto molto meglio da manuali speciali). Il nostro obiettivo è quello di introdurre il lettore ad alcuni "trucchi" per facilitare la strada attraverso la teoria dell'accodamento, che in un certo numero di libri disponibili (anche affermando di essere popolare) può sembrare una sconclusionata raccolta di esempi.
Tutti i flussi di eventi che trasferiscono QS da stato a stato, in questa sezione, considereremo il più semplice (senza specificarlo ogni volta in modo specifico). Tra questi ci sarà il cosiddetto "flusso di servizio". Significa il flusso di richieste servite da un canale continuamente occupato. In questo stream l'intervallo tra gli eventi, come sempre nello stream più semplice, ha una distribuzione esponenziale (molti manuali dicono invece: "il tempo di servizio è esponenziale", noi stessi useremo questo termine in futuro).
1) In un libro popolare viene data una derivazione un po' diversa, rispetto a quanto sopra, della formula di Little. In generale, la conoscenza di questo libro ("Seconda conversazione") è utile per una prima conoscenza della teoria delle code.
In questa sezione si darà per scontata la distribuzione esponenziale del tempo di servizio, come sempre per il sistema “più semplice”.
Introdurremo le caratteristiche di efficienza del QS in esame nel corso della presentazione.
^ 1. P-channel QS con errori(problema Erlang). Qui consideriamo uno dei primi nel tempo, problemi "classici" della teoria delle code;
questo problema è nato dalle esigenze pratiche della telefonia ed è stato risolto all'inizio del nostro secolo dal matematico danese Erlant. L'attività è impostata come segue: c'è P canali (linee di comunicazione), che ricevono un flusso di applicazioni con intensità λ. Il flusso di servizio ha un'intensità μ (il reciproco del tempo medio di servizio t di). Trova le probabilità finali degli stati QS, nonché le caratteristiche della sua efficienza:
^A- throughput assoluto, ovvero il numero medio di applicazioni servite per unità di tempo;
Q- throughput relativo, ovvero la quota media di richieste in entrata servite dal sistema;
^ Rotk- la probabilità di fallimento, ovvero il fatto che l'applicazione lascerà il QS non servito;
K- numero medio di canali occupati.
Soluzione. Stati del sistema ^ S(QS) sarà numerato in base al numero di richieste presenti nel sistema (in questo caso coincide con il numero di canali occupati):
S0 - non ci sono applicazioni nell'OCM,
S 1 - c'è una richiesta nel QS (un canale è occupato, il resto è libero),
Sk- nell'OMU è K applicazioni ( K i canali sono occupati, il resto è libero),
S n - nell'OMU è P applicazioni (tutte n i canali sono occupati).
Il grafico dello stato QS corrisponde allo schema della morte nella riproduzione (Fig. 20.1). Contrassegniamo questo grafico: mettiamo giù l'intensità dei flussi di eventi vicino alle frecce. Da S 0 dentro S1 il sistema è trasferito da un flusso di richieste con intensità λ (appena arriva una richiesta il sistema salta da S0 in S1). Lo stesso flusso di applicazioni traduce
Un sistema da qualsiasi stato sinistro a uno stato adiacente destro (vedere le frecce in alto nella Figura 20.1).
Abbassiamo l'intensità delle frecce inferiori. Lascia che il sistema sia nello stato ^ S 1 (un canale funziona). Produce μ servizi per unità di tempo. Mettiamo giù la freccia S 1 →S 0 intensità μ. Ora immagina che il sistema sia nello stato S2(due canali funzionano). Per lei andare a S 1 ,è necessario che il primo canale o il secondo finiscano di servire; l'intensità totale dei loro flussi di servizio è di 2μ; metterlo alla freccia corrispondente. Il flusso di servizio totale dato dai tre canali ha un'intensità di 3μ, K canali - km. Mettiamo giù queste intensità nelle frecce inferiori in Fig. 20.1.
E ora, conoscendo tutte le intensità, useremo le formule già pronte (19.7), (19.8) per le probabilità finali nello schema di morte e riproduzione. Dalla formula (19.8) si ottiene:
Termini di scomposizione 
saranno i coefficienti per p 0 nelle espressioni per p1
Si noti che le formule (20.1), (20.2) non includono le intensità λ e μ separatamente, ma solo come rapporto λ/μ. Denota
λ/μ = ρ (20.3)
E chiameremo il valore di p "l'intensità ridotta del flusso di applicazioni". Il suo significato è il numero medio di richieste che arrivano per il tempo medio di servizio di una richiesta. Usando questa notazione, riscriviamo le formule (20.1), (20.2) nella forma:
Le formule (20.4), (20.5) per le probabilità dello stato finale sono chiamate formule di Erlang, in onore del fondatore della teoria delle code. La maggior parte delle altre formule di questa teoria (oggi ce ne sono più dei funghi nella foresta) non portano nomi speciali.
Quindi, si trovano le probabilità finali. Sulla base di essi, calcoleremo le caratteristiche di efficienza QS. Prima troviamo ^ Rotk. - la probabilità che la richiesta in arrivo venga rifiutata (non verrà servita). Per questo è necessario che tutti P i canali erano occupati, quindi
R ok = R n = . (20.6)
Da qui troviamo il relativo throughput - la probabilità che l'applicazione venga servita:
D = 1 - P aprire = 1 - (20,7)
Otteniamo il throughput assoluto moltiplicando l'intensità del flusso di richieste λ per Q:
UN = λQ = λ . (20.8)
Resta solo da trovare il numero medio di canali occupati K. Questo valore potrebbe essere trovato "direttamente", come l'aspettativa matematica di una variabile casuale discreta con possibili valori 0, 1, ..., P e le probabilità di questi valori p 0 p 1 , ..., p n:
K = 0 · p 0 + uno · p 1 + 2 · p 2 + ... + n · p.n.
Sostituendo qui le espressioni (20.5) per R K , (k = 0, 1, ..., P) ed eseguendo le opportune trasformazioni, alla fine otterremmo la formula corretta per K. Ma lo ricaveremo molto più facilmente (eccolo, uno dei "piccoli trucchi"!) In effetti, conosciamo il throughput assoluto MA. Questo non è altro che l'intensità del flusso di applicazioni servite dal sistema. Ogni impiegato per unità di tempo soddisfa una media di |l richieste. Quindi il numero medio di canali occupati è
k = A/μ, (20.9)
oppure, data la (20.8),
K = 
(20.10)
Incoraggiamo il lettore a elaborare l'esempio da solo. C'è una stazione di comunicazione con tre canali ( n= 3), l'intensità del flusso delle applicazioni λ = 1,5 (applicazioni al minuto); tempo medio di servizio per richiesta t v = 2 (min.), tutti i flussi di eventi (come in questo intero paragrafo) sono i più semplici. Trova le probabilità dello stato finale e le caratteristiche prestazionali del QS: A, Q, P ok, K. Nel caso, ecco le risposte: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, pag 3 = 9/26 ≈ 0,346,
MA≈ 0,981, Q ≈ 0,654, P aperto ≈ 0,346, k ≈ 1,96.
Dalle risposte, tra l'altro, si evince che il nostro QS è ampiamente sovraccarico: su tre canali, in media, circa due sono occupati e circa il 35% delle applicazioni in arrivo rimane non servito. Invitiamo il lettore, se curioso e non pigro, a scoprire: quanti canali saranno necessari per soddisfare almeno l'80% delle domande in arrivo? E quale quota dei canali sarà inattiva contemporaneamente?
C'è già qualche accenno di ottimizzazione. In effetti, il contenuto di ciascun canale per unità di tempo costa un certo importo. Allo stesso tempo, ogni applicazione servita porta un reddito. Moltiplicando questo reddito per il numero medio di domande MA, servito per unità di tempo, otterremo il reddito medio da CMO per unità di tempo. Naturalmente, con l'aumentare del numero di canali, questo reddito cresce, ma crescono anche i costi legati alla manutenzione dei canali. Cosa supererà - un aumento delle entrate o delle spese? Dipende dalle condizioni dell'operazione, dal "canone del servizio applicativo" e dal costo di mantenimento del canale. Conoscendo questi valori, puoi trovare il numero ottimale di canali, il più conveniente. Non risolveremo un problema del genere, lasciando che lo stesso "lettore non pigro e curioso" inventi un esempio e lo risolva. In generale, inventare problemi sviluppa più che risolvere quelli già impostati da qualcuno.
^ 2. QS a canale singolo con coda illimitata. In pratica, QS a un canale con una coda è abbastanza comune (un medico che serve i pazienti; un telefono pubblico con una cabina; un computer che evade gli ordini degli utenti). Nella teoria dell'accodamento, anche i QS a canale singolo con coda occupano un posto speciale (la maggior parte delle formule analitiche finora ottenute per i sistemi non markoviani appartengono a tali QS). Pertanto, presteremo particolare attenzione al QS a canale singolo con una coda.
Lascia che ci sia un QS a canale singolo con una coda su cui non sono imposte restrizioni (né sulla lunghezza della coda, né sul tempo di attesa). Questo QS riceve un flusso di richieste con intensità λ ; il flusso di servizio ha un'intensità μ che è inversa al tempo medio di servizio della richiesta t di. È necessario trovare le probabilità finali degli stati QS, nonché le caratteristiche della sua efficienza:
l syst. - numero medio di domande nel sistema,
w syst. - tempo medio di permanenza della domanda nel sistema,
^L ah- il numero medio di domande in coda,
w oh - il tempo medio che un'applicazione trascorre in coda,
P zan - la probabilità che il canale sia occupato (il grado di caricamento del canale).
Per quanto riguarda il throughput assoluto MA e relativo Q, quindi non è necessario calcolarli:
a causa del fatto che la coda è illimitata, ogni applicazione verrà servita prima o poi, quindi A \u003d λ, per la stessa ragione Q= 1.
Soluzione. Gli stati del sistema, come prima, saranno numerati in base al numero di applicazioni presenti nel QS:
S 0 - il canale è gratuito
S 1 - il canale è occupato (serve la richiesta), non c'è coda,
S 2 - il canale è occupato, una richiesta è in coda,
S k - il canale è occupato, K- 1 applicazioni sono in coda,
Teoricamente, il numero di stati non è limitato da nulla (infinitamente). Il grafico di stato ha la forma mostrata in Fig. 20.2. Questo è uno schema di morte e riproduzione, ma con un numero infinito di stati. Secondo tutte le frecce, il flusso delle richieste con intensità λ trasferisce il sistema da sinistra a destra e da destra a sinistra - il flusso del servizio con intensità μ.
Prima di tutto, chiediamoci, ci sono probabilità finali in questo caso? Dopotutto, il numero di stati del sistema è infinito e, in linea di principio, a t → ∞ la coda può crescere all'infinito! Sì, è vero: le probabilità finali per un tale QS non esistono sempre, ma solo quando il sistema non è sovraccarico. Si può dimostrare che se ρ è strettamente minore di uno (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ cresce indefinitamente. Questo fatto sembra particolarmente “incomprensibile” per ρ = 1. Sembrerebbe che non ci siano requisiti impossibili per il sistema: durante il servizio di una domanda, in media, arriva una domanda e tutto dovrebbe essere in ordine, ma in realtà è non è. Per ρ = 1, il QS fa fronte al flusso di richieste solo se questo flusso è regolare, e anche il tempo di servizio non è casuale, pari all'intervallo tra le richieste. In questo caso "ideale", non ci sarà alcuna coda nel QS, il canale sarà continuamente occupato ed emetterà regolarmente richieste servite. Ma non appena il flusso delle richieste o il flusso del servizio diventano almeno un po' casuali, la coda crescerà all'infinito. In pratica, questo non accade solo perché "un numero infinito di applicazioni in coda" è un'astrazione. Questi sono gli errori grossolani a cui può portare la sostituzione di variabili casuali con le loro aspettative matematiche!
Ma torniamo al nostro QS monocanale con coda illimitata. A rigor di termini, le formule per le probabilità finali nello schema di morte e riproduzione sono state derivate da noi solo per il caso di un numero finito di stati, ma prendiamoci delle libertà: le useremo per un numero infinito di stati. Calcoliamo le probabilità finali degli stati secondo le formule (19.8), (19.7). Nel nostro caso, il numero di termini nella formula (19.8) sarà infinito. Otteniamo un'espressione per p0:
p 0 = -1 =
\u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)
La serie nella formula (20.11) è una progressione geometrica. Sappiamo che per ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., pk , ... esistono solo per r<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 - p. (20.12)
Probabilità p 1 , p 2 , ..., p K ,... può essere trovato dalle formule:
p1 = ρ p 0 , p 2= ρ2 p 0 ,…,p k = ρ p0, ...,
Da cui, tenendo conto della (20.12), troviamo infine:
p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p K =ρ K(1 - p), . . .(20.13)
Come puoi vedere, le probabilità p0, p1, ..., p k , ... formare una progressione geometrica con denominatore p. Stranamente, il più grande di loro p 0 - la probabilità che il canale sia libero. Non importa quanto sia caricato il sistema con la coda, se solo è in grado di far fronte al flusso di applicazioni (ρ<1), самое вероятное число заявок в системе будет 0.
Trova il numero medio di domande nel QS ^L sist. . Qui devi armeggiare un po '. Valore casuale Z- numero di richieste nel sistema - ha valori possibili 0, 1, 2, .... K, ... con probabilità p0, p 1 , p 2 , ..., p K , ... La sua aspettativa matematica è
l sistema = 0 p 0 + uno · p 1 + 2 p 2 +…+K · p k +…= (20.14)
(la somma non è presa da 0 a ∞, ma da 1 a ∞, poiché il termine zero è uguale a zero).
Sostituiamo nella formula (20.14) l'espressione per p k (20.13):
l syst. = 
Togliamo ora il segno della somma ρ (1-ρ):
l syst. = ρ(1-ρ)
Anche qui applichiamo il “piccolo trucco”: Kρ K-1 non è altro che la derivata rispetto a ρ dell'espressione ρ K; significa,
l syst. = ρ(1-ρ)
Scambiando le operazioni di derivazione e sommatoria si ottiene:
l syst. = ρ (1-ρ) (20.15)
Ma la somma nella formula (20.15) non è altro che la somma di una progressione geometrica infinitamente decrescente con primo termine ρ e denominatore ρ; questo importo
uguale a , e la sua derivata .Sostituendo questa espressione nella (20.15), otteniamo:
l sistema = . (20.16)
Bene, ora applichiamo la formula di Little (19.12) e troviamo il tempo medio di permanenza di un'applicazione nel sistema:
w sistema = (20.17)
Trova il numero medio di domande in coda l ah. Argomenteremo come segue: il numero di domande in coda è uguale al numero di domande nel sistema meno il numero di domande in servizio. Quindi (secondo la regola dell'addizione delle aspettative matematiche), il numero medio di domande in coda l pt è pari al numero medio di domande nel sistema l syst meno il numero medio di richieste in servizio. Il numero di richieste in servizio può essere zero (se il canale è libero) o uno (se è occupato). L'aspettativa matematica di una tale variabile casuale è uguale alla probabilità che il canale sia occupato (l'abbiamo indicato R Zan). Ovviamente, R zan è uguale a uno meno la probabilità p 0 che il canale è gratuito:
R zan = 1 - R 0 = pag. (20.18)
Pertanto, il numero medio di richieste in servizio è pari a
^L circa= ρ, (20.19)
l ah = l sist – ρ =
e infine
l pt = (20.20)
Usando la formula di Little (19.13), troviamo il tempo medio che l'applicazione trascorre in coda:
(20.21)
Pertanto, sono state trovate tutte le caratteristiche dell'efficienza QS.
Suggeriamo al lettore di risolvere da solo un esempio: un QS monocanale è uno scalo di smistamento ferroviario, che riceve il flusso più semplice di treni con intensità λ = 2 (treni all'ora). Servizio (scioglimento)
la composizione dura un tempo casuale (dimostrativo) con un valore medio t circa = 20(min.). Nel parcheggio arrivi della stazione sono presenti due binari sui quali i treni in arrivo possono attendere il servizio; se entrambi i binari sono occupati, i treni sono costretti ad attendere sui binari esterni. È necessario trovare (per la modalità di funzionamento stazionaria e limitante della stazione): media, numero di treni l sistema relativo alla stazione, tempo medio w sistema di sosta in stazione (su binari interni, su binari esterni e in manutenzione), numero medio l pt di treni in attesa in coda per lo sbandamento (non importa su quali binari), tempo medio w I punti restano in lista d'attesa. Inoltre, prova a trovare il numero medio di treni in attesa di essere sciolti sui binari esterni. l esterno e il tempo medio di questa attesa w esterno (le ultime due quantità sono correlate dalla formula di Little). Infine, trova la multa giornaliera totale W, che la stazione dovrà pagare per le controstallie dei treni sui binari esterni, se la stazione paga la multa a (rubli) per un'ora di controstallie di un treno. Nel caso, ecco le risposte: l syst. = 2 (composizione), w syst. = 1 (ora), l punti = 4/3 (composizione), w pt = 2/3 (ore), l esterno = 16/27 (composizione), w esterno = 8/27 ≈ 0,297 (ore). La sanzione media giornaliera W per l'attesa dei treni sui binari esterni si ottiene moltiplicando il numero medio di treni in arrivo in stazione al giorno, il tempo medio di attesa dei treni sui binari esterni e la sanzione oraria un: W ≈ 14.2 un.
^ 3. Re-channel QS con coda illimitata. Completamente simile al problema 2, ma un po' più complicato, il problema di n-canale QS con coda illimitata. La numerazione degli stati è sempre in base al numero di applicazioni nel sistema:
S0- non ci sono applicazioni in CMO (tutti i canali sono gratuiti),
S 1 - un canale è occupato, gli altri sono liberi,
S2- due canali sono occupati, il resto è libero,
S k- occupato K canali, il resto è gratuito,
S n- tutti sono occupati P canali (nessuna coda),
S+1- tutti sono occupati n canali, un'applicazione è in coda,
Sn+r - peso occupato P canali, r le applicazioni sono in coda
Il grafico di stato è mostrato in fig. 20.3. Invitiamo il lettore a considerare e giustificare i valori delle intensità indicate dalle frecce. Grafico fig. 20.3
λ λ λ λ λ λ λ λ λ
μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ
c'è uno schema di morte e riproduzione, ma con un numero infinito di stati. Enunciamo senza dimostrazione la condizione naturale per l'esistenza delle probabilità finali: ρ/ n<1. Если ρ/n≥ 1, la coda cresce all'infinito.
Supponiamo che la condizione ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 ci sarà una serie di termini contenenti fattoriali, più la somma di una progressione geometrica infinitamente decrescente con denominatore ρ/ n. Riassumendo, troviamo
(20.22)
Ora troviamo le caratteristiche dell'efficienza QS. Di questi, è più facile trovare il numero medio di canali occupati K== λ/μ, = ρ (questo è generalmente vero per qualsiasi QS con una coda illimitata). Trova il numero medio di applicazioni nel sistema l sistema e il numero medio di domande in coda l ah. Di questi, è più facile calcolare il secondo, secondo la formula
l ah =
eseguendo le trasformazioni corrispondenti secondo il campione del problema 2
(con derivazione della serie), si ottiene:
l ah = 
(20.23)
Sommando ad esso il numero medio di applicazioni in servizio (è anche il numero medio di canali occupati) K =ρ, otteniamo:
l sistema = l ah + ρ. (20.24)
Espressioni di divisione per l ah e l sist su λ , utilizzando la formula di Little si ottiene il tempo medio di permanenza di un'applicazione in coda e nel sistema:
(20.25)
Ora risolviamo un esempio interessante. Una biglietteria ferroviaria a due sportelli è una QS a due canali con coda illimitata che si stabilisce immediatamente a due sportelli (se uno sportello è libero, lo prende il passeggero successivo in fila). Il botteghino vende i biglietti in due punti: A e A. L'intensità del flusso di domande (passeggeri che vogliono acquistare un biglietto) per entrambi i punti A e Bè lo stesso: λ A = λ B = 0,45 (passeggeri al minuto), e in totale formano un flusso generale di applicazioni con un'intensità di λ A + λB = 0,9. Un cassiere impiega in media due minuti a servire un passeggero. L'esperienza insegna che le code si accumulano alla biglietteria, i passeggeri si lamentano della lentezza del servizio. MA e dentro A, creare due biglietterie specializzate (una finestra in ciascuna), vendendo i biglietti uno solo fino al punto MA, l'altro - solo al punto A. La solidità di questa proposta è controversa: alcuni sostengono che le code rimarranno le stesse. È necessario verificare l'utilità della proposta mediante calcolo. Poiché siamo in grado di calcolare le caratteristiche solo per il QS più semplice, assumiamo che tutti i flussi di eventi siano i più semplici (questo non influirà sul lato qualitativo delle conclusioni).
Bene, allora mettiamoci al lavoro. Consideriamo due opzioni per l'organizzazione della vendita dei biglietti: quella esistente e quella proposta.
Opzione I (esistente). Un QS a due canali riceve un flusso di applicazioni con intensità λ = 0,9; intensità del flusso di mantenimento μ = 1/2 = 0,5; ρ = λ/μ = l.8. Poiché ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. La media, il numero di domande in coda si trova con la formula (20.23): L och ≈ 7.68; il tempo medio di permanenza del cliente in coda (secondo la prima delle formule (20.25)), è pari a w punti ≈ 8,54 (minimo).
Opzione II (proposta). È necessario considerare due QS monocanale (due finestre specializzate); ciascuno riceve un flusso di richieste con intensità λ = 0,45; μ . ancora pari a 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) l ah = 8.1.
Eccone uno per te! La lunghezza della coda, si scopre, non solo non è diminuita, ma è aumentata! Forse il tempo medio di attesa in coda è diminuito? Vediamo. Delia l punti su λ = 0.45, otteniamo w pts ≈ 18 (minuti).
Questa è la razionalizzazione! Invece di diminuire, sia la lunghezza media della coda sia il tempo medio di attesa sono aumentati!
Proviamo a indovinare perché è successo? Dopo aver riflettuto, arriviamo alla conclusione: questo è accaduto perché nella prima variante (QS a due canali) la frazione media di tempo in cui ciascuno dei due cassieri è inattivo è minore: se non è impegnato a servire un passeggero che acquista un biglietto per il MA, può prendersi cura del passeggero che acquista un biglietto fino al punto A, e viceversa. Nella seconda variante, non c'è tale intercambiabilità: un cassiere non occupato se ne sta seduto pigramente...
Bene , va bene, - il lettore è pronto ad essere d'accordo, - l'aumento può essere spiegato, ma perché è così significativo? C'è un errore di calcolo qui?
E risponderemo a questa domanda. Non c'è errore. Il fatto , che nel nostro esempio, entrambi i QS stanno lavorando al limite delle loro capacità; se aumenti leggermente il tempo di servizio (cioè riduci μ), non saranno più in grado di far fronte al flusso di passeggeri e la coda inizierà a crescere all'infinito. E il "tempo morto extra" del cassiere in un certo senso equivale a una diminuzione della sua produttività μ.
Pertanto, il risultato dei calcoli, che a prima vista sembra paradossale (o anche semplicemente errato), risulta corretto e spiegabile.
Questo tipo di conclusioni paradossali, la cui ragione non è affatto ovvia, è ricca nella teoria dell'accodamento. L'autore stesso ha dovuto ripetutamente essere "sorpreso" dai risultati dei calcoli, che in seguito si sono rivelati corretti.
Riflettendo sull'ultimo compito, il lettore può porre la domanda in questo modo: dopotutto, se il botteghino vende i biglietti solo a un punto, allora, naturalmente, il tempo di servizio dovrebbe diminuire, beh, non della metà, ma almeno un po ', ma pensavamo che fosse ancora la media è 2 (min.). Invitiamo un lettore così esigente a rispondere alla domanda: quanto dovrebbe essere ridotto affinché la "proposta di razionalizzazione" diventi redditizia? Ancora una volta, incontriamo, sebbene elementare, ma ancora un problema di ottimizzazione. Con l'aiuto di calcoli approssimativi, anche sui modelli di Markov più semplici, è possibile chiarire il lato qualitativo del fenomeno: come è redditizio agire e come non è redditizio. Nella prossima sezione, introdurremo alcuni modelli elementari non markoviani che amplieranno ulteriormente le nostre possibilità.
Dopo che il lettore ha acquisito familiarità con i metodi per calcolare le probabilità dello stato finale e le caratteristiche di prestazione per il QS più semplice (ha imparato lo schema di morte e riproduzione e la formula Little), gli possono essere offerti altri due QS semplici per considerazione indipendente.
^ 4. QS a canale singolo con coda limitata. Il problema differisce dal Problema 2 solo per il fatto che il numero di richieste in coda è limitato (non può superare alcuni dati t). Se una nuova richiesta arriva nel momento in cui tutti i posti in coda sono occupati, lascia il QS non servito (respinto).
È necessario trovare le probabilità finali degli stati (a proposito, esistono in questo problema per qualsiasi ρ - dopo tutto, il numero di stati è finito), la probabilità di fallimento R ok, larghezza di banda assoluta MA, la probabilità che il canale sia occupato R zan, lunghezza media della coda l och, il numero medio di domande nell'OCM l sist , tempo medio di attesa in coda w oh , tempo medio di permanenza di una domanda nell'OCM w syst. Nel calcolo delle caratteristiche della coda si può utilizzare la stessa tecnica che abbiamo utilizzato nel Problema 2, con la differenza che è necessario riassumere non una progressione infinita, ma finita.
^ 5. QS a circuito chiuso con un canale e m fonti applicative. Per concretezza, impostiamo il compito nella seguente forma: un lavoratore serve t macchine, ognuna delle quali richiede di volta in volta una regolazione (correzione). L'intensità del flusso di domanda di ciascuna macchina funzionante è pari a λ . Se la macchina è fuori servizio nel momento in cui l'operaio è libero, va subito in servizio. Se è fuori servizio nel momento in cui l'operaio è occupato, fa la fila e aspetta che l'operaio sia libero. Tempo medio di installazione t giro = 1/μ. L'intensità del flusso di richieste che arrivano al lavoratore dipende da quante macchine stanno lavorando. Se funziona K macchine utensili, è uguale a Kλ. Trova le probabilità dello stato finale, il numero medio di macchine funzionanti e la probabilità che il lavoratore sia occupato.
Nota che in questo QS, le probabilità finali
esisterà per qualsiasi valore di λ e μ = 1/ t o, poiché il numero di stati del sistema è finito.
Breve teoria
Come indicatori dell'efficacia di QS con fallimenti, considereremo:
Il throughput assoluto del QS, ad es. il numero medio di domande servite per unità di tempo;
Rendimento relativo, ad es. la quota media di richieste in entrata servite dal sistema;
Probabilità di fallimento, ad es. il fatto che la domanda lascerà l'OCM incustodita;
Numero medio di canali occupati.
Consideriamo il classico problema di Erlang.
Ci sono canali che ricevono un flusso di applicazioni con intensità. Il flusso dei servizi ha un'intensità di . Trova le probabilità limite degli stati del sistema e gli indicatori della sua efficienza.
Il sistema (QS) ha i seguenti stati (li numeriamo in base al numero di clienti nel sistema):
Il grafico dello stato QS corrisponde al processo di morte e riproduzione ed è mostrato nella figura.
Il flusso di richieste trasferisce sequenzialmente il sistema da qualsiasi stato sinistro a quello vicino destro con la stessa intensità. L'intensità del flusso di servizi che trasferiscono il sistema da qualsiasi stato di destra a un vicino stato di sinistra cambia costantemente a seconda dello stato. Infatti, se il QS è nello stato (due canali sono occupati), può passare allo stato (un canale è occupato) quando il primo o il secondo canale termina il servizio, ovvero l'intensità totale dei loro flussi di servizio sarà . Allo stesso modo, il flusso totale di servizi che trasferisce il QS dallo stato (tre canali sono occupati) a avrà intensità, cioè ognuno dei tre canali può diventare libero, e così via.
Per lo schema di morte e riproduzione, otteniamo per la probabilità limite dello stato:
dove i termini dell'espansione saranno i coefficienti at nelle espressioni per le probabilità limite . Valore
si chiama intensità ridotta del flusso di richieste o intensità del carico del canale. Esprime il numero medio di richieste pervenute per il tempo medio di servizio di una richiesta. Adesso:
Le ultime formule per le probabilità marginali sono chiamate formule di Erlang in onore del fondatore della teoria delle code.
La probabilità di guasto QS è la probabilità marginale che tutti i canali del sistema siano occupati, ovvero:
Throughput relativo: la probabilità che l'applicazione venga servita:
Larghezza di banda assoluta:
Il numero medio di canali occupati è l'aspettativa matematica del numero di canali occupati:
dove sono le probabilità limite degli stati
Tuttavia, il numero medio di canali occupati può essere trovato più semplicemente se teniamo conto che il throughput assoluto del sistema non è altro che l'intensità del flusso di richieste servite dal sistema (per unità di tempo). Poiché ogni canale occupato soddisfa le richieste in media (per unità di tempo), il numero medio di canali occupati è:
Esempio di soluzione del problema
Il controllo del prodotto finito dell'azienda è svolto da tre controllori. Se un prodotto viene inviato per l'ispezione quando tutti gli ispettori sono impegnati a controllare i prodotti finiti, allora rimane deselezionato. Il numero medio di prodotti prodotti dall'azienda è di 20 pezzi/ora. Il tempo medio per il controllo di un prodotto è di 7 minuti.
Determinare gli indicatori di prestazione del dipartimento di controllo tecnico. Quanti controller devono essere installati affinché la probabilità di servizio sia almeno del 97%?
Sei arrivato su questa pagina mentre cercavi di risolvere un problema in un esame o in un test? Se ancora non sei riuscito a superare l'esame, la prossima volta concorda in anticipo sul sito web in merito Guida in linea sui metodi di soluzione ottimale.
Control è un sistema di accodamento multicanale aperto con denial of service.
Prendiamo l'ora come unità di tempo. Supponiamo che il controllo operi nello stato stazionario. Secondo il compito
–numero di canali di servizio
Prodotti all'ora: l'intensità del flusso di applicazioni
Articoli all'ora - portata del servizio
Calcoliamo le intensità relative delle transizioni da stato a stato:
Calcoliamo:
Probabilità di fallimento:
Probabilità di servizio
Larghezza di banda assoluta del sistema:
è il numero medio di applicazioni servite dal sistema per unità di tempo.
Il numero medio di canali occupati dal servizio applicativo:
Calcoliamo quanti controller devono essere installati in modo che la probabilità di servizio sia almeno del 97%:
Pertanto, affinché la probabilità del servizio sia almeno del 97%, è necessario disporre di 6 controllori.
medio il costo per risolvere il lavoro di controllo è di 700-1200 rubli (ma non meno di 300 rubli per l'intero ordine). Il prezzo è fortemente influenzato dall'urgenza della decisione (da giorni a diverse ore). Il costo della guida in linea nell'esame / test - da 1000 rubli. per la soluzione del biglietto.
L'applicazione può essere lasciata direttamente nella chat, avendo precedentemente gettato via la condizione dei compiti e informandoti delle scadenze per risolverlo. Il tempo di risposta è di diversi minuti.
Esempi di attività correlate
CMO con coda illimitata
Vengono fornite le informazioni teoriche necessarie e una soluzione esemplificativa del problema sull'argomento "Sistema di accodamento multicanale con coda illimitata", vengono considerati in dettaglio gli indicatori di un sistema di accodamento multicanale (QS) con attesa di servizio - il numero medio di canali occupati servendo un'applicazione, la lunghezza della coda, la probabilità di formazione della coda, lo stato privo di probabilità del sistema, il tempo medio di attesa nella coda.
Il problema dell'allocazione ottimale delle risorse
Vengono brevemente enunciati i principi fondamentali della programmazione dinamica (scheduling dinamico), vengono considerate le equazioni di Bellman. Il problema della distribuzione ottimale delle risorse tra le imprese è risolto in dettaglio.
Metodo del moltiplicatore di Lagrange
La pagina considera la ricerca di un estremo condizionale utilizzando il metodo dei moltiplicatori di Lagrange. La costruzione della funzione di Lagrange è mostrata nell'esempio della risoluzione di un problema di programmazione non lineare. Il problema risolto è preceduto da una breve teoria.
Vettore dei consumi finali e vettore della produzione lorda
Nell'esempio della risoluzione del problema, viene considerato il modello intersettoriale di Leontiev. Viene mostrato il calcolo della matrice dei coefficienti dei costi materiali diretti, della matrice "input-output", della matrice dei coefficienti dei costi indiretti, dei vettori del consumo finale e della produzione lorda.
