Giáo trình Vận trù học - Nguyễn Hải Thanh (Phần 1)

các giai đoạn mà lựa chọn phương 
pháp tối ưu thích hợp. 
Trong ví dụ đang xét, khi các hiệu ứng fi(pi) cho dưới dạng hàm tuyến tính với các 
biến pi nhận các giá trị rời rạc/nguyên thì hàm truy toán Fi+1 (xi+1) = Min [Fi(xi) + fi+1 
(pi+1)] sẽ tính được bằng thuật giải dựa trên bảng liệt kê (như phương pháp giải đã trình 
bày). Nếu fi(pi) phi tuyến với các biến pi nhận các giá trị liên tục thì để tìm Fi+1(xi+1) = 
Min[Fi(xi) + fi+1(pi+1)] ta có hai cách: 
− Cách 1: rời rạc hóa theo từng mức. Chẳng hạn nếu p1 ∈ [0, 6] thì coi p1 ∈ {0, 1, 2, 
3, 4, 5, 6}. 
− Cách 2: áp dụng phương pháp tối ưu thích hợp với biến liên tục (xem chương I) 
cho hàm mục tiêu. Chẳng hạn, trong ví dụ trên khi cần tìm F2(x2) = Min [F1(x1)+ f2(p2)] 
= Min[f1(p1) + f2(p2)] = Min [3p1 + 2p2] với điều kiện ràng buộc: p1 + p2 ≤ 15 và 
0 ≤ p1 ≤ 6, 0 ≤ p2 ≤ 6, có thể áp dụng phương pháp đơn hình. 
Bài toán 2 
Xác định tuyến đường đi của đường dây truyền tải điện từ điểm A đến điểm B, với 
các chướng ngại vật khác nhau, sao cho tổng chi phí là nhỏ nhất. Các dữ kiện của bài 
toán cho trên hình III.15. 
Như vậy để thiết lập sơ đồ đường truyền tải điện thì xuất phát từ A ta có thể định 
tuyến đi của đường truyền tải điện trước hết phải qua một trong hai điểm sát gần, theo 
hướng bắc hay hướng đông, với các chi phí là 15 và 12. Từ một trong hai điểm này, 
chúng ta lại tiếp tục xác định tuyến đi cho đường truyền tải điện, với các chi phí đã 
biết... Vậy ta có bài toán tìm đường đi với chi phí nhỏ nhất. 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
88 
10 
8 9 13 10 
6 
15 
12 
11 10 15 
A 
B 
2 
8 
10 
12 9 6 
2 
12 
4 
16 11 
7 
10 
13 
7 
15 
8 
11 
8 
9 
Hình III.15. Sơ đồ tuyến đi cho dây truyền tải điện 
Bài toán này hoàn toàn tương tự với bài toán người du lịch đã xét và có thể giải 
bằng phương pháp quy hoạch động (Hướng dẫn: Chia bài toán thành nhiều giai đoạn 
nhỏ theo các đường với nét đứt nối trên hình III.15). 
3.3. Mô hình mạng trung chuyển hàng 
Mô hình mạng vận tải có thể được xem xét dưới dạng mô hình mạng trung chuyển 
hàng (Transshipment Model), trong đó mỗi điểm cung hoặc cầu (hoặc “loại trừ”) được 
coi là các nút trung chuyển hàng, tức là các nút cung cầu kết hợp: vừa nhận hàng đến 
vừa chuyển hàng đi. Việc xem xét như vậy có ý nghĩa thực tiễn hơn do việc tính toán 
cước phí vận chuyển giữa các nút trung chuyển được thực hiện dễ dàng hơn. 
Ví dụ 3: Ta có 3 điểm cung cấp hàng A, B, C và 2 điểm cầu S, T với lượng hàng 
cung và cầu tại mỗi điểm cũng như cước phí vận tải trên một đơn vị hàng cho mỗi cung 
đường như trong bảng III.21. 
Bảng III.21. Các dữ liệu của bài toán vận tải 
Cước phí vận chuyển/đơn vị hàng cij (USD) đến 
Nơi đi 
S(2300) T(1400) 
A(1000) 80 215 
B(1500) 100 108 
C(1200) 102 68 
Cần xác định nên vận chuyển từ mỗi điểm cung tới mỗi điểm cầu bao nhiêu đơn vị 
hàng nhằm thoả mãn nhu cầu cung cầu đồng thời đạt tổng chi phí vận tải là nhỏ nhất. 
Để đưa bài toán vận tải trên về bài toán trung chuyển hàng, ta coi các điểm A, B, C, 
S và T vừa là các nút trung chuyển: nhận hàng đến và chuyển hàng đi. Do đó cần thêm 
vào các cước phí vận tải trên một đơn vị hàng giữa hai nút bất kì của mạng trung chuyển 
hàng (xem bảng III.22, chẳng hạn, từ A tới B cước phí đó là 130, từ A tới S cước phí là 
80 như đã cho, tuy nhiên từ S tới A cước phí lại là 79 trên đường đi theo chiều ngược 
lại). Tại mỗi nút, một lượng hàng hóa bất kì không vượt quá 3700 đơn vị có thể được 
trung chuyển. Nếu tại mỗi nút cung hay cầu của bài toán vận tải ban đầu, chúng ta bổ 
sung thêm một lượng “dự trữ đệm” là B ≥ 3700 đơn vị hàng thì hàng có thể chuyển đi 
trước khi hàng đến. Chọn B = 3700, chúng ta sẽ đưa bài toán trung chuyển hàng về bài 
toán vận tải với 5 nút cung đồng thời là 5 nút cầu (có các lượng cung/cầu phải được tính 
toán lại), với phương án vận chuyển tối ưu được cho trong bảng III.22: Từ A vận 
chuyển tới S 1000 đơn vị hàng, từ B tới C và S 200 và 1300 đơn vị hàng, từ C tới T 
1400 đơn vị hàng. 
Bảng III.22. Phương án tối ưu của bài toán trung chuyển hàng 
Cước phí vận chuyển/đơn vị hàng cij (USD) đến 
Nơi đi A 
3700 
B 
3700 
C 
3700 
S 
6000 
T 
5100 
A 
1000+3700 
0 
3700 
130 90 
80 
1000 
215 
B 
1500+3700 
135 
0 
3700 
101 
200 
100 
1300 
108 
C 
1200+3700 
95 105 
0 
3500 
102 
68 
1400 
S 
3700 
79 99 
110 
0 
3700 
205 
T 
3700 
200 107 72 205 
0 
3700 
Ví dụ 4: Giải bài toán tìm đường đi ngắn nhất (xem sơ đồ mạng đường đi trên hình 
III.16) bằng cách áp dụng mô hình mạng trung chuyển hàng. Để cho đơn giản chúng ta 
xét đường đi hai chiều, chẳng hạn từ nút 2 tới nút 5 và ngược lại đều có đường đi với 
cùng chiều dài là 500. 
 2 
 1 7 
 3 6 
 4 
 5 
600 
1000
400 
800 1100
500 
200 
900 
100 
300 700 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
90 
Hình III.16. Sơ đồ mạng đường đi 
Để giải bài toán này chúng ta coi nút 1 là nút đi đóng vai trò điểm cung duy nhất 
với lượng cung bằng 1 đơn vị, còn nút 7 là nút đến đóng vai trò nút cầu duy nhất với 
lượng cầu là 1, các nút còn lại là các nút trung chuyển. Chiều dài các đường đi giữa các 
nút được điền vào các ô tương ứng, được xem như cước phí vận tải. Nếu không có 
đường đi thì ta coi cước phí là M ≈ +∞. Lúc này bài toán được đưa về mô hình mạng 
trung chuyển hàng với các dữ liệu như mô tả trong bảng III.23 và có thể giải được bằng 
phương pháp phân phối hay phương pháp thế vị như đã biết. 
Bảng III.23. Dữ liệu của bài toán đường đi ngắn nhất. 
Nút đi 2 3 4 5 6 7 là nút đến 
là nút 1 200 400 1000 M M M 1 
2 0 M 1100 500 M M 0 + B 
3 M 0 300 M 100 M 0 + B 
4 1100 300 0 800 700 M 0 + B 
5 500 M 800 0 M 600 0 + B 
6 M 100 M M 0 900 0 + B 
B = 1 0 + B 0 + B 0 + B 0 + B 0 + B 1 
3.4. Bài toán tìm luồng cực đại 
Ví dụ 5: Xét mạng đường đi có hướng từ nút 1 tới nút 5 với các tải năng tối đa của 
các cung đường đã biết như mô tả trên hình III.17 (chẳng hạn tải năng x12 của cung 
đường nối các nút 1 và 2 phải nằm trong giới hạn từ 0 tới 20). Bài toán đặt ra là: Cần 
xác định được luồng cực đại (Maximal Flow) giữa nút 1 (nút nguồn) và nút 5 (nút hút). 
Hình III.17. Sơ đồ đường đi và thông lượng 
Bài toán trên có ý nghĩa thực tế như sau: Coi nút 1 là kho bơm/cấp phát dầu thô với 
khả năng rất lớn, các đường đi là các ống dẫn dầu với các tải năng (tấn/đơn vị thời gian) 
 2 
 1 
 3 
 4 5 
 (28)
(20) 
(5) (20) 
(15) 
(10) 
(30) 
(15) 
đã xác định, các nút 2, 3 và 4 là các trạm bơm/trung chuyển dầu, còn nút 5 là kho nhận 
dầu (để đưa dầu vào lọc). Cần xác định phương án bơm dầu tối ưu với các tải năng thích 
hợp của các cung đường để bơm được dầu thô nhiều nhất (tính trên một đơn vị thời 
gian) từ nút 1 tới nút 5. Đó chính là phương án sau: Bơm 20 tấn dầu thô từ nút 1 qua 
đường đi 1 → 2 → 5 tới nút 5, bơm 15 tấn dầu thô trừ nút 1 qua đường đi 1 → 4 → 5 
tới nút 5 và bơm 10 tấn dầu thô trừ nút 1 qua đường đi 1 → 3 → 5 tới nút 5. Như vậy 
luồng cực đại có thể chuyển từ nút 1 đến nút 5 qua mạng ống dẫn dầu trên có giá trị là 
45 tấn/một đơn vị thời gian. Cần chú ý là tổng lượng dầu đi qua mỗi cung đường phải 
nằm trong giới hạn cho phép của tải năng. 
Về mặt toán học, khái niệm luồng cực đại có thể được xây dựng như sau đây đối 
với bài toán trên. Trước hết, ta gọi một luồng chấp nhận được là một véc tơ (x12, x13, 
x14, x24, x25, x34, x35, x45), xij ∈[ maxij0, x ] ∀ cung (i, j) cho trên mạng đường đi có hướng 
và thoả mãn: ki ih
k I(i) h O(i)
x x
∈ ∈
=∑ ∑ ∀ nút i trên mạng, trong đó vế trái là tổng các tải năng 
của các cung đi vào nút i, còn vế phải là tổng các tải năng của các cung đi khỏi nút i. Dễ 
dàng chứng minh được rằng luôn có 1j i5
j O(1) i I(5)
x x
∈ ∈
=∑ ∑ = v. Lúc này, một luồng cực đại 
là một luồng chấp nhận được sao cho giá trị v của luồng đạt được là lớn nhất. Các khái 
niệm này được định nghĩa tương tự trong trường hợp tổng quát. 
Bài toán tìm luồng cực đại trên đây được giải bằng thuật thích hợp với kết quả 
các bước lặp được tổng hợp trong bảng III.24: 
Bảng III.24. Các bước giải bài toán luồng cực đại 
Bước Tìm đường 
tăng luồng 
Giá trị tăng 
luồng 
Các tải năng của các cung trên luồng hiện 
tại (luồng chấp nhận được) 
Giá trị 
luồng 
Bước khởi 
tạo 
 xij = 0 ∀ cung (i, j) 0 
Bước lặp 1 1 → 2 → 5 20 x12 = x25 = 20, xij = 0 ∀ cung (i, j) khác 20 
Bước lặp 2 1 → 3 → 5 10 x12 = x25 = 20, x13 = x35 = 10, xij = 0 ∀ cung 
(i, j) khác 
30 
Bước lặp 3 1 → 4 → 5 15 x12 = x25 = 20, x13 = x35 = 10, x14 = x45 = 15, 
xij = 0 ∀ cung (i, j) khác 
45 
Giải thích 
Trước hết tại bước khởi tạo cần tìm một luồng chấp nhận được, tức là một véc tơ 
luồng (x12, x13, x14, x24, x25, x34, x35, x45), xij ∈[ maxij0, x ] ∀ cung (i, j) và thoả mãn: 
ki ih
k I(i) h O(i)
x x
∈ ∈
=∑ ∑ ∀ nút i trên mạng, trong đó vế trái là tổng các tải năng của các cung 
đi vào nút i, còn vế phải là tổng các tải năng của các cung đi khỏi nút i. Trong bảng trên, 
chúng ta xuất phát bởi véc tơ luồng trùng véc tơ 0 với giá trị luồng bằng 0. 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
92 
Tại bước lặp 1 chúng ta tìm được một đường tăng luồng 1 → 2 → 5 từ nút 1 tới nút 
5 bằng cách thực hiện thủ tục đánh dấu. 
Thủ tục đánh dấu 
Bước khởi tạo. Gọi I là tập nút đã được đánh dấu I, ban đầu đặt I = {nút nguồn}. 
Các bước lặp. 
Bước 1: Nếu I chứa nút hút hoặc I = ∅ thì về bước kết thúc. Nếu trái lại, chọn nút 
bất kì i ∈ I để quét (đồng thời đưa nó ra khỏi tập I), tức là xét tất cả các nút j cạnh i, nói 
cách khác, xét mọi cung tiến có dạng (i, j) là cung trên mạng đường đi một chiều đã cho 
và tương ứng với nó là cung lùi (j, i). 
Bước 2: Xét các cung tiến (i, j) mà có j chưa được đánh dấu (không nằm trong tập I) 
thì ta đưa j vào tập I với điều kiện xij (hiện có) < maxijx , còn nếu xét các cung lùi thì điều 
kiện đó là xij (hiện có) > 0 và quay trở lại bước 1. Chú ý một khi nút hút được đưa vào 
tập I thì cũng về ngay bước kết thúc. 
Bước kết thúc. Tìm đường tăng luồng P (xem giải thích ngay sau đây) và dừng. 
Xét bước lặp 1 trong bảng III.24. Tại bước 1, ta quét nút 1 (và đưa nút 1 ra khỏi tập 
I) để có các nút 2, 3, 4 cạnh nút 1 chưa được đánh dấu và có I = {2, 3, 4}. Tại bước 2, 
chọn quét nút 2 (đồng thời đưa nút 2 ra khỏi tập I) thì được thêm nút cạnh nút 2 là nút 5 
(nút hút) nên chuyển sang bước kết thúc. Để tìm đường tăng luồng, ta đi ngược từ nút 5 
về nút 2 (vì nút 5 được đưa vào đánh dấu khi quét nút 2) và sau đó về nút 1 (vì nút 2 đã 
được đưa vào đánh dấu khi quét nút 1). Như vậy tại bước lặp 1 ta được đường tăng 
luồng 1 → 2 → 5 với giá trị tăng luồng là 
Δ(P) = Min ( )maxij ij ij
(i, j) C (i, j) C
x x , xmin min+ −∈ ∈
⎧ ⎫−⎨ ⎬⎩ ⎭
= Min{min(20 −0, 28−0)} = 20. 
Trong biểu thức trên, kí hiệu C+ để chỉ tập cung tiến, còn kí hiệu C− để chỉ tập cung 
lùi nằm trên đường tăng luồng. Tương tự, ở các bước lặp 2 và 3 ta tìm được các đường 
tăng luồng với các giá trị tăng luồng tương ứng là 10 và 15. Luồng cực đại có giá trị là 
tổng các giá trị tăng luồng và giá trị của luồng xuất phát: 20 + 10 + 15 = 45. Từ ví dụ 
trên, chúng ta có thể phát biểu thuật toán Ford − Fulkerson giải bài toán luồng cực đại. 
Thuật toán Ford − Fulkerson 
Bước khởi tạo. Tìm một luồng chấp nhận được. 
Các bước lặp. 
Bước 1: Tìm một đường tăng luồng bằng thủ tục đánh dấu. Nếu không có thì 
chuyển về bước kết thúc. Còn nếu có thì xét giá trị tăng luồng tương ứng Δ(P). 
Bước 2: Nếu Δ(P) < +∞ thì đẩy thêm Δ(P) đơn vị tải năng dọc theo đường tăng 
luồng P để được luồng chấp nhận được mới rồi quay về bước 1. Nếu trái lại, Δ(P) = +∞ 
thì về bước kết thúc. 
Bước kết thúc. Tìm luồng cực đại với giá trị hữu hạn hoặc kết luận bài toán có luồng 
chấp nhận được với giá trị v = + ∞. 
Ví dụ 6. Trường hợp khi đường tăng luồng có chứa cung lùi (xem bảng III.25, hàng 
3): Xét lại bài toán trong ví dụ 5 với luồng chấp nhận được ban đầu là x12 = x24 = 5, x14 
= 10, x45 = 15, x13 = x35 = 10, xij = 0 ∀ cung (i, j) khác. 
Bảng III.25. Trường hợp đường tăng luồng có cung lùi 
Bước Tìm đường tăng luồng 
Giá trị tăng 
luồng 
Các tải năng của các cung trên luồng hiện 
tại (luồng chấp nhận được) 
Giá trị 
luồng 
Bước khởi tạo x12 = x24 = 5, x14 = 10, x45 = 15, x13 = x35 = 
10, xij = 0 ∀ cung (i, j) khác 
25 
Bước lặp 1 1 → 4 →2 → 5 
(cung (4,2) là 
cung lùi) 
5 x12 = 5, x24 = 5 − 5 = 0, x14 = 10+5 = 15, x45 
= 15, x13 = x35 = 10, x25 = 5, xij = 0 ∀ cung (i, 
j) khác 
30 
Bước lặp 2 1 →2 → 5 
15 x12 = 5+15 =20, x24 = 5 − 5 = 0, x14 = 10+5 = 
15, x45 = 15, x13 = x35 = 10, x25 = 5+15 = 20, 
xij = 0 ∀ cung (i, j) khác 
45 
Nhận xét. Xét tập hợp gồm một số cung đường nào đó trên một mạng đường đi 
có hướng với tính chất: Nếu cho tải năng của tất cả các cung đường này bằng 0 thì 
mọi luồng chấp nhận được đều có giá trị bằng 0. Một tập hợp như vậy được coi là 
một lát cắt. Tổng các tải năng tối đa của tất cả các cung đường của một lát cắt được 
gọi là dung lượng của lát cắt. Từ thuật toán Ford − Fulkerson có thể chứng minh 
được rằng: Nếu luồng cực đại tồn tại với giá trị v hữu hạn thì v chính bằng giá trị 
cực tiểu của dung lượng của các lát cắt. Có thể minh họa nhận xét qua việc xét các 
lát cắt trên mạng đường đi có hướng cho trong ví dụ 5 (xét chẳng hạn lát cắt (1, 2), 
(1, 3), (1, 4) với dung lượng 60, lát cắt (2, 5), (3, 5, (4, 5) với dung lượng 63, lát cắt 
(1, 2), (1, 3), (4, 5) với dung lượng 45). Trong ví dụ 5, có thể hình dung lát cắt là 
một tập hợp các cung đường, mà nếu cấm tải dầu trên các cung đường đó thì không 
một lượng dầu nào có thể bơm được từ nút nguồn tới nút hút. 
BÀI TẬP CHƯƠNG III 
1. Giải bài toán vận tải cho trong bảng sau: 
7 11 8 13 110 
21 17 12 10 100 
8 18 13 16 50 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
94 
50 70 60 80 Σ =260 
2. Giải bài toán phân công nhiệm vụ với thời gian thực hiện (của mỗi kĩ sư đối với 
từng nhiệm vụ được ghi theo hàng) cho trong bảng sau: 
32 18 32 16 1 
22 14 12 16 1 
24 30 26 24 1 
26 30 28 20 1 
1 1 1 1 
Tìm cách phân công nhiệm vụ (mỗi một trong số bốn kĩ sư chỉ được giao đúng một 
nhiệm vụ) để cực tiểu hóa tổng thời gian thực hiện. 
3. Hai máy biến áp có dung lượng 580KVA và 650KVA hoà điện lên thanh cái để 
cung cấp điện cho bốn nhóm máy A, B, C và C có công suất tối đa lần lượt là 180, 270, 
420 và 320. Qua khảo sát, chúng ta có các số liệu sau: 
− Chi phí truyền tải một đơn vị công suất từ máy biến áp thứ nhất đến các nhóm 
máy là: C1A = 250, C1B = 300, C1C = 320 và C1D = 310 đồng/đơn vị công suất. 
− Chi phí truyền tải một đơn vị công suất từ máy biến áp thứ hai đến các nhóm máy 
là: C2A = 350, C2B = 380, C2C = 330 và C2D = 340 đồng/đơn vị công suất. 
Hãy tìm công suất mà mỗi nhóm máy có thể nhận từ các máy biến áp để đảm bảo 
tổng chi phí truyền tải là nhỏ nhất. 
Xem xét một dự án với các dữ kiện như sau: 
Thời gian ước tính (ngày) 
Hoạt động Hoạt động kề trước a m b 
A 
B 
C 
D 
E 
F 
G 
− 
− 
A 
B 
B 
C, D 
E 
3 
2 
2 
2 
1 
4 
1 
6 
5 
4 
3 
3 
6 
5 
9 
8 
6 
10 
11 
8 
15 
Hãy giải quyết các vấn đề sau đây: 
− Vẽ sơ đồ mạng. 
− Tính thời gian (trung bình) hoàn thành dự án sớm nhất. 
− Tìm xác suất để dự án thực hiện trong vòng 20 ngày. 
5. Xác định cây khung tối thiểu cho mạng đường dẫn sau và phát biểu ý nghĩa thực 
tiễn của nó: 
 120 
47 
33 
 F
 G 
 E 
D 
C 
B 
A 
12
70
52 
33
70
43
23 20
6. Cho một lượng đầu tư có 15 (đơn vị tiền) có thể đầu tư vào các dự án sau: I, II, 
III theo các mức 0, 3, 6, 9, 12, 15 với mức lợi nhuận được cho trong bảng. Xác định 
phương án chọn danh mục đầu tư và mức đầu tư sao cho tổng lợi nhuận là lớn nhất. 
Mức lợi nhuận 
Số tiền đầu tư 
I II III 
0 
3 
6 
9 
12 
15 
0 
1 
4 
6 
8 
10 
0 
2 
5 
6 
7 
9 
0 
2 
5 
6 
7 
8 
7. Hãy tìm phương án tối ưu phân phối công suất của ba nhà máy 1, 2 và 3 với phụ 
tải và tổn thất cố định. Biết chi phí của các nhà máy là hàm phụ thuộc vào công suất 
fi(pi), trong đó pi là công suất thực tế của nhà máy i, với i = 1, 2, 3. Giả sử chúng ta đã 
khảo sát được các số liệu sau: 
− Tổng công suất cả ba nhà máy cần cung cấp là 18 (đơn vị công suất). 
− f1(p1) = 4p1, f2(p2) = 3P2, f3(p3) = 3P3. 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
96 
− 0 ≤ p1 ≤ P1MAX = 7, 0 ≤ p2 ≤ P2MAX = 8, 0 ≤ p3 ≤ P3MAX = 6. 
8. Hãy tìm đường đi ngắn nhất từ nút 1 tới nút 7 trên mạng đường đi sau đây với 
quy trình tính toán tiến: 
 2 
 1 7 
 3 6 
 4 
 5 
600 
1000
400 
800 1100
500 
200 
900 
100 
300 700 
Phương pháp 1: Tính toán bằng cách lập bảng (tương tự bảng III.19), từ đó thiết lập 
quy trình tính toán tổng quát với hàm truy toán thích hợp. 
Giai đoạn Đầu vào Đầu ra Đường đi tối ưu Khoảng cách tính từ gốc 
Giai đoạn 0 1 1 1 → 1 0 
Giai đoạn I 1 
2 
3 
1 → 2 
1 → 3 
200 
400 
Giai đoạn II 
1 
2 
3 
4 
1 → 4 
2 → 4 
3 → 4 
1000 
1300 
700 
Giai đoạn III 
2 
3 
4 
5 
6 
2 → 5 
3 → 6 
4 → 6 
700 
500 
1700 
Giai đoạn IV 5 6 
7 
5 → 7 
6 → 7 
1300 
1400 
Phương pháp 2: Có thể xây dựng hàm truy toán 
Fi+1(xi+1) = Min{Min [Fi(xi) + fi, i+1(ui, i+1)], Min [Fi-1(xi-1) + fi-1, i+1(ui-1, i+1)], 
, Min [F0(x0) + f0,i+1(u0, i+1)]}, 
với Min{Min...} tìm theo mọi tổ hợp thích hợp xk và uk,i+1, trong đó uk,i+1 là biến 
điều khiển để điều khiển chuyển trạng thái từ trạng thái xk sang xi+1 và fk,i+1(uk, i+1) là 
hiệu ứng của biến điều khiển tác động lên hàm truy toán, trong đó k có thể nhận các giá 
trị 0, 1,..., i -1, i. Điều này hoàn toàn phù hợp với việc “áp dụng nguyên tắc tối ưu 
Bellman trong quy hoạch động bằng cách chia bài toán thành nhiều giai đoạn, tại mỗi 
giai đoạn ta cần tìm phương án tối ưu là các phương án tốt nhất của tình trạng hiện có, 
xét trong mối quan hệ với các phương án tối ưu đã tìm được của các giai đoạn trước”. 
Phương pháp 3: Đưa về bài toán trung chuyển hàng và bảng III.24. 
Phương pháp 4: Xác định các biến quyết định thích hợp để đưa bài toán tìm đường 
đi ngắn nhất về BTQHTT và giải theo phương pháp đơn hình đã biết 
9. Hãy áp dụng mô hình mạng trung chuyển hàng (có thể có ô cấm) để giải quyết 
bài toán xích cung cầu tối ưu sau (hàng các điểm cung A, B và C phải đi qua các trung 
tâm phân phối D và E trước khi tới các điểm cầu F, G, H, I, J). Biết rằng các lượng cung 
tại A, B và C theo thứ tự là 1000, 1500, 1200; còn các lượng cầu tại F, G, H, I, J theo 
thứ tự là 800, 500, 750, 1000 và 650. Các cước phí vận tải trên một đơn vị hàng từ A, B 
và C đến D và E theo thứ tự là: 5, 6, 7 và 8, 4, 3; còn các cước phí từ D và E tới E, G, H, 
I, J theo thứ tự là 8, 6, 7, 4, 5 và 6, 10, 7, 8, 6. 
10. Hãy tìm luồng cực đại trên mạng đường đi có hướng với các tải năng tối đa 
được tổng hợp trên hình dưới, sau đó hãy phát biểu tình huống minh hoạ ý nghĩa thực tế 
của bài toán. 
Hướng dẫn. Có thể giải bằng thuật toán Ford − Fulkerson hoặc đưa bài toán trên về 
BTQHTT và giải bằng phương pháp đơn hình. 
 2 
 1 7 
 3 6 
 4 
 5 
60 
30 
40 
80 60 
50 
70 
90 
10 
30 70 
11. Xác định tuyến đường đi của đường dây truyền tải điện từ điểm A đến điểm B, 
với các chướng ngại vật khác nhau, sao cho tổng chi phí là nhỏ nhất. Các dữ kiện của 
bài toán như sau: 
10 
8 9 13 10 
6 
15 
12
 11 
10 15 A 
B 
2 
8 
10 
12 9 6 
 2 
12 
4 
16 
11 
7
10
13 
7 
15 
8 
11
8 
9
Như vậy để thiết lập sơ đồ đường truyền tải điện thì xuất phát từ A ta có thể định 
tuyến đi của đường truyền tải điện trước hết qua một trong hai điểm sát gần, theo hướng 
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học  
98 
bắc hay hướng đông, với các chi phí là 15 và 12. Từ một trong hai điểm này, chúng ta 
lại tiếp tục xác định tuyến đi cho đường truyền tải điện, với các chi phí đã biết,... Vậy ta 
có bài toán tìm đường đi với chi phí nhỏ nhất. 
Hướng dẫn: Chia bài toán thành nhiều giai đoạn nhỏ và áp dụng phương pháp quy 
hoạch động.