Марковын процессыг ямар график тодорхойлдог вэ? Марковын санамсаргүй үйл явц

Дарааллын онол бол магадлалын онолын нэг салбар юм. Энэ онол авч үздэг магадлалдаалгавар ба математик загварууд(үүнээс өмнө бид детерминист математик загваруудыг авч үзсэн). Үүнийг сануулъя:

Детерминист математик загваробъектын (систем, үйл явц) зан төлөвийг хэтийн төлөвөөс харуулдаг бүрэн итгэлтэйодоо ба ирээдүйд.

Магадлалын математик загваробъектын (систем, үйл явц) зан төлөвт санамсаргүй хүчин зүйлийн нөлөөллийг харгалзан үздэг тул тодорхой үйл явдлын магадлалын үүднээс ирээдүйг үнэлдэг.

Тэдгээр. Энд жишээ нь тоглоомын онолын асуудлуудыг авч үздэг нөхцөлдтодорхойгүй байдал.

Асуудалд орсон тодорхойгүй хүчин зүйлүүд нь санамсаргүй хэмжигдэхүүнүүд (эсвэл санамсаргүй функцууд) байх үед эхлээд "стохастик тодорхойгүй байдал" -ыг тодорхойлдог зарим ойлголтыг авч үзье. магадлалын шинж чанаруудмэдэгдэж байгаа эсвэл туршлагаас олж авч болно. Ийм тодорхой бус байдлыг "тааштай", "хортой" гэж нэрлэдэг.

Санамсаргүй үйл явцын тухай ойлголт

Хатуухан хэлэхэд санамсаргүй эвдрэл нь аливаа үйл явцын онцлог шинж чанартай байдаг. Санамсаргүй үйл явцын жишээг өгөх нь "санамсаргүй" үйл явцаас илүү хялбар байдаг. Жишээлбэл, цаг ажиллуулах үйл явц (энэ нь нарийн тохируулагдсан ажил юм шиг санагддаг - "цаг шиг ажилладаг") санамсаргүй өөрчлөлтөд (урагшлах, хоцрох, зогсох) хамаарна. Гэхдээ эдгээр эвдрэлүүд нь ач холбогдолгүй бөгөөд бидний сонирхож буй параметрүүдэд бага нөлөө үзүүлдэг бол бид тэдгээрийг үл тоомсорлож, үйл явцыг детерминист, санамсаргүй гэж үзэж болно.

Ямар нэг системтэй байя С(техникийн төхөөрөмж, ийм төхөөрөмжүүдийн бүлэг, технологийн систем - машин, талбай, цех, аж ахуйн нэгж, үйлдвэр гэх мэт). Системд Сгоожиж байна санамсаргүй үйл явц, хэрэв энэ нь цаг хугацааны явцад төлөвөө өөрчилдөг бол (нэг төлөвөөс нөгөөд шилжих), үүнээс гадна урьд өмнө мэдэгдээгүй санамсаргүй байдлаар.

Жишээ нь: 1. Систем С– технологийн систем (машины хэсэг). Машинууд үе үе эвдэрч, засвар үйлчилгээ хийдэг. Энэ системд болж буй үйл явц нь санамсаргүй байдлаар явагддаг.

2. Систем С- тодорхой маршрутын дагуу өгөгдсөн өндөрт нисч буй нисэх онгоц. Сэтгэл түгшсэн хүчин зүйлүүд - цаг агаарын нөхцөл байдал, багийн алдаа гэх мэт, үр дагавар - овойлт, нислэгийн хуваарийг зөрчсөн гэх мэт.

Марковын санамсаргүй үйл явц

Системд тохиолдох санамсаргүй үйл явцыг гэж нэрлэдэг Марковский, хэрэв ямар нэгэн мөчид т 0 ирээдүйн үйл явцын магадлалын шинж чанар нь зөвхөн тухайн үеийн төлөв байдлаас хамаарна т 0 бөгөөд систем хэзээ, хэрхэн ийм байдалд хүрсэнээс хамаарахгүй.

t 0 үед систем тодорхой төлөвт байг С 0 . Өнөөгийн системийн төлөв байдлын шинж чанарууд, хэзээ болсон бүх зүйлийг бид мэднэ т<т 0 (процессын түүх). Бид ирээдүйг урьдчилан таамаглаж чадах уу, өөрөөр хэлбэл. хэзээ юу болох бол т>т 0 ? Яг тийм биш, гэхдээ үйл явцын зарим магадлалын шинж чанаруудыг ирээдүйд олж болно. Жишээлбэл, хэсэг хугацааны дараа системд орох магадлал Счадах болно С 1 эсвэл төлөвт үлдэнэ С 0 гэх мэт.

Жишээ. Систем С- оролцож буй нисэх онгоцны бүлэг агаарын тулаан. Болъё x- "улаан" онгоцны тоо; y- "цэнхэр" онгоцны тоо. Тэр үед т 0 амьд үлдсэн (сөнөөгдөөгүй) агаарын хөлгийн тоо - x 0 ,y 0 . Одоогийн байдлаар тооны давуу тал "улаануудын" талд байх магадлалыг бид сонирхож байна. Энэ магадлал нь тухайн үед систем ямар төлөвт байснаас хамаарна т 0 бөгөөд буудсан хүмүүс яг хэзээ, ямар дарааллаар нас барсан тухай биш т 0 онгоц.

Практикт Марковын процессыг цэвэр хэлбэрээр нь ихэвчлэн хийдэггүй. Гэхдээ "түүхийн өмнөх үеийн" нөлөөг үл тоомсорлож болох үйл явц байдаг. Ийм үйл явцыг судлахдаа Марковын загварыг ашиглаж болно (онолын хувьд дараалалМарковын дарааллын системийг авч үзэхгүй, харин тэдгээрийг дүрсэлсэн математикийн аппарат нь илүү төвөгтэй байдаг).

Үйл ажиллагааны судалгаанд их үнэ цэнэДискрет төлөв, тасралтгүй хугацаатай Марковын санамсаргүй процессуудтай.

Процесс гэж нэрлэдэг дискрет төлөвийн процесс, хэрэв тийм бол боломжит мужуудС 1 ,С 2, ...-ийг урьдчилан тодорхойлж болох бөгөөд системийн төлөвөөс төлөв рүү шилжих нь "үсрэлтээр" бараг тэр даруй тохиолддог.

Процесс гэж нэрлэдэг -тай процесс тасралтгүй хугацаа , хэрэв төлөвөөс төлөв рүү шилжих боломжит мөчүүд нь урьдчилан тогтоогдоогүй боловч тодорхойгүй, санамсаргүй бөгөөд ямар ч үед тохиолдож болно.

Жишээ. Технологийн систем (хэсэг) СЭнэ нь хоёр машинаас бүрдэх бөгөөд тус бүр нь санамсаргүй агшинд бүтэлгүйтэх (амжилтгүй болох) бөгөөд үүний дараа нэгжийн засвар нэн даруй эхлэх бөгөөд энэ нь мөн үл мэдэгдэх, санамсаргүй хугацаанд үргэлжилдэг. Дараахь системийн төлөвүүд боломжтой:

С 0 - хоёр машин ажиллаж байна;

С 1 - эхний машиныг засварлаж, хоёр дахь нь ажиллаж байна;

С 2 - хоёр дахь машиныг засварлаж байна, эхнийх нь ажиллаж байна;

С 3 - хоёр машиныг засварлаж байна.

Системийн шилжилтүүд СТухайн машин эвдрэх эсвэл засвар дуусмагц санамсаргүй тохиолдлын үед мужаас муж руу шилжих нь бараг агшин зуур тохиолддог.

Шинжилгээ хийх үед санамсаргүй үйл явцсалангид төлөвтэй бол геометрийн схемийг ашиглахад тохиромжтой - төрийн график. Графикийн оройнууд нь системийн төлөвүүд юм. График нумууд - төлөвөөс шилжих боломжтой

Зураг 1. Системийн төлөвийн график

муж. Бидний жишээн дээр төлөвийн графикийг 1-р зурагт үзүүлэв.

Анхаарна уу. Төрөөс шилжих С 0 инч СЗураг дээр 3-ыг заагаагүй тул машинууд бие биенээсээ үл хамааран бүтэлгүйтдэг гэж үздэг. Бид хоёр машин нэгэн зэрэг эвдрэх боломжийг үл тоомсорлодог.

Энэ нь гадаад төрхийг дүрслэхэд маш тохиромжтой санамсаргүй үйл явдлуудсистемийн нэг төлөвөөс нөгөөд шилжих магадлалын хэлбэрээр, учир нь аль нэг мужид шилжсэнээр систем нь энэ төлөвт хэрхэн орсон нөхцөл байдлыг харгалзан үзэхээ больсон гэж үздэг.

Санамсаргүй үйл явц гэж нэрлэдэг Марковын үйл явц(эсвэл үр дагаваргүйгээр үйл явц), хэрэв цаг мөч бүрийн хувьд тИрээдүйд системийн аливаа төлөв байдлын магадлал нь зөвхөн одоогийн төлөв байдлаас хамаарах бөгөөд систем хэрхэн ийм байдалд хүрсэнээс хамаарахгүй.

Тэгэхээр, Марковын үйл явцМужаас муж руу шилжих графикийг зааж өгөх нь тохиромжтой. Бид Марковын үйл явцыг тайлбарлах хоёр сонголтыг авч үзэх болно салангид ба тасралтгүй хугацаатай.

Эхний тохиолдолд нэг төлөвөөс нөгөөд шилжих нь урьд өмнө мэдэгдэж байсан цаг хугацаа, цагийн мөчлөг (1, 2, 3, 4, ) дээр тохиолддог. Шилжилт нь цагийн мөчлөг бүрт тохиолддог, өөрөөр хэлбэл судлаач зөвхөн санамсаргүй үйл явц нь түүний хөгжилд дамждаг төлөв байдлын дарааллыг сонирхдог бөгөөд шилжилт бүр яг хэзээ болсоныг сонирхдоггүй.

Хоёр дахь тохиолдолд судлаач бие биенээ өөрчилдөг төлөв байдлын гинжин хэлхээ болон ийм шилжилт үүссэн цаг хугацааны агшинг хоёуланг нь сонирхож байна.

Бас нэг зүйл. Хэрэв шилжилтийн магадлал нь цаг хугацаанаас хамаарахгүй бол Марковын гинжийг нэгэн төрлийн гэж нэрлэдэг.

Дискрет хугацааны Марковын процесс

Тиймээс бид Марковын үйл явцын загварыг төлөвүүд (оройнууд) нь холболтоор (шилжилтүүд) хоорондоо холбогдсон график хэлбэрээр төлөөлдөг. би- дахь муж j-р төлөв), зургийг үз. 33.1.

Шилжилт бүр тодорхойлогддог шилжилтийн магадлал П ij. Магадлал П ijцохиулсны дараа хэр олон удаа харагдана би--р төлөв рүү шилжинэ j-р муж. Мэдээжийн хэрэг, ийм шилжилт нь санамсаргүй байдлаар тохиолддог, гэхдээ хэрэв та шилжилтийн давтамжийг хангалттай хугацаанд хэмжих юм бол их цаг, дараа нь энэ давтамж давхцах болно өгөгдсөн магадлалшилжилт.

Муж бүрийн хувьд үүнээс бусад муж руу шилжих бүх шилжилтийн (гарч буй сум) магадлалын нийлбэр нь үргэлж 1-тэй тэнцүү байх ёстой (33.2-р зургийг үз).

Жишээлбэл, график бүхэлдээ Зураг дээр үзүүлсэн шиг харагдаж болно. 33.3.

Марковын үйл явцыг хэрэгжүүлэх (түүний загварчлалын үйл явц) нь төлөвөөс төлөвт шилжих шилжилтийн дарааллыг (гинж) тооцоолох явдал юм (Зураг 33.4-ийг үз). Зураг дээрх хэлхээ. 33.4 нь санамсаргүй дараалал бөгөөд өөр хэрэгжүүлэлттэй байж болно.

Үйл явц одоогийнхоос ямар шинэ төлөвт шилжихийг тодорхойлохын тулд би-р төлөвийн хувьд интервалыг хэмжээний дэд интервалд хуваахад хангалттай П би 1 , П би 2 , П би 3, ( П би 1 + П би 2 + П би 3 + = 1), зургийг үз. 33.5. Дараа нь RNG ашиглан та интервалд жигд тархсан дараагийн санамсаргүй тоог авах хэрэгтэй r pp ба аль интервалд орохыг тодорхойлно (Лекц 23-ыг үзнэ үү).

Үүний дараа RNG-ээр тодорхойлсон төлөв рүү шилжиж, шинэ төлөвт тайлбарласан процедурыг давтана. Загварын үр дүн нь Марковын гинж юм (33.4-р зургийг үз ) .

Жишээ. Зорилтот руу их буугаар буудах симуляци. Зорилтот руу их буугаар буудахын тулд бид Марковын санамсаргүй үйл явцын загварыг бүтээх болно.

Дараах гурван төлөвийг тодорхойлъё. С 0 зорилт гэмтээгүй; С 1 бай гэмтсэн; С 2 бай устгасан. Векторыг тохируулъя анхны магадлал:

Утга ПБуудлага эхлэхээс өмнө муж бүрийн 0 нь тухайн объектын төлөв тус бүрийн магадлал ямар байхыг харуулдаг.

Төрийн шилжилтийн матрицыг тохируулъя (Хүснэгт 33.1-ийг үз).

Матриц нь төлөв бүрээс тус бүр рүү шилжих магадлалыг тодорхойлдог. Магадлалыг тодорхой төлөвөөс бусад руу шилжих магадлалын нийлбэр нь үргэлж нэгтэй тэнцүү байхаар тодорхойлогддог болохыг анхаарна уу (систем нь хаа нэгтээ явах ёстой).

Марковын процессын загварыг дараах графикаар дүрсэлж болно (33.6-р зургийг үз).

Загвар, аргыг ашиглах статистик загварчлал, бид дараах асуудлыг шийдэхийг хичээх болно: байг бүрэн устгахад шаардагдах бүрхүүлийн дундаж тоог тодорхойлох.

Санамсаргүй тоонуудын хүснэгтийг ашиглан буудлагын процессыг дуурайцгаая. Анхны төлөв байг С 0 . Санамсаргүй тоонуудын хүснэгтээс дарааллыг авч үзье: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, ( санамсаргүй тоожишээ нь энэ хүснэгтээс авч болно).

0.31 : зорилт нь төлөвт байна С 0 бөгөөд мужид хэвээр байна С 0-ээс хойш 0< 0.31 < 0.45;
0.53 : зорилт нь төлөвт байна С 0 ба төлөвт орно С 0.45-аас хойш 1< 0.53 < 0.45 + 0.40;
0.23 : зорилт нь төлөвт байна С 1 бөгөөд төлөв хэвээр байна С 0-ээс хойш 1< 0.23 < 0.45;
0.42 : зорилт нь төлөвт байна С 1 бөгөөд төлөв хэвээр байна С 0-ээс хойш 1< 0.42 < 0.45;
0.63 : зорилт нь төлөвт байна С 1 ба төлөвт орно С 0.45-аас хойш 2< 0.63 < 0.45 + 0.55.

Төрд хүрснээс хойш С 2 (дараа нь зорилтот байрнаас хөдөлнө С 2 төлөвт байна С 2 магадлал 1), дараа нь бай оносон байна. Энэ туршилтанд үүнийг хийхийн тулд 5 бүрхүүл шаардлагатай байсан.

Зураг дээр. Зураг 33.7-д тайлбарласан загварчлалын явцад олж авсан цаг хугацааны диаграммыг үзүүлэв. Диаграмм нь төлөв өөрчлөгдөх үйл явц цаг хугацааны явцад хэрхэн явагддагийг харуулж байна. Энэ тохиолдолд загварчлах мөчлөг нь тогтмол утгатай байна. Бидний хувьд чухал зүйл бол шилжилтийн баримт (систем ямар төлөвт ордог) бөгөөд энэ нь хэзээ болох нь хамаагүй.

Зорилтотыг устгах процедурыг 5 цагийн мөчлөгөөр дуусгадаг, өөрөөр хэлбэл энэхүү хэрэгжүүлэлтийн Марковын гинж нь дараах байдалтай байна. С 0 — С 0 — С 1 С 1 С 1 С 2 . Мэдээжийн хэрэг, энэ тоо нь асуудлын хариулт байж чадахгүй, учир нь өөр өөр хэрэгжилт өөр өөр хариулт өгөх болно. Мөн аливаа асуудалд ганцхан хариулт байж болно.

Энэ симуляцийг давтан хийснээр та жишээлбэл, дараах ойлголтуудыг авч болно (энэ нь ямар санамсаргүй тоо гарч ирэхээс хамаарна): 4 ( С 0 — С 0 — С 1 С 1 С 2 ); 11 (С 0 — С 0 — С 0 — С 0 — С 0 — С 1 С 1 С 1 С 1 С 1 С 1 С 2 ); 5 (С 1 С 1 С 1 С 1 С 1 С 2 ); 6 (С 0 — С 0 — С 1 С 1 С 1 С 1 С 2 ); 4 (С 1 С 1 С 1 С 1 С 2 ); 6 (С 0 — С 0 — С 1 С 1 С 1 С 1 С 2 ); 5 (С 0 — С 0 — С 1 С 1 С 1 С 2 ). Нийт 8 байг устгасан. Буудах процедурын мөчлөгийн дундаж тоо нь: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 эсвэл дугуйрвал 6. Энэ нь буудахыг зөвлөдөг бүрхүүлийн дундаж тоо юм. Байлдааны нөөцөд ийм цохилт өгөх магадлалтай байг устгах зориулалттай буу байна.

Одоо бид нарийвчлалыг тодорхойлох хэрэгтэй. Энэ нь өгөгдсөн хариултанд хэр их итгэх ёстойг бидэнд харуулж чадах нарийвчлал юм. Үүнийг хийхийн тулд санамсаргүй (ойролцоогоор) хариултуудын дараалал хэрхэн зөв (яг) үр дүнд нийлж байгааг ажиглацгаая. Үүнийг эргэн сануулъя гэж төвөөс мэдээллээ хязгаарын теорем(25-р лекц, 21-р лекцийг үзнэ үү), санамсаргүй хэмжигдэхүүний нийлбэр нь санамсаргүй бус утга учир статистикийн хувьд найдвартай хариулт авахын тулд хэд хэдэн санамсаргүй хэрэгжүүлэлтээр олж авсан сумны дундаж тоог хянах шаардлагатай.

Тооцооллын эхний шатанд дунджаар 5 сум, хоёрдугаар шатанд дундаж хариу (5 + 4)/2 = 4.5 сум, гуравдугаар шатанд (5 + 4 + 11)/3 = 6.7 байна. Цаашилбал, статистик хуримтлагдах үед хэд хэдэн дундаж утгууд дараах байдалтай байна: 6.3, 6.2, 5.8, 5.9, 5.8. Хэрэв бид энэ цувралыг график хэлбэрээр дүрсэлвэл дундаж хэмжээбайг оноход шаардлагатай харвасан сумыг туршилтын тооноос хамааран олж мэдэх болно энэ цувралхариулт болох тодорхой утгад нийлдэг (33.8-р зургийг үз).

График нь "тайвширч", тооцоолсон одоогийн утга ба түүний хоорондох тархалтыг нүдээр харж болно онолын үнэ цэнэцаг хугацааны явцад буурч, статистикийн хувьд үнэн зөв үр дүнд хүрэх хандлагатай байдаг. Өөрөөр хэлбэл, график нь тодорхой "хоолой" руу ордог бөгөөд хэмжээ нь хариултын үнэн зөвийг тодорхойлдог.

Симуляцийн алгоритм нь дараах хэлбэртэй байна (33.9-р зургийг үз).

Дээр дурьдсан тохиолдолд шилжилт ямар үед тохиолдох нь бидэнд хамаагүй гэдгийг дахин сануулъя. Шилжилтийн үе шат дамжлагаар явагддаг. Шилжилт ямар үед тохиолдох, систем муж бүрт хэр удаан үлдэхийг зааж өгөх нь чухал бол тасралтгүй цагийн загварыг хэрэглэх шаардлагатай.

Тасралтгүй хугацааны Марковын санамсаргүй үйл явц

Тиймээс бид Марковын процессын загварыг дахин график хэлбэрээр төлөөлдөг бөгөөд үүнд мужууд (оройнууд) нь холболтоор (шилжилтүүд) хоорондоо холбогдсон байдаг. би- дахь муж j-р төлөв), зургийг үз. 33.10.

Одоо шилжилт бүр нь шилжилтийн магадлалын нягтралаар тодорхойлогддог λ ij. Тодорхойлолтоор:

Энэ тохиолдолд нягтралыг цаг хугацааны хувьд магадлалын хуваарилалт гэж ойлгодог.

-аас шилжих би- дахь муж j-д тохиолддог санамсаргүй мөчүүдшилжилтийн эрч хүчээр тодорхойлогддог цаг хугацаа λ ij .

Шилжилтийн эрч хүч (энд энэ ойлголт нь цаг хугацааны хувьд магадлалын нягтын хуваарилалттай давхцаж байна) т) процесс тасралтгүй, өөрөөр хэлбэл цаг хугацааны туршид тархсан үед дамждаг.

Бид 28-р лекцээс урсгалын эрчимтэй (мөн шилжилтүүд нь үйл явдлын урсгал юм) хэрхэн ажиллах талаар аль хэдийн сурсан. Эрчим хүчийг мэддэг λ ijУтаснаас үүсгэсэн үйл явдлуудын дүр төрхөөр та энэ хэлхээний хоёр үйл явдлын хоорондох санамсаргүй интервалыг дуурайж болно.

Хаана τ ijсистемд байх хоорондох хугацааны интервал би-ом ба j-р нөхцөл.

Цаашилбал, ямар ч байсан систем би- муж хэд хэдэн муж улсын аль нэгэнд орж болно j , j + 1 , j+ 2, , түүнтэй холбоотой шилжилтүүд λ ij , λ ij + 1 , λ ij+ 2, .

IN j-Тэрээр дамжин өнгөрөх муж τ ij; V ( j+ 1 )-р төлөвт энэ нь дамжих болно τ ij+ 1; V ( j+ 2 )-р төлөв энэ нь дамжих болно τ ij+ 2 гэх мэт.

Системээс явах боломжтой нь тодорхой байна би---р төлөв нь эдгээрийн зөвхөн аль нэгэнд, шилжилтийн өмнөх үе рүү шилжих.

Тиймээс цаг хугацааны дарааллаар: τ ij , τ ij + 1 , τ ij+ 2 гэх мэт хамгийн бага хэмжээг сонгож, индексийг тодорхойлох хэрэгтэй j, аль төлөвт шилжилт хийхийг заана.

Жишээ. Машины үйл ажиллагааны симуляци. Машины ажиллагааг дуурайж үзье (33.10-р зургийг үз), энэ нь дараах төлөвт байж болно. С 0 машин ажиллаж байгаа, үнэ төлбөргүй (сул зогсолт); С 1 машин ажиллаж байна, завгүй (боловсруулж байна); С 2 машин ажиллаж байна, багаж солих (дахин тохируулах) λ 02 < λ 21 ; С 3 машин гэмтэлтэй, засварын ажил хийгдэж байна λ 13 < λ 30 .

Параметрийн утгыг тохируулъя λ , онд олж авсан туршилтын өгөгдлийг ашиглан үйлдвэрлэлийн нөхцөл: λ Боловсруулах 01 урсгал (өөрчлөхгүйгээр); λ 10 үйлчилгээний урсгал; λ 13 тоног төхөөрөмжийн эвдрэлийн урсгал; λ 30 сэргээх урсгал.

Хэрэгжилт нь иймэрхүү харагдах болно (33.11-р зургийг үз).

Ялангуяа, Зураг дээрээс. 33.11-ээс та хэрэгжүүлсэн хэлхээ дараах байдалтай байгааг харж болно. С 0 — С 1 С 0 —… Шилжилтүүд дараах үеүүдэд тохиолдсон. Т 0 — Т 1 Т 2 Т 3…, Хаана Т 0 = 0 , Т 1 = τ 01, Т 2 = τ 01 + τ 10.

Даалгавар. Загвар нь өмнө нь хариулт нь бидэнд тодорхойгүй байсан асуудлыг шийдвэрлэхэд ашиглахаар бүтээгдсэн тул (лекц 01-ийг үзнэ үү) бид ийм асуудлыг томъёолох болно. энэ жишээ. Өдрийн турш машин ажиллахгүй байх хугацааг тодорхойлох (зураг дээр үндэслэн тооцоолно уу) Т av = ( Т + Т + Т + Т)/Н .

Симуляцийн алгоритм нь дараах хэлбэртэй байна (33.12-р зургийг үз).

Ихэнхдээ Марковын процессын төхөөрөмжийг компьютерийн тоглоом, компьютерийн дүрүүдийн үйлдлийг загварчлахад ашигладаг.

Марковын санамсаргүй үйл явц нь Оросын нэрт математикч А.А. Марков (1856-1922) анх санамсаргүй хэмжигдэхүүнүүдийн магадлалын хамаарлыг судалж эхэлсэн бөгөөд "магадлалын динамик" гэж нэрлэж болох онолыг бий болгосон. IN нэмэлт суурьЭнэ онол нь анхны үндэс суурь болсон ерөнхий онолсанамсаргүй үйл явц, түүнчлэн ийм чухал ач холбогдолтой хэрэглээний шинжлэх ухаан, тухайлбал тархалтын процессын онол, найдвартай байдлын онол, дарааллын онол гэх мэт. Одоогийн байдлаар Марковын үйл явцын онол ба түүний хэрэглээг хамгийн их ашиглаж байна янз бүрийн бүс нутагмеханик, физик, хими гэх мэт шинжлэх ухаан.

Математикийн аппаратын харьцангуй энгийн, ойлгомжтой байдлын ачаар олж авсан шийдлүүдийн өндөр найдвартай байдал, нарийвчлал онцгой анхааралМарковын процессыг үйл ажиллагааны судалгаа, оновчтой шийдвэрийн онолд хамрагдсан мэргэжилтнүүдээс олж авсан.

Дээрх энгийн бөгөөд ойлгомжтой байдлыг үл харгалзан, практик хэрэглээМарковын гинжин хэлхээний онол нь жишээ үзүүлэхээс өмнө хэлэлцэх ёстой зарим нэр томъёо, үндсэн зарчмуудын талаархи мэдлэгийг шаарддаг.

Марковын санамсаргүй процессууд нь санамсаргүй үйл явцын (SP) онцгой тохиолдлуудыг хэлдэг. Эргээд санамсаргүй үйл явц нь санамсаргүй функц (SF) гэсэн ойлголт дээр суурилдаг.

Санамсаргүй функц нь аргументийн аль ч утгын хувьд санамсаргүй хэмжигдэхүүн (RV) байх функц юм. Өөрөөр хэлбэл, тест болгонд урьд өмнө нь үл мэдэгдэх хэлбэрийг авдаг SF функц гэж нэрлэж болно.

SF-ийн ийм жишээнүүд нь: хүчдэлийн хэлбэлзэл цахилгаан хэлхээ, хурдны хязгаарлалттай замын хэсэг дэх машины хурд, тодорхой хэсэг дэх хэсгийн гадаргуугийн барзгар байдал гэх мэт.

Дүрмээр бол, хэрэв SF-ийн аргумент нь цаг хугацаа бол ийм үйл явцыг санамсаргүй гэж нэрлэдэг гэж үздэг. Шийдвэрлэх онолтой ойр санамсаргүй үйл явцын өөр нэг тодорхойлолт байдаг. Энэ тохиолдолд санамсаргүй үйл явц нь аливаа физик эсвэл төлөв байдлын санамсаргүй өөрчлөлтийн үйл явц гэж ойлгогддог техникийн системцаг хугацаа эсвэл өөр ямар нэг үндэслэлээр.

Хэрэв та төлөвийг тодорхойлж, хамаарлыг дүрсэлсэн бол ийм хамаарал нь санамсаргүй функц болно гэдгийг харахад хялбар байдаг.

Санамсаргүй үйл явц нь төлөвийн төрлүүд болон аргумент t-ийн дагуу ангилагдана. Энэ тохиолдолд санамсаргүй процессууд нь салангид эсвэл байж болно тасралтгүй төлөвүүдэсвэл цаг хугацаа.

Санамсаргүй үйл явцын ангиллын дээрх жишээнүүдээс гадна өөр нэг зүйл бий чухал өмч. Энэ шинж чанар нь санамсаргүй үйл явцын төлөв хоорондын магадлалын холболтыг тодорхойлдог. Жишээлбэл, санамсаргүй байдлаар систем дараагийн төлөвт шилжих магадлал нь зөвхөн өмнөх төлөвөөс хамаардаг бол ийм үйл явцыг сөрөг нөлөөгүй процесс гэж нэрлэдэг.

Юуны өмнө, салангид төлөв, цаг хугацаатай санамсаргүй үйл явцыг санамсаргүй дараалал гэж нэрлэдэг гэдгийг тэмдэглэе.

Хэрэв санамсаргүй дараалал Марковын шинж чанартай бол түүнийг Марковын гинж гэнэ.

Нөгөөтэйгүүр санамсаргүй үйл явцын үед төлөвүүд нь салангид, цаг тасралтгүй, үр дагаварын шинж чанар нь хадгалагдвал ийм санамсаргүй үйл явцыг тасралтгүй хугацаатай Марковын процесс гэнэ.

Хэрэв процессын явцад шилжилтийн магадлал тогтмол хэвээр байвал Марковын санамсаргүй процессыг нэгэн төрлийн гэж нэрлэдэг.

Хэрэв хоёр нөхцөл өгөгдсөн бол Марковын хэлхээг өгсөн гэж үзнэ.

1. Матриц хэлбэрийн шилжилтийн магадлалын багц байна.

2. Анхны магадлалын вектор байна

системийн анхны төлөвийг дүрсэлсэн.

Үүнээс бусад нь матриц хэлбэрМарковын гинжин хэлхээний загварыг чиглэсэн жинтэй график хэлбэрээр дүрсэлж болно (Зураг 1).

Цагаан будаа. 1

Марковын гинжин системийн төлөв байдлын багцыг системийн цаашдын үйл ажиллагааг харгалзан тодорхой байдлаар ангилдаг.

1. Буцахгүй багц (Зураг 2).

Зураг 2.

Буцахгүй олонлогийн хувьд энэ багц дотор ямар ч шилжилт хийх боломжтой. Систем энэ багцыг орхиж болох боловч буцаж чадахгүй.

2. Буцах багц (Зураг 3).

Цагаан будаа. 3.

Энэ тохиолдолд багц доторх аливаа шилжилт бас боломжтой. Систем энэ багц руу орж болох боловч орхиж болохгүй.

3. Эргодик багц (Зураг 4).

Цагаан будаа. 4.

Эргодик багцын хувьд багц доторх аливаа шилжилт боломжтой боловч олонлогоос болон олонлог руу шилжих шилжилтийг оруулаагүй болно.

4. Шингээгч багц (Зураг 5)

Цагаан будаа. 5.

Систем энэ багц руу ороход процесс дуусна.

Зарим тохиолдолд үйл явцын санамсаргүй байдлаас үл хамааран үүнийг хийх боломжтой тодорхой хэмжээгээрхуваарилалтын хууль буюу шилжилтийн магадлалын параметрүүдийг хянах. Ийм Марковын гинжийг хяналттай гэж нэрлэдэг. Мэдээжийн хэрэг, Марковын хяналттай гинжин хэлхээний (CMC) тусламжтайгаар шийдвэр гаргах үйл явц ялангуяа үр дүнтэй болох бөгөөд үүнийг дараа хэлэлцэх болно.

Дискрет Марковын гинжин хэлхээний (DMC) гол онцлог нь үйл явцын бие даасан алхмуудын (үе шат) хоорондын хугацааны интервалын детерминизм юм. Гэсэн хэдий ч ихэнхдээ бодит процесст энэ шинж чанар ажиглагддаггүй бөгөөд интервалууд нь зарим тархалтын хуулиар санамсаргүй байдлаар хувирдаг боловч процессын Марковын шинж чанар хадгалагдан үлддэг. Ийм санамсаргүй дараалалхагас Марков гэж нэрлэдэг.

Нэмж дурдахад, дээр дурьдсан төлөв байдлын тодорхой багц байгаа эсэхээс үл хамааран Марковын гинж нь дор хаяж нэг шингээх төлөвтэй бол шингээгч, шилжилтийн магадлал нь эргодик багц үүсгэдэг бол эргодик байж болно. Хариуд нь ergodic гинж нь тогтмол эсвэл мөчлөгтэй байж болно. Циклийн гинж нь ердийнхөөс ялгаатай нь тодорхой тооны алхмууд (мөчлөгүүд) дамжин шилжих үед зарим төлөвт буцаж ирдэг. Ердийн сүлжээнүүд ийм өмчтэй байдаггүй.

Үүний дараа ямар ч хувьсал утгыг тохируулахцаг хугацааны параметр t нь өмнөх хувьсалаас хамаарахгүй т,тухайн үеийн үйл явцын үнэ цэнэ тогтсон тохиолдолд (товчхондоо: үйл явцын "ирээдүй" ба "өнгөрсөн" нь мэдэгдэж буй "одоо"-той бие биенээсээ хамаардаггүй).

Соронзон талбарыг тодорхойлдог шинж чанарыг ихэвчлэн нэрлэдэг Марковиан; Үүнийг анх A. A. Марков томъёолсон. Гэсэн хэдий ч аль хэдийн Л.Бачелиерийн бүтээлээс Брауны хөдөлгөөнийг соронзон процесс гэж тайлбарлах оролдлого нь Н.Винерийн судалгааны дараа үндэслэлээ олж авсан оролдлого (N. Wiener, 1923) байгааг анзаарч болно. Тасралтгүй хугацааны соронзон үйл явцын ерөнхий онолын үндэс суурийг A. N. Колмогоров тавьсан.

Марковын өмч. Бие биенээсээ эрс ялгаатай M.-ийн тодорхойлолтууд байдаг бөгөөд тэдгээрийн нэг нь дараахь зүйл юм. Явцгаая магадлалын орон зайхэмжигдэхүйц орон зайн утгууд бүхий санамсаргүй үйл явц энд өгөгдсөн Т -дэд олонлог бодит тэнхлэгБолъё Nt(тус тус Nt).-д s-алгебр байдаг X(s).at хэмжигдэхүүнээр үүсгэгдсэн Хаана Өөрөөр хэлбэл, Nt(тус тус Nt) нь t мөч (t-ээс эхлэн) хүртэлх үйл явцын хувьсалтай холбоотой үйл явдлын багц юм. . X(t) процессыг дуудна Хэрэв (бараг гарцаагүй) Марковын өмч нь бүгдэд зориулагдсан бол Марковын процесс:

эсвэл, юу нь ижил, хэрэв байгаа бол

M. p., үүний төлөө T нь багцад агуулагддаг натурал тоонууд, дуудсан Марковын гинж(гэхдээ сүүлийн нэр томьёо нь хамгийн их тоологдох E-тэй холбоотой байдаг) . Хэрэв Is интервал тоолохоос илүү байвал M. гэж дуудагдана. тасралтгүй хугацаа Марковын гинж. Тасралтгүй үргэлжлэх соронзон үйл явцын жишээг Пуассон ба Винерийн процесс зэрэг бие даасан өсөлт бүхий тархалтын процессууд болон процессуудаар өгсөн болно.

Ирээдүйд, тодорхой болгохын тулд бид зөвхөн (1) ба (2) томъёоны жишээн дээр "өнгөрсөн" ба "ирээдүй" -ийн бие даасан байдлын зарчмыг мэдэгдэж буй "одоо"-той тодорхой тайлбарлах болно. Тэдгээрийн үндсэн дээр M. p-ийн тодорхойлолт нь нэг биш, харин харилцан тохиролцсон (1) эсвэл (2) төрлийн нөхцлүүдийн багцыг авч үзэх шаардлагатай үед хангалттай уян хатан биш болсон. тодорхой байдлаар, ийм төрлийн арга хэмжээнүүд нь үрчлүүлэхэд хүргэсэн дараах тодорхойлолт(см., ).

Дараахь зүйлийг өгье.

a) s-алгебр нь Е дахь бүх нэг цэгийн олонлогуудыг агуулсан хэмжигдэхүйц орон зай;

b) s-алгебрын бүлгээр тоноглогдсон хэмжигдэхүйц зай, хэрэв бол

в) функц ("траектор") x t = xт(w) , хэмжиж болох аливаа зураглалыг тодорхойлох

г) тус бүрийн хувьд ба s-алгебр дээрх функцийг хэрэв болон -тэй харьцуулах боломжтой байх магадлалын хэмжүүр.

Нэрийн багц (төгсгөхгүй) Марковын процесс if -бараг гарцаагүй байдлаар тодорхойлогддог

Тэд юу ч байсан энд орон зай байна энгийн үйл явдлууд, - фазын орон зай эсвэл төлөвийн орон зай, P( s, x, t, V)- шилжилтийн функцэсвэл процессын шилжилтийн магадлал X(t) . Хэрэв E нь топологитой бөгөөд Borel-ийн цуглуулга юм Э,дараа нь M. p өгөгдсөн гэж хэлэх нь заншилтай байдаг Э.Ер нь, M. p-ийн тодорхойлолт нь тухайн тохиолдолд магадлал гэж тайлбарлах шаардлагыг агуулдаг x s = x.

Асуулт гарч ирнэ: Марковын шилжилтийн функц бүр P( s, x;т, В), хэмжигдэхүйц орон зайд өгөгдсөнийг тодорхой M. орон зайн шилжилтийн функц гэж үзэж болно, жишээлбэл, E нь салгах боломжтой орон нутгийн авсаархан орон зай бөгөөд Borel багцуудын цуглуулга бол эерэг байна. Э.Түүнээс гадна, зөвшөөр E -бүрэн хэмжүүр зай ба зөвшөөрөх

A - цэгийн цахим хөршийн нэмэлт X.Дараа нь харгалзах соронзон орон нь баруун талдаа тасралтгүй, зүүн талдаа хязгаартай гэж үзэж болно (өөрөөр хэлбэл түүний траекторийг сонгож болно). Тасралтгүй соронзон орон байх нь нөхцөлөөр баталгааждаг (харна уу). Механик процессын онолд нэгэн төрлийн (цаг хугацааны хувьд) процессуудад гол анхаарлаа хандуулдаг. Холбогдох тодорхойлолт нь өгөгдсөн систем объектууд a) - d) тайлбар дээр гарч ирсэн s ба u параметрүүдийн хувьд одоо зөвхөн 0 утгыг зөвшөөрч байгаа тул тэмдэглэгээг хялбаршуулсан болно.

Цаашилбал, W орон зайн нэгэн төрлийн байдал, өөрөөр хэлбэл, s-алгебр дээр (w) байх шаардлагатай. Н,Маягтын аливаа үйл явдлыг агуулсан W дахь s-алгебруудын хамгийн бага нь q цаг шилжүүлэх операторууд өгөгдсөн. т, олонлогуудын нэгдэл, огтлолцол, хасах үйлдлүүдийг хадгалах ба аль нь

Нэрийн багц (төгсгөхгүй) нэгэн төрлийн Марков процессыг if -бараг гарцаагүй байдлаар тодорхойлсон

X(t) процессын Шилжилтийн функцийн хувьд P( гэж үзнэ. t, x, V), мөн тусгай захиалга байхгүй бол тэд нэмэлтээр шаарддаг. (4)-г шалгахдаа зөвхөн хаана, юу (4)-д байгаа маягтын багцыг авч үзэх нь хангалттай гэдгийг санах нь зүйтэй. Фт s-алгебраар сольж болно, уулзвартай тэнцүү байнанөхөн Фтбүх боломжит хэмжүүрүүдийн хувьд ихэвчлэн магадлалын хэмжүүр m ("анхны тархалт") тогтмол байдаг ба Марков санамсаргүй функцтэгшитгэлээр өгөгдсөн хэмжүүр хаана байна

M. p. Хэрэв t>0 тутамд функц нь s-алгебр хаана байгааг хэмжих боломжтой зураглалыг өдөөдөг бол аажмаар хэмжигдэх боломжтой

Borel дэд олонлогууд . Зөв үргэлжилсэн УИХ-ын гишүүдийг аажмаар хэмжиж болно. бууруулах арга бий гетероген тохиолдолнэгэн төрлийн (харна уу), ирээдүйд бид нэгэн төрлийн M. зүйлийн талаар ярих болно.

Марковын өмч.Хэмжих боломжтой зайг м-ээр өгье.

Функцийг дууддаг Марковын мөч,Хэрэв хүн бүрт Энэ тохиолдолд олонлогийг F t if at (ихэнхдээ F t нь X(t)-ийн t мөч хүртэлх хувьсалтай холбоотой үйл явдлын багц гэж тайлбарладаг) гэр бүл гэж ангилдаг. Итгэлийн төлөө

Аажмаар хэмжигдэхүйц M. Xnaz. хатуу Марковын процесс (s.m.p.), хэрэв ямар нэгэн Марков агшинд m ба бүх ба хамаарал

(хатуу Марков өмч) багц W t дээр бараг гарцаагүй сэтгэл хангалуун байна. (5)-ыг шалгахдаа энэ тохиолдолд тэгш хэмтэй орон зай нь, жишээлбэл, топологийн аль ч баруун үргэлжилсэн Феллер хэмжээст орон зай байх хэлбэрийн багцуудыг авч үзэхэд хангалттай. орон зай Э. M. p. Фэллер Марков үйл явц бол функц

f тасралтгүй ба хязгаарлагдмал байх бүрт тасралтгүй байна.

-тай ангид. m.p. тодорхой дэд ангиуд нь ялгагдана. Марковын шилжилтийн функц P( t, x, V), хэмжигдэхүүн орон нутгийн авсаархан зайд тодорхойлсон Э,стохастик тасралтгүй:

Цэг бүрийн аль ч хөршийн U хувьд Дараа нь операторууд хязгааргүйд алга болдог тасралтгүй функцүүдийн ангиллыг өөртөө авбал P( функцууд. t, x, V) стандартыг хангасан M. p. X,өөрөөр хэлбэл баруун талд үргэлжилсэн. m.p., үүний төлөө

Марковын үйл явцыг дуусгавар болгож байна.Ихэнхдээ бие махбодь Төгсгөлгүй соронзон орон ашиглан системийг дүрслэхийг зөвлөж байна, гэхдээ зөвхөн санамсаргүй урттай хугацааны интервал дээр. Түүнээс гадна, бүр энгийн өөрчлөлтүүдУИХ-ын гишүүд тодорхой чиглэлтэй үйл явцад хүргэж болно санамсаргүй интервал(см. "Функциональ"Марковын процессоос). Эдгээр бодолд тулгуурлан эвдэрсэн УИХ-ын гишүүн гэсэн ойлголтыг оруулж ирж байна.

Шилжилтийн функцтэй фазын орон зайд нэгэн төрлийн соронзон орон байг, мөн адил цэг ба функц байг (хэрэв тусгай тайлбар байхгүй бол ). Шинэ замнал х т(w) нь зөвхөн ) тэгш байдлын тусламжтайгаар тодорхойлогддог a Фтбагц дахь ул мөр гэж тодорхойлогддог

Дуудсан газраа тохируулна уу z үед дуусгавар болгох (эсвэл алах) замаар олж авсан Марковын төгсгөлийн процессоор (o.m.p.). z утгыг дуудна завсарлах мөч буюу амьдралын цаг, о. м.п. Фазын орон зайШинэ процесс нь s-алгебрийн ул мөр байгаа газарт үйлчилдэг Э.Шилжилтийн функц o. m.p. нь X(t) процесст заасан хязгаарлалт юм. хатуу Марков процесс, эсвэл стандарт Марков процесс бол холбогдох өмчхугаршгүй M.-тэй байна p гэж үзэж болно. m.p. эвдрэх мөчтэй Гетероген o. m.p. ижил төстэй байдлаар тодорхойлогддог. М.

Марковын процесс ба дифференциал тэгшитгэл. M. p. төрөл Брауны хөдөлгөөнпараболын дифференциал тэгшитгэлтэй нягт холбоотой. төрөл. Шилжилтийн нягт p(s, x, t, y) тархалтын процесс нь тодорхой нэмэлт таамаглалын дагуу Колмогоровын урвуу ба шууд дифференциал тэгшитгэлийг хангадаг.

функц p( s, x, t, y).нь (6) - (7) тэгшитгэлийн Ногоон функц ба эхнийх мэдэгдэж байгаа аргуудДиффузын процессыг бүтээхдээ энэ функцийн оршин тогтнох теоремууд дээр үндэслэсэн дифференциал тэгшитгэл(6) - (7). Цаг хугацааны хувьд нэгэн төрлийн процессын хувьд оператор L( s, x)= Л(x).on жигд функцуудшинж чанартай таарч байна оператор M. p "Шилжилтийн операторуудын хагас бүлэг").

Математик. Янз бүрийн функцүүдийн тархалтын процессоос хүлээгдэж буй хүлээлт нь холбогдох асуудлыг шийдэх шийдэл болдог хил хязгаарын асуудалдифференциал тэгшитгэлийн хувьд (1). Математикийн. хэмжигдэхүүн дэх хүлээлт Дараа нь функц нь цагт хангадаг s тэгшитгэл (6) ба нөхцөл

Үүний нэгэн адил функц

-д сэтгэл хангалуун байдаг s тэгшитгэл

болон нөхцөл ба 2 ( Т, х) = 0.

Хил дээр хамгийн түрүүнд хүрэх мөчийг tt гэж үзье dDбүс нутаг үйл явцын замнал Дараа нь, тодорхой нөхцөлд, функц

тэгшитгэлийг хангана

мөн багц дээрх cp утгыг авдаг

Ерөнхий шугаман параболын 1-р хилийн бодлогын шийдэл. 2-р эрэмбийн тэгшитгэл

нэлээн ерөнхий төсөөллийн дагуу хэлбэрээр бичиж болно

Оператор L ба функц ажиллах тохиолдолд s, f-аас хамаарахгүй с,Шугаман эллипсийг шийдвэрлэхэд (9)-тэй төстэй дүрслэл бас боломжтой. тэгшитгэл Илүү нарийн, функц

тодорхой таамаглалын дагуу асуудлыг шийдэх гарц байдаг

L оператор доройтох тохиолдолд (del b() s, x) = 0 ).эсвэл хил dDХангалттай "сайн" биш бол хилийн утгыг (9), (10) функцууд бие даасан цэгүүд эсвэл бүхэл бүтэн багц дээр хүлээн авахгүй байж болно. Операторын ердийн хилийн цэгийн тухай ойлголт Лмагадлалын тайлбартай. Хилийн ердийн цэгүүдэд (9), (10) функцээр хилийн утгыг олж авдаг. Асуудлыг шийдвэрлэх (8), (11) нь харгалзах тархалтын процессуудын шинж чанар, тэдгээрийн функцийг судлах боломжийг олгодог.

Жишээлбэл, (6), (7) тэгшитгэлийн шийдлийг бий болгоход тулгуурлаагүй УИХ-ын гишүүдийг байгуулах аргууд байдаг. арга стохастик дифференциал тэгшитгэл,хэмжүүрийн туйлын тасралтгүй өөрчлөлт гэх мэт. Энэхүү нөхцөл байдал нь (9), (10) томъёоны хамт (8) тэгшитгэлийн хилийн бодлогын шинж чанаруудыг магадлалын дагуу барьж, судлах боломжийг олгодог. харгалзах эллипс. тэгшитгэл

Стохастик дифференциал тэгшитгэлийн шийдэл нь b() матрицын доройтолд мэдрэмтгий биш тул s, x), Тэр магадлалын аргуудэллипс ба параболын дифференциал тэгшитгэлийг задлах шийдлүүдийг бүтээхэд ашигласан. Н.М.Крылов, Н.Н.Боголюбов нарын дундажийг тооцох зарчмыг стохастик дифференциал тэгшитгэл болгон өргөжүүлснээр (9)-ийг ашиглан эллипс ба параболын дифференциал тэгшитгэлд тохирох үр дүнг гаргах боломжтой болсон. Зарим хэцүү даалгаварЭнэ төрлийн тэгшитгэлийн шийдлүүдийн шинж чанарыг хамгийн өндөр дериватив дээр бага параметртэй судлах нь магадлалын үндэслэлийг ашиглан шийдвэрлэх боломжтой болсон. (6) тэгшитгэлийн 2-р хилийн бодлогын шийдэл нь мөн магадлалын утгатай байна. Хязгааргүй домэйны хилийн утгын бодлогуудын томъёолол нь харгалзах тархалтын процессын давтагдахтай нягт холбоотой байдаг.

Цаг хугацааны нэгэн төрлийн үйл явцын хувьд (L нь s-ээс хамаардаггүй) үржүүлэх тогтмол хүртэл тэгшитгэлийн эерэг шийдэл нь тодорхой таамаглалаар давхцдаг. суурин нягтралМП-ийн хуваарилалт нь шугаман бус параболикуудын хилийн утгын бодлогуудыг авч үзэхэд бас ашигтай байдаг. тэгшитгэл. R. 3. Хасминский.

Гэрэл.: Марков А.А., "Известия. Казанийн их сургуулийн Физик-математикийн нийгэмлэг", 1906, 15-р боть, №4, х. 135-56; В а ш е л и э р Л., "Анн. шинжлэх ухаан. Экол норм, супер.", 1900, v. 17, х. 21-86; Колмогоров А.Н., "Математик Анн.", 1931, Bd 104, S. 415-458; орос. Орч. - "Успехи Математических Наук", 1938, зуун. 5, х. 5-41; Жун Кай-лай, Нэг төрлийн Марковын хэлхээ, транс. Англи хэлнээс, М., 1964; R e 1 1 e r W., "Ann. Math.", 1954, v. 60, х. 417-36; Динкин Е.Б., Юшкевич А.А., " Онол байх магадлалтай. ба түүний хэрэглээ.", 1956, 1-р боть, 1-р тал, 149-55 хуудас; X ба н т Ж.-А., Марков процесс ба потенциал, англи хэлнээс орчуулсан, М., 1962; Д е л ла шер. болон K., Capacities and random processs, trans. , Санамсаргүй үйл явцын онол, 2-р боть, М., 1973: Шинжлэх ухааны үр дүн. математик статистик. - Онолын кибернетик. 1966, М., 1967, х. 7-58; X a s minskiy R. 3., "Магадлалын онол ба түүний хэрэглээ", 1963, 8-р боть . 1, х. 3-25; Ventzel A.D., Freidlin M.I., Fluctuations in динамик системүүджижиг санамсаргүй эвдрэлийн нөлөөн дор, М., 1979; Blumenthal R. M., G e t o r R. K., Марков процесс ба боломжийн онол, N.Y.-L., 1968; Getоor R. K., Марков процесс: Рэй процесс ба зөв процесс, В., 1975; Кузнецов С.Е., "Магадлалын онол ба түүний хэрэглээ", 1980, 25-р боть. 2, х. 389-93.

Дарааллын системийн бүтэц, ангилал

Дарааллын системүүд

Ихэнхдээ дарааллын системтэй (QS) холбоотой магадлалын асуудлуудыг шийдвэрлэх шаардлагатай байдаг бөгөөд үүний жишээ нь:

Тасалбарын кассууд;

засварын газрууд;

Худалдаа, тээвэр, эрчим хүчний системүүд;

Харилцаа холбооны систем;

Ийм тогтолцооны нийтлэг байдал нь нэгдмэл байдлаар илэрдэг математик аргуудболон тэдний үйл ажиллагааг судлахад ашигласан загварууд.

Цагаан будаа. 4.1. TMO-ийн хэрэглээний үндсэн чиглэлүүд

QS-ийн оролт нь үйлчилгээний хүсэлтийн урсгалыг хүлээн авдаг. Жишээлбэл, үйлчлүүлэгч эсвэл өвчтөн, тоног төхөөрөмжийн эвдрэл, утасны дуудлага. Хүсэлтүүд тогтмол бус, санамсаргүй цагт ирдэг. Үйлчилгээний үргэлжлэх хугацаа нь бас санамсаргүй байдаг. Энэ нь QS-ийн ажилд жигд бус байдлыг бий болгож, хэт ачаалал, бага ачаалал үүсгэдэг.

Дарааллын системүүд байдаг өөр бүтэц, гэхдээ ихэвчлэн тэдгээрийг ялгаж чаддаг дөрвөн үндсэн элемент:

1. Шаардлагын орж ирж буй урсгал.

2. Хадгалах (дараалал).

3. Төхөөрөмжүүд (үйлчилгээний суваг).

4. гадагшлах урсгал.

Цагаан будаа. 4.2. Ерөнхий схемдарааллын системүүд

Цагаан будаа. 4.3. Системийн үйл ажиллагааны загвар

(сум нь шаардлага хүлээн авах мөчийг заана

систем, тэгш өнцөгт - үйлчилгээний хугацаа)

Зураг 4.3 а-д шаардлагын тогтмол урсгал бүхий системийн загварыг үзүүлэв. Хүсэлт хүлээн авах хоорондын зай тодорхой тул үйлчилгээний хугацааг системийг бүрэн ачаалахаар сонгосон. Шаардлагын стохастик урсгалтай системийн хувьд нөхцөл байдал огт өөр байдаг - шаардлага гарч ирдэг янз бүрийн мөчүүдцаг ба үйлчилгээний хугацаа нь мөн санамсаргүй хэмжигдэхүүн бөгөөд үүнийг зарим тархалтын хуулиар тодорхойлж болно (Зураг 4.3 б).

Дараалалд тавих дүрмээс хамааран дараахь QS-ийг ялгадаг.

1) алдаатай системүүд , үйлчилгээний бүх сувгууд завгүй байх үед хүсэлт нь системийг үйлчилгээгүй орхидог;

2) хязгааргүй дараалал бүхий системүүд , хүсэлтийг хүлээн авах үед бүх үйлчилгээний суваг завгүй байсан бол дараалалд ордог;

3) хүлээлт, хязгаарлагдмал дараалал бүхий системүүд , хүлээх хугацаа нь зарим нөхцлөөр хязгаарлагддаг эсвэл дараалалд байгаа програмуудын тоонд хязгаарлалт байдаг.

Ирж буй шаардлагын урсгалын шинж чанарыг авч үзье.

Шаардлагын урсгал гэж нэрлэдэг суурин , хэрэв тодорхой тооны үйл явдлын тодорхой урттай цагийн сегментэд орох магадлал нь зөвхөн энэ сегментийн уртаас хамаарна.

Үйл явдлын урсгал гэж нэрлэгддэг үр дагаваргүйгээр урсах , хэрэв тодорхой хугацаанд унасан үйл явдлын тоо бусад дээр унасан үйл явдлын тооноос хамаарахгүй бол.

Үйл явдлын урсгал гэж нэрлэгддэг жирийн , хэрэв хоёр ба түүнээс дээш үйл явдал нэгэн зэрэг ирэх боломжгүй бол.

Шаардлагын урсгал гэж нэрлэдэг Пуассон (эсвэл хамгийн энгийн) хэрэв энэ нь гурван шинж чанартай бол: суурин, энгийн, үр дагаваргүй. Гүйцэтгэх үед энэ нэрээс гаралтай заасан нөхцөлТогтмол хугацааны интервалд хамаарах үйл явдлын тоог Пуассоны хуулийн дагуу хуваарилна.

Эрчим хүчхэрэглээний урсгал λ нь урсгалаас нэгж хугацаанд ирж буй хэрэглээний дундаж тоо юм.

Хөдөлгөөнгүй урсгалын хувьд эрчим нь тогтмол байна. Хэрэв τ нь хоёр хөрш хүсэлтийн хоорондох хугацааны интервалын дундаж утга бол Пуассон урсгалын хувьд үйлчилгээнд ирэх магадлал. мтодорхой хугацаанд өргөдөл гаргах тПуассоны хуулиар тодорхойлогддог:

Хөрш зэргэлдээх хүсэлтүүдийн хоорондох хугацааг дагуу хуваарилдаг экспоненциал хуульмагадлалын нягтралтай

Үйлчилгээний хугацаа нь санамсаргүй хэмжигдэхүүн бөгөөд үүнд хамаарна экспоненциал хуульмагадлалын нягтрал бүхий тархалт Энд μ нь үйлчилгээний урсгалын эрчим, i.e. нэгж цаг тутамд үйлчилсэн хүсэлтийн дундаж тоо,

Ирж буй урсгалын эрчмийг үйлчилгээний урсгалын эрчимтэй харьцуулсан харьцааг нэрлэдэг. системийг ачаалах

Дарааллын систем нь хязгаарлагдмал буюу тоолж болох олон төлөвтэй салангид төрлийн систем бөгөөд ямар нэгэн үйл явдал тохиолдоход системийн нэг төлөвөөс нөгөөд шилжих шилжилт гэнэт явагддаг.

Процесс гэж нэрлэдэг салангид төлөвтэй процесс , хэрэв түүний боломжит төлөвүүдийг урьдчилан дахин дугаарлаж болох бөгөөд системийн төлөвөөс төлөв рүү шилжих шилжилт бараг тэр даруй тохиолддог.

Ийм үйл явц нь салангид эсвэл тасралтгүй цаг гэсэн хоёр төрөл байдаг.

Дискрет цагийн хувьд төлөвөөс төлөв рүү шилжих шилжилт нь цаг хугацааны хатуу тодорхойлогдсон цэгүүдэд тохиолдож болно. Тасралтгүй хугацааны процессууд нь систем ямар ч үед шинэ төлөвт шилжиж чаддагаараа ялгагдана.

Санамсаргүй үйл явц гэдэг нь аргументийн утга тус бүрийг агуулсан захидал харилцаа юм энэ тохиолдолд– туршилтын хугацаа) нь санамсаргүй хэмжигдэхүүнтэй холбоотой (энэ тохиолдолд QS-ийн төлөв). Санамсаргүй хувьсагч Туршлагын үр дүнд нэг зүйлийг авч болох хэмжигдэхүүн бөгөөд аль нь болохыг урьдчилж мэдэгдээгүй, тоон утгаөгөгдсөн тооны багцаас.

Тиймээс дарааллын онолын асуудлыг шийдэхийн тулд энэ санамсаргүй үйл явцыг судлах шаардлагатай, i.e. түүний математик загварыг барьж, дүн шинжилгээ хийх.

Санамсаргүй үйл явцдуудсан Марковиан , хэрэв цаг хугацааны аль нэг мөчид ирээдүйн үйл явцын магадлалын шинж чанар нь зөвхөн тухайн үеийн төлөв байдлаас хамаарах бөгөөд систем хэзээ, хэрхэн ийм байдалд хүрсэнээс хамаарахгүй бол.

Системийн төлөв байдлаас төлөв рүү шилжих шилжилт нь зарим урсгалын нөлөөн дор явагддаг (өргөдлийн урсгал, татгалзах урсгал). Хэрэв системийг шинэ төлөвт авчрах үйл явдлын бүх урсгал нь хамгийн энгийн Пуассон бол системд тохиолдох үйл явц Марков байх болно, учир нь хамгийн энгийн урсгал нь үр дагаварт хүргэхгүй: үүн дээр ирээдүй нь өнгөрсөн үеэс хамаарахгүй. .