ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC 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 THẠC SĨ KHOA HỌC

NGƢỜI HƢỚNG DẪN: Ts. Trần Mạnh Cƣờng

Hà Nội - 2016
1


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.

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.

3


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é …



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!

5


CHƢƠNG 1
KIẾN THỨC CHUẨN BỊ
Trong chƣơng này em xin trình bày về một sốphân bốxác suất liên quan là
phân bố Poisson, phân bố mũvà một số định nghĩa, định lý về xích Markov gồm
hai trƣờng hợp là không gian trạng thái hữu hạn và không gian trạng thái vô hạn
đếm đƣợc để chuẩn bị kiến thức cho các chƣơng tiếp theo của khóa luận.
1.1 Phân bố Poisson và phân bố mũ
1.1.1 Phân bố Poisson
Định nghĩa.Biến ngẫu nhiên rời rạc X nhận các giá trị từ 0, 1, 2, … gọi là phân

=λ

Do đó, chúng ta có thể viết: X ~ Poisson (µ).
Mô hình Poisson:
Giả sử chúng ta quan tâm đến số lần xảy ra của một sự kiện A trong một khoảng
thời gian hoặc không gian liên tục có chiều dài w; với điều kiện là số lần xảy ra
trong những khoảng không giao nhau là độc lập nhau, và xác suất xuất hiện A
nhiều hơn một lần trong khoảng đó là rất bé. Hơn nữa, “cƣờng độ” xuất hiện A là
không thay đổi, tức là số lần xuất hiện trung bình của A trong một khoảng chỉ phụ
thuộc vào độ dài của khoảng đó.
Với các điều kiện trên, nếu gọi X là BNN chỉ số lần xuất hiện A trong một khoảng
chiều dài w thì ngƣời ta chứng minh đƣợc rằng X tuân theo luật phân phối Poisson
với tham số λ = mw, trong đó m là một hằng số dƣơng chỉ “cƣờng độ” xuất hiện
của A.
6


Thí dụ, số cuộc điện thoại gọi đến trong một phút tại một trạm nào đó; sốlỗi trên
một trang giấy trong một quyển sách dầy; số đơn đặt hàng gửi tới một cơ sở trong
một tháng, …
Biến ngẫu nhiên chỉ số lần xuất hiện nêu trên đã đƣợc nhà toán học Simeon D.
Poisson nghiên cứu và hình thành phân phối Poisson.
Ngoài ra, phân phối Poisson còn đƣợc dùng để tính xấp xỉ phân phối nhịthức
B(n;p) khi n lớn và p khá gần 0 hoặc gần 1.
Định lý Poisson.
Giả sử trong một dãy n phép thử độc lập, một biến cố A xuất hiện với xác suất 𝑝𝑛
trong mỗi phép thử. Nếu khi 𝑛 → ∞ mà 𝑝𝑛 → 0 sao cho 𝑛. 𝑝𝑛 = 𝜆 (λ là một
hằng số dƣơng) thì với mọi 𝑘 ∈ {0,1,2, … , 𝑛}, chúng ta có:
lim


đƣợc hỗ trợ dựa trên khoảng [0; ∞).
Nếu một biến ngẫu nhiên X có phân phối này, ta viết:
𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆).
Đặc tả:
7


Một cách khác để định nghĩa hàm mật độ xác suất của một phân phối mũ nhƣ
sau:
1 −𝑥/𝜆
𝑓 𝑥, 𝜆 = 𝜆 𝑒
0

,𝑥 ≥ 0
,𝑥 < 0

Trong đó 𝜆 > 0 là một tham số của phân bố và có thể đƣợc coi là nghịch đảo
của tham số tỉ lệ đƣợc định nghĩa ở trên. Trong đặc tả, λ là một tham số sống sót
theo nghĩa: nếu một biến ngẫu nhiên X là khoảng thời gian mà một hệthống sinh
học hoặc cơ học M cho trƣớc sống sót đƣợc và 𝑋~𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 (𝜆)thì 𝐸 𝑋 = 𝜆.
Nghĩa là khoảng thời gian sống sót kì vọng của M là λ đơn vị thời gian.
Tính chất:
+ Giá trị trung bình và phương sai:
Giá trị trung bình hay giá trị kì vọng của một biến ngẫu nhiên phân phối mũ X với
tham số tỉ lệ λ đƣợc cho bởi công thức:
𝐸𝑋 =
Phƣơng sai của X là:

1
𝜆

phát biểu dƣới dạng: Nếu biết trạng thái hiện tại của hệ thì quá khứ và tƣơng lai
độc lập với nhau.
Giả sử 𝑃 𝑋𝑚 +𝑛 = 𝑗/𝑋𝑚 = 𝑖 là xác suất để xích tại thời điểm m ở trạng thái i sau n
bƣớc, tại thời điểm m + n chuyển sang trạng thái j. Đây là một con số nói chung
phụ thuộc vào i, j, m, n. Nếu đại lƣợng này không phụ thuộc m ta nói xích là thuần
nhất. Ký hiệu:
𝑃𝑖𝑗 = 𝑃 𝑋𝑛 +1 = 𝑗 /𝑋𝑛 = 1 ,
𝑃𝑖𝑗 𝑛 = 𝑃 𝑋𝑚 +𝑛 = 𝑗/𝑋𝑚 = 𝑖 .
Ta gọi (𝑃𝑖𝑗 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau một bƣớc hay xác suất chuyển còn
(𝑃𝑖𝑗 𝑛 , 𝑖, 𝑗 ∈ 𝐸) là xác suất chuyển sau n bƣớc. Chú ý rằng:
𝑗 ∈𝐸 𝑃𝑖𝑗

= 1,

𝑛 = 1.

𝑗 ∈𝐸 𝑃𝑖𝑗

Phân bố của X0 đƣợc gọi là phân bố ban đầu. Ta ký hiệu 𝑢𝑖 = 𝑃(𝑋0 = 𝑖).
Định lý 1.2.1.Phân bố đồng thời của (X0, X1, ..., Xn) được hoàn toàn xác định từ
phân bố ban đầu và xác suất chuyển. Cụ thể ta có:
𝑃 𝑋0 = 𝑖0 , 𝑋1 = 𝑖1 , … , 𝑋𝑛 = 𝑖𝑛 = 𝑢𝑖0 𝑃𝑖0 𝑖1 … 𝑃𝑖𝑛 −1 𝑖𝑛 .
Nhƣ vậy phân bố đồng thời của 𝑋0 , … , 𝑋𝑛 đƣợc xác định bởi phân bố ban đầu
và xác suất chuyển.
Định lý 1.2.2.(Phương trình C - K (Chapman-Kolmogorov)):
𝑃𝑖𝑗 (n + m) =

𝑘 ∈𝐸 𝑃𝑖𝑘

9

Giới hạn này không phụ thuộc i ∈ E. khi đó:
• 1.

𝑗 ∈𝐸 𝜋𝑗

≤ 1 và πj =

𝑖 ∈𝐸 𝜋𝑖 𝑃𝑖𝑗 .

• 2. Hoặc πj = 0 với mọi j ∈ E, hoặc

𝑗 ∈𝐸 𝜋𝑗 =

10

1.


• 3. Nếu 𝑗 ∈𝐸 𝜋𝑗 = 1 thì U = (π1, π2, ...) là phân bố dừng và phân bố dừng là duy
nhất. Nếu πj = 0 với mọi j ∈ E thì phân bố dừng không tồn tại.
Ý nghĩa của phân bố giới hạn là nhƣ sau: Gọi 𝑢𝑖 (𝑛) = 𝑃(𝑋𝑛 = 𝑖). Ký hiệu
vector 𝑈(𝑛) = (𝑢1 (𝑛), 𝑢2 (𝑛), . . . )là vector hàng d - chiều mô tả phân bố của 𝑋𝑛 .
Ta có:
P(Xn = j) =

𝑗 ∈𝐸 𝑃 (X0

= i)𝑃𝑖𝑗 (n).

Do đó:

11


Định nghĩa 1.2.4.Ta nói rằng trạng thái i đến được trạng thái j và ký hiệu là
𝑖 → 𝑗 nếu tồn tại 𝑛 ≥ 0 sao cho 𝑃𝑖𝑗 (𝑛) > 0.
(Ta quy ước 𝑃𝑖𝑖 0 = 1, 𝑃𝑖𝑗 (0) = 0 nếu(i ≠ j)).
Hai trạng thái i và j được gọi là liên lạc được nếu 𝑖 → 𝑗và 𝑗 → 𝑖. Trong trường
hợp đó ta viết 𝑖 ↔ 𝑗.
Định nghĩa 1.2.5.Xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ là
liên lạc được. Có nghĩa là theo cách phân lớp trên thì E không thể phân hoạch
thành các lớp con nhỏ hơn.
Định nghĩa 1.1.6.Ký hiệu 𝑓𝑖𝑖 𝑛 là xác suất để hệ xuất phát từ i lần đầu tiên quay
lại i ở thời diểm n. Nghĩa là:
𝑓𝑖𝑖 (n) = P(Xn = i, 𝑋𝑛−1 ≠ i, ..., 𝑋1 ≠ i|X0 = i)
và ký hiệu:
𝑓𝑖𝑖 ∗ =

∞
𝑛=1 𝑓𝑖𝑖

(𝑛).

Định lý 1.2.6.Trạng thái i là hồi quy khi và chỉ khi:
∞
𝑛=1 𝑃𝑖𝑖 (𝑛)=

∞.

Định lý 1.2.7.Nếu i ↔ j và j hồi quy thì i hồi quy.
Chứng minh:

lim𝑛→ ∞ 𝑃𝑖𝑗 = 0
và xích không tồn tại phân bố dừng.
Định lý 1.2.10.Cho (𝑋𝑛 ) là xích tối giản hồi quy không có chu kỳ. Khi đó với mọi i,
j ta có:
lim𝑛→ ∞ 𝑃𝑖𝑗 (n) =

1
𝜇𝑗

ở đó:
µ𝑗 =

∞
𝑘=1 𝑘𝑓𝑗𝑗

(k).

Định nghĩa 1.2.7.Trạng thái hồi quy i được gọi là trạng thái hồi quy dương nếu
𝜇𝑖 < ∞ và được gọi là trạng thái hồi quy không nếu µ𝑖 = ∞.
Định lý 1.2.11.Giả sử 𝑖 → 𝑗. Nếu i hồi quy dương thì j hồi quy dương. Nếu i hồi
quy không thì j hồi quy không.
Định lý 1.2.12.Giả sử (𝑋𝑛 ) là xích tối giản không có chu kỳ với không gian trạng
thái đếm được E. Khi đó sẽ xảy ra một trong ba khả năng sau đây:
• 1)Mọi trạng thái là không hồi quy. Khi đó với mọi i, j ta có:
𝑙𝑖𝑚𝑛→ ∞ 𝑃𝑖𝑗 (n) = 0.
Xích không có phân bố dừng.
• 2) Mọi trạng thái là hồi quy không. Khi đó với mọi i, j ta có:
𝑙𝑖𝑚𝑛→ ∞ 𝑃𝑖𝑗 = 0.
Xích không có phân bố dừng.
• 3) Mọi trạng thái là hồi quy dương. Khi đó với mọi i, j, ta có:


∞
𝑗 =1 𝜋𝑗

≤ 1,

b) 𝜋𝑗 =

∞
𝑖=1 𝜋𝑖 𝑃𝑖𝑗 .

Định lý 1.2.15.Cho (𝑋𝑛 ) là xích Markov tối giản. Khi đó:
• 1. Nếu E hữu hạn có d phần tử thì (𝜋1 , . . . , 𝜋𝑑 ) là phân bố dừng duy nhất.
• 2. Chỉ có các khả năng sau:
a) Mọi trạng thái của E là không hồi quy
b) Mọi trạng thái của E là hồi quy không
c) Mọi trạng thái của E là hồi quy dương.
• 3. Nếu E là vô hạn đếm được thì xích có phân bố dừng khi và chỉ khi mọi
trạng thát của E là hồi quy dương. Trong trường hợp này phân bố dừng là duy
nhất.

1.3. Quá trình Markov
14


Xét họ các ĐLNN rời rạc (𝑋𝑡 ), t ≥ 0 với tập chỉ số t là các số thực không âm
𝑡 ∈ [0, ∞). Ký hiệu 𝐸 = 𝑋𝑡 Ω là tập giá trị của 𝑋𝑡 . Khi đó E là một tập hữu hạn
hay đếm đƣợc, các phần tử của nó đƣợc ký hiệu 𝑙à 𝑖, 𝑗, 𝑘. . .. Ta gọi (𝑋𝑡 ) là một quá
trình ngẫu nhiên với không gian trạng thái E .
Định nghĩa 1.3.1. Ta nói rằng (𝑋𝑡 ) là một quá trình Markov nếu với mọi


P(𝑋𝑡 1 = i1, ..., 𝑋𝑡 𝑛 = in) =
=

𝑖 ∈𝐸 𝑢𝑖 𝑃𝑖𝑖 1

𝑡1 𝑃𝑖1 𝑖2 𝑡2 − 𝑡1 … 𝑃𝑖𝑛 −1 𝑖𝑛 (𝑡𝑛 − 𝑡𝑛 −1 ).

Định lý 1.3.2.( Phương trình Chap - Kolmogorov):
𝑃𝑖𝑗 (t + s) =

𝑘 ∈𝐸 𝑃𝑖𝑘 (𝑡)𝑃𝑘𝑗 (𝑠)

.

1.3.1. Trƣờng hợp không gian trạng thái hữu hạn
Giả sử E = {1, 2,..., d}. Khi đó từ phƣơng trình C - K P(t), t > 0 là một họ các ma
trận thoả mãn đẳng thức sau:
𝑃(𝑡 + 𝑠) = 𝑃(𝑡)𝑃(𝑠).
Nói cách khác họ (P(t), t > 0) lập thành một nửa nhóm các ma trận. Từ nay về sau
ta sẽ luôn giả thiết thêm rằng:
1.𝑃𝑖𝑗 (0) = δij.
2.lim𝑛→ ∞ 𝑃𝑖𝑗 (𝑡)= δij.
Ở đây 𝛿𝑖𝑗 là ký hiệu Kronecke:
δij =

1
0

𝑘𝑕𝑖 𝑖 = 𝑗

(1.3.2)


với𝑎𝑖𝑗 là cƣờng độ chuyển từ trạng thái i sang trạng thái j và 𝑎𝑖 là cƣờng độ thoát
khỏi trạng thái i của hệ.
Phƣơng trình (1.3.1) gọi là phƣơng trình thuận và phƣơng trình (1.3.2) gọi là
phƣơng trình ngƣợc Kolmogorov.
Định lý 1.3.5.Cho quá trình Markov tối giản (𝑋𝑡 ) với không gian trạng thái E = 1,
2,..., d hữu hạn và ma trận xác suất chuyểnP(t) = 𝑃𝑖𝑗 (t). Khi đó với mỗi 𝑖, 𝑗 ∈ 𝐸
tồn tại giới hạn hữu hạn:
𝑙𝑖𝑚 𝑃𝑖𝑗 𝑡 = 𝜋𝑗

𝑡→ ∞

chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó 𝜋 = (𝜋1 , 𝜋2 , . . . , 𝜋𝑑 ) là phân bố
xác suất duy nhất thoả mãn phương trình:
𝜋 = 𝜋𝑃(𝑡), ∀𝑡 > 0.
1.3.2. Trƣờng hợp không gian trạng thái vô hạn đếm đƣợc
Định lý 1.3.6.
(1)Với mọi i ≠ j, giới hạn:
𝑃𝑖𝑗 (𝑡)
= 𝑎𝑖𝑗
𝑡→ ∞
𝑡

𝑃𝑖𝑗 ′ (0) = lim
luôn tồn tại hữu hạn.
(2)Với mỗi i giới hạn:
𝑃′ 𝑖𝑖 (0) = lim𝑡→ ∞


với𝑎𝑖𝑗 là cường độ chuyển từ trạng thái i sang trạng thái j và ai là cường độ thoát
khỏi trạng thái i của hệ.
Phương trình (1.3.3) gọi là phương trình thuận và phương trình (1.3.4) gọi là
phương trình ngược Kolmogorov.
Định lý 1.3.8.Cho quá trình Markov tối giản (𝑋𝑡 ) với không gian trạng thái E = 1,
2,..., đếm được và ma trận xác suất chuyểnP(t) = 𝑃𝑖𝑗 (t). Khi đó, với mỗi 𝑖, 𝑗 ∈ 𝐸 tồn
tại giới hạn hữu hạn:
𝑙𝑖𝑚𝑡→ ∞ 𝑃𝑖𝑗 (𝑡)= πj
chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó giới hạn 𝜋 = (𝜋1 , 𝜋2 , . . . , ) hoặc là
tất cả bằng không:
𝜋𝑗 = 0

∀𝑗 ∈ 𝐸

hoặc là tất cả dương và lập thành một phân bố xác suất. Phân bố đó được gọi là
phân bố giới hạn của quá trình:
π j> 0

∀j ∈ E,

𝑗

𝜋𝑗 = 1.

CHƢƠNG 2:
MỘT SỐ MÔ HÌNH XẾP HÀNG
2.1 Khái niệm và phân loại quá trình xếp hàng
18



theo nguyên tắc “đến trƣớc phục vụ trƣớc” (FIFO), nghĩa là phục vụ cho
khách hàng nào đứng đầu hàng.
4) Cơ cấu phục vụ: Một phƣơng tiện phục vụ bao gồm một hay nhiều Server.
Các Server có thể kết nối thành chuỗi vì thế mỗi yêu cầu phục vụ đƣợc
phục vụ theo nhiều cách hoặc lần lƣợt hoặc song song.
2.1.2 Các yếu tố cơ bản của hàng đợi
a. Bố trí vật lí của hệ thống
Hệ thống hàng đợi có một số dạng bố trí vật lí (phisical layout)





Một kênh phục vụ, một loại dịch vụ (Single Channel – Single Server)
Một kênh phục vụ, nhiều loại dịch vụ (Single Channel – Multi Server)
Nhiều kênh phục vụ, một loại dịch vụ (Multi Channel – Single Server)
Nhiều kênh phục vụ, một loại dịch vụ (Multi Channel – Multi Server)
19


Các kênh phục vụ đƣợc hiểu là những thiết bị kỹ thuật hoặc con ngƣời hoặc những
tổ hợp các thiết bị kỹ thuật và con ngƣời đƣợc tổ chức quản lí một cách thích hợp
nhằm phục vụ các yêu cầu / các tín hiệu đến hệ thống. Chẳng hạn, ở các trạm điện
thoại tự động, kênh phục vụ là các đƣờng dây liên lạc cùng các thiết bị kĩ thuật
khác phục vụ cho việc đàm thoại.
b. Nguyên tắc phục vụ
Nguyên tắc phục vụ (hay nội quy) của hệ thống là cách thức nhận các yêu cầu
vào các kênh phục vụ. Nguyên tắc phục vụ cho biết trƣờng hợp nào thì yêu cầu
đƣợc nhận vào phục vụ và cách thức phân bố các yêu cầu vào các kênh nhƣ thế
nào. Đồng thời nguyên tắc phục vụ cũng cho biết trong trƣờng hợp nào yêu cầu bị

Tính dừng: Dòng tín hiệu có tính dừng nếu xác suất xuất hiện một số tín hiệu nào
đó trong khoảng thời gian 𝜏 chỉ phụ thuộc vào độ dài của 𝜏 chứ không phụ thuộc
vào thời điểm khởi đầu của 𝜏.
2.1.3 Phân tích hàng đợi
Có các phương pháp phân tích hàng đợi như sau
 Phân tích giải tích
 Quá trình mô phỏng
 Cả hai phƣơng pháp trên
Phƣơng pháp giải tích để giải mô hình hàng đợi gồm các bƣớc sau:
Bước 1: Phân tích hệ thống, chủ yếu là phân tích bản chất của dòng yêu cầu / tín
hiệu đến và các trạng thái của hệ thống.
Bước 2: Thiết lập hệ phƣơng trình trạng thái cho các xác suất trạng thái (xác
suất để hệ thống ở một trạng thái nào đó tại thời điểm t).
Bước 3: Giải hệ phƣơng trình để tìm các xác suất trạng thái. Từ đó thiết lập các
mối quan hệ giữa các chỉ tiêu cần phân tích.
Bước 4: Tính toán, phân tích các chi tiêu, trên cơ sở đó đƣa ra các nhận xét và
các quyết định.
Phƣơng pháp giải tích thƣờng đƣợc sử dụng các giả thiết rất chặt chẽ của Toán
học về các đặc trƣng của hệ thống, vì vậy nó có một số hạn chế nhất định khi giải
các bài toán thực tế.
Trong khi đó phƣơng pháp mô phỏng / mô phỏng ngẫu nhiên để giải mô hình
hàng đợi đƣợc áp dụng cho các bài toán dịch vụ đám đông không giải đƣợc bằng
công cụ giải tích, nhất là những bài toán liên quan đén hệ thống lớn, bất ổn định,
hàm chứa nhiều yếu tố ngẫu nhiên, không tuân theo các giả thiết quá chặt chẽ của
Toán học. Trong nhiều trƣờng hợp phƣơng pháp mô phỏng cho ta tiết kiệm đƣợc
thời gian và chi phí nghiên cứu. Tuy phƣơng pháp mô phỏng chỉ tạo ra các phƣơng
án đủ tốt để đánh giá hoạt động của hệ thống chứ không đƣa ra đƣợc kĩ thuật tìm
21



Biểu diễn dạng của phân bố thời gian đến trung
gian
Dạng phân bố thời gian phục vụ
Số Server
22


K
N
D

Số lƣợng vị trí trong hàng đợi
Số lƣợng khách hàng
Nguyên tắc phục vụ: FIFO, LCFS, SIRO, PNPN
...

Avà B có thể mang bất kì kiểu phân bố sau đây:
Ký hiệu
M
𝐸𝑘
G
D

Dạng phân bố
Phân bố theo cấp số nhân (Markovian)
Phân bố Erlang – k
Phân bố đƣợc xét dƣới dạng tổng quát
Hắng số (Deterministic)

Cụ thể nhƣ sau:

Kết quả phân tích (về phía hệ ngƣời phục vụ)





Khả năng sử dụng Server
Khả năng sử dụng bộ đệm
Lợi ích thu đƣợc (thông số dịch vụ và các xem xét về kinh tế)
Lợi ích bị mất (thông số dịch vụ và các xem xét về kinh tế

Ta phân tích hàng đợi sau:
𝜆tốc độ đến trung bình, thời gian đến trung bình
1/𝜇tốc độ phục vụ trung bình, thời gian phục vụ trung bình 1/𝜇
Với kích thƣớc của bộ đệm là vô hạn, quy tắc phục vụ là FIFO
- Sự kiện A: có một sự đến trong ∆𝑡
- Sự kiện B: không có sự đến nào trong ∆𝑡
- Sự kiện C: có nhiều hơn 1 sự đến trong ∆𝑡
Giả sử rằng ∆𝑡 → 0. Nhƣ vậy ta sẽ có:
𝑃𝑟 𝐴 = 𝜆𝑡
𝑃𝑟 𝐵 = 1 − 𝜆𝑡
Giả thiết

𝑃𝑟 𝐶 = 0

Số lƣợng sự kiện đến tuân theo phân bố Poisson
Đồng thời, khoảng thời gian đến (đƣợc tính giữa hai sự đến liên tiếp) tuân theo
luật phân bố mũ.
- Sự kiện A: có một sự kiện đi trong ∆𝑡
- Sự kiện B: không có sự kiện đi nào trong ∆𝑡

Kích thƣớc quần thể n tƣơng ứng là số lƣợng khách hàng (customer) trong hệ
thống xếp hàng, các sự kiện tƣơng ứng với sinh và tử là các lƣợt đến (arrivals) và
các lƣợt đi (departures) của các khách hàng, λn và µnlần lƣợt là tốc độ đến của
khách hàng và tốc độ phục vụ của hệ thống. Giả sử, khách hàng đang ở trong một
quá trình Poisson và thời gian phục vụ là theo phân phối mũ, chúng ta có công thức
tính xác suất trong khoảng thời gian (t, t + ∆t] nhƣ sau:
sinh(birth) (n ≥ 0):

25