Header Page 1 of 258.

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH

Lê Văn Thìa

PHƯƠNG PHÁP NHÁNH – CẬN CHO
BÀI TOÁN QUY HOẠCH NGUYÊN

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thành phố Hồ Chí Minh – 2012

Footer Page 1 of 258.


Header Page 2 of 258.

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH

Lê Văn Thìa

PHƯƠNG PHÁP NHÁNH – CẬN CHO
BÀI TOÁN QUY HOẠCH NGUYÊN

Chuyên ngành: Toán Giải Tích
Mã số: 60 46 01
LUẬN VĂN THẠC SĨ TOÁN HỌC



LỜI MỞ ĐẦU
Quy hoạch nguyên (hay quy hoạch rời rạc) là một hướng quan trọng của quy
hoạch toán học. Nó nghiên cứu lớp bài toán quy hoạch trong đó thêm điều kiện các
biến chỉ nhận giá trị trên tập số nguyên. Lớp bài toán này rất phổ biến trong thực tế.
Nó thu hút sự quan tâm của các nhà khoa học nghiên cứu trong các lĩnh vực: kinh
tế, điều khiển, thiết kế, sinh học,… Chính trong các lĩnh vực đó các phương pháp
liên tục tỏ ra kém hiệu quả khi nghiên cứu các đối tượng không thể chia nhỏ tùy ý,
thì quy hoạch nguyên là công cụ chủ yếu nghiên cứu hiệu quả các lĩnh vực đó.
Có thể nói quy hoạch nguyên bắt đầu khai sinh lịch sử của mình từ năm
1958, khi công bố thuật toán nổi tiếng của Gomory về phương pháp cắt. Sau đó một
thời gian dài, phương pháp cắt là công cụ duy nhất để giải các bài toán quy hoạch
nguyên. Nhưng từ khi phương pháp nhánh – cận xuất hiện trong [Land – Doig
1960] và nhất là dạng hoàn thiện của nó trong [Dakin 1965], nó trở nên ưu thế rõ
rệt. Hiện nay phương pháp nhánh – cận là một trong những phương pháp chủ yếu
để giải bài toán quy hoạch nguyên. Do đó, việc tìm hiểu về phương pháp nhánh –
cận là cần thiết.
Mục tiêu của luận văn là tìm hiểu và trình bày lại một cách chi tiết phương
pháp nhánh – cận. Các vấn đề được đề cập trong luận văn được trình bày một cách
chặt chẽ về mặt toán học.
Nội dung luận văn gồm ba chương:
Chương 1 “Một số kết quả của Quy hoạch tuyến tính và Giải tích lồi”
trình bày lại một số khái niệm và tính chất của Quy hoạch tuyến tính và Giải tích
lồi. Các khái niệm đối ngẫu, định lý đối ngẫu, tập lồi, tập lồi đa diện, điểm cực biên,
tia cực biên của tập lồi đa diện. Đặc biệt là các tính chất về sự biễu diễn của mỗi tập

Footer Page 4 of 258.


Header Page 5 of 258.

2.2. Thuật toán nhánh – cận giải bài toán quy hoạch tuyến tính nguyên bộ phận ........... 25
2.2.1. Cơ sở lý luận của thuật toán............................................................................... 25
2.2.2. Thuật toán nhánh – cận ...................................................................................... 31
2.3. Một số kĩ thuật được sử dụng trong thuật toán nhánh- cận ...................................... 31
2.3.1. Kĩ thuật Hậu tối ưu (Reoptimization)................................................................. 31
2.3.2. Quy tắc chọn bài toán phân nhánh và quy tắc phân nhánh ................................ 34
2.4. Ví Dụ......................................................................................................................... 34
Chương 3 ............................................................................................................................. 44
3.1. Bài toán Quy hoạch tuyến tính với Matlab .............................................................. 44
3.2. Lập trình thuật toán giải bài toán quy hoạch tuyến tính nguyên bộ phận trên Matlab
......................................................................................................................................... 47
3.3. Giải bài toán Quy hoạch tuyến tính nguyên bộ phận trên Matlab ............................ 50
KẾT LUẬN.......................................................................................................................... 53
TÀI LIỆU THAM KHẢO ................................................................................................... 54

Footer Page 6 of 258.


Header Page 7 of 258.

1

Chương 1
Một số kết quả của Quy hoạch tuyến tính và
Giải tích lồi
1.1. Quy hoạch tuyến tính
Ta nhắc lại một số kết quả của quy hoạch tuyến tính mà chúng sẽ được sử
dụng để chứng minh các kết quả phía sau.
Định nghĩa 1.1.1. Bài toán Quy hoạch tuyến tính dạng tổng quát có dạng:


Định nghĩa 1.1.3. Bài toán Quy hoạch tuyến tính có thể phát biểu dưới dạng ma
trận như sau:

f ( x) =< c, x > → min
thỏa hệ ràng buộc:

 Ax (≤ =≥)b

x ≥ 0
trong đó, A là ma trận kích thước m × n .

Footer Page 7 of 258.


Header Page 8 of 258.

2

 Phương án x = ( x1 ,..., xn ) được gọi là phương án cơ sở nếu hệ các vectơ cột

{ Aj } của ma trận A ứng với các thành phần x j > 0 ( j =
1,..., n) là độc lập tuyến
tính.

 Phương pháp đơn hình:
Xét bài toán Quy hoạch tuyến tính dạng chính tắc sau:

=
f ( x)


xb1 a1 , x=
a2 ,..., x=
am ),
b2
bm
được xác định từ hệ vectơ cơ sở đơn vị m chiều Ab1 , Ab 2 ,..., Abm .
- Khai triển mọi vectơ điều kiện Aj ( j = 1,..., n) theo hệ vec tơ cơ sở

Ab1 , Ab 2 ,..., Abm có nghĩa là tính các hệ số x1 j , x2 j ,..., xmj , j = 1,..., n .
- Tính các hiệu Z j − c j , j =
1,..., n,
trong đó =
Z j C=
b Aj

m

∑c
i =1

x =
, j 1,..., n .

bi ij

Để tiện tính toán người ta trình bày theo bảng sau:

Footer Page 8 of 258.



Abl … Ak … Aj …

Abm … An

Ab1

cb1

xb1 x11 … 1

… 0

… 0

… x1k … x1 j … 0

… x1n

Ab 2

cb 2

xb 2 x21 … 0

..

… 0

… x2k … x2 j … 0


… … … …

cbm xbm xbm … 0

… 0

… 0

… xmk … xmj … 1

… xmn

…

…

…

…

xbl

Z0

xb1 … 0

…

… …



xij > 0 thì phương án cơ sở chấp nhận được chưa tối ưu và có thể cải thiện
được bằng cách đưa vào cơ sở vectơ có ( Z j − c j ) max > 0 . Giả sử

( Z j − c j ) max = Z k − ck > 0 , khi đó đưa vectơ Ak vào cơ sở và loại ra khỏi cơ
sở vectơ ứng với:

t = min
xik > 0

Footer Page 9 of 258.

xbi
xik


Header Page 10 of 258.

4

xbi xbl
Giả=
sử t min
, do đó Abl bị loại ra khỏi cơ sở. Cơ sở mới gồm m
=
xik > 0 x
xlk
ik
vectơ: ( Ab1 ,..., Abl −1 , AK , Abl +1 ,..., Abm ) . Phần tử xlk được gọi là phần tử giải được.
Bằng phép biến đổi cơ bản và đơn giản biểu thức:

Với ràng buộc

Với ràng buộc

< ai , x=
> bi , i ∈ M 1

yi tự do, i ∈ M 1

< ai , x > ≤ bi , i ∈ M 2

yi ≤ 0, i ∈ M 2

< ai , x > ≥ bi , i ∈ M 2

yi ≥ 0, i ∈ M 3

x j ≥ 0, j ∈ N1

< y, Aj >≤ c j , j ∈ N1

x j ≤ 0, j ∈ N 2

< y, Aj > ≥ c j , j ∈ N 2

x j tự do j ∈ N 3

< y, A=
c j , j ∈ N3
j >

u=
yi (< ai , x > −bi ),
i
v=
(c j − < y , A j >) x j .
j
Theo định nghĩa của bài toán đối ngẫu thì yi và < ai , x > −bi cùng dấu, còn

c j − < y, Aj > và x j cùng dấu. Do đó, ui ≥ 0, ∀i và v j ≥ 0, ∀j .
Nhận xét rằng

∑u

i

=
< y, Ax − b >,

j

=
< c − yA, x > .

i

∑v
j

Do đó,


mục tiêu tối ưu bằng nhau.
Chứng minh
Ta có thể đưa cặp bài toán đối ngẫu đối xứng về cặp bài toán đối ngẫu không
đối xứng, do đó chỉ chứng minh cho cặp bài toán đối ngẫu không đối xứng. Giả sử
bài toán đối ngẫu không đối xứng có phương án tối ưu nhận được bằng phương
pháp đơn hình (xem trong tài liệu tham khảo [Cảnh 2004], [Khánh – Nương 2000],
[Khánh 2002]). Hệ vectơ cơ sở tương ứng với phương án tối ưu gồm các vectơ

Ab1 , Ab 2 ,..., Abm . Đặt Ab = ( Ab1 ,..., Abm ) ma trận được thành lập từ hệ các vectơ cơ sở.
Khi đó, Aj = Ab X j . Biểu diễn D = ( X 1 ,..., X n ) ma trận được thành lập từ những hệ
số của bảng đơn hình cuối cùng. Ta có:

=
A A=
D Ab−1 A
b D;

(1.1)

=
Ab X opt A=
X opt Ab−1 A0
0;

(1.2)

=
Z min C=
Cb Ab−1 A0 ,
b X opt

Xét vectơ Yopt A − C . Khi sử dụng liên tiếp các công thức (1.5), (1.1), (1.4) ta
được

Yopt A − C= Cb Ab−1 A − C= Cb D − C ≤ 0.
Do đó, Yopt A ≤ C có nghĩa là Yopt là phương án chấp nhận được của bài toán
đối ngẫu. Bây giờ tính giá trị của dạng tuyến tính f khi Y = Yopt .
−1
f (=
Yopt ) Y=
Cb A=
Cb=
X opt min Z
opt A0
b A0

(1.6)

ở đây các công thức (1.5), (1.2), (1.3) được dùng liên tiếp.
Biểu thức (1.6) chứng tỏ rằng: giá trị dạng tuyến tính của bài toán đối ngẫu
(khi Y = Yopt ), f (Yopt ) trùng với giá trị tối ưu của bài toán gốc.
Bây giờ cần chứng minh rằng: Yopt là phương án tối ưu của bài toán đối
ngẫu.
Ta có:

f (=
Y ) YA
=
YAX .
0
Một phương án chấp nhận được bất kỳ Y của bài toán đối ngẫu phải thỏa

Chứng minh
Ở chứng minh định lý 1.1.6 ta đã đặt

u=
yi (< ai , x > −bi ),
i
v=
(c j − < y , A j > ) x j
j
Theo định nghĩa của bài toán đối ngẫu ta thấy rằng ui ≥ 0, v j ≥ 0 ∀i, ∀j .
Đồng thời ta cũng có

< c , x > − < b, =
y>

∑u + ∑v .
i

i

j

j

Theo định lý đối ngẫu mạnh , nếu x và y là phương án tối ưu thì

< c, x > = < b, y > . Do đó, ui = v j = 0, ∀i, ∀j . Ngược lại, nếu ui = v j = 0, ∀i, ∀j thì
< c, x > = < b, y > suy ra x, y là phương án tối ưu.



+ Thông thường thì phương án ấy không phải là phương án tối ưu, vì trong
các biến cơ sở vẫn còn có biến âm, chuyển sang giai đoạn 2.
- Giai đoạn 2: Khi các biến cơ sở còn biến âm ta cần khử các biến âm mà vẫn
giữ được ∀( Z j − c j ) ≤ 0 . Phương án là tối ưu khi mọi biến cơ sở đều không âm.
Giả sử xbl < 0 , khi đó ta loại vectơ Al khỏi cơ sở. Nếu trong hàng l không
có thành phần xlj < 0 thì bài toán không có phương án chấp nhận được. Nếu có một
vài xlj < 0 thì phương án có thể cải thiện được và đưa vectơ Ak vào cơ sở với k
được xác định bởi:

min

Z j − cj

xlj < 0

xlj

=

Z k − ck
.
xlk

Việc chọn như vậy các hiệu Z j − c j vẫn không dương. Quá trình tính toán
tương tự được tiếp tục đến khi nhận được phương án tối ưu.
Trong trường hợp, nếu có vài biến cơ sở xbl < 0 thì việc chọn phần tử giải
được chọn theo công thức:

min
xij < 0

i =1

i =1

tổ hợp lồi của các vectơ x1 ,..., x m .
 Cho tập X ⊂  n , bao lồi của X , được kí hiệu là conv( X ) là tập hợp tất
cả tổ hợp lồi của các vectơ trong X . Tức là
k

k

conv( X ) :=
{x =
1, v1 ,..., vk ∈ X }.
∑ λi vi : λi ≥ 0,∑ λi =
=i 1 =i 1

Nếu
=
x

k

∑ λ v ∈ conv( X ) là tổ hợp lồi của các vectơ v ,..., v
i =1

i i

i


Định nghĩa 1.2.3. Cho tập lồi đa diện P ⊂  n . Tập hợp F ⊂ P được gọi là diện
của

P

nếu

F= {x ∈ P :< w, x =
> t} và

P ⊆ {x ∈  n :< w, x > ≤ t} trong đó

w ∈  n , t ∈  . Nếu F ≠ ∅ và F ≠ P thì F được gọi là diện không tầm thường.
Ta thấy rằng mỗi diện

F

của đa diện

P = P ( A, b)

có dạng

F= {x ∈  n : Ax ≤ b, < w, x >≤ t , − < w, x >≤ −t} , với một t ∈  nào đó. Do đó F
cũng là tập lồi đa diện.
Định nghĩa 1.2.4. Cho tập lồi đa diện
=
P P ( A, b) ⊆  n và M là tập chỉ số các
dòng của A . Cho I ⊆ M ta xét tập hợp


max{< c, x >: Ax ≤ b}

(1.11) .

Theo định lý đối ngẫu mạnh, ta có bài toán quy hoạch đối ngẫu của (1.11)

min{< b, y >: AT y = c, y ≥ 0} cũng có nghiệm tối ưu y * và thỏa < b, y* >= t . Đặt

=
I : {i : yi * > 0} . Theo điều kiện độ lệch bù, những nghiệm tối ưu x * của bài toán
(1.11) thỏa Ai x*= bi , ∀i ∈ I . Vậy F = fa ( I ) .



Định nghĩa 1.2.6. (tập tương đương) Cho tập lồi đa diện
=
P P ( A, b) ⊆  n , S ⊆ P .
Khi đó ta gọi eq ( S ) := {i ∈ M : Ai x = bi , ∀x ∈ S } là tập tương đương của S .
Nhận xét: Cho S , S ' là hai tập con của tập lồi đa diện P . Nếu S ⊆ S ' thì

eq ( S ) ⊇ eq ( S ') . Như vậy, với S là tập con khác rỗng của tập lồi đa diện P , nếu F
là diện của P chứa S thì eq ( F ) ⊆ eq ( S ) . Thêm nữa là fa (eq ( S )) sẽ là diện của P
và chứa S . Do đó, ta có mệnh đề sau:
Mệnh đề 1.2.7. Cho tập lồi đa diện
=
P P ( A, b) ⊆  n và S là tập con khác rỗng
của P . Diện nhỏ nhất chứa S của P là fa (eq ( S )) .
Hệ quả 1.2.8.
(i) Tập lồi đa diện P = P ( A, b) không có bất kỳ diện không tầm thường nào
khi và chỉ khi eq ( P ) = M , trong đó M là tập chỉ số các dòng của A .

) : {=
x

k

k

∑ λ v : ∑ λ=

i i
=i 1 =i 1

i

1, v1 ,..., vk ∈ X } .

Hệ vectơ v1 ,..., vk ∈  n được gọi là độc lập affine nếu
k

∑λ
i =1

i

k

∑λ v
i =1

i i


Footer Page 18 of 258.




Header Page 19 of 258.

13

Do đó, ta có định nghĩa tương đương với định nghĩa 1.2.11 là :

x ∈P =
P ( A, b) là điểm trong tương đối của P nếu eq ({x }) = eq ( P ) .
Bổ đề 1.2.13. Cho P = P ( A, b) là tập lồi đa diện khác rỗng. Khi đó, tập hợp các
điểm trong tương đối của P cũng khác rỗng.
Chứng minh
Đặt M = {1,..., m} là tập chỉ số các dòng của A .

I := eq ( P ) và J := M \ I .
Khi đó, nếu J = ∅ thì I = M . Theo hệ quả 1.2.8 (i) ta có tập lồi đa diện P
không có bất kỳ diện không tầm thường nào. Do đó, bất kỳ điểm nào của P cũng là
điểm trong tương đối.
Nếu J ≠ ∅ thì với mỗi j ∈ J ta tìm được x j ∈ P sao cho Ax j ≤ b và Aj x j < b j .
Do P là tập lồi nên y :=

1
∑ x j (trong đó | J | là số phần tử của J ) cũng thuộc
| J | j∈J




Header Page 20 of 258.

14

“ r ≥ s ”: Chọn s + 1 vectơ độc lập affine x 0 , x1 ,..., x s ∈ F . Suy ra theo bổ đề
hệ

1.2.10

vectơ

x1 − x 0 ,..., x s − x 0

là

độc

lập

tuyến

tính

và

AI ( x j − x 0 ) = bI − bI = 0 , j = 1,..., s . Suy ra r ≥ s .
“ r ≤ s ”: Vì F ≠ ∅ nên s ≥ 0 . Do đó ta cũng giả thiết r ≥ 0 . Do F ≠ ∅
Theo bổ đề 1.2.13 tồn tại một điểm trong tương đối x ∈ F mà theo bổ đề 1.2.12 ta

(1.12) .

Ta cần chứng minh F = G , trong đó

=
G {=
x : AI x bI }

(1.13) .

Theo (1.12) ta có F ⊆ G . Giả sử tồn tại y ∈ G \ F . Khi đó, tồn tại j ∈ J sao
cho

=
AI y bI , Aj y > b j

(1.14) .

Do F ≠ ∅ nên theo bổ đề 1.2.13 tồn tại điểm trong tương đối của F , ta gọi
điểm đó là x . Ta xét điểm z (τ ) =
x +τ ( y − x) =
(1 − τ ) x + τ y .

Footer Page 20 of 258.


Header Page 21 of 258.

15


1.3.Điểm cực biên. Tia cực biên
Định nghĩa 1.3.1. Điểm x ∈ P =
P ( A, b) được gọi là điểm cực biên của P nếu

x = λ x + (1 − λ ) y với x, y ∈ P và 0 < λ < 1 ta suy ra x= y= x .
Định lý 1.3.2. Cho
=
P P ( A, b) ⊆  n là tập lồi đa diện và x ∈ P . Khi đó các mệnh
đề sau là tương đương:
(i) {x } là 0-diện của P (diện có số chiều là 0).
(ii) Tồn tại một vectơ c ∈  n sao cho x là nghiệm tối ưu duy nhất của quy
hoạch tuyến tính min{< c, x >: x ∈ P} .
(iii) x là điểm cực biên của P .
(iv) rank Aeq ({ x }) = n .
Chứng minh

Footer Page 21 of 258.


Header Page 22 of 258.

16

“(i) ⇒ (ii)”: Vì x là diện của P nên tồn tại bất phương trình < w, x > ≥ t sao
cho P ⊆ {x :< w, x > ≥ t} và {x } =
P ∩ {x :< w, x > ≥ t} =
{x ∈ P :< w, x > =
t} . Do đó,
x là nghiệm duy nhất của quy hoạch tuyến tính min{< c, x >: x ∈ P} với c := w .



Hệ quả 1.3.3. Tập lồi đa diện khác rỗng
P P ( A, b) ⊆  n có ít nhất một điểm cực
=
biên khi và chỉ khi rank A = n .
Chứng minh
Theo hệ quả 1.2.17 diện khác rỗng nhỏ nhất của P có số chiều là 0 khi và
chỉ khi rank A = n . 
Định nghĩa 1.3.4. Cho P là tập lồi đa diện. Khi đó, nón lùi xa char.cone( P ) được
định nghĩa là: char.cone( P=
) : {r : x + r ∈ P , ∀x ∈ P} .
Mỗi r ∈ char.cone( P ) được gọi là tia của P . Tia r của P được gọi là tia
cực biên nếu không tồn tại tia r1 , r 2 của P sao cho r1 ≠ θ r 2 , ∀θ ∈  +

r = λ r1 + (1 − λ )r 2 , λ ∈ [0,1] .

Footer Page 22 of 258.


Header Page 23 of 258.

17

Nhận xét: ta thấy rằng nếu P ≠ ∅ thì 0 ∈ char.cone( P ) , và nếu P = ∅ thì

char.cone( P ) = ∅ . Vậy ta có char.cone( P ) = ∅ khi và chỉ khi P = ∅ .
Bổ đề 1.3.5. Cho P = P ( A, b) là tập lồi đa diện khác rỗng. Khi đó,

char.cone
=


char.cone( P ) . Khi đó, A.r ≤ 0 và từ r ≠ 0 ta có r ≠
r≠

1
r ∈ char.cone( P ) và
2

1 1
1 3
3
=
r
( r ) + ( r ) , điều này mâu thuẫn với giả
r ∈ char.cone( P ) . Nhưng
2 2
2 2
2

thiết r là điểm cực biên của char.cone( P ) . Do đó, cùng với hệ quả 1.3.3 ta có
mệnh đề sau:
Mệnh đề 1.3.6: Cho tập lồi đa diện
=
P P ( A, b) ≠ ∅ . Vectơ không là điểm cực biên
của char.cone( P ) khi và chỉ khi rank A = n .
Định lý 1.3.7: Cho
=
P P ( A, b) ⊂  n là một tập lồi đa diện khác rỗng. Khi đó các
mệnh đề sau là tương đương:
(i) r là tia cực biên của P .

AI r1 0 và AM \ I r < 0 . Nhưng ta có r =

1
1
(r + ε r1 ) + (r − ε r1 ) , điều này
2
2

mâu thuẫn với giả thiết r là tia cực biên.
Do đó, dim F = 1 . Vì r ≠ 0 , tập không bị chặn {θ r : θ ∈  + } chứa trong F
cũng có số chiều bằng 1. Vậy
=
F {θ r : θ ∈  + } là 1-diện của char.cone( P ) .
“(ii)⇒(iii)”: Áp dụng định lý số chiều 1.2.15 cho char.cone( P ) ta suy ra

rank AI= n − 1 . Do {θ r : θ ∈  + } có số chiều là 1 nên r ≠ 0 .
“(iii)⇒(i)”: Theo kết quả của đại số tuyến tính ta có tập nghiệm của hệ

AI x = 0 I có số chiều bằng 1. Do AI r = 0 và r ≠ 0 nên với y thỏa AI y = 0 ta có

=
y θ r ,θ ∈  .
Giả sử r = λ r1 + (1 − λ )r 2 với r1 , r 2 ∈ char.cone( P ) . Khi đó,

0 I = AI r= λ AI r1 + (1 − λ ) AI r 2 ≤ 0 I


≤0I

≤0I

max{− < c, x >: Ax ≤ 0, − < c, x >≤=
1} max{− < c, x >: x ∈ P '}

(1.15) .

Vì rank A = n nên P ' cũng là tập lồi đa diện có ít nhất một điểm cực biên.
Thêm nữa là P ' ≠ ∅ vì

r'
∈ P ' . Do ràng buộc − < c, x >≤ 1 suy ra
− < c, r ' >

(1.15) có nghiệm tối ưu. Dễ dàng suy ra được giá trị tối ưu của (1.15) là 1 đạt
được tại x =

r'
.
− < c, r ' >

Do nghiệm tối ưu của bài toán (1.15) đạt được tại điểm cực biên của
nên r* :
P ' ⊆ char.cone( P )=

r'
∈ char.cone( P ) .
− < c, r ' >
< c, r* >= −1

Suy ra


trong đó, x k , k ∈ K là các điểm cực biên của P và r j , j ∈ J là các tia cực biên của
P.

Footer Page 25 of 258.