1

MỤC LỤC
1. Lí do chọn đề tài................................................................................................1
2. Mục tiêu nghiên cứu..........................................................................................1
3. Lịch sử nghiên cứu............................................................................................2
4. Nhiệm vụ nghiên cứu.........................................................................................2
5. Đối tượng nghiên cứu........................................................................................2
6. Phạm vi nghiên cứu...........................................................................................2
7. Phương pháp nghiên cứu...................................................................................3
Chương I: TÌM HIỂU MỘT SỐ KHÁI NIỆM TRONG MẠNG PERT...............4
1. Một số khái niệm...............................................................................................4
1.1 Sơ đồ mạng......................................................................................................4
1.2 Đường đi trong mạng.......................................................................................4
1.4 Sơ đồ mạng PERT............................................................................................5
1.5 Giới thiệu về sơ đồ PERT................................................................................5
1.6 Các thông số thời gian trong sơ đồ PERT........................................................7
1.7 Cách thành lập sơ đồ mạng PERT.................................................................10
Chương II: PHƯƠNG PHÁP/KĨ THUẬT RÚT NGẮN ĐƯỜNG ĐI TRONG
MẠNG PERT.......................................................................................................14
2.1 Một số khái niệm liên quan đến rút ngắn đường đi.......................................14
2.1.1 Chi phí trực tiếp..........................................................................................14
2.1.2 Chi phí gián tiếp..........................................................................................14
2.1.3 Chi phí liên quan đến thời gian...................................................................15
2.1.4 Phương pháp thực hiện kế hoạch chi phí cực tiểu......................................15

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh

2

2.2 Bài toán tính xác suất hoàn thành dự án........................................................16
2.2.1 Ví dụ minh họa...........................................................................................19
2.3 Kĩ thuật rút ngắn đường đi trong mạng Pert sử dụng quy hoạch tuyến tính
đa mục tiêu...........................................................................................................20
2.3.1 Sơ lược về lý thuyết Quy hoạch tuyến tính................................................20
2.3.2 Bài toán.......................................................................................................22
2.3.3 Sơ đồ tóm tắt các bước sử dụng Quy hoạch tuyến tính để giải bài toán.....23
2.3.4 Ví dụ minh họa...........................................................................................23
2.4 Phương pháp CMP (Critical Path Method)....................................................39
2.4.1 Bài toán.......................................................................................................40
2.4.2 Các bước thực hiện.....................................................................................40
2.4.3 Ví dụ minh họa...........................................................................................42
2.5 Phương pháp Unit Crash................................................................................45
2.5.1 Bài toán.......................................................................................................45
2.5.1 Các bước thực hiện.....................................................................................45
2.5.2 Ví dụ minh họa...........................................................................................48
2.6 Phương pháp đồ thị tính giá trị gần đúng của Chi phí trực tiếp.....................51
2.6.1 Các bước thực hiện Phương pháp tính gần đúng chi phí trực tiếp.............52
2.6.2 Ví dụ minh họa:..........................................................................................57
TÀI LIỆU THAM KHẢO--------------------------------------------------------------------------65

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


3


MỞ ĐẦU
1. Lí do chọn đề tài:
Trong quản lý dự án phần mềm, ước lượng về thời gian và chi phí tác
động không nhỏ đến thành công của dự án, kết thúc dự án đúng hạn là một
trong những thử thách lớn nhất, thường thì rất khó để chúng ta có thể ước
lượng chính xác về số đơn vị thời gian hoàn thành dự án cho từng công việc.
Các vấn đề về lịch biểu là lý do chính dẫn đến xung đột trong dự án, đặc biệt
là nữa sau của dự án. Vì vậy chúng ta cần một khoảng một thời gian để dự
phòng cho từng công việc.
Mặt khác xuất phát từ vấn đề hạn chế về nguồn vốn đầu tư, tính cạnh
tranh khốc liệt về giá thành và hiệu quả của việc rút ngắn thời gian để kịp
hoàn thành tiến độ công việc nên việc nghiên cứu tối ưu hoá sơ đồ mạng theo
chỉ tiêu thời gian với chi phí tăng thêm nhỏ nhất là hết sức cần thiết nhằm
mang lại hiệu quả kinh tế cao trong việc tổ chức xây dựng sản phẩm phần
mềm.
Tối ưu hoá theo chỉ tiêu thời gian - chi phí trên sơ đồ mạng là một trong
những giải pháp tương đối hữu hiệu nhằm rút ngắn thời gian thực hiện từng
danh mục công việc hay toàn bộ công trình tương ứng với tổng chi phí thấp
nhất. Xuất phát từ những lý do trên chúng tôi chọn đề tài: “Bài toán rút ngắn
đường tới hạn trong mạng Pert”.
2. Mục tiêu nghiên cứu:
 Hiểu được mạng Pert là gì? Đường đi trong mạng Pert là gì?
Đường tới hạn trong mạng Pert là gì?
 Rút ngắn đường tới hạn là làm gì? Rút ngắn để làm gì?
 Các bài toán đặt ra là gì? Cách giải các bài toán đó.

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh



4

3. Lịch sử nghiên cứu:
 Vấn đề này đã được một số tác giả nhắc đến trong quản lý xây
dựng các công trình xây dựng (kinh tế xây dựng), trong quản lý
doanh nghiệp kinh doanh…
4. Nhiệm vụ nghiên cứu:
 Tìm hiểu mạng Pert trong quản lý dự án, đường đi trong mạng
Pert, cách rút ngắn đường đi.
 Đưa ra được một số bài toán vận dụng quy hoạch tuyến tính để
giải.
 Chuyển về bài toán rút ngắn đường đi trong mạng PERT về bài
toán tổng quát vận dụng quy hoạch tuyến tính để giải.
 Tìm hiểu một số phương pháp khác về rút ngắn đường đi trong
mạng PERT.
 Lưu ý mối quan hệ giữa rút ngắn thời gian và chi phí.
5. Đối tượng nghiên cứu:
 Lý thuyết tối ưu và các thành phần trong sơ đồ mạng Pert
 Các bài toán trong quản lý chi phí, thời gian trong sơ đồ mạng
Pert
 Phương pháp rút ngắn đường đi trong sơ đồ mạng Pert
6. Phạm vi nghiên cứu:
Đề tài tập trung nghiên cứu:
 Sơ đồ mạng Pert trong quản lý dự án phần mềm
 Lý thuyết về quy hoạch tuyến tính
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh



5

 Các phương pháp rút ngắn đường tới hạn trong mạng Pert
7. Phương pháp nghiên cứu:
 Phương pháp nghiên cứu lý thuyết: Lý thuyết về quản lý dự án,
sơ đồ mạng, lý thuyết về tối ưu…

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


6

NỘI DUNG
Chương I: TÌM HIỂU MỘT SỐ KHÁI NIỆM TRONG MẠNG PERT
1. Một số khái niệm
1.1 Sơ đồ mạng:
Một tập hợp các điểm (ta gọi là các đỉnh, kí hiệu A) và tập hợp các mũi
tên (ta gọi là các cung, kí hiệu là U) được gọi là một sơ đồ mạng lưới nếu
chúng thỏa mãn các điều kiện sau:


Giữa hai đỉnh có không quá một cung nối liền và ngược lại mỗi
cung liên kết 2 đỉnh nào đó với nhau. Cung nối từ đỉnh i đến đỉnh j
kí hiệu là (i, j) trong đó i là điểm gốc của cung, và j là điểm ngọn
của cung.




Trong sơ đồ không chứa vòng kín, nghĩa là từ một đỉnh bất kỳ, đi
theo chiều các mũi tên, không bao giờ quay về điểm xuất phát. Giữa
2 đỉnh tùy ý bao giờ cũng có một dãy các cung nối liền.



Có một đỉnh chỉ toàn các cung đi ra được gọi là đỉnh bắt đầu và có
một đỉnh chỉ toàn các cung đi vào được gọi là đỉnh kết thúc. Các
đỉnh còn lại có cả cung đi ra và cung đi vào.

1.2 Đường đi trong mạng:
Trong sơ đồ mạng mà một dãy các cung nối tiếp nhau được gọi là một
đường đi.
1.3 Đường tới hạn trong mạng:
Đường tới hạn là đường nối những công việc tới hạn. Công việc tới hạn
là những công việc mà không cho phép trễ, vì trễ sẽ ảnh hưởng đến việc trễ
hạn của toàn bộ thời gian dự án.

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


7

1.4 Sơ đồ mạng PERT:
Là phương pháp áp dụng kết hợp giữa lý thuyết xác suất thống kê (để
ước tính thời lượng công việc trong các dự án mà công việc có thời lượng
không xác định trước) với dạng sơ đồ mạng đường găng sử dụng lý thuyết đồ

thị.
Áp dụng PERT/CPM đối với quản trị dự án sẽ giúp các nhà quản trị xây
dựng được lộ trình và thời gian cho các hoạt động của dựán theo từng bước,
từng giai đoạn cụ thể. Đồng thời chủ động khống chế được thời gian của dự
án, tránh tình trạng không đảm bảo tiến độ như khá nhiều dự án đang gặp
phải.
1.5 Giới thiệu về sơ đồ PERT:
Trong các phương pháp sơ đồ mạng thì phương pháp PERT được
nhiều người biết đến hơn cả, PERT có nghĩa là kĩ thuật ước lượng và kiểm tra
dự án (Program Evaluation and Review Technique).
Trước hết là kết quả đáng chú ý khi ở Mĩ người ta sử dụng PERT để
điều khiển việc xây dựng hệ thống tên lửa Polaris vào năm 1958 đã rút ngắn
thời gian xây dựng từ 55 năm xuống còn 3 năm. Sau đó PERT được phổ biến
rất nhanh chóng sang các lĩnh vực khác trong nền kinh tế quốc dân ở Mĩ.
Mục tiêu chính của phương pháp: đánh giá khả năng hoàn thành dự án
trong thời hạn định trước.
Cho biết:
 Trình tự thực hiện các công việc: việc nào có thể làm ngay, việc nào
làm sau việc việc nào.
 Thời gian cần thiết để hoàn thành mỗi việc.
Phải làm:
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


8

 Thời hạn sớm nhất để hoàn thành toàn bộ dự án.
 Thời hạn bắt đầu sớm nhất và muộn nhất của mỗi công việc sao cho

toàn bộ dự án được hoàn thành đúng kế hoạch.
 Thời điểm kết thúc sớm nhất và muộn nhất của mỗi việc sao cho
toàn bộ dự án được hoàn thành đúng kế hoạch.
 Thời gian dự trữ cho mỗi việc, nghĩa là khoảng thời gian mà có thể
bắt đầu muộn hoặc kết thúc muộn mà không ảnh hưởng tới toàn bộ
dự án.
Trên cơ sở xem thời hạn hoàn thành mỗi công việc không đổi (t ij =
const). Thật ra trong thực tế xây dựng thường gặp rất nhiều yếu tố ngẫu nhiên
tác động (điều kiện về thời tiết, việc cung cấp nguyên vật liệu, thiết bị...). Vì
vậy, thời hạn hoàn thành các công việc nhiều khi không cố định (tij).
Ví dụ: Khi cần đóng một hệ thống cọc để gia cố nền của một tòa nhà,
người điều khiển thi công dự tính làm trong 1 tháng. Có khi do chuẩn bị các
mặt tốt, công tác tiến hành trong thời tiết thuận lợi, nên thời gian chỉ hết 20
ngày. Nhưng khi gặp khó khăn về thời tiết, về dụng cụ… thời gian hoàn thành
là 35 ngày, mất nhiều thời gian hơn kế hoạch dự tính. Như vậy vấn đề được
đặt ra là: Phải xử lí tình trạng không ổn định về thời gian như thể nào để rút ra
được những kết luận đáng tin cậy và có thể sử dụng được trong thực tế thi
công. Muốn giải quyết vấn đề này có thể vận dụng các phương pháp của lí
thuyết xác suất thống kê, để nghiên cứu PERT và đó cũng là một ưu điểm nổi
bật trong các ưu điểm của phương pháp PERT. Phương pháp PERT lại đưa
yếu tố không xác định (hay còn gọi là yếu tố ngẫu nhiên) vào, khi ước lượng
thời gian thực hiện các công việc và thời gian hoàn thành dự án; do đó nó rất
phù hợp với những trường hợp, những số liệu ban đầu và các công việc đang
được nghiên cứu thực hiện chưa có định mức.

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh



9

1.6 Các thông số thời gian trong sơ đồ PERT:
Mỗi công việc thường có một định mức thời gian thực hiện dựa trên
công nghệ và tài nguyên sử dụng (thiết bị, nguyên liệu, lao động…).
Cũng có những công việc chưa có định mức thời gian, chẳng hạn
những công việc thuộc lĩnh vực nghiên cứu, thử nghiệm, chế tạo, sản xuất lần
đầu, hoặc quy cách sản phẩm thay đổi…, do đó khó xác định được thời gian
thực hiện các công việc.
Thời gian dự kiến hoàn thành công việc tij của dự án thưởng là ước
lượng. Thực tế thời gian thực hiện các công việc không hoàn toàn đúng bằng
thời gian dự kiến, cũng có khi chúng lớn hơn, cũng có lúc lại nhỏ hơn thời
gian dự kiến. Chỉ người nào đã quen làm một loại công việc thì với kinh
nghiệm và khả năng riêng mới dự kiến đúng đắn được thời gian này cho chính
mình. Vậy đây vẫn là một sự ước lượng thời gian theo chủ quan của con
người.
Thời gian dự trữ của các sự kiện (điểm nút)
Công thức xác định thời gian sớm nhất và thời gian muộn nhất đạt tới
một sự kiện
Kí hiệu:
tij: độ dài cung i hay thời gian thực hiện công việc mà kéo dài mà kéo
dài từ sự kiện i tới sự kiện j (i là sự kiện trước, j là sự kiện sau)
Eij: thời gian sớm nhất để đạt tới sự kiện j tính từ khi bắt đầu dự án
(quãng đường dài nhất tính từ sự kiện đầu tiên đến sự kiện j)
Lij: thời gian chậm nhất sự kiện j phải xuất hiện mà không làm chậm
trễ việc hoàn thành dự án
Công thức tính Ei
Ej=Maxi(Ei+tij)
GVHD: Thầy giáo Nguyễn Thế Dũng


Sinh viên thực hiện: Nguyễn Thị Tú Anh


10

E1=0
Công thức tính Li
Li = Minj(Li - tij)
Lcuối cùng= thời gian thực hiện dự án
Ý nghĩa của việc tính E và L:
 Thứ nhất, tính toán thời gian dự trữ của một sự kiện
Thời gian dự trữ của một sự kiện là thời gian sự kiện có thể kéo dài
thêm mà không làm ảnh hưởng đến thời gian hoàn thành dự án.
Si = Li - Ei
 Thứ hai, là cơ sở để xác định đường găng
Đường găng (đường tới hạn) là đường nối các sự kiện găng. Sự kiện
găng là sự kiện có thời gian dự trữ bằng không.
 Thứ ba, là căn cứ để để xác định khả năng thực hiện tiến độ thời
gian dự kiến đạt đến các sự kiện (điểm nút). Trên cơ sở các thông tin về thời
gian cực tiểu (a), thời gian thường xuất hiện (m), thời gian cực đại (b), thời
gian sớm nhất đạt tới sự kiện (E j), thời gian muộn nhất sự kiện nào đó phải
được thực hiện (Lj) và dựa vào lý thuyết xác suất thực hiện tiến độ thời gian
dự kiến đạt tới các sự kiện. Đây là cơ sở kiểm tra tiến độ, điều chỉnh, khắc
phục những bất hợp lí có thể xảy ra.
Thời gian dự trữ của các công việc:
Trong quản lý dự án việc quản lý thời gian dữ trữ các công việc giữ vị
trí quan trọng, trên cơ sở thông tin về thời gian dự trữ các công việc, cán bộ
quản lý dự án có thể bố trí lại trình tự thực hiện các công việc theo mục tiêu
giảm bớt chi phí mà vẫn đảm bảo thực hiện dự án đúng thời hạn.


GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


11

Thời gian dự trữ toàn phần của một công việc nào đó là khoảng thời
gian công việc này có thể kéo dài thêm nhưng không làm chậm ngày kết thúc
dự án.
Kí hiệu:
ES(a): Thời gian bắt đầu sớm của công việc a
EF(a): Thời gian kết thúc sớm của công việc a
t(a): Độ dài thời gian thực hiện công việc a
LS(a): Thời gian bắt đầu muộn của công việc a
LF(a): Thời gian kết thúc muộn của công việc a
LF(cc): Thời gian kết thúc muộn của công việc cuối cùng
EF(a) = ES(a) + T(a)
ES(a) = Max(EFj)

(j là công việc trước a)

ES1=0
LF(a)=Min(LSj)

(j là công việc đứng sau a)

LS(a)= LF(a) – t(a)
LFcc = thời gian thực hiện dự án
Thời gian dự trữ toàn phần(a) = LS(a) - LF(a)


GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


12

Ví dụ:

Hình 1. Sơ đồ mạng PERT của dự án A

Công
việc

Thời
gian

ES

EF

LS

Thời gian dự trữ
toàn phần

LF

A


2

0

2

0

2

0

B

8

0

8

5

13

5

C

3


2

5

2

5

0

D

2

5

7

9

11

4

E

10

5


15

5

15

0

F

4

8

12

13

17

5

G

4

7

11


11

15

4

H

1

15

16

17

18

2

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


13

I


3

15

18

15

18

0

J

2

18

20

18

20

0

Bảng 1: Thời gian dự trữ toàn phần của các công việc
theo chương trình bình thường của dự án A
1.7 Cách thành lập sơ đồ mạng Pert:
Mỗi công việc hay thao tác được biểu diễn bằng một cung. Công việc

được kí hiệu bằng chữ hay số kèm theo thời gian thực hiện được ghi trong
ngoặc
Các đỉnh của đồ thị biểu diễn kết thúc các công việc (hoặc các công
việc bộ phận)
Các đỉnh được bố trí để phản ánh các hạn chế về trình tự thực hiện (nối
tiếp hay đồng thời) các công việc.
Ví dụ đồ thị dưới đây biểu diễn 4 công việc a, b, c, d với thời gian thực
hiện tương ứng 6, 2, 5, 8. Các công việc a, b có thể thực hiện đồng thời,
ngược lại công việc d chỉ có thể bắt đầu sau khi thực hiện xong công việc b,
còn c chỉ bắt đầu sau khi hoàn thành xong cả a lẫn d. Đỉnh 1 đánh dấu khởi
đầu công việc a và b trong khi đỉnh 4 ứng với kết thúc công việc c

Hình 2: Cách thành lập sơ đồ PERT
Sơ đồ mạng lưới Pert là một hình thức mô tả trình tự thực hiện các
công việc của dự án nhằm đạt một mục tiêu nào đó (tiết kiệm thời gian, chi
phí…)
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


14

Hai yếu tố cơ bản của sơ đồ mạng lưới:
 Các công việc biểu thị bằng các cạnh có hướng
 Các sự kiện được biểu thị bằng các đỉnh
Trong đó một đỉnh vào là sự kiện bắt đầu và đỉnh ra là sự kiện hoàn
thành toàn bộ
Nguyên tắc chung:
 Giữa hai đỉnh bất kỳ chỉ duy nhất có một cạnh nối liền

 Trong sơ đồ không có chu trình, các cạnh không nên bắt chéo
nhau khi không cần thiết
Thực hành:
Nếu có nhiều công việc cùng làm song song thì:
 Hoặc gộp chúng lại thành một công việc lớn và thời gian bằng
tổng các thời gian gộp lại nếu chúng cùng tính chất công việc
 Hoặc lập thành các đỉnh mới và các cạnh giả và thời gian tij=0

Hình 3a

Hình 3b

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


15

Hình 3c
Hình 3: Cách thành lập sơ đồ PERT
Nếu có một nhóm công việc tạo thành một mạch con khi đưa vào mạch
lớn ta coi là một việc, thời gian bằng đường găng của mạch con.

Hình 4a

Hình 4b
Hình 4: Cách thành lập sơ đồ PERT
Một số trường hợp vẻ mạng PERT có sử dụng biến giả tránh các công
việc có cùng nút bắt đầu và cùng nút kết thúc (xem phần phụ lục)


GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


16

Chương II: PHƯƠNG PHÁP/KĨ THUẬT
RÚT NGẮN ĐƯỜNG TỚI HẠN TRONG MẠNG PERT
2.1 Một số khái niệm liên quan đến rút ngắn đường tới hạn:
2.1.1 Chi phí trực tiếp:
Chi phí trực tiếp: là những khoản mục chi phí có thể xác định cụ thể,
trực tiếp cho từng công việc cụ thể hoặc dự án. Chi phí trực tiếp được dự toán,
kiểm soát và quản lí dễ dàng hơn chi phí gián tiếp.
Ví dụ:
 Chi phí nguyên vật liệu trực tiếp: tiền lương trả cho những người
trực tiếp thực hiện các công việc dự án.
 Chi phí thiết bị trực tiếp: chi phí máy móc thiết bị công cụ sản xuất
được sử dụng để thực hiện từng công việc dự án.
 Chi phí dịch vụ trực tiếp: là những chi phí liên quan đến công việc
hay toàn bộ dự án như chi phí thuê máy, chi phí thiết kế.
 Chi phí quản lí trực tiếp: tiền lương giám đốc, nhân viên lập kế
hoạch, kế toán, thư kí, nhân viên quản lý chất lượng.
2.1.2 Chi phí gián tiếp:
Là chi phí không được tính trực tiếp cho từng công việc nhưng lại rất
cần thiết để duy trì hoạt động của dự án.
Ví dụ:
 Chi phí lao động gián tiếp: tiền lương của nhân viên bảo trì thiết bị,
bảo vệ, nhân viên dọn vệ sinh, những người lao động phục vụ hoạt

động chung của dự án.
 Chi phí nguyên vật liệu gián tiếp: bao gồm nguyên vật liệu được sử
dụng để quét dọn, lau chùi các thiết bị.

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


17

 Chi phí thiết bị gián tiếp: bao gồm chi phí máy tính, máy photo, fax.
 Chi phí văn phòng dự án: tiền thuê văn phòng, điện, nước, thiết bị
văn phòng, điện thoại, internet.
2.1.3 Chi phí liên quan đến thời gian:
 Chi phí thiết bị tăng thêm khi kéo dài thời gian thực hiện công việc.
 Chi phí điện nước tăng lên do kéo dài thời gian hoạt động của văn
phòng dự án.
 Chi phí tiền công tăng lên khi rút ngắn thời gian thực hiện các công
việc của dự án do phải làm thêm giờ.
 Chi phí lao động hợp đồng trên một đơn vị thời gian không thay đổi dù
kéo dài thời gian thực hiện nhưng năng suất lao động có thể bị ảnh
hưởng.
 Đơn giá hợp đồng không bị ảnh hưởng bởi yếu tố thời gian.
2.1.4 Phương pháp thực hiện kế hoạch chi phí cực tiểu:
Kế hoạch chi phí cực tiểu là phương pháp rút ngắn tiến độ thực hiện
những công việc lựa chọn sao cho chi phí tăng thêm cực tiểu, giảm tổng chi
phí và rút ngắn hợp lý độ dài thời gian thực hiện dự án.
Thời gian bình thường: là thời gian hoàn thành công việc trong những
điều kiện bình thường, không có những thay đổi đột biến về thiết bị, lao động,

các nhân tố bên ngoài…
Chi phí bình thường: chi phí cho một công việc nào đó được thực hiện
trong điều kiện bình thường (gắn với thời gian bình thường nêu trên).
Thời gian rút ngắn: thời gian thực hiện công việc trong điều kiện đã
được rút ngắn đến mực cho phép hợp lý (không thể rút ngắn thêm được nữa)
trong điều kiện kỹ thuật, trình độ lao động, các nhân tố khác hiện tại.
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


18

Chi phí rút ngắn: chi phí thực hiện công việc gắn với thời gian rút
ngắn, là mức chi phí được xem là cao nhất khi thời gian thực hiện công việc
đó không thể rút ngắn thêm trong điều kiện hiện tại.
2.2 Bài toán tính xác suất hoàn thành dự án:
Bài toán xuôi: Cho n công việc có ràng buộc trước sau với thời gian
thực hiện mỗi công việc bao gồm: thời gian thuận lợi (a), thời gian khó khăn
(b), thời gian có khả năng (m). Tính xác suất hoàn thành dự án.
Bài toán ngược: Cho n công việc có ràng buộc trước sau với thời gian
thực hiện mỗi công việc bao gồm: thời gian thuận lợi (a), thời gian khó khăn
(b), thời gian có khả năng (m). Tính số ngày cần hoàn thành dự án với xác
suất cho trước.
Thời gian thực hiện từng hoạt động của dự án nói chung là một lượng
biến động khó dự đoán trước, chúng ta giả thiết chúng là các biến ngẫu nhiên.
Giả sử ta có các số liệu ước tính về thời gian thực hiện các hoạt động của dự
án a, m, b.
Lúc đó thời gian trung bình và độ lệch chuẩn thời gian thực hiện các hoạt
động được ước tính theo các công thức:


Z: là hệ số GAUSS, Z>dự án hoàn thành muộn, Z<0 dự án hoàn thành
sớm
S: thời gian dự kiến hoàn thành toàn bộ dự án
D: Độ dài thời gian hoàn thành các công việc găng

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


19

Độ lệch chuẩn của thời gian hoàn thành các công việc găng
Khi đó:

: Thời gian thực hiện công việc găng thứ i
Phương sai càng lớn thì tính không chắc chắn về thời gian hoàn thành
dự án tăng

: Phương sai hoàn thành dự án
i: là các công việc găng
: phương sai các công việc găng và được tính như sau:
a: thời gian dự án diễn ra trong điều kiện thuận lợi (thời gian sớm)
b: là thời gian dự án diễn ra trong điều kiện khó khăn (thời gian muộn)
m: thời gian phù hợp (có khả năng)
: Độ lệch tiêu chuẩn, độ biến thiên

GVHD: Thầy giáo Nguyễn Thế Dũng


Sinh viên thực hiện: Nguyễn Thị Tú Anh


20

Phương pháp xác định xác suất hoàn thành dự án

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


21

2.2.1 Ví dụ minh họa:
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


22

Ví dụ: Cho sơ đồ mạng Pert sau:

Hình 1: Sơ đồ mạng PERT của dự án A

Thời gian ước tính
Công việc

a


m

b

t

Sớm
nhất

Khả năng
xảy ra
nhiều nhất

muộn
nhất

Thời
gian
trung
bình

Độ lệch
tiêu chuẩn,
độ biến
thiên

A

1


2

3

2

2/6

B

6

8

10

8

4/6

C

3

2

7

3


4/6

D

1

2

3

2

2/6

E

5

11

11

10

6/6

F

2


3

10

4

8/6

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


23

G

1

4

7

4

6/6

H


1

1

1

1

0

I

2

3

4

3

2/6

J

1

2

3


2

2/6

Bảng 2: Thời gian ước tính các công việc
Bước tiếp theo là lập sơ đồ mạng cho dựán với các thời gian trung bình
T và tìm đường găng. Đường găng là A CE IJ
Các công việc này có độ trễ cho phép bằng 0, hay nói cách khác, không
cho phép sự chậm trễ nào.
Ta tìm kì vọng của T (thời gian trung bình thực hiện dự án) theo công
thức:
m = mT = tA+ tC + tE + tI + tJ = 20 (tuần).
Tính độ lệch chuẩn của thời gian thực hiện dự án:

Ta coi T là biến ngẫu nhiên phân phối chuẩn
Ta tính được N(m=20, σ =1,333)
Tính số tuần tối thiểu để dự án hoàn thành với độ tin cậy là 90%?
Đặt P(T<=t) = 90% Tra bảng phân phối chuẩn tắc N(0,1) tìm được
Z=1,28
Z = (T-20)/1,33=1,28 => T=21,7
Dự án đang xem xét có khả năng hoàn thành với độ tin cậy tới 90%
trong vòng (không vượt quá) 22 tuần.

GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh


24


Có thể sử dụng hàm tính phân phối xác suất chuẩn và công cụ Goal
seek trong Microsoft Excel để tính giá trị ngược, cho biết số tuần cần hoàn
thành dự án khi biết xác suất tương ứng
2.3 Kĩ thuật rút ngắn đường đi trong mạng Pert sử dụng quy hoạch tuyến
tính đa mục tiêu
2.3.1 Sơ lược về lý thuyết về quy hoạch tuyến tính:
Trong toán học, quy hoạch tuyến tính là bài toán tối ưu hóa, trong
đó hàm mục tiêu và các điều kiện ràng buộc được mô tả bằng các đẳng thức
và bất đẳng thức tuyến tính.
Mô hình quy hoạch tuyến tính đa mục tiêu:
Trong các bài toán kĩ thuật, công nghệ, quản lí, kinh tế nông nghiệp v.v...
nảy sinh từ thực tế, chúng ta thường phải xem xét để tối ưu hoá đồng thời một
lúc nhiều mục tiêu.
Bài toán tối ưu đa mục tiêu mà trong đó miền ràng buộc D là tập lồi đa
diện và các mục tiêu zi= fi(X), với i = 1, 2,…, p là các hàm tuyến tính xác định
trên D, được gọi là bài toán quy hoạch tuyến tính đa mục tiêu. Khi đó, ta có
mô hình toán học sau đây được gọi là mô hình quy hoạch tuyến tính đa mục
tiêu:
Max CX với ràng buộc trong đó
C là ma trận cấp p x n

Với A là ma trận cấp m x n và
Ví dụ: Bài toán quy hoạch tuyến tính với 2 mục tiêu:
f1(X)=x1+2x2min
f2(X)=2x2max
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh



25

Với các ràng buộc:
-x1 + x2 ≤ 3
x1+ x2 ≥ 3
x1, x2 ≥ 0
Có thể nói, bài toán quy hoạch tuyến tính đa mục tiêu là bài toán quy
hoạch tuyến tính mà trong đó chúng ta phải tối ưu hoá cùng một lúc nhiều
mục tiêu.Tuy nhiên, các mục tiêu này thường đối chọi cạnh tranh với
nhau.Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số
mục tiêu khác. Vì vậy, việc giải các bài toán tối ưu đa mục tiêu tức là tìm ra
một phương án khả thi tốt nhất theo một nghĩa nào đó.
2.3.2 Bài toán:
Phát biểu bài toán tổng quát:
Có n công việc ràng buộc trước sau về thời gian trong mạng PERT. Mục
tiêu của bài toán là rút ngắn thời gian thực hiện ở từng công việc sao cho tổng
thời gian rút ngắn và chi phí trực tiếp tăng lên sau khi rút ngắn là nhỏ nhất.
Bài toán tổng quát được chuyển về như sau:
Hàm mục tiêu: cần cực tiểu hóa cả thời gian thực hiện dự án lẫn tổng chi
phí gia tăng.
min (thời gian)
min (chi phí)
Các ràng buộc:

Trong đó:
n: là số công việc
GVHD: Thầy giáo Nguyễn Thế Dũng

Sinh viên thực hiện: Nguyễn Thị Tú Anh