Giáo trình Tối ưu hóa - Nguyễn Hải Thanh

g buộc D6 
= {x ∈ D3: x1 ≤ 
3}. LP6 có phương 
án tối ưu là K(3, 
1) có các tọa độ 
nguyên với zmax = 
13. Lưu trữ x* = 
(3, 1) và Record = 
13. Loại bỏ bài 
toán LP6. 
Xây dựng LP5 với 
miền ràng buộc D5 = 
{x ∈ D2: x1 ≤ 2}. 
LP5 có phương án tối 
ưu là F(2, 19/8) với 
 zmax = 31/2. Chia 
BTQHTT nguyên 
tương ứng với LP5 
thành hai bài toán 
căn cứ tọa độ x2 = 
19/8 không nguyên. 
Xây dựng LP4 
với miền ràng 
buộc D4 = {x 
∈ D2: x1 ≥ 3}. 
LP4 có miền 
phương án là 
miền rỗng. 
Loại bỏ bài 
toán LP4. 
Xây dựng 
LP7 với 
miền ràng 
buộc D7 = 
{x ∈ D3: x1 
≥ 4}. LP7 có 
miền 
phương án 
là miền 
rỗng. Loại 
bỏ bài toán 
Xây dựng LP9 với miền ràng buộc D9 
= {x ∈ D5: x2 ≤ 2}. LP9 có phương án 
tối ưu có các tọa độ nguyên là H(2, 2) 
với zmax = 14. Lưu trữ x* = 
(2, 2) và Record = 14. Loại bỏ bài 
toán LP9. 
Xây dựng LP8 với miền ràng 
buộc D8 = {x ∈ D5: x2 ≥ 3}. LP8 
có phương án tối ưu là G(4/7, 3) 
với zmax = 96/7 < Record = 14. 
Loại bỏ bài toán LP8. 
Dừng 
Hình IV.3. Mô tả phương pháp nhánh cận Land – Doig 
 90 
i) Nếu bài toán không có phương án thì loại bài toán ra khỏi tập S. 
ii) Nếu bài toán có phương án với tọa độ nguyên thì so sánh zmaxvới Record hiện có: 
– Nếu zmax ≤ Record thì loại bỏ bài toán ra khỏi tập S. 
– Nếu zmax > Record thì đặt lại Record = zmax và ghi lại phương án tối ưu sau đó loại bài 
toán ra khỏi tập S. 
iii) Còn nếu bài toán có phương án tối ưu nhưng có ít nhất một tọa độ không nguyên thì so 
sánh zmax với Record hiện có: 
– Nếu zmax ≤ Record ta loại bỏ bài toán ra khỏi tập S. 
– Nếu zmax > Record ta chia bài toán thành hai bài toán căn cứ vào một tọa độ không 
nguyên bất kỳ của phương án tối ưu tìm được. 
Bước 2: Thiết lập mới tập S gồm tất cả các bài toán thu được từ bước 1. Kiểm tra xem S có 
bao nhiêu bài toán: Nếu S khác rỗng thì đặt k := k+1 và quay về bước 1, còn nếu S là tập rỗng thì 
về bước kết thúc. 
Bước kết thúc. Dừng và in ra Record. 
3. Giải bài toán quy hoạch tuyến tính nguyên bằng quy hoạch động 
3.1. Bài toán người du lịch 
Để hiểu rõ các khái niệm cơ bản của quy hoạch động, trước hết chúng ta hãy xét bài toán 
người du lịch. Trong bài toán người du lịch, chúng ta muốn xác định đường đi ngắn nhất từ một 
địa điểm xuất phát (điểm gốc) để đi tới điểm cần đến (điểm đích) trên một mạng hành trình du 
lịch. 
Ví dụ 4 (Bài toán người đi du lịch). Có một người đi du lịch, xuất phát từ nút 1 và kết thúc 
hành trình ở nút 10 theo hành trình với sơ đồ như trên hình IV.4. 
 2 
 1 
 7 3 
 5 4 
 6 9 
 8 
 10 
175 
175 
150 
275 200 
400 
150 
100 
200 300 
100 
125 
250 
275 
350 
200 
Hình IV.4. Sơ đồ hành trình đường đi 
 91
Người du lịch xuất phát từ nút 1. Trong giai đoạn đầu anh ta chỉ được quyền (và bắt buộc) 
chọn một trong ba nút (thành phố) 2, 3, 4 để vào thăm quan. Giai đoạn tiếp theo, anh ta chỉ được 
chọn một trong ba nút 5, 6, 7 để du lịch. Trong giai đoạn tiếp nối, anh ta có quyền vào một trong 
hai nút 8 hoặc 9 trước khi kết thúc hành trình tại nút 10. 
Như vậy, trong mỗi giai đoạn người đi du lịch chỉ được quyền đi vào một thành phố (mỗi 
thành phố được coi là một trạng thái của giai đoạn đó). Hãy tìm cách xác định đường đi ngắn nhất 
từ nút 1 tới nút 10 thoả mãn các điều kiện đặt ra của bài toán. 
Nguyên tắc tối ưu Bellman trong quy hoạch động 
Sử dụng nguyên tắc tối ưu Bellman trong quy hoạch động để giải bài toán người du lịch, 
chúng ta chia bài toán thành nhiều giai đoạn, tức là thành nhiều bài toán nhỏ. 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. 
Ta có thể giải quyết bài toán dần theo từng giai đoạn theo cách tính toán tiến hoặc tính toán 
lùi. Để giải bài toán này, ta áp dụng cách tính toán lùi (Backward Computing) với các ký kiệu và 
dữ kiện cho trong bảng IV.4. 
Bảng IV.4. Dữ kiện của các giai đoạn trong bài toán người du lịch 
Giai đoạn Đầu vào Đầu ra Đường đi tối ưu Khoảng cách tới đích 
Giai đoạn I 
8 
9 
10 
10 
8 → 10 
9 → 10 
150 
100 
Giai đoạn II 
5 
6 
7 
8 
9 
5 → 8 
6 → 9 
7 → 8 
400 
300 
275 
Giai đoạn III 
2 
3 
4 
5 
6 
7 
2 → 6 
3 → 5 
4 → 6 
600 
600 
500 
Giai đoạn IV 
1 2 
3 
4 
1 → 2 
1 → 3 
1 → 4 
700 
775 
650 
Giải thích. Sử dụng nguyên tắc tối ưu Bellman, để tìm đường đi ngắn nhất từ nút 4 tới nút 
10 chúng ta tìm được phương án tối ưu là đi từ nút 4 tới nút 6 cho giai đoạn III Lúc này khoảng 
cách ngắn nhất từ nút 4 tới nút 10 là d(4,10) = d(4,6) + min d(6,10) = 200 + 300 = 500. Điều này 
là do hai lựa chọn khác là đi từ nút 4 tới nút 5 hay 7 thì đều cho khoảng cách từ nút 4 tới đích là 
nút 10 lớn hơn (chẳng hạn nếu đi qua nút 5 thì d(4,10) = d(4,5) + min d(5,10) = 175 + 400 = 575). 
Trong bảng IV.4, tại giai đoạn IV, ta thấy khoảng cách ngắn nhất tới đích là 650. Đi ngược 
lại, từ điểm gốc tới điểm đích ta xác định được đường đi ngắn nhất là: 1 → 4 → 6 → 9 → 10 với 
tổng chiều dài là 650. 
3.2. Quy trình tính toán tổng quát 
– Trước hết, cần chọn các biến trạng thái (State variables) như mô tả trong bảng IV.5. 
 92 
Bảng IV.5. Các biến trạng thái của bài toán quy hoạch động 
Biến Số trạng thái Các trạng thái (nút) Giá trị có thể xảy ra của các biến trạng thái 
x4 1 1 x4 = 1 
x3 3 2, 3, 4 x3 = 2, x3 = 3, x3 = 4 
x2 3 5, 6, 7 x2 = 5, x2 = 6, x2 = 7 
x1 2 8, 9 x1 = 8, x1 = 9 
x0 1 10 x0 = 10 
Biến trạng thái mô tả trạng thái của hệ thống trong từng giai đoạn. 
– Xác định hàm mục tiêu: Đặt Fi(xi) là khoảng cách ngắn nhất tới đích tính tại giai đoạn i. 
Theo bảng IV.4, ta thấy: 
F1(x1) = 1
víi x
víi
=⎡⎢ =⎣ 1
150 8
100 x 9
 và F2(x2) = 
2
2
2
400 x 5
300 x 6
275 x 7.
=⎡⎢ =⎢⎢ =⎣
víi
víi
víi
Mục đích của bài toán là cần tìm được giá trị F4(x4) = F4(1). 
– Lập hàm truy toán: Fi+1(xi+1) = Min {Fi(xi) + fi (ui)}, Min tìm theo mọi tổ hợp thích hợp xi 
và ui, trong đó ui là biến điều khiển để điều khiển chuyển trạng thái từ trạng thái xi sang xi+1 và 
fi(ui) là hiệu ứng của biến điều khiển tác động lên hàm truy toán (và lên hàm mục tiêu nếu tính 
đến bài toán cuối cùng). Theo biểu thức của hàm truy toán ta thấy, nếu Fi(xi) + fi (ui) là hàm phi 
tuyến thì phải dùng kỹ thuật tối ưu thích hợp để tìm ra Fi+1(xi+1) . 
Sau đây chúng ta đi tìm các hàm truy toán Fi+1(xi+1) với quy trình tính toán lùi để giải bài 
toán theo từng giai đoạn, nhằm cuối cùng tìm ra được F4(x4) = F4(1). 
Giai đoạn 1: Trong giai đoạn này, muốn chuyển từ nút 10 (x0 = 10) về nút 8 (x1 = 8) chẳng 
hạn, thì biến điều khiển u0 phải có giá trị 150 (u0 = 150). Hiệu ứng gây nên bởi u0 là f(u0) = 150. 
Điều này có nghĩa là nếu chuyển từ nút 10 ngược về nút 8 thì cần đi quãng đường có chiều dài là 
150. 
x1 x0 = 10 u0 f0(u0) F1(x1) 
x1 = 8 + u0 = 150 150 150 150 
x1 = 9 + u0 = 100 100 100 100 
Chú ý. Không phải bài toán nào cũng có ui trùng với hiệu ứng fi(ui) của nó. Nói chung, 
biến điều khiển ui có thể gây ra hiệu ứng fi(ui) khác với ui cả về độ lớn cũng như đơn vị đo. 
Giai đoạn 2: 
F1 (x1) + f1(u1) x2 x1 = 8 x1 = 9 
x1 = 8 x1 = 9 
F2(x2) = 
Min{F1(x1) +f1(u1)} 
5 
6 
7 
+u1 = 250 
– 
+u1 = 125 
+u1 = 400 
+u1 = 200 
– 
400 
– 
275 
500 
300 
– 
400 = 150 + 250 
300 = 100 + 200 
275 = 150 + 125 
 93
Giai đoạn 3: 
x3 x2 F2(x2) + f2(u2) F3 (x3) = Min 
 5 6 7 x2 = 5 x2 = 6 x2 = 7 {F2(x2) + 
f2(u2)} 
2 
3 
4 
u2 = 275 
u2 = 200 
u2 = 175 
u2 = 300 
– 
u2 = 200 
– 
u2 = 350 
u2 = 275 
675 
600 
575 
600 
– 
500 
– 
625 
550 
600 
600 
500 
Giai đoạn 4: 
x4 x3 = 2 x3 = 3 x3 = 4 F3(x3) + f3(u3) F4 (x4) = Min 
 x3 = 2 x3 = 3 x3 = 4 {F3(x3) + f3(u3)} 
1 u3 =100 u3 =175 u3 =150 700 775 650 650 
Đáp số: F4(x4) = F4(1) = 650 với đường đi ngắn nhất trên hình IV.5. 
3.3. Áp dụng quy hoạch động giải bài toán quy hoạch tuyến tính nguyên 
Ví dụ 5. Giải BTQHTT nguyên: Max z = 8x1 + 5x2 + x3 
với điều kiện ràng buộc 
2
1 2 3
1 3
3 2 13
, , 0 
+ + ≤⎧⎪⎨ ≥⎪⎩
x x x
x x x
Để phù hợp với cách ký hiệu ở mục 3.2 trên đây, chúng ta viết lại bài toán trên như sau: 
Max z = 8u0 + 5u1 + u2, với điều kiện ràng buộc 
1
0 1 2
0 2
3 2 13
, , 0 
+ + ≤⎧⎪⎨ ≥⎪⎩
u u u
u u u
Ký hiệu lại: X0 = 0, X1 = X0 + 3u0, X2 = X1 + 2u1 = 3u0 + 2u1, X3 = X2 + u2 = 3u0 + 2u1 + 
u2. Gọi các biến trạng thái là X1, X2, X3 và các biến điều khiển là u0, u1, u2. Các hiệu ứng gây nên 
bởi các biến điều khiển là f(u0) = 8u0, f(u1) = 5u1, f(u2) = u2, 
x4 = 1 x3 = 4 x0 = 10 x1 = 9 x2 = 6 
u0 = 100 u1 = 200 u3 = 150 u2 = 200 
Hình IV.5. Đường đi ngắn nhất 1→4→6→9→10 
X0 = 0 X1 X3 X2 
 u2 u0 u1 Biến điều khiển 
và nguyên. 
và nguyên. 
 94 
Thiết lập hàm truy toán Fi+1(Xi+1) = Max {Fi(Xi) + fi (ui)} với F0(X0) = 0. Dễ thấy: F1 (X1) 
= Max f(u0), F2 (X2) = Max {f(u0) + f(u1)} và F3(X3) = Max {f(u0) + f(u1) + f(u2)} = 8u0 + 5u1 + 
u2 . Mục tiêu cuối cùng là cực đại hoá z = F3 (X3). Trong ví dụ này, chúng ta áp dụng cách tính 
toán tiến. 
Giai đoạn 1: (Coi F0(X0) = 0) 
X0 = 0 
X1 u0 = 0, 1, , 
[13/3] 
f0(u0) = 8u0 F1(X1) = Max{F0(X0) + f0(u0)} u0 tối ưu 
0 
3 
6 
9 
12 
13 
0 
1 
2 
3 
4 
0 
8 
16 
24 
32 
0 
8 
16 
24 
32 
0 
1 
2 
3 
4 
Giai đoạn 2: 
X1 
0 3 6 9 12 X2 
u1 = 0, 1, , [(13– X1)/2] 
F2 (X2) = Max{F1(X1) + f1(u1)} u1 tối ưu 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
0 
 – 
1 
 – 
2 
 – 
3 
 – 
4 
 – 
5 
 – 
6 
– 
 – 
 – 
 – 
0 
 – 
1 
 – 
2 
 – 
3 
 – 
4 
 – 
5 
 – 
 – 
 – 
 – 
 – 
– 
0 
 – 
1 
– 
2 
– 
3 
 – 
– 
– 
– 
– 
– 
– 
– 
– 
 – 
0 
 – 
1 
 – 
2 
– 
– 
– 
– 
– 
– 
– 
– 
– 
– 
– 
– 
0 
– 
0 
– 
5 
8 
10 
13 
16 
18 
21 
24 
26 
29 
32 
34 
0 
– 
1 
0 
2 
1 
0 
2 
1 
0 
2 
1 
0 
2 
 95
 Giai đoạn 3: 
X2 
0 – 2 3 4 5 6 7 8 9 10 11 12 13 X3 
u2 = 0, 1, , 13 – X2 
F3(X3) = 
Max{F2(X2) 
+ f2(u2)} 
u2 
tối 
ưu 
0 
1 
2 
3