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Ĩ TOÁ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: toán giải tích
Mã số: 60.46.05
LUẬN VĂN THẠC SĨ TOÁ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 hoà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 toá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 hoà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ự yên tâm để tôi có thể hoà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 toán học là một ngành toá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 toán học, bài toá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
toá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 toá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 toá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 toá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 toá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 toán sẽ không có lời giải nếu bài toán yê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 toá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 toá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 toá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 toán QHĐMT được gọi là bài toá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 toá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
toá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 toà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 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 toá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 toá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 toán của bài toá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 toá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 toá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 đó, quá trình giải bài toá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 toá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 toá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
- Xem thêm -