Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
NGUYỄN THỊ HIỂN
PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN QUY HOẠCH TOÀN
PHƯƠNG
Chuyên ngành: Toán Giải tích Mã số: 60 46 01 02
LUẬN VĂN THẠC Sĩ TOÁN HỌC
Người hướng dẫn khoa học: PGS. TS. Tạ Duy Phượng
HÀ NỘI, 2014
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của
thầy giáo PGS.TS. Tạ Duy Phượng. Sự hướng dẫn giúp đỡ rất tận tình, nghiêm túc của thầy
trong suốt quá trình thực hiện luận văn này đã giúp tác giả trưởng thành hơn rất nhiều trong
cách tiếp cận một vấn đề mới. Tác giả xin bày tỏ lòng biết ơn lòng kính trọng sâu sắc nhất
đối với thầy.
Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà Nội
1
2, phòng Sau đại học, các thầy cô giáo trong nhà trường và các thầy cô giáo dạy Cao học
chuyên ngành Toán giải tích đã giúp đỡ, tạo điều kiện thuận lợi cho tác giả trong suốt quá
trình học tập.
Tác giả xin cảm ơn Sở GD-ĐT tỉnh Vĩnh Phúc, Ban giám hiệu, các thầy cô đồng nghiệp
Trường trung học phổ thông Liên Bảo cùng gia đình, người thân, bạn bè đã giúp đỡ, động
viên và tạo điều kiện thuận lợi để tác giả hoàn thành khóa học Thạc sĩ và hoàn thành luận
văn này.
Hà Nội, ngày tháng 02 năm2014
Học viên
Nguyễn Thị Hiển
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của
PGS.TS. Tạ Duy Phượng.
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi.
Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa những thành quả khoa
học của các nhà khoa học và đồng nghiệp với sự trân trọng và biết ơn. Tôi xin cam đoan
những thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.

trình nghiên cứu lý thuyết và thực hành của Tối ưu hóa ngày càng mở rộng và
phát triển.
Ngày nay, đối với các kỹ sư và các nhà nghiên cứu khoa học, kỹ thuật, kinh tế,
công nghệ thông tin, sự hiểu biết về các phương pháp tối ưu cũng cần thiết như
các kiến thức cơ sở của Giải tích, Vật lý, Hóa học,
Bài toán quy hoạch toàn phương đã được nhiều người nghiên cứu, nhưng cho
đến nay nó vẫn là bài toán mang tính thời sự. Với mong muốn tìm hiểu sâu
hơn và nghiên cứu về phương pháp số giải bài toán quy hoạch toàn phương
nên tôi đã chọn đề tài:
“Phương pháp số giải bài toán quy hoạch toàn phương”
2. Mục đích nghiên cứu
Luận văn nghiên cứu một số phương pháp số giải bài toán quy hoạch toàn
phương, ứng dụng vào giải một số bài toán cụ thể.
3. Nhiệm yụ nghiên cứu
Nghiên cứu một số phương pháp số. Phân tích các ưu điểm, nhược điểm của
từng phương pháp. Nêu các ứng dụng của các phương pháp vào giải một số
bài toán cụ thể.
5
4. Đối tượng và phạm vi nghiên cứu
Phương pháp hạn chế tích cực.
Phương pháp hạn chế giả định.
Phương pháp Gradien đối ngẫu.
Phương pháp điểm trong.
5. Phương pháp nghiên cứu
Sử dụng các kiến thức và công cụ của Đại số tuyến tính, Giải tích, Giải tích
hàm, Lý thuyết tối ưu, Giải tích số và lập trình cho máy tính để tiếp cận và giải
quyết vấn đề.
Sưu tầm nghiên cứu các tài liệu liên quan, đặc biệt là các bài báo mới về vấn
đề mà luận văn đề cập tới.
Suy luận logic, phân tích, tổng hợp và hệ thống hóa các kiến thức về tối ưu.

TỐI ƯU.
Nếu hàm mục tiêu F(X) và các hàm ràng buộc g ; ( x ) đều là các hàm
tuyến tính và X = M
+
, ta có bài toán QUY HOẠCH TUYỂN TÍNH, ngược lại là
các bài toán QUY HOẠCH PHI TUYỂN. Nếu X là tập hợp rời rạc ta có bài toán
QUY HOẠCH RỜI RẠC.
Trong các bài toán quy hoạch phi tuyến thì bài toán quy hoạch toàn phương đã
được nghiên cứu đầy đủ nhất. Luận văn của tôi tập trung nghiên cứu: BÀI
TOÁN QUY HOẠCH TOÀN PHƯƠNG là bài toán với hàm mục tiêu là một dạng
toàn
phương /(*) = —(.X, À*)+ (c,.x) + a, trong đó A là ma trận xác định dương,
A là hằng số, còn các hàm ràng buộc g.(x),/ỉ.(x),Ịỉ' = \,RÌ\,J = L,M
2
J đều là
các hàm tuyến tính. Đối vói quy hoạch toàn phương đã có những thuật toán rất
nổi tiếng của Beale, Frank-Wolfe,
Bài toán quy hoạch toàn phương được xét ở đây là trường hợp đặc biệt của bài
toán quy hoạch lồi.
Bài toán quy hoạch lồi là bài toán:
F(X) —»min
8
với các điêu kiện:
trong đó các hàm F{X),GỊ (*),(ỉ = 1,/ra) đều là các hàm lồi và tập X là tập lồi.
Bài toán quy hoạch lồi cũng đã được nhiều nhà toán học nghiên cứu và đề ra
các thuật toán hữu hiệu. Tuy nhiên đến nay vẫn còn rất nhiều vấn đề cần được
nghiên cứu tiếp.
1.2Một sổ khái niệm cơ bản
1.2.1 Hàm toàn phưomg
Hàm / : R" —>■ R gọi là hàm toàn phương nếu có dạng

*
Ể
+a,
Minimize/ (*) := —X
T
DX + C
T
X,
s.t. xeK",Ax>Z7, trong đó D là ma trận đối xứng
(không nhất thiết là xác định dương).
Kí hiệu:
À = |jceM": Ax>b}, ỡ
=inf |/(jc): jceA|.
Qui ước: Nếu À = 0 thì đặt 0 - +00.
Neu À ^ 0 thì có hai trường hợp xảy ra:
• 6 e R là một số thực ỊD > -ao).
• 0 - -00 thì bài toán (P) không có nghiệm.
Câu hỏi 1 Khi 0 ^ —00 thì tồn tại hay không một điểm X € À để hàm số đạt giá
trị cực tiểu, tức là tồn tại hay không một điểm Ĩ6À sao cho F(X) = MIA{F(X))L
Nhận xét Nếu / (x) không phải là hàm toàn phương và À không phải là tập
compact thì điểm tối ưu X E À có thể không tồn tại.
Ví dụ: = —, jteR
+
,jt>l.
X
Ta thấy inf Ị/ (*): X > lj = 0 nhưng không tồn tại X để / (*) = 0.
Định lí 1.1 (Frank-Wolfe, 1956) Nếu 9 = inf {/(*): X € aỊ là hữu hạn thì bài toán
(P) có nghiệm, tức là tằn tại ĨGÁ để f{x) = 0.
Chúng minh Xem, thí dụ, [1], trang 30-35.
Ý nghĩa Nếu / (*) bị chặn dưới trên tập A thì bài toán (P) có nghiệm.

Ỉ
X
2
Y >0,A: = (^,A:
2
)
R
EM
2
. Đặt A = |a: = (j[:
1
,J[:
2
)gM
2
: X
L
>0,.x
2
>oỊ.
Câu hỏi 2 Khi nào /(x)bị chặn dưới trên trên tập À?
Định lí 1.2 (Eaves, 1971) Bài toán (P) có nghiệm khỉ và chỉ khi ba điều kiện
sau được thỏa mãn:
1. A*0
2. Nếu V € R", Av > 0 thì v
T
Dv > 0.
3. Nếu V € M", xeR
n
sao cho Av > 0 ,V

T
DV > 0 với mọi V G R" mà AV > 0. Bây giờ giả sử V
T
DV - 0 với
mọi veR",JceR" mà AV>0,AX>B.
Khi ấy vì JceA nên X + TV eA,Ví >0, suy ra F(X + TV)> /(x),Ví >0, hay
1 T
—(л + ív) D(x + tv) + c
T
(x + tv)>>0,
tức là
—x
T
Dx + —t
2
v
T
Dv + tx
T
Dv + с
т
X + tc
T
V >/(^),Ví> 0.
Do V
T
DV - 0 nên biểu thức trên trở thành
1 _ T .
—x
T

v
r
Dv<0,Vv€R".
Theo điều kiện 2 của Định lí Eaves (Định lí 1.2) thì từ V € R", AV > 0, suy ra
V
T
DV > 0. Chứng tỏ V
T
DV = 0.
Mặt khác, từ điều kiện AV > 0 suy ra V
T
DV - 0. Do đó kết luận cuối cùng của Hệ
quả 1.2 được suy ra từ kết luận 3 của Định lí 1.2.
Hệ quả 1.3 Giả sử D là ma trận đối xứng xác định dương. Khi ấy (P) có nghiệm
khi và chỉ khi À ^ 0.
Chúng minh Do D là ma trận xác định dương nên từ V
T
DV = 0 suy ra V = 0,
chứng tỏ (DX + CỴ V = 0. Kết họfp với Hệ quả 1.1 ta có điều phải chứng minh.
Hệ quả 1.4 Giả sử D là ma trận đối xứng xác định âm. Khi ấy (P) có nghiệm khi
và chỉ khi À khác rỗng và compact.
CHỨNG MINH Do D là ma trận đối xứng nửa xác định âm nên điều kiện (ii),
(iii) của Hệ quả 1.2 được thỏa mãn khi và chỉ khi tập L := Ịv € M": AV > o|
chứa một phần tử v = 0. Vì L là nón lùi xa của tập đa diện lồi À = Ịje e M": Ax
> &| nên điều kiện L = Ịo} tương đương với tính compact của A. Do đó ta
khẳng định được Hệ quả 1.4 từ Hệ quả 1.2.
Hệ QUẢ 1.5 Giả sử D là ma trận đối xứng. Khi ấy bài toán
min ị— X
T
DX + C

,B =
,0,
Chúng minh Đặt A - thì (Pl) trở thành
(P2
3. Nếu veM",JC€l" sao cho Av > 0,Cv - 0,v
T
Dv - 0,ẨJC >b và Cx — d thì (Dx
+ cỴ v> 0.
Chứng minh Đặt
Khi đó bài toán (P2) có thể viết lại thành
min Ị— x
T
Dx + C
T
X: X € M", Ax > bị.
Áp dụng Định lí 1.2 suy ra điều phải chứng minh.
1.3Các điều kiện cực trị
1.3.1 Điều kiện cực trị cấp 1
Định lí 1.3 Giả sử X là nghiệm của bài toán sau
đây: min Ị/ (*) = —x
T
Dx + C
T
X: X e Aị,,
trong đó D là ma trận đối xứng, À cz M" là đa diện lồi.
i) Neu X là nghiệm của bài toán (1.1) thì
(Dx + c,x-x}> 0,Vjt€ A.
ii) Nếu
(Dx + c,x - *) > 0, Vx € À \ ì*} , thì
X

(Ả
1
, ,Ẳ
n
Ỵ eM
m
sao cho:
Dx - A
T
Ẳ + с = 0
< Ах-Ъ> ОД > о (1.5)
Ả
T
(Ax-b) = Q
Chúng minh Kí hiệu AỊ là dòng thứ I của A, và tập ÃỊ = AỊ, BỊ là thành phàn thứ I
của vectơ B. Kí hiệu tập А = Ịjc e M" : AX > .
Giả sử X là một nghiệm địa phuofng của (P). Theo Định lí 1.3 (i), ta có tính chất
(1.2).
Kí hiệu tập I = = ịie I :(a
i
,x) = b
i
} và /j = Ị ỉ' e I :[a
i
,x)>b
i
Giả sử vel" thỏa mãn (ữ.,v) >0,Vỉ'e/
0
.
Tưofng tự như chứng minh Định lí 1.3 (ii), tồn tại S

Dx + с
т
X : X € R”, Ax > b, X > o|
thì tồn tại Ả € M" sao cho
Dx - A
T
Ẳ + с > 0 < Ах-Ь>0,х >0Д>0 (1.6)
X (DX - A
T
Ẵ + c"j + Ẵ
T
(Ах - b) = 0.
HỆ QUẢ 1.8 Neu je e M" là nghiệm địa phương của bài toán (P2)
min ị— X
T
DX + С
Т
X : X € R", AX > B, CX = í/|
ứiì tồn tại Ắ G M" và /íeK" sao cho
Dx - A
T
Ẳ - с
т
/л + с = 0
< Ах -Ь>0,х >0Д >0 Ẳ
T

(Ах -b^ = о
1.3.2 Điều kiện cực trị cấp hai
Định lí 1.5 (Majthay 1971, Contese 1980 ) Điều kiện cần và đủ để ĩel" là nghiệm

nếu hai điều kiện sau được thỏa mãn: i) (V/(^),v} = (D^ +
c)>0,Vver
A
(^),
trong đó
T
A (*) = {v e M”: AJV > 0,CV = o},/
0
= {i ■.A
I
X=B
I
)
iĩ) v
T
Dv > 0 với mọi ve T
ầ
(!x)
n (v/ (^))
x
,
trong đó
V/(ĩ)
1
= {veE":(V/(ĩ),v) = o}.
Chứng minh Xem [1], trang 52.
Định lí 1.7 (Mangasarian 1980, Contesse 1980) ĐIỂM X e R" LÀ NGHIỆM ĐỊA
phương của bài toán (P2) khi và chỉ khi tồn tại e M
m
X R* sao cho

>
TRONG ĐỎ
T
Ă
(x) = {v e R": A
Ig
>0,Cv = 0ị,ĩ
0
= ịi :A
I
X=B
I
}
ii) v
T
Dv > 0,Vv G r
A
(!x) n (v/(^))
X
,
trong đỏ
V/(Ĩ)
1
= {VEK”:(V/(Ĩ),V) = OỊ.
Chứng minh Xem [1], trang 60 - 61.
Định lí 1.9 Nếu ĩeR" là nghiệm địa phương duy nhất của bài toán (P2) thì
tồn tại £ >0,p>0 sao cho /(*)-/(*)>p||;t-Ã:||
2
,V.X€ Afì#(*",£) , trong ĐÓ
A = Ị* € R”: Ax > b, Cx =

>0, i € /.
2.1.2 Tối ưu hàm toàn phương trên đa tạp affine. Phương pháp phân rã
vuông góc
Xét bài toán
min f(x) = — ^Dx + C
T
X,
Ax = b,
trong đó
DeR
nx
, AeM"”, m<n, jc.ceR", beR
m
.
ĐỊNH NGHĨA Tập M được gọi là ĐA TẠP AFFINE nếu với mọi X
L
,X
2
EM thì aXj
+ SSX
2
e M với mọiA,SS e M.
Ta có điều kiệncực trị sau cho bài toán (EP):
xeR" là nghiệm của bài toán (EP) khỉ và chỉ khỉ tồn tại X G R
m
sao cho
Dx + c- A
T
X - 0, (2.1)
Ax=b (2.2)

2
tạo thành cơ sở của không gian nhân của A,
N ( A ) :={jeeM":Aje = o}
có số chiều là N-M.
Giả sử JC° =Q
1
(R
T
Y
Ỉ
B thì
Ajc° = (Q
X
R)
T
Q
x
(R
T
r
l
b = R
T
QĨ ổ! (R
T
y
l
b = b.
Giả xử X là điểm chấp nhận được của bài toán (EP), tức là AX = B. Khi ấy A(X -
л:

nghiệm của bài toán (P) khi và chỉ khi Z là nghiệm của hệ tuyến tính
v/(z ) = 0Qĩ DQ
2
)Z + Qĩ (Dx° + c) = 0.
Do đó
(.QÎDQ
2
)z=-QUDx° + C). (2.3)
Q
T
Q = i
n
, QĨQi=i
m
, QĨQ
2
= i
m
-n’ QĨQ
2
=0.
Suy
(P
= x(*
u
+ Q2Z)
T
D(X° + Q
2
z) + C

k
=b ị , i& A
k
\
aỊx
k
>b ị iiA
k
.
Ở đây A
K
là tập các hạn chế tích cực,
A
k
—E\jịiel :afx
k
—bịỴ
Cùng với bài toán (EP)
min f(x) = — x^Dx + C
T
X,
ta xét bài toán (EP )
aỊx>
b, a Ị
(EP
I

€
/; I
min—s

-
'
Z
^
í
k
a
i
=

0
ieA
k
afs
k
= 0, ieA
k
trong đó ẲF,I € A
K
là
các nhân tử Lagrange
ứng với S
K
. Từ (2.4) và
(2.5) ta suy ra:
D(x
k
+S
k
) + C-