Luận văn Thạc sĩ Toán học: Quy hoạch đa mục tiêu

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

109
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Toán học: Quy hoạch đa mục tiêu nêu lên những kiến thức cơ bản và phương pháp giải bài toán quy hoạch đa mục tiêu. Mời các bạn tham khảo luận văn để nắm bắt nội dung chi tiết. Với các bạn chuyên ngành Toán học thì đây là tài liệu hữu ích.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Quy hoạch đa mục tiêu

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 =1 i ≠∅ { } 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
p Hoặc có phát biểu tương đương như sau, C i =1 i = ∅ khi và chỉ khi có một tập con n +1 { } gồm n + 1 phần tử Ci1 , Ci2 ,..., Cin +1 ⊂ {C1 , C2 ,..., C p } thỏa C ik = ∅. k =1 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 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 = i =1 i =1 Đị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 =: epif {( x, r ) ∈ D ×  : f ( x ) ≤ r} Đị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 * ≥ sup x, y * y∈Y x∈X Và sup y, y * > inf x, y * y∈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 1, 2,..., p không có lời giải thì tồn tại các số λk ≥ 0, ∑ λk = Nếu hệ f k ( x ) < 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
4 x1 x x • Số lượng nhân công: f 2 ( x ) = 10 + 5 2 + 4 3 → min 450 2000 200 x1 x x • Lượng phân bón sử dụng: f3 (= x ) 0, 215 + 4 2 + 3 3 → min 450 2000 200 • Giá bán sản phẩm: x1 x x f 4 ( x )= 8,8 × 2,3 × + 43,1× 2,526 2 + 18 × 2 × 3 → m ax 450 2000 200 • Với các ràng buộc: x1 x 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. 1, 2,..., p được gọi là các f i : X → , i = 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 ) ) x∈X 1 2 x2 , f2 ( x ) = Trong đó f1 ( x ) = [ −1,1] . Với từng mục tiêu riêng rẽ ta có 1 − x, X = min f ( x ) = 0 khi x x∈X 1 1 =0 min f ( x ) = 0 khi x x∈X 2 2 =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ố thứ tự trong không gian Euclide p . Lấy =y1 ( y , y= 1 1 ,..., y ) , y ( y , y ,..., y ) ∈  1 2 1 p 2 2 1 2 2 2 p p 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 Thứ tự từng phần chặt y1 < y 2 y1k < yk2 , k = 1, 2,..., p Thứ tự kiểu từ điển y1 ≤ lex y 2 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. Không tồn tại f ( x ) ∈ f ( X ) \ { f ( xˆ )} với f ( x ) ∈ f ( xˆ ) −  ≥p 6. 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
x2 , f2 ( x ) = với f1 ( x ) = [ −1,1] . Để tìm ảnh của tập khả thi Y = f ( X ) trong 1 − x, X = 1 − f 2 , f 2 ∈ [ 0, 2] . Suy ra trường hợp này ta tính f1 theo f 2 . Ta có x = (1 − f 2 ) 2 , f 2 ∈ [ 0, 2] f1 = 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 {( x ,1 − x ) ∈  , x ∈ [0,1]} 2 2 17
Đị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