BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

NGUYỄN THÙY LINH

MỘT SỐ THUẬT TOÁN GIẢI
BÀI TOÁN TỐI ƯU TRÊN TẬP PARETO

LUẬN VĂN THẠC SĨ KHOA HỌC
ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ CÁC HỆ THỐNG TÍNH TOÁN

Hà Nội – Năm 2011


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

NGUYỄN THÙY LINH

MỘT SỐ THUẬT TOÁN GIẢI
BÀI TOÁN TỐI ƯU TRÊN TẬP PARETO

LUẬN VĂN THẠC SĨ KHOA HỌC
ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ CÁC HỆ THỐNG TÍNH TOÁN

Hà Nội – Năm 2011


Mục lục

1 Bài toán tối ưu trên tập Pareto
1.1 Bài toán quy hoạch tuyến tính đa
1.1.1 Một số ví dụ . . . . . . . .
1.1.2 Phát biểu bài toán . . . .
1.1.3 Điều kiện hữu hiệu . . . .
1.1.4 Điều kiện tồn tại nghiệm .
1.1.5 Cấu trúc tập nghiệm . . .
1.2 Bài toán tối ưu trên tập Pareto .
2 Bốn trường hợp đặc biệt của bài
Pareto
2.1 Cơ sở lý thuyết . . . . . . . . . .
2.2 Thuật toán . . . . . . . . . . . .
2.2.1 Trường hợp 1 . . . . . . .
2.2.2 Trường hợp 2 . . . . . . .
2.2.3 Trường hợp 3 . . . . . . .
2.2.4 Trường hợp 4 . . . . . . .

mục tiêu
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

toán tối ưu trên tập

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


3 Giải bài toán tối ưu trên tập Pareto bằng phương pháp
quy hoạch lồi lõm
3.1 Dạng tương đương của bài toán (P ) . . . . . . . . . . . .
3.2 Dạng rút gọn của bài toán (3.1) . . . . . . . . . . . . . .
3.3 Phương pháp nhánh cận giải bài toán . . . . . . . . . . .
3.3.1 Thuật toán xấp xỉ ngoài xây dựng tập đa diện ban
đầu . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Thuật toán nhánh cận giải bài toán (3.5) . . . . .

1

8
9
9
10
11
17
23
24
27
29
41
42
43
45
48
50
51
57

62
63
66


Một số ký hiệu
R
Rn
x∈X
x∈
/X
∃x
∃x
∀x
|x|
∅
F ⊂A
F ⊆A
A=B
A\B
A∪B
A∩B
x, y
[v 1 , v 2 ]
affA
cone{c1 , · · · , ck }
convA
dimA
domg
epig

intA
kerC
rankC

tập số thực
không gian Euclid n chiều
x thuộc tập X
x không thuộc tập X
tồn tại x
không tồn tại x
mọi x
giá trị tuyệt đối của x
tập rỗng
F là tập con thực sự của tập A
F là tập con của tập A hoặc có thể bằng tập A
tập A khác tập B
hiệu của tập A và tập B
hợp của tập A và tập B
giao của tập A và tập B
tích vô hướng của x và y
đoạn thẳng nối hai điểm v 1 và v 2
bao afin của tập A
nón sinh bởi các véc tơ c1 , · · · , ck
bao lồi của tập A
thứ nguyên (hoặc số chiều) của tập A
miền xác định hữu hiệu của g
epigraph của hàm g
phần trong của tập A
hạt nhân của C
hạng của ma trận C

3


riA
rec(K)
span{c1 , · · · , ck }
∇f (x)
Ip
B(a, ε)
wT
AT
∂g(x)

phần trong tương đối của tập A
nón lùi xa của tập K
không gian tuyến tính sinh bởi các véc tơ c1 , · · · , ck
véc tơ gradient của hàm f tại điểm x
ma trận đơn vị cấp p × p
hình tròn mở tâm a, bán kính ε > 0
véc tơ chuyển vị của véc tơ w
ma trận chuyển vị của ma trận A
dưới vi phân của g tại x

4


Mở đầu
Bài toán quy hoạch tuyến tính đa mục tiêu là bài toán tối ưu đồng thời
p ≥ 2 hàm mục tiêu tuyến tính ci , x , trong đó ci ∈ Rn , i = 1, · · · , p,
độc lập với nhau trên một tập lồi đa diện khác rỗng X ⊂ Rn . Đây là

bài toán có ý nghĩa ứng dụng quan trọng trong thực tế, đặc biệt trong
lý thuyết quyết định, kinh tế, tài chính, quản lý, công nghiệp, · · · .
Cho đến nay, rất nhiều tác giả đã đề xuất các thuật toán để xác định
toàn bộ hoặc một phần tập nghiệm hữu hiệu XE của bài toán quy hoạch
tuyến tính đa mục tiêu, chẳng hạn xem [2], [4], [5], [9] và danh mục tài
liệu tham khảo kèm theo.
Một bài toán quan trọng có liên quan chặt chẽ với bài toán quy hoạch
tuyến tính đa mục tiêu là bài toán tối ưu trên tập Pareto, ký hiệu là (P ).
Đó là bài toán tối ưu một hàm thực f (x) trên tập nghiệm hữu hiệu XE
của bài toán quy hoạch tuyến tính đa mục tiêu. Việc giải bài toán này
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 thiết đòi hỏi phải xác định toàn bộ tập XE . Bài toán
này được Philip đưa ra năm 1972. Đây là bài toán khó và thuộc lớp bài
toán tối ưu toàn cục, tức là nghiệm tối ưu địa phương chưa chắc đã là
nghiệm tối ưu toàn cục. Tuy nhiên, do nhu cầu ứng dụng, bài toán (P )
đã thu hút được sự quan tâm đặc biệt của rất nhiều tác giả. Nhiều thuật
5


toán theo các tiếp cận khác nhau đã được đề xuất để giải bài toán tối ưu
trên tập Pareto (P ), chẳng hạn xem [3], [6], [7], [10], [12], [13] và danh
mục tài liệu tham khảo kèm theo.
Mục đích chính của luận văn này là trình bày một số thuật toán để giải
bài toán tối ưu trên tập Pareto. Ngoài phần Mở đầu, Lời cảm ơn, Kết
luận và danh sách Tài liệu tham khảo, nội dung chính của luận văn được
trình bày trong ba chương.
• Chương 1 - "Bài toán tối ưu trên tập Pareto". Trình bày
mô hình toán học của bài toán quy hoạch tuyến tính đa mục tiêu
(VP), một vài ví dụ thực tế, một số khái niệm và kết quả cơ bản
như điểm hữu hiệu, nghiệm hữu hiệu, điều kiện hữu hiệu và cấu

trúc tập nghiệm của bài toán. Tiếp đó, giới thiệu mô hình toán
học của bài toán tối ưu trên tập Pareto.
• Chương 2 - "Bốn trường hợp đặc biệt của bài toán tối ưu
trên tập Pareto". Chương này dành để trình bày cơ sở lý thuyết
và các thuật toán giải bốn trường hợp đặc biệt của bài toán tối ưu
trên tập Pareto với hàm mục tiêu tuyến tính do H. P. Benson và
S. Sayin [6] đề xuất.
• Chương 3 - "Giải bài toán tối ưu trên tập Pareto bằng
phương pháp quy hoạch lồi lõm". Trình bày dạng tương đương,
dạng rút gọn của bài toán tối ưu trên tập Pareto và thuật toán
nhánh cận [12] để giải bài toán này với hàm mục tiêu là hàm lõm.

6


Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình,
nghiêm khắc của PGS. TS. Nguyễn Thị Bạch Kim. Tôi xin bày tỏ lòng
kính trọng và biết ơn sâu sắc nhất tới cô.
Đồng thời, tôi xin được gửi lời cảm ơn tới toàn thể các thầy cô trong
Khoa Toán Tin ứng dụng, Viện Đào tạo sau đại học - Trường Đại học
Bách Khoa Hà Nội và Khoa Công Nghệ Tin Học - Viện Đại học Mở
Hà Nội đã tạo điều kiện thuận lợi cho tôi trong suốt thời gian học tập,
nghiên cứu và hoàn thành luận văn này.
Tôi cũng xin được bày tỏ lòng biết ơn vô hạn tới bố mẹ và gia đình đã
tạo điều kiện thuận lợi, động viên và giúp đỡ để tôi có thể hoàn thành
tốt được luận văn này.
Hà Nội, tháng 3 năm 2011
Học viên
Nguyễn Thùy Linh


7


Chương 1

Bài toán tối ưu trên tập
Pareto
Mục đích chính của chương này là giới thiệu mô hình toán học và một
số tính chất cơ bản của bài toán tối ưu trên tập Pareto (Mục 1.2). Trước
hết, Mục 1.1 sẽ trình bày mô hình toán học của bài toán quy hoạch
tuyến tính đa mục tiêu (V P ), một vài ví dụ thực tế và một số khái niệm
cơ bản của lớp bài toán này như nghiệm hữu hiệu, điều kiện hữu hiệu
và cấu trúc tập nghiệm của bài toán. Nội dung chính của chương được
tham khảo chủ yếu ở [1], [2], [9], [11] và [12].

8


1.1

Bài toán quy hoạch tuyến tính đa mục
tiêu

1.1.1

Một số ví dụ

Sau đây là hai ví dụ thực tế có mô hình toán học là bài toán quy hoạch
tuyến tính đa mục tiêu.

Ví dụ 1.1 Một khách hàng muốn nhân viên của cửa hàng tư vấn để
mua xe ô tô. Theo sở thích, khách hàng muốn chọn mua một trong bốn
loại xe: VW Golf, Opel Astra, Ford Mondeo và Toyota Avensis. Chi tiết
giá cả và thông số công suất động cơ của từng loại xe được cho trong
Bảng 1.1. Nhân viên tư vấn cần giúp khách hàng chọn mua được một
xe sao cho giá cả rẻ nhất và công suất động cơ cao nhất.
Bảng 1.1
VW

Opel

Ford

Toyota

Giá (nghìn USD)

31

29

30

27

Công suất động cơ (Mã lực)

90

75


80

75

Đây là bài toán tối ưu đồng thời hai mục tiêu. Bài toán này phức tạp
nên nhân viên của cửa hàng khó có thể tư vấn được cho khách hàng một
cách dễ dàng.
Ví dụ 1.2 Một nhà máy thủy điện cần thiết kế xây dựng một đập nước.
Quyết định xây dựng đập nước phụ thuộc vào chi phí nhân công xây
dựng, bán kính trung bình của hồ và tuân theo một số ràng buộc như
khả năng chịu lực tối thiểu của đập nước sao cho tối đa hóa khả năng
9


lưu trữ, đồng thời giảm thiểu sự mất nước do bay hơi và chi phí xây
dựng. Trong ví dụ này, tập chấp nhận được là tập các đập nước có thể
được thiết lập và các hàm mục tiêu gồm các biến quyết định được cực
đại hoặc cực tiểu hóa. Các hàm mục tiêu có sự đối kháng nhau: cực tiểu
của hàm mục tiêu này thì lại không là tối ưu đối với hàm mục tiêu khác.

1.1.2

Phát biểu bài toán

Thông thường, trong Rp với p ≥ 2, người ta sử dụng thứ tự sau:
Cho x = (x1 , x2 , · · · , xp ), y = (y1 , y2 , · · · , yp ). Ta nói:
x ≥ y ⇔ xi ≥ yi
i = 1, · · · , p;
xi ≥ yi , ∀i = 1, · · · , p

x≥y
⇔
x>y⇔
x=y
và ∃i0 ∈ {1, · · · , p} : xi0 > yi0 ;
x
y ⇔ xi > yi , ∀i = 1, · · · , p.
Bài toán quy hoạch tuyến tính đa mục tiêu được phát biểu như sau
Max Cx, x ∈ X,

(V P )

trong đó C là ma trận mục tiêu cấp p × n, p ≥ 2 với p hàng là cj ∈
Rn , j = 1, · · · , p; X ⊂ Rn là tập lồi đa diện khác rỗng.
Theo định nghĩa, tập lồi đa diện X ⊂ Rn là giao của một số hữu hạn các
nửa không gian đóng. Nói cách khác, tập lồi đa diện X là tập nghiệm
của một hệ hữu hạn các bất đẳng thức tuyến tính. Tập lồi đa diện bị
chặn được gọi là đa diện.
Một điểm x0 ∈ X được gọi là một nghiệm hữu hiệu của bài toán (V P )
nếu
x ∈ X : Cx ≥ Cx0 và Cx = Cx0 .
10


Nghiệm hữu hiệu còn được gọi là nghiệm tối ưu Pareto. Ký hiệu XE là
tập tất cả các nghiệm hữu hiệu của bài toán (V P ).

1.1.3

Điều kiện hữu hiệu


Ký hiệu Rp+ = {λ = (λ1 , · · · , λp ) ∈ Rp |λj ≥ 0, j = 1, · · · , p}.
Định lý sau đây cho phép ta tìm được một nghiệm hữu hiệu của bài
toán quy hoạch tuyến tính đa mục tiêu (V P ) thông qua việc giải một
quy hoạch tuyến tính thông thường.
Định lý 1.1 (Định lý vô hướng hóa) Điểm x0 ∈ X là nghiệm hữu hiệu
của bài toán (V P ) khi và chỉ khi tồn tại một véc tơ λ ∈ intRp+ (tức là
λ

0) sao cho x0 là nghiệm tối ưu của bài toán quy hoạch tuyến tính

vô hướng sau
max{ λ, Cx , x ∈ X}.
Cho A ⊂ Rn . Ký hiệu riA là tập các điểm trong tương đối của A, tức
riA = {x0 ∈ A|∃B(a0 , ε) ∩ affA ⊂ A},
trong đó B(a0 , ε) là hình tròn mở tâm a0 , bán kính ε > 0 và affA là bao
afin của tập A.
Cho tập lồi khác rỗng A ⊂ Rn . Nhắc lại rằng, một tập con lồi khác rỗng
F ⊆ A được gọi là một diện của A nếu bất cứ đoạn thẳng nào nằm
trong A và có một điểm trong tương đối x ∈ F đều nằm trọn trong F ,
nghĩa là
x ∈ F, x = λy + (1 − λ)z, 0 < λ < 1, y, z ∈ A ⇒ y ∈ F, z ∈ F.

11


Hệ quả 1.1 Xét bài toán quy hoạch tuyến tính đa mục tiêu (V P ). Cho
tập F là một diện của tập lồi đa diện X. Nếu một điểm x0 ∈ riF và x0
là nghiệm hữu hiệu (tức là x0 ∈ XE ) thì F ⊂ XE .
Một diện F là một diện hữu hiệu (efficient face) nếu tất cả các phần tử

của F đều là nghiệm hữu hiệu của bài toán (V P ).
Đặt
p
1

p

n

λj cj , λj ≥ 0, j = 1, · · · , p}.

K = cone{c , · · · , c } := {v ∈ R | v =
j=1

Như thường lệ, K được gọi là nón sinh bởi {c1 , · · · , cp }.
Cho tập lồi khác rỗng M ⊂ Rn . Nón pháp tuyến của M tại x0 ∈ M , ký
hiệu là NM (x0 ), được định nghĩa bởi
NM (x0 ) := {v ∈ Rn | v, x − x0 ≤ 0, ∀x ∈ M }.
Sau đây là điều kiện để một điểm x0 ∈ X là nghiệm hữu hiệu của bài
toán quy hoạch tuyến tính đa mục tiêu (V P ) được phát biểu theo ngôn
ngữ nón pháp tuyến.
Mệnh đề 1.1 Một điểm x0 ∈ X là nghiệm hữu hiệu của bài toán (V P )
khi và chỉ khi
NX (x0 ) ∩ riK = ∅,
trong đó NX (x0 ) là nón pháp tuyến của tập lồi đa diện X tại điểm x0
và K = cone{c1 , · · · , cp }.
Chứng minh. Theo Định lý 1.1, x0 ∈ X là nghiệm hữu hiệu của bài toán
quy hoạch tuyến tính đa mục tiêu (VP) khi và chỉ khi tồn tại một véc
12



tơ λ

0 thỏa mãn
x0 ∈ argmax{ λ, Cx , x ∈ X},

tức là
λ, Cx ≤ λ, Cx0 , ∀x ∈ X
⇔ λ, Cx − Cx0 = λ, C(x − x0 ) = C T λ, x − x0 ≤ 0, ∀x ∈ X.
Đặt véc tơ v = C T λ. Bất đẳng thức trên chứng tỏ v nằm trong nón pháp
tuyến của X tại x0 . Theo định nghĩa và do λ

0, ta có v = C T λ ∈ riK,

trong đó K = cone{c1 , · · · , cp }. Suy ra, NX (x0 ) ∩ riK = ∅.
Ngược lại, nếu NX (x0 ) ∩ riK = ∅, tức là tồn tại một véc tơ v ∈ NX (x0 )
và v = C T λ với λ

0. Suy ra v, x − x0 ≤ 0 với mọi x ∈ X. Nói cách

khác, x0 ∈ argmax{ λ, Cx , x ∈ X}. Theo Định lý 1.1, x0 là nghiệm
hữu hiệu của bài toán (VP).
Sau đây là công thức tính nón pháp tuyến NX (x0 ), với x0 ∈ X, trong
trường hợp tập lồi đa diện X là tập nghiệm của hệ bất đẳng thức tuyến
tính
ai , x ≥ bi , i = 1, · · · , m,

(1.1)

trong đó ai ∈ Rn , bi ∈ R, i = 1, · · · , m.

Mệnh đề 1.2 Giả sử tập lồi đa diện X được xác định bởi hệ (1.1) và
x0 ∈ X. Khi đó
NX (x0 ) = cone{−ai |i ∈ I(x0 )},
trong đó I(x0 ) := {i ∈ {1, · · · , m}| ai , x0 = bi }.
Trong thực tế tính toán, người ta sử dụng dạng tương đương sau của
Mệnh đề 1.1.
13


Mệnh đề 1.3 Một điểm x0 ∈ X là nghiệm hữu hiệu của bài toán quy
hoạch tuyến tính đa mục tiêu (V P ), trong đó X được xác định bởi hệ
(1.1), khi và chỉ khi hệ sau có nghiệm
p
i

λj cj = 0,

µi a −

−

j=1

i∈I(x0 )

µi ≥ 0, ∀i ∈ I(x0 ),
λj > 0, ∀j = 1, · · · , p.
Ví dụ 1.3 Xét bài toán quy hoạch tuyến tính hai mục tiêu

 −x + 3x

1
2
Max
 −x1 − 3x2
với các ràng buộc



−x1 − 2x2




 −2x − x
1
2


−x1 + 2x2




 x1 , x2
Ta có


C=

−1


3

−1 −3


⇒

≥ −8
≥ −7
≥ −1
≥ 0.

c1 = (−1, 3)
c2 = (−1, −3),

nón K = cone{c1 , c2 }, tập chấp nhận được và nón pháp tuyến tại một
số điểm của tập chấp nhận được được minh họa ở Hình 1.1.
Từ Hình 1.1, ta thấy
NX (v 1 ) ∩ riK = ∅ ⇒ v 1 ∈ XE ,
NX (v 2 ) ∩ riK = ∅ ⇒ v 2 ∈
/ XE .
14


Hình 1.1

Ví dụ 1.4 Xét bài toán quy hoạch tuyến tính hai mục tiêu

 −x + x

1
2
Max

x2
với các ràng buộc



−x1 − x2 ≥ −4


x1 − x2 ≥ −2



 x1 ,
x2 ≥ 0.
Ta có


C=

−1 1
0

1


⇒

15

c1 = (−1, 1)
c2 = (0, 1),


nón K = cone{c1 , c2 }, tập chấp nhận được và nón pháp tuyến tại một
số điểm của tập chấp nhận được được minh họa ở Hình 1.2.

Hình 1.2

Từ Hình 1.2, ta thấy
NX (v 2 ) ∩ riK = riK = ∅ ⇒ v 2 ∈ XE ,
NX (v 3 ) ∩ riK = ∅ ⇒ v 3 ∈
/ XE .
Điều kiện hữu hiệu sau đây là công cụ cơ bản của thuật toán giải một
trường hợp đặc biệt của bài toán tối ưu trên tập hữu hiệu. Thuật toán
này được trình bày ở Chương 2.
Định lý 1.2 Cho x0 ∈ X. Khi đó, x0 ∈ XE khi và chỉ khi với x = x0 ,
quy hoạch tuyến tính (LPx ) sau
16


max e, s ,

(LPx )

với điều kiện
Cz − s = Cx,
z ∈ X,

s ≥ 0,
có một giá trị tối ưu vx = 0, trong đó e = (1, · · · , 1) ∈ Rp .

1.1.4

Điều kiện tồn tại nghiệm

Như là một hệ quả trực tiếp của Định lý 1.1, dễ thấy rằng nếu tập chấp
nhận được X ⊂ Rn của bài toán quy hoạch tuyến tính đa mục tiêu (V P )
là đa diện, tức là tập lồi đa diện X bị chặn, thì bài toán (V P ) luôn có
nghiệm hữu hiệu. Cụ thể
Mệnh đề 1.4 Nếu X ⊂ Rn là đa diện thì tập nghiệm hữu hiệu XE của
bài toán (V P ) là tập compact khác rỗng.
Nếu X ⊂ Rn là tập lồi đa diện không bị chặn thì bài toán (V P ) chưa
chắc đã có nghiệm hữu hiệu. Kết quả sau cho phép xác định được sự tồn
tại nghiệm hữu hiệu của bài toán (V P ) và tìm được một nghiệm hữu
hiệu đầu tiên trong trường hợp X ⊂ Rn là tập lồi đa diện xác định bởi
hệ bất đẳng thức tuyến tính (1.1).
Mệnh đề 1.5 Tập nghiệm hữu hiệu XE của bài toán (V P ) bằng rỗng
khi và chỉ khi hệ
17


p

m

µ i ai +
i=1


λj cj = 0,
j=1

µi ≥ 0, i = 1, · · · , m,

(1.2)

λj > 0, j = 1, · · · , p
không có nghiệm. Nếu hệ (1.2) có nghiệm (µ1 , · · · , µm , λ1 , · · · , λp ) thì
bài toán

p

λj cj , x , x ∈ X

max

(LP )

j=1

có nghiệm tối ưu và mỗi nghiệm tối ưu của (LP ) là một nghiệm hữu
hiệu của bài toán (V P ).
Ví dụ 1.5 Xét lại bài toán cho ở Ví dụ 1.3.
Ta có c1 = (−1, 3)T , c2 = (−1, −3)T ;
a1 = (−1, −2)T , a2 = (−2, −1)T , a3 = (−1, 2)T , a4 = (1, 0)T ,
a5 = (0, 1)T và hệ




µ a1 + µ2 a2 + µ3 a3 + µ4 a4 + µ5 a5 + λ1 c1 + λ2 c2 = 0,

 1
µi ≥ 0, i = 1, · · · , 5,




λj > 0, j = 1, 2.
 





 
 


−1
−2
−1
1
0













µ
+
µ
+
µ
+
µ
+
µ

1
2
3
4
5



−2
−1
2
0
1










−1
−1
 + λ2 
 = 0,
⇔
+λ1 


3
−3






µi ≥ 0, i = 1, · · · , 5,




 λj > 0, j = 1, 2.

18





−µ1




 −2µ
1
⇔


µi




 λj

− 2µ2 − µ3 +

− λ1 − λ2 = 0,

µ4

− µ2 + 2µ3


+ µ5 + 3λ1 − 3λ2 = 0,

≥

0,

i

=

1, · · · , 5,

>

0,

j

=

1,

2.

Dễ thấy (0, 0, 0, 2, 0, 1,1) là một nghiệm của hệ trên. Khi đó, theo Mệnh
đề 1.5, ta có bài toán quy hoạch tuyến tính sau
max{ w, x , x ∈ X},
trong đó


w = λ1 c1 + λ2 c2 = 

−1
3





+

Hình 1.3

19

−1
−3





=

−2
0


.



Theo hình học giải quy hoạch tuyến tính (Hình 1.3), ta có
argmax{ w, x , x ∈ X} = [v 1 , v 5 ],
trong đó [v 1 , v 5 ] là đoạn thẳng nối điểm v 1 và v 5 .

Hình 1.4

Từ Hình 1.4, ta thấy
NX (v 1 ) ∩ riK = riK = ∅ ⇒ v 1 ∈ XE ,
NX (v 5 ) ∩ riK = riK = ∅ ⇒ v 5 ∈ XE ,
NX (v 0 ) ∩ riK = ∅ ⇒ v 0 ∈ XE ,
20


v 0 ∈ ri[v 1 , v 5 ] ⇒ [v 1 , v 5 ] ⊂ XE .
Như vậy, ta thấy mỗi nghiệm tối ưu của (LP ) là một nghiệm hữu hiệu
của bài toán (V P ).
Sau đây là một vài ví dụ số được tính toán bởi chương trình viết bằng
ngôn ngữ Dev-C++ , chạy trên nền máy PC, hệ điều hành window, để
kiểm tra sự tồn tại của nghiệm hữu hiệu và xác định nghiệm hữu hiệu
ban đầu của bài toán quy hoạch tuyến tính đa mục tiêu (VP) theo Mệnh
đề 1.5.
Ví dụ 1.6

Max 



≥


2

≥

2

x
 1


 x2 


1.5
x3

−1 −1 −0.25
1



1



với các ràng buộc



2x1 + x2 + 2x3





 x
+ 2x2 + x3
1


−x1 − x2 − x3




 x1 , x2 , x3

≥ −6
≥

0.

Kết quả thu được: Nghiệm hữu hiệu ban đầu của bài toán quy hoạch
tuyến tính đa mục tiêu (VP) là x0 = (0, 0, 6).
Ví dụ 1.7







1 2 0
x

 1 



Max  1 0 −2   x2 



−1 0 1
x3
21


với các ràng buộc



−x1 − x2





− x2


−x1 + x2 − x3





 x1 , x2 , x3

≥ −1
≥ −2
≥ −4
≥

0.

Kết quả thu được: Nghiệm hữu hiệu ban đầu của bài toán quy hoạch
tuyến tính đa mục tiêu (VP) là x0 = (0, 1, 0).
Ví dụ 1.8





Max 




x
 1 



1 3 −2 0 1  x2 




3 −1 0 3 1   x3 




1 0 2 0 3  x4 


x5

với các ràng buộc

 −2 −4 0

 0 0 −2


 −5 0 0


 0 0 0

−5 −5 −2




−3  

−5 −4  


0 0 


−2 0  

0 0
0





x1  
 
x2  
 
 
x3  ≥ 
 
 
x4  
 
x5




−27 

−35 


−26  ,


−24 

−36

x1 , · · · , x5 ≥ 0.
Kết quả thu được: Nghiệm hữu hiệu ban đầu của bài toán quy hoạch
tuyến tính đa mục tiêu (VP) là x0 = (5.2, 0, 0, 2.5733, 5.5333).

22


1.1.5

Cấu trúc tập nghiệm

Định lý 1.3 (Định lý về cấu trúc tập nghiệm) Tập nghiệm hữu hiệu
XE của bài toán quy hoạch tuyến tính đa mục tiêu (V P ) là liên thông
đường gấp khúc và là hợp của một số hữu hạn các diện đóng của tập lồi
đa diện ràng buộc X.
Nhắc lại rằng, một tập A ⊂ Rn được gọi là liên thông đường gấp khúc

nếu với mỗi cặp điểm x, y ∈ A có thể tìm được một số hữu hạn điểm
x1 , · · · , xs ∈ A sao cho x1 = x, xs = y và đoạn thẳng [xi , xi+1 ] ⊆ A, i =
1, · · · , s − 1.
Nhận xét 1.1 Tập nghiệm hữu hiệu nói chung là tập không lồi và có
cấu trúc rất phức tạp. Đây là lý do để việc giải bài toán quy hoạch tuyến
tính đa mục tiêu có độ phức tạp cao.
Ví dụ 1.9 Xét bài toán Max{Cx, x ∈ X}, trong đó


1 0

C=
0 1
và X được xác định bởi hệ (1.1) với m = 6 và được minh họa như Hình
vẽ 1.5
Ta có K = cone{c1 , c2 } = R2+ . Bằng hình học, dễ thấy
XE = [v 1 , v 2 ] ∪ [v 2 , v 3 ].
Như vậy, XE là hợp của hai cạnh và XE không lồi ngay cả trong bài
toán đơn giản này.

23


Hình 1.5

1.2

Bài toán tối ưu trên tập Pareto

Bài toán tối ưu trên tập Pareto được phát biểu như sau

max{f (x) : x ∈ XE },

(P )

trong đó f là hàm giá trị thực, đóng vai trò như hàm mục tiêu, và XE
là tập nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêu
(V P ), đóng vai trò như tập ràng buộc.
Như đã biết, tập nghiệm hữu hiệu XE là liên thông nhưng nói chung,
XE là một tập con không lồi của X và có cấu trúc rất phức tạp. Vì vậy,
bài toán (P ) là một bài toán quy hoạch không lồi, tức là một nghiệm
địa phương bất kỳ của bài toán nhưng chưa chắc đã là nghiệm toàn cục.
Ta gọi một điểm x0 ∈ XE là nghiệm tối ưu địa phương hay cực đại địa
phương của bài toán (P ) nếu tồn tại một ε lân cận B(x0 , ε) của điểm
24