Bài giảng Toán kinh tế - Nguyễn Hoàng Anh Khoa

a
 
 
 
 
 
 
Hệ {Ak | xk > 0} gọi là hệ liên kết của phương án x. 
Định lí: Giả sử x = (x1 ; x2 ;; xn) là một phương án khác không của bài toán 
QHTT dạng chính tắc. Khi đó, x là phương án cực biên khi và chỉ khi hệ liên kết 
của x độc lập tuyến tính 
Th.s. Nguyễn Hoàng Anh Khoa 
 7 
Ví dụ: Xét bài toán 
1 2 3
1 2 3
1 2 3
j
Z 4x x x min
2x x x 5
x x 4x 2
x 0, j 1,3.
   
   

  

 
Chứng minh x = (7/3;1/3;0) là phương án cực biên. 
2.4 Phương pháp đơn hình 
Trong mục này ta chỉ xét bài toán QHTT dạng chính tắc 
Z c,x min
Ax B
x 0
   



A cỡ mxn và rankA = m ≤ n 
Giả sử x0 = (x10; x20; ; xm0; 0; ;0) với xi0 >0, i =1,2,..,m là phương án cực biên 
Khi đó, A1,A2, ..., Am là hệ liên kết hay x10A1 + x20A2 + + xm0Am = B 
Với mỗi Aj tìm Xj = (x1j; x2j; ; xmj) sao cho x1jA1 + x2jA2 + + xmjAm = Aj 
Đặt j = c1x1j + c2x2j + + cmxmj – cj 
2.4.1 Các định lí 
Định lý 1:(Dấu hiệu tối ưu) 
Nếu j ≤ 0, j thì x0 là phương án tối ưu, và ngược lại. 
Định lý 2: 
Nếu tồn tại j > 0 và xkj ≤ 0 với k =1,2,..,m, thì bài toán Quy hoạch tuyến tính 
dạng chính tắc không có phương án tối ưu. 
Định lí 3: 
Nếu tồn tại k, s sao cho   0 0max : 0 và min : 0
 
        
 
i s
j j k ik s
ik sk
x x
x
x x
 
Xét cơ sở mới bằng cách thay As
bởi Ak. Khi đó, phương án X ứng với cơ sở mới 
là phương án tốt hơn phương án X0 
Ví dụ: Xét bài toán 
1 2 3
1 2 4
2 3 4
( ) 2 2 min
4 6
2 5 8
0, 1,2,3,4.
   
   

   
   j
f x x x x
x x x
x x x
x j
Chứng minh x = (6;0;8;0) là phương án cực biên nhưng không là phương án tối ưu. 
Áp dụng định lí 3 tìm phương án tốt hơn, kiểm xem phương án mới có phải là 
phương án tối ưu không? 
Th.s. Nguyễn Hoàng Anh Khoa 
 8 
2.4.2 Bài toán QHTT dạng chính tắc có sẵn ma trận đơn vị 
Xét bài toán 
( ) , min
0
   



f x c x
Ax b
x
Trong đó, b > 0 và A có sẵn một ma trận đơn vị cấp m. Không mất tính tổng quát 
có thể giả sử đó là m cột đầu A1, A2,..,Am. Lúc đó, phương án cực biên x trong 
bước lặp đầu tiên là: x0 = (b1,b2,...,bm, 0, ..,0) hệ liên kết là A1, A2,..,Am. 
Hơn nữa, Xj = (a1j; a2j; ; amj) 
Để thuận tiện ta sắp xếp dữ liệu lên bảng như sau (gọi là bảng đơn hình) 
Cơ sở H.số P.án 
c1 c2 ... cm cm+1 ... cn 
X1 X2  Xm Xm+1  Xn 
A1 
A2 
: 
Am 
c1 
c2 
: 
cm 
b1 
b2 
: 
bm 
1 
0 
: 
0 
0 
1 
: 
0 
... 
... 
... 
0 
0 
: 
1 
a1m+1 
a2m+1 
: 
amm+1 
 a1n 
a2n 
: 
amn 
 f(x0) 0 0 ... 0 m+1 n 
Áp dụng định lí 1,2,3 ta có thuật toán đơn hình 
Bước 1: Tính j , j = 1,2,..,n 
Nếu j ≤ 0 với j = 1,2,..,n. thì x0 là phương án tối ưu. 
Nếu tồn tại j > 0 và xkj ≤ 0 với k =1,2,..,m, thì bài toán không có phương án tối ưu. 
Bước 2: Xác định k,s sao cho 
  0 0max : 0 và min : 0
 
        
 
i s
j j k ik s
ik sk
x x
x
x x
 
Bước 3: Thay As bởi Ak. Tìm phương án và các Xj ứng với hệ liên kết mới. 
Phương pháp: 
ij
' sk
ij
ik
ij sj
sk
x
khi i j
x
x
x
x x
x



 
 

. Quay về bước 1 
Ví dụ: Giải bài toán 
1 2 3 4 5
1 3 4 5
2 4 5
3 4 5 6
j
f (x) x x 2x 2x x min
x x x x 2
x x x 6
4x 2x 3x x 9
x 0, j 1,6.
     
   

  
    

  
Th.s. Nguyễn Hoàng Anh Khoa 
 9 
Giải: 
Vì [A1,A2,A6] là ma trận đơn vị. Ta có bảng đơn hình 
 1 -1 2 -2 -1 0 
CS HS PA X1 X2 X3 X4 X5 X6  
A1 1 2 1 0 1 1 -1 0 2 
A2 -1 6 0 1 0 1 1 0 6 
A6 0 9 0 0 4 2 3 1 4,5 
 0 0 -1 2 -1 0 
A4 -2 2 1 0 1 1 -1 0 
A2 -1 4 -1 1 -1 0 2 0 2 
A6 0 5 -2 0 2 0 5 1 1 
 -2 0 -3 0 1 0 
A4 -2 3 0,6 0 1,4 1 0 0,2 
A2 -1 2 -0,2 1 -1,8 0 0 -0,4 
A5 -1 1 -0,4 0 0,4 0 1 0,2 
 -9 -1,6 0 -3,4 0 0 -0,2 
Vậy phương án tối ưu là: x1 = 0; x2 = 2; x3 = 0; x4 = 2; x5 =1; x6 = 0 và fmin = – 9 
2.4.3. Bài toán QHTT dạng chính tắc không có sẵn ma trận đơn vị 
Xét bai toán 
( ) , min
(*)
0
   


f x c x
Ax b
x
trong đó A không có ma trận đơn vị 
Xét bài toán M 
1 2( ) .. min
( )
0
      


n n n mf x Mx Mx Mx
Bx b M
x
trong đó B = [A|I] cỡ mx(n+m), M là số lớn nhất. 
Định lí 4: Nếu x0 = (x10;x20;..;xn0) là phương án tối ưu của bài toán (*) thì 
x=(x10;x20;..;xn0;0;..;0) là phương án tối ưu của bài toán M và ngược lại. 
Chú ý: 
0,
0
0, 0
 
     
 
j j
j j j
j j
M
 
 
 
0,
0
0, 0
 
     
 
j j
j j j
j j
M
 
 
 
;
.
 
        
 
k j k j
k k k j j j
k j k j
M M
   
   
   
Th.s. Nguyễn Hoàng Anh Khoa 
 10 
BÀI TẬP CHƯƠNG 2 
Câu 1. Một xí nghiệp có 2 máy A, B dùng để sản xuất ra 3 loại sản phẩm. Định 
mức thời gian (đơn vị: giờ) cho mỗi đơn vị sản phẩm đối với từng máy và quỹ thời 
gian (đơn vị: giờ) của từng máy được cho trong bảng sau: 
 SP 
MÁY 
Định mức thời gian cho mỗi đơn vị sản phầm 
Quỹ thời gian SP1 SP2 SP3 
A 1 2 1 120 
B 
2 1 1 90 
Giá 1 SP 
(đv 1000 đ) 
40 30 35 
Hãy lập mô hình toán học cho bài toán: Tìm phương án sản xuất sao cho tổng thu 
nhập là lớn nhất mà vẫn đảm bảo an toàn cho máy. 
Câu 2. Hai địa phương Ninh Bình và Hưng Yên cung cấp Khoai với khối lượng 
200 tấn và 300 tấn cho 3 địa phương tiêu thụ Khoai là Hải Phòng, Nghệ An và 
Nam Định với yêu cầu tương ứng là 170 tấn, 200 tấn và 130 tấn cước phí vận 
chuyển (nghìn/ tấn) cho trong bảng sau: 
 Nơi tiêu thụ 
Hải Phòng Ngệ An Nam Định 
Ninh Bình 20 12 25 
Hưng Yên 12 24 14 
Hãy lập mô hình toán học cho bài toán: Tìm kế hoạch vận chuyển sao cho tổng chi 
phí nhỏ nhất. 
Câu 3. Giải các bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình: 
1 2 3 4 5
1 3 4 5
2 3 5
3 4 5 6
j
a) f (x) x x 2x 2x x min
x x x x 1
x x x 6
2x 4x 3x x 2
x 0, j 1, 6.
     
   

  
    

  
1 2 3 4
1 2 4
2 3 4
2 3 4
j
b) f (x) 2x x 3x x min
x 2x x 8
x x 4x 2
x 3 x 2x 4
x 0, j 1; 2;3; 4.
    
  

  

   
  
1 2 3 4
1 3 4
1 2 3 4
1 4
j
c) f (x) 3x 5x 2x x min
x 2x 2x 4
2x x x x 5
x 2x 6
x 0, j 1; 2;3; 4.
    
  

   

 
  
1 2 4
1 2 3
1 2 4
1 2
j
d) f (x) 2x x x min
2x x x 1
x x x 4
x x 2
x 0, j 1; 2;3; 4.
    
   

  

  
  
Th.s. Nguyễn Hoàng Anh Khoa 
 11 
Chương 3. BÀI TOÁN VẬN TẢI 
3.1. Các khái niệm 
3.1.1. Bài toán vận tải 
a. Bài toán 
Có m địa điểm A1,A2,..,Am cùng sản xuất một loại hàng với lượng hàng là a1,a2,..,an. 
Có n địa điểm B1,B2,..,Bn cùng tiêu thụ loại hàng đó với lượng hàng là b1,b2,..,bn. 
Hàng một đơn vị hàng được vận chuyển từ Ai đến Bj với cước phí là cij. Gọi xij là 
lượng hàng vận chuyển từ Ai đến Bj. Xác định xij , i=1,2,,m ; j =1,2,..,n để tổng 
cước phí vận chuyển nhỏ nhất. (hàng được vận chuyển cho đến khi hết hàng hoặc 
nhu cầu)
b. Mô hình bài toán vận tải 
 
 
1 1
1
1
min (1)
1, (2)
1, (3)
0 (4)
 


 
 
 




m n
ij ij
i j
n
ij i
j
m
ij j
i
ij
Z c x
x a i m
x b j n
x
Bài toán vận tải là bài toán QHTT gồm m+n ràng buộc và mn biến số. Một ma 
trận X gồm các số thực xij không âm thỏa mãn m+n ràng buộc được gọi là một 
phương án vận tải. Một phương án vận tải cho tổng chi phí vận tải thấp nhất được 
gọi là phương án vận tải tối ưu (hay nói gọn là phương án tối ưu). 
c. Dạng bảng của bài toán vận tải 
Thu 
Phát 
b1 b2  bj  bn 
a1 
c11 
x11 
c12 
x12 
... c1j 
x1j 
... c1n 
x1n 
a2 
c21 
x21 
c22 
x22 
... c2j 
x2j 
... c2n 
x2n 
: 
: : : : 
ai 
ci1 
xi1 
ci2 
xi2 
... cij 
xij 
... cin 
xin 
: 
: : : : 
am 
cm1 
xm1 
cm2 
xm2 
... cmj 
xmj 
... cmn 
xmn 
Th.s. Nguyễn Hoàng Anh Khoa 
 12 
3.1.2. Bài toán cân bằng thu phát 
Bài toán vận tải cân bằng thu phát là bài toán vận tải có tổng lượng hàng thu bằng 
tổng lượng hàng phát. 
1 1 
 
m n
i j
i j
a b 
Chú ý: Với điều kiện cân bằng thu phát bài toán vận tải trở thành bài toán QHTT 
dạng chuẩn 
 
 
1 1
1
1
min (1)
1, (2)
1, (3)
0 (4)
 


 
 
 




m n
ij ij
i j
n
ij i
j
m
ij j
i
ij
Z c x
x a i m
x b j n
x
Nhận xét: rankA = m + n – 1 
Định lí: Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu. 
3.2. Phương pháp tìm phương án cực biên ban đầu 
Trong mục này ta chỉ xét bài toán vận tải cân bằng thu phát 
+ Ta gọi một đường đi là tập hợp các ô của bảng sao cho cứ hai ô liên tiếp thì nằm 
trên cùng một dòng hay một cột. Một đường đi khép kín được gọi là chu trình. 
+ Giả sử x = (x11,x12,...,x1n, x21,x22,...,x2n,..., xm1,xm2,...,xmn) là một phương án của 
bài toán vận tải, nếu xịj > 0 thì ô (i,j) gọi là ô chọn. 
Định lí: Phương án x là một phương án cực biên của bài toán vận tải và chỉ khi tập 
các ô chọn tương ứng với nó không chứa chu trình. 
3.2.1. Phương pháp góc Tây-Bắc 
Chúng ta ưu tiên phân phối lượng hàng nhiều nhất vào ô ở góc Tây Bắc. 
Nếu nơi nào đủ hàng thì ta xóa cột chứa nơi nhận đó; nếu nơi phát nào hết hàng thì 
ta xóa dòng chứa nơi phát đó. 
( Đường đi) ( Chu trình ) 
X 
X 
X X 
X 
 X 
X 
X 
X X 
X X 
Th.s. Nguyễn Hoàng Anh Khoa 
 13 
3.2.2. Phương pháp cước phí cực tiểu 
Chọn ô cij có giá trị nhỏ nhất trong bảng chi phí vận chuyển. Tính và điền vào ô có 
giá trị xij = min (ai, bj). Sau đó, ta không xét hàng hoặc cột có dự trữ đã hết hay nhu 
cầu đã thoả mãn. Nếu ai = bj thì không xét đồng thời cả cột Bj lẫn hàng Ai. 
Từ phần còn lại của bảng ta lại chọn ô có giá trị nhỏ nhất và quá trình phân phối 
tiếp tục cho đến khi thoả mãn nhu cầu ở các điểm tiêu thụ. 
Ví dụ: Tìm phương án cực biên của bài toán vận tải cho bởi bảng 
 35 25 45 
30 5 2 3 
75 2 1 1 
3.3. Phương pháp thế vị giải bài toán vận tải 
Định lí: Giả sử x = (x11,x12,...,x1n, x21,x22,...,x2n,..., xm1,xm2,...,xmn) là một phương án 
cực biên của bài toán vận tải. Tính  ij = u i + v j – c ij với  ij = 0 ở các ô chọn ký 
hiệu E (số ô chọn của E là m + n – 1) 
- Nếu  ij  0 với mọi (i,j) thì x là phương án tối ưu 
- Ngược lại, 
+ Giả sử  ij là ô có giá trị lớn nhất, đặt E:=E U (i,j) 
+ Gọi G là chu trình đi qua ô (i,j), tiến hành đánh dấu “+”, “-“ liên tiếp 
bắt đầu từ ô (i,j) được đánh dấu “+”. Kí hiệu G+ là tập các ô có dấu “+” 
và G
-
 là ô có dấu “-“. 
+ Giả sử min{xij |(i,j)G
-
} = xst và 
( , )
( , )
( , )


  

   


ij
ij ij
ij
x a i j G
x x a i j G
x i j G
 đặt E’:=E\(s,t). 
Khi đó, phương án x’ = (x’ij) là phương án cực biên mới tốt hơn phương án x. 
Các bước giải bài toán vận tải 
Bước 1: Thành lập một phương án cực biên ban đầu, số ô chọn là m+n-1, cũng có 
thể có ô chọn không. 
Bước 2: Xác định ui và vj 
 Tính  ij. Nếu  ij  0 với mọi (i,j) thì x là phương án tối ưu 
 Ngược lại, chuyển sang bước 3. 
Bước 3: Xây dựng phương án mới như định lí. Quay về bước 2. 
3.4. Một số dạng của bài toán vận tải 
+ Với bài toán vận tải có ô cấm, ta xem ô cấm như ô bình thường nhưng cước phí 
là M rất lớn rồi giải bình thường. 
+ Với bài toán vận tải không cần bằng thu phát, ta thêm vào trạm thu hoặc trạm 
phát giả với cước phí bằng 0 rồi giải bình thường. 
Th.s. Nguyễn Hoàng Anh Khoa 
 14 
BÀI TẬP CHƯƠNG 3 
Câu 1: Giải bài toán vận tải sau: 
 Thu 
Phát 
5 10 15 
10 1 2 1 
8 3 4 2 
12 3 1 3 
Câu 2: Giải bài toán vận tải sau: 
 Thu 
Phát 
8 7 5 
6 2 2 4 
4 3 1 2 
10 1 3 2 
Câu 3: Giải bài toán vận tải sau: 
 Thu 
Phát 
10 8 12 
15 1 3 2 
10 3 4 1 
Câu 4: Giải bài toán vận tải sau: 
 Thu Phát 15 10 
10 1 2 
8 3 4 
12 2 1 
Câu 5: Giải bài toán vận tải sau: 
 Thu 
Phát 
20 15 25 
10 1 3 3 
20 2 1 
30 1 2 3 
Th.s. Nguyễn Hoàng Anh Khoa 
 15 
Chương 4. BÀI TOÁN TỐI ƯU TRÊN MẠNG 
4.1. Một số khái niệm cơ bản 
4.1.1 Đồ thị, đồ thị có hướng 
Đồ thị: (Graph) là một cặp tập hợp, ký hiệu G = (X,A), trong đó X = {x1;x2;;xn} 
là tập các điểm (đỉnh, nút), A là tập các nhánh (cạnh, cung) nối tất cả hoặc một 
phần các điểm của đồ thị lại với nhau. Nhánh nối liền đỉnh i và j, ký hiệu là (i;j). 
Nhánh định hướng: Một nhánh được định hướng (ký hiệu mũi tên) gọi là cung. 
Đồ thị có hướng: Đồ thị G = (X,A) trong đó A là tập hợp các cung gọi là đồ thị 
định hướng (có hướng). 
4.1.2 Biễu diễn đồ thị dưới dạng ma trận 
Xét đồ thị G = (X,A). Ma trận liên hệ trực tiếp của đồ thị được ký hiệu là A = [aij] 
và được xác định như sau: 
ij
1, Gcócung(i, j)
a
0,G khôngcócung(i, j)

 

4.2 Mạng liên thông ngắn nhất. 
4.2.1 Bài toán 
Cho đồ thị vô hướng G = (X,A) trên mỗi cạnh đồ thị có gắn một số không âm, gọi 
là độ dài của cạnh đó (độ dài cạnh (i,j) ký hiệu cij). Hãy tìm một cây (đường nối tất 
cả các đỉnh) của đồ thị sao cho tổng độ dài các cạnh là nhỏ nhất 
4.2.2 Ý nghĩa bài toán 
Nếu coi các đỉnh của đồ thị là các trạm thông tin, trạm xăng  thì nên đặt đường 
dây, hệ thống cáp, ống dẫn xăng dầu  như thế nào để tiết kiệm chi phí nhất? 
4.2.3 Thuật toán Prim 
Ký hiệu T là tập các đỉnh và cạnh của cây (cần xác định T) 
Bước 1: Giải sử ckl = min{cij| (i,j)  A}. T:= {(k,l)} 
Bước 2: Kiểm tra T là mạng liên thông . Kết luận T. Ngược lại, sang bước 3 
Bước 3: Tìm cst = min {cij với xi  T và xj T}. T:=T{(s,t)}. Quay về Bước 2. 
Ví dụ : Tìm mạng liên thông ngắn nhất và tính độ dài của sơ đồ mạng 
2 
1 4 
2 
3 
4 
3 7 
5 
5 
7 
5 
6 
3 
4 5 
8 
7 
6 
Th.s. Nguyễn Hoàng Anh Khoa 
 16 
Giải 
Bước 1 : min(cij) = c12 = 2. T := {(1,2)} 
Bước 2 : min{c13 = 7; c14 = 5; c24 = 4 ;c25 = 7} = c24 = 4. T := {(1,2) ;(2,4)} 
Bước 3 : min{c13 = 7; c25 = 7 ; c43 =3 ; c45 = 5 ; c46 = 5; c47 = 8} = c43 = 3 
T := {(1,2) ;(2,4) ;(4,3)} 
Bước 4 : min{ c25 = 7 ; c45 = 5 ; c46 = 5 ; c47 = 8 ; c36 = 6} = c45 = 5 
T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5)} 
Bước 5 : min{c46 = 5 ; c47 = 8 ; c36 = 6 ; c57 = 3} = c57 = 3 
T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5) ;(5 ;7)} 
Bước 6 : min{ c46 = 5; c36 = 6 ; c76 = 4} = c76 = 4 
T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5) ;(5 ;7) ; (7 ,6)} 
Vậy độ dài l(T) = 2 + 4 + 3+ 5 + 3 + 4 = 21 
4.3 Bài toán đường đi ngắn nhất. 
4.3.1 Bài toán 
Cho đồ thị G = (X,A), trên mỗi nhánh của A ta gắn một số không âm, biểu thị độ 
dài của nhánh đó (nhánh (i,j) ký hiệu cij). Trên X lấy xs gọi là đỉnh xuất phát 
(nguồn) và đỉnh xt gọi là đỉnh kết thúc (đích). Vấn đề đặt ra là: Hãy tìm đường đi 
ngắn nhất từ đỉnh xs đến đỉnh xt (cung (i,j) chỉ được phép đi từ xi đến xj). 
4.3.2 Ý nghĩa bài toán 
Trong thực tê, việc di chuyển từ A đến B thông qua mạng lưới giao thông có sẵn là 
chuyện thường gặp (các cung tương ứng đường 1 chiều). Vần đề đặt ra là chọn 
đường đi ngắn nhất để đảm bảo việc tiết kiệm nhiên liệu, thời gian  
4.3.3 Thuật toán Difkatra 
Bước 1: 
L(xi) := +∞ (khi i ≠ s) (nhãn tạm thời) 
L(xs) := 0
+ 
 (xs gán nhãn cố định 0
+
) 
xp:=xs 
Bước 2: Kiểm tra xp = xt kết luận L(xt) = L(xp). 
 Ngược lại sang bước 3 
Bước 3: 
Thay đổi nhãn tạm thời của các đỉnh xi G(xp) (các đỉnh có gốc xp) 
L(xi) := min{L(xi); L(xp) + cpi} 
Tìm xj sao cho L(xj) = min{L(xi) với L(xi) là nhãn tạm thời} 
L(xj):= L(xj)
+
 (gán nhãn cố định cho xj) 
xp:=xj 
Quay về bước 2. 
Th.s. Nguyễn Hoàng Anh Khoa 
 17 
Ví dụ: Xét sơ đồ mạng 
Bằng thuật toán Difkatra tìm đường đi ngắn nhất từ x1 đến x7 
Giải 
Đỉnh x1 x2 x3 x4 x5 x6 x7 
Vòng 1 0+ +∞ +∞ +∞ +∞ +∞ +∞ 
Vòng 2 2+ 9 5 +∞ +∞ +∞ 
Vòng 3 9 5+ 2+8 +∞ +∞ 
Vòng 4 5+3+ 2+8 5+5 5+8 
Vòng 5 10 8+1+ 13 
Vòng 6 10+ 9+2 
Vòng 7 11+ 
Vậy đường đi ngắn nhất là x1 -> x4 -> x3 -> x6 -> x7 
Tổng độ dài là 5 + 3 + 1 + 2 = 11 
4.4. Phương pháp sơ đồ mạng lưới (Mạng Pert) 
4.4.1. Sơ đồ mạng Pert 
Mạng Pert là đồ thị định hướng với hai yếu tố cơ bản là công việc và sự kiện . 
- C
ông việc được biểu thị bằng một cạnh có hướng (cung ) 
- S
ự kiện được biểu thị bằng một đỉnh, tại đỉnh có sự kết thúc một số công 
việc và sự bắt đầu một số công việc. 
Trình tự lập sơ đồ mạng 
 Liệt kê tất cả công việc: các công việc phải được liệt kê theo đúng quy trình 
công nghệ, theo thứ tự thời gian trước sau. Nên lập theo bảng 
 Xác định thời gian thực hiện các công việc 
 Lập sơ đồ 
Quy tắc lập sơ đồ mạng 
 Quy tắc 1 sơ đồ lập từ trái sang phải 
2 
1 4 
2 
3 
4 
3 9 
5 
5 
7 
5 
6 
3 
2 5 
8 
8 
1 
Th.s. Nguyễn Hoàng Anh Khoa 
 18 
 Quy tắc 2 các công việc chỉ có thể đi ra khỏi một sự kiện khi các công việc đi 
vào đó đều hoàn thành. 
 Quy tắc 3 sơ đồ mạng thường không theo tỉ lệ 
 Quy tắc 4 tên các sự kiện không được trùng lắp 
 Quy tắc 5 trên sơ đồ không được có vòng kín 
 Quy tắc 6 trên sơ đồ không được có đường cụt 
Các đỉnh 
Đỉnh xuất phát (khởi công) đánh số 1, các đỉnh còn lại được đánh số nguyên liên 
tiếp , những đỉnh nào chỉ có cạnh ra mà không có cạnh vào thì đánh trước. 
Các cung 
4.4.2. Đường găng (gant) 
Sơ đồ Pert cho ta đánh giá được những thông tin: 
a) Thời gian sớm nhất để hoàn thành công việc 
Là thời gian sớm nhất để hoàn thành công việc mà không ảnh hưởng đến yêu cầu 
kỹ thuật 
Thời gian sớm nhất để hoàn thành công việc tại đỉnh j được ký hiệu là tj
s . Ta có 
 t
1
s = 0 
 t
j
s
 = max{(ti s + tij ) | (i,j)  Nj} 
Trong đó, Nj là tập hợp các cung có ngọn là đỉnh j 
tij thời gian hoàn thành công việc giữa hai đỉnh i và j 
b) Thời gian muộn nhất để hoàn thành công việc 
Là thời gian muộn nhất để hoàn thành công việc mà không ảnh hưởng đến tiến độ 
của công trình. (kéo dài thời gian hoàn thành công trình) 
Thời gian muộn nhất để hoàn thành công việc tại đỉnh j được ký hiệu là ti
m. Ta có 
 tn
m
 = tn
s
 t
i
m = min {(tj
m
 - tij ) | (i,j)  Gi} 
Trong đó, Gi là tập hợp các cung có gốc là đỉnh i 
Thời gian dự trữ của công việc 
Th.s. Nguyễn Hoàng Anh Khoa 
 19 
tij thời gian hoàn thành công việc giữa hai đỉnh i và j 
c) Tính thời gian dữ trữ tại các đỉnh, ký hiệu là di 
Là thời gian dự trữ tại các mốc thời gian của công trình, là thời gian cho phép trễ 
mà không ảnh hưởng đến tiến độ của công trình. 
di = ti
m
 - ti
s 
d) Tính thời gian dữ trữ công việc tại các cạnh , ký hiệu là dij 
Là thời gian cho phép trễ của công việc mà không ảnh hưởng đến tiến độ của công 
trình. 
dij = tj
m
 - ti
s
 – tij 
e) Công việc gant (găng) 
 Công việc (i,j) gọi là công việc gant nếu có dij = 0 
f) Đường gant 
 Đường gant là đường đi từ điểm khởi đầu đến điểm kết thúc và đi qua các 
công việc gant. 
Ví dụ: Để thực hiện một công trình ta phải thực hiện các công việc sau: 
Công việc Yêu cầu Thời gian 
A 3 
B 4 
C 6 
D sau A 2 
E sau B 5 
F sau A 6 
G sau C,D,E 6 
H sau F,G 3 
K sau C,D,E 7 
a) Lập sơ đồ mạng 
b) Xác định thời gian dự trữ của mỗi công việc. 
c) Xác định đường gant. 
Giải 
t1
s
 = 0 
t2
s
 = max{3}=3 
t3
s
 = max {4}=4 
t4
s
 = max {3+4 ;3 ;4+5}=9 
t5
s
 = max {3+6 ;9+6}=15 
t6
s
 = max {15+3 ;9+7}=18 
t6
m
 = t6
s
 = 6 
t5
m
 = min{18-3} = 15 
t4
m
 = min{15-6 ;18-7} = 9 
t3
m
 = min{9 - 5} = 4 
t2
m
 = min{9 - 2} = 7 
t1
m
 = min{7-3 ; 9-3 ; 4-4} = 0 
Th.s. Nguyễn Hoàng Anh Khoa 
 20 
BÀI TẬP CHƯƠNG 4 
Câu 1 : Xét sơ đồ mạng 
a) Bằng thuật toán Prim tìm mạng liên thông ngắn nhất và tính độ dài. 
b) Bằng thuật toán Difkatra tìm đường đi ngắn nhất từ x1 đến x7 
Câu 2: Cho sơ đồ mạng 
Hãy tìm thời gian sớm nhất và thời gian muộn nhất để hoàn thành công việc tại các 
đỉnh, xác định thời gian dự trữ tại các đỉnh và các cung. 
 1 
0 
0 0 
 4 
0 
9 9 
 6 
0 
18 18 
 44 
44 
44 44 
 5 
0 
15 15 
2 
4 
7 3 
 3 
0 
4 4 
A3 
 4 
 E5 
 0 
F6 
6 
G6 
 0 
 H3 
 0 
 D2 
 4 
 B4 
 0 
C6 
3 
K7 
2 
6 
1 4 
2 
3 
2 
5 2 
6 
3 
6 
5 
4 
5 
9 
6 
1 4 
2 
3 
2 
1 2 
5 
7 
7 
5 
6 
2 
8 5 
9 
4 
5 
Th.s. Nguyễn Hoàng Anh Khoa 
 21 
TÀI LIỆU THAM KHẢO 
1. PGS.TS. Nguyễn Quang Dong- Ngô Văn Thứ - PGS.TS. Hoàng Đình Tuấn. 
Giáo trình “Mô hình toán kinh tế”. Nhà xuất bản Thống kê 2006. 
2. Bùi Minh Trí. Toán kinh tế. Nhà xuất bản Bách khoa Hà Nội 2011. 
3. PGS.TS. Nguyễn Quảng - TS. Nguyễn Thượng Thái. Toán kinh tế. Hà nội 2007.