LỜI MỞ ĐẦU
1. Giới thiệu bài toán tối ưu đa mục tiêu
Trong những năm 50 của thế kỷ 20, Quy hoạch đa mục tiêu, hay còn được gọi là Tối
ưu đa mục tiêu hoặc Tối ưu véc tơ, đã trở thành một chuyên ngành toán học, thu hút
sự quan tâm của nhiều tác giả và được phát triển mạnh mẽ suốt gần 70 năm qua. Các
thành tựu của Quy hoạch đa mục tiêu được ứng dụng rộng rãi trong thực tế, đặc biệt
là trong lý thuyết ra quyết định, kinh tế, tài chính, kỹ thuật, viễn thông,... (xem [23],
[64], [83], [93], [94],...). Bài toán quy hoạch đa mục tiêu được phát biểu dưới dạng
Min f (x) = ( f1 (x), f2 (x), . . . , f p (x))

với điều kiện

x ∈ X,

(MOP)

trong đó X ⊂ Rn là tập các phương án chấp nhận được, f j : X → R, j = 1, . . . , p,
p ≥ 2, là các hàm mục tiêu. Do không gian giá trị R p không có thứ tự đầy đủ nên
thay vì khái niệm nghiệm tối ưu thông thường, tối ưu véc tơ sử dụng khái niệm
nghiệm hữu hiệu được xác định theo thứ tự từng phần do G. Cantor (1845-1918) [21]
và F. Hausdorff (1868-1942) [37] đề xuất.
Bài toán (MOP) được gọi là bài toán quy hoạch đa mục tiêu lồi, ký hiệu là
(CMOP), nếu X là tập lồi và f1 , . . . , f p là các hàm lồi. Đây là trường hợp đặc biệt của
bài toán quy hoạch đa mục tiêu lồi suy rộng, ký hiệu là (GMOP), trong đó f1 , . . . , f p
là các hàm lồi suy rộng và tập chấp nhận được X cũng là tập lồi. Nếu tất cả các hàm
f1 , . . . , f p đều là hàm tuyến tính và X là tập lồi đa diện thì ta gọi (MOP) là bài toán
quy hoạch đa mục tiêu tuyến tính và ký hiệu là (LMOP). Như đã biết, (LMOP) là
trường hợp đơn giản nhất của bài toán (MOP) nói chung và (CMOP) nói riêng.
Theo tiếp cận trên không gian quyết định (decision space), việc giải bài toán
(MOP) được xem như việc xác định toàn bộ hay một phần của tập nghiệm hữu hiệu
XE hoặc tập nghiệm hữu hiệu yếu XW E . Đây là một việc khó, vì ngay cả trong trường

and C. Malivert [7], R.E. Steuer [83], J.P. Dauer và Y.H. Liu [27], H.P. Benson [11],
N.T.B. Kim và D.T. Lục [44], [45], M. Ehrgott, A. L¨ohne và L. Shao [29],...
Với bài toán quy hoạch đa mục tiêu lồi và không lồi, đã có một số thuật toán được
đề xuất. Hầu hết các thuật toán theo tiếp cận trên không gian quyết định được thiết
kế dựa trên các phương pháp trọng số [25], phương pháp ε−ràng buộc [36], phương
pháp hàm lợi ích [93], phương pháp lexicographic [20], phương pháp Tchebycheff
[83],... để sinh một phần tập nghiệm hữu hiệu hay hữu hiệu yếu của bài toán. Theo
tiếp cận trên không gian ảnh, các thuật toán thường sử dụng kỹ thuật xấp xỉ ngoài để
xây dựng một dãy các tập xấp xỉ tập ảnh, trong đó ta có thể dễ dàng xác định được
tập hữu hiệu các tập xấp xỉ này. Với cách tiếp cận này, một mặt, thuật toán sinh ra
một phần của tập ảnh hữu hiệu của bài toán, mặt khác, nó sinh ra tập xấp xỉ của tập
ảnh hữu hiệu chứa toàn bộ tập ảnh hữu hiệu (xem [30], [34], [62] và danh mục tài
liệu tham khảo kèm theo). Trong [65], K. Miettinen đã phân loại chi tiết và so sánh
các phương pháp hiện có để giải các bài toán quy hoạch đa mục tiêu phi tuyến. Các
phương pháp để sinh ra tập xấp xỉ của tập nghiệm hữu hiệu và tập ảnh hữu hiệu được
thống kê trong [78].
Hai bài toán tối ưu toàn cục quan trọng có liên quan chặt chẽ đến bài toán quy
hoạch đa mục tiêu là bài toán tối ưu một hàm thực trên tập nghiệm hữu hiệu của bài
toán quy hoạch đa mục tiêu (gọi tắt là Bài toán tối ưu trên tập nghiệm hữu hiệu) và
bài toán quy hoạch tích cũng như các dạng mở rộng của nó.
Bài toán tối ưu trên tập nghiệm hữu hiệu có mô hình toán học như sau
min h(x) v.đ.k. x ∈ XE ,

(P)

trong đó h(x) là một hàm số thực xác định trên Rn và XE là tập nghiệm của bài toán
quy hoạch đa mục tiêu (MOP). Việc giải bài toán này có ý nghĩa đặc biệt vì nó giúp
ta chọn được nghiệm hữu hiệu tốt nhất theo một tiêu chuẩn nào đó mà không nhất
1 Từ



min ∏ f j (x),

(MP)

j=1

trong đó f j , j = 1, . . . , p, p ≥ 2, là các hàm số thực xác định trên X ⊂ Rn . Tương tự
như cách phân loại các bài toán quy hoạch đa mục tiêu, nếu X là tập lồi đóng và các
hàm f1 , . . . , f p là các hàm lồi trên X thì (MP) được gọi là bài toán quy hoạch tích
lồi, ký hiệu là (CMP). Bài toán (MP) được gọi là bài toán quy hoạch tích tuyến tính,
ký hiệu là (LMP), khi f1 , . . . , f p là các hàm tuyến tính và X là tập lồi đa diện. Trong
[63], T. Matsui đã chỉ ra rằng, ngay cả trường hợp đơn giản nhất của bài toán (MP),
tức là bài toán (LMP) với p = 2 và X là đa diện khác rỗng, cũng thuộc lớp bài toán
NP−khó. Hiện nay đã có nhiều thuật toán được đề xuất để giải bài toán quy hoạch
tích tuyến tính (LMP) (xem H. Konno và T. Kuno [52], S. Schaible và C. Sodini
[80], H.P. Benson và G.M. Boger [17], T. Kuno [53], N.T.B. Kim [43], N.T.B. Kim,
T.T.H. Yên và N.T.L. Trang [48], L. Shao và M. Ehrgott [82],...) và quy hoạch tích lồi
(CMP) (xem N.V. Thoại [86], T. Kuno, Y. Yajima, và H. Konno [54], H.P. Benson
[12], R.M. Oliveira, và P.A.V. Ferreira [71], N.T.B. Kim, N.C. Nam, L.Q. Thủy [46],
L. Shao và M. Ehrgott [81],...). Theo hiểu biết của tác giả, mặc dù có nhiều ứng dụng
thực tiễn nhưng có rất ít công trình nghiên cứu bài toán quy hoạch tích mở rộng.
3


2. Mục đích nghiên cứu và ý nghĩa của đề tài
Như đã trình bày, mặc dù bài toán quy hoạch đa mục tiêu lồi và các vấn đề liên quan
đã được nghiên cứu tương đối hoàn chỉnh nhưng cho đến nay vẫn còn rất ít thuật toán
giải bài toán tối ưu đa mục tiêu lồi suy rộng [92]. Hơn nữa, do nhu cầu ứng dụng,
việc nghiên cứu xây dựng các thuật toán hiệu quả để giải bài toán quy hoạch đa mục


max Φ(x) = f0 (x) + ∏ fi (x) v.đ.k. x ∈ X,

(GIMP)

i=1

trong đó X ⊂ Rn là tập lồi compact khác rỗng và f j , j = 0, 1, . . . , k, là các hàm lõm
nhận giá trị dương trên X. Bài toán quy hoạch tích mở rộng liên quan gần gũi nhất
với bài toán (GIMP) đã được nghiên cứu trong [41]. Trong trường hợp đặc biệt, khi
k = 2, đã có một số thuật toán hữu hiệu được đề xuất để giải bài toán (GIMP) (xem
[6], [14], [68],...). Theo hiểu biết của chúng tôi, cho đến nay, hầu như chưa có thuật
toán nào được đề xuất để giải bài toán (GIMP) trong trường hợp tổng quát.
4. Hai bài toán tối ưu trên tập nghiệm hữu hiệu XE của bài toán quy hoạch hai mục
tiêu lồi. Đó là bài toán
min h(x) = ϕ( f (x)) v.đ.k. x ∈ XE ,

(QP)

trong đó ϕ : R2 → R là hàm tựa lõm trên tập ảnh Y và bài toán
max h(x) = ϕ( f (x)) v.đ.k. x ∈ XE ,

(DP)

với ϕ : R2 → R là hàm đơn điệu tăng trên tập ảnh Y . Dạng hàm mục tiêu h(x) =
ϕ( f (x)) với hàm số thực ϕ : Y → R xuất hiện nhiều trong các bài toán nảy sinh từ
thực tế và cũng đã được nhiều tác giả quan tâm nghiên cứu, chẳng hạn [47], [87],
[88], [91] và danh sách tài liệu tham khảo kèm theo.
4


thuật toán theo tiếp cận trên không gian ảnh để giải hai bài toán quy hoạch tích: Bài
toán quy hoạch tích lồi suy rộng (GMP) và Bài toán quy hoạch tích lõm mở rộng
(GIMP). Thuật toán giải bài toán (GMP) được thiết lập dựa trên mối quan hệ của
bài toán (GMP) và bài toán (GMOP) tương ứng với nó, và cũng được xem như là
một ứng dụng của thuật toán giải bài toán (GMOP) đã thiết lập ở Chương 2. Bằng
các biến đổi thích hợp, việc giải bài toán (GIMP) được đưa về việc giải bài toán cực
đại một hàm đơn điệu tăng trên tập các điểm hữu hiệu của một tập lồi đóng trong R2 .
Các tính toán thử nghiệm chứng tỏ thuật toán đề xuất là hiệu quả.
Chương 4. “Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu” đề xuất các
thuật toán trên không gian ảnh để giải hai bài toán (QP) và (DP). Bằng cách biến đổi
các bài toán gốc về bài toán tương đương trên không gian ảnh và tận dụng cấu trúc
đặc biệt của tập ảnh hữu hiệu và tính chất đặc thù của các hàm mục tiêu, chương này
đề xuất một thuật toán nhánh cận giải bài toán (QP) và một thuật toán nhánh cận kết
hợp với lược đồ xấp xỉ ngoài giải bài toán (DP).
Việc đánh số của các chương, mục, định lý,... trong bản tóm tắt này được giữ nguyên
như ở trong luận án.
5


Chương 1
BÀI TOÁN QUY HOẠCH ĐA MỤC TIÊU LỒI SUY RỘNG
Tất cả các bài toán được nghiên cứu trong luận án này đều liên quan gần gũi đến
bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) và trường hợp riêng của nó là
bài toán quy hoạch đa mục tiêu lồi (CMOP). Chương này giới thiệu mô hình toán
học của bài toán (GMOP) cùng một số khái niệm và kết quả cơ bản liên quan.
1.1 Hàm lồi suy rộng
Cho tập lồi khác rỗng S ⊆ Rn . Hàm số h xác định trên tập mở chứa S được gọi là
hàm giả lồi (pseudoconvex) trên S (xem [66, tr. 141]) nếu h khả vi trên S và
∇h(x2 ), x1 − x2 ≥ 0 ⇒ h(x1 ) − h(x2 ) ≥ 0,


S. Giả sử điều kiện Slater được thỏa mãn, tức
∃ x∗ ∈ S : gi (x∗ ) < 0 với mọi i = 1, . . . , m.
¯ , sao cho
Khi đó, x¯ ∈ Argmin(SOP) khi và chỉ khi tồn tại một véc tơ u¯ ∈ R|I(x)|

∇h(x)
¯ +

∑

u¯ j ∇g j (x)
¯ = 0,

j∈I(x)
¯

6

g(x)
¯ ≤ 0,

u¯ ≥ 0.


1.2 Điểm hữu hiệu và hướng pháp tuyến
p
và
Như thường lệ, với hai điểm bất kỳ a, b ∈ R p , ta viết a ≥ b nếu a − b ∈ R+
p
a > b nếu a − b ∈ intR+ . Cho tập khác rỗng Q ⊂ R p . Ký hiệu MinQ và MaxQ lần

Cho một tập đóng khác rỗng Q ⊂ R p và một điểm q∗ ∈ Q. Véc tơ v ∈ R p được
gọi là một hướng pháp tuyến (trong) của Q tại q∗ nếu v, q − q∗ ≥ 0 với mọi q ∈ Q.
Tập tất cả các hướng pháp tuyến của Q tại q∗ được gọi là nón pháp tuyến của tập Q
tại q∗ và ký hiệu là NQ (q∗ ) (xem [77, Định nghĩa 6.3, tr. 199]).
Định nghĩa 1.2. Cho v ∈ NQ (q∗ ) ⊂ R p . Khi đó, v được gọi là hướng pháp tuyến
p
p
dương nếu v ∈ intR+
và ta gọi v là hướng pháp tuyến không âm nếu v ∈ R+
\ {0}.
Định lý 1.5. (xem [57, Định lý 2.10, Định lý 2.11, tr. 91]) Cho tập lồi khác rỗng
Q ⊂ R p . Nếu tồn tại một hướng pháp tuyến dương của Q tại q∗ ∈ Q thì q∗ ∈ MinQ;
Điểm q∗ ∈ WMinQ khi và chỉ khi tồn tại hướng pháp tuyến không âm của Q tại q∗ .
Mệnh đề 1.6. (Xem [58, Mệnh đề 5.24]) Nếu Q ⊂ R p là đóng thì WMinQ là tập
đóng. Nếu Q là compact thì WMinQ là tập compact.
Định lý 1.6. (Xem [40, Định lý 1.2] và [74, Định lý 3]) Cho Q ⊂ R2 lồi đóng khác
rỗng và MinQ = 0.
/ Khi đó, MinQ đồng phôi với một đoạn đóng khác rỗng trong R.
Xét một tập đóng khác rỗng Q ⊂ R p . Ký hiệu
p
Q+ = Q + R +
,

p
Q− = Q − R +
.

7

(1.2)

) \ Q+ . Khi
đó, bài toán

min t

v.đ.k. yO + t(v − yO ) ∈ Q+

(P(v))

có một nghiệm duy nhất, ký hiệu là t¯. Hơn nữa, điểm y¯ = yO + t¯(v − yO ) ∈ WMinQ+ .
Kết quả sau mô tả mối quan hệ giữa NQ+ (y)
¯ và NQ (q)
¯ trong đó y¯ ∈ WMinQ+ và
q¯ ∈ WMinQ.
¯ Khi đó, q¯ ∈ WMinQ và
Mệnh đề 1.10. Cho y¯ ∈ WMinQ+ và q¯ ∈ Q với y¯ ≥ q.
p
p
NQ+ (y)
¯ ∩ R+
= NQ (q)
¯ ∩ λ ∈ R+
: λ , y¯ − q¯ = 0 .

Định lý 1.7. (Xem [58, Định lý 5.14, Định lý 5.15]) Cho tập compact khác rỗng
Q ⊂ R p thỏa mãn Q+ là tập lồi. Khi đó, tập điểm hữu hiệu MinQ là liên thông và
tập điểm hữu hiệu yếu WMinQ là tập liên thông đường.
1.3 Bài toán quy hoạch đa mục tiêu lồi suy rộng
Chương 2 của luận án xét bài toán quy hoạch đa mục tiêu lồi suy rộng
Min f (x) = ( f1 (x), f2 (x), ..., f p (x))T


Chương 2
THUẬT TOÁN HƯỚNG PHÁP TUYẾN GIẢI BÀI TOÁN
QUY HOẠCH ĐA MỤC TIÊU LỒI SUY RỘNG
Xét bài toán quy hoạch đa mục tiêu lồi suy rộng
Min f (x) v.đ.k.

x ∈ X,

(GMOP)

trong đó X = {x ∈ Rn : g(x) ≤ 0} là tập lồi compact khác rỗng, g : Rn → Rm là hàm
véc tơ tựa lồi, khả vi liên tục trên Rn , hàm véc tơ f : X → R p là giả lồi vô hướng trên
X và điều kiện Slater được thỏa mãn, tức tồn tại x∗ ∈ X sao cho g(x∗ ) < 0.
Tương tự lược đồ chung của các thuật toán xấp xỉ ngoài trên không gian ảnh,
thuật toán nón pháp tuyến Solve(GMOP) giải bài toán (GMOP) sinh ra một dãy các
đa diện {Bk } lồng nhau thỏa mãn B0 ⊃ B1 ⊃ · · · ⊃ Bk ⊃ · · · ⊃ Y ⊃ Y, trong đó,
Y ⊂ R p là một tập lồi compact khác rỗng và WMinY ∩Y = WMinY. Đa diện Bk+1
được xác định bởi Bk+1 = y ∈ Bk | λ k , y ≥ λ k , yk , trong đó yk ∈ WMinY và
λ k ∈ NY (yk ). Đó cũng là lý do cho tên gọi thuật toán hướng pháp tuyến trên không
gian ảnh. Khi thuật toán kết thúc, ta nhận được một phần tập WMin(Y, θ ) chứa toàn
bộ tập WMinY và một phần tập XW E,θ chứa toàn bộ tập XW E , trong đó θ = εe với
e = (1, . . . , 1) ∈ R p và ε ≥ 0 là sai số cho trước. Đặc biệt, nếu bài toán (GMOP) là
một bài toán quy hoạch đa mục tiêu tuyến tính thì sau hữu hạn bước lặp, với ε = 0,
ta nhận được tập YW E và tập XW E .
2.1 Xác định điểm ảnh hữu hiệu yếu và hướng pháp tuyến
Xác định hai điểm lý tưởng ym và yM của tập Y . Chọn yO , b, d ∈ R p sao cho
yO < b < ym ≤ yM < d
9



v.đ.k. g(x) ≤ 0.

(P2 (vk ))

Đây là bài toán cực tiểu một hàm giả lồi trên tập lồi. Vì vậy, bài toán (P2 (vk )) có thể
giải được bằng các thuật toán của quy hoạch lồi.
Định lý 2.1. Cho wk ∈ WMinY + và xk là nghiệm hữu hiệu yếu của bài toán (GMOP)
p
thỏa mãn f (xk ) ≤ wk . Khi đó, véc tơ khác không λ k thuộc NY + (wk ) ∩ R+
khi và chỉ
k
khi tồn tại một véc tơ µ k ∈ R|I(x )| sao cho (λ k , µ k ) là một nghiệm của hệ
 p
k
k

∑i=1 λi ∇ fi (x ) + ∑ j∈I(xk ) µ j ∇g j (x ) = 0
p
k
k
=0
∑i=1 λi wi − fi (x )


p
λ ≥ 0, µ ≥ 0, ∑i=1 λi
= 1.

(2.2)

và xác định tập đỉnh V k+1 ;

Giả sử thuật toán dừng tại Bước lặp k. Khi đó, thuật toán sinh ra tập EO và EY . Đặt
p
p
Y in : = (convEY + R+
) ∩ (d − R+
),
p
p
Y out : = (convEO + R+
) ∩ (d − R+
) ≡ Bk .

Định lý 2.3 chỉ ra rằng Y in và Y out tương ứng là các tập xấp xỉ trong và tập xấp xỉ
ngoài của Y . Hơn nữa, tất cả các điểm hữu hiệu yếu của Y in đều là điểm hữu hiệu
yếu θ −xấp xỉ của Y , tức WMinY in ⊆ WMin(Y , θ ), và tất cả các điểm hữu hiệu
yếu của Y out đều là điểm hữu hiệu yếu θ −xấp xỉ ngoài của Y tức WMinY out + θ ⊆
WMin(Y , θ ). Dựa trên tập Y out , ta thiết lập được tập xấp xỉ ngoài EX của tập
nghiệm hữu hiệu yếu XW E của bài toán (GMOP). Cụ thể là EX = y∈WMin(Y
out ,θ ) {x ∈
¯
X | f (x) ≤ y}.
¯ Hơn nữa, EX bao gồm các nghiệm hữu hiệu yếu θ - xấp xỉ của bài
toán (GMOP) và cũng chứa toàn bộ tập nghiệm hữu hiệu yếu XW E (Hệ quả 2.1).
2.3 Sự hội tụ của thuật toán
Kết quả sau chỉ ra rằng các đa diện Bk , k = 0, 1, . . . , được xây dựng trong thuật
toán là các xấp xỉ ngoài của tập Y vã dãy {Bk } hội tụ tới Y .
Định lý 2.2. Với một sai số ε ≥ 0 cho trước, các tập Bk , k ≥ 0, được xây dựng trong
thuật toán thỏa mãn Y ⊆ Bk+1 ⊆ Bk . Hơn nữa, với ε = 0, các khẳng định sau đúng:


mục tiêu tuyến tính thì thuật toán dừng sau một số hữu hạn bước ngay cả khi ε = 0,
và khi đó XW E ≡ EX ≡ XW E,θ .
2.4 Tính toán thử nghiệm
Việc tính toán thử nghiệm thuật toán Solve(GMOP) được thực hiện trên máy
laptop HP Pavilion 1.8Ghz, RAM 2GB sử dụng mã nguồn được viết trên ngôn ngữ
Matlab 2009a. Ví dụ 2.1 và Ví dụ 2.2 cho thấy với ε = 0, thuật toán giải bài toán quy
hoạch đa mục tiêu tuyến tính kết thúc sau hữu hạn bước lặp và nhận được chính xác
tập WMinY và XW E . Để tiện kiểm định, kết quả tính toán giải bài toán (GMOP) bằng
thuật toán Solve(GMOP) được so sánh với một số kết quả đã công bố. Các bài toán
trong các Ví dụ 2.3, 2.4 và 2.6 được lấy trong [28], [61], [30] tương ứng. Ví dụ 2.5
là một thử nghiệm của thuật toán Solve(GMOP) cho bài toán (GMOP) trong trường
hợp f là không lồi và X là đa diện khác rỗng. Kết quả tính toán của Ví dụ 2.7 và 2.8
với dữ liệu đầu vào được sinh ngẫu nhiên đã chứng tỏ tính hiệu quả của thuật toán.
Chương 3
THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN QUY HOẠCH TÍCH MỞ RỘNG
3.1 Thuật toán giải bài toán quy hoạch tích lồi suy rộng
Xét bài toán quy hoạch tích lồi suy rộng
m

min ∏ f j (x),

x ∈ X,

v.đ.k.

(GMP)

j=1


y ∈ WMinY.

(GMPY )

j=1

Tương tự thuật toán Solve(GMOP) giải bài toán (GMOP), thuật toán Solve(GMPY )
giải bài toán (GMP) cũng xây dựng dãy đa diện {Bk } thỏa mãn B0 ⊃ B1 ⊃ · · · ⊃
12


Bk ⊃ Y ⊃ WMinY, trong đó B0 = B[b, d], hai điểm b, d được xác định như (2.1) và
p
p
là tập lồi compact có thứ nguyên đầy đủ. Đa diện Bk+1
) ⊂ R+
Y = Y + ∩ (d − R+
được xác định như mô tả ở Bước 2 và Bước 3 của thuật toán Solve(GMOP).
Quá trình xây dựng dãy đa diện {Bk } sẽ đồng thời sinh ra hai dãy cận trên và cận
dưới của bài toán (GMPY ) và cho phép ta nhận được nghiệm và giá trị tối ưu xấp xỉ
của bài toán (GMPY ).
Giả sử ta có điểm y¯ ∈ WMinY . Hiển nhiên là α¯ = ϕ(y)
¯ là một cận trên của bài
toán (GMPY ). Cho số thực ε > 0 đủ nhỏ. Điểm y¯ được gọi là một nghiệm ε-xấp xỉ
của bài toán (GMPY ) nếu tồn tại một cận dưới β¯ của bài toán này sao cho α¯ − β¯ ≤ ε.
Theo Bổ đề 3.1, bất kỳ x¯ ∈ X thỏa mãn f (x)
¯ ≤ y,
¯ trong đó y¯ là một nghiệm ε-xấp xỉ
của bài toán (GMPY ), là một nghiệm ε-xấp xỉ của (GMP).
Tại mỗi bước lặp k điển hình, cận dưới tốt nhất hiện tại của bài toán (GMPY ) là

Nhận xét 3.2. Dãy {y¯k } mô tả trong Định lý 3.1 không nhất thiết phải hội tụ nhưng
do Y là tập compact nên nó chứa một dãy con hội tụ và mỗi điểm tụ của nó là
một nghiệm tối ưu của bài toán (GMPY ). Tương tự, mỗi điểm tụ của dãy {x¯k } với
f (x¯k ) = y¯k là một nghiệm tối ưu của bài toán (GMP).
Thuật toán được cài đặt bằng ngôn ngữ Matlab và thực hiện trên máy laptop HP
Pavilion 1.8Ghz, RAM 2GB. Kết quả tính toán của Ví dụ 3.1, trong đó hàm f không
lồi và X là đa diện khác rỗng, đã chứng tỏ tính đúng đắn của thuật toán.
3.2 Thuật toán giải bài toán quy hoạch tích lõm mở rộng (GIMP)
Xét bài toán quy hoạch tích lõm mở rộng
k

max Φ(x) = f0 (x) + ∏ fi (x) ,
x∈X

(GIMP)

i=1

trong đó k ≥ 2 và X ⊂ Rn là tập lồi compact khác rỗng, với mỗi i = 0, 1, . . . , k,
fi (x) > 0, với mọi x ∈ X.
Đặt f1 (x) = f0 (x), f2 (x) = ∏ki=1 fi (x)
ϕ( f (x)) và bài toán (GIMP) đã trở thành

1/k

, và ϕ(y1 , y2 ) = y1 + yk2 . Ta có Φ(x) =

max Φ(x) = ϕ( f (x)) v.đ.k. x ∈ X,

(GIMPX )



Nhận xét 3.3. Cho z∗ ∈ (zI − R2+ ) \Y − . Theo hình học, nếu p∗ là hình chiếu của z∗
lên Y − thì p∗ là điểm hữu hiệu của Y − và p∗ là nghiệm duy nhất của bài toán
min z∗ − z v.đ.k. z ∈ Y − .

(Pro(z∗ ))

Theo [61], d ∗ = (z∗ − p∗ )/ ∑2i=1 (z∗i − p∗i ) là véc tơ pháp tuyến của siêu phẳng tựa của
Y − tại p∗ . Để thuận tiện, ta gọi d ∗ là véc tơ pháp tuyến tương ứng với p∗ . Dễ thấy,
véc tơ d start = (0, 1) và d end = (1, 0) lần lượt là các véc tơ pháp tuyến của siêu phẳng
tựa của Y − tại zstart và zend .
3.2.1 Các thao tác cơ bản của lược đồ nhánh cận
a) Cận trên của bài toán con
Xét hai điểm z , zr ∈ MaxY − thỏa mãn zr1 > z1 và z2 > zr2 , và E ⊆ MaxY − là
đường cong duy nhất nối z với zr . Đặt d và d r lần lượt là các véc tơ pháp tuyến
tương ứng với z và zr . Rõ ràng rằng nếu z = zstart và zr = zend thì E ≡ MaxY − và
d = (0, 1), d r = (1, 0). Xét bài toán con
max ϕ(z) v.đ.k. z ∈ E .

(SP(E ))

Dễ thấy, bài toán (SP(E )) thuộc một trong ba trường hợp sau:
Trường hợp 1 (d = td r với t > 0): E = [z , zr ] và bài toán SP(E ) trở thành
max ψ(t) v.đ.k. t ∈ [0, 1],

1 )
(Psub

1 ). Khi đó,



trong đó
φ (t) = ϕ(z) =

ϕ z∗ + t(z∗ − z ) ,
ϕ (z∗ + t(zr − z∗ )) ,

−1 ≤ t ≤ 0
0 ≤ t ≤ 1.

2 ). Nếu t opt > 0 thì đặt zˆ = z∗ + t opt (zr − z∗ ),
Gọi t opt là một nghiệm của bài toán (Psub
∗
opt
∗
ngược lại đặt zˆ = z + t (z − z ). Khi đó, giá trị tối ưu α = α(E ) = ϕ(ˆz) là một
cận trên của bài toán (EPY − ).

Thủ tục tính cận trên của bài toán con (SP(E )) có thể mô tả như sau.
Thủ tục Solve(SP(E ))
Đầu vào: Hai điểm hữu hiệu z , zr và hai véc tơ pháp tuyến d , d r tương ứng.
Đầu ra: Nghiệm tối ưu zˆ của (RP(E )) và một chỉ số id. Nếu (RP(E )) thuộc vào
Trường hợp 3 thì id = 1 và zˆ ∈ (zI − R2+ ) \Y − . Ngược lại, id = 0 và zˆ ∈ MaxY − .
Bước 1. If d = td r với t > 0 Then chuyển sang Bước 3;
Else Tìm nghiệm z∗ của hệ phương trình tuyến tính (3.9).
Bước 2. If z∗ ∈ {z , zr } Then chuyển sang Bước 3;
2 ) để xác định nghiệm tối ưu t opt ;
Else Đặt id = 1. Giải bài toán (Psub
If t opt > 0 Then zˆ = z∗ + t opt (zr − z∗ ); Else zˆ = z∗ + t opt (z∗ − z ).



3.2.2 Thuật toán nhánh cận trên không gian ảnh
Cho ε > 0 đủ nhỏ. Nếu z ∈ MaxY − thì ϕ(z) là một cận dưới của bài toán (EPY − ).
Điểm zopt ∈ MaxY − được gọi là một nghiệm ε-xấp xỉ của bài toán (EPY − ) nếu tồn
tại một cận trên α ∗ của bài toán (EPY − ) thỏa mãn |α ∗ − ϕ(zopt )| ≤ ε(|ϕ(zopt )| + 1).
Thuật toán Solve(EPY − )
Bước khởi tạo. Chọn sai số ε > 0; Giải bài toán (IPi ), i = 1, 2, để tìm zstart và zend
của MaxY − ; Đặt β0 = max{ϕ(zstart ), ϕ(zend )} (cận dưới tốt nhất hiện tại);
Chọn z˜0 ∈ {zstart , zend } sao cho β0 = ϕ(˜z0 ) (˜z0 là nghiệm chấp nhận được tốt nhất
hiện tại); Tìm nghiệm tối ưu zˆ0 của bài toán (RP(E )) với E = E0 , trong đó E0 =
MaxY − là đường cong hữu hiệu nối hai điểm z = zstart và zr = zend ;
Đặt α(E0 ) = ϕ(ˆz0 ); Đặt k := 0 và R0 = {E0 }.
Bước lặp k, k = 0, 1, 2, . . . Xem Bước 1 đến Bước 4 dưới đây.
Bước 1. Tìm Ek ∈ Rk sao cho α(Ek ) = max{α(E ) | E ∈ Rk }, trong đó Ek là đường
cong hữu hiệu nối hai điểm z k và zrk ; Đặt αk := α(Ek ) (cận trên tốt nhất hiện tại).
Bước 2. Giải bài toán (Pro(z∗ )) với z∗ = zˆk để xác định pˆk ∈ MaxY − . Khi đó
dˆk =

(ˆzk − pˆk )
∑2i=1 (ˆzki − pˆki )

là một véc tơ pháp tuyến tương ứng với pˆk ; Cập nhật βk+1 = max{βk , ϕ( pˆk )} (cận
dưới tốt nhất hiện tại); Chọn z˜k+1 ∈ {˜zk , pˆk } thỏa mãn βk+1 = ϕ(˜zk+1 ) ( z˜k+1 là
nghiệm chấp nhận được tốt nhất hiện tại);
Đặt Rk+1 = Rk \ Ek ∪ {Ek1 , Ek2 }, trong đó Ek1 là đường cong hữu hiệu nối hai
điểm z k và pˆk , Ek2 là đường cong hữu hiệu nối hai điểm pˆk và zrk .
Bước 3. Với mỗi i ∈ {1, 2}, giải bài toán (RP(E )) với E = Eki để xác định Idi và
nghiệm tối ưu zˆki ; Đặt α(Eki ) = ϕ(ˆzki ) (cận trên của bài toán (SP(E )) với E = Eki );
If Idi = 0 và βk+1 < ϕ(ˆzki ) Then đặt

Chương này là đề xuất hai thuật toán trên không gian ảnh để giải bài toán
min h(x) = ϕ( f (x)) v.đ.k. x ∈ XE ,

(QP)

trong đó ϕ : R2 → R là hàm tựa lõm và bài toán
max h(x) = ϕ( f (x)) v.đ.k. x ∈ XE ,

(DP)

với ϕ : R2 → R là hàm đơn điệu tăng trên tập ảnh Y .
4.1 Thuật toán giải bài toán (QP) với ϕ là hàm tựa lõm
Theo định nghĩa, việc giải bài toán (QP) có thể đưa về việc giải bài toán
min ϕ(y) v.đ.k. y ∈ MinY + ,

(QPY + )

trong đó ϕ : R2 → R là hàm tựa lõm. Véc tơ v¯ ∈ R2 được gọi là một véc tơ pháp tuyến
trong của siêu phẳng tựa với Y + tại y¯ ∈ MinY + nếu v,
¯ y − y¯ ≥ 0 với mọi y ∈ Y + .
Để thuận tiện, ta gọi v¯ là véc tơ pháp tuyến trong tương ứng với điểm y.
¯ Dễ thấy,
vˆ1 = (1, 0) và vˆ2 = (0, 1) là các véc tơ pháp tuyến trong tương ứng với hai điểm đầu
mút yˆ1 và yˆ2 của MinY + . Hơn nữa, nếu điểm y¯ ∈ MinY + \ {yˆ1 , yˆ2 } thì véc tơ pháp
tuyến trong v¯ tương ứng với y¯ là hướng pháp tuyến dương của Y + tại y.
¯
4.1.1 Phân hoạch và bài toán con
Cho hai điểm yL , yR ∈ MinY + . Ký hiệu là Γ(yL , yR ) ⊆ MinY + là đoạn cong hữu
hiệu nối yL và yR . Các véc tơ pháp tuyến trong tương ứng với yL và yR được ký hiệu
là vL và vR . Cho hai điểm yL , yR ∈ MinY + thỏa mãn

+
0
1
2
là một phân hoạch của MinY và mịn hơn phân hoạch D. Tập D = Γ(yˆ , yˆ ) được
dùng như là một phân hoạch khởi tạo.
Cho hai điểm yL , yR ∈ MinY + thỏa mãn (4.3) và vL , vR là các véc tơ pháp tuyến
trong tương ứng với yL , yR . Xét bài toán con (SP(yL , yR )) của bài toán (QPY + )
min ϕ(y) v.đ.k. y ∈ Γ(yL , yR ).

(SP(yL , yR ))

Chỉ có một trong hai trường hợp sau xảy ra.
Trường hợp 1(vL = tvR với t > 0): Khi đó Γ(yL , yR ) = [yL , yR ] ⊂ MinY + . Vì ϕ(y) là
hàm tựa lõm nên Argmin(SP(yL , yR )) ∈ {yL , yR }.
Trường hợp 2 (vL và vR độc lập tuyến tính): Ký hiệu HL là siêu phẳng tựa của Y + tại
yL và HR là siêu phẳng tựa của Y + tại yR . Giao điểm yO của hai đường thẳng này là
nghiệm duy nhất yO của hệ
vL , y = vL , yL
vR , y = vR , yR .

(4.5)

Ký hiệu S(yL , yR ) = conv{yL , yO , yR }. Ta có Γ(yL , yR ) ⊂ S(yL , yR ) . Vì vậy, giá trị tối
ưu của bài toán nới lỏng
min ϕ(y) v.đ.k. y ∈ S(yL , yR )

(RP(yL , yR ))

là một cận dưới của bài toán con (SP(yL , yR )). Vì hàm mục tiêu ϕ(y) là hàm tựa lõm

2
Else α0 = ϕ(yˆ ) và y0 = yˆ , x0 = xˆ (α0 - cận trên tốt nhất hiện tại,
best tương ứng với ybest );
ybest
0 - nghiệm chấp nhận được tốt nhất hiện tại, x0
0
L
R
L
1
R
2
Giải bài toán (RP(y , y )) với y = yˆ và y = yˆ để tìm nghiệm tối ưu yopt ;
Đặt Γ0 = Γ(yˆ1 , yˆ2 );
If ϕ(yO ) = ϕ(yopt ) Then Đặt G = {Γ0 }, β (Γ0 ) = ϕ(yopt ) và k := 0
best
Else Thuật toán dừng (ybest
0 ∈ Argmin(QPY + ) và x0 ∈ Argmin(QP)).
Bước 1. (Điều kiện dừng) If G = 0/ Then Thuật toán dừng. (ybest
là nghiệm tối ưu
k
best
ε-xấp xỉ của (QPY + ) và xk là nghiệm tối ưu xấp xỉ của (QP))
Bước 2. (Cập nhật cận dưới) Tìm Γk ∈ G , trong đó Γk = Γ(yL , yR ), thỏa mãn
β (Γk ) = min{β (Γ) | Γ ∈ G }; Đặt βk := β (Γk ). (cận dưới tốt nhất hiện tại)
Bước 3. (Rẽ nhánh và cập nhật cận trên) Giải bài toán (BP0 ) để xác định
∈ MinY + và xknew ∈ XE tương ứng;
ynew
k
new

Nếu thuật toán không dừng thì nó hội tụ như khẳng định trong kết quả sau.
Định lý 4.1. Nếu thuật toán không dừng thì dãy {ϕ(ybest
k )} hội tụ tới giá trị tối ưu
+ có một điểm tụ là nghiệm toàn cục của
của bài toán (QPY + ) và dãy {ybest
}
∈
MinY
k
bài toán (QPY + ).
Nhận xét 4.1. Thuật toán Solve(QPY + ) có thể được dùng để giải bài toán
min f1 (x) f2 (x) v.đ.k. x ∈ X,

(CBMP)

trong đó các hàm f j , j = 1, 2 và X được cho như trong (CBOP).
4.1.3 Tính toán thử nghiệm Tất cả các ví dụ trong mục này được thử nghiệm với
thuật toán cài đặt bằng ngôn ngữ Matlab trên máy laptop Pavilon 1.8Ghz, RAM 2GB.
Kết quả tính toán chỉ ra rằng thuật toán làm việc hiệu quả với nhiều dạng khác nhau
của hàm mục tiêu và đối với các bài toán có số chiều của không gian quyết định cũng
như số ràng buộc tương đối lớn.
4.2 Thuật toán giải bài toán (DP) với ϕ là hàm đơn điệu tăng
Theo định nghĩa, việc giải bài toán (QP) có thể đưa về việc giải bài toán
max ϕ(y) v.đ.k. y ∈ MinY + ,

(DPY + )

trong đó ϕ : Y → R là hàm đơn điệu tăng trên Y . Mục này đề xuất thuật toán giải bài
toán (DPY + ) theo lược đồ nhánh cận kết hợp kỹ thuật xấp xỉ ngoài.
4.2.1 Đơn hình xấp xỉ ngoài và lược đồ rẽ nhánh


v.đ.k.

f (x) − λ yO ≤ 0, x ∈ X.

(T (yO ))

Khi đó x∗ là nghiệm hữu hiệu tương ứng với yω = λ ∗ yO (Xem Mệnh đề 1.9).
21


Nhận xét 4.2. Giả sử hai điểm yL , yR ∈ MinY + thỏa mãn (4.3) và Γ(yL , yR ) ⊆ MinY +
là đường cong hữu hiệu nối yL và yR . Xét 2−đơn hình S(yL , yR ) sinh bởi yL và yR . Ký
hiệu yω là điểm xác định như mô tả trong Mệnh đề 4.1. Theo (4.7), ký hiệu S(yL , yω )
là đơn hình sinh bởi yL và yω , và S(yω , yR ) là đơn hình sinh bởi yω và yR . Khi đó, ta
có
Γ(yL , yR ) ⊂ S(yL , yω ) ∪ S(yω , yR ) ⊂ S(yL , yR ).
Điểm yω được xem như một điểm chia đôi đơn hình S(yL , yR ). Việc chia đơn hình
S(yL , yR ) như vậy được gọi là lược đồ rẽ nhánh áp dụng cho đơn hình S(yL , yR ). Tính
chất này sẽ được sử dụng để xây dựng thuật toán giải bài toán (DPY + ). Hiển nhiên là
(4.3) thỏa mãn với yL = yˆ1 , yR = yˆ2 . Đặt S(yˆ1 , yˆ2 ) là đơn hình sinh bởi hai điểm yˆ1 và
yˆ2 . Ta có MinY + ⊂ S(yˆ1 , yˆ2 ), và S(yˆ1 , yˆ2 ) được chọn làm đơn hình xuất phát.
4.2.2 Thuật toán nhánh cận - xấp xỉ ngoài
Đặt T 0 = {S0,1 }, trong đó S0,1 = S(yˆ1 , yˆ2 ) và U 0 = S∈T 0 S = S0,1 ⊃ MinY + .
Xuất phát từ hai tập T 0 và U 0 , thuật toán là một quá trình lặp sinh ra hai dãy T k =
{Sk,1 , Sk,2 , . . . , Sk,ηk } gồm các 2−đơn hình, trong đó ηk là số phần tử của T k , và
U k = S∈T k S thỏa mãn U 0 ⊃ U 1 ⊃ ...U k ⊃ U k+1 ⊃ ... ⊃ MinY + .
Cho số thực ε > 0 đủ nhỏ. Điểm chấp nhận được y∗ ∈ MinY + được gọi là nghiệm
tối ưu ε−xấp xỉ của bài toán (DPY + ) nếu tồn tại một cận trên α ∗ của bài toán này
thỏa mãn α ∗ − ϕ(y∗ ) < ε(|ϕ(y∗ )| + 1). Khi đó, nghiệm hữu hiệu x∗ tương ứng với y∗

hai điểm yL , yR nào đó. Vì ϕ là hàm đơn điệu tăng trên S(yL , yR ) ⊂ R2+ nên nghiệm
tối ưu của bài toán (DP(S(yL , yR ))) đạt tại cạnh yL , yR của đơn hình S(yL , yR ). Do
đó, bài toán (DP(S(yL , yR ))) có thể đưa về một bài toán max{θ (t)|0 ≤ t ≤ 1}, trong
đó θ (t) = ϕ tyL + (1 − t)yR .
Thuật toán Solve(DPY + )
Bước khởi tạo. Chọn sai số ε > 0; Giải bài toán (SPi ) với i = 1, 2 để xác định
yˆ1 , yˆ2 ∈ MinY + và xˆ1 , xˆ2 ∈ XE tương ứng với yˆ1 , yˆ2 ;
If yˆ1 ≡ yˆ2 Then Thuật toán dừng, yˆ1 ∈ Argmax(DPY + ) và xˆ1 ∈ Argmax(DP);
If ϕ(yˆ1 ) > ϕ(yˆ2 ) Then β0 = ϕ(yˆ1 ) và ybest = yˆ1 , xbest = xˆ1
Else β0 = ϕ(yˆ2 ) và ybest = yˆ2 , xbest = xˆ2 ;
Đặt S0,1 = S(yˆ1 , yˆ2 ). Đặt T 0 := {S0,1 } và U 0 := S0,1 ;
Tìm giá trị tối ưu α(S) của bài toán (DP(S(yL , yR ))) với S = S(yˆ1 , yˆ2 );
Đặt k := 0; Chuyển sang Bước lặp k.
Bước lặp k, (k = 0, 1, 2, ...) Thực hiện từ Bước 1 đến Bước 3 như dưới đây.
Bước 1. Tìm Sk,η¯ ∈ T k , trong đó Sk,η¯ = S(yL , yR ), thỏa mãn
α(Sk,η¯ ) := max{α(S ) | S ∈ T k }; αk := α(Sk,η¯ ) (cận trên tốt nhất hiện tại);
If αk − βk ≤ ε(|βk | + 1) Then Thuật toán dừng (ybest là nghiệm tối ưu
ε−xấp xỉ của (DPY + ), xbest là nghiệm tối ưu xấp xỉ của (DP))
Else Đặt Sk = Sk,η¯ .
Bước 2. Xác định gốc yO của đơn hình Sk bởi ((4.6)), trong đó Sk = S(yL , yR );
Giải bài toán (T (yO )) để tìm nghiệm tối ưu (λ ∗ , x∗ );
Đặt yωk = λ ∗ yO ∈ MinY + và x∗ ∈ XE tương ứng với yωk ;
If ϕ(yωk ) > βk Then
βk+1 = ϕ(yωk ) (cận dưới tốt nhất hiện tại)
best
ω
y = y k (nghiệm chấp nhận được tốt nhất hiện tại)
xbest = x∗ ; (nghiệm hữu hiệu tương ứng với ybest )
Bước 3. Đặt S1k = S(yL , yωk ) và S2k = S(yωk , yR );
Với mỗi i = 1, 2, tìm giá trị tối ưu α(Sik ) của (DP(S(yL , yR ))) với S = Sik ;

quy hoạch tích lồi suy rộng (GMP) dựa trên mối quan hệ của bài toán này với bài
toán quy hoạch đa mục tiêu lồi suy rộng tương ứng. Đây là một ứng dụng trực tiếp
của thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mục tiêu lồi suy rộng
(GMOP). Tính hội tụ của thuật toán được chỉ ra ở Định lý 3.1.
3. Nghiên cứu bài toán (GIMP) cực đại một hàm mục tiêu là tổng của một hàm lõm
với tích p ≥ 2 hàm lõm trên tập chấp nhận được là tập lồi compact khác rỗng, đưa
việc giải bài toán này về giải bài toán (EPY − ) cực đại một hàm liên tục, đơn điệu tăng
trên tập điểm hữu hiệu yếu của một tập lồi có thứ nguyên đầy đủ trong R2 . Thuật toán
nhánh cận Solve(EPY − ) giải bài toán (EPY − ) được xây dựng dựa trên cấu trúc đặc
biệt của tập điểm hữu hiệu và được chứng minh là hội tụ (Định lý 3.2). Các kết quả
tính toán thử nghiệm cho thấy thuật toán có thể giải các bài toán có số biến lớn.
4. Đề xuất hai thuật toán trên không gian ảnh để giải hai bài toán tối ưu hàm mục tiêu
có dạng h(x) = ϕ( f (x)) trên tập nghiệm hữu hiệu XE của bài toán quy hoạch hai mục
tiêu lồi (CBOP), trong đó hàm véc tơ lồi f (x) = ( f1 (x), f2 (x)) là hàm mục tiêu của bài
toán (CBOP), dựa trên cấu trúc đặc biệt của tập giá trị hữu hiệu YE = f (XE ) và tính
đặc thù của hàm ϕ: Thuật toán nhánh cận giải bài toán cực tiểu hàm h(x) = ϕ( f (x))
trên XE , trong đó ϕ : R2 → R là hàm tựa lõm (Thuật toán Solve(QPY + )); Thuật toán
nhánh cận kết hợp xấp xỉ ngoài giải bài toán cực đại hàm h(x) = ϕ( f (x)) trên XE ,
trong đó ϕ : R2 → R là đơn điệu tăng (Thuật toán Solve(DPY + )). Cả hai thuật toán
này đều được chứng minh là hội tụ (Định lý 4.1 và Định lý 4.2).
24


Danh mục tài liệu tham khảo
Tiếng Việt
1. Lê Dũng Mưu, Nguyễn Văn Hiền (2009), Nhập môn giải tích lồi ứng dụng,
NXB Khoa học tự nhiên và Công nghệ, Hà Nội.
2. Nguyễn Thị Bạch Kim (2014), Giáo trình các phương pháp tối ưu: Lý thuyết
và thuật toán, NXB Bách Khoa, Hà Nội.
3. Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến,