Chuyên đề Chương 6: Thuật toán nhánh cận

nh: 
1) Tìm cực tiểu (8) trên 31G được ( ) ( ) ] [313 3, 2 5 51X Gζ  ′= ⇒ = − = −   
2) 32G =∅ ( )32Gζ ′⇒ = +∞ 
3) Tìm cực tiểu (8) trên 33G được 
 ( )333 2 1 12 ,3 5 53 2 2 2X X Gζ       ′= = ⇒ = − = −              
4) 3 24 3G G= =∅ ( )34Gζ ′⇒ = +∞ 
Bùi Thế Tâm VI.6 Quy hoạch rời rạc 
Phương án ( )3 3, 2
1
X X  = =  
 thỏa mãn điều kịên nguyên (11). Đồng thời 
( ) ( ) ( ) ( ){ } { } ( )3 3 3 31 2 3 4min , , , min 5, , 5, 5G G G G f Xζ ζ ζ ζ ζ′ ′ ′ ′ ′= = − ∞ − ∞ ≤ = − . 
Vậy phương án tối ưu của bài toán ban đầu là ( )3, 2X = . 
Ta có cây phân nhánh sau: 
3. PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGƯỜI DU 
LỊCH 
3.1. Phát biểu bài toán. Có n thành phố, đánh số từ 1 đến n . Xuất phát từ một 
trong n thành phố này, chẳng hạn thành phố 1, một người du lịch muốn tới thăm n -1 
thành phố còn lại, mỗi thành phố đúng một lần, rồi trở về thành phố xuất phát. Cho biết 
ijc là chi phí (hoặc là khoảng cách) đi từ thành phố i đến thành phố j . Giả thiết 
0, ,ij iic i j c> ∀ ≠ = ∞ , với mọi i ( có thể ij jic c≠ ). Hãy tìm hành trình với tổng chi 
phí nhỏ nhất? 
Ký hiệu ma trận 
, 1,....,ij i j n
C c == , 1ijx = hoặc 0 tùy thuộc người du lịch có đi từ 
thành phố i tới thành j hay không. Khi đó bài toán người du lịch có thể viết dưới dạng: 
1
1
6
G
ζ ′ = − 
0
7
G
ζ ′ = − 
1 2 3
2 3 4G G G
ζ
≡ ≡
′ = +∞ 
1 2
1,1 1
5
G G
ζ
≡
′ = − 
1 2 3
1,2 2 3
5
G G G
ζ
≡ ≡
′ = − 
2 3
1,1 1
5
G G
ζ
≡
′ = − 
2 3
1,2 2G G
ζ
= =∅
′ = +∞ 
Bùi Thế Tâm VI.7 Quy hoạch rời rạc 
1 1
min ij ij
n n
i j
c x
= =
∑∑ (12) 
{ }
ij
1
ij
1
ij
ij
1, 1, 2,..., (13)
1, 1, 2,..., (14)
0;1 , , 1,2,..., (15)
1, 2 i j n (16)
n
j
m
i
i j
x i n
x j n
x i j n
u u nx n
=
=
= =
= =
∈ =
− + ≤ − ≤ ≠ ≤
∑
∑ 
trong đó iu nhận giá trị nguyên hay thực. 
3.2. Thuật toán nhánh cận 
Tập tất cả các phương án của bài toán (tập 0S )sẽ được chia nhỏ dần thành nhiều 
tập con rời nhau, mỗi tập con bao gồm những phương án đi qua và không đi qua một số 
cặp thành phố nhất định sẽ được ấn định dần trong quá trình giải bài toán. Mỗi tập con 
này được gắn với một số thực không âm (cách tìm số này xem ở phần tiếp theo), biểu 
thị cận dưới của chi phí đối với mọi phương án thuộc tập này. Tập con kS có cận dưới 
nhỏ nhất sẽ có nhiều khả năng chứa phương án tối ưu, vì thế tập kS sẽ được chọn để 
chia nhỏ tiếp (phân nhánh). Khi phân nhánh 1 2k k kS S S= ∪ sao cho một tập 2kS bắt 
buộc đi qua thêm một cặp thành phố rsx nào đó (cách chọn xem ở phần tiếp theo), một 
tập 1kS không được đi qua cặp thành phố rsx . Khi một tập con nào đó chỉ gồm một 
phương án duy nhất thì ta sẽ tính được chi phí C của phương án này và nhờ đó có thể 
cải tiến được phương án tốt nhất hiện biết, giá trị hàm mục tiêu của bài toán ứng với 
phương án tốt nhất hiện biết gọi là giá trị kỷ lục. Tập con nào có cận dưới lớn hơn hay 
bằng giá trị kỷ lục sẽ bị loại (không cần xem xét tiếp nữa), vì chắc chắn tập này không 
chứa phương án nào tốt hơn phương án tốt nhất hiện biết. Quá trình giải kết thúc khi 
không còn tập con nào cần xem xét tiếp. Khi đó, phương án tốt nhất hiện biết sẽ là 
phương án tối ưu của bài toán. Tính hữu hạn của thuật toán được suy ra từ tính hữu hạn 
của tập 0S . 
Thủ tục tính cận 
Bổ đề. Phương án tối ưu *x vẫn còn là tối ưu nếu ma trận chi phí C được thay 
bởi ma trận C′ với 
 , ( , 1, 2,.., )ij ij i jc c i j nα β′ = − − = (17) 
trong đó ,i jα β là các số thực bất kỳ. 
Chứng minh. Xét một phương án bất kỳ x của bài toán. Do *x là phương án 
tối ưu nên 
 *ij ij
1 1 1 1
n n n n
ij ij
i j i j
c x c x
= = = =
≤∑∑ ∑∑ 
Từ các hệ thức (12) và (17) ta có: 
Bùi Thế Tâm VI.8 Quy hoạch rời rạc 
( )* * *ij ij ij
1 1 1 1 1 1 1 1
ij ij
1 1 1 1 1 1
n n n n n n n n
ij i j ij ij i j
i j i j i j i j
n n n n n n
ij i j ij
i j i i i j
c x c x c x
c x c x
α β α β
α β
= = = = = = = =
= = = = = =
′ = − − = − −
′≤ − − =
∑∑ ∑∑ ∑∑ ∑ ∑
∑∑ ∑ ∑ ∑∑
điều này chứng tỏ *x vẫn còn là phương án tối ưu. 
Các số ,i jα β cần được chọn sao cho ij 0, ,c i j′ ≥ ∀ và trên mỗi hàng, mỗi cột 
của ma trận C′ có ít nhất một số 0. Chẳng hạn có thể chọn iα là số nhỏ nhất trong hàng 
i của C và jβ là số nhỏ nhất trong cột j của ma trận thu được từ C bằng cách trừ các 
phần tử trên hàng i cho iα , trừ các phần tử trên cột j cho jβ . 
Phép toán (17) được gọi là phép rút gọn ma trận hay thủ tục rút gọn và hằng số 
1 1
n n
i j
i i
γ α β
= =
= +∑ ∑ được gọi là hằng số rút gọn và đó chính là một cận dưới cho giá trị 
hàm mục tiêu của bài toán, vì mỗi phương án của người du lịch sẽ chứa đúng một phần 
tử của mỗi hàng và đúng một phần tử của mỗi cột trong ma trận chi phí . 
Tương tự, nếu tập con các phương án, ký hiệu là pS thu được từ tập ban đầu 0S 
bằng cách cố định một số biến ijx ở giá trị 1 hay 0 (nghĩa là cho phép đi qua hay cấm 
không được đi qua một số cặp thành phố nào đó) thì để tính cận dưới cho pS ta chỉ việc 
tiến hành thủ tục rút gọn trên ma trận tương ứng với pS . 
Thủ tục phân nhánh 
Giả sử ta cần phân nhánh tập 0pS S⊂ . Cách hay dùng là phân chia tập này thành 
hai tập con rời nhau ,p pS S′ ′′ với 
{ }
{ }
| , 0 ,
| , 1
p p rs
p p rs
S x x S x
S x x S x
′ = ∈ =
′′ = ∈ =
. 
trong đó, rsx là biến chưa cố định ở giá trị 0 hay 1 trong tập pS . 
 Cặp ( ),r s dùng để phân nhánh được chọn sao cho tập pS ′′ có nhiều khả năng 
chứa phương án tối ưu, còn tập pS ′ thì không. Nói cách khác, ( ),r s được chọn sao cho 
hiệu số các cận dưới của pS ′′ và pS ′ là lớn nhất có thể được. 
Để giải quyết vấn đề này, ta chỉ cần xét tập các phương án ban đầu 0S , vì mọi bài 
toán con nhận được về sau có cùng cấu trúc như đối với bài toán ban đầu. Giả sử ma 
trận chi phí C đã được rút gọn , nghĩa là 0, ,ijc i j≥ ∀ và trên mỗi hàng , mỗi cột của 
C có ít nhất một số 0. Tập 0S được chia thành hai tập rời nhau 1S và 2S với 
Bùi Thế Tâm VI.9 Quy hoạch rời rạc 
{ }
{ }
1 0
2 0
| , 0 ,
| , 1
rs
rs
S x x S x
S x x S x
= ∈ =
= ∈ = 
Trong tập 2S cấu trúc bài toán không thay đổi, trừ ra hàng r và cột s bị loại, bởi 
vì đã đi từ r đến s thì không thể đi từ r đến bất cứ nơi nào khác, và cũng không được 
phép đi từ bất cứ đâu vào s . Các hàng và cột còn lại chỉ chứa các phần tử không âm, vì 
thế ứng với 2S một cận dưới đối với giá trị hàm mục tiêu tăng thêm là ( )2 rsS cγ = . 
Trong tập 1S do cố định 0rsx = nên từ các điều kiện (14), (15) suy ra phải có một 
( )1rjx j s= ≠ và một ( )1isx i r= ≠ . Vì thế ( )1 min minrj isj s i rS c cγ ≠ ≠= + là một cận dưới 
đối với giá trị mục tiêu tăng thêm. Ta sẽ chọn biến rsx sao cho hiệu giữa các cận dưới 
này là lớn nhất, nghĩa là đạt 
 ( ) ( ){ }1 2
( , )
max
r s
S Sγ γ− (18) 
Nếu 0rsc > thì ( )1 0Sγ = (do trên hàng r và cột s của C đều chứa số 0), 
còn ( )2 0rsS cγ = > , từ đó ( ) ( )1 2 0S Sγ γ− < . Vì thế để có (18) ta chỉ cần xét các cặp 
( ),r s với 0.rsc = Trong trường hợp này ( )2 0Sγ = và ( )1 0Sγ ≥ . 
 Điều này có nghĩa là thay cho (18) ta có thể chọn biến rsx để phân nhánh theo 
qui tắc 
 ( ) ( )
0
, max , min min
pq
pj iqj q i pc
r s p q c cθ θ ≠ ≠=
 = = +   . 
Lập luận trên đây cũng đúng cả khi các tập phương án iS về sau được chia thành 
các tập 1,r rS S + , nhưng thay cho mức tăng của các cận dưới ( )2Sγ và ( )1Sγ ta xét mức 
tăng của các cận dưới ( )rSγ và ( )1rSγ + tương ứng. 
Ngăn cấm tạo các chu trình con 
Nếu tập được xét không phải là 0S mà là 
 { }1 1 2 20 1 2| , , ,....., k kp i j i j i j kS x x S x x xδ δ δ= ∈ = = = , 
thì qui tắc chọn biến để phân nhánh về cơ bản vẫn như trước, tuy nhiên cần tiến hành 
một số thay đổi . Trước hết, đó là việc thực hiện các lựa chọn bắt buộc. Chẳng hạn, nếu 
0, 1,.., 1, 1,..,ujx j v v n= = − + thì tất nhiên phải có 1uvx = . Cũng làm vậy đối với các 
cột . 
Một số loại lựa chọn bắt buộc khác: khi đã cố định 1rsx = thì phải có 0srx = 
bằng cách đặt src = ∞ . Hơn nữa, nếu đường đi dài nhất trong pS chứa cạnh ( ),r s gồm 
ít nhất 2 và nhiều nhất 2n − cạnh 
 ( )
1 2 1 1
... ... 1
1 3
u u v vi i i r rs si i ix x x x x
v n
+ −= = = = = = =
≤ ≤ − 
Bùi Thế Tâm VI.10 Quy hoạch rời rạc 
(không có cạnh nào có dạng 
1
1kix = hay 1vi jx = ), thì để ngăn cấm tạo chu trình con 
dạng ( )1 2 1, ,...., , , ,ui i i r s i ta đặt 1sic = ∞ , còn để ngăn cấm tạo chu trình con dạng 
( )1 2, , , ,...., ,u u vr s i i i r+ + ta đặt vi rc = ∞ . Hơn nữa, ta cần có 1 0vi ix = bằng cách đặt 
1vi ic = ∞ . 
Để tìm 1i ta có thể đi ngược từ r và để tìm vi ta có thể đi xuôi từ s theo danh 
sách các biến đã cố định ở giá trị 1 trong tập pS . 
Ở mỗi bước lặp, trước khi tính các cận dưới cho các tập mới, cần thực hiện những 
lựa chọn bắt buộc nêu trên. Có như vậy mới thu được những cận dưới chính xác và 
tránh được những phân nhánh vô ích. 
 3.3. Giải ví dụ bằng số 
Giải bài toán người du lịch với ma trận chi phí ( không đối xứng ) như sau(n=6) 
1 2 3 4 5 6
1 3 93 13 33 9
2 4 77 42 21 16
3 47 17 36 16 28
4 39 90 80 56 7
5 28 46 88 33 25
6 3 88 18 46 92
∞
∞
∞
∞
∞
∞
Bước lặp 0. Tập đầu tiên 0S là tập hợp tất cả các hành trình có thể. Vì ban đầu 
chưa biết một phương án nào nên cận trên β = +∞ . 
Tính cận dưới cho 0S . Từ ma trận (19) trừ mỗi phần tử của các hàng 1, 2, 3, 4, 5, 
6 cho số nhỏ nhất trên hàng tương ứng là 3, 4, 16, 7, 25, 3 ta được một ma trận mới. 
Tiếp theo, trừ mỗi phần tử của các cột 3, 4 của ma trận mới cho số nhỏ nhất trên cột 
tương ứng là 15, 8 ta được ma trận rút gọn (20) (chưa kể các số mũ ở trên các phần tử 
bằng 0). 
y
y y
y
y
i1 
i2 
r s 
i3 
i4 
(19) 
Bùi Thế Tâm VI.11 Quy hoạch rời rạc 
3
12
18
32
2 0
0 48
1 2 3 4 5 6
0 75 2 30 61
0 58 30 17 122
3 31 1 12 0 12
4 32 83 58 49 0
5 3 21 48 0 0
6
0 85 0 35 89
∞
∞
∞
∞
∞
∞
Tổng các hằng số rút gọn là 3 + 4 + 16 + 7 + 25 + 3 + 15 + 8 = 81. Vì vậy, cận 
dưới cho tất cả các hành trình thuộc tập 0S là 81. Điều này có nghĩa là không thể tìm 
được hành trình có tổng chi phí nhỏ hơn 81. 
Bước