Engsetův vzorec - Engset formula

v teorie front, Engsetův vzorec se používá k určení pravděpodobnosti blokování fronty M / M / c / c / N (v Kendallova notace ).

Vzorec je pojmenován po svém vývojáři, T. O. Engset.

Příklad aplikace

Zvažte flotilu ${ displaystyle c}$ vozidla a ${ displaystyle N}$ operátory. Provozovatelé vstupují do systému náhodně a žádají o použití vozidla. Pokud nejsou k dispozici žádná vozidla, je žádající operátor „zablokován“ (tj. Operátor odjíždí bez vozidla). Majitel vozového parku by si chtěl vybrat ${ displaystyle c}$ malé, aby se minimalizovaly náklady, ale dostatečně velké, aby zajistily tolerovatelnost pravděpodobnosti blokování.

Vzorec

Nechat

• ${ displaystyle c> 0}$ být (celé číslo) počet serverů.
• ${ displaystyle N> c}$ být (celé číslo) počet zdrojů provozu;
• ${ displaystyle lambda> 0}$ být míra příchodu nečinného zdroje (tj. míra, při které bezplatný zdroj iniciuje požadavky);
• ${ displaystyle h> 0}$ být průměrná doba zadržení (tj. průměrná doba, kterou server potřebuje ke zpracování požadavku);

Poté pravděpodobnost blokování je dáno^[1]

${ displaystyle P = { frac {{ binom {N-1} {c}} left ( lambda h right) ^ {c}} { sum _ {i = 0} ^ {c} { binom {N-1} {i}} left ( lambda h right) ^ {i}}}.}$

Přeskupením výrazů lze výše uvedený vzorec přepsat na^[2]

${ displaystyle P = { frac {1} {{} _ {2} F_ {1} (1, -c; N-c; -1 / ( lambda h))}}}$

kde ${ displaystyle {} _ {2} F_ {1}}$ je Gaussian Hypergeometrická funkce.

Výpočet

Existuje několik rekurzí^[3] které lze použít k výpočtu ${ displaystyle P}$ numericky stabilním způsobem.

Alternativně jakýkoli číselný balíček, který podporuje Hypergeometrická funkce Některé příklady jsou uvedeny níže.

Krajta s SciPy

z scipy.special import hyp2f1P = 1.0 / hyp2f1(1, -C, N - C, -1.0 / (Lambda * h))

MATLAB s Symbolická matematická sada nástrojů

P = 1 / hypergeom([1, -C], N - C, -1 / (Lambda * h))

Neznámá míra příjezdu zdroje

V praxi se často stává, že míra příchodu zdroje ${ displaystyle lambda}$ není známo (nebo je těžké jej odhadnout) ${ displaystyle alpha> 0}$, nabízený provoz na zdroj je známo. V tomto případě lze vztah nahradit

${ displaystyle lambda h = { frac { alfa} {1- alfa (1-P)}}}$

mezi mírou příchodu zdroje a pravděpodobností blokování do vzorce Engset k dosažení rovnice pevného bodu

${ displaystyle P = f (P)}$

kde

${ displaystyle f (P) = { frac {1} {{} _ {2} F_ {1} (1, -c; N-c; 1-P-1 / alfa)}}}$

Výpočet

Zatímco výše uvedené odstraní neznámé ${ displaystyle lambda}$ z vzorce zavádí další bod složitosti: už nemůžeme přímo vypočítat pravděpodobnost blokování a místo toho musíme použít iterační metodu. Zatímco iterace s pevným bodem je lákavé, ukázalo se, že taková iterace je někdy odlišný při aplikaci na ${ displaystyle f}$.^[2] Alternativně je možné použít jednu z půlení nebo Newtonova metoda, pro které implementace open source je k dispozici.

Reference