Luận văn Thạc sĩ Khoa học: Một số mô hình xếp hàng và ứng dụng

́<br /> ĐẠI HỌC QUÔC GIA HÀ NỘI<br /> ̀<br /> TRƢƠNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN<br /> <br /> -----------------------<br /> <br /> NGUYỄN THỊ HÀ<br /> <br /> MỘT SỐ MÔ HÌNH XẾP HÀNG VÀ ỨNG DỤNG<br /> Chuyên ngành: Lý thuyết xác xuất và thống kê toán học<br /> Mã số: 604601106<br /> <br /> LUẬN VĂN THẠC SĨ KHOA HỌC<br /> <br /> NGƢỜI HƢỚNG DẪN: Ts. Trần Mạnh Cƣờng<br /> <br /> Hà Nội - 2016<br /> 1<br /> <br /> Mục Lục<br /> MỞ ĐẦU ....................................................................................................... Error! Bookmark not defined.<br /> CHƢƠNG 1 ................................................................................................... Error! Bookmark not defined.<br /> KIẾN THỨC CHUẨN BỊ .............................................................................. Error! Bookmark not defined.<br /> 1.1<br /> <br /> Phân bố Poisson và phân bố mũ..................................................... Error! Bookmark not defined.<br /> <br /> 1.1.1 Phân bố Poisson ............................................................................ Error! Bookmark not defined.<br /> 1.1.2 Phân bố mũ: .................................................................................. Error! Bookmark not defined.<br /> 1.2. Xích Markov ....................................................................................... Error! Bookmark not defined.<br /> 1.2.1. Phân loại trạng thái xích Markov ................................................. Error! Bookmark not defined.<br /> 1.3. Quá trình Markov ................................................................................ Error! Bookmark not defined.<br /> 1.3.1. Trƣờng hợp không gian trạng thái hữu hạn.................................. Error! Bookmark not defined.<br /> 1.3.2. Trƣờng hợp không gian trạng thái vô hạn đếm đƣợc ................... Error! Bookmark not defined.<br /> CHƢƠNG 2: .................................................................................................. Error! Bookmark not defined.<br /> MỘT SỐ MÔ HÌNH XẾP HÀNG ................................................................. Error! Bookmark not defined.<br /> 2.1 Khái niệm và phân loại quá trình xếp hàng ......................................... Error! Bookmark not defined.<br /> 2.1.1 Khái niệm quá trình xếp hàng ....................................................... Error! Bookmark not defined.<br /> 2.1.2 Các yếu tố cơ bản của hàng đợi .................................................... Error! Bookmark not defined.<br /> a. Bố trí vật lí của hệ thống .................................................................... Error! Bookmark not defined.<br /> b. Nguyên tắc phục vụ............................................................................ Error! Bookmark not defined.<br /> c. Các phân phối xác suất của các dòng tín hiệu, dòng phục vụ ............ Error! Bookmark not defined.<br /> 2.1.3 Phân tích hàng đợi......................................................................... Error! Bookmark not defined.<br /> 2.1.4 Phân loại Kendall .......................................................................... Error! Bookmark not defined.<br /> 2.1.5 Mục tiêu của phân tích hàng đợi ................................................... Error! Bookmark not defined.<br /> 2.2 Một số mô hình xếp hàng cơ bản ......................................................... Error! Bookmark not defined.<br /> 2.2.1 Mô hình xếp hàng sinh – chết tổng quát ....................................... Error! Bookmark not defined.<br /> 2.2.2 Mô hình hàng đợi M/M/1.............................................................. Error! Bookmark not defined.<br /> a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined.<br /> b. Thời gian khách hàng chờ đợi............................................................ Error! Bookmark not defined.<br /> c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined.<br /> d. Quá trình dời đi .................................................................................. Error! Bookmark not defined.<br /> e. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined.<br /> 2.2.3. Mô hình hàng đợi M/M/s ............................................................. Error! Bookmark not defined.<br /> a. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined.<br /> 2<br /> <br /> b. Thời gian bận rộn ............................................................................... Error! Bookmark not defined.<br /> c. Quá trình dời đi .................................................................................. Error! Bookmark not defined.<br /> d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined.<br /> 2.2.4. Mô hình hàng đợi hữu hạn M/M/s/K ........................................... Error! Bookmark not defined.<br /> a. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined.<br /> 2.2.5. Mô hình hàng đợi M/G/1 ............................................................. Error! Bookmark not defined.<br /> a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined.<br /> b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined.<br /> c. Thời gian bận rộn ............................................................................... Error! Bookmark not defined.<br /> d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined.<br /> 2.2.6. Mô hình hàng đợi G/M/1 ............................................................. Error! Bookmark not defined.<br /> a. Phân bố giới hạn ................................................................................. Error! Bookmark not defined.<br /> b. Thời gian chờ đợi ............................................................................... Error! Bookmark not defined.<br /> c. Chu kỳ bận rộn ................................................................................... Error! Bookmark not defined.<br /> d. Bài toán ví dụ ..................................................................................... Error! Bookmark not defined.<br /> CHƢƠNG 3: .................................................................................................. Error! Bookmark not defined.<br /> ỨNG DỤNG .................................................................................................. Error! Bookmark not defined.<br /> 3.1 Mô phỏng một số mô hình xếp hàng bằng Matlab............................... Error! Bookmark not defined.<br /> 3.1.1 Mô phỏng hàng đợi M/M/1 ........................................................... Error! Bookmark not defined.<br /> 3.2 Ứng dụng của mô hình xếp hàng trong bài toán ra quyết định. ........... Error! Bookmark not defined.<br /> a) Xét ba bài toán sau: ............................................................................ Error! Bookmark not defined.<br /> b) Hàm giá: ............................................................................................ Error! Bookmark not defined.<br /> KẾT LUẬN.................................................................................................... Error! Bookmark not defined.<br /> TÀI LIỆU THAM KHẢO ............................................................................. Error! Bookmark not defined.<br /> <br /> 3<br /> <br /> MỞ ĐẦU<br /> Lý thuyết xếp hàng đã đƣợc nghiên cứu và ứng dụng rộng rãi trên thế giới trong<br /> nhiều lĩnh vực ngành nghề khác nhau nhƣ bƣu chính viễn thông, hàng không,<br /> đƣờng sắt, kiểm soát lƣu lƣợng giao thông, đánh giá hiệu năng hệ thống máy tính,<br /> y tế và chăm sóc sức khỏe, không lƣu, bán vé …<br /> Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài<br /> nguyên, phải chờ để đƣợc phục vụ và đôi khi bị từ chối phục vụ. Lý thuyết quá<br /> trình xếp hàng (queueing process) xác định và tìm các phƣơng án tối ƣu để hệ<br /> thống phục vụ là tốt nhất.<br /> Trong nửa đầu của thế kỷ 20 lý thuyết xếp hàng đã đƣợc ứng dụng để nghiên<br /> cứu thời đợi trong các hệ thống điện thoại. Ngày nay lý thuyết xếp hàng còn có<br /> nhiều ứng dụng trong các lĩnh vực khác nhau nhƣ trong mạng máy tính, trong việc<br /> quản lý xí nghiệp, quản lý giao thông và trong các hệ phục vụ khác … Ngoài ra lý<br /> thuyết xếp hàng cũng còn là cơ sở toán học để nghiên cứu và ứng dụng trong nhiều<br /> bài toán kinh tế nhƣ đầu tƣ, kiểm kê, rủi ro của bảo hiểm, thị trƣờng chứng khoán<br /> … Chuỗi Markov là quá trình xếp hàng với thời gian rời rạc đã đƣợc xem xét trong<br /> giáo trình xác suất thống kê. Quá trình sinh tử cũng là quá trình xếp hàng, trong đó<br /> sinh biểu thị sự đến và tử biểu thị sự rời hàng của hệ thống.<br /> Đối với lý thuyết xếp hàng ta quan tâm đến các số đo hiệu năng, đó là các giá trị<br /> trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình<br /> của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của<br /> hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống). Để<br /> tính các đại lƣợng này ta có thể sử dụng phƣơng pháp giải phƣơng trình tích phân<br /> dạng Wiener – Hopf hoặc phƣơng pháp khảo sát chuỗi Markov nhúng. Từ đó suy<br /> ra các công thức tính các phân bố ổn định cho các loại hàng M/M/k, M/M/k/N;<br /> Công thức tổng quát tính các giá trị trung bình này cho các hàng G/G/1 và công<br /> thức cụ thể cho các hàng đặc biệt M/M/1, M/D/1 và M/