TEORI ANTRIAN
Perkenalan
Teori antrian adalah cabang penting dari analisis sistem dan riset operasi. Ini kaya akan beragam aplikasi: dari tugas. terkait dengan operasi tersebut jaringan telepon, untuk organisasi produksi ilmiah. Teori ini digunakan ketika ada panggilan dan klien, sinyal dan produk yang diproduksi secara massal, serta ketika produk dilayani, diproses, dikirim.
Ide dan metode teori mengantri(TMO) menjadi semakin luas. Banyak permasalahan di bidang teknologi, ekonomi, militer, dan ilmu pengetahuan alam dapat diajukan dan diselesaikan melalui TMT.
Kemunculan TMO terutama disebabkan oleh masalah-masalah terapan telepon, yang disebabkan oleh jumlah besar dari sumber yang independen atau lemah (pelanggan pertukaran telepon), arus permintaan (panggilan) mempunyai sifat acak yang jelas. Osilasi acak (fluktuasi) di sekitar rata-rata tertentu dalam hal ini bukanlah akibat dari suatu penyimpangan dari norma, melainkan suatu pola yang melekat pada keseluruhan proses. Di sisi lain, stabilitas pertukaran telepon dan kemungkinan memperoleh data statistik yang baik menciptakan prasyarat untuk mengidentifikasi karakteristik utama yang melekat dalam proses layanan tertentu.
Untuk pertama kalinya, Danish A.K. memperhatikan hal ini dan melakukan penelitian. Erlang. Karya utamanya di bidang ini dimulai pada tahun 1908 - 1921. Sejak saat itu, minat terhadap masalah yang dikemukakan oleh Erlang telah meningkat pesat. Pada tahun 1927 - 1928 muncul karya Molina dan Frey, kemudian pada tahun 1930 - 1932 - karya menarik Pollacek, A.N. Kolmogorova, A.Ya. Khinchin.
Harus dikatakan bahwa masalah pertama TMT cukup sederhana dan memungkinkan diperolehnya ketergantungan analitis akhir. Oh, perkembangannya sejalan dengan peningkatan cakupan penerapan TMO, dan juga semakin rumitnya tugas-tugas yang dihadapinya. Ternyata masalah seperti panggilan telepon muncul di berbagai bidang penelitian: ilmu alam. dalam teknologi, transportasi, urusan militer, organisasi produksi, dll.
23. Sistem antrian
Di banyak bidang aktivitas praktis manusia, kita dihadapkan pada kebutuhan untuk tetap berada dalam kondisi antisipasi. Situasi serupa muncul dalam antrian di loket tiket, di bandara besar, ketika petugas pemeliharaan pesawat sedang menunggu izin lepas landas atau mendarat, di sentral telepon sambil menunggu saluran pelanggan bebas, di bengkel sambil menunggu perbaikan mesin. dan peralatan, di gudang organisasi pemasok dan distribusi sambil menunggu pembongkaran atau pemuatan kendaraan. Dalam semua kasus di atas, kita berurusan dengan produksi dan pelayanan massal. Teori antrian mempelajari situasi seperti itu.
Teori antrian– bidang matematika terapan yang berhubungan dengan analisis proses dalam produksi, jasa, dan sistem manajemen di mana peristiwa homogen diulang berkali-kali, misalnya, di perusahaan jasa konsumen; dalam sistem untuk menerima, memproses dan mengirimkan informasi; jalur produksi otomatis, dll.
Subyek teori antrian adalah membangun ketergantungan antara sifat aliran permintaan, jumlah saluran layanan, kinerja saluran individu dan layanan yang efektif untuk menemukan cara terbaik untuk mengelola proses-proses ini.
23.1. konsep asap
Dalam teori sistem antrian (QS), objek yang dilayani disebut dengan kebutuhan. Secara umum kebutuhan biasanya dipahami sebagai permintaan untuk memenuhi suatu kebutuhan, misalnya percakapan dengan pelanggan, mendaratkan pesawat, membeli tiket, menerima bahan dari gudang.
Alat yang memenuhi persyaratan disebut perangkat layanan atau saluran layanan . Misalnya, saluran komunikasi telepon, landasan pendaratan, tukang reparasi, kasir tiket, titik bongkar muat di pangkalan dan gudang.
Seperangkat perangkat servis serupa disebut sistem antrian . Sistem tersebut dapat berupa pertukaran telepon, lapangan terbang, kantor tiket, bengkel, gudang dan pangkalan organisasi pemasok dan penjualan, dll.
Tugas utama teori QS adalah mempelajari mode operasi sistem pelayanan dan mempelajari fenomena yang timbul selama proses pelayanan. Jadi, salah satu karakteristik sistem pelayanan adalah lamanya permintaan tetap berada dalam antrian. Tentunya, waktu ini dapat dikurangi dengan menambah jumlah perangkat servis. Namun, setiap perangkat tambahan memerlukan biaya material tertentu, dan waktu tidak aktif perangkat servis meningkat karena kurangnya persyaratan pemeliharaan, yang juga merupakan fenomena negatif. Akibatnya, dalam teori QS, muncul masalah optimasi: bagaimana mencapai tingkat layanan tertentu (pengurangan antrian maksimum atau hilangnya persyaratan) dengan biaya minimal terkait dengan waktu henti perangkat layanan.
Sumber. Sumber didefinisikan sebagai perangkat atau kumpulan dari mana permintaan memasuki sistem untuk dilayani. Suatu sumber disebut tak terhingga atau terhingga bergantung pada apakah sumber tersebut memuat persyaratan yang tak terhingga atau terhingga. Kami akan selalu berasumsi bahwa persyaratan pembangkitan sumber tidak ada habisnya. Misalnya, meskipun jumlah pelanggan suatu sentral telepon tertentu terbatas, kita berasumsi bahwa mereka merupakan sumber yang tidak terbatas.
Aliran masuk. Persyaratan yang datang dari sumber layanan membentuk aliran masuk. Persyaratan itu sendiri dapat dianggap sebagai permintaan untuk memenuhi suatu kebutuhan. Ada banyak contoh arus masuk. Ini adalah aliran informasi yang masuk ke komputer untuk diproses; alur permohonan pertukaran telepon otomatis; arus klien yang datang ke studio, dan pasien ke klinik, arus kapal yang tiba di pelabuhan; pesawat musuh dan rudal terbang ke sasaran, dll.
Sistem pelayanan. Sistem pelayanan dipahami sebagai seperangkat sarana teknis atau personel produksi (berbagai jenis instalasi, instrumen, perangkat, terowongan, landasan pacu, jalur komunikasi, tenaga penjualan, tim pekerja atau karyawan, kasir, dll) yang menjalankan fungsi pelayanan. Semua hal di atas, sebagaimana telah disebutkan, disatukan oleh satu nama “saluran layanan” (perangkat layanan). Komposisi sistem ditentukan oleh jumlah saluran (perangkat, saluran). Berdasarkan jumlah saluran, sistem dapat dibagi menjadi saluran tunggal dan multi saluran.
Aliran keluar. Aliran keluar adalah aliran permintaan yang meninggalkan sistem setelah diservis. Ini mungkin termasuk persyaratan yang meninggalkan sistem tanpa dilayani.
Arus masuk, berfungsinya sistem pelayanan sebagai hasil pelayanan, dan arus keluar tunduk pada gambaran kuantitatif. Untuk melakukan kajian matematis terhadap proses antrian, perlu didefinisikan secara lengkap sistem pelayanannya. Biasanya ini berarti:
- menentukan aliran masuk. Di sini yang kami maksud adalah intensitas rata-rata penerimaan persyaratan dan model statistik penerimaannya (yaitu, hukum distribusi momen penerimaan persyaratan ke dalam sistem);
- mengatur mekanisme layanan. Ini berarti menentukan kapan layanan dapat diterima, berapa banyak permintaan yang dapat dilayani sekaligus, dan berapa lama layanan tersebut bertahan. Properti terakhir biasanya dicirikan oleh distribusi statistik durasi layanan (hukum distribusi waktu layanan);
- penugasan disiplin pelayanan. Ini berarti menunjukkan metode dimana satu permintaan dipilih dari antrian (jika ada) untuk layanan. Dalam bentuknya yang paling sederhana, disiplin pelayanan adalah melayani permintaan sesuai urutan penerimaannya (prinsip adil), namun masih banyak kemungkinan lainnya.
Spesifikasi suatu sistem juga mengandaikan gambaran yang diketahui tentang interaksi antara bagian-bagian individualnya.
Ketika sistem sudah cukup terdefinisi, terdapat dasar untuk membangun model matematika. Jika suatu model matematika kurang lebih cukup mencerminkan sistem nyata, maka model tersebut memungkinkan seseorang memperoleh karakteristik utama dari berfungsinya sistem tersebut. Tentu saja, model ini sangat menyederhanakan situasi praktis, tetapi hal ini tidak mengurangi metode matematika teori antrian dan keadaannya tidak berbeda dengan keadaan di bidang matematika terapan lainnya.
Jenis sistem antrian
Tergantung pada bagaimana aplikasi ditangani jika semua saluran sibuk, ada:
QS dengan penolakan melayani aplikasi dan QS dengan menunggu.
Untuk QS yang gagal, biasanya permintaan yang menganggap semua saluran sibuk segera meninggalkan sistem.
Dalam QS dengan menunggu, permintaan yang menemukan semua saluran sibuk tidak meninggalkan sistem, namun dimasukkan ke dalam antrian dan dilayani ketika salah satu saluran menjadi bebas. Dalam QS yang antri, proses menunggu aplikasi dalam antrean mungkin memiliki batasan apa pun atau tidak. Dalam kasus terakhir, mereka mengatakan bahwa mereka berurusan dengan QS “murni” dengan harapan. Jika pembatasan dikenakan pada proses menunggu, maka QS disebut “sistem tipe campuran". Dalam sistem seperti itu, karena pembatasan yang diberlakukan, mungkin ada kasus ketika permintaan layanan ditolak, mis. QS tipe campuran juga menunjukkan tanda-tanda QS yang gagal.
Dalam sistem tipe campuran, pembatasan berikut dapat diberlakukan:
a) jumlah lamaran dalam antrian;
b) selama permohonan berada dalam antrian;
c) aktif waktu keseluruhan menemukan aplikasi di CMO.
Dalam teknologi REU, sistem QS tipe campuran paling sering ditemui.
Deskripsi matematis QS dengan kegagalan
Pertimbangkan sistem antrian yang mengalami kegagalan P saluran. Mari kita asumsikan bahwa aliran permintaan yang masuk ke QS adalah yang paling sederhana dan memiliki kepadatan l. Selain itu, kami berasumsi bahwa waktu untuk melayani permintaan didistribusikan menurut hukum eksponensial dengan parameter
Di mana M(Tob) - ekspektasi matematis dari waktu layanan permintaan.
Oleh karena itu, kepadatan distribusi waktu pelayanan
Untuk sistem yang sedang dipertimbangkan, hal ini dimungkinkan negara bagian berikut:
x 0- semua saluran gratis;
x 1 - satu saluran sedang sibuk;
x k -- sibuk k saluran;
x n -- semua orang sibuk P saluran.
Data status sistem layanan dapat dijelaskan persamaan diferensial Erlang. penyelesaiannya memungkinkan seseorang memperoleh rumus untuk menghitung probabilitas yang konstan untuk keadaan tunak. Rezim ini terjadi ketika t® ¥.
Koefisien ditentukan sebagai
Di mana M(Tob) - ekspektasi matematis waktu layanan untuk satu permintaan.
Rumus Erlang diperoleh untuk kasus distribusi waktu layanan secara eksponensial, tetapi juga berlaku berdasarkan hukum lain, selama alur permintaannya sederhana.
Kemungkinan suatu permintaan tidak dilayani didefinisikan sebagai
Q
Proporsi waktu rata-rata sistem layanan akan menganggur dapat ditentukan oleh probabilitas kondisi tersebut x 0 , itu.
P menganggur = p(x 0) = p 0
Contoh. Biarkan pergi ke area perbaikan peralatan teknologi perangkat berasal kepadatan sedang aku= 2 unit/jam. Waktu servis rata-rata untuk satu peralatan adalah 24 menit (0,4 jam). Aplikasi yang menganggap semua saluran sibuk ditolak layanannya.
Diperlukan untuk menentukan karakteristik QS dengan asumsi adanya satu tempat kerja. Selain itu, perlu diketahui bagaimana karakteristik QS berubah dengan diperkenalkannya tempat kerja kedua.
Larutan. Berdasarkan kondisi masalahnya, kami memiliki QS yang gagal. Kita asumsikan bahwa aliran aplikasi yang masuk ke QS adalah yang paling sederhana dengan kepadatan rata-rata l.
1. Hitung faktor beban saluran atau pengurangan kepadatan permintaan
2. Carilah karakteristik QS untuk jumlah saluran n = 1. Kemungkinan permintaan tidak dilayani:
Relatif keluaran Q akan menentukan caranya
q=1- P diperlukan = 1 – 0,44 = 0,56.
Akibatnya, sekitar 56% aplikasi yang diterima oleh CMO akan dilayani.
Kemungkinan downtime saluran hal 0
Teori QS dikhususkan untuk pengembangan metode analisis, desain dan organisasi rasional sistem yang berkaitan dengan berbagai bidang kegiatan, seperti komunikasi, Teknik Komputer, perdagangan, transportasi, urusan militer. Terlepas dari segala keragamannya, sistem di atas memiliki sejumlah ciri khas, yaitu.
- Sistem antrian (queuing system) adalah model sistem, di mana lamaran (persyaratan) diterima secara acak dari luar atau dalam. Mereka harus dilayani oleh sistem dengan satu atau lain cara. Durasi layanan seringkali acak.
- QS adalah keseluruhan porsi peralatan Dan personil dengan organisasi yang tepat dari proses layanan.
- Menetapkan QMS berarti mengaturnya struktur dan statistik karakteristik urutan permintaan yang diterima dan urutan pelayanannya.
- indikator yang mencirikan sistem secara keseluruhan: nomor N saluran layanan sibuk, jumlah layanan (λ B), layanan tertunda atau permohonan ditolak (λ C) per satuan waktu, dll.;
- karakteristik probabilistik: probabilitas bahwa permintaan akan dilayani ( P obs) atau menerima penolakan layanan ( P terbuka) bahwa semua perangkat gratis ( P 0) atau sejumlah tertentu terisi ( hal), kemungkinan antrian, dll.;
- indikator ekonomi: biaya kerugian yang berhubungan dengan keluarnya suatu aplikasi yang tidak dilayani karena satu dan lain hal dari sistem, dampak ekonomi yang diperoleh dari pelayanan aplikasi tersebut, dan lain-lain.
Saat mengerjakan pekerjaan rumah pekerjaan tes QS paling sederhana dipelajari. Ini adalah sistem loop terbuka; sumber aplikasi yang tidak ada habisnya tidak termasuk dalam sistem. Aliran masukan permintaan, aliran layanan, dan ekspektasi sistem ini adalah yang paling sederhana. Tidak ada prioritas. Sistem fase tunggal.
Sistem multi-saluran dengan kegagalan
Sistem ini terdiri dari satu node layanan yang berisi n saluran layanan, yang masing-masing hanya dapat melayani satu permintaan.Semua saluran layanan memiliki kinerja yang sama dan tidak dapat dibedakan untuk model sistem. Jika permintaan memasuki sistem dan menemukan setidaknya satu saluran kosong, permintaan tersebut segera mulai dilayani. Jika pada saat penerimaan aplikasi di sistem semua saluran sibuk, maka aplikasi tersebut membiarkan sistem tidak terlayani.
Sistem campuran
- Sistem dengan batasan berdasarkan panjang antrian
.
Terdiri dari perangkat penyimpanan (antrian) dan node layanan. Suatu aplikasi meninggalkan antrian dan keluar dari sistem jika sudah ada m aplikasi di penyimpanan pada saat aplikasi tersebut muncul (m adalah jumlah maksimum tempat dalam antrian). Jika permintaan telah memasuki sistem dan menemukan setidaknya satu saluran gratis, permintaan tersebut segera mulai dilayani. Jika pada saat aplikasi masuk ke sistem, semua saluran sedang sibuk, maka aplikasi tersebut tidak keluar dari sistem, melainkan mengambil tempat di antrian. Suatu aplikasi meninggalkan sistem tidak terlayani jika, pada saat memasuki sistem, semua saluran layanan dan semua tempat dalam antrian sudah terisi.
Untuk setiap sistem, disiplin antrian ditentukan. Ini adalah sistem aturan yang menentukan urutan kedatangan permintaan dari antrian ke node layanan. Jika semua permintaan dan saluran layanan sama, maka aturan “siapa yang datang lebih dulu dilayani lebih dulu” paling sering berlaku. - Sistem dengan batasan selama aplikasi berada dalam antrian.
Terdiri dari perangkat penyimpanan (antrian) dan node layanan. Berbeda dengan sistem sebelumnya, permintaan yang diterima di penyimpanan (antrian) hanya dapat menunggu layanan dimulai dalam waktu terbatas. Jadi(paling sering ini adalah variabel acak). Jika sudah waktunya Jadi telah kedaluwarsa, maka aplikasi meninggalkan antrian dan membiarkan sistem tidak terlayani.
Deskripsi matematis QS
QS dianggap sebagai beberapa sistem fisik dengan keadaan diskrit x 0, x 1, ..., x n, beroperasi di waktu terus menerus T. Jumlah negara bagian n dapat berhingga atau dapat dihitung (n → ∞). Sistem dapat berpindah dari satu keadaan x i (i= 1, 2, … , n) ke keadaan lain xj (j= 0, 1,... ,N) kapan saja T. Untuk menunjukkan aturan transisi tersebut, gunakan diagram yang disebut grafik keadaan. Untuk jenis sistem yang tercantum di atas, grafik keadaan membentuk rantai di mana setiap keadaan (kecuali yang ekstrim) dihubungkan secara langsung dan umpan balik dengan dua keadaan yang bertetangga. Ini diagramnya kematian dan reproduksi .Transisi dari satu negara bagian ke negara lain terjadi pada waktu yang acak. Mudah untuk berasumsi bahwa transisi ini terjadi sebagai akibat dari tindakan beberapa orang aliran(aliran permintaan masukan, penolakan permintaan layanan, alur pemulihan perangkat, dll.). Jika semua thread protozoa, maka aliran acak terjadi dalam sistem suatu proses dengan keadaan diskrit dan waktu kontinu akan bersifat Markovian .
Aliran acara adalah rangkaian peristiwa serupa yang terjadi pada saat-saat acak dalam waktu. Ini dapat dilihat sebagai rangkaian momen acak dalam waktu T 1 ,T 2 , ... terjadinya peristiwa.
Yang paling sederhana adalah aliran yang memiliki properti berikut:
- Hal biasa. Acara mengikuti satu per satu (kebalikan dari aliran, dimana acara mengikuti dalam kelompok).
- stasioneritas. Probabilitas terjadinya sejumlah kejadian tertentu dalam selang waktu tertentu T hanya bergantung pada panjang interval dan tidak bergantung pada letak interval tersebut pada sumbu waktu.
- Tidak ada efek samping. Untuk dua selang waktu yang tidak tumpang tindih τ 1 dan τ 2, banyaknya kejadian yang terjadi pada salah satu selang waktu tersebut tidak bergantung pada banyaknya kejadian yang terjadi pada selang waktu yang lain.
Markovsky peristiwa acak dijelaskan dengan biasa persamaan diferensial. Variabel di dalamnya adalah probabilitas keadaan R 0 (t), hal 1 (t),…,p n (t).
Untuk sangat momen besar waktu pengoperasian sistem (secara teoritis pada t → ∞) dalam sistem paling sederhana (sistem di mana semua aliran paling sederhana, dan grafiknya adalah skema kematian dan reproduksi) diamati stabil, atau tidak bergerak Modus operasi. Dalam mode ini, sistem akan mengubah statusnya, tetapi probabilitas status tersebut ( probabilitas akhir) r k, k= 1, 2 ,…, N, tidak bergantung pada waktu dan dapat dianggap sebagai waktu relatif rata-rata sistem tetap berada pada kondisi yang sesuai.
Saat meneliti operasi, sering kali kita menemukan sistem yang dirancang untuk digunakan kembali ketika memecahkan masalah serupa. Proses yang timbul dalam hal ini disebut proses layanan, dan sistem - sistem antrian (QS). Contoh sistem tersebut adalah sistem telepon, bengkel, kompleks komputer, kantor tiket, toko, penata rambut, dll.
Setiap SMO terdiri dari sejumlah tertentu unit layanan (perangkat, perangkat, titik, stasiun), yang akan kami hubungi saluran layanan. Saluran dapat berupa jalur komunikasi, titik kerja, komputer, penjual, dll. Berdasarkan jumlah salurannya, QS dibagi menjadi saluran tunggal Dan banyak saluran.
Lamaran biasanya diterima oleh CMO tidak secara teratur, tetapi secara acak, membentuk apa yang disebut aliran acak aplikasi (persyaratan). Pelayanan permintaan, secara umum, juga berlanjut untuk beberapa waktu acak. Sifat acak dari aliran permintaan dan waktu layanan mengarah pada fakta bahwa QS dimuat secara tidak merata: dalam beberapa periode waktu, jumlah yang sangat besar sejumlah besar permintaan (mereka mengantri atau membiarkan QS tidak terlayani); di periode lain, QS bekerja dengan beban kurang atau menganggur.
Pokok bahasan teori antrian adalah konstruksinya model matematika, menghubungkan kondisi operasi QS tertentu (jumlah saluran, produktivitasnya, sifat aliran permintaan, dll.) dengan indikator kinerja QS, menggambarkan kemampuannya untuk mengatasi aliran permintaan.
Sebagai Indikator kinerja QS digunakan: rata-rata jumlah lamaran yang dilayani per satuan waktu; rata-rata jumlah lamaran dalam antrian; waktu tunggu rata-rata untuk layanan; kemungkinan penolakan layanan tanpa menunggu; kemungkinan jumlah aplikasi dalam antrian akan melebihi nilai tertentu dan seterusnya.
QS dibagi menjadi dua tipe (kelas) utama: QS dengan kegagalan Dan QS dengan menunggu (antrian). Pada QS dengan penolakan, permohonan yang diterima pada saat semua saluran sedang sibuk menerima penolakan, keluar dari QS dan tidak ikut serta dalam proses pelayanan selanjutnya (misalnya permohonan untuk Percakapan telepon pada saat semua saluran sibuk, ia menerima penolakan dan membiarkan QS tidak terlayani). Dalam QS yang menunggu, permintaan yang datang pada saat semua saluran sedang sibuk tidak keluar, namun menjadi antrian untuk dilayani.
QS dengan ekspektasi dibagi menjadi jenis yang berbeda tergantung bagaimana antrian diatur: dengan panjang antrian terbatas atau tidak terbatas, dengan waktu tunggu terbatas, dll.
Untuk klasifikasi SMO penting Memiliki disiplin pelayanan, yang menentukan prosedur untuk memilih aplikasi dari antara yang diterima dan prosedur untuk mendistribusikannya di antara saluran gratis. Atas dasar ini, pelayanan suatu aplikasi dapat diatur menurut prinsip “yang pertama datang - yang pertama dilayani”, “yang terakhir datang - yang pertama dilayani” (pesanan ini dapat digunakan, misalnya, ketika mengambil produk dari gudang untuk diservis, karena yang terakhir seringkali lebih mudah diakses) atau layanan prioritas (bila permintaan yang paling penting dilayani terlebih dahulu). Prioritasnya dapat bersifat absolut, ketika permintaan yang lebih penting “menggantikan” permintaan reguler dari layanan (misalnya, dalam keadaan darurat, pekerjaan yang direncanakan dari kru perbaikan terganggu hingga keadaan darurat tersebut dihilangkan), atau relatif, ketika permintaan yang lebih penting hanya menerima antrian tempat “terbaik”.
Konsep proses acak Markov
Proses kerja QS adalah proses acak.
Di bawah proses acak (probabilistik atau stokastik). mengacu pada proses perubahan keadaan suatu sistem dari waktu ke waktu sesuai dengan hukum probabilistik.
Prosesnya disebut proses dengan keadaan diskrit, jika kemungkinan keadaannya dapat dicantumkan terlebih dahulu, dan transisi sistem dari satu keadaan ke keadaan lain terjadi secara instan (dalam lompatan). Prosesnya disebut proses waktu yang berkesinambungan, jika momen kemungkinan transisi sistem dari satu negara ke negara lain tidak ditetapkan sebelumnya, tetapi acak.
Proses operasi QS merupakan proses acak dengan keadaan diskrit dan waktu kontinu. Artinya keadaan QS berubah secara tiba-tiba pada saat-saat acak ketika beberapa peristiwa terjadi (misalnya kedatangan aplikasi baru, akhir layanan, dll.).
Analisis matematis dari operasi QS disederhanakan secara signifikan jika proses operasi ini adalah Markovian. Proses acak disebut Markovian atau proses acak tanpa konsekuensi, jika suatu saat karakteristik probabilistik dari proses di masa depan hanya bergantung pada keadaannya saat ini dan tidak bergantung pada kapan dan bagaimana sistem sampai pada keadaan ini.
Contoh proses Markov: sistem - meteran taksi. Keadaan sistem pada suatu saat ditandai dengan jumlah kilometer (sepuluh kilometer) yang ditempuh mobil hingga saat itu. Biarkan penghitung muncul saat ini. Probabilitas bahwa pada saat ini meteran akan menunjukkan jumlah kilometer tertentu (lebih tepatnya, jumlah rubel yang sesuai) bergantung pada , tetapi tidak bergantung pada titik waktu mana pembacaan meteran berubah sebelum momen tersebut .
Banyak proses yang secara kasar dapat dianggap Markovian. Misalnya proses bermain catur; sistem - sekelompok bidak catur. Keadaan sistem ditandai dengan jumlah bidak musuh yang tersisa di papan saat ini. Kemungkinan bahwa pada saat itu keuntungan materi akan berada di pihak salah satu lawan terutama bergantung pada keadaan sistem pada saat itu, dan bukan pada kapan dan dalam urutan apa bidak-bidak tersebut menghilang dari papan sebelum momen tersebut.
Dalam beberapa kasus, prasejarah dari proses yang sedang dipertimbangkan dapat diabaikan begitu saja dan model Markov dapat digunakan untuk mempelajarinya.
Saat menganalisis proses acak dengan keadaan diskrit, akan lebih mudah untuk menggunakan skema geometris - yang disebut grafik keadaan. Biasanya, keadaan sistem digambarkan dengan persegi panjang (lingkaran), dan kemungkinan transisi dari satu keadaan ke keadaan lain digambarkan dengan panah (busur berorientasi) yang menghubungkan keadaan-keadaan tersebut.
Contoh 1. Buatlah grafik keadaan dari proses acak berikut: perangkat terdiri dari dua node, yang masing-masing dapat gagal pada waktu yang acak, setelah itu Anda segera mulai memperbaiki node, yang berlanjut untuk waktu acak yang sebelumnya tidak diketahui.
Larutan. Kemungkinan status sistem: - kedua node beroperasi; - unit pertama sedang diperbaiki, unit kedua berfungsi; - unit kedua sedang diperbaiki, unit pertama berfungsi; - kedua unit sedang diperbaiki. Grafik sistem ditunjukkan pada Gambar. 1.
Panah yang diarahkan, misalnya, dari ke, berarti transisi sistem pada saat kegagalan node pertama, dari ke - transisi pada saat selesainya perbaikan node ini.
Tidak ada panah dari ke dan dari ke pada grafik. Hal ini dijelaskan oleh fakta bahwa kegagalan node diasumsikan tidak bergantung satu sama lain dan, misalnya, kemungkinan kegagalan dua node secara bersamaan (transisi dari ke) atau penyelesaian perbaikan dua node secara bersamaan (transisi dari ke ) dapat diabaikan.
Untuk deskripsi matematis dari proses acak Markov dengan keadaan diskrit dan waktu kontinu yang mengalir dalam QS, kita akan mengenal salah satu konsep penting teori probabilitas - konsep aliran peristiwa.
Aliran Acara
Di bawah aliran peristiwa dipahami sebagai rangkaian peristiwa homogen yang mengikuti satu demi satu pada saat-saat tertentu yang acak (misalnya, aliran panggilan di sentral telepon, aliran kegagalan komputer, aliran pelanggan, dll.).
Alirannya ditandai intensitas- frekuensi terjadinya peristiwa atau rata-rata jumlah peristiwa yang termasuk dalam QS per satuan waktu.
Alur peristiwa disebut reguler, jika peristiwa terjadi satu sama lain dalam selang waktu tertentu yang sama. Misalnya, aliran produk pada jalur perakitan di toko perakitan (dengan kecepatan konstan) adalah teratur.
Alur peristiwa disebut tidak bergerak, jika karakteristik probabilistiknya tidak bergantung pada waktu. Secara khusus, intensitas aliran stasioner adalah nilai konstan: . Misalnya, arus mobil di jalan raya kota tidak stasioner pada siang hari, namun arus ini dapat dianggap stasioner pada siang hari, misalnya pada jam-jam sibuk. Harap dicatat bahwa dalam kasus terakhir, jumlah sebenarnya mobil yang lewat per satuan waktu (misalnya, setiap menit) mungkin sangat berbeda satu sama lain, namun jumlah rata-ratanya akan konstan dan tidak bergantung pada waktu.
Alur peristiwa disebut mengalir tanpa efek samping, jika untuk dua periode waktu yang tidak tumpang tindih dan - jumlah kejadian yang terjadi pada salah satu periode tersebut tidak bergantung pada jumlah kejadian yang terjadi pada periode lainnya. Misalnya, arus penumpang yang memasuki kereta bawah tanah hampir tidak memiliki dampak apa pun. Dan, katakanlah, aliran pelanggan yang meninggalkan konter dengan pembelian sudah memiliki efek samping (jika hanya karena interval waktu antara masing-masing pelanggan tidak boleh kurang dari waktu layanan minimum untuk masing-masing pelanggan).
Alur peristiwa disebut biasa, jika peluang terjadinya dua peristiwa atau lebih dalam kurun waktu (dasar) yang kecil dapat diabaikan dibandingkan dengan peluang terjadinya satu peristiwa. Dengan kata lain, suatu aliran peristiwa dikatakan biasa jika peristiwa-peristiwa yang muncul di dalamnya secara tunggal dan tidak berkelompok. Misalnya arus kereta api yang mendekati suatu stasiun biasa saja, tetapi arus mobil tidak biasa.
Alur peristiwa disebut paling sederhana (atau Poisson stasioner), jika secara bersamaan stasioner, biasa saja dan tidak memiliki efek samping. Nama “paling sederhana” dijelaskan oleh fakta bahwa QS dengan aliran paling sederhana memiliki deskripsi matematis paling sederhana. Perhatikan bahwa aliran reguler bukanlah aliran yang “paling sederhana”, karena aliran ini memiliki efek samping: momen terjadinya peristiwa dalam aliran tersebut ditentukan secara ketat.
Aliran paling sederhana muncul sebagai batasan dalam teori proses acak secara alami seperti dalam teori probabilitas, distribusi normal muncul sebagai batasan jumlah variabel acak: ketika melapiskan (superposisi) sejumlah besar aliran independen, stasioner, dan biasa (intensitasnya sebanding satu sama lain), diperoleh aliran yang mendekati aliran paling sederhana dengan intensitas yang sama dengan jumlah intensitas aliran masuk, yaitu Mari kita pertimbangkan pada sumbu waktu (Gbr. 1) aliran peristiwa paling sederhana sebagai rangkaian titik acak yang tidak terbatas.
Dapat ditunjukkan bahwa untuk aliran yang paling sederhana, jumlah m peristiwa (titik) yang terjadi pada suatu jangka waktu yang berubah-ubah didistribusikan ke seluruh hukum Poisson
yang ekspektasi matematisnya variabel acak sama dengan variansnya: .
Secara khusus, probabilitas bahwa tidak ada peristiwa yang akan terjadi selama waktu tertentu adalah sama dengan
Mari kita cari distribusi interval waktu antara dua kejadian bertetangga yang berubah-ubah dari aliran paling sederhana.
Sesuai dengan (2), peluang tidak akan terjadinya kejadian-kejadian berikutnya dalam suatu jangka waktu adalah sama dengan
dan peluang kejadian sebaliknya, yaitu. fungsi distribusi variabel acak, ada
Kepadatan probabilitas suatu variabel acak adalah turunan dari fungsi distribusinya (Gbr. 3), yaitu.
Distribusi yang ditentukan oleh kepadatan probabilitas (5) atau fungsi distribusi (4) disebut indikatif(atau eksponensial). Jadi, interval waktu antara dua peristiwa sembarang yang bertetangga memiliki distribusi eksponensial, yang ekspektasi matematisnya sama dengan deviasi standar variabel acak.
dan sebaliknya sesuai dengan intensitas aliran.
Properti yang paling penting distribusi eksponensial (hanya melekat pada distribusi eksponensial) adalah sebagai berikut: jika suatu periode waktu yang didistribusikan menurut hukum eksponensial telah berlangsung selama beberapa waktu, maka hal ini sama sekali tidak mempengaruhi hukum distribusi sisa interval. : akan sama dengan hukum distribusi seluruh interval.
Dengan kata lain, untuk selang waktu antara dua kejadian tetangga yang berurutan dari suatu aliran yang berdistribusi eksponensial, informasi apa pun tentang berapa lama selang waktu tersebut berlangsung tidak mempengaruhi hukum distribusi bagian yang tersisa. Sifat hukum eksponensial ini, pada dasarnya, merupakan rumusan lain dari "tidak adanya efek samping" - sifat utama dari aliran paling sederhana.
Untuk aliran paling sederhana dengan intensitas, kemungkinan mengenai (Perhatikan bahwa rumus perkiraan ini, yang diperoleh dengan mengganti fungsi hanya dengan dua suku pertama dari pemuaiannya, semakin kecil rumusnya, semakin akurat).
Saat meneliti operasi, sering kali kita menemukan sistem yang dirancang untuk digunakan kembali ketika memecahkan masalah serupa. Proses yang timbul dalam hal ini disebut proses layanan, dan sistem - sistem antrian (QS). Contoh sistem tersebut adalah sistem telepon, bengkel, kompleks komputer, kantor tiket, toko, penata rambut, dll.
Setiap QS terdiri dari sejumlah unit layanan (instrumen, perangkat, titik, stasiun) tertentu, yang akan kita sebut saluran layanan. Saluran dapat berupa jalur komunikasi, titik kerja, komputer, penjual, dll. Berdasarkan jumlah salurannya, QS dibagi menjadi saluran tunggal Dan banyak saluran.
Lamaran biasanya diterima oleh CMO tidak secara teratur, tetapi secara acak, membentuk apa yang disebut aliran acak aplikasi (persyaratan). Pelayanan permintaan, secara umum, juga berlanjut untuk beberapa waktu acak. Sifat aliran aplikasi dan waktu layanan yang acak menyebabkan fakta bahwa QS dimuat secara tidak merata: dalam beberapa periode waktu, sejumlah besar aplikasi terakumulasi (mereka mengantri atau membiarkan QS tidak terlayani), di periode lain QS beroperasi dengan underload atau idle.
Pokok bahasan teori antrian adalah konstruksi model matematika yang menghubungkan kondisi operasi QS tertentu (jumlah saluran, produktivitasnya, sifat aliran permintaan, dll.) dengan indikator kinerja QS, yang menggambarkan kemampuannya untuk mengatasi aliran permintaan.
Sebagai Indikator kinerja QS digunakan: rata-rata jumlah lamaran yang dilayani per satuan waktu; rata-rata jumlah lamaran dalam antrian; waktu tunggu rata-rata untuk layanan; kemungkinan penolakan layanan tanpa menunggu; kemungkinan jumlah aplikasi dalam antrian akan melebihi nilai tertentu, dll.
QS dibagi menjadi dua tipe (kelas) utama: QS dengan kegagalan Dan QS dengan menunggu (antrian). Dalam QS dengan penolakan, aplikasi yang diterima pada saat semua saluran sibuk menerima penolakan, meninggalkan QS dan tidak berpartisipasi dalam proses layanan lebih lanjut (misalnya, permintaan percakapan telepon pada saat semua saluran sedang sibuk) sibuk, menerima penolakan dan membiarkan QS tidak terlayani). Dalam QS yang menunggu, permintaan yang datang pada saat semua saluran sedang sibuk tidak keluar, namun menjadi antrian untuk dilayani.
Antrian dengan menunggu dibagi menjadi beberapa jenis tergantung pada bagaimana antrian diatur: dengan panjang antrian terbatas atau tidak terbatas, dengan waktu tunggu terbatas, dll.
Untuk klasifikasi SMO itu penting disiplin pelayanan, yang menentukan prosedur untuk memilih aplikasi dari antara yang diterima dan prosedur untuk mendistribusikannya di antara saluran gratis. Atas dasar ini, pelayanan suatu aplikasi dapat diatur menurut prinsip “yang pertama datang - yang pertama dilayani”, “yang terakhir datang - yang pertama dilayani” (pesanan ini dapat digunakan, misalnya, ketika mengambil produk dari gudang untuk diservis, karena yang terakhir seringkali lebih mudah diakses) atau layanan prioritas (bila permintaan yang paling penting dilayani terlebih dahulu). Prioritasnya dapat bersifat absolut, ketika permintaan yang lebih penting “menggantikan” permintaan reguler dari layanan (misalnya, dalam keadaan darurat, pekerjaan yang direncanakan dari kru perbaikan terganggu hingga keadaan darurat tersebut dihilangkan), atau relatif, ketika permintaan yang lebih penting hanya menerima antrian tempat “terbaik”.
Konsep proses acak Markov
Proses kerja QS adalah proses acak.
Di bawah proses acak (probabilistik atau stokastik). mengacu pada proses perubahan keadaan suatu sistem dari waktu ke waktu sesuai dengan hukum probabilistik.
Prosesnya disebut proses dengan keadaan diskrit, jika memungkinkan S_1,S_2,\ltitik,S_n dapat didaftar terlebih dahulu, dan transisi sistem dari satu negara ke negara lain terjadi secara instan (dalam lompatan). Prosesnya disebut proses waktu yang berkesinambungan, jika momen kemungkinan transisi sistem dari satu negara ke negara lain tidak ditetapkan sebelumnya, tetapi acak.
Proses operasi QS merupakan proses acak dengan keadaan diskrit dan waktu kontinu. Ini berarti bahwa keadaan QS berubah secara tiba-tiba pada saat-saat acak ketika beberapa peristiwa terjadi (misalnya, kedatangan permintaan baru, berakhirnya layanan, dll.).
Analisis matematis dari operasi QS disederhanakan secara signifikan jika proses operasi ini adalah Markovian. Proses acak disebut Markovian atau proses acak tanpa konsekuensi, jika pada suatu saat t_0 karakteristik probabilistik dari proses di masa depan hanya bergantung pada keadaannya pada saat tertentu t_0 dan tidak bergantung pada kapan dan bagaimana sistem sampai pada keadaan ini.
Contoh proses Markov: sistem S adalah meteran taksi. Keadaan sistem pada saat t ditandai dengan jumlah kilometer (sepuluh kilometer) yang ditempuh mobil hingga saat ini. Biarkan penghitung menunjukkan S_0 pada waktu t_0. Probabilitas bahwa pada saat t>t_0 penghitung akan menunjukkan jumlah kilometer ini atau itu (lebih tepatnya, jumlah rubel yang sesuai) S_1 bergantung pada S_0, tetapi tidak bergantung pada titik waktu mana pembacaan penghitung berubah sebelum momen t_0.
Banyak proses yang secara kasar dapat dianggap Markovian. Misalnya proses bermain catur; sistem S adalah sekelompok bidak catur. Keadaan sistem ditandai dengan jumlah bidak musuh yang tersisa di papan pada waktu t_0. Probabilitas bahwa pada saat t>t_0 keunggulan materi akan berada di pihak salah satu lawan terutama bergantung pada keadaan sistem saat ini t_0, dan bukan pada kapan dan dalam urutan apa bidak-bidak tersebut menghilang dari papan. ke momen t_0 .
Dalam beberapa kasus, prasejarah dari proses yang sedang dipertimbangkan dapat diabaikan begitu saja dan model Markov dapat digunakan untuk mempelajarinya.
Saat menganalisis proses acak dengan keadaan diskrit, akan lebih mudah untuk menggunakan skema geometris - yang disebut grafik keadaan. Biasanya, keadaan sistem digambarkan dengan persegi panjang (lingkaran), dan kemungkinan transisi dari satu keadaan ke keadaan lain digambarkan dengan panah (busur berorientasi) yang menghubungkan keadaan-keadaan tersebut.
Contoh 1. Buatlah grafik keadaan dari proses acak berikut: perangkat S terdiri dari dua node, yang masing-masing dapat gagal pada waktu yang acak, setelah itu Anda segera mulai memperbaiki node, yang berlanjut untuk waktu acak yang tidak diketahui.
Larutan. Kemungkinan status sistem: S_0 - kedua node beroperasi; S_1 - unit pertama sedang diperbaiki, unit kedua berfungsi; S_2 - unit kedua sedang diperbaiki, unit pertama berfungsi; S_3 - kedua unit sedang diperbaiki. Grafik sistem ditunjukkan pada Gambar. 1.
Panah yang diarahkan, misalnya, dari S_0 ke S_1 berarti transisi sistem pada saat kegagalan node pertama, dari S_1 ke S_0 - transisi pada saat selesainya perbaikan node ini.
Grafik tidak memiliki panah dari S_0 ke S_3 dan dari S_1 ke S_2. Hal ini dijelaskan oleh fakta bahwa kegagalan node diasumsikan independen satu sama lain dan, misalnya, kemungkinan kegagalan dua node secara bersamaan (transisi dari S_0 ke S_3) atau penyelesaian perbaikan dua node secara bersamaan (transisi dari S_3 ke S_3) S_0) dapat diabaikan.
Untuk deskripsi matematis dari proses acak Markov dengan keadaan diskrit dan waktu kontinu yang mengalir dalam QS, kita akan mengenal salah satu konsep penting teori probabilitas - konsep aliran peristiwa.
Aliran Acara
Di bawah aliran peristiwa dipahami sebagai rangkaian peristiwa homogen yang mengikuti satu demi satu pada saat-saat tertentu yang acak (misalnya, aliran panggilan di sentral telepon, aliran kegagalan komputer, aliran pelanggan, dll.).
Alirannya ditandai intensitas\lambda - frekuensi terjadinya peristiwa atau jumlah rata-rata peristiwa yang memasuki QS per satuan waktu.
Alur peristiwa disebut reguler, jika peristiwa terjadi satu sama lain dalam selang waktu tertentu yang sama. Misalnya, aliran produk pada jalur perakitan di toko perakitan (dengan kecepatan konstan) adalah teratur.
Alur peristiwa disebut tidak bergerak, jika karakteristik probabilistiknya tidak bergantung pada waktu. Secara khusus, intensitas aliran stasioner adalah nilai konstan: \lambda(t)=\lambda. Misalnya, arus mobil di jalan raya kota tidak stasioner pada siang hari, namun arus ini dapat dianggap stasioner pada siang hari, misalnya pada jam-jam sibuk. Harap dicatat bahwa dalam kasus terakhir, jumlah sebenarnya mobil yang lewat per satuan waktu (misalnya, setiap menit) mungkin sangat berbeda satu sama lain, namun jumlah rata-ratanya akan konstan dan tidak bergantung pada waktu.
Alur peristiwa disebut mengalir tanpa efek samping, jika untuk dua periode waktu yang tidak tumpang tindih \tau_1 dan \tau_2 - jumlah kejadian yang terjadi pada salah satu periode tersebut tidak bergantung pada jumlah kejadian yang terjadi pada periode lainnya. Misalnya, arus penumpang yang memasuki kereta bawah tanah hampir tidak memiliki dampak apa pun. Dan, katakanlah, aliran pelanggan yang meninggalkan konter dengan pembelian sudah memiliki efek samping (jika hanya karena interval waktu antara masing-masing pelanggan tidak boleh kurang dari waktu layanan minimum untuk masing-masing pelanggan).
Alur peristiwa disebut biasa, jika peluang terjadinya dua peristiwa atau lebih dalam selang waktu kecil (dasar) \Delta t dapat diabaikan dibandingkan dengan peluang terjadinya satu peristiwa. Dengan kata lain, suatu aliran peristiwa dikatakan biasa jika peristiwa-peristiwa yang muncul di dalamnya secara tunggal dan tidak berkelompok. Misalnya arus kereta api yang mendekati suatu stasiun biasa saja, tetapi arus mobil tidak biasa.
Alur peristiwa disebut paling sederhana (atau Poisson stasioner), jika secara bersamaan stasioner, biasa saja dan tidak memiliki efek samping. Nama “paling sederhana” dijelaskan oleh fakta bahwa QS dengan aliran paling sederhana memiliki deskripsi matematis paling sederhana. Perhatikan bahwa aliran reguler bukanlah aliran yang “paling sederhana”, karena aliran ini memiliki efek samping: momen terjadinya peristiwa dalam aliran tersebut ditentukan secara ketat.
Aliran paling sederhana muncul sebagai batasan dalam teori proses acak secara alami seperti dalam teori probabilitas, distribusi normal muncul sebagai batasan jumlah variabel acak: dengan pengenaan (superposisi) sejumlah n aliran independen, stasioner, dan biasa dalam jumlah yang cukup besar (intensitasnya sebanding satu sama lain \lambda_i~(i=1,2,\ltitik,n) hasilnya adalah aliran mendekati aliran paling sederhana dengan intensitas \lambda sama dengan jumlah intensitas aliran masuk, yaitu \textstyle(\lambda=\jumlah\batas_(i=1)^(n)\lambda_i). Mari kita perhatikan pada sumbu waktu Ot (Gbr. 1) aliran peristiwa paling sederhana sebagai barisan titik acak yang tidak terbatas.
Dapat ditunjukkan bahwa untuk aliran paling sederhana, jumlah m peristiwa (titik) yang terjadi pada segmen waktu sembarang \tau didistribusikan ke seluruh hukum Poisson
P_(m)(\tau)= \frac((\lambda\tau)^m)(m\,e^{-\lambda\tau}, !}
yang ekspektasi matematisnya terhadap variabel acak sama dengan variansnya: a=\sigma^2=\lambda\tau.
Secara khusus, probabilitas bahwa tidak ada peristiwa yang akan terjadi selama waktu \tau (m=0) adalah sama dengan
P_0(\tau)=e^(-\lambda\tau).
Mari kita cari distribusi interval waktu T antara dua kejadian bertetangga dari aliran paling sederhana.
Sesuai dengan (2), peluang bahwa dalam jangka waktu t tidak akan terjadi kejadian-kejadian berikutnya adalah sama dengan
P(T\geqslant t)=e^(-\lambda t),
dan peluang terjadinya kejadian sebaliknya, yaitu. fungsi distribusi variabel acak T, adalah
F(t)=P(T Kepadatan probabilitas suatu variabel acak adalah turunan dari fungsi distribusinya (Gbr. 3), yaitu. \varphi(t)=F"(t)=\lambda e^(-\lambda t). Distribusi yang ditentukan oleh kepadatan probabilitas (5) atau fungsi distribusi (4) disebut indikatif(atau eksponensial). Jadi, interval waktu antara dua peristiwa sembarang yang bertetangga memiliki distribusi eksponensial, yang ekspektasi matematisnya sama dengan deviasi standar variabel acak. A=\sigma=\frac(1)(\lambda) Begitu pula sebaliknya menurut intensitas aliran \lambda. Sifat terpenting dari distribusi eksponensial (hanya melekat pada distribusi eksponensial) adalah sebagai berikut: jika periode waktu yang didistribusikan menurut hukum eksponensial telah berlangsung selama beberapa waktu \tau, maka hal ini tidak mempengaruhi distribusi sama sekali hukum bagian sisa interval (T-\tau): sama dengan hukum distribusi seluruh interval T. Dengan kata lain, untuk selang waktu T antara dua kejadian tetangga yang berurutan dari suatu aliran yang berdistribusi eksponensial, informasi apa pun tentang berapa lama selang waktu tersebut berlangsung tidak mempengaruhi hukum distribusi bagian sisanya. Sifat hukum eksponensial ini, pada dasarnya, merupakan rumusan lain dari "tidak adanya efek samping" - sifat utama dari aliran paling sederhana. Untuk aliran paling sederhana dengan intensitas \lambda, kemungkinan mengenai dasar (kecil) interval waktu \Delta t dari setidaknya satu kejadian aliran sama dengan (4) P_(\Delta t)= P(T<\Delta t)= 1-e^{-\lambda\Delta t}\approx\lambda\Delta t.
(Perhatikan bahwa rumus perkiraan ini diperoleh dengan mengganti fungsi e^(-\lambda\Delta t) hanya dua suku pertama dari perluasan pangkat \Delta t, semakin akurat semakin kecil \Delta t).
Lanjutkan ke bagian selanjutnya
Persamaan Kolmogorov. Batasi probabilitas negara bagian Javascript dinonaktifkan di browser Anda.
Untuk melakukan penghitungan, Anda harus mengaktifkan kontrol ActiveX!