Mục lục
Lời mở đầu 3
Chú giải những kí hiệu viết tắt 5
1. Sơ l-ợc về sơ đồ mạng CPM/PERT 6
1.1. Các phần tử của sơ đồ mạng . . . . . . . . . . . . . . . . . . . . 6
1.2. Các chỉ tiêu thời gian của sự kiện . . . . . . . . . . . . . . . . . . 8
1.3. Các chỉ tiêu thời gian của công việc . . . . . . . . . . . . . . . . 9
2. Một số kết quả quan trọng của lý thuyết xác suất 12
2.1. Căn bậc hai của ma trận . . . . . . . . . . . . . . . . . . . . . . 12
2.2. Vec-tơ ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3. Phân phối chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4. Định lý giới hạn trung tâm . . . . . . . . . . . . . . . . . . . . . 17
3. Khảo sát tính ngẫu nhiên trên sơ đồ PERT 19
3.1. Tính ngẫu nhiên của chỉ tiêu thời gian trên sơ đồ PERT . . . . . . 19
3.2. Phân tích xác suất hoàn thành dự án . . . . . . . . . . . . . . . . 22
i
3.2.1. Phân tích trên dự án có một đ-ờng găng . . . . . . . . . . 23
3.2.2. Phân tích trên dự án có kđ-ờng găng . . . . . . . . . . . 27
3.2.3. Xác suất hoàn thành trên dự án có hai đ-ờng găng . . . . . 32
Kết Luận 37
Tài liệu tham khảo 38
ii
Lời mở đầu
Sơ đồ PERT (Program and Evaluation Review Technique) là một dạng
của sơ đồ mạng l-ới, một ph-ơng pháp của toán kinh tế sử dụng trong công
tác lập kế hoạch và điều khiển sản xuất. Vấn đề khác biệt chủ yếu giữa
PERT và các ph-ơng pháp sơ đồ mạng l-ới khác đó là tính ngẫu nhiên của
chỉ tiêu thời gian hoàn thành công việc trên sơ đồ, đấy cũng là lí do mà
PERT trở lên phổ biến, áp dụng rộng rãi ở nhiều lĩnh vực khác nhau và đã
đem lại những kết quả có ý nghĩa rất lớn trong thực tiễn.
Khi thời gian hoàn thành công việc có tính ngẫu nhiên, thì thời gian hoàn

Ch-ơng 2: Trình bày các kiến thức của lý thuyết xác suất dùng để khảo
sát, phân tích sơ đồ mạng l-ới, trong đó đáng chú ý là hệ quả (2.4.1), một
hệ quả đã đ-ợc xây dựng và có áp dụng trực tiếp trong đề tài.
Ch-ơng 3: Nghiên cứu mối quan hệ giữa xác suất hoàn thành dự án và
thời gian dự định, trong đó có xét các tr-ờng hợp dự án có một đ-ờng găng
và dự án có nhiều đ-ờng găng. Đây là ch-ơng đ-a ra kết quả chính của đề
tài.
4
.
Chú giải những kí hiệu viết tắt
CPM: Critical path methol- ph-ơng pháp đ-ờng găng.
PERT: Program and Evaluation Review Technique- Kỹ thuật đánh giá và
tự kiểm tra.
5
Ch-ơng 1.
Sơ l-ợc về sơ đồ mạng CPM/PERT
Sơ đồ mạng là một mô hình thể hiện toàn bộ dự án thành một thể
thống nhất. Sơ đồ mạng mô tả mối quan hệ liên tục giữa các công việc,
nối kết các công việc và sự kiện theo một thứ tự tr-ớc sau giữa chúng. Có
nhiều ph-ơng pháp sơ đồ mạng, nh-ng đ-ợc dùng phổ biến hơn cả là sơ
đồ CPM (Critical path methol- ph-ơng pháp đ-ờng găng) và sơ đồ PERT
(Program and Evaluation Review Technique- Kỹ thuật đánh giá và tự kiểm
tra). Về cơ bản, hai ph-ơng pháp này là giống nhau về hình thức, trình
tự lập mạng, chỉ khác nhau về tính toán thời gian. Thời gian trong CPM
là một đại l-ợng xác định, đ-ợc tính từ định mức lao động, còn thời gian
trong PERT không căn cứ vào định mức lao động để tính mà phụ thuộc vào
nhiều yếu tố ngẫu nhiên.
1.1. Các phần tử của sơ đồ mạng
Trên sơ đồ mạng có hai đối t-ợng chính là mũi tên và các nút (hình
tròn), mũi tên biểu thị cho trình tự thực hiện của công việc, các nút biểu

t
s
j
) là thời điểm sớm nhất để kết thúc các công việc đi vào sự kiện j, hoặc
sớm nhất để bắt đầu các công việc đi ra khỏi sự kiện j. Công thức tính:
- Nếu đứng tr-ớc j, chỉ có sự kiện i thì t
s
j
= t
s
i
+ t
ij
;
- Nếu đứng tr-ớc j, có nhiều sự kiện thì t
s
j
= max(t
s
i
+ t
ij
);
- Sự kiện khởi công có t
s
j
=0.
8
b.Thời điểm muộn của sự kiện: Tại sự kiện j, thời điểm muộn( kí hiệu
là t

c. Thời gian dự trữ của sự kiện: Tại sự kiện j, thời gian dự trữ ( kí hiệu
là d
j
) là khoảng thời gian chênh lệch giữa thời điểm muộn và thời điểm
sớm. Công thức tính: d
j
= t
m
j
t
s
j
, ta có d
j
0, nếu d
j
=0thì sự kiện j
đ-ợc gọi là sự kiện găng.
1.3. Các chỉ tiêu thời gian của công việc
Công việc A bắt đầu từ sự kiện đỉnh i kết thúc ở sự kiện đỉnh j kí
hiệu là công việc ij, trên nó có sáu chỉ tiêu thời gian nh- sau:
a. Thời điểm khởi công sớm của công việc: là thời điểm sớm nhất để bắt
đầu công việc ij, nó chính là thời điểm sớm nhất để sự kiện i xảy ra, kí
hiệu là: t
ks
ij
= t
s
i
.

ij
= t
hm
ij
t
ij
.
e. Thời gian dự trữ chung của công việc: là dự trữ chung của tất cả các
công việc không găng liên quan kề nhau trên đ-ờng đi dài nhất từ sự kiện
khởi công đến sự kiện kết thúc, kí hiệu là: d
c
ij
= t
m
j
t
ij
t
s
i
. Nếu d
c
ij
=0,
thì công việc ij là công việc găng.
d. Thời gian dự trữ riêng của công việc: là thời gian tối đa có thể trì
hoãn của công việc ij mà không ảnh h-ởng đến thời điểm kết thúc muộn
của các công việc liền tr-ớc, cũng nh- thời điểm bắt đầu sớm của các công
việc liền sau, kí hiệu là: d
r

Ch-ơng 2.
Một số kết quả quan trọng của lý thuyết
xác suất
2.1. Căn bậc hai của ma trận
Cho A là một ma trận đối xứng cấp n ì n. Khi đó A có n cặp giá
trị riêng và vec-tơ riêng

1
,e
1
;
2
,e
2
; ;
n
,e
n
.
Các vec-tơ riêng có thể chọn sao cho nó tạo thành một cơ sở trực chuẩn
của R
n
, tức là
e
T
1
e
1
= = e
T

các số thực không âm.
Mệnh đề 2.1.2. Nếu
1
,e
1
;
2
,e
2
; ;
n
,e
n
là n cặp giá trị riêng và vec-tơ
riêng của ma trận đối xứng A thì A có thể biểu diễn d-ới dạng:
A =
1
e
1
e
T
1
+ +
n
e
n
e
T
n
.

A
1/2
= P
1/2
P
T
sẽ thỏa mãn điều kiện A
1/2
A
1/2
= A. Do đó A
1/2
đ-ợc gọi là ma trận căn
bậc hai của A>0.
Ta có các hệ thức sau:
a) (A
1/2
)
T
= A
1/2
;
b) (A
1/2
)
1
=
n

1

; A
1/2
A
1/2
= A
1
.
2.2. Vec-tơ ngẫu nhiên
Vec-tơ ngẫu nhiên X =[X
1
, , X
n
] là một vec-tơ mà mỗi thành phần
X
1
, , X
n
của nó là một biến ngẫu nhiên. T-ơng tự nếu X =[X
ij
] là ma
13
trận cấp n ì p mà các thành phần X
ij
là các biến ngẫu nhiên sẽ đ-ợc gọi
là ma trận ngẫu nhiên.
Định nghĩa 2.2.3 (Vec-tơ trung bình và ma trận ph-ơng sai).
Cho X =[X
1
, , X
n

ij
= E(X
i
à
i
)(X
j
à
j
) đ-ợc gọi là hiệp ph-ơng sai của biến X
i
và X
j
;
d)
ij
=
ij
/


ii

jj
đ-ợc gọi là hệ số t-ơng quan của biến X
i
và X
j
.
Nếu (X

i
,x
j
)dx
i
dx
j
=
+


+


x
i
x
j
f
ij
(x
i
,x
j
)dx
i
dx
j
à
i

= diag(


11
, ,


nn
) và V
1/2
=
diag(1/


11
, , 1/


nn
) ta có:
P = V
1/2
V
1/2
=V
1/2
PV
1/2
2.3. Phân phối chuẩn
Phần này chúng ta sẽ trình bày một số kết quả quan trọng của phân

2

2
có thể viết d-ới dạng (x à)
T
(
2
)
1
(x à). Cách viết
này có thể dùng để định nghĩa phân phối chuẩn nhiều chiều.
Định nghĩa 2.3.5 (phân phối chuẩn nhiều chiều). Vec-tơ X đ-ợc gọi là
có phân phối chuẩn không suy biến pchiều nếu X =(X
1
, , X
p
)
T
có
15
hàm mật độ
f(x)=
1
(2)
p/2
||
1/2
exp{
1
2

=(à
1
, , à
p
)
T
và cov(X)=, khi đó ta kí
hiệu X N(à, ).
Một số tính chất:
a) Nếu X N(à, ) thì mọi tập con các thành phần của X cũng có phân
phối chuẩn, đặc biệt X
i
N(à
i
,
ii
)-chuẩn một chiều.
b) Nếu X N(à, ) và
ij
=0(i = j) thì các thành phần X
1
, , X
n
trong vec-tơ X là độc lập.
c) Một vec-tơ X =(X
1
, , X
p
)
T

1
,X
2
). Khi đó
12
=

12


11

22
là hệ số t-ơng quan của
X
1
và X
2
và
=


11

12

12

22


=
1
1
2
12


1
11

12
(
11

22
)
1/2

12
(
11

22
)
1/2

1
22

Do đó


12


11

22

1
22



x
1
à
1
x
2
à
2

=
1
1
2
12

x
1



22

2

Vì vậy, mật độ chuẩn hai chiều của (X
1
,X
2
) là
f(x
1
,x
2
)=
1
2{
11

22
(1
2
)}
1/2

exp

1
2(1

22
+(
x
2
à
2


22
)
2

2.4. Định lý giới hạn trung tâm
Xét một dãy các biến ngẫu nhiên X
1
,X
2
, (kí hiệu là dãy {X
k
}), ta
nói dãy {X
k
} tuân theo định lý giới hạn trung tâm nếu dãy phân phối của
biến ngẫu nhiên
S
n
ES
n

DS

k
|
2
.I
(|X
k
à
k
|B
n
)
] 0 khi n
trong đó à
n
= EX
n
,B
2
n
= D(S
n
),n 1, thì dãy {X
k
} tuân theo định lý
giới hạn trung tâm
Định lý giới hạn trung tâm Lindeberg đ-a ra một kết quả áp dụng
tổng quát trong lý thuyết xác suất, để cho phù hợp với nội dung nghiên cứu
của đề tài chúng ta xây dựng một tr-ờng hợp riêng của nó nh- sau:
Hệ quả 2.4.1. Giả sử {X
k

DS
n
)=, k.
Suy ra L
n
()=0với mọi >0 và n đủ lớn, vậy dãy {X
k
} tuân theo định
lý giới hạn trung tâm.
18
Ch-ơng 3.
Khảo sát tính ngẫu nhiên trên sơ đồ
PERT
Trong ch-ơng này, chúng tôi sẽ áp dụng các kết quả xác suất ở ch-ơng
2 để phân tích tính ngẫu nhiên trên sơ đồ PERT và khảo sát xác suất hoàn
thành dự án.
3.1. Tính ngẫu nhiên của chỉ tiêu thời gian trên sơ đồ
PERT
Một khi đã xác định đ-ợc toàn bộ các công việc của dự án, chúng
ta cần xác định thời gian cần thiết hoàn thành mỗi công việc. Thông tin
này đ-ợc sử dụng trong việc tính toán tổng thời gian cần có để hoàn thành
dự án và trong điều hành từng công việc cụ thể. Đối với dự án lặp đi lặp
lại nh- các dự án xây dựng, duy tu, các nhà quản trị có thể sử dụng dữ
liệu quá khứ và kinh nghiệm cần thiết để -ớc tính thời gian hoàn thành của
mỗi công việc một cách chính xác. Tuy nhiên, đối với các dự án mới hay
chỉ làm một lần, thì việc -ớc tính thời gian của mỗi công việc có phần khó
19
khăn hơn. Quả thực, trong nhiều tr-ờng hợp, thời gian hoàn thành của mỗi
công việc là không chắn chắn và tốt nhất chúng nên đ-ợc biểu diễn bằng
tính ngẫu nhiên, khi đó thời gian hoàn thành của mỗi công việc đ-ợc xem

gian hoàn thành công việc, do đó ch-a đủ để xác định thời gian kỳ vọng
t
e
(ij) và ph-ơng sai
2
(ij) đặc tr-ng cho độ biến động của thời gian hoàn
thành công việc so với thời gian kỳ vọng. Bằng tính toán thực nghiệm,
ng-ời ta đ-a ra giả thiết (b a) khoảng chênh lệch giữa giá trị cận trên và
cận d-ới của phân phối xác suất xấp xỉ bằng 6 lần độ lệch chuẩn. Do vậy,
ph-ơng sai của thời gian hoàn thành công việc đ-ợc xác định bằng công
thức:

2
(ij)=(
b a
6
)
2
Tiếp tục, giả thiết phân phối xác suất của thời gian hoàn thành công việc
đều là phân phối xác suất Beta (đây là phân phối không có hình dạng nhất
định nên nó phù hợp với việc mô tả thời gian của các công việc). Để tính
thời gian kỳ vọng t
e
của thời gian hoàn thành công việc, chúng ta sử dụng
21
công thức sau:
t
e
(ij)=
a +4m + b

sử có n công việc A
i
trên đ-ờng găng theo thứ tự là:
G : A
1
A
2
A
n
Gọi X
k
là thời gian hoàn thành công việc A
k
thuộc đ-ờng găng (G), giả
sử dãy các biến ngẫu nhiên X
k
độc lập, khi đó ta có kết quả sau:
Định lý 3.2.2. Dãy các biến ngẫu nhiên độc lập {X
k
} tuân theo định lý
giới hạn trung tâm, tức là dãy biến ngẫu nhiên
S
n
ES
n

DS
n
(S
n

2
=0 (k 1), và dãy D(S
n
)
không bị chặn.
Theo hệ quả (2.4.1), ta có dãy các biến ngẫu nhiên (X
k
) tuân theo định lý
giới hạn trung tâm.
23
Khi đó, nếu ta đặt
G =
S
n
E(S
n
)

D(S
n
)
thì đại l-ợng ngẫu nhiên G xấp xỉ phân phối chuẩn tắc N(0, 1).
Nếu gọi D là thời gian dự kiến dự án hoàn thành, thì xác suất để dự án
hoàn thành là:
P

S
n
D



=
D E(S
n
)

D(S
n
)
, và (u

) là hàm phân phối của N(0, 1).
Nhận xét: Từ đẳng thức (3.2.1) ta có thể đ-a ra mối quan hệ giữa xác
suất hoàn thành dự án (P ) và thời gian dự định (D):
- Cho thời gian dự kiến hoàn thành dự án, hãy tính xác suất hoàn thành
dự án t-ơng ứng(-quan hệ thuận).
- Hãy tìm khoảng thời gian nhỏ nhất để đạt đ-ợc yêu cầu dự án hoàn
với một xác suất cho tr-ớc(-quan hệ ng-ợc).
Ví dụ 3. Cho một dự án có trình tự tiến hành và các thông số thời gian
nh- trong bảng d-ới đây, hãy:
a) Tính xác suất để dự án hoàn thành nếu mong muốn dự án hoàn thành
trong vòng 16 tuần.
b) Nếu yêu cầu dự án hoàn thành với xác suất 0, 99 thì phải cần khoảng
thời gian tối tiểu là bao nhiêu để thực hiện.
24
Stt
Tên công
việc
Thứ tự tiến
hành

2
1
A 2 4/36
2 B 3 4/36
3
C 2 4/36
4
D 4 16/36
5 E 4 36/36
6
F 3 64/36
7 G 5 64/36
8 H 2 4/36
Sơ đồ mạng của dự án thể hiện nh- sau:
25