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

BÙI PHÚC KIểN

QUY HOẠCH ĐA MỤC TIÊU

LUẬN VĂN THẠC SĨ TỐN HỌC

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


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

Bùi Phúc Kiển

QUY HOẠCH ĐA MỤC TIÊU
Chuyên ngành: tốn giải tích
Mã số: 60.46.05

LUẬN VĂN THẠC SĨ TỐN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:

Ts Trịnh công Diệu

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


Lời cảm ơn

Trước hết, tôi xin gởi lời cám ơn đến Ts Trịnh Công Diệu, người đã dành
nhiều thời gian và cơng sức giúp tơi hồn thành luận văn này. Cám ơn ban giám
hiệu trường đại học sư phạm Tp.HCM, phịng sau đại học và các thầy cơ khoa tốn
– tin đã tạo nhiều điều kiện thuận lợi cho tôi trong suốt thời gian học tập và thực
hiện luận văn.
Cám ơn ba mẹ tôi và các thành viên trong gia đình những người đã động viên
tơi vượt qua những lúc khó khăn. Họ là nguồn động lực giúp tơi hồn thành luận
văn này.
Cuối cùng, tôi xin gởi lời cám ơn đến các bạn của tôi, những giúp đỡ về vật
chất cũng như về tinh thần của các bạn đã cho tơi sự n tâm để tơi có thể hồn
thành khóa học.
Tp. Hồ Chí Minh, ngày 23 tháng 9 năm 2012
Bùi Phúc Kiển


Lời nói đầu
Quy hoạch tốn học là một ngành tốn học có nhiều ứng dụng trong thực tế
Quy hoạch tuyến tính, một bộ phận của quy hoạch tốn học, bài tốn với một
hàm mục tiêu trong đó hàm mục tiêu và các ràng buộc là các hàm tuyến tính, đã
được đưa vào giảng dạy ở chương trình đại học. Tuy nhiên, do nhu cầu thực tế, phát
sinh nhiều bài toán đòi hỏi phải tối ưu cùng một lúc nhiều hàm mục tiêu với các
hàm mục tiêu và các ràng buộc thường là những hàm phi tuyến.
Quy hoạch đa mục tiêu (QHĐMT) ra đời đã đáp ứng những đòi hỏi nêu trên.
Từ những nền tảng đầu tiên được đặt ra bởi Pareto (1848 – 1923 ), đến nay
QHĐMT đã thu hút được nhiều nhà nghiên cứu và có nhiều ứng dụng rộng rãi trong
các lĩnh vực khác nhau từ kinh tế, tài chính, tin học, nơng nghiệp,…
Luận văn này trình bày những kiến thức cơ bản về QHĐMT và được chia
làm ba chương:
Chương 1 nhắc lại các kiến thức cơ bản của giải tích lồi như: tập lồi, tập
affine, hàm lồi, các định lý tách tập lồi,…

Chương 2 trình bày các kiến thức cơ bản về QHĐMT như các quan niệm về
tối ưu, các khái niệm tối ưu, những khó khăn đối với bài toán tối ưu đa mục tiêu,…
Chương 3 nêu ra một số phương pháp giải bài toán QHĐMT. Các phương
pháp được trình bày chủ yếu là các phương pháp vơ hướng, nghĩa là chuyển bài
tốn QHĐMT về bài toán quy hoạch đơn mục tiêu hoặc một họ các bài toán đơn
mục tiêu để giải.


MỤC LỤC

Chương 1. Kiến thức chuẩn bị

6

1.1 Tập lồi

6

1.2 Hàm lồi và các định lý tách tập lồi

7

Chương 2. Quy hoạch đa mục tiêu: những kiến thức cơ bản

10

2.1 Tối ưu với nhiều mục tiêu

10


2.2 Mơ hình tối ưu đa mục tiêu

12

2.3 Những khó khăn đối với bài tốn tối ưu đa mục tiêu

13

2.4 Các khái niệm tối ưu

15

2.5 Tối ưu đơn mục tiêu và đa mục tiêu: những khác biệt

19

Chương 3. Quy hoạch đa mục tiêu: các phương pháp giải

21

3.1 Phương pháp tổng trọng số ( the weighted sum method )

21

3.2 Phương pháp ε - ràng buộc ( the ε - constraint method )

26

3.3 Phương pháp lai ( The hybrid method )


30

3.4 Phương pháp co giãn ràng buộc ( The elastic constraint method )

31

3.5 Phương pháp Benson ( Benson’s method )

34

3.6 Tối ưu hóa kiểu từ điển ( lexicographic optimality )

37

3.7 Tối ưu theo thứ tự Max ( Max-Ordering optimality )

39

Tài liệu tham khảo

43

5


Chương 1. Kiến thức chuẩn bị
1.1 Tập lồi
Định nghĩa 1.1.1. Cho X là khơng gian tuyến tính. Tập A ⊂ X được gọi là lồi
nếu


∀x1 , x 2 ∈ A, ∀λ ∈ [ 0,1] ⇒ λ x1 + (1 − λ ) x 2 ∈ A .
Theo định nghĩa, ∅ và X được xem là tập lồi.
Mệnh đề 1.1.2. Giao của tất cả các tập lồi là một tập lồi.
Chứng minh: lấy Ai ⊂ X với i ∈ I là một họ các tập lồi. Đặt A =  Ai . Khi đó
i∈I

∀x, y ∈ A , ta có x, y ∈ Ai với mọi i ∈ I . Do ∀i ∈ I , Ai lồi nên

λ x + (1 − λ ) y ∈ Ai với mọi λ ∈ [ 0,1]

Suy ra λ x + (1 − λ ) y ∈ A với mọi λ ∈ [ 0,1] . Vậy A là tập lồi.



Mệnh đề 1.1.3 ( Định lý Helly ). Cho p > n và C1 , C2 ,..., C p ⊂  n là các tập lồi.
Khi đó
p

C

i

≠∅

i =1

{

}


khi và chỉ khi với mọi tập con gồm n + 1 phần tử Ci1 , Ci2 ,..., Cin +1 ⊂ {C1 , C2 ,..., C p }
ta đều có
n +1

C
k =1

ik

≠∅

6


Hoặc có phát biểu tương đương như sau,

p

C

i

= ∅ khi và chỉ khi có một tập con

i =1

{

}


gồm n + 1 phần tử Ci1 , Ci2 ,..., Cin +1 ⊂ {C1 , C2 ,..., C p } thỏa

n +1

C
k =1

ik

= ∅.

Chứng minh của mệnh đề 1.1.3 có thể tham khảo Đỗ Văn Lưu và Phan Huy Khải
(2000, trang 180-183).
Định nghĩa 1.1.4. Vectơ x ∈ X được gọi là một tổ hợp lồi của các vectơ
n

n

i =1

i =1

1, 2,..., n , ∑ λi = 1 sao cho x = ∑ λi x i .
x1 , x 2 ,..., x n ∈ X nếu tồn tại các λi ≥ 0, i =
Định lý 1.1.5. Giả sử A ⊂ X là tập lồi; x1 , x 2 ,..., x n ∈ A . Khi đó, A chứa tất cả các
tổ hợp lồi của x1 , x 2 ,..., x n .
Chứng minh: tham khảo Đỗ Văn Lưu và Phan Huy Khải (2000, trang 5-6)
Định nghĩa 1.1.6. Giả sử A ⊂ X . Giao của tất cả các tập lồi trong trong X chứa A
được gọi là bao lồi ( convex hull ) của A ký hiệu coA .
Định nghĩa 1.1.7. Tập A ⊂  n được gọi là tập affine nếu ∀x, y ∈ A, ∀λ ∈  ta có


(1 − λ ) x + λ y ∈ A .
Định nghĩa 1.1.8. Giao của tất cả các tập affine chứa A ⊂  n được gọi là bao
affine ( affine hull ) của A ký hiệu affA .
Định nghĩa 1.1.9. Phần trong tương đối của tập A ⊂  n là phần trong của A trong

affA và ký hiệu bởi riA . Các điểm thuộc riA được gọi là điểm trong tương đối của
A.

1.2 Hàm lồi và các định lý tách tập lồi

7


Giả sử X là không gian lồi địa phương, D ⊂ X , f : D →  ∪ {±∞} .
Định nghĩa 1.2.1. Trên đồ thị ( epigraph ) của hàm f , ký hiệu epif , được định
nghĩa như sau

{( x, r ) ∈ D ×  : f ( x ) ≤ r}

=:
epif

Định nghĩa 1.2.2. Hàm f được gọi là hàm lồi trên D nếu epif là tập lồi trong
X ×  . Hàm f được gọi là hàm lõm trên D nếu − f là hàm lồi trên D .

Định lý 1.2.3. Lấy X , Y ⊂  n là các tập lồi khác rỗng. Khi đó, tồn tại y* ∈  n thỏa

inf
y∈Y


Và

y, y * ≥ sup x, y *

sup
y∈Y

x∈X

y, y * > inf x, y *
x∈X

nếu và chỉ nếu riX ∩ riY =
∅.
Định lý 1.2.4. Lấy Y ⊂  n là một tập lồi, đóng, khác rỗng và y 0 ∈  n \ Y . Thì tồn
tại y* ∈  n \ {0} và α ∈  thỏa

y*, y 0 < α < y*, y với mọi y ∈ Y .
Chứng minh của định lý 1.2.3 và định lý 1.2.4 có thể tham khảo Đỗ Văn Lưu và
Phan Huy Khải (2000, trang 71-73).
Định lý 1.2.5. Cho X ⊂  n là tập lồi và f k :  n → , k =
1, 2,..., p là các hàm lồi.
p

Nếu hệ f k ( x ) < 0, k =
1, 2,..., p khơng có lời giải thì tồn tại các số λk ≥ 0, ∑ λk =
1
k =1


thỏa

8


p

∑ λ f ( x ) ≥ 0 với mọi x ∈ X
k =1

k

k

Chứng minh của định lý 1.2.5 có thể tìm trong Mangasarian ( 1994, trang 63-65 )

9


Chương 2. Quy hoạch đa mục tiêu: những kiến thức cơ bản
2.1 Tối ưu với nhiều mục tiêu
Ta xét bài tốn ra quyết định như sau:
Một chủ trang trại có 10 hecta đất và quyết định đầu tư trồng ba loại cây công
nghiệp gồm cao su, cà phê và điều. Các thông số về giá cây giống, mật độ trồng,
phân bón, giá bán sản phẩm, năng suất trung bình và nhân cơng chăm sóc được cho
trong bảng sau:
Loại cây

Cao su


Cà phê

Điều

Giá cây giống ( 1000đ/cây)

5

3,5

2,5

Mật độ (cây/ha )

450

2000

200

Phân bón (tấn/ha)

0,215

0,5

0,3

Năng suất trung bình (tấn/ha)


2,3

2,526

2

Giá bán sản phẩm (triệu đ/ tấn)

8,8

43,1

18

Nhân công ( người/ha)

10

5

4

Người chủ trang trại đặt ra các mục tiêu như sau:
• Vốn đầu tư, số lượng nhân cơng, khối lượng phân bón là tối thiểu
• Giá bán sản phẩm là cao nhất có thể
Nếu ta gọi số cây phải trồng của cao su, cà phê, điều lần lượt là x1 , x2 , và x3 thì vấn
đề của người chủ trang trại được xem xét dưới dạng mô hình của bài tốn tối ưu như
sau:
• Vốn đầu tư:


f1 ( x ) = 5 x1 + 3x2 + 2,5 x3 → min

10


• Số lượng nhân công:

f 2 ( x ) = 10

x
x
4 x1
+ 5 2 + 4 3 → min
450
2000
200

• Lượng phân bón sử dụng: f3 (=
x ) 0, 215

x
x1
x
+ 4 2 + 3 3 → min
450
2000
200

• Giá bán sản phẩm:


f 4 ( x )= 8,8 ì 2,3 ì
ã

x
x1
x
+ 43,1ì 2,526 2 + 18 × 2 × 3 → m ax
450
2000
200

Với các ràng buộc:

x
x1
x
+ 2 + 3 ≤ 10
450 2000 200
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Bài toán trên là một bài toán tối ưu với nhiều mục tiêu, các mục tiêu có ràng buộc
chặt chẽ với nhau, đơi khi mâu thuẫn nhau. Do đó trong bài tốn tối ưu với nhiều
mục tiêu, hầu như không thể đạt được giá trị tốt nhất của tất cả các mục tiêu cùng
một lúc. Điều này có nghĩa là bài tốn sẽ khơng có lời giải nếu bài tốn u cầu tìm
một phương án để tất cả các mục tiêu đều là tốt nhất. Tuy nhiên, ta có thể tìm được
lời giải nếu hiểu ý nghĩa của chữ tối ưu theo một cách khác.
Trong ví dụ nêu trên, có thể số tiền thu được khi bán sản phẩm là mục tiêu quan
trọng nhất đối với chủ trang trại, tiếp đến là vốn đầu tư, kém quan trọng hơn nữa là
nhân công và cuối cùng là mục tiêu phân bón. Như vậy, trong bài tốn trên, có một
thứ tự ưu tiên giữa các mục tiêu. Khi đó, trong việc giải bài tốn, mục tiêu kém ưu
tiên hơn chỉ được xem xét ở mức tốt nhất có thể khi mục tiêu ưu tiên trước nó đã đạt

được. Tối ưu đa mục tiêu có sự ưu tiên giữa các mục tiêu như vậy được gọi là tối ưu
theo kiểu từ điển.
Cũng trong ví dụ trên, trường hợp các mục tiêu có tầm quan trọng như nhau đối với
chủ trang trại. Anh ta xem một phương án là tối ưu khi không thể cải thiện bất kỳ

11


mục tiêu nào nữa mà không làm ảnh hưởng đến mục tiêu khác. Điều này dẫn ta đến
khái niệm điểm hữu hiệu hay còn gọi là phương án tối ưu Pareto.
Đôi khi xảy ra trường hợp một mục tiêu đạt giá trị quá cao trong khi mục tiêu khác
lại nhận được giá trị quá thấp. Trường hợp này đối với người chủ trang trại cũng là
một điều không mong muốn. Và tối ưu theo thứ tự max sẽ được sử dụng nhằm tránh
những trường hợp như thế này.
Các khái niệm về tối ưu trên ( tối ưu theo kiểu từ điển, tối ưu Pareto, tối ưu theo thứ
tự max ) sẽ được trình bày rõ hơn về mặt tốn học ở các mục sau.

2.2 Mơ hình tối ưu đa mục tiêu
Về mặt toán học, một bài toán quy hoạch đa mục tiêu (QHĐMT) có dạng:

min f ( x ) = min ( f1 ( x), f 2 ( x),..., f p ( x) ) .
x∈X

x∈X

X ⊂  n thường được cho ở dạng:

X=
{ x ∈  n : g j ( x ) ≤ 0, g j :  n → , j =1, 2,..., m}
X được gọi là tập khả thi ( feasible set ), không gian chứa X được gọi là không


gian quyết định ( decision space ), g j :  n → , j =
1, 2,..., m được gọi là các hàm
ràng buộc.

f i : X → , i =
1, 2,..., p được gọi là các

hàm mục tiêu ( objective function ),

f ( x ) = ( f1 ( x ) , f 2 ( x ) ,..., f p ( x ) ) được gọi là vectơ hàm mục tiêu ( vector objective
function ).
Ký hiệu Y = f ( X ) là ảnh của tập khả thi qua ánh xạ f được, không gian chứa Y
được gọi là không gian mục tiêu ( objective space ).

12


Từ “min” ở đây được hiểu theo nghĩa chúng ta muốn tối ưu tất cả các mục tiêu cùng
một lúc. Thực tế là các hàm mục tiêu có ràng buộc chặt chẽ nhau, một phương án để
các mục tiêu đều đạt được giá trị tốt nhất hầu như không thể tìm được. Điều này sẽ
được phân tích kỹ hơn trong mục tiếp theo.

Hình 2.2.1. Khơng gian quyết định và khơng gian mục tiêu
Căn cứ vào các hàm mục tiêu, các hàm ràng buộc, tập khả thi, ta có những loại bài
toán QHĐMT như sau:
Định nghĩa 2.2.1. Khi tất cả các hàm mục tiêu và các hàm ràng buộc của tập khả thi
là tuyến tính thì bài tốn QHĐMT được gọi là bài tốn quy hoạch tuyến tính đa mục
tiêu (QHTTĐMT).
Nếu có ít nhất một trong các hàm mục tiêu hoặc các hàm ràng buộc là phi tuyến, bài

toán QHĐMT được gọi là bài toán quy hoạch phi tuyến đa mục tiêu (QHPTĐMT).
Định nghĩa 2.2.2. Bài toán QHĐMT được gọi là bài toán QHĐMT lồi nếu tất cả
các hàm mục tiêu là hàm lồi và tập khả thi là tập lồi.

2.3 Những khó khăn đối với bài tốn tối ưu đa mục tiêu
Để làm rõ vấn đề, ta xét bài toán tối ưu với hai mục tiêu sau:

13


min ( f ( x ) , f ( x ) )
1

x∈X

2

x2 , f2 ( x ) =
1 − x, X =
Trong đó f1 ( x ) =
[ −1,1] . Với từng mục tiêu riêng rẽ ta có

min f ( x ) = 0 khi x
x∈X

1

1

min f ( x ) = 0 khi x

x∈X

2

2

=0
=1

Tuy nhiên, khơng có bất kỳ phương án x* nào thuộc X thỏa

f1 ( x* ) ≤ f1 ( x ) , f 2 ( x* ) ≤ f 2 ( x ) với mọi x ∈ X
Như vậy, câu hỏi đặt ra ở đây là như thế nào là một phương án tối ưu của một bài
tốn QHĐMT?

Hình 2.3.1. Đồ thị của các hàm số y = x 2 và y = 1 − x
Để trả lời cho câu hỏi trên, ta trở lại với bài toán QHĐMT trong trường hợp tổng
quát. Với x ∈ X , ta có f ( x ) là một vectơ trong  p . Do đó, để chỉ ra như thế nào là

14


một phương án tối ưu của bài toán QHĐMT ta cần một công cụ để so sánh các
vectơ với nhau. Thứ tự từng phần thường được sử dụng trong trường hợp này. Tuy
nhiên, đây là thứ tự khơng tồn phần, hai vectơ bất kỳ khơng phải lúc nào cũng có
thể so sánh được.

2.4 Các khái niệm tối ưu
Trước khi trình bày các khái niệm về tối ưu trong tối ưu đa mục tiêu ta nêu ra một
số

=
y1

thứ

tự

trong

không

,..., y ) , y ( y , y ,..., y ) ∈ 
( y , y=
1
1

1
2

1
p

2

2
1

2
2


2
p

p

gian

p .

Euclide

Lấy

và nếu y1 ≠ y 2 ta
đặt k *: min {k : y1k ≠ yk2 } .
=

Tên và các ký hiệu trong bảng sau sẽ được sử dụng trong luận văn này.
Ký hiệu

Định nghĩa

Tên

y1 ≤ y 2

y1k ≤ yk2 , k =
1, 2,..., p

Thứ tự từng phần yếu


y1 ≤ y 2

y1k ≤ yk2=
, k 1, 2,..., p; y1 ≠ y 2

Thứ tự từng phần

y1 < y 2

y1k < yk2 , k =
1, 2,..., p

y1 ≤

y
y ≤

2
lex y

1
k*

2
k*

Thứ tự từng phần chặt

y
or y =
1

2

Thứ tự kiểu từ điển
Thứ tự Max

1

MO

y

2

max y ≤ max yk2

1
k
=
=
k 1,...,
p
k 1,..., n

Với các thứ tự theo từng phần ( chặt, yếu ), ta định nghĩa các tập con của  p như
sau :
•

 ≥p :=
{ y ∈ R p , y ≥ 0} , nón khơng âm của  p

•

 ≥p := { y ∈ R p , y ≥ 0} =  ≥p \ {0}

•

 >p := { y ∈ R p , y > 0} = int  ≥p , nón dương của  p

15


Ta đi vào định nghĩa các phương án tối ưu trong bài toán QHĐMT
Định nghĩa 2.4.1. Điểm khả thi xˆ ∈ X được gọi là điểm hữu hiệu (efficient solution)
nếu không tồn tại x ∈ X thỏa f ( x ) ≤ f ( xˆ ) . Nếu xˆ hữu hiệu thì f ( xˆ ) được gọi là
điểm khơng trội (nondominated point). Tập tất cả các điểm hữu hiệu xˆ ∈ X ký hiệu
X E và được gọi là tập hữu hiệu (efficient set). Tập tất cả các điểm không trội
=
yˆ f ( xˆ ) ∈ Y , với xˆ ∈ X E , ký hiệu YN và được gọi là tập không trội (nondominated

set).
Một vài định nghĩa khác về điểm hữu hiệu, tuơng đương với định nghĩa trên,
thường được sử dụng trong những ngữ cảnh thích hợp sẽ được nêu ra sau đây.
xˆ ∈ X là hữu hiệu nếu

1.

Không tồn tại x ∈ X thỏa f k ( x ) ≤ f k ( xˆ ) , k = 1, 2,..., p và fi ( x ) ≤ fi ( xˆ ) với i

nào đó thuộc {1, 2,..., p} .
2.

Không tồn tại x ∈ X thỏa f ( x ) − f ( xˆ ) ∈ − ≥p \ {0}

3.

f ( x ) − f ( xˆ ) ∈  p \ ( −  ≥p \ {0} ) với mọi x ∈ X

4.

f ( X )  ( f ( xˆ ) −  ≥p ) =
{ f ( xˆ )}

5.
6.

Không tồn tại f ( x ) ∈ f ( X ) \ { f ( xˆ )} với f ( x ) ∈ f ( xˆ ) −  ≥p

f ( x ) ≤ f ( xˆ ) với x ∈ X thì f ( x ) = f ( xˆ ) .

Từ những định nghĩa trên cho ta sự mơ tả về hình học của điểm hữu hiệu và khơng
trội như trong hình 2.4.1.
Ta xét bài toán được xét ở mục 2.3

min ( f ( x ) , f ( x ) )
x∈X

1

2

16


với f1 ( x ) =
x2 , f2 ( x ) =
1 − x, X =
[ −1,1] . Để tìm ảnh của tập khả thi Y = f ( X ) trong
trường hợp này ta tính f1 theo f 2 . Ta có x =
1 − f 2 , f 2 ∈ [ 0, 2] . Suy ra

f1 =
(1 − f 2 ) 2 , f 2 ∈ [ 0, 2]

Hình 2.4.1. Sự mơ tả về mặt hình học của điểm khơng trội

Hình 2.4.2. Đồ thị mơ tả sự biểu diễn của f1 qua f 2
Như vậy, trong bài toán này ta có X E = [ 0,1] và Y=
N

17

{( x ,1 − x ) ∈  , x ∈ [0,1]}
2

2

Định nghĩa 2.4.2. Điểm xˆ ∈ X được gọi là hữu hiệu yếu ( weakly efficient ) nếu
không tồn tại x ∈ X thỏa f ( x ) < f ( xˆ ) , nghĩa là f k ( x ) < f k ( xˆ ) với mọi k = 1, p .
Khi đó, điểm yˆ = f ( xˆ ) được gọi là điểm không trội yếu ( weakly nondominated ).
Điểm xˆ ∈ X được gọi là hữu hiệu chặt ( strictly efficient ) nếu khơng có

x ∈ X , x ≠ xˆ thỏa f ( x ) ≤ f ( xˆ ) . Điểm không trội yếu, điểm hữu hiệu yếu và điểm
hữu hiệu chặt lần lượt được ký hiệu YwN , X wE , X sE .
Từ định nghĩa ta có YN ⊂ YwN và X sE ⊂ X E ⊂ X wE .

Hình 2.4.3. Sự mơ tả về mặt hình học của YwN
Như đối với điểm hữu hiệu, điểm hữu hiệu yếu cũng có một vài định nghĩa tương
đương. xˆ ∈ X được gọi là điểm hữu hiệu yếu khi và chỉ khi:
1.

Khơng có x ∈ X thỏa f ( xˆ ) − f ( x ) ∈ int  ≥p =
 >p

2.

∅
( f ( xˆ ) −  )  Y =
p
>

18


Theo định nghĩa, một điểm hữu hiệu không cho phép ta giảm giá trị của một mục
tiêu trong khi giữ lại các giá trị tương tự của các mục tiêu khác. Như vậy, giá trị của

một hoặc một vài mục tiêu giảm xuống chỉ có thể đạt được khi giá trị của ít nhất
một mục tiêu khác tăng lên. Điều này gọi là sự thỏa hiệp. Những thỏa hiệp giữa các
mục tiêu có thể được đo lường bằng việc tính tốn sự tăng lên của mục tiêu fi nói
lên phần đơn vị giảm xuống trong mục tiêu f j . Điều này đưa đến khái niệm về
điểm hữu hiệu chính thường.
Định nghĩa 2.4.3. Điểm xˆ ∈ X được gọi là hữu hiệu chính thường ( properly
efficient ) nếu nó hữu hiệu và tồn tại một số thực M > 0 sao cho với mọi cặp i và

x ∈ X thỏa fi ( x ) < fi ( xˆ ) thì tồn tại một chỉ số j thỏa f j ( xˆ ) < f j ( x ) và
fi ( xˆ ) − fi ( x )
≤M.
f j ( x ) − f j ( xˆ )
Nếu xˆ ∈ X là điểm hữu hiệu chính thường thì yˆ = f ( xˆ ) được gọi là điểm khơng
trội chính thường ( properly nondominated point ). Tập các điểm hữu hiệu chính
thường và tập các điểm khơng trội chính thường lần lượt được ký hiệu là X pE và

YpE .

2.5 Tối ưu đơn mục tiêu và đa mục tiêu: những khác biệt
Trong bài tốn tối ưu đơn mục tiêu, cơng việc chỉ là tìm một phương án tốt nhất cho
mục tiêu đó. Do đó, trong các thuật tốn của bài tốn tối ưu đơn mục tiêu, một
phương án mới sẽ được chấp nhận nếu nó có giá trị mục tiêu tốt hơn phương án cũ.
Đối với bài toán tối ưu đa mục tiêu, việc giải bài tốn thường hướng đến tìm tập
hữu hiệu. Tuy nhiên, chúng ta chỉ cần một phương án cuối cùng cho bài tốn nên sẽ
có sự chọn lựa từ những phương án nằm trong tập hữu hiệu và ở đây có sự thỏa hiệp
giữa các mục tiêu. Do đó, q trình giải bài tốn tối ưu đa mục tiêu có sự phối hợp

19

giữa nhà phân tích ( một người hoặc một chương trình máy tính chịu trách nhiệm về
mặt tốn học của bài toán ) và người ra quyết định ( một người hoặc một nhóm
người cung cấp thơng tin cho bài tốn và lựa chọn phương án sau cùng ). Đó là sự
khác biệt cơ bản của tối ưu đơn mục tiêu và đa mục tiêu.

20


Chương 3. Quy hoạch đa mục tiêu: các phương pháp giải
3.1 Phương pháp tổng trọng số ( the weighted sum method )
Ý tưởng của phương pháp là mỗi mục tiêu được nhân với một trọng số

λi ∈ , λi ≥ 0 với mọi i ∈ {1, 2,..., p} sau đó cực tiểu hóa tổng của các hàm mục tiêu
đã nhân với từng trọng số. Nghĩa là, việc giải bài toán QHĐMT

min ( f ( x ) , f ( x ) ,..., f ( x ) )
x∈X

1

2

p

được chuyển về việc giải bài tốn đơn mục tiêu có dạng:
p

min ∑ λ f ( x )
x∈X

k =1

k

(3.1.1)

k

Các trọng số ứng với mỗi mục tiêu được chọn phụ thuộc vào tầm quan trọng của
các mục tiêu trong bài toán và thường được chuẩn hóa

p

∑λ
k =1

k

= 1.

Định lý 3.1.1. Nếu xˆ là phương án tối ưu của bài tốn (3.1.1) thì xˆ ∈ X wE
Chứng minh: Ta chứng minh bằng phản chứng. Lấy xˆ là một phương án tối ưu của
bài toán (3.1.1). Giả sử xˆ khơng hữu hiệu yếu. Khi đó tồn tại x ∈ X thỏa

fi ( x ) < fi ( xˆ ) với mọi i = 1, 2,..., p . Do các trọng số λi > 0 với ít nhất một i nên
p

p

∑ λk f k ( x ) < ∑ λk f k ( xˆ ) . Điều này trái với giả thiết xˆ là phương án tối ưu của bài

k 1=
k 1
=

toán (3.1.1). Vậy xˆ ∈ X wE .



Định lý 3.1.2. Nếu xˆ là một phương án tối ưu của bài toán (3.1.1) với các trọng số
dương ( λi > 0, ∀i ∈ {1, 2,..., p} ) thì xˆ ∈ X E .

21


Chứng minh: Lấy xˆ ∈ X là một phương án tối ưu của bài toán (3.1.1) với các trọng
số dương. Giả sử xˆ không hữu hiệu. Nghĩa là tồn tại x ∈ X sao cho fi ( x ) ≤ fi ( xˆ )
với mọi

i = 1, 2,..., p

và có ít nhất một bất đẳng thức là chặt. Vì

λi > 0, ∀i ∈ {1, 2,..., p} do đó

p

p

∑ λ f ( x ) < ∑ λ f ( xˆ ) . Điều này trái với giả thiết

k k
k 1=
k 1
=

k

k

xˆ ∈ X là một phương án tối ưu của bài toán (3.1.1). Vậy xˆ là hữu hiệu.



Định lý 3.1.3. Nếu xˆ là phương án tối ưu duy nhất của bài tốn (3.1.1) thì xˆ ∈ X E .
Chứng minh: Lấy xˆ là phương án tối ưu duy nhất của bài tốn (3.1.1). Giả sử xˆ
khơng hữu hiệu. Khi đó tồn tại x ∈ X sao cho fi ( x ) ≤ fi ( xˆ ) với mọi i = 1, 2,..., p
và có ít nhất một bất đẳng thức là chặt. Do các trọng số là không âm nên ta có
p

p

∑ λ f ( x ) ≤ ∑ λ f ( xˆ ) . Do

k k
k 1=
k 1
=

k

k

nên ∀x′ ∈ X , x′ ≠ xˆ ta có

xˆ là phương án tối ưu duy nhất của bài toán (3.1.1)

p

p

∑ λ f ( xˆ ) < ∑ λ f ( x′) . Rõ ràng hai bất đẳng thức trên

k k
=
k 1=
k 1

k

k

là mâu thuẩn nhau. Vậy xˆ ∈ X E .



Định lý 3.1.4. Cho X là tập lồi, f k , k = 1, 2,..., p là các hàm lồi. Nếu xˆ ∈ X E thì tồn
p

tại λ ∈  ≥p , ∑ λk =

1 sao cho xˆ là phương án tối ưu của bài toán (3.1.1)
k =1

Chứng minh: xem Miettinen (1999) trang 89.
Theo định lý 3.1.4 tất cả các điểm hữu hiệu của bài tốn QHĐMT lồi đều có thể tìm
được thơng quan phương pháp tổng trọng số. Hình 3.1.1 cho sự diễn giải về mặt
hình học của định lý 3.1.1
Sau đây ta đưa ra mối liên hệ giữa phương án tối ưu của bài tốn (3.1.1) và điểm
hữu hiệu chính thường.

22


Hình 3.1.1. Phương pháp tổng trọng số với bài tốn lồi
Định lý 3.1.5. ( Geoffrion (1968) ). Lấy λk > 0, k =
1, 2,..., p với

p

∑λ
k =1

k

= 1 là các

trọng số dương. Nếu xˆ là phương án tối ưu của (3.1.1) thì xˆ là điểm hữu hiệu chính
thường.
Chứng minh: Lấy xˆ là một phương án tối ưu của (3.1.1). Trước tiên ta chỉ ra xˆ là
hữu hiệu. Giả sử có x′ ∈ X với f ( x′ ) ≤ f ( xˆ ) . Do các trọng số λk > 0 và

∃i ∈ {1, 2,..., p} : fi ( x′ ) < fi ( xˆ ) dẫn đến điều tương phản:
p

p

∑ λk f k ( x′) < ∑ λk f k ( xˆ )

=
k 1=
k 1

Để chỉ ra rằng xˆ hữu hiệu chính thường, lấy

M=:

( p − 1) max
i, j

23

λj
λi


Giả sử

xˆ khơng hữu hiệu chính thường. Thì có i ∈ {1, 2,..., p} và x ∈ X thỏa

fi ( x ) < fi ( xˆ ) và fi ( xˆ ) − fi ( x ) > M ( f j ( x ) − f j ( xˆ ) ) với mọi j ∈ {1, 2,..., p} thỏa

f j ( xˆ ) < f j ( x ) . Vì vậy
fi ( xˆ ) − fi ( x ) >

p −1

λi

λ j ( f j ( x ) − f j ( xˆ ) )

Với mọi j ≠ i . Suy ra

λi
p −1
⇒∑
j ≠i

( f ( xˆ ) − f ( x ) ) > λ ( f ( x ) − f ( xˆ ) )
i

λi
p −1

i

j

j

j

( f ( xˆ ) − f ( x ) ) > ∑ λ ( f ( x ) − f ( xˆ ) )
i

i

j ≠i

j

j

j

⇒ λi fi ( xˆ ) − λi fi ( x ) > ∑ λ j f j ( x ) − ∑ λ j f j ( xˆ )
j ≠i

p

j ≠i

p

⇒ ∑ λ j f j ( xˆ ) > ∑ λ j f j ( x )

=j 1 =j 1

trái với tính tối ưu của xˆ đối với bài tốn (3.1.1). Do đó xˆ là hữu hiệu chính
thường.



Định lý 3.1.6. ( Geoffrion (1968)). Cho X ⊂  n là tập lồi và f k : X →  là các
hàm lồi với k = 1, 2,..., p . Thì xˆ là hữu hiệu chính thường nếu và chỉ nếu xˆ là một
phương án tối ưu của (3.1.1) với các trọng số λk > 0, k =
1, 2,..., p .
Chứng minh: Do định lý 3.1.5 ta chỉ phải chứng minh điều kiện cần. Lấy xˆ ∈ X là
hữu hiệu chính thường. Theo định nghĩa, tồn tại số dương M thỏa với mọi
i = 1, 2,..., p hệ

24


fi ( x ) < fi ( xˆ )
fi ( x ) + Mf j ( x ) < fi ( xˆ ) + Mf j ( xˆ )

∀j ≠ i

khơng có lời giải. Theo định lý 1.2.5, tồn tại các số λki ≥ 0, k =
1, 2,..., p với
p

∑λ
k =1

i
k

= 1 sao cho với mọi x ∈ X ta có

λii fi ( x ) + ∑ λki ( fi ( x ) + Mf k ( x ) ) ≥ λii fi ( xˆ ) + ∑ λki ( fi ( xˆ ) + Mf k ( xˆ ) )

k ≠i

k ≠i

⇔ λii fi ( x ) + ∑ λki fi ( x ) + M ∑ λ ij f j ( x ) ≥ λii fi ( xˆ ) + ∑ λki fi ( xˆ ) + M ∑ λ ij f j ( xˆ )
k ≠i

j ≠i

k ≠i

p

j ≠i

p

⇔ ∑ λ fi ( x ) + M ∑ λ f j ( x ) ≥ ∑ λki fi ( xˆ ) + M ∑ λ ij f j ( xˆ )
k 1
=

i
k

j ≠i

i
j

k 1

=

j ≠i

⇔ fi ( x ) + M ∑ λ ij f j ( x ) ≥ fi ( xˆ ) + M ∑ λ ij f j ( xˆ )
j ≠i

j ≠i

Ta có bất đẳng thức như vậy với mọi i = 1, 2,..., p . Lấy tổng các bất đẳng thức đó
theo chỉ số i ta được


 p 

i
i
ˆ
ˆ
+
f
x
M
λ
f
x
 i( )
∑
∑
j j ( )  ≥ ∑  fi ( x ) + M ∑ λ j f j ( x ) 

i= 1 
j ≠i
j ≠i
 i= 1 

p

p

p

p

⇔ ∑ fi ( x ) + M ∑∑ λ f ( x ) ≥ ∑
i=
1

i
j j
i=
1 j ≠i

p

f i ( xˆ ) + M ∑∑ λ ij f j ( xˆ )

i=
1

i=

1 j ≠i

p
p




⇔ ∑ 1 + M ∑ λki  f k ( x ) ≥ ∑ 1 + M ∑ λki  f k ( xˆ )
k=
i≠k
k=
i≠k
1
1



Với mọi x ∈ X .

25