ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
  
TIỂU LUẬN
MÔ PHỎNG NGẪU NHIÊN
Đề tài
ÁP DỤNG HỆ THỐNG CHỜ VỚI ĐỘ DÀI
HÀNG CHỜ HẠN CHẾ ĐỂ GIẢI QUYẾT
BÀI TOÁN DỊCH VỤ RỬA XE
Giáo viên hướng dẫn: PGS.TS. Trần Lộc Hùng
Học viên thực hiện: Nguyễn Thị Thuỷ
Lớp Cao học khoá 2008-2010
Chuyên ngành: Khoa học máy tính
Tiểu luận: Mô phỏng ngẫu nhiên
Sử dụng hệ thống chờ để giải quyết bài toán dịch vụ rửa xe
Huế, tháng 07/ 2009
-2-
Tiểu luận: Mô phỏng ngẫu nhiên
Sử dụng hệ thống chờ để giải quyết bài toán dịch vụ rửa xe
PHẦN MỞ ĐẦU
Bài toán phục vụ công cộng cho chúng ta cách nhìn một hệ thống ngẫu nhiên.
Chẳng hạn, tại sao một siêu thị với khá nhiều quầy thanh toán vẫn xảy ra tình trạng ùn
tắc vào thời điểm này và vắng tanh vào thời điểm khác. Trong rất nhiều trường hợp hệ
thống này gắn liền với hiện tượng xếp hàng chờ của các đối tượng cần phục vụ.
Đặc trưng quan trọng trong các hệ thống phục vụ công cộng là sự biến động của
các yếu tố cấu thành có tính ngẫu nhiên và đám đông.
Các mô hình này có nhiều ứng dụng trong thực tế, từ đơn giản đến phức tạp. Với
kiến thức đã học được trong môn học “Mô phỏng ngẫu nhiên”, tôi đã tìm hiểu hệ thống
chờ với độ dài hàng chờ hạn chế và thời gian chờ không hạn chế để giải quyết bài toán
dịch vụ rửa xe tại một cửa hàng.
Nội dung trình bày trong tiểu luận gồm:

a. Dòng yêu cầu đến hệ thống
Dòng các đối tượng hướng đến hệ thống nhằm thoã mãn một loại nhu cầu mà hệ
thống phục vụ có khả năng đáp ứng gọi là dòng yêu cầu.
Đặc trưng quan trọng của dòng yêu cầu là quy luật về sự xuất hiện các yêu cầu
theo thời gian. Một trong những dòng yêu cầu phổ biến là dòng tuân theo quy luật
Poisson và đặc biệt là dòng tuân theo quy luật Poisson dừng. Trong một số trường hợp
khi dòng yêu cầu ngẫu nhiên hình thành do số lớn các tác động ngẫu nhiên ta gọi là
dòng yêu cầu phân phối tổng quát.
b. Kênh phục vụ
Tập hợp một số điều kiện vật chất, con người, thông tin,… có chức năng thoả
mãn một loại yêu cầu nào đó gọi là kênh phục vụ.
Đặc trưng của kênh phục vụ là thời gian phục vụ một yêu cầu hoặc số yêu cầu có
thể phục vụ trong một đơn vị thời gian. Thời gian phục vụ một yêu cầu (còn gọi là thời
gian phục vụ) cũng là một biến ngẫu nhiên, tuân theo một quy luật phân phối xác suất
nào đó.
Một trong những quy luật phổ biến là quy luật chỉ số (hay phân phối mũ), với
hàm mật độ: f(t) = µe
-
µ
t
.
c. Dòng phục vụ
Là dòng các đối tượng đã được phục vụ đi ra khỏi hệ thống.
Quy luật phân phối xác suất của dòng phục vụ tuỳ thuộc quy luật phân phối của
thời gian phục vụ của các kênh. Nếu thời gian phục vụ tuân theo quy luật phân phối
mũ thì dòng phục vụ là dòng Poisson dừng và ngược lại.
d. Hàng chờ
Đối với một số hệ thống, tuỳ thuộc chế độ tiếp nhận yêu cầu và tính chất của các
-5-
Các kênh phục vụ

P
0
(t,∆t) + P
1
(t,∆t) = 1 – O(∆t). (O(∆t) là một vô cùng bé của ∆t)
b. Tính không hiệu quả
Một dòng yêu cầu có tính không hiệu quả nếu xác suất xuất hiện x yêu cầu trong
khoảng thời gian t đến t + ∆t không phụ thuộc vào việc trước thời điểm t đã có bao
nhiêu yêu cầu xuất hiện. Như vậy biến cố có x yêu cầu xuất hiện trong khoảng thời
gian t đến t + ∆t và biến cố x yêu cầu xuất hiện trong khoảng thời gian t đến t + ∆t với
điều kiện trước đó đã có k yêu cầu xuất hiện độc lập với nhau với mọi k, tức là:
P
x
(t,∆t) = P
x
(t,∆t/k yêu cầu đã xuất hiện) với mọi k.
Định lý: Dòng yêu cầu với hai tính chất không hậu quả và đơn nhất là dòng
Poisson, có xác suất xuất hiện x yêu cầu trong khoảng thời gian t đến t + ∆t được tính
theo công thức Poisson như sau:
!
),(
),(
),(
x
etta
ttP
ttax
x
∆−
∆

[(t+∆t)/(t,x)] là xác suất A xuất hiện i lần trong khoảng thời gian
(t,t+∆t) với điều kiện tính đến t, A đã xuất hiện x lần.
Do tính không hậu quả của dòng biến cố ta có: P
i
[(t+∆t)/(t,x)] = P
i
(t+∆t)
Tức (1) trở thành:
P
n
(t+∆t) = P
n-1
(t)P
1
(t+∆t) + P
n
(t)P
0
(t+∆t). (2)
Với giả thiết cường độ xuất hiện A là λ(t) ta có:
P
1
(t+∆t) = λ(t)∆t
P
0
(t+∆t) = 1 - λ(t)∆t
Thay vào (2) ta có: P
n
(t+∆t) = P
n-1

λ
(t)dt
Đặt a(t) = ∫-λ(t)dt, ta có: P
0
(t) = e
-a(t)+C

Ta thấy tại t = 0, P
0
(0) = 1 vì vậy hằng số C = 0
Cuối cùng ta có: P
0
(t) = e
-a(t)
(5)
Với n ≥ 1
)()()()(
)()(
1
ttPttP
t
tPttP
nn
nn
λλ
−=
∆
−∆+
−
Khi ∆t dần tới 0 ta có: P