Tema : Maksimal aǵım máselesi

Tema : Maksimal aǵım máselesi

Joba :

1. Maksimal aǵım haqqındaǵı másele
2. Belgi qoyıw usılı
3. Ǵalabalıq xizmet kórsetiw máseleleri
4. Buyırtpalar aǵımı

Maksimal aǵım haqqındaǵı máseleni bayanlaymız. 0 punktten m punktke ılajı bolǵanınsha kóprok muǵdardaǵı júklerdi jıberiwden ibarat. Bunda biz 0 punktte júklerdiń shegaralanbaǵan rezervi ámeldegi hám ayqulaqlardıń júk ótkeriw qábileti joqarıdan shegaralanǵan dep shama menen oylaymız. Sonday etip, berilgen ótkeriw qábiletine iye bolǵan ayqulaqlardan paydalanıp, jıberiw punktinen qabıllaw punktine jónetiletuǵın maksimal aǵımdı (onı v menen belgileymiz) anıqlawımız kerek. Qoyılǵan máseleni tómendegi tor járdeminde bayanlaymız.

Buǵan uqsas tor ushın matematikalıq modeldi qurıw qıyın emes.
Onıń ushın tómendegilerden paydalanamız :
1) i punktten j punktke alıp barılatuǵın júk muǵdarı x_ij ózgeriwshiden ibarat ;
2) tor arqalı ótkerilgen júklerdiń ulıwma muǵdarı v den ibarat ;
3) (i, j) joldaǵı aǵımdıń joqarı shegarası b_ij den ibarat ;
4) aǵımdıń saqlanıwı haqqındaǵı boljaw atqarıladı ;
5) v aǵım hám x_ij ózgeriwshiler nomanfiy.
Nátiyjede tómendegi sızıqlı programmalastırıw máselesin payda etemiz:

shártlerden

Funkstiya maksimallashtirilsin.
Sistema daǵı 1-teńleme 0 punktke túsken v aǵım 0 punktten basqa (1, 2, 3) túyin punktlerge jo'natilayotgan jıyındı aǵımǵa teń bolıwın ańlatadı. 2-teńleme 1 punktten 2, 3, m punktlerge jo'natilayotgan júkler muǵdarlarınıń x_1, 2+x_13+x_1 m jıyındısı 1-punktke kiyatırǵan júk muǵdarı x_01 ge teńliginen, yaǵnıy x_12+x_13+x_1 m=x_01 teńlemeden kelip shıǵadı. Qalǵan teńlemeler de soǵan uqsas aytinadi. Sistema daǵı teńsizlikler (i, j) yoydagi x_ij aǵımdıń joqarı shegarası b_ij den ibaratlıgınan kelip shıǵadı. x_ij≥0 teńsizlik 5) atap aytqanda kelip shıǵadı.
Másele, shubhasız, sheshimge iye sebebi eger x_ij=0 hám v=0 bolsa, barlıq shekleniwler qánaatlanadı. Eger maksimal aǵım haqqındaǵı máseleni simpleks usıl menenyechish múmkin sonda da, buǵan uqsas máselelerdiń matematikalıq dúzilisi maqsetke tez hám ańsat jetkizetuǵın sheshiw usılların qóllawǵa múmkinshilik beredi. Bunday máselelerdiyechish ushın nátiyjeli usıllar tiykarlanatuǵın birpara maǵlıwmatlardı keltiremiz.
Kesim túsinigin kiritemiz. Kesim bul sonday jollar kompleksiki, onı tordan alıp taslansa, tor birinde jıberiw punkti, basqasında qabıl punkti bolǵan eki óz-ara baylanıspaǵan bólimlerge bóleklengen bolıp qaladı. Qandayda bir kesimge tiyisli bolǵan jollar anıq belgilengen ulıwma ótkeriw qábiletine iye boladı. 0 hám m punktlerdi ajıratıwshı kesimler arasında ótkeriw qábileti eń kishi bolǵan kesim minimal kesim dep ataladı.
Torlar teoriyasınıń tiykarǵı teoremasi (Maksimal aǵım hám minimal kesim haqqındaǵı Ford-Falkerson teoremasi) tómendeginen ibarat. Qálegen tor ushın 0 punktten m punktke bolǵan maksimal aǵım úlkenligi minimal kesimdiń ótkeriw qábiletine teń. Maksimal aǵım haqqındaǵı máseleni belgi qoyıw usılı menenyechish da múmkin. Bul usıl keyingi temada bayanlainadi.
Belgi qoyıw usılı
Tor birden-bir a_0 baslanǵısh uchga hám birden-bir a_m aqırǵı uchga iye bolsın. Hár bir (a_i, a_j) yoyga onıń a_i den a_j ga baǵdardaǵı ótkeriw qábileti dep atalıwshı nomanfiy b_ij san uyqas qoyılǵan bolsın. Bunda b_ij=b_jibo'lishi shárt emes. Torda a_0 den a_m ga aǵım dep, (a_i, a_j) ayqulaqlarǵa uyqas qoyılǵan sonday nomanfiy θ_ij sanlardıń {a_ij } kompleksine aytıladıki; olar ushın

Atqarılsa, , san aǵım úlkenligi dep ataladı.
Maksimal aǵım dúziw algoritmın bayanlaymız. Qandayda bir baslanǵısh, mısalı, nol aǵım alınadı. Ayqulaqlardıń baslanǵısh ótkeriw qábiletleri berilgen. Aytaylik algoritmdıń bir qansha qádeminen keyin qandayda bir θ_ij aǵım ayqulaqlardıń ótkeriw qábiletleriniń ámeldegi bahaları hám v aǵım úlkenliginiń qandayda bir ámeldegi ma`nisi alınǵan bolsın. Ol halda algoritm tómendegishe isleydi:
10 Oń q ótkeriw qábiletke iye a_0 den a_n ga jol saylanadı, buyerda q -joldı payda etiwshi ayqulaqlar ótkeriw qábiletleriniń eń kichigi. Onıń ushın tómendegi algoritmnan paydalanıw múmkin (a_0 úsh aldın basında belgilengen, lekin qorıb shıǵılmaǵan dep esaplanadı, qalǵan barlıq úshler bolsa belgilenmagan dep esaplanadı ):
1. a. Belgilengen, biraq kórip shıǵılmaǵan qálegen a_i úsh saylanadı.
1. b. b_ij>0 shárt atqarılatuǵın barlıq a_j úshlerge (i, j) belgiler quyıladı hám olardı belgilengen dep esaplanadı. a_i úsh kórip shıǵılǵan dep esaplanadı. Eger bunda a_n aqırǵı úsh belgilengen bolıp qalsa, ol halda belgiler boyınsha a_0 den a_n ge shekem ızlenip atırǵan joldı qayta tiklew ańsat. Keri jaǵdayda 1. a. qádemge ótiledi. Eger bunıń múmkinshiligi bolmasa, ol halda ızlenip atırǵan jol ámeldegi bolmaydı.
20. Aytaylik (a_0, a_ (i_1 )), (a_ (i_1 ), a_ (i_2 )), …, (a_ (i_ (m-1) ), a_ (i_m )), tabılǵan jol bolsın. Ol halda bul jolǵa kiretuǵın hár bir (a_ (i_ (k-1) ), a_ (i_k )) ayqulaq ushın
operatorlar atqarıladı. Keyin 10 qádemge ótiledi. Eger oń ótkeriw qábiletke iye bolǵan jol ámeldegi bolmasa, ol halda alınǵan aǵım maksimal boladı.
Ǵalabalıq xizmet kórsetiw máseleleri
Ǵalabalıq xizmet kórsetiw teoriyasında ǵalabalıq xizmet kórsetiw sistemalarındaǵı processlerdi itimallar teoriyası quralları menen uyreniledi. Ǵalabalıq xizmet kórsetiw teoriyasınıń tiykarǵı máselelerinen biri - ǵalabalıq xizmet kórsetiw sistemaları jumısın málim kórsetkishler boyınsha optimal shólkemlestiriw bolıp tabıladı.
Múmkinshiligıy modeller real dúnyadaǵı óz-ara baylanısıw hám munasábetlerdi eń úlken itimal menen ańlatıwǵa múmkinshilik beredi. Házirgi waqıtta ol yamasa bul extimoliy model hám usıllardan paydalanılmaytuǵın tarawdı kórsetiw qıyın. Bul model hám usıllar júdá keń tarqalǵan bolıp, kúnden-kunga jaqınlastırılgan hám real processlerdi joqarı dárejede anıq ańlatadı. Bunday modeller quramına kiretuǵın hár bir muǵdar bólistiriw nızamları jáne bul bólistiriw nızamlarınıń xarakteristikaları menen beriledi.
Itimallar teoriyası nátiyjelerinen paydalanıladı. Házirgi waqıtta itimallar teoriyası tiykarında bir neshe matematikalıq pánler rawajlanıp atır. Olardan biri ǵalabalıq xizmet kórsetiw teoriyası bolıp tabıladı. Ǵalabalıq xizmet kórsetiw teoriyası máselelerin tarqatıp alıwdıń tiykarǵı usıllarınan biri itimallar iazariyasi bolıp tabıladı.
Bul teoriya túrli xizmet kórsetiw shólkemleriniń jumısları menen baylanıslı processlerdi úyrenedi. Mısalı :
telefon stanstiyalari;
ta'mirlash ustaxonalari;
chipta kassaları ;
savdo noqatları ;
sartaroshxonalar;
aloqa jolları ;
tikuv ustaxonalari hám basqalar.
Hár bir bunday shólkemler aldınan belgisiz bolǵan waqıt momentlerinde túsetuǵın buyırtpalarǵa xizmet kórsetiw ushın mólsherlengen. Ǵalabalıq xizmet kórsetiw teoriyasında buyırtpalarǵa xızmet kórsetetuǵın shólkemler ǵalabalıq xizmet kórsetiw sistemaları dep ataladı. Ǵalabalıq xizmet kórsetiw sistemalarınıń ótkeriw qábileti tómendegilerge baylanıslı :
uning quramına kiretuǵın xızmet kórsetiwshi birlikler (kanallar ) sanı ;
har bir kanaldıń jumıs qábileti;
buyurtmalar aǵımınıń xarakteri;
Ǵalabalıq xizmet kórsetiw sistemasınıń absolyut ótkeriw qábileti dep waqtıniń bir birliginde xızmet kórsete alatuǵın buyırtpalardıń ortasha sanına aytıladı.
Salıstırmalı ótkeriw qábileti dep waqtıniń bir birliginde xızmet kórsetilgen buyırtpalar sanınıń waqtıniń bir birliginde berilgen buyırtpalar sanına ortasha qatnasın aytıladı.
Absolyut hám salıstırmalı ótkeriw qábileti sistemanıń rejiminegine baylanıslı bolıp qalmay, bálki buyırtpalar aǵımı xarakterine de baylanıslı. Eger buyırtpalar izbe-iz hár qalay regulyar kelseler, ol halda sistema olarǵa jaqsı xızmet kórsete aladı. Eger buyırtpalar aǵımı regulyar bolmasa hám jergilikli zichlanish hám siyreklikler payda etsalar, ol halda sistemanıń jumısı qıyınlasadı : waqtıniń birpara bóleklerinde xizmet etiw qurallarınıń biykar turıwları payda bolıp, basqa bóleklerinde sistemada jumıstıń artıp ketiwi payda boladı, bunda birpara buyırtpalar biykarlaw etiledi yamasa buyırtpalardıń úlken gezekleri jıynaladı.
Absolyut hám salıstırmalı ótkeriw qábiletlerinen tısqarı ǵalabalıq xizmet kórsetiw teoriyası sistemanıń taǵı basqa xarakteristikalarına itibar qaratadı, mısalı :
" rad" larning ortasha procenti;
buyurtmalar joq ekenligi sebepli sistemanıń " biykar turıwı" dıń ortasha salıstırmalı waqtı ;
navbatning ortasha uzınlıǵı ;
kutishning ortasha waqtı ;
vaqtning berilgen momentinde 0, 1, 2,... ta kanallar bánt bolıwı múmkinshiligı hám basqalar.
Ǵalabalıq xizmet kórsetiw teoriyasınıń máselesi bul xarakteristikalar, sistemanıń kanallar sanı, xizmet etiw tezligi hám buyırtpalar aǵımı kórinisi arasındaǵı baylanısıwdı úyreniwden ibarat.
Ǵalabalıq xizmet kórsetiw sistemalarınıń eki tiykarǵı túri uyreniledi:
1. Biykarlawlar menen (buyırtpadan bas tartatuǵın) sistemalar. Bunday sistemalarda hámme kanallar bandligi waqtında túsken buyırtpa biykarlaw etiledi hám keyin xızmet etińiw processinde qatnasıw etpeydi. Mısalı, telefon stanstiyalariga shaqiriq tosınarlı tártipte keledi. Eger bos liniya bolsa, abonentke sol ondayoq xızmet etiledi. Eger bos liniya bolmasa, sizdiń buyırtpańız " rad" aladı hám siz telefon awlaq jergini ornına qoyıwıńız múmkin. Telefon nomerin tákiraran terip, siz jańa buyırtpa berasiz.
2. Kútiletuǵın (gezekli) sistemalar. Bunday sistemalarda hámme kanallar bandligi waqtında túsken buyırtpa gezekke turadı hám kanallardan biri bosaguncha kutadi. Kanal bosagan zamati náwbette turıwshı buyırtpalardan biri xızmet orınlaw ushın alınadı.
Kútiletuǵın sistemada xizmet kórsetiw " tártiplengen" (buyırtpalar kelip túsiwi tártibinde) bolıwı múmkin hám " tártiplanmagan" (buyırtpalarǵa tosınarlı tártipte) bolıwı múmkin.
Náwbettegi kútiw waqtı shegaralanǵan hám shegaralanbaǵan hallar qaraladı.
Kútiletuǵın sistemada bizni abonenttiń ortasha kútiw waqtı hám gezektiń ortasha uzınlıǵı qızıqtiradi, buyırtpadan bas tartatuǵın sistemada buyırtpanı abonent biykarlaw etiw múmkinshiligı qızıqtiradi. Bul esaplawlar tiykarında telefon tarmaqlarınıń rastional parametrlerin anıqlaw múmkin, mısalı, xızmet etiwshi liniyaning rastional sanı (bunda kútiw waqtı da, liniyaning biykar jas waqtı da kem bolıwı kerek bolıp tabıladı).
Ǵalabalıq xizmet kórsetiw teoriyası járdeminde sawda kárxanasında satıwshılar hám kassirlarning rastional sanın anıqlaw múmkin. Artıqsha satıwshı hám kassirlarni magazinda xizmet etiwi qosımsha ǵárejet qılıwdı talap etedi, lekin qarıydarlardıń uzaq waqıt gezek kútiwdi hoxlamasdan, magazindan ketib qalıwı da sawda kárxanasına úlken zıyan keltiredi, sol sebepli satıwshı hám kassirlarning sanı hám de magazindagi gezek úlkenligi arasındaǵı munasábetti optimallastırıw mashqalası bar bolıp tabıladı.
Ǵalabalıq xizmet kórsetiw teoriyasında ádewir quramalı hallar da qaraladı, mısalı, xizmet etiw ásbaplarınıń isten shıǵıp qalıwı múmkinshiligı yamasa xizmet etiwde buyırtpalardıń zárúrligini esapqa alıw halları qaraladı. Bunda zárúrli buyırtpalar sistemalarǵa gezeksiz qabıl etiledi.
Ǵalabalıq xizmet kórsetiw teoriyası usılları járdeminde stanoklardıń biykar turıw waqtı hám xızmet etiwshi apparatlardı isletiw ǵárejetleri arasındaǵı munasábetlerdi optimallastırıw máseleleriyechiladi.
Ǵalabalıq xizmet kórsetiw teoriyası modelleri járdeminde toqımashılıq sanaatı daǵı, ásirese tútelerge sabaq oraw, iyiriw hám gezleme toqıw stexlaridagi processleryetarli dárejede anıq ańlatıladı.
Joqarıda sanap ótilgen xizmet kórsetiw sistemalarınıń hár birewiniń tabıslı islep atirǵanlıǵın bahalaw ushın tiykarlanıp eki kórsetkish xızmet etedi. Bul, birinshiden, jumıstıń sapası, yaǵnıy qanshellilik jaqsı xızmet kórsetilayotganligi, ekinshiden, xizmet kórsetiwdiń dúziliwi bolıp tabıladı.
Sistemanıń xizmet kórsetiw sapası jáne onıń ótkera alıw kuvvati barlıq jaǵdaylarda da xizmet kórsetiw birlikleri sanına hám olardıń ónimliligine baylanıslılıǵı ayqın bolıp tabıladı.
Biraq xızmet kórsetiwshi xızmetkerler (apparatlar ) sanın hádden tıs kópaytirib jiberiw kúsh hám aqshalardıń paydasız sarıplanıwı menen baylanıslı.
Usınıń menen birge keletuǵın talaplardıń sanı tosınarlı muǵdar bolıp, ámeldegi apparatlar sanı bolsa turaqlı bolıp tabıladı. Talaplar aǵımınıń ózgerip turıwı ádewir ulken bolıwı múmkin.
Talaplardıń atqarılıw waqtı da ózgermeytuǵın bolmaydıden bálki apparatlardıń ónimliligine de, talaptıń xarakterine de baylanıslı bolıp tabıladı, yaǵnıy ol tosınarlı muǵdar bolıp tabıladı.
Ǵalabalıq xizmet kórsetiw teoriyasınıń tiykarǵı máselesi xızmet kórsetiwshi birlikler sanı, ayırım xızmet kórsetiwshi birliktiń ónimliligi, kiyatırǵan talaplardıń xarakteri hám xizmet kórsetiw sapası arasındaǵı óz-ara baylanıslılıqtı ashıp beriwden ibarat.
waqtıniń tosınarlı momentlerinde júz beretuǵın buyırtpalardı qaraymız.
Buyırtpalar aǵımı dep, waqtıniń tosınarlı momentlerinde júz beretuǵın buyırtpalar izbe-izligin aytıladı.
Aǵımlarǵa tán bolǵan qásiyetler ishinde stastionarlik, sońǵı tásirdiń joq ekenligi hám ordinarlik ózgeshelikler bar.
Stastionarlik ózgesheligi qálegen waqıt aralıǵinda k ta hádiyse júz beriw múmkinshiligı k ga hám waqıt aralıǵınıń uzınlıǵı t ga baylanıslı bolıp, onıń sanaq basına baylanıslı bolmawi menen xarakterlenedi. Bunda túrli waqıt aralıqları kesilispeydi dep shama menen oylainadi. Mısalı, k ta hádiysediń dawam etiw waqti t waqıt birligine teń bolǵan (0, t) hám (T, T+t) waqıt aralıqlarında júz beriw itimalları óz-ara teń bolıp tabıladı.
Aǵım stastionarlik ózgesheligine iye bolsa, ol halda dawam etiw waqti t ga teń bolǵan waqıt aralıǵinda k ta hádiysediń júz beriw múmkinshiligı k hám t dıń funkstiyasi boladı.
" Keyin tásirdiń joq ekenligi" ózgesheligi qálegen waqıt aralıǵinda k ta hádiysediń júz beriw múmkinshiligı ko'rilayotgan aralıq baslanıwınan aldınǵı waqıt momentlerinde hádiyseler júz bergenliginde yamasa júz bermegenligine baylanıslı emesligi menen xarakterlenedi.
Aǵım keyin tásirdiń joq ekenligi ózgesheligine iye bolsa, ol halda óz-ara kesilispeytuǵın waqıt aralıqlarında bir yamasa bir neshe hádiyselerdiń júz beriwi óz-ara baylanıslı bolmaydı.
Ordinarlik ózgesheligi kishi waqıt aralıǵinda eki hám odan kóp hádiyselerdiń júz beriwi ámelde múmkin emesligi menen xarakterlenedi. Basqasha etip aytqanda, kishi waqıt aralıǵinda birden artıq hádiysediń júz beriw múmkinshiligı bir hádiysediń júz beriw múmkinshiligına qaraǵanda itibarǵa almasa xam bolatuǵın dárejede kishi.
Aǵım ordinarlik ózgesheligine iye bolsa, ol halda sheksiz kishi waqıt aralıǵinda kópi menen bir hádiyse júz beriwi múmkin. Eń ápiwayı aǵım (Puasson aǵımı ) dep, stastionarlik, keyin tásirdiń joq ekenligi hám ordinarlik hossalariga iye bolǵan aǵımdı aytıladı.
Ámeliyatda kóbinese aǵım joqarıda aytıp ótilgen hossalarga iye yamasa iye emesligin anıqlaw qıyın. Sol sebepli basqa hartlar da tabılǵanki, olar orınlanǵanda aǵımdı eń ápiwayı yamasa eń ápiwayı aǵımǵa jaqın, dep alıw múmkin. Atap aytqanda, eger aǵım kóp sandaǵı óz-ara baylanıslı bolmaǵan stastionar aǵımlardıń jıyındısı bolıp, olardıń hár birewiniń jıyındına (jıynalǵan aǵımǵa ) tásiri esapqa almasa da bolatuǵın dárejede kishi bolsa, ol halda jıynalǵan aǵım (onıń ordinarligi shártida) eń ápiwayı aǵımǵa júdá jaqın.
Buyırtpalar aǵımı
Buyırtpalardıń Puasson aǵımında kirisiw aǵımınıń ózgermeytuǵın γ intensivligi (waqıt birligi ishinde túsetuǵın buyırtpalardıń ortasha sanı ) málim bolsa, ol halda t waqıt dawamında k ta buyırtpa túsiw múmkinshiligı :

Formulası menen anıqlanadı
Tómendegi tiykarǵı xarakteristikalarni tabıw talap etilgen bolsın.
Lcèño' -sistema daǵı buyırtpalar ortasha sanı,
Wñèño'-buyırtpanıń sistemada turıwınıń ortasha waqtı,
Lí àâá-náwbettegi buyırtpalar ortasha sanı, yaoni gezektiń ortasha uzınlıǵı,
Wí àâá-buyırtpanıń náwbette turıw ortasha waqtı,
Páàí ä-kanaldıń bandligi múmkinshiligı,
Pá¢ø-kanaldıń bos turıwı múmkinshiligı.
ρ=γ/μbelgilash kiritemiz. ρ1 dep shama menen oylaymız. Bul halda


formulalar orınlı.