Mô hình hệ thống phục vụ công cộng

TRƯỜNG ĐẠI HỌC CẦN THƠ
KHOA KHOA HỌC TỰ NHIÊN
BỘ MÔN TOÁN
------------

LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC

MÔ HÌNH HỆ THỐNG
PHỤC VỤ CÔNG CỘNG

GIÁO VIÊN HƯỚNG DẪN

SINH VIÊN THỰC HIỆN

Th.S. NGUYỄN THỊ HỒNG DÂN

HUỲNH THỊ LY

(BỘ MÔN TOÁN – KHOA KHTN)

MSSV: 1100176
NGÀNH: TOÁN ỨNG DỤNG

CẦN THƠ - 12/2013


Mô hình hệ thống phục vụ công cộng

LỜI CẢM ƠN

-----------

Trước tiên, em xin gửi lòng biết ơn sâu sắc đến cô Nguyễn Thị Hồng
Dân đã tận tình hướng dẫn em hoàn thành tốt luận văn này. Em xin cảm ơn cô
đã quan tâm chỉ dạy, giúp đỡ em trong suốt quá trình làm luận văn.
Em xin gửi lời cảm ơn đến thầy cố vấn Trần Phước Lộc và các thầy, cô
Trường Đại Học Cần Thơ đặc biệt là các thầy, cô Khoa Khoa Học Tự Nhiên,
những người đã dạy dỗ, hỗ trợ em trong suốt 4 năm học đại học.
Em xin gửi lời cảm ơn chân thành đến các Quý Thầy cô trong Hội đồng
chấm luận văn đã dành thời gian đọc và đóng góp nhiều ý kiến quý báo cho
luận văn.
Em xin gửi lời cảm ơn đến các bạn em, những người luôn sát cánh bên
em, giúp đỡ em trong những lúc khó khăn và đã gắn bó với em trong những
tháng ngày học đại học.
Em xin gửi lòng biết ơn sâu sắc đến cha mẹ, cha mẹ luôn tạo mọi điều
kiện tốt nhất cho em học tập ở trường, luôn bên cạnh động viên em trong
những lúc khó khăn nhất.
Cuối cùng, một lần nữa em xin gửi lòng biết ơn sâu sắc đến cha mẹ,
thầy cô và bạn bè của em, đã giúp em tiếp cận nguồn tri thức và có thể hoàn
thành tốt chương trình Đại Học.
Mặc dù đã cố gắng hết sức, song luận văn không tránh khỏi những thiếu
sót. Em rất mong nhận được sự thông cảm và chỉ bảo tận tình của Quý Thầy
cô và các bạn.
Cần Thơ, tháng 12 năm 2013
i

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng


HUỲNH THỊ LY

DANH MỤC CÁC BẢNG
Trang
Bảng I.1. Tính toán giá trị các tần số lý thuyết ................................................9
Bảng I.2. Tính toán mô phỏng tìm số nhu cầu được phục vụ ........................ 25
Bảng I.3. Tính toán giá trị các tần số lý thuyết .............................................. 42

DANH MỤC CÁC HÌNH
Trang
Hình 1.1. Cấu trúc hệ thống phục vụ công cộng .............................................3
..........................................................................................................................
Hình 1.2. Mô phỏng tổng quát của lý thuyết xếp hàng .................................. 10
Hình 1.3. Hệ thống hàng chờ ........................................................................ 14
Hình 1.4. Các dạng hệ thống hàng chờ ......................................................... 15

ii

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

MỤC LỤC
LỜI CẢM ƠN .................................................................................................i
DANH MỤC CÁC BẢNG ............................................................................ ii
DANH MỤC CÁC HÌNH ............................................................................ ii
MỤC LỤC ................................................................................................... iii
LỜI NÓI ĐẦU ...............................................................................................1

PHẦN MỞ ĐẦU
I. Lý do chọn đề tài .................................................................................2
II. Mục đích nghiên cứu ...........................................................................2
III. Đối tựợng và phạm vi nghiên cứu ........................................................2
IV. Phương pháp nghiên cứu .....................................................................2
PHẦN NỘI DUNG
Chương 1

CƠ SỞ LÝ THUYẾT ...................................................3

1.1. MÔ HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG ..............................3
1.1.1. Hệ thống phục vụ và các yếu tố ......................................................3
1.1.2. Tính chất của một dòng yêu cầu Poisson và Poisson dừng ..............4
1.1.3. Kiểm định giả thiết về phân phối Poisson – Tiêu chuẩn khi bình
phương ............................................................................................8
1.2. QUÁ TRÌNH XẾP HÀNG .................................................................10
1.2.1. Khái niệm quá trình xếp hàng .....................................................10
1.2.2. Một số đặc trưng của hệ thống xếp hàng .....................................11
1.2.3. Mô hình hàng chờ .......................................................................12
1.2.4. Các yếu tố cơ bản của hệ thống hàng chờ ....................................14
1.2.5. Phân tích hàng chờ ......................................................................16
iii

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

1.2.6. Ký hiệu Kendall ..........................................................................17
1.2.7. Các chỉ tiêu đánh giá ...................................................................18

1.2.8. Các chỉ số cần khảo sát ...............................................................20
1.2.9. Tính toán các chỉ số ....................................................................21
1.2.10. Một số điểm hạn chế của các mô hình hàng chờ .........................22
Chương 2

BÀI TOÁN MÔ HÌNH HỆ THỐNG PHỤC VỤ
CÔNG CỘNG .............................................................27

2.1. TỔNG QUAN VỀ HỆ THỐNG PHỤC VỤ CÔNG CỘNG ................27
2.1.1. Bài toán lý thuyết phục vụ công cộng .........................................27
2.1.2. Trạng thái hệ thống và quá trình chuyển trạng thái ......................28
2.1.3. Sơ đồ trạng thái và hệ phương trình trạng thái .............................39
2.1.4. Quá trình hủy và sinh – Lời giải của hệ phương trình trạng thái ..31
2.1.5. Phân loại hệ thống ......................................................................33
2.2. MỘT SỐ HỆ THỐNG PHỤC VỤ CÔNG CỘNG POISSON DỪNG .33
2.2.1. Hệ thống phục vụ công cộng từ chối cổ điển (hệ thống Eclang) ..33
2.2.2. Hệ thống phục vụ công cộng chờ thuần nhất ...............................41
2.2.3. Hệ thống chờ với độ dài hàng chờ hạn chế và thời gian chờ không
hạn chế .......................................................................................49
Chương 3 ỨNG DỤNG PHẦN MỀM MATLAB TRONG BÀI TOÁN MÔ
HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG ..........................58
3.1. CÂU LỆNH MATLLAB CHO VÍ DỤ 1.2 .......................................58
3.2. CHƯƠNG TRÌNH MATLAB CHO HỆ THỐNG ECLANG ............60
3.2.1. Chương trình Matlab ....................................................................60
3.2.2. Ví dụ ............................................................................................61

iv

SVTH: Huỳnh Thị Ly



Mô hình hệ thống phục vụ công cộng

3.3. CHƯƠNG TRÌNH MATLAB CHO HỆ THỐNG PHỤC VỤ CÔNG
CỘNG CHỜ THUẦN NHẤT ...............................................................65
3.3.1. Chương trình Matlab ....................................................................65
3.3.2. Ví dụ ............................................................................................66
3.4. CHƯƠNG TRÌNH MATLAB CHO HỆ THỐNG CHỜ VỚI ĐỘ DÀI
HÀNG CHỜ HẠN CHẾ VÀ THỜI GIAN CHỜ KHÔNG HẠN CHẾ ..68
3.4.1. Chương trình Matlab ....................................................................68
3.4.2. Ví dụ ............................................................................................69
PHẦN KẾT LUẬN ......................................................................................72
TÀI LIỆU THAM KHẢO ...........................................................................73

v

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

LỜI NÓI ĐẦU
Mô hình hóa là một trong các công cụ phân tích và điều khiển đã và
đang được ứng dụng rộng rãi trong nhiều lĩnh vực kinh tế - xã hội khác nhau.
Trong thực tế, nhiều khách hàng phải xếp thành hàng để đợi mua vé, các cuộc
gọi điện thoại phải đợi để được liên lạc tại các tổng đài điện thoại và các tác
vụ có thể phải đợi để nhận được điều khiển của CPU trong máy tính. Trong
một mạng máy tính, nhiều người cùng sẽ chia tài nguyên nhưng chỉ có thể sử
dụng tài nguyên cho mỗi công việc tại mỗi thời điểm, vì thế các công việc
khác phải xếp hàng đợi. 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ó tên là Mô hình hệ thống phục vụ công cộng.
Mô hình hệ thống phục vụ công cộng có nguồn gốc từ đầu thế kỷ 20 với
các nghiên cứu khởi đầu của nhà toán học người Đan Mạch A.K. Erlang trên
các mạng điện thoại.
Với sự trợ giúp của phần mềm Matlab không chỉ làm nhẹ các tính toán
mà còn trang bị cách tiếp cận lời giải của một số lớp bài toán nhờ máy tính
điện tử, bước đầu làm cho tin học không chỉ là công cụ làm việc mà còn có thể
sử dụng như một công cụ tư duy.
Trong khuôn khổ cho phép, luận văn gồm có 3 phần: Phần mở đầu ,
phần nội dung và phần kết thúc.
Phần nội dung gồm 3 chương:
- Chương 1: CƠ SỞ LÝ THUYẾT
- Chương 2: BÀI TOÁN MÔ HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG
- Chương 3: ỨNG DỤNG PHẦN MỀM MATLAB TRONG CÁC
BÀI TOÁN MÔ HÌNH HỆ THỐNG PHỤC CÔNG CỘNG
Trong quá trình nghiên cứu thực hiện, đề tài đã sử dụng phương pháp
phân tích tổng hợp tài liệu, đồng thời kết hợp với nguồn thông tin được sưu
tầm từ sách báo và các website có liên quan.

1

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

PHẦN MỞ ĐẦU
I. Lý do chọn đề tài
Ngày nay mô hình hệ thống phục vụ công cộ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 nghành nghề khác nhau

như bưu chính viễn thông, kiểm soát lưu lượng giao thông, bán vé và trong các
hệ thống phục vụ khác… Trong nhiều hệ thống phục vụ, 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ụ. Mô hình hệ thống phục vụ công cộng xác định và tìm các phưong án tối ưu
để hệ thống phục vụ tốt nhất.
Ngoài ra mô hình hệ thống phục vụ cô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 như đầu tư, kiểm kê, rủi ro của
bảo hiểm, thị trường chứng khoán…Với mục đích phục vụ cho công tác kế
hoạch hóa phát triển kinh tế và kinh doanh thì nhu cầu hệ thống phục vụ công
cộng ngày càng trở nên cấp thiết.
Vì vậy, em đã chọn đề tài “ Mô hình hệ thống phục vụ công cộng” do đề
tài này cung cấp những thông tin hữu ích cho chúng ta cách nhìn một hệ thống
ngẫu nhiên.
II. Mục đích nghiên cứu
Nghiên cứu hệ thống phục vụ trong điều kiện tác động của yếu tố ngẫu
nhiên đưa ra phân tích đánh hiệu quả.
Tiếp cận các hệ thống ngẫu nhiên, đánh giá khác biệt của nó với hệ
thống liên tục.
III. Đối tượng và phạm vi nghiên cứu

IV.

-

Luật phân phối Poisson

-

Hệ thống phục vụ công cộng cổ điển


-

Hệ thống phục vụ công cộng chờ thuần nhất

-

Hệ thống chờ phục vụ

Phương pháp nghiên cứu
- Đọc tài liệu tham khảo.
- Chạy thử nghiệm bằng Matlab và kiểm định bằng các bài toán cụ thể.
2

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

Chương 1
1.1.

CƠ SỞ LÝ THUYẾT

MÔ HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG

1.1.1. Hệ thống phục vụ công cộng và các yếu tố
Cấu trúc một hệ thống phục vụ công cộng được mô tả sơ bộ như sau:
Yêu cầu
***** [***….**]
hàng chờ


Dòng phục vụ
Các kênh phục vụ và

*****

chế độ PV

Yêu cầu không
thỏa mãn

Hình 1.1. Cấu trúc hệ thống phục vụ công cộng
a. Dòng yêu cầu đến hệ thống (dòng yêu cầu)
Dòng các đối tượng hướng đến hệ thống nhằm thỏa 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 qui luật Poisson và đặc biệt là dòng tuân theo qui luật Poisson dừng.
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
thỏa 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
qui luật phân phối xác suất nào đó.
Một trong những qui luật phổ biến là qui luật chỉ số (hay phân phối mũ),
với hàm mật độ: f (t )    e  t .

3


SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

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.
Qui luật phân phối xác suất của dòng phục vụ tùy thuộc qui 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 qui
luật chỉ số thì dòng phục vụ là dòng Poisson và ngược lại.
d. Hàng chờ
Đối với một số hệ thống, tùy thuộc chế độ tiếp nhận yêu cầu và tính chất
của các yêu cầu, có thể xuất hiện hàng chờ trước các kênh phục vụ, đó là dòng
các yêu cầu đến hệ thống nhưng chưa được phục vụ ngay, phải xếp hàng chờ
theo một nguyên tắc nào đó, ở đây ta chỉ xét hàng chờ đơn giản, không có một
sự phân biệt, ưu tiên nào.
e. Dòng các yêu cầu không được phục vụ
Đây là bộ phân yêu cầu đến hệ thống nhưng không được nhận phục vụ
vì một lý do nào đó.
f. Chế độ phục vụ
Chế đô phục vụ xác định cách thức làm việc của các kênh và cách thức
tiếp nhận các yêu cầu.
Có thể phân chia chế độ phục vụ theo một số cách thức khác nhau,
thông thường người ta chia các hệ thống thành các hệ thống không chờ (từ
chối) và có chờ; hệ thống phục vụ song song, độc lâp hay hợp tác, hệ thống
đơn hay hệ thống nối tiếp.
1.1.2. Tính chất của một dòng yêu cầu Poisson và Poisson dừng
a. Tính đơn nhất
Một dòng yêu cầu có tính đơn nhất nếu trong một khoảng thời gian đủ
nhỏ hầu như chắc chắn là không có quá một yêu cầu xuất hiện. Như vậy nếu ta

ký hiệu Pk (t , t ) là xác suất trong thời gian từ t đến t  t có k yêu cầu xuất
hiện thì:
P0 (t , t )  P1 (t , t )  1  (t ). ( (t ) là một vô cùng bé của t ).
4

SVTH: Huỳnh Thị Ly

(1.1)


Mô hình hệ thống phục vụ công cộng

b. Tính không hậu quả
Một dòng yêu cầu có tính không hậ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ố 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à:
Px (t , t )  Px ( t , t / k yêu cầu đã xuất hiện) với mọi k.

(1.2)

Định lý 1.1: 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:

a (t , t ) x e  a ( t ,t )
Px (t , t ) 
; x=0,1,2,3,…

x!

(1.3)

trong đó a(t , t ) là số trung bình yêu cầu xuất hiện từ t đến t  t.
Chứng minh: Xét dòng biến cố A theo thời gian
Gọi: Pn (t ) là xác suất A đã xuất hiện n lần tính đến thời điểm t
Pk (t , t ) là xác suất A xuất hiện k lần từ trong khoảng thời gian (t , t  t ) .

Như vậy xác suất A xuất hiện n lần tính đến t  t là: Pn (t  t ) .
Với tính đơn nhất của dòng biến cố ta có thể viết:
Pn (t  t )  Pn 1 (t ) P1[(t  t ) /(t , n  1)]  Pn (t ) P0 [(t  t ) /(t , n)] .

(i)

Trong đó: Pi [(t  t ) /(t , x)] là xác suất A xuất hiện i lần trong khoảng (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ó: Pi [(t  t ) /(t , x )]  Pi (t  t )
Tức là (i) trở thành:
Pn (t  t )  Pn 1 (t ) P1 (t  t )  Pn (t ) P0 (t  t )

Với giả thiết cường độ xuất hiện A là  (t ) ta có:
P1 (t  t )   (t )t
5

SVTH: Huỳnh Thị Ly

(ii)



Mô hình hệ thống phục vụ công cộng

P0 (t  t )  1   (t )t

Thay vào (ii) ta có:

Pn (t  t )  Pn 1 (t ) (t )t  Pn (t )(1   (t )t ).

(iii)

Từ (iii) ta có:
P0 (t  t )  P0 (t )
  P0 (t ) (t )
t

Với n=0

P0' (t )   P0 (t ) (t )

Khi t dần tới 0 ta có:

(iv)

d ln( P0 (t )) / dt    (t )
P0 (t )  e 

  ( t ) dt

Đặt: a(t )    (t )dt , ta có: P0 (t )  e  a ( t ) c
Ta thấy tại t=0, P0 (0)  1 vì vậy hằng số C=0

Cuối cùng ta có:
Với

n  1 thì

P0 (t )  e  a (t )

(v)

Pn (t  t )  Pn (t )
 Pn1 (t ) (t )  Pn (t ) (t )
t

Khi t dần tới 0 ta có: Pn' (t )  Pn1 (t ) (t )  Pn (t ) (t )

(vi)

Pn' (t )  Pn (t ) (t )  Pn1 (t ) (t )

Có thể giải hệ phương trình vi phân (vi) với điều kiện chuẩn là:


 P (t )  1 .
i

i 0

bằng cách thay (v) vào phương trình trong (vi) khi n=1 ta có:
P1' (t )  P1 (t ) (t )  e  a (t )  (t )


Nghiệm phương trình là:

P1 (t )  a (t )e  a (t )

(vii)

Từ (v) và (vii) ta có thể đưa ra công thức tổng quát:
Pk (t ) 

[a(t )]k e  a (t )
k!

Dễ dàng chứng minh công thức (viii) cho k bất kỳ.
Thật vậy: (viii) đúng với k=0 và 1.
Giả sử (viii) đúng với k=n-1 ta sẽ chứng minh (viii) đúng với k=n.
Với k=n ta có:

6

SVTH: Huỳnh Thị Ly

(viii)


Mô hình hệ thống phục vụ công cộng

Pn (t ) 

[a (t )]n e  a (t )
n!


dPn (t )

dt
dPn (t )

dt

n[a(t )] n1

da (t ) a ( t ) da (t )

a (t )e a (t )
e
dt
dt
n!

da (t )  a (t ) da (t )
e
[a (t )] n e a ( t )
dt
 dt
(n  1)!
n!

[a (t )]n 1

Hay: Pn' (t )  Pn1 (t ) (t )  Pn (t ) (t ) (chú ý rằng: a(t )    (t )dt ) (đpcm).
Khi thay t bằng t  t ta có: Pk (t , t ) 


[a (t , t )]k e  a ( t ,t )
k!

t  t

Với: a(t , t ) 

  (t )dt
t

Hệ quả: Nếu dòng yêu cầu phân phối Poisson với mật độ  (t ) thì thời gian
giữa hai lần liên tiếp xuất hiện yêu cầu phân phối chỉ số.
Thật vậy, nếu gọi T là thời gian xuất hiện một yêu cầu kể từ t*=0 thì
xác suất (T
P (T  t )  1  P0 (t *, t ) .

Với dòng yêu cầu phân phối Poission ta có:
P0 (t *, t ) 

[a(t )]0e a (t )
 e a (t )
0!

(1.4)

Vậy: F (T )  P(T  t )  1  e  a (t ) .
Đây chính là hàm phân phối xác suất của qui luật chỉ số.
c. Tính dừng

Dòng yêu cầu có tính dừng nếu như xác suất xuất hiện x yêu cầu trong
khoảng thời gian t không phụ thuộc vào điểm đặt của khoảng thời gian đó.
Tức là: Px (t , t )  Px (t ) với mọi t.
Dòng Poisson có tính chất dừng được gọi là dòng Poisson dừng.
Nói cách khác mật độ dòng yêu cầu không đổi: a(t )  t và ta có:
Px (t ) 

(t ) x e  t
x!

Trong đó:  là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian.
7

SVTH: Huỳnh Thị Ly

(1.5)


Mô hình hệ thống phục vụ công cộng

Nếu chọn t  1 ta có công thức của qui luật Poisson quen thuộc:
Px 

x e 

; x=0,1,2,3…

x!

(1.7)

1.1.3. Kiểm định giả thiết về phân phối Poisson – Tiêu chuẩn khi bình phương
Như trên ta đã biết các tính chất cơ bản để xác định qui luật của các
dòng yêu cầu. Tuy nhiên, thực tế hai tính chất nói trên và kể cả tính dừng của
dòng biến cố chỉ được xác định qua mô hình thống kê. Nói cách khác là chúng
ta không có một dòng Poisson lý thuyết mà hầu như chỉ có các dòng yêu cầu
gần Poisson. Với các bài toán thực tế, cần kiểm định sự phù hợp của các giả
thiết về phân phối của chúng, ta có thể sử dụng thống kê  2 . Để kiểm định giả
thiết dòng yêu cầu phân phối Poisson ta thực hiện.
- Chia thời gian thành các đơn vị nhỏ và tiến hành quan sát sự xuất hiện
các yêu cầu trong các khoảng thời gian đó. Ta nhận được bộ số liệu bao gồm
số yêu cầu xuất hiện trong một đơn vị thời gian: xi và số khoảng thời gian
tương ứng: ni. Nếu các khoảng thời gian có số yêu cầu tương ứng nhỏ hơn 5 ta
ghép các khoảng đó để có ni  5 , giá trị đại diện là giá trị trung bình.
- Tính giá trị thống kê
k

2 
i 1

(ni'  ni ) 2
ni'2

(1.8)

Trong đó: ni' là giá trị tần số lý thuyết nhận được từ phân phối Poisson
k

với trung bình là   
i 1

ni xi
, k là số nhóm giá trị xi , ni là tần số quan sát; n là
n

tổng số quan sát.


Ví dụ 1.1. Khi quan sát số khách hàng đến một cửa hàng, người ta thu

được số liệu sau:
Số khách

0

1

2

3

4

7

Số khoảng thời gian

21

23

10

4

1

1

Với mức ý nghĩa   0.05 kiểm định số khách đến cửa hàng phân phối
Poisson.
8

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

Giải:
Để kiểm tra giả thiết số khách đến cửa hàng phân phối Poisson ta tiến
hành các thủ tục sau:
k

- Tính giá trị quan sát   
i 1

ni xi
; k là số nhóm giá trị xi , ni là tần số
n

quan sát; n là tổng số quan sát.
- Dùng giá trị này ước lượng giá trị trung bình của phân phối, từ đó tra
bảng Poisson P( ) với các giá trị có tần số thấp đã được ghép lại đủ
điều kiện ni  5 và lập bảng.
- Chọn một mức ý nghĩa  ; nếu giá trị thống kê  qs 2   2 ( ; n ) ; trong đó
n  k  2 thì giả thiết dòng yêu cầu phân phối Poisson không bị bác bỏ.

Với các quan sát trên ta có bài giải sau:
+ Kiểm định
Giả thiết H 0 : Dòng khách hàng đến cửa hàng phân phối Poisson
k

+ Giá trị trung bình   
i 1

ni xi
 1.1
n

+ Bảng tính các tần số lý thuyết ni  nPi
Bảng I.1. Tính toán giá trị các tần số lý thuyết
Số yêu cầu

Tần số

xi

quan sát ni

0

21

0.33287

19.9722

0.002648

1

23

0.36616

21.9696

0.00219972

2

10

0.20139

12.0834

0.029728

3

4

0.07384

4

1

0.02031

5

0

0.00447

6

0

0.00082

7

1

0.00013

Pxi

n=60

lý thuyết ni

5.9742

(ni  ni ) 2
2
ni

0.00002

0.03459

9

SVTH: Huỳnh Thị Ly

Tần số


Mô hình hệ thống phục vụ công cộng

k

+ Giá trị quan sát  qs 2  
i 1

(ni'  ni ) 2

 0.03459
ni' 2

+ Giá trị lý thuyết  2 ( ; n )   2 ( 0.05; 4)  11,0705 (với n  k  2 )
+  qs 2   2 ( ; n ) với mức ý nghĩa   0.05
Vậy giả thiết dòng yêu cầu Poisson không bị bác bỏ. Hay có thể xem là
dòng khách đến cửa hàng phân phối Poisson với trung bình   1.1
1.2.

QUÁ TRÌNH XẾP HÀNG

1.2.1. Khái niệm quá trình xếp hàng
Mô hình tổng quát của lý thuyết xếp hàng là khách hàng đến ở một thời
điểm ngẫu nhiên nào đó và yêu cầu được phục vụ theo một loại nào đó. Giả
thiết khoảng thời gian đến của khách hàng và thời gian phục vụ có thể ngẫu
nhiên.

Hình 1.2. Mô hình tổng quát của lý thuyết xếp hàng
Đặt tn là khoảng thời gian giữa hai lần đến của khách hàng thứ n và
n+1.
Ta giả định rằng tất cả các t n (n  1) là độc lập và có cùng phân bố. Vì
vậy việc đến của các khách hàng tạo thành một hàng kế tiếp nhau với tốc độ

10

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

đến là  

1
. Ta gọi quá trình t n , n  1,2,... là quá trình đến. Khách hàng
E ( t1 )

đến hệ thống yêu cầu các server của hệ thống phục vụ. Ta giả sử rằng khách
hàng thứ n cần một thời gian phục vụ là (n  1) , tất cả các s n độc lập và có
cùng phân bố. Quá trình t n ; n  1,2,... được gọi là quá trình phục vụ. Ta cũng
giả thiết rằng các thời gian đến trung gian độc lập với thời gian phục vụ.
Quá trình xếp hàng được phân loại dựa vào các tiêu chí sau:
+ Phân bố của quá trình đến (input process) l q t t 0
+ Phân bố của thời gian phục vụ (service distribution) sn ; n  1,2,...
+ Nguyên tắc phục vụ: Các khách hàng đến được sắp xếp vào hàng đợi
đến lượt được phục vụ. Để đơn giản ta giả thiết chỉ có một hàng. Tuy nhiên
trong nhiều trường hợp có thể mở rộng cho nhiều hàng cùng hoạt động song
song. Nếu độ dài hàng có đặt ngưỡng thì các đơn vị đến hàng khi hàng đầy
vượt ngưỡng sẽ bị loại. các khách hàng được chọn để phục vụ 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.
+ 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 song song.
1.2.2. Một số đặc trưng của hệ thống xếp hàng
Bất kỳ một hệ thống xếp hàng nào cũng được mô tả bởi các đặc trưng
sau:
o Quá trình đến: Nếu các khách hàng đến hàng đợi vào các thời điểm t1,
t2, t3,…, tj thì các biến số ngẫu nhiên Pj=tj- tj-1 được gọi là các thời điểm giữa
các lần đến. Các thời điểm này thường được giả thiết là các biến ngẫu nhiên
độc lập và được phân bố đồng nhất. Các quá trình đến thông dụng nhất là:

+ M=quá trình mũ (là quá trình Markov hay quá trình không có bộ
nhớ)
+ Er (Erlang_r)= là quá trình Erlang bậc r: trung tâm dịch vụ ở đây
được biểu diễn bởi một dãy có r giai đoạn trễ, mỗi giai đoạn có cùng thời gian
11

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

dịch vụ trung bình và có phân phối mũ. Không có các hàng đợi tại bất cứ một
giai đoạn phục vụ nào vì yêu cầu tiếp theo sẽ không được phục vụ nếu như
yêu cầu trước đó chưa hoàn thành dịch vụ ở tất cả r_giai đoạn.
+ Hr (hyperexponential)= quá trình siêu số mũ bậc r: mỗi giai đoạn trễ
trong mô hình Erlang_r có các thời gian dịch vụ khác nhau với r giai đoạn
phục vụ được thực hiện song song mà không phải là nối tiếp tuy nhiên nó cung
cấp chỉ một dịch vụ tại một thời điểm. Phân phối này có độ phân tán (phương
sai) lớn hơn phân phối mũ.
+ D (deterministic) = quá trình tất định: khoảng thời gian giữa hai
khách hàng đến hay rời liên tiếp là bằng nhau.
+ G (general) = quá trình chung: các khoảng thời gian đến hay rời
không được đặc trưng bởi bất kỳ một phân phối nào bởi vì quá trình đến hay
rời là một quá trình hoàn toàn tùy ý.
o Quá trình phục vụ: thời gian mà mỗi công việc tiêu tốn cần thiết tại
server gọi là thời gian phục vụ (server time). Các thời gian phục vụ thường
được giả thiết là các biến số ngẫu nhiên. Các quá trình phục vụ thông dụng
nhất cũng giống như thời gian đến.
o Số lượng các bộ server: số các server phục vụ cho xếp hàng. Dung
lượng bộ đệm hay dung lượng lưu trữ tại hàng đợi.

o Quy mô mật độ: tổng số các yêu cầu hiện đang có mặt tại hàng đợi.
Quy mô mật độ luôn là hữu hạn trong hệ thống thực. Tuy nhiên, phân tích hệ
thống với quy mô mật độ lớn sẽ dễ dàng hơn nếu chúng ta giả thiết rằng quy
mô mật độ là vô hạn.
o Các quy tắc phục vụ.
1.2.3. Mô hình hàng chờ
Trong các hệ thống xếp hàng thường xuyên diễn ra hai quá trình: Quá
trình nảy sinh các yêu cầu (một yêu cầu còn được coi là một tín hiệu cần được
phục vụ) và quá trình phục vụ các yêu cầu ấy. Song trong quá trình phục vụ
của các hệ thống, do nhiều nguyên nhân khác nhau, thường xảy ra các tình
trạng sau: Trong nhiều trường hợp, quá trình phục vụ không đáp ứng các yêu
12

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

cầu và do đó dẫn đến kết quả là nhiều yêu cầu phải chờ để được phục vụ.
Ngược lại, trong một số tình huống khác, khả năng phục vụ của hệ thống vượt
quá số yêu cầu cần được phục vụ, với kết quả là hệ thống không sử dụng hết
phương tiện phục vụ.
Người quản trị hệ thống phải xác định cho được những chi phí vô ích.
Những chi phí vô ích này tạo thành tính không hiệu quả của hệ thống. Có hai
dạng chi phí vô ích:
o Chi phí của khách hàng phải xếp hàng chờ trong hệ thống trước khi
được phục vụ. Chi phí này có thể hiểu được một cách tương đương là trong
cùng một khoảng thời gian quản lý T, nếu khách hàng chờ lâu thì lượng khách
hàng xếp hàng chờ tới trong khoảng thời gian T giảm.
o Chi phí cho các trạm phục vụ khách hàng nhưng lại không có khách

hàng. Như vậy trong khoảng thời gian quản lý T, tỷ lệ thời gian phục vụ khách
hàng tạo thành hiệu suất U của một trạm phục vụ. Hiệu suất càng gần 1 thì chi
phí vô ích càng nhỏ và ngược lại, nếu hiệu suất gần bằng 0 thì chi phí vô ích
càng lớn.
Đây là hai loại chi phí ngược nhau: nếu giảm chi phí vô ích từ phía
khách hàng tức là giảm thời gian chờ của khách hàng thì phải tăng số trạm
phục vụ; và như vậy làm tăng chi phí vô ích từ phía phục vụ. Ngược lại nếu
muốn giảm chi phí vô ích từ phía phục vụ thì phải giảm số trạm phục vụ
nhưng điều này lại làm tăng thời gian xếp hàng chờ của khách hàng. Rõ ràng
muốn tăng tính hiệu quả hoạt động của hệ thống thì cần phải cân đối tổng thể
từ hai loại chi phí này.
Vì vậy bài toán đặt ra là:
+ Phân tích bản chất của quá trình diễn ra trong hệ thống xếp hàng chờ và
thiết lập các mối liên hệ về lượng giữa các đặc trưng của các quá trình ấy.
Điều đó có nghĩa là cần thiết lập hay lựa chọn một mô hình xếp hàng chờ phản
ánh được bản chất của hệ thống.
+ Trên cơ sở các mối liên hệ đã được xây dựng và các số liệu thu được từ
hệ thống, cần tính toán, phân tích và đưa ra các quyết định nhằm tìm ra các giá
13

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

trị thích hợp cho các tham số điều khiển / thiết kế của hệ thống để thiết kế hay
điều khiển các hoạt động của hệ thống hoạt động một cách hiệu quả hơn.
1.2.4. Các yếu tố cơ bản của hệ thống hàng chờ
Hệ thống hàng chờ tổng quát được minh họa như trên hình sau

Input

Hàng
chờ

Dòng tín hiệu đến

Output
KÊNH PHỤC VỤ
Dòng tín hiệu ra

Hình 1.3. Hệ thống hàng chờ
Các yếu tố cơ bản của hệ thống hàng chờ bao gồm:
a. Bố trí vật lí của hệ thống
Hệ thống hàng chờ có một số dạng bố trí vật lí (physical layout) như
minh họa trên hình …
Single Channel – single server (một kênh phục vụ, một loại dịch vụ)

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

Dịch vụ 1

Dịch vụ 2

Dịch vụ 3

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

Multi Channel – Multi server (Nhiều kênh phục vụ, nhiều loại dịch vụ)

14

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

Dịch vụ 1

Dịch vụ 2

Hình 1.4. Các dạng hệ thống hàng chờ
Trên hình 1.3, 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ụ của hệ thống là cách thức nhận các yêu cầu vào
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ừ chối hoặc phải chờ và giới hạn của thời gian chờ.
Một số nguyên tắc phục vụ thường được áp dụng trong các hệ thống
hàng chờ là FIFO (first in first out), LIFO (Last in first out), FCFS (First come
first serve), có ưu tiên , không ưu tiên,…
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ụ
Số tín hiệu đến trong một khoảng thời gian cũng như thời gian phục vụ
từng tín hiệu nói chung là những biến ngẫu nhiên, và do đó, chúng tuân theo
các quy luật phân phối xác suất. Các quy luật phân phối xác suất này được

thiết lập căn cứ số liệu thực nghiệm thu thập từ các quan sát, thí ngiệm, hay từ
cơ sở dữ liệu sẵn có.
Đối với dòng tín hiệu đầu vào, thông thường chúng ta giả sử rằng số tín
hiệu đến trong vòng một khoảng thời gian nào đó được ấn định trước (1 phút,
3 phút, 5 phút, 30 phút,…) tuân theo luật phân phối Poisson P( ). Ở đây, tham
số  đặc trưng cho tín hiệu đến (trung bình) trong khoảng thời gian trên. Ví
dụ, số khách vào siêu thị (trung bình) là 100 người trong 1 giờ. Có nghĩa là, số
15

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

khách vào siêu thị là biến ngẫu nhiên X có phân phối Poisson
với   100. Hoặc, với số cuộc gọi (trung bình) đến tổng đài trong vòng 1 phút
là 3 (tín hiệu) thì có X ~ P(3).
1.2.5. Phân tích hàng chờ
Có các phương pháp phân tích hàng chờ như sau:
o Phân tích giải tích
o Quá trình mô phỏng
o Cả hai phương pháp trên
Phương pháp để giải mô hình hàng chờ 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 chỉ 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 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 chờ đượ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 lời giải tốt nhất, nó tỏ ra rất thành công khi
giải quyết nhiều bài toán hàng đợi nảy sinh từ thực tiễn.
Các bước cần tiến hành khi áp dụng phương pháp mô phỏng bao gồm:
16

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

Bước 1: Xác định bài toán hay hệ thống hàng đợi cần mô phỏng và mô hình
mô phỏng.
Bước 2: Đo và thu thập số liệu cần thiết để khảo sát thống kê các số đặc trưng
/ các yếu tố cơ bản của mô hình.
Bước 3: Chạy mô phỏng kiểm chứng (test simulation) mô hình và so sánh kết
quả kiểm chứng với các kết quả đã biết được trong thực tế. Phân tích kết quả
chạy mô phỏng kiểm chứng, nếu cần thì phải sửa lại phương án đã được đánh
giá qua chạy mô phỏng.
Bước 4: Chạy mô phỏng kiểm chứng phương án cuối cùng và kiểm tra tính

đúng đắn của mọi kết luận về hệ thống thực tế được rút ra sau khi chạy mô
phỏng. Triển khai hoạt động của hệ thống hàng đợi dựa trên phương án tìm
được.
Từ những phân tích trên đây có thể thấy Lí thuyết xếp hàng còn gọi là
Lí thuyết hệ phục vụ công cộng hay Lí thuyết dịch vụ đám đông là lĩnh vực
quan trọng của Toán ứng dụng /Vận trù học. Nhiều bài toán thực tế trong các
lĩnh vực hệ thống dịch vụ, kĩ thuật,… đã được giải quyết thành công nhờ áp
dụng phương pháp mô phỏng mô hình hàng đợi.
1.2.6. Ký hiệu Kendall
Kendall đã đưa ra 6 tham số để phân biệt hệ thống này với hệ thống
khác: A/B/s/k/m/q. Vị trí của các tham số là tầm quan trọng của tham số ảnh
hưởng tới hệ thống.
Vị trí số 1: tham số A đặc trưng cho phân phối khách hàng đi tới hệ thống.
Vị trí số 2: tham số B đại diện cho phân phối của thời gian phục vụ khách
hàng.
Vị trí số 3: tham số s là các trạm phục vụ khách hàng.
Vị trí số 4: tham số k giới hạn sức chứa của hệ thống đối với số khách hàng
phải đợi.
Vị trí số 5: tham số m mô tả lực lượng của quần thể nơi mà khách hàng phát
sinh. Lực lượng có thể vô hạn cũng như hữu hạn với số lượng nhiều hoặc ít.
Vị trí số 6: tham số q đại diện cho các quy tắc áp dụng để phục vụ khách hàng.
17

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

1.2.7. Các chỉ tiêu đánh giá
Một số các chỉ tiêu đánh giá (hay các thông số hiệu năng) quan trọng

thường dung khi phân tích một mạng, đó là:
o Tốc độ đến của các khách hàng (  ):


A
T

Trong đó: A là số các khách hàng trong hệ thống
T là thời gian quan sát (hay thời gian đo)
Trong khi A đếm số các yêu cầu đến hàng đợi thì  biểu diễn tốc độ mà
các yêu cầu đó đến. Đơn vị đo của tốc độ là: khách hàng /đơn vị thời gian. Ví
dụ, nếu một hệ thống điều hành được cung cấp công cụ để đếm số yêu cầu về
phục vụ một số tài nguyên (CPU, đĩa…) thì tổng số lần đếm trong một đơn vị
thời gian chính là tốc độ đến.
o Thông lượng (throughput) của hệ thống xếp hàng là tốc độ trung bình
các khách hàng chuyển qua hệ thống:
Throughput  X 

C
(ở đây C là số khách hàng hoàn thành dịch vụ).
T

Đại lượng này cũng biểu thị tốc độ. Do nó là một đại lượng có thể đo tốc
độ hoàn thành dịch vụ một cách trực tiếp giống như tốc độ đến. Trong một số
trường hợp ta sẽ thấy tốc độ đến hệ thống của khách hàng  sẽ bằng với thông
lượng X. Dạng biểu diễn khác:


Throughput  Y    (n) Pn . (khách hàng/giây)
n 1

Trong đó Pn là xác suất trạng thái cân bằng khi hệ thống có n khách hàng
trong hệ thống. Thông lượng trung bình là trung bình trọng số của các tốc độ dịch
vụ  (n) còn các xác suất trạng thái cân bằng Pn được dùng như các trọng số.
o Số khách hàng trung bình trong hệ thống xếp hàng:


Q  n   nPn (khách hàng)
n 1

18

SVTH: Huỳnh Thị Ly


Mô hình hệ thống phục vụ công cộng

Độ đo này là trung bình trọng số của số các khách hàng trong hệ thống
xếp hàng với các xác suất trạng thái được dùng như các trọng số. Cách biểu
diễn:
Q

t
T

Trong đó: t là tổng thời gian thường trú của tất cả các khách hàng đã
hoàn thành dịch vụ.
o Độ trễ thời gian trung bình (mean time delay) hay thời gian đáp ứng
(R_Response time):
t

(giây)
C

Rt 

Trong đó: t là tổng thời gian thường trú của tất cả các khách hàng đã hoàn
thành dịch vụ.
Hay R=W+S (thời gian thường trú bằng tổng thời gian phục vụ và thời
gian mà khách hàng đó phải đợi trước khi được phục vụ).
o Thời gian phục vụ (service time) được định nghĩa là:
S

B
C

Trong đó: B là tổng thời gian hệ thống bận trong khoảng thời gian T. Đại
lượng này không phải là tốc độ mà nó biểu diễn tổng thời gian trung bình để
hoàn thành phục vụ một yêu cầu đến.
o Thời gian đợi (W_waiting time): thời gian đợi của một khách hàng
trước khi được phục vụ được xác định:
W=SQ
Trong đó Q là số các khách hàng trung bình trong hàng đợi, S_tốc độ dịch vụ.
o Độ hiệu dụng (utilitization) hay là xác suất để hệ thống xếp hàng là
không rỗng và tất cả các server bận (trường hợp nhiều server):
U  1  P0

Ngoài ra còn có các định nghĩa khác như là độ hiệu dụng trung bình
U

B

 S
T
19

SVTH: Huỳnh Thị Ly