01/27/14
LUẬN VĂN TỐT NGHIỆP
•
Đề Tài: Điều Hành Dự Án Bằng
Phương pháp PERT-CPM và Ứng
Dụng Giải Bài Toán Lập Lòch Thi
Công Công Trình
•
Giáo Viên Hướng Dẫn:
•
Đỗ Như An
•
Sinh Viên:
•
Đàm Văn Khởn
01/27/14
Nội Dung Đề Tài
•
ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG
PHÁP PERT-CMP
•
CƠ SỞ VỀ LÝ THUYẾT ĐỒ THỊ
•
BÀI TOÁN LẬP LỊCH THI CÔNG CÔNG
TRÌNH
•
CÀI ĐẶT BÀI TOÁN
•
KẾT LUẬN
•
LỜI CẢM ƠN

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 hoá hiệu quả (về thời
gian và tiết kiệm nguyên liệu).
01/27/14
•
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 theo đặt hàng của hải quân
Mỹ, dùng để điều hành các hoạt động nghiên cứu
và phát triển chương trình tên lửa đối cực.
01/27/14

Có nội dung là lập một sơ đồ mạng lưới (arrow
network diagram hoặc arrow diagram), tương tự
một đồ thò có hướng. Pha này mở đầu bằng việc
tách dự án thành nhiều hoạt động riêng và đònh
thời gian hoàn thành chúng. Trong mạng, mỗi
cung có hướng biểu diễn hoạt động và cả sơ đồ
mạng biểu thò mối quan hệ giữa các hoạt động.
Mỗi nút biểu thò một biến cố hoặc sự kiện (event),
đánh dấu hoàn thành một số hoạt động (activity)
là các cung đi vào nút, và bắt đầu các hoạt động
ứng với các cung ra khỏi nút.
01/27/14
•
Pha đầu của phương pháp PERT-CPM là lập kế
hoạch thể hiện ở một sơ đồ mạng lưới, biểu diễn
như một đồ thò có hướng.
•
Ví dụ: hãy xét một dự án xây dựng một toà 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ình sau:
•
Các số bên cạnh cung là thời gian thực hiện hoạt
động đó.
01/27/14
01/27/14
•
Pha điều hành

j
, các L
j
được tính theo hướng lùi
01/27/14
•
Pha kiểm tra
Bao gồm việc sử dụng sơ đồ mạng lưới,
và biểu đồ thời gian để theo dõi và báo
cáo đònh kì tiến triển của dự án. Nếu cần
thì phải phân tích lại và xác đònh sơ đồ
mới cho phần dự án còn lại.
01/27/14
•
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 toá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.
01/27/14
Cơ Sở Lý Thuyết Về Đồ Thò
•
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
•

1

và e
2
được gọi là cạnh lặp nếu chúng cùng tương ứng
với một cặp đỉnh.
•
Giả đồ thò vô hướng G = (V,E) bao gồm V là tập các
đỉnh, và E là họ các cặp không có thứ tự gồm hai
phần tử (không nhất thiết phải khác nhau) của V gọi
là các cạnh. Cạnh e được gọi là khuyên nếu có dạng
e = (u,u).
01/27/14
•
Đơn đồ thò có hướng G =(V,E) bao gồm V là
tập các đỉnh, và E là tập 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.
•
Đ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.
01/27/14
Biểu Diễn Đồ Thò Trên Máy Tính
•

ứng chính xác đến cách đánh số đỉnh (còn nói là:
chính xác đến đẳng cấu), với một đơn đồ thò vô
hướng n đỉnh.
+ Tổng các phần tử trên dòng i (cột j) của ma trận
kề chính bằng bậc của đỉnh i (đỉnh j).
+ Nếu ký hiệu a
ij
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.
01/27/14
•
Danh sách cạnh (cung).
+ Trong trường hợp đồ thò thưa (đồ thò có số cạnh m thỏa
mãn bất đẳng thức m < 6n) người ta thường dùng cách
biểu diễn đồ thò dưới dạng danh sách cạnh.
+ Trong cách biểu diễn đồ thò bởi danh sách cạnh (cung)
chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung)
của đồ thò vô hướng (có hướng). Mỗi cạnh (cung) e =
(x, y) của đồ thò sẽ tương ứng với hai biến Dau[e],
Cuoi[e]. Như vậy, để lưu trữ đồ thò ta cần sử dụng 2m
đơn vò bộ nhớ. Nhược điểm của cách biểu diễn này là
để xác đònh những đỉnh nào của đồ thò là kề với một

việc, nếu công việc i phải được thực hiện trước
công đoạn j thì trên đồ thò có cung (i, j), trọng số
trên cung này được gán bằng t[i].