Multi-channel smo na may walang limitasyong pila. Teorya ng Pagpila

Ang sistema ay tumatanggap ng isang Poisson na daloy ng mga kinakailangan na may intensity λ, ang daloy ng serbisyo ay may intensity μ, ang maximum na bilang ng mga lugar sa queue ay t. Kung ang isang claim ay pumasok sa system kapag ang lahat ng mga lugar sa queue ay napuno, ito ay umalis sa system na hindi naihatid.

Ang mga huling probabilidad ng mga estado ng naturang sistema ay palaging umiiral, dahil ang bilang ng mga estado ay may hangganan:

S 0 - ang sistema ay libre at idle;

S 1 - isang kahilingan ang inihain, ang channel ay abala, walang pila;

S 2 - isang aplikasyon ang inihain, ang isa ay nasa pila;

S m +1 - isang aplikasyon ang inihain, t pila.

Ang graph ng estado ng naturang sistema ay ipinapakita sa Figure 5:

S 0 S 1 S 2 S m+1

μ μ μ ………. μ μ

Figure 5: Single-channel na QS na may limitadong pila.

Sa pormula para sa R 0 hanapin ang kabuuan ng isang tiyak na bilang ng mga miyembro ng isang geometric na pag-unlad:

(52)

Isinasaalang-alang ang formula para sa ρ, nakuha namin ang expression:

Mayroong (m+2) na mga elemento ng isang geometric na progression sa mga panaklong na may unang miyembro na 1 at ang denominator na ρ. Ayon sa formula para sa kabuuan (m + 2) ng mga miyembro ng pag-unlad:

(54)

(55)

Ang mga formula para sa mga probabilidad ng mga estado ng limitasyon ay magiging ganito:

Probability ng Pagtanggi sa Serbisyo Tinukoy namin ang isang kahilingan bilang ang posibilidad na kapag ang isang kahilingan ay pumasok sa system, ang channel nito ay sasakupin at lahat ng mga lugar sa pila ay inookupahan din:

(57)

Kaya ang probabilidad ng serbisyo(pati na rin mula sa bandwidth ng carrier) ay katumbas ng mga probabilidad ng kabaligtaran na kaganapan:

Ganap na Bandwidth ay ang bilang ng mga kahilingang inihatid ng system bawat yunit ng oras:

(59)

Average na bilang ng mga kahilingan sa ilalim ng serbisyo:

(60)

(61)

Average na bilang ng mga application sa system:

(62)

Ang isang solong channel na QS na may limitadong pila ay maaaring isaalang-alang sa Mathcad.

Halimbawa:

Naghahain ang paradahan ng 3 kotse na may flow rate na 0.5 at isang average na oras ng serbisyo na 2.5 minuto. Tukuyin ang lahat ng mga tagapagpahiwatig ng system.

6 Multi-channel smoo na may walang limitasyong pila

Hayaang magbigay ng isang sistema S na mayroon P mga channel ng serbisyo na tumatanggap ng pinakasimpleng daloy ng mga kahilingan na may intensity λ. Hayaang ang daloy ng serbisyo din ang pinakasimple at may intensity μ. Ang pila para sa serbisyo ay hindi limitado.

Sa bilang ng mga application sa system, tinutukoy namin ang mga estado ng system: S 0 ,S 1 ,S 2 ,…,S k ,… S n , kung saan S k – ang estado ng system kapag mayroong k na mga kahilingan sa loob nito (ang maximum na bilang ng mga kahilingan sa ilalim ng serbisyo ay n). Ang graph ng estado ng naturang sistema ay inilalarawan bilang isang diagram sa Figure 6:

λ λ λ λ λ λ λ

……. …….

S 0 S 1 S 2 S m+1 S n

μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ

Figure 6: Multichannel QS na may walang limitasyong pila.

Ang intensity ng daloy ng mga serbisyo ay nag-iiba depende sa estado ng system: kμ sa paglipat mula sa estado S k sa estado S k -1 dahil alinman sa k mga channel; matapos ang lahat ng mga channel ay abala sa serbisyo, ang intensity ng daloy ng mga serbisyo ay nananatiling katumbas ng pμ, sa pagtanggap ng mga sumusunod na aplikasyon sa system.

Upang mahanap ang mga huling probabilidad ng mga estado, kumuha kami ng mga formula na katulad ng kung paano ito ginawa para sa isang solong channel na sistema.

(63)

Samakatuwid ang mga formula para sa mga huling probabilidad ay ipinahayag sa mga tuntunin ng

Para sa paghahanap R 0 makuha namin ang equation:

Para sa mga termino sa mga bracket, simula sa (n + 2)th, maaari mong ilapat ang formula para sa paghahanap ng kabuuan ng isang walang katapusang pagbaba ng geometric na pag-unlad sa unang termino at denominator ρ/n:

(66)

Sa wakas, nakuha namin ang formula ng Erlang para sa paghahanap ng posibilidad ng downtime ng system:

(67)

Magbigay tayo ng mga formula para sa pagkalkula ng mga pangunahing tagapagpahiwatig ng kahusayan ng system.

Haharapin ng system ang daloy ng mga kahilingan kung

kundisyon

, (68)

na nangangahulugan na ang bilang ng mga kahilingang natanggap ng system sa bawat yunit ng oras ay hindi lalampas sa bilang ng mga kahilingang inihatid ng system sa parehong oras. Kung saan posibilidad ng pagtanggi sa serbisyo katumbas ng zero.

Mula rito probabilidad ng serbisyo(pati na rin ang relatibong throughput system) ay katumbas ng mga probabilidad ng kabaligtaran na kaganapan, iyon ay, sa pagkakaisa:

(69)

Ganapthroughput- ang bilang ng mga application na inihatid ng system sa bawat yunit ng oras:

(70)

Kung ang sistema ay nakayanan ang daloy ng mga aplikasyon, pagkatapos ay nasa nakatigil na mode intensity ng outflow ay katumbas ng intensity ng daloy ng mga kahilingang pumapasok sa system, dahil ang lahat ng mga kahilingan ay sineserbisyuhan:

ν=λ . (71)

Dahil ang bawat channel ay naghahatid ng μ kahilingan sa bawat yunit ng oras, kung gayon average na busy channels maaaring kalkulahin:

(72)

Karaniwanorasserbisyo isang channel ng aplikasyon ;

. (73)

Ang posibilidad na, sa pagpasok sa system, ang isang order ay mauuwi sa isang pila ay katumbas ng posibilidad na mayroong higit sa P mga aplikasyon:

(74)

Ang bilang ng mga aplikasyon sa ilalim ng serbisyo, ay katumbas ng bilang ng mga abalang channel:

(75)

Average na bilang ng mga application sa queue:

(76)

Pagkatapos karaniwannumeromga aplikasyonsa system:

(77)

Average na oras ng paninirahan ng isang application sa system (sa pila):

(78)

(79)

Ang isang multi-channel na QS na may walang limitasyong queue ay maaaring isaalang-alang sa Mathcad system.

Halimbawa 1:

Ang hairdressing salon ay may 5 masters. Sa rush hour, ang intensity ng daloy ng mga customer ay 6 na tao. Sa oras. Ang serbisyo ng isang kliyente ay tumatagal ng average na 40 minuto. Tukuyin ang average na haba ng pila, sa pag-aakalang ito ay walang limitasyon.

Fragment ng paglutas ng problema sa Mathcad.

Halimbawa 2:

Ang opisina ng tiket sa tren ay may 2 bintana. Ang oras para maglingkod sa isang pasahero ay 0.5 minuto. Ang mga pasahero ay lumalapit sa opisina ng tiket sa mga grupo ng 3. Tukuyin ang lahat ng katangian ng system.

Fragment ng paglutas ng problema sa Mathcad.

Pagpapatuloy ng solusyon ng problema sa Mathcad.

Ang isang kahilingan ay tinanggihan ng serbisyo kapag ang lahat ng m na lugar sa pila ay inookupahan, ibig sabihin.:

Ang relatibong throughput ay:

Ganap na Bandwidth:

Karaniwang Mga Abala na Channel

21. Multichannel QS na may inaasahan

Isang system na may limitadong haba ng pila. Isaalang-alang ang isang channel QS na may paghihintay, na tumatanggap ng daloy ng mga kahilingan na may intensity ; intensity ng serbisyo (para sa isang channel); ang dami ng upuan sa pila.

Ang mga estado ng system ay binibilang ayon sa bilang ng mga kahilingan na konektado ng system:

walang pila:

Lahat ng channel ay libre;

Ang isang channel ay abala, ang iba ay libre;

Mga abalang channel, ang iba ay hindi;

Ang lahat ng mga channel ay abala, walang mga libre;

may pila:

Lahat ng n channel ay inookupahan; isang application ang nasa pila;

Lahat ng n channel ay inookupahan, r kahilingan ay nasa pila;

Ang lahat ng mga channel ay abala, ang mga kahilingan ay nasa pila.

Ang bawat arrow ay may katumbas na intensity ng mga daloy ng kaganapan. Ayon sa mga arrow mula kaliwa hanggang kanan, ang system ay palaging inililipat sa pamamagitan ng parehong daloy ng mga kahilingan na may intensity , ayon sa mga arrow mula sa kanan papuntang kaliwa, ang system ay inililipat ng isang daloy ng serbisyo, ang intensity nito ay katumbas ng, pinarami sa dami ng abalang channel.

Average na bilang ng mga abalang channel. Para sa QS na may pila, ang average na bilang ng mga abalang channel ay hindi tumutugma sa average na bilang ng mga kahilingan sa system: ang huling halaga ay naiiba sa una sa average na bilang ng mga kahilingan sa queue.

Tukuyin natin ang average na bilang ng mga abalang channel . Ang bawat abalang channel ay naghahatid ng average ng mga kahilingan sa bawat yunit ng oras, at ang QS sa kabuuan ay naghahatid ng average na A na mga kahilingan sa bawat yunit ng oras. Ang paghahati sa isa't isa, nakukuha natin:

Ang average na bilang ng mga customer sa queue ay maaaring direktang kalkulahin bilang inaasahang halaga discrete random variable:

Dito muli (expression sa mga bracket) ang derivative ng kabuuan ng isang geometric progression ay nangyayari gamit ang ratio para dito, nakukuha natin:

Average na bilang ng mga application sa system:

22. Average na oras ng paghihintay para sa isang aplikasyon sa pila. Isaalang-alang natin ang ilang sitwasyon na naiiba sa estado kung saan mahahanap ng bagong dating na kahilingan ang system at kung gaano ito katagal maghihintay para sa serbisyo.

Kung hindi makita ng entity na abala ang lahat ng channel, hindi na ito kailangang maghintay (ang mga kaukulang termino sa inaasahan sa matematika ay katumbas ng zero). Kung ang customer ay dumating sa sandaling ang lahat ng n channel ay inookupahan at walang pila, ito ay kailangang maghintay sa average para sa isang oras na katumbas ng (dahil ang "daloy ng mga release" ng mga channel ay may intensity ). Kung nakita ng isang customer na abala ang lahat ng channel at isang customer ang nasa unahan nito sa pila, kakailanganin itong maghintay sa average para sa oras (para sa bawat customer sa harap), atbp. Kung makita ito ng customer sa pila ng mga customer, ito ay kailangang maghintay sa karaniwan para sa oras. Kung ang isang bagong dating na customer ay nakahanap na ng m customer sa pila, hindi na ito maghihintay (ngunit hindi rin ihahatid). Nahanap namin ang average na oras ng paghihintay sa pamamagitan ng pagpaparami ng bawat isa sa mga halagang ito sa mga katumbas na probabilidad:

Tulad ng sa kaso ng isang solong channel na QS na may paghihintay, tandaan namin na ang expression na ito ay naiiba sa expression para sa average na haba ng queue (5.59) sa pamamagitan lamang ng factor , i.e.

Ang average na oras ng paninirahan ng isang kahilingan sa system, pati na rin para sa isang solong channel na QS, ay naiiba sa average na oras ng paghihintay sa average na oras ng serbisyo na pinarami ng kamag-anak. throughput:

23/24. Mga system na may walang limitasyong haba ng pila. Isinaalang-alang namin ang isang channel QS na may paghihintay, kapag hindi hihigit sa m na kahilingan ang maaaring nasa queue nang sabay.

Tulad ng dati, kapag sinusuri ang mga sistema nang walang mga paghihigpit, kinakailangang isaalang-alang ang mga nakuhang relasyon para sa .

Nakukuha namin ang mga probabilidad ng mga estado mula sa mga formula sa pamamagitan ng pagpasa sa limitasyon (sa ). Tandaan na ang kabuuan ng katumbas na geometric progression ay nagtatagpo para sa at diverges para sa > 1. Ipagpalagay na< 1 и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

Ang posibilidad ng pagkabigo, kamag-anak at ganap na throughput. Dahil ang bawat kahilingan ay ihahatid nang maaga o huli, ang mga katangian ng QS throughput ay magiging:

Ang average na bilang ng mga kahilingan sa queue ay nakuha mula sa (5.59):

isang average na oras ng paghihintay - mula (5.60):

Ang average na bilang ng mga abalang channel, tulad ng dati, ay tinutukoy sa mga tuntunin ng ganap na throughput:

Ang average na bilang ng mga customer na nauugnay sa QS ay tinukoy bilang ang average na bilang ng mga customer sa queue kasama ang average na bilang ng mga customer na nasa ilalim ng serbisyo (ang average na bilang ng mga abalang channel):

CMO na may limitadong oras ng paghihintay. Noong nakaraan, isinasaalang-alang namin ang mga system na may oras ng paghihintay na limitado lamang sa haba ng pila (ang bilang m ng mga customer nang sabay-sabay sa pila). Sa ganoong QS, ang isang customer, kapag inilagay sa isang pila, ay hindi umaalis dito hanggang sa maghintay para sa serbisyo. Sa pagsasagawa, mayroong QS ng isa pang uri, kung saan ang aplikasyon, pagkatapos maghintay ng ilang oras, ay maaaring umalis sa pila (ang tinatawag na "impatient" na mga aplikasyon).

Isaalang-alang ang isang QS ng ganitong uri, sa pag-aakalang ang hadlang sa oras ng paghihintay ay isang random na variable.

Ipagpalagay natin na mayroong n-channel na naghihintay na QS, kung saan hindi limitado ang bilang ng mga lugar sa pila, ngunit ang oras na manatili ang customer sa pila ay ilang random na variable na may average na halaga , kaya, para sa bawat customer sa ang pila, isang uri ng Poisson care flow" na may tindi

Kung ang daloy na ito ay Poisson, kung gayon ang prosesong magaganap sa QS ay magiging Markov. Hanapin natin ang mga probabilidad ng mga estado para dito. Ang pagbilang ng mga estado ng system ay nauugnay sa bilang ng mga kahilingan sa system - parehong inihatid at nakapila:

walang pila:

Lahat ng channel ay libre;

Ang isang channel ay abala;

Dalawang channel ang abala;

Lahat ng n channel ay inookupahan; may pila:

Lahat ng n channel ay inookupahan, isang kahilingan ang nasa pila;

Ang lahat ng mga channel ay abala, ang mga kahilingan ay nasa pila, at iba pa.

Ang graph ng mga estado at mga transition ng system ay ipinapakita sa fig. 5.10.

Lagyan natin ng label ang graph na ito tulad ng dati; lahat ng mga arrow na humahantong mula kaliwa hanggang kanan ay magkakaroon ng intensity ng daloy ng mga application. Para sa mga estadong walang pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay magkakaroon ng kabuuang intensity ng daloy ng serbisyo ng lahat ng abalang channel. Para sa mga estado na may pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay magkakaroon ng kabuuang intensity ng daloy ng serbisyo ng lahat ng n channel at ang katumbas na intensity ng daloy ng pag-alis sa pila. Kung mayroong r kahilingan sa pila, ang kabuuang intensity ng daloy ng mga pag-alis ay magiging katumbas ng

Tulad ng makikita mula sa graph, mayroong isang pattern ng pagpaparami at kamatayan; paglalapat ng mga pangkalahatang ekspresyon para sa paglilimita ng mga probabilidad ng mga estado sa pamamaraang ito (gamit ang pinaikling notasyon , isinusulat namin:

Tandaan natin ang ilang feature ng QS na may limitadong paghihintay kumpara sa dating itinuturing na QS na may mga kahilingang "pasyente".

Kung ang haba ng pila ay hindi limitado at ang mga customer ay "pasyente" (huwag umalis sa pila), kung gayon ang nakatigil na limitasyon na mode ay umiiral lamang sa kaso (ang kaukulang walang katapusang geometric na pag-unlad ay nag-iiba, na pisikal na tumutugma sa walang limitasyong paglaki ng pila. sa ).

Sa kabaligtaran, sa isang QS na may "impatient" na mga customer na umaalis sa pila nang maaga, ang steady-state na mode ng serbisyo ay palaging nakakamit, anuman ang pinababang intensity ng daloy ng customer . Ito ay sumusunod sa katotohanan na ang serye para sa denominator ng formula ay nagtatagpo para sa anumang positibong halaga ng at .

Para sa mga CMO na may "impatient" na mga application, ang konsepto ng "probability of failure" ay walang saysay - ang bawat aplikasyon ay nakakakuha sa linya, ngunit maaaring hindi maghintay para sa serbisyo, umaalis nang maaga.

Relative throughput, ang average na bilang ng mga application sa queue. Ang kamag-anak na throughput q ng naturang QS ay maaaring kalkulahin bilang mga sumusunod. Malinaw, lahat ng mga aplikasyon ay ihahatid, maliban sa mga umalis sa pila nang mas maaga sa iskedyul. Kalkulahin natin ang average na bilang ng mga kahilingan na nauuna sa iskedyul. Upang gawin ito, kinakalkula namin ang average na bilang ng mga application sa queue:

Para sa bawat isa sa mga kahilingang ito, mayroong "flux of exit" na may intensity na . Nangangahulugan ito na mula sa average na bilang ng mga kahilingan sa pila, sa karaniwan, ay aalis nang hindi naghihintay ng serbisyo, ang mga kahilingan sa bawat yunit ng oras at sa kabuuan sa bawat yunit ng oras, sa karaniwan, ay maseserbisyuhan.

mga aplikasyon. Ang relatibong throughput ng QS ay magiging:

Ang average na bilang ng mga abalang channel ay nakukuha pa rin sa pamamagitan ng paghahati sa absolute throughput A sa:

Ang average na bilang ng mga application sa queue. Ang kaugnayan (5.64) ay nagbibigay-daan sa amin na kalkulahin ang average na bilang ng mga kahilingan sa queue nang hindi nagsusuma walang katapusang hilera(5.63). Mula sa (5.64) nakukuha natin ang:

at ang average na bilang ng mga abalang channel na kasama sa formula na ito ay makikita bilang ang mathematical na inaasahan ng isang random na variable Z, na kumukuha ng mga halaga 0, 1, 2, ..., n na may probabilities , :

25. Mga laro na may magkasalungat na interes. Pangunahing konsepto. Payment matrix.

Ang isang sitwasyon kung saan ang dalawa o higit pang partido na naghahabol ng magkaibang layunin ay nagsasalpukan ay tinatawag na salungatan. Isa sa mga diskarte sa pagpapatupad ng optimization mat. Ang mga modelo sa ilalim ng mga kondisyon ng kawalan ng katiyakan, kapag lumitaw ang isang sitwasyon ng salungatan, ay isang teorya ng laro.

Game-event, na binubuo ng isang serye ng mga aksyon ng mga partido.

Ang mga patakaran ng laro ay isang hanay ng isang sistema ng mga kundisyon na kumokontrol sa mga posibleng opsyon para sa mga aksyon ng mga partido, ang dami ng impormasyon ng bawat panig tungkol sa pag-uugali ng isa, ang mga resulta na humahantong sa isang hanay ng mga posibleng pagpipilian para sa mga aksyon. Ang laro ay binubuo ng isang serye ng mga magkakasunod na galaw.

Ang isang paglipat ay ang pagpili ng isang aksyon mula sa isang hanay ng mga aksyon na ibinigay ng mga patakaran.

Tinatawag ang mga partidong sangkot sa tunggalian. mga manlalaro, at ang kinalabasan ng salungatan ay isang pagkatalo (panalo).

Ang diskarte ay tinatawag isang hanay ng mga panuntunan na tumutukoy sa pagpili ng opsyon sa bawat paglipat.

Tinatawag na pinakamainam. isang diskarte na, kapag ang laro ay inulit ng maraming beses, ay nagbibigay sa ibinigay na partido ng pinakamataas na posibleng average na kabayaran.

Mga laro ng diskarte nagmomodelo sila ng mga sitwasyon ng salungatan kung saan kumikilos ang hindi bababa sa dalawang partido, na bawat isa ay may sariling mga opsyon para sa pagkilos. Ang mga non-strategic na laro ay ginagaya ang mga sitwasyon ng salungatan kapag ang alinman sa isang panig ay kumilos, o mayroong isang koalisyon ng mga partido, na ang lahat ng mga kalahok ay may parehong hanay ng mga opsyon para sa pagkilos. Ang laro ay tinatawag na pares na laro kung eksaktong 2 manlalaro ang lumahok dito at maramihan kung ang bilang ng mga manlalaro ay higit sa dalawa. Ang isang pares na diskarte ay antagonistic kung ang mga layunin ng mga partido ay direktang kabaligtaran. Sa kasong ito, ang pakinabang ng isang manlalaro ay ang pagkawala ng isa pa. Ang mga huling diskarte ng laro ay naglalarawan sitwasyon ng tunggalian, kung saan ang lahat ng partido ay may limitadong bilang ng mga posibleng kurso ng aksyon. Kung ang kahit isang panig ay may walang katapusang bilang ng mga opsyon, ang laro ay kabilang sa klase ng walang katapusan. Sa isang larong one-move, may isang galaw ang bawat panig. Sa multi-pass, higit sa dalawang galaw ang ginawa.

Matrix laro na tinatawag. strategic pair antagonistic one-move game na may limitadong bilang ng mga opsyon para sa bawat panig.

Payment matrix- istatistikal na paraan paggawa ng desisyon, pagtulong sa tagapamahala na pumili mula sa mga posibleng alternatibo.

A, B	SA 1	SA 2	…	Bahay-panuluyan
A 1	isang 11	isang 12	…	isang 1n
A 2	isang 21	isang 22	…	isang 2n
…	…	…	…	…
Isang m	isang m1	isang m2	…	amn

Ang mga hilera ng matrix na ito ay tumutugma sa mga diskarte ng manlalaro A, at ang mga column ay mga diskarte ng manlalaro B.

26. Mas mababa at mas mataas na presyo ng laro. Prinsipyo ng Minimax.

Sa puso ng solusyon larong matrix namamalagi ang prinsipyo ng minimax o maximin, na binubuo sa katotohanan na ang isang panig ay sinusuri ang pagiging posible ng paglalapat ng alinman sa mga estratehiya nito, na nalikom mula sa posibilidad ng pinaka-hindi kanais-nais na paglipat ng pagtugon para sa kabilang panig.

Ang diskarte na pinili sa paraang ito ay ginagarantiyahan ang isang partido ng pinakamataas na posibleng pakinabang (A) na may pinaka hindi kanais-nais na diskarte para sa kanya para sa anumang partido.

A: sinusuri para sa bawat isa sa kanyang mga diskarte ang pinakamababang posibleng kabayaran αij..

αi= min αij i=1,m

βj= max αij j=1,n

α= max αi i=1,m

α= max min αij i=1,m, j=1,n ay ang mas mababang presyo ng laro

β= min max αij i=1,m, j=1,n ang pinakamataas na presyo ng laro

Ang diskarte ng manlalaro A na naghahatid ng pinakamataas na kabayaran ay tinatawag na pinakamataas na diskarte. Ang Strategy B na naghahatid ng pinakamababang pagkawala ay tinatawag na minimum na diskarte.

Tinatawag na value na υ=α=β. ang dalisay na halaga ng laro.

27. Mga larong may saddle point.

Tinatawag ang isang elemento ng payoff matrix na parehong minimum sa row nito at maximum sa column nito. saddle point.

Kung ang laro ay may saddle point, ang anumang panig na lumihis sa diskarteng pinili alinsunod sa prinsipyo ng minimax ay tiyak na mawawalan ng bisa, hangga't ang kabilang panig ay nananatili sa diskarte nito. Ang isang katulad na sitwasyon ay sitwasyon ng ekwilibriyo.

Kung mayroong saddle point, ang solusyon ng laro ay ang pinakamainam na pares ng diskarte (A * ij , B * ij) na naaayon sa puntong ito.

Ang hanay ng mga pinakamainam na estratehiya ay tinatawag. paglutas ng laro ng mga purong estratehiya.

1. Kung pinili ni A ang pinakamainam. diskarte, kung gayon anuman ang diskarte B, ang kanyang kabayaran ay hindi bababa sa netong halaga ng laro.

2. Kung pinili ni B ang pinakamainam. diskarte, at kahit anong diskarte A ang sundin, ang kabayaran ni B ay hindi lalampas sa netong halaga ng laro.

28. Paglutas ng laro sa magkahalong estratehiya. aktibong mga estratehiya. Theorem sa mga aktibong estratehiya.

Isaalang-alang ang α ≠β, α<β, α<υ<β.

Kung α ≠β, kung gayon ang naturang laro ay walang saddle point. Sa kasong ito, ang prinsipyo ng minimax o maximin ay hindi angkop.

(Desisyon ng mga laro 2x2)

Ipinapalagay ng mga pinaghalong diskarte na random na pipili ang bawat manlalaro mula sa mga posibleng purong diskarte, o bahagyang magpapatupad ng mga purong diskarte sa ibinigay na proporsyon.

Ang mga aktibong estratehiya ay yaong nangingibabaw sa iba.

Isaalang-alang ang laro 2xn

I-plot ang presyo ng player B sa axis.

Mula sa pinakamataas na punto ibinababa namin ang patayo.

Ang pinakamataas na punto ng mas mababang polyline ay ang punto ng intersection ng mga linya na tumutugma sa mga aktibong diskarte B*1 at B*2.

Kaya, ang orihinal na laro ay nabawasan sa isang 2v2 na laro.

Niresolba namin ang laro at hinahanap ang mga probabilidad ng mga aktibong diskarte. Mga posibilidad ng aktibong estratehiya.

Tinutumbas namin ang mga probabilidad ng mga passive na diskarte sa zero.

36. Laro 2 * 2. Analytical at graphical na paraan ng paglutas.

Sa pangkalahatan, ang laro 2 2 ay tinukoy ng matrix

Una sa lahat, ito ay kinakailangan upang suriin kung ang ibinigay na laro ay may saddle point. Kung oo, kung gayon ang laro ay may solusyon sa mga purong diskarte, at ang pinakamainam na diskarte ng mga manlalaro 1 at 2, ayon sa pagkakabanggit, ay ang purong maximin at purong minimax na diskarte. Kung ang larong may payoff matrix A ay walang mga purong diskarte, ang parehong mga manlalaro ay mayroon lamang mga pinakamainam na diskarte na gumagamit ng lahat ng kanilang mga purong diskarte na may positibong probabilidad. Kung hindi, ang isa sa mga manlalaro (halimbawa, 1) ay may purong pinakamainam na diskarte, habang ang isa ay may mga halo-halong diskarte lamang. Nang walang pagkawala ng pangkalahatan, maaari nating ipagpalagay na ang pinakamainam na diskarte para sa manlalaro 1 ay ang piliin ang unang hanay na may posibilidad na 1. Dagdag pa, sa pamamagitan ng ari-arian 1 sinusundan nito iyon a 11 = a 12 =  at ang matris ay may anyo

Madaling makita na para sa mga matrice ng form na ito, ang isa sa mga diskarte ng player 2 ay nangingibabaw. Samakatuwid, sa pamamagitan ng property 4, ang manlalarong ito ay may purong diskarte, na sumasalungat sa palagay.

Hayaan X =(, 1  ) ay ang pinakamainam na diskarte ng manlalaro 1. Dahil ang manlalaro 2 ay may magkahalong pinakamainam na diskarte, nakuha namin iyon mula sa property 1 (tingnan din ang property 7)

Ito ay sumusunod mula dito na kapag   0 matrix column PERO hindi maaaring proporsyonal sa isang salik ng proporsyonalidad maliban sa pagkakaisa. Kung ang koepisyent ng proporsyonalidad ay katumbas ng isa, kung gayon ang matrix PERO kumukuha ng form

at ang manlalaro 1 ay may purong pinakamainam na diskarte (pinili niya nang may probabilidad 1 ang isa sa mga hilera na ang mga elemento ay hindi bababa sa mga katumbas na elemento ng isa pa), na sumasalungat sa palagay. Samakatuwid, kung   0 at ang mga manlalaro ay mayroon lamang pinaghalong pinakamainam na diskarte, pagkatapos ay ang determinant ng matrix PERO iba sa zero. Ito ay sumusunod mula dito na ang huling sistema ng mga equation ay may natatanging solusyon. Ang paglutas nito, nahanap namin

;

Ang katulad na pangangatwiran ay humahantong sa amin sa katotohanan na ang pinakamainam na diskarte ng manlalaro 2 Y = ( , 1 -  ) natutugunan ang sistema ng mga equation

Ang graphical na paraan ay naaangkop sa mga laro kung saan ang kahit isang manlalaro ay may dalawang diskarte lamang.

Unang kaso.

Isaalang-alang ang isang (2x2) laro na may matrix walang saddle point.

Ang solusyon ng laro ay ang magkahalong diskarte ng mga manlalaro at , saan

x 1 - ang posibilidad na gagamitin ng unang manlalaro ang unang diskarte,

x 2 - ang posibilidad na gagamitin ng unang manlalaro ang pangalawang diskarte,

sa 1 - ang posibilidad na gagamitin ng pangalawang manlalaro ang unang diskarte,

sa 2 - ang posibilidad na gagamitin ng pangalawang manlalaro ang pangalawang diskarte.

Obvious naman yun

Hanapin natin ang solusyon ng laro sa pamamagitan ng graphical na pamamaraan (Larawan 1).

sa ehe OH magtabi ng isang segment na ang haba ay katumbas ng isa.

kaliwang dulo ( x = 0) tumutugma sa diskarte ng unang manlalaro A 1 , tama
(x = 1) - mga diskarte A 2 .

Ang panloob na mga punto ng segment ay tumutugma sa magkahalong mga diskarte
ang unang manlalaro, kung saan

Sa pamamagitan ng mga dulo ng segment gumuhit kami ng mga tuwid na linya na patayo sa axis OH, kung saan ipagpaliban natin ang kabayaran para sa kaukulang purong estratehiya. Kung gagamitin ng manlalaro B ang diskarte SA 1, pagkatapos ay ang kabayaran kapag ginamit ng unang manlalaro ang mga estratehiya A 1 at A 2 ay magiging ayon sa pagkakabanggit isang 11 at isang 21 . Ilagay natin ang mga puntong ito sa mga tuwid na linya at ikonekta ang mga ito sa isang segment Sa 1 Sa 1. Kung ang manlalaro A ay gumagamit ng magkahalong diskarte, ang kabayaran ay tumutugma sa ilang punto M, nakahiga sa segment na ito.

Katulad nito, ang segment B 2 B 2 ay binuo na naaayon sa diskarte SA 2 manlalaro V.

Kahulugan 20. Ang isang putol na linya na binubuo ng mga bahagi ng mga segment na nagpapakahulugan sa mga diskarte ng player B, na matatagpuan sa ibaba ng lahat ng mga segment, ay tinatawag ang mas mababang limitasyon ng pakinabang natanggap manlalaro A.

Kahulugan 21. Ang mga diskarte na ang mga bahagi ay bumubuo ng mas mababang payoff bound ay tinatawag mga aktibong estratehiya.

Sa laro (2x2) parehong mga diskarte ay aktibo.

putol na linya B 1 KV 2 ay ang lower bound ng payoff (Fig. 2) na natanggap ng player A. Point SA, kung saan ito ay pinakamataas na tumutukoy sa presyo ng laro at solusyon nito.

Hanapin ang pinakamainam na diskarte para sa unang manlalaro. Isinulat namin ang sistema ng mga equation

Pagtutumbas ng mga ekspresyon para sa v mula sa mga equation ng system at isinasaalang-alang na nakukuha natin

(1)

(2)

Pag-compile ng isang katulad na sistema

at binigyan ng kondisyon

mahahanap natin ang pinakamainam na diskarte para sa player B:

(3)

Kung ang isang 2xn o mx2 na laro ay hindi isang purong laro ng diskarte, dapat na subukang bawasan ang laki ng laro sa pamamagitan ng pagdoble at pangingibabaw. Kung nabigo ito, pagkatapos ay gamitin ang graph-analytical na paraan upang matukoy ang mga aktibong diskarte.

Magkomento. Ang mga aktibong estratehiya ay ang mga estratehiyang nangingibabaw sa iba (yaong nananatili pagkatapos ng pagbabawas)

Isaalang-alang ang laro 2xn

Nilulutas namin ang isang 2x2 na laro at hinahanap ang mga probabilidad ng mga aktibong diskarte. Nagtatalaga kami ng mga zero sa mga probabilidad ng mga passive na diskarte.

Isaalang-alang ang larong mx2

	SA 1	SA 2
A1	isang 11	isang 12
A2	isang 21	isang 22
…	…..	……
An	isang m1	isang m2

Ang ibabang punto ng itaas na putol na linya ay tumutugma sa mga aktibong estratehiya ai at aj.

Pagkatapos nito, ang problema ay nabawasan sa laki ng 2x2 at nalutas sa pamamagitan ng pamamaraan na nabanggit sa itaas.

38. laro m x n pagbabawas ng solusyon ng laro m x n sa isang linear na problema sa programming. Pangunahing teorama ng teorya ng laro.

Laki ng laro mxn walang malinaw na geometric na interpretasyon. Ang solusyon nito ay medyo matrabaho, ngunit wala itong pangunahing mga paghihirap, dahil maaari itong mabawasan sa paglutas ng isang linear na problema sa programming.

Mas kumplikadong mga problema sa teorya ng pila

Sa seksyong ito, maikli naming isasaalang-alang ang ilang isyu na nauugnay sa mga hindi-Markov QS. Sa ngayon, ang lahat ng mga formula ay hinango na natin, o hindi bababa sa maaaring makuha ng mambabasa, armado ng pamamaraan ng kamatayan at pagpaparami, pormula ni Little, at ang kakayahang mag-iba. Kung ano ang sasabihin sa talatang ito, ang mambabasa ay magkakaroon ng pananampalataya.

Hanggang ngayon, nakipag-usap lang kami sa pinakasimpleng QS, kung saan ang lahat ng daloy ng mga kaganapan na naglilipat sa kanila mula sa estado patungo sa estado ay ang pinakasimpleng. Ngunit paano kung hindi sila ang pinakasimple? Gaano katotoo ang pagpapalagay na ito? Gaano kabuluhan ang mga pagkakamaling dulot nito kapag ito ay nilabag? Susubukan naming sagutin ang lahat ng mga tanong na ito dito.

Nakakalungkot man, ngunit dapat nating aminin na sa larangan ng teorya ng pagpila na hindi Markovian, wala tayong espesyal na maipagmamalaki. Para sa hindi-Markovian QS, mayroon lamang mga hiwalay, nabasa na mga resulta na nagpapahintulot sa pagpapahayag sa isang tahasang, analytical na anyo ng mga katangian ng QS sa pamamagitan ng mga ibinigay na kondisyon ng problema - ang bilang ng mga channel, ang likas na katangian ng daloy ng mga aplikasyon, ang uri ng serbisyo pamamahagi ng oras. Ipinakita namin ang ilan sa mga resultang ito.

1. n-channel QS na may mga pagkabigo, na may pinakasimpleng daloy ng mga application at arbitrary na pamamahagi ng oras ng serbisyo. Sa nakaraang seksyon, nakuha namin ang mga formula ng Erlang (20.4), (20.5) para sa mga huling probabilidad ng mga estado ng QS na may mga pagkabigo. Medyo kamakailan lamang (noong 1959) B. A. Sevastyanov pinatunayan na ang mga formula na ito ay wasto hindi lamang para sa isang exponential, ngunit din para sa isang di-makatwirang pamamahagi ng oras ng serbisyo.

^ 2. Single-channel na QS na may walang limitasyong queue, ang pinakasimpleng daloy ng mga kahilingan at isang arbitrary na pamamahagi ng oras ng serbisyo. Kung ang isang single-channel na QS na may walang limitasyong queue ay nakakatanggap ng pinakasimpleng daloy ng mga kahilingan na may intensity λ , at ang oras ng serbisyo ay may arbitrary na pamamahagi na may inaasahan sa matematika t rev = 1/μ. at koepisyent ng pagkakaiba-iba vμ , kung gayon ang average na bilang ng mga kahilingan sa queue ay katumbas ng

at ang average na bilang ng mga application sa system

(21.2)

Kung saan, tulad ng dati, ρ = λ/μ ., a v μ - ang ratio ng karaniwang paglihis ng oras ng serbisyo sa inaasahan nitong matematika. Ang mga formula (21.1), (21.2) ay tinatawag na mga pormula ng Polyachek-Khinchin.

Delya L oh, at L syst sa λ, nakukuha namin, ayon sa Little formula, ang average na oras ng paninirahan ng application sa queue at ang average na oras ng paninirahan sa system:

(21.3)

(21.4)

Tandaan na sa espesyal na kaso kapag ang oras ng serbisyo ay exponential, v Ang μ = 1 at ang mga formula (21.1), (21.2) ay nagiging mga formula (20.16), (20.20) na pamilyar na sa amin para sa pinakasimpleng one-channel na QS. Kumuha tayo ng isa pang espesyal na kaso - kapag ang oras ng serbisyo ay hindi random at vμ = 0. Pagkatapos ang average na bilang ng mga kahilingan sa pila ay hinahati kumpara sa pinakasimpleng kaso. Ito ay natural: kung ang serbisyo ng aplikasyon ay magpapatuloy sa isang mas organisado, "regular" na paraan, kung gayon ang QS ay gumagana nang mas mahusay kaysa sa hindi maayos, hindi maayos na serbisyo.

^ 3. Single-channel na QS na may arbitrary na daloy ng mga kahilingan at arbitrary na pamamahagi ng oras ng serbisyo. Isinasaalang-alang namin ang isang single-channel na QS na may walang limitasyong queue, na tumatanggap ng arbitrary na paulit-ulit na daloy ng mga kahilingan na may intensity λ at koepisyent ng variation v Mga agwat ng λ sa pagitan ng mga kahilingan, natapos sa pagitan ng zero at isa: 0< v λ < 1. Oras ng serbisyo T o mayroon ding arbitrary distribution na may mean t vol = 1/μ at koepisyent ng variation v μ , nakapaloob din sa pagitan ng zero at isa. Para sa kasong ito, hindi makukuha ang eksaktong analytical formula;

maaari lamang tantiyahin ng isa ang average na haba ng pila, limitahan ito mula sa itaas at ibaba.

Ito ay napatunayan na sa kasong ito

Kung ang papasok na stream ay ang pinakasimpleng, pagkatapos ay ang parehong mga pagtatantya - ang itaas at mas mababang mga - nag-tutugma, at ang Polyachek-Khinchin formula (21.1) ay nakuha. Para sa tinatayang tinatayang pagtatantya ng average na haba ng pila, nakuha ni M. A. Fainberg (tingnan) ang isang napakasimpleng formula:

(21.6)

Ang average na bilang ng mga application sa system ay nakuha mula sa L och sa pamamagitan lamang ng pagdaragdag ng ρ - ang average na bilang ng mga serbisyong kahilingan:

L syst = L och + ρ. (21.7)

Tulad ng para sa average na oras ng paninirahan ng isang aplikasyon sa pila at sa system, kinakalkula ang mga ito gamit L och at L syst sa pamamagitan ng pormula ni Little sa pamamagitan ng paghahati sa λ .

Kaya, ang mga katangian ng single-channel na QS na may walang limitasyong queue ay maaaring matagpuan (kung hindi eksakto, pagkatapos ay humigit-kumulang) kahit na sa mga kaso kung saan ang mga daloy ng mga kahilingan at serbisyo ay hindi ang pinakasimpleng.

Isang natural na tanong ang lumitaw: paano ang multichannel na hindi Markov QS? Sa buong katapatan, sasagutin natin: masama. Ang mga eksaktong analytical na pamamaraan para sa mga naturang sistema ay hindi umiiral. Ang tanging bagay na palagi naming mahahanap ay ang average na bilang ng mga abalang channel k =ρ. Tungkol sa L och, L syst, W och, W syst, imposibleng magsulat ng mga pangkalahatang formula para sa kanila.

Totoo, kung mayroon talagang maraming mga channel (4-5 o higit pa), kung gayon ang oras ng serbisyo na nagpapahiwatig ay hindi nakakatakot: ang input stream ang magiging pinakasimpleng. Sa katunayan, ang kabuuang daloy ng mga "release" ng mga channel ay binubuo ng mga daloy ng mga release ng mga indibidwal na channel, at bilang resulta ng naturang overlay ("superposition"), tulad ng alam natin, ang isang daloy na malapit sa pinakasimpleng ay nakuha. Kaya sa kasong ito, ang pagpapalit ng hindi exponential service time distribution ng exponential one ay humahantong sa medyo maliliit na error. Sa kabutihang palad, ang daloy ng input ng mga application sa maraming praktikal na problema ay malapit sa pinakasimpleng.

Mas malala ang sitwasyon kapag ang input stream ay malinaw na hindi ang pinakasimpleng isa. Well, sa kasong ito, kailangan mong magpakasawa sa mga trick. Halimbawa, pumili ng dalawang single-channel na QS, na ang isa ay malinaw na "mas mahusay" sa kahusayan nito kaysa sa isang multi-channel na ito, at ang isa ay halatang "mas masahol pa" (mas mahaba ang pila, mas matagal ang oras ng paghihintay). At para sa isang solong channel na QS, kahit papaano ay alam na namin kung paano hanapin ang mga katangian sa anumang kaso.

Paano pumili ng naturang single-channel QS - "pinakamahusay" at "pinakamasama"? Ito ay maaaring gawin sa iba't ibang paraan. Lumalabas na ang malinaw na pinakamasamang variant ay maaaring makuha sa pamamagitan ng paghiwa-hiwalay ng ibinigay n-naka-on ang channel QS P single-channel, at ipamahagi ang kabuuang pinakasimpleng daloy na dumarating sa kanila sa pagitan ng mga single-channel na QS na ito sa pagkakasunud-sunod ng priyoridad: ang unang kahilingan - sa unang QS, ang pangalawa - sa pangalawa, atbp. Alam namin na sa kasong ito, bawat QS ay makakatanggap ng isang Erlang flow n ika-utos, na may koepisyent ng variation na katumbas ng 1/ . Tulad ng para sa koepisyent ng pagkakaiba-iba ng oras ng serbisyo, nananatili itong pareho. Para sa isang solong channel na QS, alam na namin kung paano kalkulahin ang oras ng paninirahan ng isang aplikasyon sa system W syst; ito ay tiyak na mas malaki kaysa sa orihinal n-channel QS. Alam ang oras na ito, posibleng magbigay ng "pessimistic" na pagtatantya para sa average na bilang ng mga application sa queue, gamit ang Little formula at multiply ang average na oras sa intensity λ ng kabuuang daloy ng mga application. Ang isang "optimistic" na pagtatantya ay maaaring makuha sa pamamagitan ng pagpapalit n-channel QS ng isang solong channel, ngunit may rate ng daloy ng serbisyo na n beses na mas malaki kaysa sa isang ibinigay, katumbas ng nμ. Naturally, sa kasong ito, ang parameter ρ ay dapat ding baguhin, bawasan sa n minsan. Para sa naturang QS, ang oras ng paninirahan ng isang aplikasyon sa system W syst ay nabawasan dahil sa ang katunayan na ang serbisyo ay nagpapatuloy sa n beses na mas kaunting oras. Gamit ang binagong halaga , ang koepisyent ng variation ng papasok na daloy vλ at oras ng serbisyo v μ , maaari nating kalkulahin ang average na bilang ng mga aplikasyon sa system. Ibinabawas mula dito ang orihinal (hindi nabago) na halaga ρ, nakukuha namin ang average na bilang ng mga application sa queue . Ang parehong mga katangian ay magiging mas mababa kaysa sa orihinal n-channel QS (magiging "optimistic" na mga pagtatantya). Mula sa kanila, hinahati sa pamamagitan ng λ , ang isa ay maaaring pumasa sa "optimistic" na mga pagtatantya para sa oras na ginugol sa QS at sa pila.

2.2 Multi-channel latency QS

Ang mga estado ng system ay binibilang ayon sa bilang ng mga kahilingan na konektado ng system:

walang pila:

Lahat ng channel ay libre;

Ang isang channel ay abala, ang iba ay libre;

Busy -channels, ang iba ay hindi;

Ang lahat ng mga channel ay inookupahan, walang mga libre;

may pila:

Lahat ng n-channel ay inookupahan; isang application ang nasa pila;

Lahat ng n-channel ay inookupahan, r-requests sa pila;

Ang lahat ng mga n-channel ay okupado, ang mga r-order ay nasa pila.

Ang GSP ay ipinapakita sa fig. 17. Ang bawat arrow ay may katumbas na intensity ng mga stream ng kaganapan. Ayon sa mga arrow mula kaliwa hanggang kanan, ang system ay palaging inililipat sa pamamagitan ng parehong daloy ng mga kahilingan na may intensity , ayon sa mga arrow mula sa kanan papuntang kaliwa, ang system ay inililipat ng isang daloy ng serbisyo, ang intensity nito ay katumbas ng, pinarami sa dami ng abalang channel.

kanin. 17. Multichannel QS na may paghihintay

Ang graph ay tipikal para sa mga proseso ng pagpaparami at kamatayan, kung saan ang solusyon ay nakuha dati. Sumulat tayo ng mga expression para sa paglilimita ng mga probabilidad ng mga estado gamit ang notasyon : (dito ginagamit natin ang expression para sa kabuuan ng isang geometric na pag-unlad na may denominator ).

Kaya, ang lahat ng mga probabilidad ng estado ay matatagpuan.

Tukuyin natin ang mga katangian ng kahusayan ng system.

Probabilidad ng pagkabigo. Ang isang papasok na kahilingan ay tatanggihan kung ang lahat ng n-channel at lahat ng m-lugar sa pila ay inookupahan:

(18)

Ang kamag-anak na throughput ay umaakma sa posibilidad ng pagkabigo sa isa:

Ganap na throughput ng QS:

(19)

Average na bilang ng mga abalang channel. Para sa mga CMO na may mga pagkabigo, ito ay kasabay ng average na bilang ng mga aplikasyon sa system. Para sa QS na may pila, ang average na bilang ng mga abalang channel ay hindi tumutugma sa average na bilang ng mga kahilingan sa system: ang huling halaga ay naiiba sa una sa average na bilang ng mga kahilingan sa queue.

Tukuyin natin ang average na bilang ng mga abalang channel . Ang bawat abalang channel ay nagsisilbi sa average - mga kahilingan sa bawat yunit ng oras, at ang QS sa kabuuan ay nagsisilbi sa average na A - mga kahilingan sa bawat yunit ng oras. Ang paghahati sa isa't isa, nakukuha natin:

Ang average na bilang ng mga kahilingan sa queue ay maaaring direktang kalkulahin bilang ang mathematical na inaasahan ng isang discrete random variable:

(20)

Dito muli (expression sa mga bracket) ang derivative ng kabuuan ng isang geometric progression ay nangyayari (tingnan sa itaas (11), (12) - (14)), gamit ang ratio para dito, nakukuha natin:

Average na bilang ng mga application sa system:

Average na oras ng paghihintay para sa isang aplikasyon sa pila. Isaalang-alang natin ang ilang sitwasyon na naiiba sa estado kung saan mahahanap ng bagong dating na kahilingan ang system at kung gaano ito katagal maghihintay para sa serbisyo.

Kung hindi makita ng entity na abala ang lahat ng channel, hindi na ito kailangang maghintay (ang mga kaukulang termino sa inaasahan sa matematika ay katumbas ng zero). Kung ang kahilingan ay dumating sa sandaling ang lahat ng n-channel ay inookupahan, at walang pila, ito ay kailangang maghintay sa average para sa isang oras na katumbas ng (dahil ang "paglabas ng daloy" ng -channel ay may intensity ). Kung nakita ng customer na abala ang lahat ng channel at isang customer ang nasa harap niya sa pila, kailangan niyang maghintay sa average para sa isang yugto ng panahon (para sa bawat nauuna na customer), atbp. Kung nakahanap ang customer - mga customer sa pila, siya ay kailangang maghintay sa karaniwan para sa oras. Kung ang isang bagong dating na customer ay nakahanap na ng m-customer sa pila, hindi na ito maghihintay (ngunit hindi rin ihahatid). Nahanap namin ang average na oras ng paghihintay sa pamamagitan ng pagpaparami ng bawat isa sa mga halagang ito sa mga katumbas na probabilidad:

(21)

Tulad ng kaso ng isang solong channel na QS na may paghihintay, napapansin namin na ang expression na ito ay naiiba sa expression para sa average na haba ng queue (20) sa pamamagitan lamang ng factor , i.e.

Mga system na may walang limitasyong haba ng pila. Isinaalang-alang namin ang isang channel QS na may paghihintay, kapag hindi hihigit sa m-customer ang maaaring nasa pila nang sabay.

Tulad ng dati, kapag sinusuri ang mga sistema nang walang mga paghihigpit, kinakailangang isaalang-alang ang mga nakuhang relasyon para sa .

Nakukuha namin ang mga probabilidad ng mga estado mula sa mga formula sa pamamagitan ng pagpasa sa limitasyon (sa ). Tandaan na ang kabuuan ng kaukulang geometric na pag-unlad ay nagtatagpo sa at diverges sa >1. Ipagpalagay na<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Ang posibilidad ng pagkabigo, kamag-anak at ganap na throughput. Dahil ang bawat kahilingan ay ihahatid nang maaga o huli, ang mga katangian ng QS throughput ay magiging:

Ang average na bilang ng mga kahilingan sa queue ay nakuha mula sa (20):

at ang average na oras ng paghihintay ay mula sa (21):

Ang average na bilang ng mga abalang channel, tulad ng dati, ay tinutukoy sa mga tuntunin ng ganap na throughput:

Halimbawa 2. Ang isang gasolinahan na may dalawang dispenser (n = 2) ay nagsisilbi sa daloy ng mga sasakyan na may rate na =0.8 (mga kotse kada minuto). Average na oras ng serbisyo bawat makina:

Walang ibang gasolinahan sa lugar, kaya ang pila ng mga sasakyan sa harap ng gasolinahan ay maaaring lumaki nang halos walang katiyakan. Hanapin ang mga katangian ng QS.

Dahil ang<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

atbp.

Nahanap namin ang average na bilang ng mga inookupahang channel sa pamamagitan ng paghahati sa absolute throughput ng QS A==0.8 sa intensity ng serbisyo=0.5:

Ang posibilidad na walang pila sa gasolinahan ay:

Average na bilang ng mga sasakyan sa pila:

Average na bilang ng mga sasakyan sa mga filling station:

Average na oras ng paghihintay sa pila:

Karaniwang oras na nananatili ang isang kotse sa isang gasolinahan:

CMO na may limitadong oras ng paghihintay. Noong nakaraan, isinasaalang-alang namin ang mga system na limitado lamang ang paghihintay sa haba ng pila (ang bilang ng m-customer nang sabay-sabay sa pila). Sa naturang QS, ang isang claim na naging isang pila ay hindi umaalis dito hanggang sa ito ay naghihintay para sa serbisyo. Sa pagsasagawa, mayroong QS ng isa pang uri, kung saan ang aplikasyon, pagkatapos maghintay ng ilang oras, ay maaaring umalis sa pila (ang tinatawag na "impatient" na mga aplikasyon).

Isaalang-alang ang isang QS ng ganitong uri, sa pag-aakalang ang hadlang sa oras ng paghihintay ay isang random na variable.

Ipagpalagay natin na mayroong n-channel waiting QS kung saan ang bilang ng mga lugar sa queue ay hindi limitado, ngunit ang oras na ginugol sa queue ng isang customer ay ilang random na variable na may average na halaga, upang ang bawat customer sa ang queue ay napapailalim sa isang uri ng Poisson na "care flow" na may intensity:

walang pila:

Lahat ng channel ay libre;

Ang isang channel ay abala;

Dalawang channel ang abala;

Lahat ng n-channel ay inookupahan;

may pila:

Ang lahat ng mga n-channel ay inookupahan, isang aplikasyon ang nasa pila;

Ang lahat ng mga n-channel ay abala, ang mga r-hiling ay nasa pila, atbp.

Ang graph ng mga estado at mga transition ng system ay ipinapakita sa fig. 23.

kanin. 23. QS na may limitadong oras ng paghihintay

Lagyan natin ng label ang graph na ito tulad ng dati; lahat ng mga arrow na humahantong mula kaliwa hanggang kanan ay magkakaroon ng intensity ng daloy ng mga application. Para sa mga estadong walang pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay magkakaroon ng kabuuang intensity ng daloy ng serbisyo ng lahat ng abalang channel. Para sa mga estadong may pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay magkakaroon ng kabuuang intensity ng daloy ng serbisyo ng lahat ng n-channel at ang katumbas na intensity ng daloy ng mga pag-alis mula sa pila. Kung may mga r-order sa pila, ang kabuuang intensity ng daloy ng mga pag-alis ay magiging katumbas ng .

(24)

Tandaan natin ang ilang feature ng QS na may limitadong paghihintay kumpara sa dating itinuturing na QS na may mga kahilingang "pasyente".

Kung ang haba ng pila ay hindi limitado at ang mga customer ay "pasyente" (huwag umalis sa pila), kung gayon ang nakatigil na limit mode ay umiiral lamang sa kaso (para sa , ang kaukulang walang katapusang geometric na pag-unlad ay nag-iiba, na pisikal na tumutugma sa walang limitasyong paglago ng ang pila para sa ).

Sa kabaligtaran, sa isang QS na may "impatient" na mga customer na umaalis sa pila nang maaga, ang steady-state na mode ng serbisyo ay palaging nakakamit, anuman ang pinababang intensity ng daloy ng customer . Ito ay sumusunod sa katotohanan na ang serye para sa denominator ng formula (24) ay nagtatagpo para sa anumang positibong halaga ng at .

Para sa bawat isa sa mga kahilingang ito, mayroong "flux of exit" na may intensity na . Nangangahulugan ito na mula sa average na bilang ng -mga kahilingan sa pila, sa karaniwan, -ang mga kahilingan ay aalis nang hindi naghihintay ng serbisyo, -mga kahilingan sa bawat yunit ng oras at tanging -mga kahilingan ang maseserbisyuhan sa average bawat yunit ng oras. Ang relatibong throughput ng QS ay magiging:

Ang average na bilang ng mga abalang channel ay nakukuha pa rin sa pamamagitan ng paghahati sa absolute throughput A sa:

(26)

Ang average na bilang ng mga application sa queue. Ang Relation (26) ay nagbibigay-daan sa amin na kalkulahin ang average na bilang ng mga kahilingan sa queue nang hindi nagsusuma ng walang katapusang serye (25). Mula sa (26) nakukuha natin ang:

at ang average na bilang ng mga abalang channel na kasama sa formula na ito ay matatagpuan bilang ang matematikal na inaasahan ng isang random na variable Z, na kumukuha ng mga halaga 0, 1, 2,..., n na may probabilities ,:

Sa konklusyon, tandaan namin na kung sa mga formula (24) pumasa tayo sa limitasyon sa (o, na pareho, sa ), pagkatapos ay sa

Isang pila na may haba k, nananatili dito na may probability Pk at hindi sumasali sa queue na may probability gk=1 - Pk,". value (halimbawa, kapasidad ng bunker). Malinaw, ito ay isang espesyal na kaso ng pangkalahatang setting. Ang ilan ...

System na may limitadong haba ng pila. Isaalang-alang ang isang channel QS na may paghihintay, na tumatanggap ng daloy ng mga kahilingan na may intensity ; intensity ng serbisyo (para sa isang channel); ang dami ng upuan sa pila.

Ang mga estado ng system ay binibilang ayon sa bilang ng mga kahilingan na konektado ng system:

walang pila:

Lahat ng channel ay libre;

Ang isang channel ay abala, ang iba ay libre;

Mga abalang channel, ang iba ay hindi;

Ang lahat ng mga channel ay abala, walang mga libre;

may pila:

Lahat ng n channel ay inookupahan; isang application ang nasa pila;

Lahat ng n channel ay inookupahan, r kahilingan ay nasa pila;

Lahat ng n channel ay inookupahan, m mga application sa pila.

Ang GSP ay ipinapakita sa fig. 5.9. Ang bawat arrow ay may katumbas na intensity ng mga daloy ng kaganapan. Ayon sa mga arrow mula kaliwa hanggang kanan, ang system ay palaging inililipat sa pamamagitan ng parehong daloy ng mga kahilingan na may intensity , ayon sa mga arrow mula sa kanan papuntang kaliwa, ang system ay inililipat ng isang daloy ng serbisyo, ang intensity nito ay katumbas ng, pinarami sa dami ng abalang channel.

Multi-channel exponential CMO naiiba sa single-channel gaya ng mga sumusunod. Ang bilang ng mga channel sa loob nito ay higit sa isa. Ang isang papasok na kahilingan ay nakapila kung ang lahat ng mga channel ay abala. Kung hindi, ang kahilingan ay sumasakop sa isang libreng channel. (5.56)

Nagsusulat kami ng mga expression para sa paglilimita ng mga probabilidad ng mga estado gamit ang notasyon : (tingnan ang 5.45)

Probability ng Pagkabigo. Ang natanggap na aplikasyon ay tinanggihan kung ang lahat ay okupado n mga channel at lahat m mga lugar sa linya:

(5.57)

Ang kamag-anak na throughput ay umaakma sa posibilidad ng pagkabigo sa isa:

Ganap na throughput ng QS:

(5.58)

Karaniwang Mga Abala na Channel. Para sa CMO na may mga pagkabigo, ito ay kasabay ng average na bilang ng mga aplikasyon sa system. Para sa CMO na may pila, ang average na bilang ng mga abalang channel ay hindi tumutugma sa average na bilang ng mga kahilingan sa system: ang huling halaga ay naiiba sa una sa average na bilang ng mga kahilingan sa queue.

Tukuyin natin ang average na bilang ng mga abalang channel . Ang bawat abalang channel ay naghahatid ng mga kahilingan sa bawat yunit ng oras sa karaniwan, at CMO sa pangkalahatan ay nagsisilbi ng isang average PERO mga kahilingan sa bawat yunit ng oras. Ang paghahati sa isa't isa, nakukuha natin:

Ang average na bilang ng mga kahilingan sa queue ay maaaring direktang kalkulahin bilang ang mathematical na inaasahan ng isang discrete random variable:

(5.59)

Dito muli (expression sa mga bracket) ang derivative ng kabuuan ng isang geometric progression ay nangyayari (tingnan sa itaas (5.50), (5.51) - (5.53)), gamit ang ratio para dito, nakukuha natin:

Average na bilang ng mga application sa system:

Average na oras ng paghihintay para sa isang aplikasyon sa pila. Isaalang-alang natin ang ilang sitwasyon na naiiba sa estado kung saan mahahanap ng bagong dating na kahilingan ang system at kung gaano ito katagal maghihintay para sa serbisyo.

Kung hindi makita ng entity na abala ang lahat ng channel, hindi na ito kailangang maghintay (ang mga kaukulang termino sa inaasahan sa matematika ay katumbas ng zero). Kung ang aplikasyon ay dumating sa oras na ang lahat ay abala P channel, at walang pila, kakailanganin itong maghintay ng average na oras na katumbas ng (dahil ang "daloy ng mga paglabas" ng mga channel ay may intensity ). Kung nakita ng isang customer na abala ang lahat ng channel at isang customer ang nasa unahan nito sa pila, kakailanganin itong maghintay sa average para sa oras (para sa bawat customer sa harap), atbp. Kung makita ito ng customer sa pila ng mga customer, ito ay kailangang maghintay sa karaniwan para sa oras. Kung ang bagong dating na application ay nasa pila na m mga aplikasyon, pagkatapos ay hindi ito maghihintay sa lahat (ngunit hindi ihahatid).

Average na oras ng paghihintay hanapin sa pamamagitan ng pagpaparami ng bawat isa sa mga halagang ito sa kaukulang mga probabilidad:

(5.60)

Average na oras ng paninirahan ng isang aplikasyon sa system, kapareho ng para sa single-channel CMO, ay naiiba sa average na oras ng paghihintay sa average na oras ng serbisyo na na-multiply sa relative throughput:

Mga system na may walang limitasyong haba ng pila.

Isinaalang-alang namin ang isang channel QS na may paghihintay, kapag hindi hihigit sa m mga aplikasyon.

Tulad ng dati, kapag sinusuri ang mga sistema nang walang mga paghihigpit, kinakailangang isaalang-alang ang mga nakuhang relasyon para sa .

Nakukuha namin ang mga probabilidad ng mga estado mula sa mga formula (5.56) sa pamamagitan ng pagpasa sa limitasyon (sa ). Tandaan na ang kabuuan ng katumbas na geometric progression ay nagtatagpo para sa at diverges para sa > 1. Ipagpalagay na< 1 и устремив в формулах (5.56) величину m hanggang sa kawalang-hanggan, nakakakuha kami ng mga expression para sa paglilimita ng mga probabilidad ng mga estado:

(5.61)

Ang posibilidad ng pagkabigo, kamag-anak at ganap na throughput. Dahil ang bawat kahilingan ay ihahatid nang maaga o huli, ang mga katangian ng QS throughput ay magiging:

Ang average na bilang ng mga kahilingan sa queue ay nakuha mula sa (5.59):

at ang average na oras ng paghihintay - mula (5.60):

Ang average na bilang ng mga abalang channel, tulad ng dati, ay tinutukoy sa mga tuntunin ng ganap na throughput:

Ang komplikasyon ng mga istruktura at mga mode ng mga tunay na sistema ay nagpapahirap sa paggamit ng mga klasikal na pamamaraan ng teorya ng pagpila dahil sa pagtaas ng dimensyon ng mga gawaing nilulutas, na partikular na tipikal para sa mga system na may istraktura ng network. Ang isa sa mga posibleng paraan upang malampasan ang dimensyon ay ang paggamit ng mga modelo sa anyo ng mga queuing network (QNS).

Semo ay isang set ng isang may hangganan na bilang ng mga service node, kung saan ang mga kahilingan ay umiikot, na gumagalaw alinsunod sa routing matrix mula sa isang node patungo sa isa pa. Palaging bukas ang node CMO. Kasabay nito, indibidwal CMO CMO- ang istraktura ng system, at ang mga kinakailangan na nagpapalipat-lipat Semo, − mga bahagi ng mga daloy ng materyal (mga mensahe (packet) sa isang network ng komunikasyon, mga gawain sa mga multiprocessor system, mga lalagyan ng daloy ng kargamento, atbp.).

Sa turn nito, Semo ay ginagamit upang matukoy ang pinakamahalagang katangian ng system ng mga sistema ng impormasyon: pagiging produktibo; oras ng paghahatid ng pakete; mga posibilidad ng pagkawala ng mensahe at pagharang sa mga node; mga lugar ng pinahihintulutang halaga ng pag-load, kung saan ibinibigay ang kinakailangang kalidad ng serbisyo, atbp.

Sa teorya Semo pangunahing ay ang konsepto ng network estado. Ang pinakamahalagang katangian ng mga network MO− probabilidad ng kanilang mga estado. Upang matukoy ang mga probabilidad ng mga estado Semo pag-aralan ang random na proseso na nagaganap sa network. Habang dumadaloy ang mga modelo Semo Ang mga proseso ay karaniwang ginagamit din Markov at semi-Markov.

3.3. Sistema ng pagpila bilang isang modelo

1.5. Mga network ng pagpila

Ang proseso ng Markov na may tuluy-tuloy na oras ay naglalarawan sa pagpapatakbo ng exponential SEMO.

Tinatawag ang network exponential kung ang papasok na demand ay dumadaloy sa bawat isa CMO Poisson, at ang mga oras ng bawat yugto ng serbisyo na ipinatupad sa alinman CMO mga network, mayroon exponential pamamahagi. Ito ay nagpapahintulot sa amin na isaalang-alang na ang mga yugto ng serbisyo ay independiyente sa bawat isa at hindi nakadepende sa mga parameter ng papasok na stream, o sa estado ng network, o sa mga ruta ng mga kinakailangan.

Teorya ng exponentials Semo pinaka-binuo, at malawak itong ginagamit kapwa para sa pag-aaral ng mga PD network at para sa pag-aaral ng multiprocessor mga sistema ng kompyuter (CS). Ang mga praktikal na formula ay binuo para sa pagkalkula ng probabilistic-temporal na katangian (TTS) ng naturang mga network at system.

Ang mga pagtatangka na malalim na pag-aralan ang mga hindi-Markovian na modelo ng mga sistema ng network ay nahaharap sa mga makabuluhang paghihirap, na sanhi, sa partikular, ng kakulangan ng kalayaan ng tagal ng pananatili ng mga kinakailangan sa iba't ibang mga node ng mga modelo ng mga sistema ng network na may mga di-karaniwang disiplina. Kaya, halimbawa, sa ilalim ng isang medyo makatotohanang pagpapalagay na ang haba ng kinakailangan ay nananatiling pare-pareho sa panahon ng paghahatid nito sa pamamagitan ng mga node ng network, kinakailangan upang subaybayan ang landas ng bawat kinakailangan, na ginagawang imposibleng analytically kalkulahin ang katangian para sa isang network na may ang bilang ng mga node M> 2.

Ang pagsusuri ng mga gawa na nakatuon sa pag-aaral o pagkalkula ng mga modelong hindi Markovian ay nagpapakita na ang mga solusyon, bilang panuntunan, ay nakukuha ayon sa algoritmo sa pamamagitan ng mga kumplikadong kalkulasyon ng numero gamit ang mga pagbabagong Laplace-Stieltjes, ay ipinapatupad sa programmatically, napakahirap, o may malalaking pagkakamali sa pagtatasa ng pagganap ng mga sistema ng impormasyon (IS) sa lugar ng katamtaman at mataas na pagkarga. Samakatuwid, para sa pagmomodelo Semo, umuusbong mula sa klase ng mga multiplicative, gumamit ng mga tinatayang pamamaraan.

Comparative analysis ng tinatayang pamamaraan ng pagmomodelo Semo at ang mga halimbawang ibinigay sa ay nagpapakita na kinakailangang gumamit ng tinatayang mga pamamaraan para sa pagkalkula ng QMS nang may matinding pag-iingat, na kapag kinakalkula ang mga tiyak na QMS, sa proseso ng paglutas ng iba't ibang mga problema, tila kinakailangan na magsagawa ng pananaliksik upang masuri ang katumpakan at pagiging sensitibo. ng pamamaraang ginamit, pati na rin ang pagsasagawa ng isang eksperimento sa simulation na paunang QEM para sa isang sapat na malaking hanay ng mga halaga ng mga variable na parameter.

Ang mga analytical na pamamaraan para sa pagkalkula ng mga katangian ng mga IC ay batay, bilang panuntunan, sa pagsusuri ng mga exponential QMO. Kapag ginagamit ang mathematical apparatus na ito, posible na makakuha ng mga analytical na modelo para sa paglutas ng malawak na hanay ng mga problema sa pag-aaral ng mga system. Ang CEMO ay, una sa lahat, isang hanay ng mga magkakaugnay na sistema ng pagpila. Samakatuwid, kinakailangang alalahanin ang mga pangunahing tampok ng mga sistemang ito.

Network ng pila ay isang koleksyon ng isang may hangganang numero N paghahatid ng mga node, kung saan ang mga kahilingan ay nagpapalipat-lipat, na dumadaan alinsunod sa routing matrix mula sa isang node patungo sa isa pa. Ang isang node ay palaging isang bukas na QS (bukod dito, ang QS ay maaaring maging sa anumang klase). Kasabay nito, indibidwal CMO ipakita ang mga functionally independent na bahagi ng isang tunay na system, mga link sa pagitan CMO- ang istraktura ng system, at ang mga kinakailangan na nagpapalipat-lipat Semo,- mga bahagi ng mga daloy ng materyal (mga mensahe (packet) sa isang network ng komunikasyon, mga gawain sa mga multiprocessor system, mga lalagyan ng daloy ng kargamento, atbp.).

Para sa isang visual na presentasyon Semo ginagamit ang isang graph na ang mga vertex (node) ay tumutugma sa indibidwal CMO, at ang mga arko ay kumakatawan sa mga koneksyon sa pagitan ng mga node.

Ang paglipat ng mga aplikasyon sa pagitan ng mga node ay nangyayari kaagad alinsunod sa mga posibilidad ng paglipat , p ij- ang posibilidad na ang application pagkatapos ng serbisyo sa node i pumunta sa node j. Naturally, kung ang mga node ay hindi direktang konektado sa isa't isa, kung gayon p ij= 0. Kung mula sa ako- th node transition sa isa lang anumang node j, pagkatapos p ij= 1.

Semo inuri ayon sa ilang pamantayan (Larawan 4).

Tinatawag ang network linear, kung ang intensity ng mga daloy ng mga kahilingan sa mga node ay magkakaugnay ng isang linear na relasyon

l j= a ij l i,

saan a ij- koepisyent ng proporsyonalidad, o nauugnay sa pinagmulan

l j= a j l 0 ,.

Coefficient a j tinatawag na transfer coefficient, ito ay nagpapakilala sa proporsyon ng mga aplikasyon na natanggap sa j- th node mula sa pinagmulan ng mga kahilingan, o - ang average na bilang ng mga sipi ng kahilingan sa pamamagitan ng node na ito sa panahong nasa network ang kahilingan.

Kung ang intensity ng mga daloy ng mga kahilingan sa mga node ng network ay konektado sa pamamagitan ng isang non-linear na pag-asa (halimbawa, ), pagkatapos ay tinawag ang network hindi linear..

Ang network ay palaging linear kung ang mga kahilingan ay hindi mawawala at hindi dumami dito.

bukas na circuit Ang network ay tulad ng isang bukas na network kung saan ang mga kahilingan ay dumarating mula sa panlabas na kapaligiran at umalis sa network pagkatapos ng serbisyo sa panlabas na kapaligiran. Sa madaling salita, ang tampok na open-loop Semo(RSeMO) ay ang pagkakaroon ng isa o higit pang independiyenteng panlabas na pinagmumulan na bumubuo ng mga application na pumapasok sa network, gaano man karaming mga application ang nasa network. Sa anumang oras sa RSEMO maaaring mayroong arbitrary na bilang ng mga aplikasyon (mula 0 hanggang ¥).

kanin. 4. Pag-uuri ng mga network ng pila

AT saradong QSMO (ZSMO) isang nakapirming bilang ng mga application ang umiikot, at walang panlabas na independiyenteng mapagkukunan. Batay sa pisikal na pagsasaalang-alang, ZSEMО ang panlabas na arko ay pinili, kung saan ang pseudo-zero isang punto na may kaugnayan sa kung saan ang mga katangian ng oras ay maaaring masukat.

pinagsama-sama ang network ay isang network kung saan ang isang tiyak na bilang ng mga application ay patuloy na nagpapalipat-lipat at may mga application na nagmumula sa mga panlabas na independiyenteng mapagkukunan.

AT homogenous nagpapakalat ang mga network ng mga claim ng parehong klase. At kabaliktaran, sa magkakaiba Sa isang network, maaaring may mga claim ng ilang klase. Ang mga application ay nabibilang sa iba't ibang klase kung naiiba ang mga ito sa hindi bababa sa isa sa mga sumusunod na katangian:

Ang batas ng pamamahagi ng tagal ng serbisyo sa mga node;

Mga Priyoridad;

Mga Ruta (mga landas ng paggalaw ng mga application sa network).

AT exponential Ang mga network ng tagal ng serbisyo sa lahat ng mga node ay ipinamamahagi ayon sa isang exponential na batas, at ang mga daloy na pumapasok sa bukas na network ay ang pinakasimpleng (Poisson). Sa lahat ng iba pang mga kaso, ang network ay hindi exponential.

Kung hindi bababa sa isang node ang nagbibigay ng priyoridad na serbisyo, kung gayon ito ay - priority net. Ang priyoridad ay isang tampok na tumutukoy sa pagkakasunud-sunod ng serbisyo. Kung ang mga kahilingan ay sineserbisyuhan sa mga node sa pagkakasunud-sunod kung saan sila dumating, kung gayon ang naturang network hindi priority.

Kaya, tatawagin natin ang exponential Semo na nakakatugon sa mga kinakailangan:

Mga stream ng input Semo Poisson;

Sa lahat N SMO ang oras ng serbisyo ng mga kahilingan ay may exponential probability distribution function, at ang mga kahilingan ay sineserbisyuhan sa pagkakasunud-sunod ng pagdating;

Transition ng application mula sa exit i-th CMO sa input j Ang -th ay isang independiyenteng random na kaganapan na may posibilidad p ij ; p i0- ang posibilidad ng pag-alis ng aplikasyon sa CeMO.

Kung ang mga customer ay pumasok sa network at umalis dito, ang network ay tinatawag na bukas. Kung ang mga customer ay hindi pumasok sa network at hindi umalis dito, ang network ay tinatawag na sarado. Ang bilang ng mga kahilingan sa isang saradong network ay pare-pareho.