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