ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————

LÊ THỊ TUYÊN

LÝ THUYẾT XẾP HÀNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

Đà Nẵng - Năm 2019


ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————–

LÊ THỊ TUYÊN

LÝ THUYẾT XẾP HÀNG

Chun ngành: Tốn Giải Tích
Mã số: 8460102

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:
PGS.TS. Huỳnh Thế Phùng

Đà Nẵng - Năm 2019

LỜI CAM ĐOAN

Tồn bộ nội dung trình bày trong luận văn này là cơng trình nghiên cứu
tổng quan của tơi, được hoàn thành dưới sự hướng dẫn của PGS.TS.Huỳnh
Thế Phùng. Những khái niệm và kết quả trong luận văn được tổng hợp từ
các tài liệu khoa học đáng tin cậy, và được chỉ rõ nguồn gốc trích dẫn. Đóng
góp của tơi là tổng hợp tài liệu, trình bày thêm các hình ảnh, ví dụ minh
hoạ. Tơi xin chịu trách nhiệm với những lời cam đoan của mình.
Đà Nẵng, ngày 12 tháng 5 năm 2019
Tác giả

Lê Thị Tuyên


,1

I

I

I

!

TANG TH6NG TIN LU�N VAN TH�C Si
Ten dB tai: Ly THUYET XEP ANG.
Nganh: Toan giai tich.
HQ va ten h9c vien: LE THT TUYEN.
Nguoi hu6ng dan khoa h9c: PGS.TS. H THE PHUNG.

Co so dao t�o: TruIlg D�i h9c Su Ph�m - D�i h9c Da N�ng.
Tom tit: Lu�n van la m(>t ban tang quan kha diy du vs ly thuy8t x8p hang. C1 thS, a day tac gia trinh bay
m(>t s6 ki8n thuc co ban vS ly thuy8t xac suat, d�c biet nhan m�nh phan ph6i mu va phan ph6i Poison, ma
biSu di�n hieu qua phan b6 thai gian d8n va th'i gian ph1c VJ. Lu�n van mo phong he th6ng x8p hang nhu
m)t qua trinh sinh tu. Tu d6 xay d,mg nen cac mo hinh x8p hang co ban dva tren qua trinh sinh tu va dua
ra m>t sb phan tich cac d�c dism, sb do hieu suat va neu cac vi d1 minh h9a cho tung mo hinh ctva tren
qua trinh M /M /1, M /M /s, M /M /1 /K, M /M /s /K.
Y nghia khoa h9c va thl,rc ti�n: Hang dgi la m)t phin cua cu)c s6ng hang ngay. Lu"ng thm gian ma m)t
nguoi dan trong m)t qu6c gia tieu phi khi sip hang la m9t y6u t6 chinh trong viec do chat luJng cu)c s6ng
a d6 va ca hieu qua cua nSn kinh t6 qu6c gia. Ly thuy8t x6p hang la nghien CU vs cac lo�i cha dgi trong
tat ca cac mo hinh khac nhau. N6 SU dlllg cac mo hinh hang dgi dS thS hien cac lo�i he th6ng x8p hang
khac nhau phat sinh trong thvc t6. Cong thuc cho m6i mo hinh cho bi6t he th6ng x6p hang tuong ung se
thvc hien nhu th€ nao, bao g6m ca th'i gian cha trung binh ma se xay ra, trong m)t lo�t cac trulg hgp.
Do d6, cac mo hinh x6p hang nay rAt hm ich dB xac djnh each v�n hanh he th6ng x6p hang theo each hieu
qua nhat.
Huong nghien CU ti8p: DB xuAt cac giai phap lam can bing gira chi phi phvc l va chi phi gay ra do thai
gian cha dgi. Tim hiSu va xay dig them cac mo hinh khac dugc SU d1ng dB giai quy6t cac vin dB lien
quan.
Tu kh6a: Mo hinh x6p hang - khach hang - don vi ph1c l - t6c d> d6n - t6c d9 ph1c J.

Xac nhin cua iao vien htr6ng din

Ngtroi th'C hi\n d� tai

Le Thj Tuyen



LỜI CẢM ƠN


Để có thể hồn thành đề tài luận văn thạc sĩ một cách hoàn chỉnh, bên
cạnh sự nỗ lực cố gắng của bản thân cịn có sự chỉ bảo nhiệt tình của q
thầy cơ, cũng như sự động viên ủng hộ của gia đình và bạn bè trong suốt
thời gian học tập, nghiên cứu và thực hiện luận văn.
Trước hết, tôi xin gửi lời cảm ơn chân thành nhất tới thầy giáo –PGS.TS.
Huỳnh Thế Phùng đã hết lòng quan tâm giúp đỡ, hướng dẫn tơi hồn thành
tốt luận văn này trong thời gian qua.
Tôi cũng xin bày tỏ lịng biết ơn sâu sắc đến các q Thầy, Cơ giáo và
Ban chủ nhiệm Khoa Toán, Trường Đại học Sư Phạm - Đại học Đà Nẵng đã
tận tình truyền đạt những kiến thức quý báu và tạo điều kiện thuận lợi nhất
cho tơi trong suốt q trình học tập nghiên cứu cho đến khi thực hiện đề tài
luận văn.
Cảm ơn các anh, chị và các bạn trong lớp Cao Học Tốn Giải Tích Khóa
34 đã hỗ trợ tơi rất nhiều trong quá trình học tập và nghiên cứu.
Do điều kiện thời gian cũng như kinh nghiệm còn hạn chế nên luận văn
khơng thể tránh khỏi những thiếu sót. Tơi rất mong nhận được sự chỉ bảo,
đóng góp ý kiến của các thầy cơ để tơi có thể bổ sung và hồn thiện luận
văn một cách tốt hơn.
Tơi xin chân thành cảm ơn!
Đà Nẵng, ngày 12 tháng 5 năm 2019
Tác giả

Lê Thị Tuyên


MỤC LỤC
MỞ ĐẦU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
CHƯƠNG 1. MỘT SỐ PHÂN PHỐI XÁC SUẤT CƠ BẢN.4
1.1. PHÂN PHỐI CHUẨN VÀ PHÂN PHỐI NHỊ THỨC


...................... 4

1.1.1. Phân phối chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.1.2. Phân phối nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. PHÂN PHỐI POISSON VÀ PHÂN PHỐI

.............................. 7

1.2.1. Phân phối Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2. Phân phối mũ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. PHÂN PHỐI ERLANG

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

CHƯƠNG 2. MƠ HÌNH XẾP HÀNG CƠ BẢN . . . . . . . . . . . . . 12
2.1. CẤU TRÚC CƠ BẢN CỦA MƠ HÌNH XẾP HÀNG [3]

. . . . . . . . . . . . . . . . . . 12

2.1.1. Các dạng xếp hàng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2. Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.3. Các ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2. MỘT SỐ VÍ DỤ CỤ THỂ VỀ MƠ HÌNH XẾP HÀNG

. . . . . . . . . . . . . . . . . . . . 15

2.3. VAI TRỊ CỦA PHÂN PHỐI MŨ TRONG MƠ HÌNH XẾP HÀNG [3]

. . . . . . . 16


CHƯƠNG 3. MƠ HÌNH XẾP HÀNG DỰA TRÊN Q TRÌNH
SINH TỬ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1. QUÁ TRÌNH SINH TỬ [3]

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.1. Các giả thiết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2. Sơ đồ của quá trình sinh tử . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21


3.2. MƠ HÌNH DỰA TRÊN Q TRÌNH M/M/1 [3]

. . . . . . . . . . . . . . . . . . . . . . . . 25

3.2.1. Đặc điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2. Đo hiệu suất hàng đợi M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.3. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3. MƠ HÌNH DỰA TRÊN QUÁ TRÌNH M/M/s [3]

. . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1. Đặc điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.2. Đo hiệu suất hệ thống M/M/s . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.3. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4. MƠ HÌNH DỰA TRÊN Q TRÌNH M/M/1/K [3]

. . . . . . . . . . . . . . . . . . . . . 35

3.4.1. Đặc điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.5. MƠ HÌNH DỰA TRÊN Q TRÌNH M/M/s/K [3]

. . . . . . . . . . . . . . . . . . . . . 38

3.5.1. Đặc điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.2. Đo hiệu suất của hệ thống M/M/s/K . . . . . . . . . . . . . . . . . 38
KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41


DANH MỤC

1. Danh mục các ký hiệu:
N : Tập hợp các số nguyên dương.
R : Tập hợp các số thực.
2. Danh mục các bảng - hình vẽ:
Số hiệu bảng

Tên bảng

Trang

3.1

Các phương trình cân bằng cho quá trình sinh tử

23

Số hiệu hình vẽ


Tên hình vẽ

Trang

2.1

Mơ hình xếp hàng cơ bản

12

2.2

Một số hệ thống xếp hàng cơ bản

14

2.3

Hàm mật độ xác suất cho phân phối mũ

16

3.1

Biểu đồ tỉ lệ cho quá trình sinh - tử

21

3.2


Sơ đồ tỉ lệ cho M/M/1

25

3.3

Sơ đồ tỉ lệ cho M/M/s

31

3.4

Giá trị P0 trong mơ hình M/M/s

32

3.5

Giá trị L trong mơ hình M/M/s

33


1

MỞ ĐẦU

1. Lý do chọn đề tài
Hàng đợi là một phần của cuộc sống hàng ngày. Chúng ta phải đứng chờ
tại quầy thu tiền ở siêu thị, chờ để mua vé xem phim, mua vé xe, vé tàu, rút

tiền tại các trạm ATM, lấy thức uống trong quán cà phê, đứng chờ mua xăng
tại trạm xăng, chờ được xử lý tại phòng cấp cứu, máy bay chờ được cất cánh,
hạ cánh, tàu thuỷ chờ được bốc, dỡ hàng hoá tại cảng. . . Trong những mơ
hình phục vụ như trên, các khách hàng 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ụ. Trong mọi tình huống, thời
gian chờ là điều mà chúng ta không muốn. Chúng ta phải xác định những
cách để tính thời gian chờ trong giới hạn cho phép. Tất cả các ví dụ trên đã
và đang được nghiên cứu nhờ sử dụng một lý thuyết toán học của các hàng
đợi có tên là lý thuyết xếp hàng (hay lý thuyết phục vụ đám đông).
Lý thuyết xếp hàng liên quan đến nghiên cứu toán học của các hàng đợi
hoặc các dịng chờ. Sự hình thành các hàng đợi là một hiện tượng phổ biến
xảy ra bất cứ khi nào nhu cầu được phục vụ vượt quá khả năng hiện tại để
cung cấp dịch vụ đó. Các quyết định liên quan đến số lượng, khả năng cung
cấp dịch vụ phải được thực hiện thường xun. Tuy nhiên, vì thường khơng
thể dự đốn chính xác khi nào các đơn vị đến để tìm dịch vụ và việc tính
tốn cần bao nhiêu thời gian để cung cấp dịch vụ đó thường rất khó. Cung
cấp nhiều đơn vị phục vụ sẽ dẫn đến chi phí q cao. Ngược lại, nếu khơng
cung cấp đủ đơn vị phục vụ khiến cho thời gian chờ đợi trở nên quá lâu, mà
điều đó cũng dẫn đến tốn kém theo nhiều nghĩa. Do đó, mục đích cuối cùng
là đạt được một sự cân bằng kinh tế giữa chi phí dịch vụ và chi phí liên quan
đến việc chờ đợi dịch vụ đó. Lý thuyết xếp hàng khơng giải quyết vấn đề này
một cách trực tiếp; tuy nhiên, nó đóng góp thơng tin quan trọng cần thiết


2

bằng cách dự đốn các đặc tính khác nhau của hàng đợi. Lý thuyết xếp hàng
xác định và tìm các phương án tối ưu để hệ thống phục vụ tốt nhất trên cơ
sở việc xác định được các số đo hiệu năng của các hàng xếp. 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ư

mạng máy tính, quản lý xí nghiệp. Ngồi ra lý thuyết xếp hàng cũng cịn là
cơ sở tố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.
Với các ứng dụng thực tiễn như trên, lý thuyết xếp hàng thực sự rất cần
thiết trong mọi lĩnh vực của đời sống xã hội. Vì vậy, được sự đồng ý hướng
dẫn của PGS.TS. Huỳnh Thế Phùng, em chọn đề tài: “LÝ THUYẾT XẾP
HÀNG” cho luận văn thạc sĩ của mình.
2. Mục tiêu của đề tài
Nghiên cứu một số mơ hình cơ bản của Lý thuyết xếp hàng thơng qua
các q trình sinh tử khác nhau. Từ đó đề xuất các giải pháp làm cân bằng
giữa chi phí phục vụ và chi phí gây ra do thời gian chờ đợi.
3. Phương pháp nghiên cứu
Luận văn được nghiên cứu dựa trên các phương pháp:
- Nghiên cứu các tài liệu liên quan đến đề tài, bao gồm các tài liệu kinh
điển, tổng hợp và trình bày báo cáo tổng quan.
- Tham khảo, trao đổi với cán bộ hướng dẫn.
4. Đóng góp của đề tài
- Tổng hợp tài liệu để có một báo cáo tổng quan khá đầy đủ về Lý
Thuyết Xếp Hàng cùng các ứng dụng bằng số đối với các mơ hình cụ thể.
- Bổ sung các ví dụ, hình ảnh và các chứng minh chi tiết.
5. Cấu trúc luận văn
Ngoài phần mở đầu và kết luận, tài liệu tham khảo, luận văn gồm ba
chương:
- Chương 1: Một số phân phối xác suất cơ bản. Chương này trình bày


3

sơ lược một số khái niệm và vấn đề liên quan đến xác suất để làm cơ sở cho
chương sau.

- Chương 2: Mơ hình xếp hàng cơ bản. Chương này trình bày một số
khái niệm, ký hiệu và ví dụ về Mơ hình xếp hàng.
- Chương 3: Mơ hình xếp hàng dựa trên quá trình sinh tử. Chương này
là nội dung chính của luận văn, trình bày một số Mơ hình xếp hàng cơ bản.


4

CHƯƠNG 1

MỘT SỐ PHÂN PHỐI XÁC SUẤT CƠ BẢN

1.1. PHÂN PHỐI CHUẨN VÀ PHÂN PHỐI NHỊ THỨC

1.1.1. Phân phối chuẩn
Định nghĩa 1.1.1. [1] Biến ngẫu nhiên liên tục X được gọi là có phân phối
chuẩn với tham số µ và σ (−∞ < µ < ∞ và σ > 0) kí hiệu X ∼ N (µ, σ 2 )

nếu hàm mật độ xác suất của nó có dạng:
(x − µ)2
−
1
2σ 2 , x ∈ R.
f (x) = √ e
σ 2π
Lúc đó:
+∞

f (x)dx = 1.
−∞


- Đồ thị đối xứng qua đường x = µ.
1
khi x = µ.
- Hàm số đạt cực đại bằng √
σ 2π
- Có hai điểm uốn tại x = µ + σ và x = µ − σ.

- Ln nằm phía trên trục Ox và nhận Ox làm tiệm cận ngang.

Các tham số đặc trưng
- Kỳ vọng toán:
+∞

E(X) =
−∞

1
xf (x)dx = √
σ 2π

Thực hiện phép biến đổi:

z=

x−µ
σ

ta có


x = σz + µ.
Do vậy dx = σdz, nên

+∞
−∞

(x − µ)2
2σ 2 dx.
xe
−


5

1
E(X) = √
2π
1
= √
2π
= 0+µ

+∞
−∞
+∞
−∞

z2
(σz + µ)e 2 dz
−


z2
−
µ
σze 2 dz + √
2π

z2
e 2 dz

+∞ −
−∞

= µ.
- Phương sai:

1
E(X 2 ) = √
2π
2

σ
= √
2π
2

+∞
−∞
+∞


z2
(σz + µ)2 e 2 dz
−

z2
−
z 2 e 2 dz + µ2

−∞

σ
− ze
= √
2π
= σ 2 + µ2 .

−z 2
2

+∞

+∞

+
−∞

−z 2
e 2 dz + µ2

−∞


V ar(X) = E(X 2 ) − E(X)2 = σ 2 + µ2 − µ2 = σ 2 .
Vậy µ và σ 2 là kỳ vọng và phương sai của biến ngẫu nhiên X.
- Cho X1 , X2 , X3 , ..., Xn là các biến ngẫu nhiên độc lập và có cùng phân
phối chuẩn với tham số µ và σ 2 thì
và

S = X1 + X2 + X3 + ... + Xn ∼ N (nµ; nσ 2 )

X1 + X2 + X3 + ... + Xn
∼ N (µ; σ 2 /n).
n
α−µ
- P (X < α) = P (X ≤ α) = Φ(
)
σ
−x2
1
α
trong đó Φ(α) = −∞ √ e 2 dx.
2π
- Với α < β,
β−µ
α−µ
P (α < X < β) = P (α ≤ X ≤ β) = Φ(
) − Φ(
).
σ
σ
X=



6

1.1.2. Phân phối nhị thức
Định nghĩa 1.1.2. [1] Biến ngẫu nhiên rời rạc X được gọi là có phân phối
Bernoulli với tham số p (0 < p < 1) kí hiệu X ∼ Ber(p) nếu hàm xác suất:

p(x; p) = px (1 − p)1−x , x ∈ {0, 1}.

Các tham số đặc trưng:
- Kỳ vọng:

E(X) = p1 (1 − p)0 = p.
- Phương sai:

V ar(X) = E(X 2 ) − E(X)2

= p − p2 = p(1 − p).

Định nghĩa 1.1.3. [1] Biến ngẫu nhiên rời rạc X được gọi là có phân phối
theo quy luật nhị thức với tham số n và p (n ∈ N\0, 0 < p < 1) kí hiệu

X ∼ B(n, p) nếu X có hàm xác suất:

p(x; n, p) = Cnx px (1 − p)n−x , x ∈ 0, 1, 2, ..., n.

Các tham số đặc trưng:
- Kỳ vọng:
n


E(X) =
x=0

xCnx px (1 − p)n−x
n

= np
x=1
n

= np
x=1

x x x−1
Cn p (1 − p)(n−1)−(x−1)
n
x−1 x−1
Cn−1
p (1 − p)(n−1)−(x−1)

= np[p + (1 − p)n−1 ] = np.
- Phương sai:

V ar(X) = E(X 2 ) − E(X)2
trong đó E(X)2 = n2 p2 .


7
n

2

E(X ) =
x=0
n

x2 Cnx px (1 − p)n−x

= p
x=1
n

= np
x=1

x−1
x−1 x−1
p (1 − p)(n−1)−(x−1) vớix2 Cnx = nxCn−1
nxCn−1
x−1 x−1
[(x − 1) + 1]Cn−1
p (1 − p)(n−1)−(x−1)
n

= np[(n − 1)p
= np[(n − 1)p

x=2
n
x=2


x − 1 x−1 x−2
Cn−1 p (1 − p)(n−2)−(x−2) + 1]
n−1
x−2 x−2
Cn−2
p (1 − p)(n−2)−(x−2) + 1]

= np[(n − 1)p.1 + 1]
= n2 p2 − np2 + np.

Vậy V ar(X) = n2 p2 − np2 + np − n2 p2 = np(1 − p).
Nếu X1 , X2 , X3 , ..., Xn là các biến ngẫu nhiên độc lập và có cùng phân
phối Ber(p), thì

S = X1 + X2 + X3 + ... + Xn ∼ B(n, p).
1.2. PHÂN PHỐI POISSON VÀ PHÂN PHỐI

1.2.1. Phân phối Poisson
Định nghĩa 1.2.1. [1] Biến ngẫu nhiên rời rạc X được gọi là phân phối
Poisson với tham số λ (λ > 0) kí hiệu X ∼ P (λ) nếu tập giá trị của X là

Ω(X) = N = {0, 1, 2, . . .} có hàm xác suất:
p(x; λ) = px =

e−λ λx
, x ∈ N.
x!

Lúc đó:

∞
x=0

px =

∞

e−λ λx
x!

x=0
−λ λ

= e e
= 1.


8

Các tham số đặc trưng:
- Kỳ vọng:
∞

λx e−λ
x
E(X) =
x!
x=1
∞


=

λx e−λ
(x − 1)!

x=1
∞

= λ

k=0

λk e−λ
k!

= λ.
- Phương sai:

V ar(X) = E(X 2 ) − E(X)2
∞
x −λ
2λ e
x
=
− λ2
x!
x=1
=
=
=


∞
x=1
∞
x=2
∞
x=2

= λ

2

xλx e−λ
− λ2
(x − 1)!

∞

(x − 1)λx e−λ
λx e−λ
+
− λ2
(x − 1)!
(x − 1)!
x=1
∞

λx e−λ
λx e−λ
+

− λ2
(x − 2)! x=1 (x − 1)!

∞

k=0

∞

λk e−λ
λk e−λ
+λ
− λ2
k!
k!
k=0

2

= λ + λ − λ2
= λ.
Biến ngẫu nhiên có phân phối Poisson khi dịng đến có đủ các đặc điểm của
q trình Poisson. Q trình Poisson có 3 tính chất sau:
Tính khơng hậu quả: Dịng khách hàng có tính khơng hậu quả có nghĩa
là nếu xác suất xuất hiện một số khách hàng nào đó trong một khoảng thời
gian nhất định không phụ thuộc vào việc đã có bao nhiêu khách hàng xuất
hiện trước khoảng thời gian đó. Hay nói khác, số khách hàng xuất hiện trước
và sau thời điểm nào đó khơng chịu ảnh hưởng qua lại lẫn nhau.



9

Tính đơn nhất Dịng khách hàng có tính chất đơn nhất có nghĩa là nếu
xét trong khoảng thời gian khá bé thì biến cố “có nhiều hơn một khách hàng
xuất hiện” là không xảy ra. Về mặt thời gian, chúng ta có thể xem dịng
khách hàng có tính chất đơn nhất nếu thời điểm xuất hiện các khách hàng
không trùng nhau.
Tính dừng (tính thuần nhất theo thời gian) Dịng khách hàng có tính
chất dừng có nghĩa là: nếu xác suất xuất hiện k khách hàng trong khoảng
thời gian t chỉ phụ thuộc vào giá trị của t và của k chứ không phụ thuộc vào
việc khoảng thời gian t này nằm ở vị trí nào trên dịng thời gian. Điều này
có nghĩa là với những khoảng thời gian t dài bằng nhau thì xác suất xuất
hiện k khách hàng như nhau.
Phân phối Poisson là dạng giới hạn của phân phối nhị thức: Cho
X là biến ngẫu nhiên nhị thức với phân phối xác suất p(x; n, p). Khi n →

+∞, p → 0 và np là hằng số λ, thì p(x; n, p) → p(x; λ).
Thật vậy:

lim p(x; n, p) = lim Cnx px (1 − p)n−x

n→∞

n→∞

λ
λ
n!
( )x .(1 − )n−x
n→∞ x!(n − x)! n

n
x
λ
λ
1
n!
=
lim
.(1 − )n .
λ
x! n→∞ x!(n − x)!
n
(1 − )x
n
x
λ −λ
.e
=
x!
= p(x, λ).
= lim

1.2.2. Phân phối mũ
Định nghĩa 1.2.2. [1] Biến ngẫu nhiên liên tục X được gọi là phân phối
mũ, kí hiệu X ∼ E(λ) nếu X có hàm mật độ xác suất:

f (x, λ) = λe−λx , x > 0.

Lúc đó:


+∞
0

λe−λx dx = 1.


10

Các tham số đặc trưng:
-Kỳ vọng:

+∞

E(X) =
0

xλe−λx dx

+∞

= λ

xe−λx dx.

0

Sử dụng cơng thức tích phân từng phần, ta được:
+∞
−1 −λx
1 +∞ −λx

e dx
e
E(X) = λ x
+
λ
λ 0
0
+∞

= −xe

1
− e−λx
λ

−λx
0

+∞
0

1
.
λ
-Phương sai: V ar(X) = E(X 2 ) − E(X)2 .
=

Ta có:

+∞


2

E(X ) =
0

x2 λe−λx dx

+∞

= λ

x2 e−λx dx.

0

Sử dụng công thức tích phân từng phần, ta được:
+∞
2

2 −λx

E(X ) = −x e
2
λ 0
2 1
= .
λ λ
2
= 2.

λ

+∞

=

Vậy V ar(X) = E(X 2 ) − E(X)2 =

0

1
+
λ

+∞

2xe−λx dx

0

xe−λx dx

1
1
2
−
=
.
λ2 λ2
λ2


1.3. PHÂN PHỐI ERLANG
Định nghĩa 1.3.1. [1] Biến ngẫu nhiên X được gọi là có phân phối Erlang ,


11

kí hiệu Ek với tham số µ và k nếu X là tổng của k biến ngẫu nhiên độc lập
có cùng phân phối mũ với tham số kµ có hàm mật độ:
k
k−1 (µk)
e−kµx , x > 0.
f (x) = x
(k − 1)!
Lúc đó:
∞

x

k−1

0

(µk)k −kµx
e
dx =
(k − 1)!
=
=
=

=

∞

(µk)k
e−kµx
x
d
(k − 1)!
−kµ
0
∞
∞
xk−1 e−kµx
(µk)k
(k − 1)xk−2 e−kµx
dx
−
+
(k − 1)!
kµ
kµ
0
0
(µk)k−1 ∞ k−2 −kµx
0+
x e
dx
(k − 2)! 0
(µk)k−2 ∞ k−3 −kµx

x e
dx
(k − 3)! 0
...
k−1

∞

= µk
0

= −e

−kµx

= 1.
Khi đó:

∞

E(X) =

e−kµx dx
∞
0

xf (x)dx

0
∞


(µk)k k −kµx
=
x e
dx
(k − 1)!
0
∞
(µk)k+1 k −kµx
k
x e
dx
=
kµ 0
k!
1
= .
µ


12

CHƯƠNG 2

MƠ HÌNH XẾP HÀNG CƠ BẢN

2.1. CẤU TRÚC CƠ BẢN CỦA MƠ HÌNH XẾP HÀNG [3]

2.1.1. Các dạng xếp hàng
Trong cuộc sống hằng ngày, chúng ta thường gặp các trường hợp đứng

chờ để mua vé tàu, vé xe, vé xem phim; chờ được phục vụ tại các nhà hàng,
quán cafe, quầy thức ăn nhanh; xe ô tô trên các xa lộ thu phí; các bệnh nhân
chờ tại phịng cấp cứu của bệnh viện; tàu chờ bốc hàng tại cảng; chờ giao
dịch tại các ngân hàng; ...các trường hợp đó được gọi là các dạng xếp hàng.
Tất cả các trường hợp trên đã và đang được nghiên cứu nhờ sử dụng
một lý thuyết tốn học của các hàng đợi có tên là lý thuyết xếp hàng (hay
lý thuyết phục vụ đám đơng).

Hình 2.1: Mơ hình xếp hàng cơ bản


13

2.1.2. Các khái niệm cơ bản
Dòng khách hàng đến hệ thống (dòng vào): Là dòng các đối tượng đi
đến hệ thống và đòi hỏi được thoả mãn nhu cầu nào đó. Dịng khách hàng
đến hệ thống là dịng biến cố ngẫu nhiên và tuân theo những phân phối xác
suất như: Phân phối Poisson, phân phối Erlang,. . .
Trạng thái của hệ thống: Là số khách hàng trong hệ thống (bao gồm cả
các khách hàng đang được phục vụ và các khách hàng đang chờ được phục
vụ).
Dòng khách hàng chờ phục vụ (hàng chờ): Là tập hợp các khách hàng
sắp xếp theo một trật tự nào đó để chờ được phục vụ. (Tuy nhiên, trong
thực tế cũng có những hệ thống khơng có hàng chờ).
Chiều dài hàng đợi: Là số khách hàng chờ được phục vụ bằng trạng thái
hệ thống trừ cho số khách hàng đang được phục vụ.
Đơn vị phục vụ: Là những thiết bị, con người hoặc tổ hợp các thiết bị
và con người mà hệ thống sử dụng để phục vụ các khách hàng đến hệ thống.
Thời gian phục vụ: Là thời gian ít nhất mỗi đơn vị phục vụ phải tiêu
hao để phục vụ xong một khách hàng và nó là một đại lượng ngẫu nhiên

tuân theo một qui luật phân phối xác suất nhất định (thường là phân phối
mũ).
Dòng khách hàng đi ra khỏi hệ thống (yêu cầu đã được phục vụ): Là
dòng các khách hàng đi ra khỏi hệ thống, gồm các khách hàng đã được phục
vụ và các khách hàng bị từ chối. Nếu dịng vào là dịng tối giản thì dịng phục
vụ tại mỗi đơn vị phục vụ sẽ là dòng xấp xỉ tối giản.
Nguyên tắc phục vụ của hệ thống: Nó cho biết cách thức khách hàng
được nhận vào và phân bố các khách hàng vào các đơn vị phục vụ. Ngoài
ra nó cũng cho biết trường hợp nào yêu cầu bị từ chối hoặc phải chờ và giới
hạn cho phép của hàng chờ hoặc giới hạn của thời gian chờ.


14

Hình 2.2: Một số hệ thống xếp hàng cơ bản

2.1.3. Các ký hiệu
− Các thuật ngữ:
+ N (t): trạng thái hệ thống tại thời điểm t ≥ 0.
+ Pn (t): xác suất có đúng n khách hàng trong hệ thống tại t ≥ 0.
+ s: số đơn vị được phục vụ (số quầy phục vụ).
+ λn : tốc độ đến trung bình khi có n khách hàng trong hệ thống. Thơng
thường λn = λ, ∀n (tốc độ trung bình khơng phụ thuộc vào trạng thái hệ
thống).

1
λ

là thời gian trung bình giữa hai lần đến của khách hàng. λ không


phụ thuộc vào s.

+ µn : tốc độ phục vụ trung bình khi có n khách hàng trong hệ thống.
Thơng thường tốc độ phục vụ trung bình tại một quầy là µ đơn vị thời gian.

µn có phụ thuộc vào s.Lúc đó tốc 
độ phục vụ trung bình của hệ thống là:
 nµ, n ≤ s
µn =
 sµ, n > s


15
∞

+ L: số lượng khách hàng kỳ vọng trong hệ thống xếp hàng =

nPn .

n=0

+ Lq : chiều dài hàng đợi (không bao gồm khách hàng đang được phục
∞

vụ) =

n=s

(n − s)Pn .


+ W : thời gian chờ đợi trong hệ thống (bao gồm thời gian phục vụ) cho
từng khách hàng.

+ Wq : thời gian chờ đợi trong hệ thống (không bao gồm thời gian phục
vụ) cho từng khách hàng.

− Mối liên hệ giữa L, W, Lq , Wq .
Giả sử λn = λ với mọi n. Ta có:

L = λW,

Lq = λW q.

Nếu λn khơng bằng nhau, λ có thể thay thế bằng λ trong các phương
trình.Giả sử thời gian phục vụ trung bình là một hằng số,
Do đó:

1
µ

với mọi n ≥ 1.

1
W = Wq + .
µ

2.2. MỘT SỐ VÍ DỤ CỤ THỂ VỀ MƠ HÌNH XẾP HÀNG
Trong các hệ thống phục vụ như: Bến cảng, khách sạn, nhà hàng, trạm
điện thoại, cửa hàng bán xăng dầu...thường diễn ra 2 quá trình: Quá trình
nảy sinh các yêu cầu và q trình phục vụ các u cầu.

Các ví dụ:
1. Các hệ thống điện thoại: khi số lượng lớn khách hàng quay số để kết
nối đến một trong những đường ra hữu hạn của tổng đài.
2. Trong mạng máy tính: khi mà gói tin được chuyển từ nguồn tới đích
và đi qua một số lượng các nút trung gian. Hệ thống hàng đợi xuất hiện tại
mỗi nút ở quá trình lưu tạm thơng tin tại bộ đệm.
3. Hệ thống máy tính: khi các cơng việc được tính tốn và tuyến làm
việc của hệ thống yêu cầu dịch vụ từ bộ xử lý trung tâm và từ các nguồn
khác.


16

Tuy nhiên, trong quá trình hoạt động của hệ thống do nhiều nguyên nhân
khác nhau thường dẫn đến các tình trạng:

− Khả năng phục vụ của hệ thống không đáp ứng yêu cầu (s quá bé)

do đó kết quả là một số yêu cầu không được phục vụ hoặc phải chờ đợi để
được phục vụ nên cần lắp đặt thêm đơn vị phục vụ dẫn đến chi phí cao.

− Khả năng phục vụ của hệ thống vượt quá yêu cầu (s q lớn) do đó

kết quả là hệ thống khơng sử dụng hết năng lực về lao động, vật tư, thiết
bị...nên thừa các đơn vị phục vụ dẫn đến chi phí cao.
Do vậy cần điều chỉnh đơn vị phục vụ(s) phù hợp với yêu cầu để tiết
kiệm chi phí.
2.3. VAI TRỊ CỦA PHÂN PHỐI MŨ TRONG MƠ HÌNH XẾP
HÀNG [3]
Giả sử T là biến ngẫu nhiên chỉ thời gian giữa 2 lần đến (hoặc thời gian

giữa 2 lần phục vụ). T thường có phân phối mũ và hàm mật độ của nó có
dạng:

fT (t) =


−αt


 αe ,




0,

t≥0
t < 0.

Hình 2.3: Hàm mật độ xác suất cho phân phối mũ