Chương mở đầu
GIỚI THIỆU CHUNG VỀ NHIỆM VỤ
Đề tài “Điều hành dự án bằng phương pháp PERT-PCM và ứng dụng giải
bài tốn lập lịch thi công công trình”, bao gồm
- Tìm hiểu phương pháp PERT-PCM (phương pháp sơ đồ mạng lưới).
- Ứng dụng giải bài tốn lập lịch thi công công trình.
+ Lưu trữ lịch thi công các dự án
+ Cho biết thới gian bắt đầu một dự án và thời gian kết thúc dự án
+ Thêm một số hạng mục khi dự án đang được thi công
+ Bỏ một số hạng mục khi dự án đang thi công
+ Đưa ra lịch thi công các hạng mục tối ưu nhất
Trang 1
Chương I
ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP
PERT-CMP
(Phương pháp sơ đồ mạng lưới)
Dự án (Project) là một tập hợp các hoạt động (Activity) liên quan với nhau
và phải được thực hiện theo một thứ tự nào đó cho đến khi hồn thành tồn bộ các
hoạt động. Hoạt động được hiểu như là một việc đòi hỏi thời gian, và nguyên liệu
(Resource) để hồn thành. Trước kia để điều hành dự án người ta thường dùng biểu
đồ Gantt (Gantt bar chart), là một đồ thị gồm các đường kẻ ngang, biểu thị điểm
khởi công và kết thúc hoạt động. Nhược điểm của biểu đồ là không xác định được
quan hệ giữa các hoạt động, nên không áp dụng được cho các dự án lớn (large-scale
project), đòi hỏi đặt kế hoạch (planning), điều hành thực hiện (scheduling) va kiểm
tra (controlling) một cách hệ thống và hiệu quả, thậm chí phải tối ưu hố hiệu quả (về
thời gian và tiết kiệm nguyên liệu). Vì vậy, gần như đồng thời vào năm 1956-1958,
hai phương pháp kế hoạch, điều hành và kiểm tra dự án đã ra đời. Phương pháp
đường găng hoặc phương pháp đường tới hạn (Critical path method, viết rắt là
CPM) được E.I.du Pont de Nemous và công ty xây dựng của ông đưa ra. Phương
pháp thứ hai có tên là Kỹ thuật xem xét và đánh giá dự án (Project evaluation and
review technique, viết tắt là PERT) là kết quả nghiên cứa của một công ty tư vấn

dựng một tồ nhà. Việc tách dự án thành các hoạt động như đào đất, xây móng, xây
tường thô, lợp mái, đặt đường dây điện … là do kiến trúc sư hoặc kỹ sư xây dựng
làm. Dựa vào đó, người quản lý dự án lập được sơ đồ mạng lưới như H.1.1. Các số
bên cạnh cung là thời gian thực hiện hoạt động đó.
Qua sơ đồ mạng lưới H.1.1 ta thấy rõ mối quan hệ giữa các hoạt động về thời
gian. Chẳng hạn hoạt động (6, 8) là trát ngồi-phải sau (4, 6) là lợp mái, nhưng độc
lập với (5, 7) là chỉnh tường trong. Cũng vậy (4, 7) độc lập với (4, 5) và (5, 7). Ở
đây có hai hoạt động giả (dummmy activity) với thời gian để thực hiện bằng 0 được
đưa vào để đảm bảo qui tắc sơ đồ.
Cung giả (11, 12), ký hiệu bởi đường đứt đoạn, đưa vào để đảm bảo qui tắc
không có hai hoạt động cùng biến cố bắt đầu và kết thúc, tức là không có 2 cung có
cùng gốc và ngọn (tức là đồ thị đơn). Việc sơn tường trong và làm sàn có cùng biến
cố dầu là nút 9, tức là biến cố lát ván tường xong, và biến cố cuối là nút 12 (làm sàn
và sơn tường xong, bắt đầu hồn thiện trong). Do đó ta phải thêm nút 11 là biến cố
giả và cung giả (11, 12).
Cung giả (5, 8) để chỉ rằng hoạt động (4, 5) phải hồn thành trước khi bắt đầu
hoạt động (8, 10) (nếu bỏ cung giả này thì thời điểm làm hai việc là độc lập).
Cung giả này là phục vụ cho qui tắc sơ đồ mạng lưới phải thể hiện đủ quan hệ
thứ tự cần có.
Nếu quan hệ thời gian có dạng: việc x
2
bắt đầu khi xong 1/3 việc x
1
, việc x
3
bắt
đầu khi xong một nửa x
1
, thì ta phải thêm các nút đánh dấu các biến cố xong 1/3x
1

9 Sơn ngồi
8 Ép ván lát tường
Làm sàn 4 5 Sơn tường Hồn thiện ngồi 2
0 Hồn thiện trong
6
Kết thúc
Hình 1.1
Tóm lại: Sơ đồ mạng lưới phải là một đồ thị có hướng, đơn, liên thông,
không có khuyên (tức là cung có gốc và ngọn cùng là một nút), không có chu trình
có hướng (directed cycle), có nút khởi công và nút kết thúc.
2
1
x
1
3
1
x
1
2
1
x
1
Hình 1.2
II. Phân tích các chỉ tiêu thời gian. Xác định đường căng.
Pha điều hành có nhiệm phân tích các chỉ tiêu thời gian và đưa ra các bảng và
số liệu cần thiết trên sơ đồ mạng lưới. Nếu trong dự án phải điều hành cả nguyên
liệu (hoặc nhân lực) thì phải xét cả các chỉ tiêu đó, ta sẽ nói đến ở mục sau.
II.1. Tính các thời điểm.
Chỉ tiêu ở đây là thời điểm sớm của biến cố (earliest time for an event) là thời
điểm biến cố xảy ra khi mọi hoạt động trước nó được bắt đầu sớm nhất có thể. Thời

và E
11
cũng tương tự vì các nút tương ứng chỉ
có một cung vào, khi đó:
E
i
= E
j
+ t
ji
Ở đây j là nút ngay trước i. Chẳng hạn E
6
+ t
46
= 16 + 6 = 22. Nếu có nhiều cung
vào nút, tức là nhiều hoạt động kết thúc tại biến cố, thì từ định nghĩa E
i
rõ ràng đây
Trang 4
X
2
X
3
là thời điểm mọi hoạt động đó vừa xong cả, tức là phải lấy maximum của các tổng.
Chẳng hạn
E
7
= max {E
4
+ t

được ghi ở H.1.3 là số
đầu trong ngoặc ở mỗi nút.
Thời điểm muộn (latest time) của biến cố j là thời điểm muộn nhất mọi cung đi
vào biến cố j đều hồn thành mà không làm thay đổi thời điểm kết thúc dự án sớm
nhất có thể, ký hiệu là L
j
. Đối lại với E
j
, các L
j
được tính theo hướng lùi (backward
pass), tức là đi từ nút kết thúc. Theo định nghĩa, ở nút kết thúc thì E
n
= L
n
, ở thí dụ
H.1.1 là E
13
= L
13
= 44. nếu ở biến cố chỉ có một cung ra, tức là một hoạt động được
bắt đầu thì, thời điểm muộn là :
L
j
=L
i
- t
ji
,
Tức là thời điểm muộn của nút ngay sau nó trừ đi thời gian thực hiện hoạt động nối

– 4, 38 - 5) = 33
Hãy chú ý sự ‘’đối
xứng ‘‘ của quá
trình tính E
i
và L
j
.
Các L
j
được ghi ở
số thứ 2 trong
ngoặc ở mỗi nút
trong H.1.3.
II.2. Tính thời
gian dự trữ.
Trong thời gian dự
trữ (slack hoặc
float) của một biến
có là hiệu thời điểm
Trang 5
1
2
3
4
5
7
9
1
1

(33, 33)
1
4
5
(38, 38)
2
4
10
4
5
8
muộn và thời điểm sớm của nó : d
i
= L
i
– E
i
. Thời gian dự trữ (slack hoặc float) của
hoạt động được chia làm hai loại. Thời gian dự trữ chung (total slack hoặc total
float) của hoạt động (i, j) là :
TF
ij
= L
j
– E
i
– t
ij
.
TF

ij
được ghi
trong ô vuông cạnh ở mỗi cung. Còn thời gian dự trữ độc lập của hoạt động FF
ij
ít
quan trọng hơn, thường không ghi, xem H.1.3.
II.3. Đường găng. (đường tới hạn)
Các hoạt động có thời gian dự trữ chung bằng 0 cần được chú ý đặc biệt vì trì
hỗn nó sẽ ảnh hưởng đến thời gian kết thúc dự án. Từ đó có :
Định nghĩa II.3.1. Đường găng hoặc đường tới hạn (critical path) là một đường
đi từ nút khởi công đến nút kết thúc mà mọi hoạt động trên đường đều có thời gian
dự trữ chung bằng 0. (Chẳng hạn trên H.1.3 có một đường găng là 1 –> 2 –> 3 –> 4
–>5 –> 7 –> 9 –> 12 –> 13 ) hoạt động (i, j có TF
ij
= 0 được gọi là hoạt động găng
(critital activity). Biến cố i có d
i
=0 được gọi là biến cố găng (critical event).
Một số tính chất quan trọng của đường găng là như sau.
1. Mỗi dự án đều có ít nhất một đường găng.
2. Tất cả các hoạt động (i, j) có TF
ij
= 0, tức là mọi hoạt động găng đều phải
nằm trên đường găng.
3. Mọi biến cố găng, tức là biến cố i có d
i
= 0, đều phải nằm trên đường
găng. Biến có không găng không thể nằm trên đường găng.
4. Đường nối nút khởi công đến nút kết thúc mà mọi biến cố trên đó đều
găng có thể không phải đường găng vì có thể có hoạt động không găng.

3 6 6 0 (3, 4) 0
4 16 16 0 (4, 5) 0
5 20 20 0 (4, 6) 4
6 22 26 4 (4, 7) 2
7 25 25 0 (5, 7) 0
8 29 33 4 (6, 8) 4
9 33 33 0 (7, 9) 0
10 38 42 4 (8, 10) 4
11 37 38 1 (9, 11) 1
12 38 38 0 (9, 12) 0
13 44 44 0 (10, 13) 4
(12, 13) 0
Bảng1.1. Chỉ tiêu thời gian xây nhà
Ngồi các chỉ tiêu chính nói trên, khi cần các thông tin chi tiết hơn để điều hành
dự án, người ta cũng đưa ra một số khái niệm về thời gian khác nữa như sau.
Thời điểm khởi công sớm (earliest start) của hoạt động (i, j) là thời sớm của nút
gốc: ES
ij
= E
i
.
Thời điểm hồn thành sớm (earliest completion) của hoạt động (i, j) là EC
ij
= E
i
+ t
ij
.
Thời điểm khởi công muộn (latest start) của hoạt động (i, j) là LS
ij

+t
ij
= EC
ij
,
Vì i cũng là một trong các nút k ngay trước j. Bất đẳng thức thứ hai tương tự.
Thời gian dự trữ của một đường đi (total float of a path) P từ nút khởi công đến
nút kết thúc, ký hiệu TF
p
, là thời gian có thể kéo dài thêm các hoạt động trên đường
này mà không ảnh hưởng đến thời điểm hồn thành công trình, tức là
TP =
∑ ∑
−=−
PGP
ij
G
ij
TTtt
,
ở đây
G
G
ij
Tt
=
∑
là độ dài đường găng và
∑
≡

và cuối trùng với nút trong đường găng, không cần là nút khởi công và kết thúc của
cả dự án.
Thí dụ II.1. Ở dự án trên H.1.3, đường găng dược tô đậm. Thời điểm hồn thành
sớm EC
68
= E
6
+ t
68
= 22 + 7 = 29 = E
8
, EC
10, 13
= 40 < E
13
= 44. Thời điểm khởi công
muộn LS
46
= L
6
– t
46
= 26 – 6 = 20 > L
4
= 16. Bây giờ giả sử P là đường đi 1 –> 2 –>
3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì T
P
=
∑
P

−
. Ta thấy mặc dù T
Q
> T
P
nhưng thời hạn thực hiện các hoạt động không găng trong P lại chặt chẽ hơn
hoạt động không găng (4, 7) duy nhất của Q. Nguyên nhân là (4, 7) là không găng
duy nhất, nên mọi sự nới lỏng của Q đều dồn cho hoạt động này.
Chú ý rằng các dữ liệu thời gian quan trọng nhất là các chỉ tiêu có trong bảng
1.1. Ở bảng này cũng cho thấy đường găng (đường gồm các hoạt động găng, tức là
có thời gian dự trữ chung bằng 0).
II.4. Biểu đồ thời gian
Một cách truyền thống, bên cạnh sơ dồ lưới bảng, để theo dõi điều hành thời
gian cho dự án là dùng biểu đồ thời gian (time chart). Ta hãy xét cách vẽ và sử dụng
biểu đồ thời gian qua một thí dụ.
Thí dụ II.2. Xét dự án ở H.1.4, và bảng 1.2 tương ứng. (chú ý là hoạt động giả
(4, 5) lại là hoạt động găng.)
H.1.4
Biến cố E
i
L
i
d
i
Hoạt
động
TF
ij
1
2

(3, 5)
(4, 5)
(4, 6)
(4, 7)
(5, 6)
(5, 7)
(6, 7)
2
0
2
0
1
0
4
11
0
8
0
Trang 8
1
2
3
4
5
6
7
Bảng 1.2
Biểu đồ thời gian cho H.1.5. Ở đây chỉ có ttrục hồnh là thời gian . Cao độ
không quan trọng. Ta biểu diễn các hoạt động găng phía trên. Độ dài (thời gian) là
cố định, chặt chẽ cho các hoạt động găng. Hoạt động giả (4, 5) có độ dài bằng 0 nên

ij
<
TF
ij
thì hoạt động (i, j) chỉ được bắt đầu muộn hơn thời điểm khởi công sớm ES
ij
một khoảng thời gian không quá FF
ij
thì mới không ảnh hưởng đến các hoạt động
ngay sau nó (duy nhất) là
(2, 4) mới được xê dịch tuỳ ý trong khoảng thời gian 2 đến 6. Nếu (1, 2) thực hiện
lùi lại khoảng 1 đến 3 chẳng hạn, thì ảnh hưởng đến hoạt động (2, 4). Mặc dù có
FF
24
= TF
24
nhưng lúc này có chỉ còn được xê dịch thực hiện trong khoảng từ 3 đến
6.
III. Điều khiển nhân lực.
Các hoạt động không găng được phép xê dịch nhất định, nhất là khi FF
ij
= TF
ij
.
Có thể sắp đặt chúng đáp ứng các yêu cầu khác nữa. Ngồi thời gian ra, chẳng hạn
nhân lực, nguyên liệu, chi phí …Về mặt tốn học xử lý yêu cầu loại nào cũng vậy. Ở
đây ta nói theo ngôn ngữ nhân lực chẳng hạn.
Trang 9
1
1

thời điểm nếu tất cả các hoạt động không găng xếp vào lúc sớm nhất có thể, còn
H.1.6 (b) là tương ứng khi xếp vào lúc muộn nhất có thể. Hai biểu đồ này nên vẽ
thẳng dưới H.1.5 nữa. Sắp đặt sớm nhất ở hình (a) cho thấy ở mỗi thời điểm dự án
cần nhiều nhất là 10 công nhân còn ở sắp đặt muộn nhất (b) là 12 công nhân. Ở hai
phương án này, số công nhân cần ở các thời điểm không đều. Theo trực quan ta
chỉnh lại từ (a) như sau: chuyển hoạt động (4, 6) đếân thời điểm muộn nhất có thể,
chuyển (4, 7) đến ngay sau khi (5, 7) kết thúc. Kết quả được vẽ lại ở biểu đồ H.1.7.
(chú ý là hoạt động (1, 2) và (2, 4) không cần công nhân nên không cần vẽ.).

(3, 5) (4, 7)
(4, 6)

(3, 4) (5, 7)

(1, 3) (6, 7)

(5, 6)
Trang 10
Số công nhân
2 5 6 7 8 10
Số nhân công
2 5 6 7 8 10 12
Thời gian
Thời gian
3 4 6 10 11 13 14 17 19
3 4 6 10 11 13 14 17 19
H .I.6 (a)
(4, 7)

(3, 5)

4
1
2
2
4
Thời gian
Số công nhân
5 6 7 9 10
3 4 6 10 11 13 14 17 19
3 4 6 10 11 13 14 17 19
Thời Gian

Hình 1.7
IV. Hồn thành sớm dự án.
Trên đây đã xét thời điểm hồn thành dự án là cố định và xác định các đường
găng, phải thực hiện chặt chẽ để dự án hồn thành đúng thời gian qui định. Nếu
muốn giảm thời gian hồn thành dự án thì làm thế nào ? Ta cũng sử dụng đường
găng, nhưng phải dựa vào kỹ thuật và công nghệ, chứ không phải quản lý bằng tốn
học được nữa. Cụ thể là phải dùng công nghệ mới, tăng vật tư, công nhân .. để có
thời gian thực hiện các hoạt động ngắn hơn. Nhưng tập chung vào hoạt động nào ?
Rõ ràng là vào các hoạt động găng. Cụ thể là nếu ta quan tâm đến hạn chế chi phí
thì với (i, j) ∈ G, tìm số gia chi phí ∆C
ij
khi đạt được rút ngắn thời gian thực hiện
hoạt động là ∆t
ij
(tìm bằng thực tế công nghệ, không phải thuần tuý tốn học). Khi đó
sẽ chọn cách tăng chí phí để giảm thời gian sao cho đạt
ij
ij

model). Trong thực tế, nhiều yếu tố bất định phải được tính đến, do đó thời gian
thực hiện hoạt động (i, j) là một biến ngẫu nhiên (random variable), mà ta chỉ xác
định được phân bố xác suất (probability distributtion) qua kinh nghiệm và sớ liệu
thống kê. Từ đó dẫn đêùn phải sử dụng mô hình ngẫu nhiên hoặc gọi khác là mô
hình xác suất (probabilistic model). Việc tính tốn các chỉ tiêu để điều hành dự án có
hai nhiệm vụ chính. Một là tính kỳ vọng (mean hoặc expected value) của các đại
lượng cần tính, chẳng hạn thời gian thực hiện hoạt động (activity time), thời gian
hồn thành dự án (project time), và phương sai (variance) của các đại lượng này. Hai
là tính xác suất của biến cố nào đó, chẳng hạn biến cố là dự án hồn thành trước thời
điểm T.
Thời gian thực hiện mỗi hoạt động, thường gọi tắt là thời gian hoạt động, trong
mô hình ngẫu nhiên thường được giả thiết là xác định được ba yêùu tố sau. Thời
gian lạc quan (optimistic time) ký hiệu là a, là thời gian cần để làm xong khi hoạt
động được thực hiện thuận lợi nhất. Thời gian này rất khó đạt được. Theo lý thuyết
Trang 12
thống kê, thì đây thực chất là cận dưới (lower bound) của phân bố xác suất. Thời
gian bi quan (pressimistic time), ký hiệu là b, là thời gian cần để xong hoạt động khi
tiên hành gặp trục trặc nhất, tức là cận trên (upper bound) của phân bố xác suất.
Thời gian hợp lý nhất (most likely time), ký hiệu là m, là thời gian hiện thực nhất,
tức là có xác suất lớn nhất (đỉnh cao nhất của hàm mật độ). Ba lượng trên chưa đủ
để xác định phân bố xác suất của thời gian hoạt động. Do đó chưa đủ để xác định kỳ
vọng t
e
tức là giá trị trung bình theo xác suất, và phương sai δ
2
đặc trưng cho độ
lệch khỏi t
e
của thời gian hoạt động. Mô hình cần hai gải thiết phù hợp thực tế sau
đây.

a
dxxfXxPXF
dxxf
,)(}{)(
,1)(
∫
∫
−=
=
b
a
e
b
a
e
dxxfxx
dxxxfX
,)()(
,)(
22
σ
ở đây x
e
là kỳ vọng và σ
2
là phương sai của biến ngẫu nhiên x, P {…} là xác suất
của biến cố {…}. Mỗi một trong hàm mật độ hoặc hàm phân phối đặc trưng hồn tồn
cho biến ngẫu nhiên. Kỳ vọng và phương sai là các đại lượng quan trọng. Ta cũng
nói là hàm mật độ (hoặc hàm phân bố), xác định hồn tồn phân bố xác suất. Phân bố
beta (beta distribution) là một trong các phân bố xác suất phổ biến nhất, xác định bởi

=Γ
1
0
11
0
1
)1(:),(
:)(
dtttB
et
t
βα
α
βα
α

α=1, β=2 α = β α=2, β=2
Trang 13
α=β=1
m1 x
Hình 1.8
Nếu y lấy giá trị trên [a, b] và có phân bố theo beta thì hàm mật độ nhân được
từ (4.2) bằng đổi biến y = a + (b - a)x. Chẳng hạn, hàm mật độ của phân bố beta có
dạng như H.1.8 với α ≥ 1, β ≥ 1 và a = 0, b = 1.
Phân bố chuẩn (normal distribution) là phân bố xác suất phổ biến nhất, định
nghĩa bởi hàm mật độ sau.
,,
2
1
)(

được gọi là độc lập (independent) nếu.
P{x
1
≤ X
1
, …, x
n
≤ X
n
} = P{x
1
≤ X
n
},
Định nghĩa giới hạn trung tâm (centrer – limit thoerem) nói rằng với các điều
kiện khá nhẹ, tổng các biến ngẫu nhiên độc lập luôn có phân bố chuẩn (không phụ
thuộc vào phân bố của từng biến ngẫu nhiên).
Trở lại mô hình ngẫu nhiên điều hành dự án. Để tính kỳ vọng t
e
của thời gian
hoạt động, người ta giả thiết là điểm giữa
2
ba
+
chiếm tỷ trọng bằng nửa điểm hợp
lý nhất m. Khi đó





Phương
sai σ
2
(1, 2)
(2, 3)
(3, 4)
(4, 5)
(4, 6)
(4, 7)
(5, 7)
(6, 8)
(7, 9)
(8, 10)
(9, 11)
(9, 12)
(10, 13)
(12, 13)
1
2
6
1
4
3
4
5
3
5
4
1
1

8
18
5
10
9
10
11
9
17
4
7
3
9
2
4
10
4
6
7
5
7
8
9
4
5
2
6
9
1
1

này. Khi đó, vì kỳ vọng và phương sai của tổng các biến ngẫu nhiên là tổng của các
kỳ vọng và phương sai nên ta có: Kỳ vọng và phương sai của thời gian dự án là tổng
các kỳ vọng và phương sai của các thời gian hoạt động trên đường găng (xây dựng
theo các kỳ vọng). Đến đây ta nhận xét rằng một trong các cách áp dụng thực tế là
dùng các kỳ vọng của các biến, rồi áp dụng mọi tính tốn và lý luận ở các mục trước
vào các kỳ vọng, thay cho các biến tất định.
Ở Thí dụ V.1 kỳ vọng và phương sai của thời gian dự án là 44 và 9, vì đường
găng là 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 .
Bây giờ ta xét vấn đề quan trọng là tính xác suất để dự án hồn thành trước một
thời hạn bắt buộc (deadline). Theo định lý giới hạn trung tâm, thời gian dự án là
biến ngẫu nhiên có phân bố chuẩn. Do đó ta tính được xác suất P(x ≤ X), thường
được tính sẵn để tra theo bảng. Chẳng hạn Bảng A
1
ở cuối sách cho biết P {x ≤ x
e
+
σK
α
}, ở đây σ là độ lệch chuẩn. Do đó K
σ
là đơn vị lệch chuẩn.
Thí dụ, hãy tính xác suất để thời gian xây nhà ở Thí dụ V.1 không quá 47 ngày.
Ta thấy 47 = 44 + 3.1 = x
e
+ σK
σ
nên K
σ
= 1. Theo bảng thì P {x ≥ 47} = 0,1584.
Do đó xác suất cần tìm là ≅ 1 – 0,1584 ≅ 0,84.

i
) quy ước lấy lượng của đường có tổng các σ
2
dái nhất.
Bây giờ hãy tính xác suất để biến cố i xong trước thời gian bắt buộc T
i
cho
trước. Theo định lý giới hạn trung tâm µ
i
tuân theo phân bố chuẩn, ta chỉ việc tra
bảng các xác suất ứng với phân bố chuẩn để tính P{µ
i
≤ T
i
}. Cụ thể, để tra bảng,
quy về trường hợp đại lương z có phân bố chuẩn với kỳ vọng 0 và phương sai 1 như
sau:
{ }
}{:
)(
)(
)(
)(
i
i
ii
i
ii
ii
KzP

ii
i
Var
ET
K
µ
µ
−
=
đã biết.
VI. Dự án có thoả hiệp thời gian – Cước phí.
Trong các mục trước ta trình bày về các dựa án có yêu cầu chủ yếu là điều hành
thời gian. Theo ngôn ngữ ban đầu thì đây là phương pháp PERT, các thời gian ở đây
có thể xét như các biến tất định hoặc ngẫu nhiên. Còn phương pháp đường găng
PCM thì đặt ngang nhau về thời gian và cước phí. Mục tiêu chính của PCM là chọn
cách thoả hiệp thời gian thực hiện mỗi hoạt động (theo ngôn ngữ hình học) tức là
biết đường cong thời gian – cước phí (time – cost curve) của mỗi hoạt động. Trong
mô hình tốn học (xấp xỉ thô tình trạng thực tế) người ta giả thiết quan hệ thời gian
Trang 16
và cước phiù là tuyến tính. Do đó chỉ cần biết hai điểm. Người ta chọn hai điển nút
như sau:
Điểm chuẩn (normal point) có toạ độ là thời gian và cước phí của hoạt động khi
nó được tiến hành trong điều kiện bình thường, tức là chuẩn, không có cước phí bổ
xung tăng cường (như làm ngồi giờ, tăng thiết bị nhân lực …). Cực điểm (crash
point) là điểm ứng với thời gian và cước phí khi đầu tư hết mức để thời gian thực
hiện hoạt động ngắn nhất có thể. Mọi điểm trung gian giữa điểm chuẩn và cực điểm,
tức là mọi cách thoả hiệp thời gian cước phí (time – cost trade - off) đều coi là chấp
nhận được, xem H.1.10.
Hình 1.10
Đường cong thời gian – cước phí của hoạt động (i, j).

là tung độ điểm đường thẳng cắt trục tung. Khi đó cước phí của hoạt
động (i, j) tương ứng với thời gian hoạt động (i, j) ứng với thời gian hoạt động x
ij
rõ
ràng là:
Bài tốn: Chọn các x
ij
để thời gian dự án không quá thời hạn bắt buộc T cho
trước và làm cực tiểu cước phí dự án C.
Nhận xét rằng các yếu tố của bài tốn đều là tuyến tính, ta cố gắng đưa về quy
hoạch tuyến tính như sau:
Đưa vào các biến bổ xung y
k
là thời điểm sớm E
k
của biến cố k. Khi đó quan hệ
giữa các biến theo Mục 4.2 là
{ }
jkjk
tEE
+=
j
max
, (1, 4)
ở đây max lấy theo các biến cố j ngay trước k, tức là có hoạt động nối (j, k). Ký hiệu
y
k
= E
k
, t

Dij
d
ij
x
ij
D
ij
Ở mục tiêu thì K
ij
là hằng. Tóm lại ta được quy hoạch tuyến tính
.,0
0
,
,min
1
),(
Tyy
yxy
Dxd
xS
n
ijiji
ijijij
ji
ijij
≤=
≤−+
≤≤
∑
Để đưa về quy hoạch tuyến tính dạng chuẩn ta làm như sau. Đổi biến x

nhất giữa tổng cước phí và tổng thời gian dự án, người ta coi T là tham số và giải
quy hoạch tuyến tính tham số để được nghiệm tối ưu như hàm của T.
VII. Kiểm tra hiệu chỉnh dự án.
Sau khi dùng phương pháp điều hành dự án PERT – CPM xác định được sơ đồ
mạng lưới, các biểu đồ và bảng tính các chỉ tiêu và dự án đang được tiến hành,
người quản lý luôn phải theo dõi, kiểm tra. Điều kiện lao động thực tế có thể nhiều
bất ngờ. Khi cần thiết có thể phải dùng phương pháp PERT – CPM lại, dựa trên các
dữ liệu mới, để tính tốn cho phần còn lai của dự án. Sau đó điều hành dự án theo các
biểu đồ và bảng tính mới.
Trang 18
CHƯƠNG 2
CƠ SỞ VỀ LÝ THUYẾT ĐỒ THỊ
I. Một số khái niệm cơ bản.
Lý thuyết độ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng
hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm
đầu của thế kỷ 18 bởi nhà tốn học lỗi lạc người Thụy Sỹ Euler. Chính ông là người
sử dụng đồ thị để giải bài tốn nổi tiếng về cái cầu ở thành phố Konigsberg.
Đồ thị được sử dụng để giải các bài tốn trong nhiều lĩnh vực khác nhau. Chẳng
hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch
điện. Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng
công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể
xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau
không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có
thể sử dụng để giải bài tốn như: Tìm đường đi ngắn nhất giữa hai thành phố trong
một mạng giao thông. Chúng ta còn sử dụng đồ thị để giải các bài tốn về lập lịch,
thời khóa biểu, và phân bố tần số cho các trạm phát thanh và truyền hình…
1.1. Định nghĩa đồ thị.
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.
Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh
nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại đồ thị khác

niệm đa đồ thị có hướng:
Định nghĩa 5: Đa đồ thị có hướng G= (V,E) bao gồm V là tập các đỉnh, và E là
họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e
1
và e
2
tương ứng với cùng một cặp đỉnh được gọi là cung lặp.
Chúng ta chủ yếu sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng.
1.2. Các thuật ngữ cơ bản.
Trước tiên ta xét thuật ngữ mô tả các đỉnh và các cạnh của đồ thị vô hướng.
Định nghĩa 1: Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu
(u,v) là cạnh của đồ thị G. Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên
thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời
các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v).
Để có thể biết bao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định nghĩa sau:
Định nghĩa 2: Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc
với nó và sẽ kí hiệu là deg(v).
b c d
a f e g
Hình 1: Đồ thị vô hướng G.
Thí dụ 1: Xét đồ thị trong hình 1, ta có:
deg(a)= 1, deg(b)=4, deg(c)=4, deg(f)=3, deg(d)=1, deg(e)=3, deg(g)=0.
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong thí dụ trên đỉnh g là
đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau:

∑
⊂
=
Vv
vm )deg(2

hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg
+
(v) (deg(v)).
Định lý 2: Giả sử G = (V,E) là đồ thị có hướng. Khi đó

Evv
VvVv
==
∑∑
∈
−
∈
+
)(deg)(deg
Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các
cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng
trên các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các
cung được gọi là đồ thị vô hướng tương ứng với dồ thị có hướng đã cho.
1.3. Đường đi, chu trình, đồ thị liên thông.
Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị vô hướng G =(V,E) là dãy x
0
, x
1
, … ,x
n-1
,x
n
trong đó u =x
0

n-1
,x
n
trong đó u =x
0
, v=x
n
, (x
i
, x
i+1
) ∈A, i= 0, 1, 2… , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng
dãy các cung: (x
0
, x
1
), (x
1
, x
2
), …, (x
n-1
, x
n
).
Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có
đỉnh đầøu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu
trình được gọi là đơn nếu như không có cung nào bị lặp lại.
Định nghĩa 3: Đồ thị vô hướng G= (V,E) được gọi là liên thông nếu luôn tìm
được đường đi giữa hai đỉnh bất kỳ của nó.

’
theo một hướng dọc theo chu trình này (không định hướng lại các
cạnh đã có hướng). Thủ tục trên sẽ lặp lại cho đến khi tất cả các cạnh của đồ thị
được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnh.
II. Biểu diễn đồ thị trên máy tính.
Để lưu trữ đồ thị và thực hiện các thuật tốn khác nhau với đồ thị trên máy tính
cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ
liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật tốn. Vì vậy,
việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ
thể (bài tốn và thuật tốn cụ thể ). Ở phần này ta sẽ xét một số phương pháp cơ bản
để biểu diễn đồ thị trên máy tính, đồng thời cũng phân tích một cách ngắn gọn
những ưu điểm cũng như những nhược điểm của chúng.
2.1. Ma trận kề, Ma trận trọng số.
Xét đơn đồ thị vô hướng G = (V,E), với tầp đỉnh V= {1, 2, …,n} tập cạnh E =
{e
1
, e
2
,…, e
m
}. Ta gọi ma trận kề của đồ thị G là (0, 1) ma trận A = {a
ij
: i,j = 1, 2,
… ,n}với các phần tử được xác định theo quy tắc sau đây:
a
ij
=0 nếu (i,j) ∉ E và a
ij
=1 nếu (i,j)∈ E, i,j =1, 2,…,n
Thí dụ1: Ma trận kề củae đồ thị vô hướng cho trong hình 1 là:

p
, i,j = 1, 2,…, n. Là các phần tử của ma trận A
p
= A.A….A. p là
thừa số, khi đó a
ij
p
, i,j = 1, 2,…, n. cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j
qua p –1 đỉnh trung gian.
Ma trận kề của đồ thị có hướng được định nghĩa một cách hồn tồn tương tự.
Thí dụ 2: Đồ thị có hướng G
1
cho trong hình 1 có ma trận kề là ma trận sau.
1 2 3 4 5 6
1
2
3
4
5
6
Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng.
Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây
dựng hồn tồn tương tự, chỉ khác, là thay vì ghi 1 vào vị trí a[i, j] nếu (i, j) là cạnh
của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i và j.
Trong rất nhều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e= (u, v) của đồ
thị được gán với một con số c(e) (còn viết là c (u, v)) gọi là trọng số của cạnh e. Đồ
thị trong trường hợp như vậy được gọi là đồ thị trọng số. Trong đồ thị có trọng số,
thay vì ma trận kề, để biểu diễn đồ thị ta dùng ma trận trọng số.
C = c[i,j], i,j=1,2,…,n.
Với c(i, j)= c[i, j], nếu (i, j) ∈ E và c[i, j] =θ nếu (i, j) ∉ E

các đỉnh kề với nó, mà ta sẽ ký hiệu là Ke(v), tức là Ke(v)={u∈V: (v, u) ∈ E} khi
đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các
phần tử được xắp xếp như sau:
For u∈ Ke(v) do…
Chẳng hạn, trên PASCAL có thể mô tả danh sách này như sau (Gọi là cấu trúc
Forward star ):
Const
m = 100; {m – số cạnh}
n = 100; {n – số đỉnh}
var
Ke: array {1..m} of integer ;
Tro: array {1..n+1} of integer ;
Trong đó Tro [i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i = 1, 2, …n,
Tro[n+1] = 2m + 1.
III. Bài tốn tìm đường đi ngắn nhất.
Trong các ứng dụng thực tế, bài tốn tìm đường đi ngắn nhất giữa hai đỉnh của
đồ thị liên thông có một ý nghĩa to lớn, có thể dẫn về bài tốn như vậy nhiều bài tốn
thực tế quan trọng. Ví dụ, bài tốn chọn một hành trình tiết kiệm nhất (theo tiêu
chuẩn khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường
bộ, đường thủy hoặc đường không; bài tốn chọn một phương pháp tiết kiệm nhất để
đưa một hệ động lực lực từ trạng thái xuất phát đến một trạng thái đích, bài tốn lập
lịch thi công các công đoạn trong công trình thi công lớn, bài tốn lựa chọn đường
truyền tin với chi phí nhỏ nhất trong mạng thông tin, …hiện nay có rất nhiều
Trang 24
phương pháp để giải các bài tốn như vậy. Thế nhưng thông thường các thuật tốn
được xây dựng dựa trên lý thuyết đồ thị tỏ ra là các thuật tốn có hiệu quả nhất.
Trong phần này ta sẽ xét một số thuật tốn như vậy.
3.1. Các khái niệm mở đầu.
Trong phần này ta chỉ xét đồ thị có hướng G = (V,E), |V| = n, |E| = m với các
cung được gán trọng số, nghĩa là mỗi cung (u, v) thuộc E của nó đựơc đặt tương ứng

trong đường đi ngắn nhất không có đỉnh nào bị lặp lại (đường đi không có đỉnh nào
lặp lại sẽ được gọi là dường đi cơ bản). Mặt khác, nếu đồ thị có chu trình với độ dài
âm (chu trình như vậy, để ngắn gọn ta gọi là chu trình âm ) thì khoảng cách giữa
một số cặp đỉnh nào đó của đồ thị có thể là không xác định, bởi vì bằng cách đi
vòng theo chu trình này một số đủ lớn lần, ta có thể chỉ ra đường đi giữa các đỉnh
này có độ dài nhỏ hơn bất cứ số thực cho trước nào. Trong các trường hợp như vậy,
có thể đặt vấn đề tìm đường đi cơ bản ngắn nhất, tuy nhiên bài tốn đặt ra sẽ trở nên
phức tạp hơn rất nhiều, bởi vì nó chứa bài tốn xét sự tồn tại đường đi Hamilton
trong đồ thị như là một trường hợp riêng.
Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, trong trường hợp
trọng số không âm, có thể tìm được một cách dễ dàng, để tìm đường đi chỉ cần để ý
là đối với cặp đỉnh s, t ∈ V tùy ý (s ≠ t) luôn tìm được v đỉnh sao cho:
d(s, t) = d(s, v) + a(v, t).
Thực vậy, đỉnh v như vậy chính là đỉnh đi trước đỉnh t trong đường đi ngắn
nhất từ s đến t. Tiếp theo ta lại có thể tìm được đỉnh u sao cho d(s, v)= d(s, u) + a(u,
v), … từ giả thiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t, v, u,
… không chứa đỉnh lặp lại và chứa đỉnh kết thúc ở đỉnh s. Rõ ràng dãy thu được xác
định (nếu lật ngược thứ tự các đỉnh trong nó) đường đi ngắn nhất từ s đến t.
3.2. Đường đi ngắn nhất xuất phát từ một đỉnh .
Phần lớn các thuật tốn tìm khoảng cách giữa hai đỉnh s và t được xây dựng nhờ
kỹ thuật tính tốn mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a{u, v}, u,
Trang 25