Luận văn Tối ưu nhiều mục tiêu với hàm mục tiêu là hàm phân tuyến tính

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Minh Tuấn TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC TIÊU LÀ HÀM PHÂN TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh – 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Minh Tuấn TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC TIÊU LÀ HÀM PHÂN TUYẾN TÍNH Chuyên ngành: Toán giải tích Mã số: 60 46 01 02 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 – 2015 LỜI NÓI ĐẦU Ngày nay, lý thuyết tối ưu là một trong các ngành Toán học phát triển mạnh và có nhiều ứng dụng thực tế. Đây là một sự đáp ứng tích cực của Toán học trừu tượng cho nhu cầu của cuộc sống “Suy tính về một công việc sao cho nó được tiến hành tốt nhất”. Trong các bài toán thực tiễn, tiêu chuẩn “ tốt nhất” thường được dựa vào nhiều tiêu chí, đó chính là vấn đề được khảo sát trong luận văn. Luận văn gồm các phần sau: Lời nói đầu Mục lục Các ký hiệu Chương 1 Lý thuyết tối ưu nhiều mục tiêu Chương 2 Tối ưu vectơ dạng phân tuyến tính (MOLFP) Kết luận Tài liệu tham khảo Nội dung của chương 1 gồm:quan hệ hai ngôi, quan hệ thứ tự định bởi một nón, tập lồi, tập lồi đa diện, nửa liên tục trên, nửa liên tục dưới, sơ lược về bài toán tối ưu nhiều mục tiêu, định nghĩa nghiệm Pareto, nghiệm Pareto yếu, nghiệm Pareto chặt, nghiệm Pareto chính thường theo Geoffrion, Borwein, Benson của bài toán tối ưu nhiều mục tiêu và mối quan hệ giữa các định nghĩa Pareto chính thường. Nội dung của chương 2 gồm: giới thiệu bài toán qui hoạch nhiều mục tiêu phân tuyến tính theo Malivert gồm các điều kiện tối ưu, xây dựng hàm phạt cho việc kiểm tra nghiệm Pareto và nghiệm Pareto yếu, tính nửa liên tục trên, nửa liên tục dưới của hàm phạt. Tôi xin kính gởi lời cám ơn sâu sắc và chân thành nhất tới TS Trịnh Công Diệu – Khoa Toán Tin – Trường Đại Học Sư Phạm TP.Hồ Chí Minh vì sự tận tình giúp đỡ và chỉ bảo của thầy đối với tôi trong thời gian làm luận văn. Tôi cũng xin gởi lời cám ơn đến Quý Thầy Cô Trường Đại Học Sư Phạm TP.Hồ Chí Minh đã tận tình giảng dạy tôi trong suốt khóa học. Tôi xin cám ơn Ban giám hiệu, Ban chủ nhiệm khoa Toán – Tin, Phòng Khoa Học Công Nghệ và Phòng Sau Đại Học – Trường Đại Học Sư Phạm TP.Hồ Chí Minh đã giúp đỡ và tạo điều kiện cho tôi trong thời gian học tại trường. Xin gởi lời cám ơn đến quý thầy, cô trong Hội đồng chấm luận văn đã dành thời gian quý báu để đọc, chỉnh sửa, góp ý và phản biện cho tôi hoàn thành luận văn này một cách hoàn chỉnh nhất. Cuối cùng xin chân thành cảm ơn gia đình và bạn bè đã luôn quan tâm, động viên giúp tôi hoàn thành luận văn này. TP. Hồ Chí Minh, tháng 03 năm 2015 Học viên thực hiện Lê Minh Tuấn MỤC LỤC Trang CHƯƠNG 1: BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU ................................. 1 1.1 Một số khái niệm cơ bản: ......................................................................... 1 1.2 Bài toán tối ưu nhiều mục tiêu: ................................................................ 5 1.3 Các khái niệm tối ưu: ............................................................................... 6 1.3.1 Tối ưu Pareto: ........................................................................................... 6 1.3.2 Tối ưu Pareto yếu và chặt: ....................................................................... 7 CHƯƠNG 2: BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC TIÊU LÀ HÀM PHÂN TUYẾN TÍNH .......................................................... 20 2.1 Giới thiệu bài toán: ................................................................................ 20 2.2 Các điều kiện tối ưu: .............................................................................. 20 2.3 Hàm phạt: ............................................................................................... 25 2.4 Nghiệm bài toán tối ưu ........................................................................... 29 KẾT LUẬN ..................................................................................................... 34 MỘT SỐ KÝ HIỆU DÙNG TRONG LUẬN VĂN  Tập số thực ( 1=  )  Tập hợp số thực mở rộng n  Không gian Euclide n chiều trên trường số thực k + = { }k ix / x 0,i 1,..., k∈ ≥ = tập các vectơ không âm ( )m nM ×  Tập hợp các ma trận cấp m n× ∅ Tập hợp rỗng E(P) Tập hợp nghiệm Pareto của bài toán (MOLP) Ew(P) Tập hợp nghiệm Pareto yếu của bài toán (MOLP) E(P1) Tập hợp nghiệm Pareto của bài toán (P1) Ew(P1) Tập hợp nghiệm Pareto yếu của bài toán (P1) E(P2) Tập hợp nghiệm Pareto của bài toán (P2) Ew(P2) Tập hợp nghiệm Pareto yếu của bài toán (P2) u.s.c Nửa liên tục trên l.s.c Nửa liên tục dưới [ ]1 2x , x = ( ){ }n 1 2x : x 1 x x ,0 1∈ = −λ + λ ≤ λ ≤ gọi là đoạn thẳng đóng nối 1x và 2x ix Tọa độ thứ i của vectơ x Tx Vectơ hàng ( chuyển vị của x) Tx, y x y= Tích vô hướng của hai vectơ x và y ( )f x∇ Gradient của f tại x kint + Tập hợp các điểm trong của k+ 1 CHƯƠNG 1 BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU 1.1 Một số khái niệm cơ bản: Định nghĩa 1.1: Quan hệ hai ngôi Cho tập hợp A ≠ ∅ , quan hệ hai ngôi trên A là tập hợp con ℜ của A A× . Khi ( )x, y ∈ℜ ta nói x, y có quan hệ với nhau theo quan hệ ℜ và còn ghi: xℜy hoặc ℜ (x,y), nếu ( )x, y ∉ℜ ta ghi xℜy Định nghĩa 1.2 Cho ℜ là một quan hệ 2 ngôi trên tập A, ta nói ℜ có tính chất: Phản xạ nếu ( )x, x ∈ℜ với mọi x A∈ . Do đó, ℜ không có tính phản xạ ( )x A, x, x⇔ ∃ ∈ ∉ℜ . i. Đối xứng nếu x A, y A∀ ∈ ∀ ∈ ( )x y y xℜ ⇒ ℜ . ii. Phản xứng nếu và chỉ nếu: ( )x, y A, x y, x y y x∀ ∈ ≠ ℜ ⇒ ℜ . Do đó ℜ có tính phản xứng ( )( )x y y x x y⇔ ℜ ∧ ℜ ⇒ = . iii. Bắc cầu nếu x, y, z A, x y y z x z∀ ∈ ℜ ∧ ℜ ⇒ ℜ . Do đó ℜkhông có tính bắc cầu ( )x, y, z A : x y y z x z⇔ ∃ ∈ ℜ ∧ ℜ ∧ ℜ . Định nghĩa 1.3 Cho ℜ là một quan hệ 2 ngôi trên tập A khi đó: i. ℜ được gọi là một quan hệ tương đương nếu ℜ thỏa các tính chất phản xạ, đối xứng và bắc cầu. ii.ℜ được gọi là tiền thứ tự nếu ℜ có tính chất phản xạ và bắc cầu. Trong trường hợp quan hệ ℜ là tiền thứ tự thì cặp (A, ℜ ) được gọi là tập tiền thứ tự. Để thuận tiện ta thay đổi quan hệ ℜ là  . Do đó ta quy ước viết: x y thay cho x yℜ , x y thay cho x yℜ . 2 Với bất kỳ một quan hệ  là tiền thứ tự nào thì cũng có hai quan hệ khác được định nghĩa như sau: x y x y và y x x y x y và y x ⇔ ∼ ⇔      Mệnh đề 1.1 Cho  là một tiền thứ tự trên tập A. Khi đó: • Quan hệ  định nghĩa như trên là không phản xạ và bắc cầu. • Quan hệ ∼ định nghĩa như trên là quan hệ tương đương. Định nghĩa 1.4 Quan hệ hai ngôi  được gọi là quan hệ thứ tự nếu  có các tính chất: phản xạ, bắc cầu và phản xứng. Quan hệ hai ngôi  được gọi là quan hệ thứ tự từng phần nếu  có các tính chất phản xạ, bắc cầu . Trong luận văn này chúng ta sử dụng quan hệ thứ tự trên không gian Euclide_ n . Khi đó ta có một số thứ tự trên n . Ký hiệu≼ Định nghĩa Tên gọi x y≤ x y< x y Lexx y Mox y Nếu i ix y , i 1,.., n≤ ∀ = Nếu i ix y , i 1,.., n, x y≤ ∀ = ≠ Nếu i ix y , i 1,.., n< ∀ = Nếu k kx y< hoặc x y= Nếu { } { }i 1,..,n i i 1,..,n imax x max y= =≤ Thứ tự từng phần yếu Thứ tự từng phần Thứ tự từng phần chặt Thứ tự tự điển Max_thứ tự Định nghĩa 1.5 Một tập con nK ⊆  được gọi là nón nếu: x Kλ ∈ với mọi x K, , 0∈ λ∈ λ > . Ví dụ: { }2 2 iK x / x 0,i 1, 2+= = ∈ ≥ =  là nón. 3 Định nghĩa 1.6 Nón K trong n gọi là: • Không tầm thường nếu nK ≠  và K ≠ ∅ . • Lồi nếu ( )1 2tx 1 t x K+ − ∈ với mọi 1 2x , x K∈ và mọi ( )t 0,1∈ . • Nhọn nếu ( ) { }K K 0∩ − ⊂ . Mệnh đề 1.2: Cho một quan hệ thứ tự  trên n , ta định nghĩa tập: { }K y x / x y= −  . Khi đó K là nón. Chứng minh: Cho u K∈  , khi đó u y x= − với nx, y , x y∈  . Ta có: x yλ λ , với mọi 0λ > ( )u x y x y K⇒λ = λ − = λ −λ ∈ , với mọi 0λ > . Vậy K là nón.  Mệnh đề 1.3` Cho  là một quan hệ hai ngôi trên n , khi đó: i. 0 K∈  nếu  là phản xạ. ii. K lồi nếu  là bắc cầu. iii. K nhọn nếu  là phản xứng. Chứng minh: i. Giả sử quan hệ  là phản xạ. Khi đó: nx x, x 0 x x K∀ ∈ ⇒ = − ∈  . ii. Giả sử quan hệ  là bắc cầu. Cho u, v K∈  , nên u 0 K và 0 v K− ∈ − ∈−  , điều này có nghĩa là: 0 u, v 0−  kéo theo v u−  ( do  là bắc cầu). Do đó u v K+ ∈  tức K lồi. iii. Lấy 0 u K≠ ∈  thì u y x K= − ∈  và u x y K− = − ∈−  với nx, y∈ . y x và x y⇒   nên x y= (mâu thuẫn u 0≠ ). 4 Định nghĩa 1.7 Cho K là nón, ta định nghĩa quan hệ K trên n như sau: Kx y y x K⇔ − ∈ . Định nghĩa 1.8 Tập nK ⊂  được gọi là lồi nếu: ( )1 2 1 2x , x K, : 0 1 1 x x K∀ ∈ ∀λ∈ ≤ λ ≤ ⇒ −λ + λ ∈ Nhận xét: Tập rỗng là tập lồi, tập một điểm cũng là tập lồi. Định nghĩa 1.9 Cho n1 2x , x ∈ , đoạn thẳng nối 1 2x , x được định nghĩa như sau: [ ] ( ){ }n1 2 1 2x , x x : x 1 x x ,0 1= ∈ = −λ + λ ≤ λ ≤ Nhận xét: Tập K là lồi khi và chỉ khi [ ]1 2 1 2x , x K x , x K∀ ∈ ⇒ ∈ Mệnh đề 1.4: Cho K là nón và thứ tự theo nón K xác định như trên là bảo toàn với phép nhân vô hướng và cộng thông thường trong n . Ta có: 1. K là phản xạ nếu 0 K∈  . 2. K là bắc cầu nếu K lồi. 3. K là phản xứng nếu K nhọn. Chứng minh: Cho nx, y, z∈ và 0 < λ∈ . Với Kx y y x K⇔ − ∈ . Do K là nón nên : ( ) ( ) ( ) K K y x K x y y z z y z x z x z y λ − ∈ ⇒ λ λ  − = + − + ⇒ + +   1. Cho nx∈ , khi đó Kx x 0 K x x.− = ∈ ⇔  2. Cho K Kx y, y z  , khi đó y x K,z y K− ∈ − ∈ . Do K lồi nên: Ky x z y z x K x z− + − = − ∈ ⇒  3. Cho nx, y∈ với K Kx y, y x  . Khi đó ta có ( ) { }y x K, x y K y x K K 0 x y.− ∈ − ∈ ⇒ − ∈ ∩ − = ⇒ =  5 Định nghĩa 1.10 Nửa không gian đóng của n là tập hợp có dạng { }nx : a, x b∈ ≥ hay { }nx : a, x b∈ ≤ trong đó na∈ , b∈ cho trước. Định nghĩa 1.11 Tập hợp nX ⊂  được gọi là tập lồi đa diện nếu nó là giao hữu hạn của các nửa không gian đóng. Từ định nghĩa trên ta suy ra dạng biểu diễn chung của một tập lồi đa diện nX ⊂  là { }nX x : Ax b= ∈ ≥ trong đó ( ) mm nA M ,b×∈ ∈  cho trước. Ví dụ: Tập lồi đa diện ( ){ }31 1 2 3 1 2 3X x , x , x : x x x 1= ∈ + + ≤ là giao của 8 nửa không gian đóng trong đó mỗi nửa không gian đóng có dạng ( ) 3 3 1 2 3 i i 1 x , x , x : x 1 ∈ δ ≤    ∑ trong đó { }1 2 3, , 1,1δ δ δ ∈ − . Định nghĩa 1.12 Một tập lồi đa diện không rỗng và bị chặn được gọi là đa diện lồi. Định nghĩa 1.13 Cho hàm : nf →  , 0 nx ∈ , hàm f được gọi là nửa liên tục trên (u.s.c) tại 0x nếu ( ) ( ) 0 0lim supx x f x f x→ ≤ . Định nghĩa 1.14 Cho hàm : nf →  , 0 nx ∈ , hàm f được gọi là nửa liên tục dưới (l.s.c) tại 0x nếu ( ) ( ) 0 0lim infx x f x f x→ ≥ . Hàm f nửa liên tục trên (u.s.c) tại 0x và nửa liên tục dưới (l.s.c) tại 0x thì hàm f liên tục tại 0x . 6 1.2 Bài toán tối ưu nhiều mục tiêu: Ta xét bài toán tối ưu nhiều mục tiêu sau: ( )1 kx XM in f(x) f (x),..., f (x)∈ = ( )MOLP Trong đó: • ( )nif : i 1,..., k→ =  là các hàm tuyến tính • X là tập lồi đa diện trong n : { }nX x | Ax b= ∈ ≤ , A là ma trận cấp mm n,b× ∈ . X gọi là không gian quyết định. Đặt ( ) ( ){ }k 1 kY y | y f x f (x),..., f (x)= ∈ = = gọi là không gian hàm mục tiêu Định nghĩa 1.15: Một điểm *x X∈ của bài toán ( )MOLP được gọi là nghiệm lý tưởng nếu: ( ) ( )i if x * f x , x X, i 1,..., k≤ ∈ ∀ = Nói một cách khác một nghiệm lý tưởng là một nghiệm mà nó phải thỏa mãn tất cả các hàm mục tiêu cần tối ưu ứng với miền chấp nhận được là X. Thực tế thì những nghiệm như vậy rất ít khi tồn tại nên ta đưa ra một số khái niệm khác về tối ưu có vẻ “mềm dẻo” hơn đó là nghiệm tối ưu Pareto. Định nghĩa 1.16 Một nghiệm ( )1 nx x ,..., x= được gọi là trội hơn nghiệm ( )1 ny y ,..., y= ký hiệu x y≤ nếu: ( ) ( ) { } ( ) ( ) i i j j f x f y , i 1,..., k j 1,..., k : f x f y ≤ ∀ =  ∃ ∈ < 7 1.3 Các khái niệm tối ưu: 1.3.1 Tối ưu Pareto: Định nghĩa 1.17: Một điểm *x X∈ được gọi là một nghiệm tối ưu Pareto (nghiệm hữu hiệu) của bài toán ( )MOLP nếu không tồn tại *x X, x x∈ ≠ sao cho x trội hơn *x , nghĩa là: ( ) ( )*f x f x< . Ký hiệu tập hợp nghiệm Pareto của bài toán ( )MOLP là E (P). Nếu *x X∈ là một nghiệm tối ưu Pareto thì ( )*f x gọi là điểm hữu hiệu, tập tất cả các điểm hữu hiệu ký hiệu là effY . 1.3.2 Tối ưu Pareto yếu và chặt: Định nghĩa 1.18: Một điểm *x X∈ được gọi là một nghiệm tối ưu Pareto yếu (nghiệm hữu hiệu yếu) của bài toán ( )MOLP nếu không tồn tại x X∈ sao cho: ( ) ( )*f x f x . Ký hiệu tập hợp nghiệm Pareto yếu của bài toán ( )MOLP là ( )wE P . Nếu *x X∈ là một nghiệm tối ưu Pareto yếu thì ( )*f x gọi là điểm hữu hiệu yếu, tập tất cả các điểm hữu hiệu yếu ký hiệu là w effY − . Ví dụ: Xét bài toán ( ) ( ) ( ) ( ) ( ){ } 1 1 1 2 2 2 1 2 3 2 1 2 1 2 1 2 1 3 1 2 1 , : 2; , 0 xMaxf x x x x Maxf x x x Maxf x x x S x x x x x x − + = − − +  − − = + +   =  ∈ = + ≤ ≥ Trong đó ( )E P là phần gạch chéo và các đường đậm nét trong hình vẽ. Những điểm thuộc đường đứt nét và là điểm trong của S không thuộc tập ( )E P . Tập ( )wE P gồm ( )E P hợp với những điểm nằm trên đường đứt nét. Từ hình vẽ ta nhận thấy ( )E P có thể không đóng, còn ( )wE P có thể đóng. 8 Định nghĩa 1.19 Một điểm *x X∈ được gọi là một nghiệm tối ưu Pareto chặt của bài toán ( )MOLP nếu không tồn tại *x X, x x∈ ≠ sao cho: ( ) ( )*f x f x≤ . Ký hiệu tập hợp nghiệm Pareto chặt của bài toán ( )MOLP là ( )sE P . Từ định nghĩa trên ta có nhận xét: • eff w effY Y −⊂ . • ( ) ( ) ( )s wE P E P E P⊂ ⊂ . Định nghĩa 1.20: Cho nX ⊂  , một ánh xạ nf : →  và x X∈ . Khi đó: i. ( )( ) ( ) ( ){ }L f x x X | f x f x≤ = ∈ ≤ được gọi là tập mức của f tại x . ii. ( )( ) ( ) ( ){ }L f x x X | f x f x= = ∈ = được gọi là mặt mức của f tại x . iii. ( )( ) ( )( ) ( )( ) ( ) ( ){ }L f x L f x \ L f x x X | f x f x< ≤ == = ∈ < được gọi là tập mức chặt của f tại x . Định lý 1.1 Cho *x X∈ và định nghĩa ( ) { }*q qy f x ,q 1,..., k= ∈ , khi đó: i. *x là một nghiệm tối ưu Pareto chặt nếu và chỉ nếu ( ) { } k * q q 1 L y x≤ = =  . ii. *x là một nghiệm tối ưu Pareto nếu và chỉ nếu ( ) ( ) k k q q q 1 q 1 L y L y≤ = = = =   . iii. *x là một nghiệm tối Pareto yếu nếu và chỉ nếu ( ) k q q 1 L y< = = ∅  . Chứng minh: i. *x là một nghiệm tối ưu Pareto chặt ⇔ không tồn tại *x X, x x∈ ≠ sao cho: ( ) ( )*f x f x≤ ⇔ không tồn tại *x X, x x∈ ≠ sao cho: ( ) ( ) { }*q qf x f x , q 1,..., k≤ ∀ ∈ 9 ⇔ không tồn tại *x X, x x∈ ≠ sao cho: ( ) ( ) { } k k * q q q 1 q 1 x L y L y x≤ ≤ = = ∈ ⇔ =   . ii. *x là một nghiệm tối ưu Pareto ⇔ không tồn tại x X∈ sao cho: ( ) ( )*f x f x≤ và ( ) ( )*f x f x≠ ⇔ không tồn tại x X∈ sao cho: ( ) ( ) { }*q qf x f x , q 1,..., k≤ ∀ ∈ và : { } ( ) ( )*j jj 1,..., k : f x f x∃ ∈ < ⇔ không tồn tại x X∈ sao cho: ( ) k q q 1 x L y≤ = ∈  và ( )jx L y<∈ ( ) ( ) k k q q q 1 q 1 L y L y≤ = = = ⇔ =   ii. *x là một nghiệm tối Pareto yếu ⇔ không tồn tại x X∈ sao cho: ( ) ( )*f x f x ⇔ không tồn tại x X∈ sao cho: ( ) ( ) { }*q qf x f x , q 1,..., k< ∀ ∈ ⇔ không tồn tại x X∈ sao cho: ( ) k q q 1 x L y< = ∈  . ( ) k q q 1 L y< = ⇔ =∅  Định nghĩa 1.21[5](Geoffrion (1968)) *x X∈ được gọi là một nghiệm tối ưu Pareto chính thường theo Geoffrion nếu *x là nghiệm tối ưu Pareto và nếu tồn tại một số M 0> sao cho mỗi i và x X∀ ∈ thõa: ( ) ( )*i if x f x< và tồn tại chỉ số j sao cho: ( ) ( )*j jf x f x< . Hơn nữa: ( ) ( ) ( ) ( ) i i * j j f x * f x M f x f x − ≤ − . Khi đó, giá trị mục tiêu đạt được tương ứng tại *x là ( )* *y f x= gọi là điểm hữu hiệu chính thường. 10 • *x không là nghiệm tối ưu Pareto chính thường của bài toán ( )P nếu mỗi M 0> có một x X∈ và một chỉ số i sao cho: ( ) ( )*i if x f x< và ( ) ( ) ( ) ( ) * i i * j i f x f x M, j f x f x − > ∀ − sao cho ( ) ( )*j jf x f x< . Ta xét bài toán lồi sau đây: ( ) k i ix X i 1 min f x ∈ = λ∑ ( )1P Bài toán ( )1P gọi là bài toán tổng trọng số, trong đó i , i 1,..., kλ = là các trọng số không âm đối với các hàm mục tiêu và k i i 1 1 = λ =∑ . Định lý 1.2 (Geoffrion (1968)) Cho i 0, i 1,..., kλ > = với k i i 1 1 = λ =∑ . nếu *x X∈ là nghiệm tối ưu của bài toán ( )1P thì *x là nghiệm tối ưu Pareto chính thường của bài toán ( )MOLP . Chứng minh: Cho *x X∈ là nghiệm tối ưu của bài toán ( )1P . Ta muốn chứng minh: *x X∈ là nghiệm tối ưu Pareto, ta giả sử tồn tại x ' X∈ sao cho ( ) ( )*f x ' f x< , với i 0, i 1,..., kλ > = và ( ) ( ) { } ( ) ( )* *i i j jf x ' f x , i 1,..., k ; j 1,..., k : f x ' f x≤ ∀ = ∃ ∈ < dẫn đến: ( ) ( ) k k i i i i i 1 i 1 f x ' f x * = = λ < λ∑ ∑ (mâu thuẫn) Cho ( ) ( )i i, j j M k 1 max k 2λ= − ≥ λ . Giả sử *x không là nghiệm tối ưu Pareto chính thường của bài toán ( )MOLP , tức là tồn tại một i và x X∈ sao cho ( ) ( )*i if x f x< và ( ) ( ) ( ) ( )( )*i i j jf x f x M f x f x * , j i− > − ∀ ≠ với ( ) ( )j jf x * f x< . Do đó ( ) ( ) ( ) ( )( )*i i j j j i k 1f x f x f x f x * , j i−− > λ − ∀ ≠ λ 11 Nhân hai vế của bất đẳng thức trên với i k 1 λ − rồi sau đó lấy tổng hai vế như sau: ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) *i i i j j j i j j i * i i i j j j j j i j i * * i i j j i i j j j i j i k k * i i i i i 1 i 1 f x f x f x f x * k 1 f x f x f x f x * f x f x f x f x f x f x ≠ ≠ ≠ ≠ ≠ ≠ = = λ − > λ − − ⇒ λ − > λ − λ ⇒ λ + λ > λ + λ ⇒ λ > λ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ Ta gặp mâu thuẫn, điều đó nói rằng giả sử là sai, khi đó *x là nghiệm tối ưu Pareto chính thường của bài toán ( )MOLP . Định lý 1.3 Cho nX ⊂  là một tập lồi và các hàm nif : →  là các hàm lồi, i 1,..., k= . Khi đó bất đẳng thức if 0< với i 1,..., k= vô nghiệm trên X thì tồn tại i 0, i 1,..., kλ ≥ = , k i i 1 1 = λ =∑ và với mọi x X∈ thỏa mãn: ( ) k i i i 1 f x 0 = λ ≥∑ . Định lý 1.4 (Geoffrion (1968)) Cho nX ⊂  là một tập lồi và các hàm if : X → là các hàm lồi, i 1,..., k= . Khi đó *x là nghiệm tối ưu Pareto chính thường của bài toán ( )MOLP nếu và chỉ nếu *x X∈ là nghiệm tối ưu của bài toán ( )1P . Chứng minh: Do định lý 1.3, chúng ta chỉ cần chứng minh điều kiện cần. Giả sử *x là nghiệm tối ưu Pareto chính thường, ta có số M 0> sao cho mỗi { }i 1,..., k∈ hệ: ( ) ( ) ( ) ( ) ( ) ( ) * i i * * i j i j f x f x , j i f x Mf x f x Mf x  < ∀ ≠ + < + vô nghiệm. Áp dụng định 12 lý 1.3 đối với hệ trên thì tồn tại ij 0, j 1,..., kλ ≥ = , k i j j 1 1 = λ =∑ và với mọi x X∈ thỏa mãn: ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) k k i i i * i * * i i j i j i i j i j j i j i k k k k i i i i * i * i * i i j i j j i i j i j j j i j i j i j i k k k k i i i * i * j i j j j i j j j 1 j i j 1 j i k i * i * i j j i j j j i f x f x Mf x f x f x Mf x f x f x M f x f x f x M f x f x M f x f x M f x f x M f x f x M f x ≠ ≠ ≠ ≠ ≠ ≠ = ≠ = ≠ ≠ λ + λ + ≥ λ + λ + ⇒ λ + λ + λ ≥ λ + λ + λ ⇒ λ + λ ≥ λ + λ ⇒ + λ ≥ + λ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ k j i≠ ∑ Lấy tổng hai vế bất đẳng thức với biến chạy là i ta được: ( ) ( ) ( ) ( ) ( ) ( ) k k k k k k i * i * i j j i j j i 1 i 1 j i i 1 i 1 j i k k k k i i * j j j j j 1 i j j 1 i j f x M f x f x M f x 1 f x 1 f x . = = ≠ = = ≠ = ≠ = ≠ + λ ≥ + λ     ⇒ + λ ≥ + λ        ∑ ∑∑ ∑ ∑∑ ∑ ∑ ∑ ∑ Ta có thể chuẩn hóa giá trị k i j i j 1 ≠   + λ    ∑ để lấy tổng đến 1 chứa những số dương i , i 1,.., kλ = . Vậy *x là nghiệm tối ưu của bài toán ( )1P . Định nghĩa 1.22[5] Cho kY ⊂  và y Y∈ 1. Nón tiếp xúc của Y tại y Y∈ là: ( ) { } { } { } ( ){ }k k k kY k kT y d | t , y Y saocho y y, t y y d= ∈ ∃ ⊂ ⊂ → − →  2. Bao nón của Y là: ( ) { }cone Y y : 0, y