http://www.ebook.edu.vn
Bùi Thế Tâm VI.1 Quy hoạch rời rạc
Chương 6
THUẬT TOÁN NHÁNH CẬN
1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN
1.1. Trong các phương pháp giải bài toán qui hoạch nguyên, phương pháp nhánh
cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land A.H
và Doig A.G xây dựng năm 1960 giải bài toán qui hoạch nguyên (trình bày Tiết 2), đến
1963 được Little J.D, Murty K.G, Sweeney D.W và Karen C sử dụng thành công giải
bài toán người du lịch (trình bày trong Tiết 3). Năm 1979 Giáo sư Hoàng Tụy đã ứng
dụng thành công phương pháp này vào giải bài toán qui hoạch lõm. Đây là thuật toán
ứng dụng rộng rãi để giải các bài toán tối ưu khó.
Xét bài toán qui hoạch rời rạc
(
)
min ,ZfX= (1)
XG
∈
( G là tập hữu hạn ) (2)
1.2. Tư tưởng của phương pháp nhánh cận gồm các phép xây dựng sau cho phép
giảm bớt khối lượng lựa chọn.
1. Tính cận dưới. Tìm cận dưới của hàm mục tiêu
(
)
f
x trên tập các phương án
G (hoặc trên tập con G′ nào đó của G) tức là số
(
)
G
ζ
hay
(
)
G
ζ
sao cho:
(
)
(
)
f
xG
ζ
≥ với
x
G
∀
∈( hay
(
)
(
)
f
xG
ζ
′
≥ với
x
G′
∀
∈).
2. Chia thành các tập con (rẽ nhánh ). Chia dần dần tập phương án G thành
cây các tập con (các nhánh). Việc chia nhánh thực hiện theo sơ đồ nhiều bước sau:
Bước 0. Đặt 0
GG≡. Bằng một cách nào đó 0
G được chia thành một số hữu
hạn các tập con ( thường là không giao nhau) 1
11 1
12
, ,...., r
GG G.
Bước 1k≥. Có tập 12
, ,...., k
kk k
r
GG G cần chia nhánh. Ta chọn tập
()
k
k
G
ϑ
theo một
qui tắc nào đó và chia thành một số hữu hạn các tập con :
() () ()
,1 , 2 , ( )
, ,....,
kk k
kk ksk
GG G
ϑϑ ϑ
,
gồm có
()
s
k tập. Khi đó, tập cần chia nhánh tiếp theo là
12 1 1
, ,...., , ,...,
kk k
kk k k k
r
GG G G G
ϑϑ
−+ ,
() () ()()
,1 ,2 ,
, ,....,
kk k
kk ksk
GG G
ϑϑ ϑ
Ta đánh số lại là 1
11 1
12
, ,...., k
kk k
r
GG G
+
++ +
.
3. Tính lại đánh giá
Nếu tập 12
GG⊂ thì
(
)
(
)
12
min min
XG XG
f
XfX
∈∈
≥.
Vì vậy khi chia tập G′ thành 12
, ,....,
s
GG G
′
′′
sao cho
1
'
s
i
i
GG
=
′
=∪ thì cận của bất
kì tập i
G′ đều có
(
)
(
)
(
)
, 1,..,
i
GGis
ζζ
′′
≥=
. Trong các tình huống cụ thể ta thường
nhận được các đánh giá tốt , tức là đối với một i nào đó
(
)
(
)
.
i
GG
ζζ
′
′
http://www.ebook.edu.vn
Bùi Thế Tâm VI.2 Quy hoạch rời rạc
4. Tính phương án
Đối với các bài toán cụ thể có thể chỉ ra các phương pháp khác nhau để tìm ra các
phương án trong các tập con được chia liên tiếp. Phương pháp này dựa trên đặc thù của
mỗi bài toán cụ thể. Nhờ phương án mới tìm được ở mỗi bước ta có thể cải tiến cận trên
(ban đầu gán cho cận trên giá trị là
+
∞) bằng cách gán cho cận trên giá trị hàm mục
tiêu tốt nhất tại thời điểm đó.
5. Tiêu chuẩn tối ưu. Giả sử
1
s
i
i
GG
=
=∪ và phương án XG
ϑ
∈ thỏa mãn điều
kiện:
(
)
(
)
(
)
, 1,..,
i
f
XG G is
ϑ
ζζ
=≤ ∀=
thì X là phương án tối ưu của bài toán
(1)-(2). Qui tắc này được ứng dụng ở giai đoạn chia nhánh .
6. Đánh giá độ chính xác của lời giải xấp xỉ. Giả sử
()
1,..,
1
,min
s
ii
is
i
GG G
ζζ
=
=
==
∪.
Nếu X là một phương án của bài toán xuất phát thì
(
)
(
)
min
xG
f
XfX
ζ
∈
≤≤. Nếu
()
fX
ζ
− đủ nhỏ thì X có thể lấy làm lời giải xấp xỉ với đánh giá độ xấp xỉ là
()
fX
ζ
∆= − .
1.3. Lược đồ tổng quát của phương pháp nhánh cận. Chia tập phương án
G thành cây tập con.
Bước 0. Tính
()
(
)
0
GG
ζζ
=. Nếu tìm được phương án X sao cho
(
)
(
)
f
XG
ζ
= thì X là phương án tối ưu. Ngược lại, chia 0
G = 1
11 1
12
.... r
GG G∪∪∪,
tức là chia thành các tập con (thường là không giao nhau).
Bước 1k≥. Tính các đánh giá
(
)
, 1,..,
k
ik
Gi r
ζ
=. Nếu tìm được phương án X,
k
r
XG∈ sao cho
(
)
(
)
(
)
,
kk
ri
fX G G
ζζ
=≤ với 1, 2,.., k
ir
∀
= , thì X là phương án
tối ưu, quá trình kết thúc. Ngược lại, chọn
()
k
k
G
ϑ
để chia, theo tiêu chuẩn
()
(
)
(
)
1,..,
min
k
kk
i
kir
GG
ϑ
ζζ
=
=. Ta chia tập
()
k
k
G
ϑ
thành một số tập con
() () () ()()
,1 , 2 ,
....
kk k k
kk k ksk
GG G G
ϑϑ ϑ ϑ
=∪∪∪ .
Tập cần chia tiếp theo là
12 1 1
, ,...., , ,...,
kk k
kk k k k
r
GG G G G
ϑϑ
−+ ,
() () ()
,1 ,2 ,
, ,...., k
kk k
kk ks
GG G
ϑϑ ϑ
Sau đó ta đánh số lại là 1
11 1
12
, ,...., k
kk k
r
GG G
+
+
++
và sang bước k+1.
http://www.ebook.edu.vn
Bùi Thế Tâm VI.3 Quy hoạch rời rạc
2. PHƯƠNG PHÁP LAND VÀ DOIG GIẢI BÀI TOÁN QUI HOẠCH
NGUYÊN
2.1. Xét bài toán qui hoạch nguyên tuyến tính sau:
()
1
min
n
jj
j
Z
fX cx
=
==
∑ (3)
với các điều kiện ràng buộc
ij
j=1
, 1,..,
n
jii
axRb i m=
∑ (quan hệ thứ tự
{
}
,,
i
R
∈
≤≥= ) (4)
0 , 1,.., .
jj
x
djn≤≤ = (5)
j
x
nguyên 1
1,..,
j
n
=
1
nn
≤
(6)
trong đó
j
d là cận trên của biến
j
x
(có thể j
d
=
+∞ ). Giả thiết tập tất cả các điểm
x
thỏa mãn (4)-(5) là bị chặn.
Nếu 1
nn=, ta có bài toán qui hoạch nguyên hoàn toàn, còn nếu 1
nn< thì có bài
toán qui hoạch nguyên bộ phận. Ngoài ra, bài toán tìm max có thể qui về bài toán tìm
min bằng cách đổi dấu hàm mục tiêu. Có nhiều phương pháp giải bài toán qui hoạch
nguyên tuyến tính, trong đó có phương pháp nhánh cận. A.H Land và A.G Doig (1960)
là những người đầu tiên áp dụng phương pháp nhánh cận để giải bài toán qui hoạch
tuyến tính nguyên.
2.2. Nội dung phương pháp
1. Cho tập 0
GG≡ xác định bởi (4) - (6).
2. Cho các tập
()
k
k
G
ϑ
, 1,.., ,
k
r
ϑ
=
và 1, 2,....k
=
. xác định bởi (4),(6) và ràng buộc
bổ sung:
, 1,..,
jjj
kk
hxd jn
ϑϑ
 
≤≤ =
 
  . (7)
3. Tính cận. Đối với 0
G ước lượng
()
(
)
0
0
GfX
ζ
= với 0
X là lời giải của bài
toán qui hoạch tuyến tính (3)-(5).
Đối với k
G
ϑ
thì
()
kk
GfX
ϑ
ζ
ϑ


=



, trong đó k
X
ϑ



là lời giải của bài toán qui
hoạch tuyến tính (3),(4) và (7).
Nếu
(
)
k
G
ϑ
=∅ thì
(
)
k
G
ϑ
ζ
=
+∞ .
4. Tính phương án. Nếu 0
X thỏa mãn điều kiện nguyên (6), thì 0
X là nghiệm
tối ưu của bài toán ban đầu, thuật toán dừng.
http://www.ebook.edu.vn
Bùi Thế Tâm VI.4 Quy hoạch rời rạc
Nếu k
X
ϑ



thỏa mãn điều kiện nguyên (6) thì nó là phương án tối ưu của bài toán
(3), (4), (7), (6) và nó cũng là một phương án của bài toán ban đầu. Lấy k
X
ϑ



để cải
tiến cận trên.
5. Chia nhánh. Cần chia nhánh khi
()
k
Xk
ϑ



không thỏa mãn điều kiện nguyên
(6). Giả sử
()
1
,1
r
k
x
rn
k
ϑ

≤≤

 là một thành phần không nguyên của phương án này,
khi đó tập hợp
()
k
k
G
ϑ
chia thành hai tập hợp
() () ()
,1 ,2
kk k
kk k
GG G
ϑϑ ϑ
=∪, trong đó
() ()
()
() ()
()
,1
,2
|,
|, 1
kk
rr
kk
kk
rr
kk
k
GXXGxx
k
k
GXXGxx
k
ϑϑ
ϑϑ
ϑ
ϑ




=∈ ≤












=∈ ≥ +








Chú ý rằng nếu tất cả j
c trong (3) là nguyên với 1
jn
≤
và 1
0
j
ckhijn=≥ thì
cận dưới
(
)
k
G
ϑ
ζ
có thể dùng đánh giá mạnh hơn
(
)
(
)
kk
GfX
ϑϑ
ζ

′=
, ở đây kí hiệu
]
[
f
là số nguyên nhỏ nhất mà lớn hơn hay bằng
f
.
2.3. Giải ví dụ bằng số
Xét bài toán qui hoạch nguyên tuyến tính sau:
min -x1 -x2 (8)
2x1 + 11 x2
≤
38
x1 + x2 ≤ 7 (9)
4 x1 - 5x2
≤
5
x1, x2 ≥ 0 (10)
x1, x2 nguyên (11)
Bước 0. Giải bài toán (8)-(10), tìm được nghiệm 045
4,2
99
X
=

. Cận dưới
() ()
][
00
77GfX
ζ

′==−=−
 . Phương án 0
X không thỏa mãn điều kiện nguyên
(11). Chúng ta chia 0
G thành hai tập hợp 011
12
GGG=∪, trong đó
{
}
{}
10
11
10
21
|,4
|,5
GXXGx
GXXGx
=
∈≤
=
∈≥
http://www.ebook.edu.vn
Bùi Thế Tâm VI.5 Quy hoạch rời rạc
Bước 1. Giải hai bài toán quy hoạch tuyến tính: cực tiểu (8) trên hai tập hợp 1
1
G
và 1
2
G. Trong bài toán đầu tiên cực tiểu trên miền 1
1
G đạt tại điểm 8
4, 2 11



, do đó
(
)
1
1
8
66
11
G
ζ

′=− =−

. Tập 1
2
G là trống nên
(
)
1
2
G
ς
=
+∞ .
Chọn 1
1
G để chia nhánh ta được:
{
}
{}
112
1,1 1 2 1
112
1,2 1 2 2
|,2
|,3
GXXGx G
GXXGx G
=∈≤≡
=∈≥≡
12
23
GG
=
=∅
Bước 2. Giải các bài toán qui hoạch tuyến tính:
1) Tìm cực tiểu (8) trên 2
1
G được
()
2
1
233
3,2 5 5
144
XG
ζ
 
′
=
⇒=−=−
  


2) Tìm cực tiểu (8) trên 2
2
G được
()
2
2
211
2,3 5 5
222
XG
ζ
 
′
=
⇒=−=−
  


3) 12
23
GG==∅,
(
)
2
3
G
ζ
′
=
+∞
Chọn 2
1
G để chia nhánh :
{
}
{}
223
1,1 1 1 1
223
1,2 1 1 2
|,3
|,4
GXXGx G
GXXGx G
=∈≤≡
=∈≥≡
Đánh số lại 232 32323
1,1 1 1,2 2 2 3 3 4
,,,G GG GGGGG≡ ≡=≡
Bước 3. Giải các bài toán qui hoạch tuyến tính:
1) Tìm cực tiểu (8) trên 3
1
G được
()
()
][
3
1
33, 2 5 5
1
XG
ζ
 ′
=
⇒=−=−


2) 3
2
G=∅
(
)
3
2
G
ζ
′
⇒=+∞
3) Tìm cực tiểu (8) trên 3
3
G được
()
3
3
32
11
2,3 5 5
32
22
XX G
ζ
 
′
== ⇒ =−=−
  


4) 32
43
GG==∅
(
)
3
4
G
ζ
′
⇒=+∞