TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
BỘ MÔN KHOA HỌC CƠ BẢN
BÀI GIẢNG
QUY HO CH TUY N Ạ Ế
T NHÍ

CHƯƠNG III:
MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI
3.1. Khái niệm đồ thị và sơ đồ mạng lưới
3.2. Quy tắc thực hành lập sơ đồ mạng lưới
3.3. Phân tích sơ đồ mạng lưới theo chỉ tiêu
thời gian
3.4. Sơ đồ mạng lưới với các yếu tố thời gian
và chi phí
3.5. Bài toán cân đối tài nguyên

3.1. Các khái niệm:
1. Đồ thị:
- Một tập hợp các điểm A
1
, A
2
, ,A
n
được nối liền với nhau
bởi các cạnh có độ dài u
1
, u
2
, ,u

j
( i ≠ j ) mà không có chiều ngược lại.

Dây chuyền: là một dãy các đỉnh, cạnh nối nhau liên tiếp.
Nếu các cạnh trên dây chuyền là có hướng nối đuôi nhau thì
dây chuyền đó trở thành một đường đi.
Chu trình: là một đường đi đóng kín.
Khuyên: là một đường xuất phát từ 1 đỉnh rồi lại quay về
đỉnh đó mà không đi qua bất kỳ đỉnh nào khác.
Đồ thị đơn: Giữa hai đỉnh bất kỳ A
i
, A
j
(i ≠ j) chỉ có nhiều
nhất là một cạnh có hướng.

2. Mạng:
Trước hết ta quy ước cho một điểm A
i
các cạnh đi tới ký
hiệu u
i
+
, các cạnh từ A
i
ra ký hiệu u
i
−
, trên mỗi cạnh u (i,j) gán
một số dương t

A
1
7

A
3
6 A
6
8 A
7
3 4 6

A
4
(Hình 1)
A
1
là đỉnh vào, A
7
là đỉnh ra.
Đường găng là đường nối các đỉnh A
1
, A
3
, A
6
, A
7
.
Ký hiệu đường Găng:

Trong đó một đỉnh vào là sự kiện khởi công và đỉnh ra là sự
kiện hoàn thành toàn bộ.

3.2. Quy tắc thực hành lập sơ đồ mạng lưới:
1. 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
chúng.
- Trong một sơ đồ không có chu trình nói chung các cạnh
không nên bắt chéo nhau khi không cần thiết.

2. Quy tắc thực hành:
a. Nếu có nhiều công việc cùng làm song song (cùng khởi
công và cùng kết thúc) (hình 1a) 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 (hình 1b).
-Hoặc lập thành các đỉnh mới và các cạnh giả và thời gian t
ij

= 0 (hình 1c).
i
j
t
1
+t
2
+t
3
Hình 1b
i j

1
x
2
x
3
x
4
x
5
Hình 2a
i
j
Z
1
Z
2
T
Hình 2b

c. Nếu Z
4
khởi công sau khi xong Z
1
, Z
2
còn Z
5
khởi công sau
khi xong Z
1

Z
2
Z
3
Z
4
Z
5
Z
1
Z
2
Z
3
Z
4
Z
5
Hình 3a Hình 3b
(Sai)
Hình 3c

d. Khi chia nhỏ công việc chẳng hạn công việc a, b, c bắt đầu
sau khi hoàn thành 1/3 ; 2/3 và cả công việc X thì vẽ như hình 4
X/3 X/3 X/3
a
b c
Hình 4
X
a

, , y
10
:
Thứ tự Tên công
việc
Thời hạn
(tháng)
Thứ tự tiến hành
1 y
1
2 Bắt đầu ngay
2 y
2
4 Bắt đầu ngay
3 y
3
3 Bắt đầu ngay
4 y
4
5 Khởi công sau khi xong y
1
5 y
5
4 Khởi công sau khi xong y
1
6 y
6
6 Khởi công sau khi xong y
1
7 y

Công việc 1 2 3 4 5 6 7 8 9 10 11 12 1 2
y
1
y
2
y
3
y
4
y
5
y
6
y
7
y
8
y
9
y
10

● Lập sơ đồ mạng:
y
5
0
1
2
3
4


♦ So sánh hai loại sơ đồ: Sơ đồ mạng có những ưu nhược điểm:
+ Ưu điểm:
- Nhờ hai yếu tố công việc sự kiện mà quá trình thi công được nêu 1
cách toàn cục, người chỉ đạo theo dõi được cả tổng thể và cá biệt.
- Có kế hoạch nhịp nhàng và kiểm tra được từng khâu công việc.
- Thấy vị trí từng việc và ảnh hưởng của nó.
- Đặc biệt thấy được khâu chủ yếu (đường Găng) để tập trung chỉ đạo
dứt điểm.
+ Nhược điểm:

- Số lượng công việc trong từng thời điểm chưa được thể hiện rõ.
- Trong các trường hợp phải cân đối tài nguyên thì sơ đồ mạng chưa
phát huy được tác dụng.
Trong quá trình lập kế hoạch và chỉ đạo thực hiện kế hoạch
người ta thường kết hợp cả hai dạng sơ đồ.

3.3. Phân tích sơ đồ mạng lưới theo chỉ tiêu thời gian:
1. Thời điểm sớm nhất hoàn thành sự kiện:
Ký hiệu: (i, j) là một cạnh của mạng
t
j
(s) là thời điểm sớm nhất hoàn thành sự kiện j,
j = 0, 1,…, n, n + 1

t
0
(s) = 0
t
j

7
3
y
6
6
y
4
5
4
y
10
5
y
9
4
Hình 7
t
0
(s) = 0 ; t
1
(s) = t
0
(s) + 2 = 2 ; t
2
(s) = t
0
(s) + 3 = 3 ;
t
3
(s) = max {t

n
(m) = t
n
(s)
t
i
(m) = min {t
j
(m) − t
ij
}, j = 1, 2, …n −1.
Ví dụ: Tìm các t
j
(m) trong sơ đồ hình 7
t
6
(m) = t
6
(s) = 14 ; t
5
(m) = t
6
(m) – 4 = 10 ;
t
4
(m) = t
6
(m) – 5 = 9 ; t
3
(m) = t

i
là thời gian dự trữ của sự kiện thứ i thì ta có:
D
i
= t
i
(m) − t
i
(s)
Tại sự kiện găng thì D
i
= 0.

B – Thời điểm sớm nhất, muộn nhất khởi công và hoàn
thành các công việc:
1. Thời điểm sớm nhất khởi công và hoàn thành công việc:
Ký hiệu t
ij
k
(s) và t
ij
h
(s) là các thời điểm sớm nhất để khởi
công và hoàn thành công việc, ta có :
t
k
ij
(s) = t
i
(s)

ij
(m) = t
h
ij
(m) − t
ij
= t
j
(m) − t
ij

3. Dự trữ chung của mỗi công việc:
Dự trữ chung của mỗi công việc là hiệu giữa thời gian
hoàn thành muộn nhất và sớm nhất của công việc đó
Gọi D
ij
(c) là dự trữ chung của công việc u
ij
thì ta có :
D
ij
(c) = t
k
ij
(m) − t
k
ij
(s) = t
h
ij