ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN - CƠ - TIN HỌC

Phan Ngọc Tú

BÀI TOÁN QUY HOẠCH PHI TUYẾN
VỚI KỸ THUẬT PHÂN RÃ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SỸ
Chuyên ngành: Toán giải tích
Mã số: 60.46.01.02

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS NGUYỄN HỮU ĐIỂN

Hà Nội - 2014


1

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT

QHTT

Quy hoạch tuyến tính.

QHPT

Quy hoạch phi tuyến.


Một số kiến thức về bài toán tối ưu . . . . . . . . . . . . . . . .

1

1.2

Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2 Phân rã trong quy hoạch tuyến tính
2.1

2.2

Những ràng buộc phức tạp . . . . . . . . . . . . . . . . . . . .

12

2.1.1

Cấu trúc bài toán . . . . . . . . . . . . . . . . . . . . . .

13

2.1.2

Sự phân rã . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Phương pháp giảm dư Lagrange . . . . . . . . . . . . . . . . .

45

3.1.1

45

Sự phân rã . . . . . . . . . . . . . . . . . . . . . . . . . .
i


3.2

3.1.2

Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.1.3

Đối ngẫu bất khả thi . . . . . . . . . . . . . . . . . . . .

51

3.1.4

Cập nhật hệ số . . . . . . . . . . . . . . . . . . . . . . .


3.2.5

Cập nhật tham số phạt . . . . . . . . . . . . . . . . . . .

57

Kết luận

61

Tài liệu tham khảo

62

ii


Lời nói đầu
Tối ưu hóa là một môn toán học ứng dụng đang được nghiên cứu, giảng dạy
và học tập ở nhiều trường Đại học - Cao đẳng, góp phần quan trọng trong
việc ứng dụng khoa học công nghệ vào cuộc sống và sản xuất.
Ngày nay, Quy hoạch tuyến tính (QHTT) vẫn là một phần quan trọng và
được phát triển hoàn thiện nhất trong lý thuyết tối ưu hóa. Phần ít được đề
cập hơn là tối ưu phi tuyến, còn gọi là quy hoạch phi tuyến (QHPT). Ở cả hai
phần này, một số bài toán thực tế trong cuộc sống ta hay gặp các bài toán có
kích thước lớn, do đó việc xử lý chúng như thông thường là điều không thể.
Vì vậy việc thiết kế những thuật toán theo hướng giải quyết các bài toán lớn
là một trong những vấn đề vẫn đang được quan tâm xử lý hiện nay.
Trong luận văn xem xét chú ý đến những trường hợp riêng của các bài
toán tối ưu hóa, những bài toán có cấu trúc phân rã có thể khai thác thuận


Chương 1

Các kiến thức cơ bản
1.1 Một số kiến thức về bài toán tối ưu
Trong không gian vectơ R n , cho D ⊆ R n là một tập khác rỗng và hàm số thực
f : D → R tùy ý. Bài toán tối ưu có dạng

(P)

min{ f ( x) : x ∈ D }

là bài toán tìm vectơ (điểm) x∗ ∈ D sao cho f ( x∗ ) ≤ f ( x) với mọi x ∈ D.
Trường hợp D = R n ta có bài toán tối ưu không ràng buộc
min{ f ( x) : x ∈ R n } hay minn f ( x)
x ∈R

Trái lại, (P) là bài toán tối ưu có ràng buộc. Khi ấy tập D thường được cho
bởi
(1.1)

D = x ∈ R n : gi ( x )

0, i = 1, . . . , m; h j ( x) = 0, j = 1, . . . , p

với gi , h j : R n → R là các hàm số cho trước, gọi là các hàm ràng buộc.

Các hệ thức gi ( x) ≥ 0 gọi là các ràng buộc bất đẳng thức, các hệ thức h j ( x) =

0 gọi là các ràng buộc đẳng thức. Bài toán (P) với f (x) không tuyến tính hoặc

m

∗
∗
∗


(1.1)
∇ f ( x ) + ∑ λi ∇ gi ( x ) + ∑ µ∗j ∇h j ( x∗ )


i =1
j =1

λi∗ gi ( x∗ ) = 0 và λi∗ 0, i = 1, . . . , m
(1.2)




gi ( x∗ ) 0, i = 1, . . . , m; h j ( x∗ ) = 0, j = 1, . . . , p (1.3)

Chứng minh. Do x∗ là điểm cực tiểu địa phương nên theo điều kiện cần tối
ưu cấp 1 ta có < ∇ f ( x∗ ), d > 0 với mọi d ∈ TD ( x∗ ). Do x∗ là điểm chính
qui (tức là TD ( x∗ ) = S( x∗ )) nên bất đẳng thức này đúng với mọi d ∈ S( x∗ ),
nghĩa là với mọi d ∈ R n nghiệm đúng hệ phương trình trên với x∗ thay cho
x0 .
Áp dụng bổ đề Farkas cho ma trận A với ma trận chuyển vị AT có các cột là

−∇ gi ( x∗ ), i ∈ I ( x∗ ), ∇h j ( x∗ ), −∇h j ( x∗ ) ( j = 1, . . . , p).

tương ứng với (P)
p

m

L( x, λ, µ) = f ( x) + ∑ λi gi ( x) +
i =1

(x ∈ R n , λi
thành

∑ µ j h j ( x).
j =1

0 với mọi i và µ j tùy ý với mọi j). Khi đó điều kiện KKT được viết lại

∇x L( x, λ, µ) = 0, λT ∇λ L( x, λ, µ) = 0,

∇λ L( x, λ, µ)

0, ∇µ L( x, λ, µ) = 0,

điều kiện (1.1) gọi là điều kiện dừng, bởi vì ∇x L( x, λ, µ) = 0; (1.2) là điều kiện bù
và (1.3) là điều kiện chấp nhận được.
b) Trường hợp tập D có thêm ràng buộc xk 0 với k ∈ K ⊂ {1, . . . , n}, tức là
D = { x ∈ R n : gi ( x )

0, i = 1, . . . , m;

h j ( x) = 0, j = 1, . . . , p; xk

∂xk
∂x
∂xk
k
i =1
j =1
p

xk∗ [

0, xk∗

0 ∀k ∈ K,

p
m
∂h j ( x∗ )
∂g ( x∗ )
∂ f (x∗ )
+ ∑ λi i
+ ∑ µj
] = 0, ∀k ∈ K.
∂xk
∂x
∂x
k
k
i =1
j =1


3
1
min ( x1 − )2 + ( x2 − )4 , với các điều kiện
x
2
2
g1 ( x ) = x 1 + x 2 − 1

g3 ( x ) = − x 1 + x 2 − 1

0, g2 ( x) = x1 − x2 − 1

0,

0, g4 ( x) = − x1 − x2 − 1

0.

Có thể thấy x∗ = (1, 0)T là điểm cực tiểu, I ( x∗ ) = {1, 2}. Ta có


−1
1
1
, ∇ g2 ( x ∗ ) =
.
∇ f ( x ∗ ) =  1  , ∇ g1 ( x ∗ ) =
1
−1
−

λ,µ

0.

Sử dụng hàm Lagrange: L( x, λ, µ) = f ( x) + λT h( x) + µT g( x).
Chúng ta có thể viết lại bài toán đối ngẫu như sau
inf L( x, λ, µ) .

max

x

λ,µ;µ 0

Định nghĩa 1.2. (Điều kiện đủ thứ hai). Giả sử f , h.g ∈ C2 . Những điều kiện sau
là đủ để điểm x∗ thỏa mãn (1) trở thành cực tiểu tương đối ngặt của bài toán trên
(a) Những ràng buộc ở định lý Karush - Kuhn - Tucker đáp ứng.
(b) Ma trận Hessian L( x∗ ) = F( x∗ ) + λT H ( x∗ ) + µT G( x∗ ) là xác định dương
trên không gian con
y : ∇ H ( x∗ ) T y = 0, ∇ g j ( x∗ ) T y = 0; ∀ j ∈ J ,
trong đó J = { j: g j ( x∗ ) = 0, µ j > 0} .
Định nghĩa 1.3. (Điều kiện cần thứ hai). Giả sử f , h.g ∈ C2 . Nếu x∗ là một điểm
chính quy cực tiểu tương đối của bài toán trên, khi đó tồn tại những vectơ λ và
µ ≥ 0 mà điều kiện (1.1) và µ j 0 được đáp ứng và ma trận Hessian L( x∗ ) =
F( x∗ ) + λT H ( x∗ ) + µT G( x∗ ) là xác định dương trên không gian tiếp xúc của
những ràng buộc tại x∗ .
Ví dụ 1.2. (Hàm đối ngẫu). Xét bài toán
min z = x12 + x2 , với
x1 ,x2


7
z∗ = 5, x1∗ = 2, x2∗ = 1, λ∗ = , µ∗ = .
4
4
Để thu được bài toán đối ngẫu đầu tiên chúng ta tính toán hàm đối ngẫu
Φ(λ, µ) = inf L( x, y, λ, µ) = inf x12 + x2 + λ(− x1 + 2x2 ) + µ(− x1 x2 + 2) .
x1 ,x2

x1 ,x2

Và khi

∂L( x1 , x2 , λ, µ)
= 2x1 − λ − µx2 = 0,
∂x1
∂L( x1 , x2 , λ, µ)
= 1 + 2λ − µx1 = 0.
∂x2

Dẫn đến
x=

1 + 2λ
2 + 4λ − λµ
,y =
.
µ
µ2

Hàm đối ngẫu trở thành

µ3
dẫn đến λ∗ = 74 , µ∗ = 49 , là nghiệm của bài toán đối ngẫu, và rõ ràng trùng
khớp với nghiệm thu được từ điều kiện KKT ở trên.
Định nghĩa 1.4. (Dưới gradient và dưới vi phân).
Cho C là một tập lồi không âm trong R n và cho Φ : C → R là lồi. Khi đó, α được
gọi là một dưới gradient của Φ(λ) tại λ ∈ C nếu
Φ(λ)

Φ(λ ) + αT (λ − λ ); ∀λ ∈ C.

Tương tự vậy, cho Φ : C → R là lõm. Khi đó, α được gọi là một dưới gradient của
λ ∈ C nếu
Φ(λ) Φ(λ ) + αT (λ − λ ); ∀λ ∈ C.
Tập tất cả các dưới gradient của Φ(λ) trong λ là một tập lồi được biết như dưới vi
phân của Φ(λ) tại λ.
Định lí 1.4. (Đối ngẫu yếu). Đối với bất kỳ nghiệm khả thi x của bài toán gốc và
bất kỳ nghiệm khả thi λ, µ của bài toán đối ngẫu, ta luôn có
f (x)

φ(λ, µ).

Định nghĩa 1.5. (Độ lệch đối ngẫu). Hiệu số giữa
sup{Φ(λ, µ)| µ

0} − inf{ f ( x)| h( x) = 0, g( x)

được gọi là độ lệch đối ngẫu của bài toán đối ngẫu và bài toán gốc.
Ví dụ 1.3. Xét bài toán sau đây
min −2x1 + x2 , với
x1 ,x2

5λ

−
nếu λ 2,
2

2,

biểu diễn trong hình vẽ. Nghiệm tối ưu của bài toán đối ngẫu là λ∗ = −1 với
giá trị hàm mục tiêu Φ(λ∗ ) = − 72 . Dễ dàng để thấy rằng x1∗ = 45 và x2∗ = 45 là
nghiệm tối ưu của bài toán gốc với một giá trị hàm mục tiêu bằng f ( x∗ ) =
− 45 .
Do đó, hiệu số f ( x∗ ) − Φ(λ∗ ) = − 54 + 27 = 49 là độ lệch đối ngẫu được biểu
diễn trong hình vẽ.

Hình 1.1: Đồ thị minh họa độ lệch đối ngẫu trong ví dụ minh họa 1.3.

Bây giờ để hiểu được về sự phân rã trong bài toán tối ưu ta xét ví dụ sau
Ví dụ 1.4. (Tính toán lưu vực sông). Xét một lưu vực sông bao gồm hai hồ
chứa như minh họa trong hình vẽ. Mỗi hồ chứa đã kết hợp một nhà máy thủy
điện sản xuất điện. Các dòng vào tự nhiên tới hồ 1 và 2 trong suốt khoảng
8


Hình 1.2: minh họa của ví dụ tính toán lưu vực sông.

thời gian t được định nghĩa tương ứng bằng wt1 và wt2 . Dung lượng nước
của hồ 1 và 2 tại thời điểm cuối của chu kỳ t được định nghĩa tương ứng bởi
rt1 và rt2 . Nước xả ra trong suốt khoảng thời gian t bởi hồ 1 và 2 tương ứng là
dt1 và dt2 . Các dung lượng được giới hạn trên và dưới tương ứng bởi những


r22 = r12 + w22 − d22 + d21 ,

r21 + r22 = r01 + r02 + w11 + w21 + w12 + w22 − d12 − d22 .

Trong đó ràng buộc cuối cùng là ràng buộc rườm rà mà nó thuận tiện để kết
hợp bởi vì nó diển tả một dạng ma trận thích hợp của bài toán; những ràng
buộc yêu cầu
k 1 d11 + k 2 d12 e1 ,
k 1 d21 + k 2 d22

e2 .

Những giới hạn cấp độ hồ
r1min

r11 , r21

r1max ; r2min

r12 , r22

r2max.

Và những giới hạn cho phép xả
0

d11 , d21

dmax



Chương 2

Phân rã trong quy hoạch tuyến tính
2.1 Những ràng buộc phức tạp
Kích thước của một bài toán quy hoạch tuyến tính có thể rất lớn. Người ta có
thể gặp phải trong thực tế những bài toán với hàng trăm hàng ngàn phương
trình hoặc ẩn số. Để giải quyết những bài toán này phải sử dụng một số kỹ
thuật đặc biệt cho thuận tiện và cần thiết. Ngoài ra, một giải pháp phân phối
của các bài toán lớn có thể được mong muốn vì lý do kỹ thuật hoặc thực tế.
Kỹ thuật phân rã cho phép loại nhất định của các bài toán được giải quyết
một cách phân cấp hoặc phân phối. Ngoài ra, chúng dẫn đến sự đơn giản
hóa thủ tục nghiệm của bài toán được nghiên cứu.
Đối với một kỹ thuật phân rã có ích , bài toán ở đây phải có cấu trúc thích
hợp. Hai trường hợp như vậy xảy ra trong thực tế: các ràng buộc phức tạp
và cấu trúc biến phức tạp. Hai trường hợp này được xem xét trong chương
này. Trong một bài toán quy hoạch tuyến tính, các ràng buộc phức tạp liên
quan đến các biến từ các khối khác nhau rõ ràng, ràng buộc phức tạp cản trở
một nghiệm của bài toán bằng các khối.

12


2.1.1

Cấu trúc bài toán

Xét bài toán quy hoạch tuyến tính
n


xj

Trong đó những ràng buộc (2.2) có một cấu trúc phân rã trong r khối, mỗi
khối có kích cỡ là nk (k = 1, . . . , r ), tức là chúng có thể được viết như sau
nk

∑
j = n k − 1 +1

eij x j = f i ; i = qk−1 + 1, . . . , qk .

Chú ý rằng n0 = q0 = 0, qr = q và nr = n.
Mặt khác, khi những ràng buộc (2.3) không có cấu trúc phân rã, chúng là
những ràng buộc phức tạp.
up

Chú ý rằng những cận trên x j ( j = 1, . . . , n) được xem xét cho tất cả các
biến tối ưu x j ( j = 1, . . . , n). Giả định này cho phép làm việc với một miền
khả thi compact (hữu hạn), dẫn đến một phân tích lý thuyết đơn giản của
bài toán (2.1) - (2.4). Giả định này là hợp lý bởi tính chất bị chặn của hầu hết
biến kỹ thuật.
Hình 2.1 cho thấy cấu trúc của bài toán nêu trên đối với trường hợp r = 3.

13


Cụ thể bài toán này có thể được viết như sau

min


Trong đó những chỉ số trong ngoặc đề cập đến những phân vùng, với




[ 1]
f
E [1 ] | |
 −−−−−−−−−−−−−   [1]   −− 
 x



  −−   [2] 

[ 2]
f
|
E
|



 
 −−−−−−−−−−−−−  

[ 2]  = 
−−


Hình 2.1: ma trận phân rã với những ràng buộc phức tạp

r

min

x [1] ,x [2] ,...,x [r ]

∑

c[ k]

k =1

14

T

x[k] , với


E[k] x[k] = f [k] ; k = 1, . . . , r;
r

∑ A[k] x[k] = b;
k =1

x [ k]

0

Nếu những ràng buộc phức tạp được bỏ qua, tức là chúng được giảm bớt
đi, bài toán gốc trở thành
r

Min

x [1] ,x [2] ,...,x [r ]

∑

c[k]

T

x [ k] ,

k =1

E[k] x[k] = f [k] ; k = 1, . . . , r;
0

x [ k]

x[k]up ; k = 1, . . . , r.

Bài toán này được gọi là phiên bản rút gọn của bài toán.
Do đó phân rã bài toán con thứ k là
min c[k]
x [k]



∑
j = n k − 1 +1

0

∑

cj xj;

j = n k − 1 +1

eij x j = f i ; i = qk−1 + 1, . . . , qk ;
up

x j ; j = nk−1 + 1, . . . , nk .

xj

Ví dụ 2.1. Bài toán với cấu trúc phân rã Xét bài toán
min

x1 ,x2 ,x3 ,y1 ,y2 ,y3 ,z1 ,z2 ,z3 ,w1

−4x1 − y1 − 6z1 , với

x1 − x2
x1

=1

x 1 , x 2 , x 3 , y 1 , y 2 , y 3 , z 1 , z 2 , z 3 , w1

0

có một cấu trúc phân rã trong ba khối, trong đó đẳng thức cuối cùng
3x1 + 2y1 + 4z1 + w1 = 17,
là ràng buộc phức tạp.
2.1.2

Sự phân rã

Giả sử rằng mỗi bài toán (bài toán giảm dư) được giải quyết p lần với hàm
mục tiêu khác nhau và tùy ý, và giả sử rằng p nghiệm chấp nhận được cơ

16


bản của bài toán giảm dư là
(1)

(1)

(1)

x1 , x2 . . . x n
.

. . .

( p)


( p)

( p)

( p)

r1 , r2 . . . r m ,
( s)

trong đó r j

là giá trị của ràng buộc phức tạp thứ i cho nghiệm thứ s, tức là
( s)
ri

n

=

( s)

∑ aij x j

.

j =1

Đối với mục dưới đây, cần nhấn mạnh rằng một sự kết hợp lồi tuyến tính
của các nghiệm cơ bản khả thi của một bài toán quy hoạch tuyến tính là một

p

∑ us = 1 : σ;
s =1

0; s = 1, . . . , p.

us

Trong đó những biến đối ngẫu λi và σ được chỉ định.
1. Mọi nghiệm của bài toán trên là sự kết hợp lồi của các nghiệm cơ bản
khả thi của bài toán giảm dư; do đó, nó chính là một nghiệm cơ bản khả thi
của bài toán giảm dư.
2. Ràng buộc phức tạp được thực thi; do đó, các nghiệm của bài toán trên
là một nghiệm cơ bản khả thi cho bài toán gốc (không giảm dư).
Hãy xem xét rằng một nghiệm cơ bản khả thi mới tiềm năng được thêm
vào bài toán nêu trên. Giá trị hàm mục tiêu của nghiệm này là z và những
giá trị ràng buộc phức tạp của nó là r1 , . . . , rm .
Bài toán trọng lượng mới trở thành
p

z(s) us + zu, với
∑
u1 ,...,u p ,u
min

s =1

p



n

z = ∑ cj xj,
j =1

trong đó x j ( j = 1, . . . , n) là nghiệm cơ bản khả thi tiềm năng mới, và
n

ri =

∑ aij x j .
j =1

Chi phí giảm biến trọng lượng u trở thành
n

m

n

j =1

i =1

j =1

∑ c j x j − ∑ λi ∑ aij x j

d=


∑
j =1

i =1

x j − σ, với

n

∑ eij x j = fi ;

i = 1, . . . , q;

j =1

0

up

xj

j = 1, . . . , n.

xj ;

Lưu ý rằng các ràng buộc của bài toán giảm dư phải được thêm vào.
Nếu hằng số σ được giảm từ hàm mục tiêu, bài toán trên trở thành
n