Luận văn Thạc sĩ Toán học: 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

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

Thêm vào BST

Báo xấu

90
lượt xem 7
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: 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 gồm có 2 chương. Trong đó, 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). 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: 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+ = {x ∈  k 1,..., k} tập các vectơ không âm / x i ≥ 0,i = M m× n (  ) 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(P 1 ) Tập hợp nghiệm Pareto của bài toán (P 1 ) Ew(P 1 ) Tập hợp nghiệm Pareto yếu của bài toán (P 1 ) E(P 2 ) Tập hợp nghiệm Pareto của bài toán (P 2 ) Ew(P 2 ) Tập hợp nghiệm Pareto yếu của bài toán (P 2 ) u.s.c Nửa liên tục trên l.s.c Nửa liên tục dưới [ x1 , x 2 ] = {x ∈  n : x= (1 − λ ) x1 + λx 2 , 0 ≤ λ ≤ 1} gọi là đoạn thẳng đóng nối x1 và x 2 xi Tọa độ thứ i của vectơ x xT Vectơ hàng ( chuyển vị của x) x, y = x T y Tích vô hướng của hai vectơ x và y ∇f x ( ) Gradient của f tại x int  k+ 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 Nếu x i ≤ yi , ∀i =1,.., n Thứ tự từng phần yếu x 0 . Ví dụ: K = 2+ ={x ∈  2 / x i ≥ 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 K ≠  n và K ≠ ∅ . • Lồi nếu tx1 + (1 − t ) x 2 ∈ K với mọi x1 , x 2 ∈ 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 x, y ∈ y n , 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 đó: x  x, ∀x ∈  n ⇒ 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 x, y ∈ y n . ⇒ 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: x K y ⇔ y − x ∈ K . Định nghĩa 1.8 Tập K ⊂  n được gọi là lồi nếu: ∀x1 , x 2 ∈ K, ∀λ ∈  : 0 ≤ λ ≤ 1 ⇒ (1 − λ ) x1 + λx 2 ∈ 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 x1 , x 2 ∈  n , đoạn thẳng nối x1 , x 2 được định nghĩa như sau: [ x1 , x 2 ]= {x ∈  n : x= (1 − λ ) x1 + λx 2 , 0 ≤ λ ≤ 1} Nhận xét: Tập K là lồi khi và chỉ khi ∀x1 , x 2 ∈ K ⇒ [ x1 , x 2 ] ∈ 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 x, y, z ∈ y n và 0 < λ ∈  . Với x K y ⇔ y − x ∈ K . Do K là nón nên : λ ( y − x ) ∈ K ⇒ λx K λy   y − z = ( z + y ) − ( z + x ) ⇒ z + x K z + y 1. Cho x ∈  n , khi đó x − x = 0 ∈ K ⇔ x K x. 2. Cho x K y, y K z , khi đó y − x ∈ K, z − y ∈ K . Do K lồi nên: y − x + z − y = z − x ∈ K ⇒ x K z 3. Cho x, y ∈ y n với x K y, y K 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 {x ∈  n : a, x ≥ b} hay {x ∈  n : a, x ≤ b} trong đó a ∈  n , b ∈  cho trước. Định nghĩa 1.11 Tập hợp X ⊂  n đượ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 {x ∈  n : Ax ≥ b} trong đó A ∈ M m×n (  ) , b ∈  m cho trước. X ⊂  n là X = Ví dụ: Tập lồi đa diện = X1 {( x1 , x 2 , x 3 ) ∈  3 : x1 + x 2 + x 3 ≤ 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  ( 1 2 3 )  x , x , x ∈  3 : ∑ 1 δi x i ≤ 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 f :  n →  , x0 ∈  n , hàm f được gọi là nửa liên tục trên (u.s.c) tại x0 nếu lim sup f ( x ) ≤ f ( x0 ) . x→ x 0 Định nghĩa 1.14 Cho hàm f :  n →  , x0 ∈  n , hàm f được gọi là nửa liên tục dưới (l.s.c) tại x0 nếu lim inf f ( x ) ≥ f ( x0 ) . x→ x 0 Hàm f nửa liên tục trên (u.s.c) tại x0 và nửa liên tục dưới (l.s.c) tại x0 thì hàm f liên tục tại x0 .
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: M in f(x) = ( f1 (x),..., f k (x) ) x∈X ( MOLP ) Trong đó: • fi :  n →  ( i = 1,..., k ) là các hàm tuyến tính {x ∈  n | Ax ≤ b} , A là ma trận cấp • X là tập lồi đa diện trong  n : X = m × n, b ∈  m . X gọi là không gian quyết định. {y y k | y = Đặt Y =∈ ( f1 (x),..., f k (x) )} gọi là không gian hàm mục tiêu f (x) = Đị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: f i ( x *) ≤ f i ( 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 x = ( x1 ,..., x n ) được gọi là trội hơn nghiệm y = ( y1 ,..., y n ) ký hiệu x ≤ y nếu: f i ( x ) ≤ f i ( y ) , ∀i =1,..., k  ∃j ∈ {1,..., k} : f j ( x ) < f j ( 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à Yeff . 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à E w ( 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à Yw −eff . Ví dụ: Xét bài toán  − x1 + 1  Maxf1 ( x ) = − x − x + 3  1 2  Maxf ( x ) = ( − x2 − 1)   2 x1 + 2 x2 + 1   Maxf3 ( x ) = x2   x ∈ S {( x1 , x2 ) : x1 + x2 ≤ 2; x1 , x2 ≥ 0} = 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 E w ( 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 E w ( 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à Es ( P ) . Từ định nghĩa trên ta có nhận xét: • Yeff ⊂ Yw −eff . • Es ( P ) ⊂ E ( P ) ⊂ E w ( P ) . Định nghĩa 1.20: Cho X ⊂  n , một ánh xạ f :  n →  và x ∈ X . Khi đó: ( ) { } x ∈ X | f ( x ) ≤ f ( x ) được gọi là tập mức của f tại x . i. L≤ f ( 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 ) ) = < ≤ = {x ∈ X | f ( x ) < f ( x )} được gọi là tập mức L ( f ( x )) \ L ( f ( x )) = chặt của f tại x . Định lý 1.1 Cho x* ∈ X và định nghĩa = y q f q ( x * ) , q ∈ {1,..., k} , khi đó:  L ( y ) = {x } . k i. x* là một nghiệm tối ưu Pareto chặt nếu và chỉ nếu ≤ q * q =1  L≤ ( yq ) =  L= ( yq ) . k k ii. x* là một nghiệm tối ưu Pareto nếu và chỉ nếu =q 1=q 1
9 {x * } . ⇔ không tồn tại x ∈ X, x ≠ x * sao cho: x ∈  L≤ ( y q ) ⇔  L≤ ( y q ) = k k =q 1=q 1 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: f q ( x ) ≤ f q ( x * ) , ∀q ∈ {1,..., k} và : ∃j ∈ {1,..., k} : f j ( x ) < f j ( x * ) ⇔ không tồn tại x ∈ X sao cho: x ∈  L≤ ( y q ) và x ∈ L< ( y j ) k q =1 ⇔  L≤ ( yq ) = ( yq ) k k =q 1=q 1  L= 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: f q ( x ) < f q ( x * ) , ∀q ∈ {1,..., k} ⇔ không tồn tại x ∈ X sao cho: x ∈ < L< ( y q ) . k q =1 ⇔ < L< ( yq ) = k ∅ q =1 Đị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: fi ( x ) < fi ( x* ) và tồn tại chỉ số j sao cho: f j ( x* ) < f j ( x ) . f i ( x *) − f i ( x ) Hơn nữa: ≤M. f j ( x ) − f j ( 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: fi ( x ) < fi ( x* ) và fi ( x* ) − fi ( x ) > M, ∀j sao cho f j ( x * ) < f j ( x ) . f j ( x ) − fi ( x * ) k Ta xét bài toán lồi sau đây: min ∑ λi fi ( x ) ( P1 ) x∈X i =1 Bài toán ( P1 ) gọi là bài toán tổng trọng số, trong đó λi ,i = 1,..., k là các k trọng số không âm đối với các hàm mục tiêu và ∑λ i =1 i =1 . Định lý 1.2 (Geoffrion (1968)) k Cho λi > 0,i =1,..., k với ∑λ i =1 i =1 . nếu x * ∈ X là nghiệm tối ưu của bài toán ( P1 ) 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 ( P1 ) . 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 x * ) , ∀i 1,..., k ; ∃j ∈ {1,..., k} : f j ( x ' ) < f j ( x * ) λ i > 0,i =1,..., k và f i ( x ') ≤ f i (= k k dẫn đến: i i =i 1 =i 1 ∑ λ f ( x ') < ∑ λ f ( x *) (mâu thuẫn) i i λi ( k − 1) max Cho M = ( k ≥ 2 ) . Giả sử x* không là nghiệm tối ưu Pareto i, j λj 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 f i ( x ) < f i ( x * ) và f i ( x * ) − f i ( x ) > M ( f j ( x ) − f j ( x *) ) , ∀j ≠ i với f j ( x *) < f j ( x ) . Do đó k −1 fi ( x* ) − fi ( x ) > λ j ( f j ( x ) − f j ( x *) ) , ∀j ≠ i λi
11 λi Nhân hai vế của bất đẳng thức trên với rồi sau đó lấy tổng hai vế k −1 như sau: λi ∑ k − 1 ( f ( x ) − f ( x ) ) > ∑ λ ( f ( x ) − f ( x *) ) i≠ j i * i j≠ i j j j ( ) ⇒ λ i f i ( x * ) − f i ( x ) > ∑ λ j f j ( x ) − ∑ λ j f j ( x *) j≠ i j≠ i ⇒ λ i f i ( x * ) + ∑ λ jf j ( x * ) > λ i f i ( x ) + ∑ λ jf j ( x ) j≠ i j≠ i ⇒ ∑ λi fi ( x* ) > ∑ λi fi ( x ) k k =i 1 =i 1 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 X ⊂  n là một tập lồi và các hàm fi :  n →  là các hàm lồi, i = 1,..., k . Khi đó bất đẳng thức f i < 0 với i = 1,..., k vô nghiệm trên X thì tồn tại k k λ i ≥ 0,i =1,..., k , ∑ λ i =1 và với mọi x ∈ X thỏa mãn: ∑λ f (x) ≥ 0 . i i i =1 i =1 Định lý 1.4 (Geoffrion (1968)) Cho X ⊂  n là một tập lồi và các hàm fi : 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 ( P1 ) . 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 f i ( x ) < f i ( x * ) i ∈ {1,..., k} hệ:  , ∀j ≠ i vô nghiệm. Áp dụng định f i ( x ) + Mf j ( x ) < f i ( x ) + Mf j ( x ) * *
12 k lý 1.3 đối với hệ trên thì tồn tại λij ≥ 0, j =1,..., k , ∑ λij =1 và với mọi x ∈ X thỏa j=1 mãn: λ f ( x ) + ∑ λ ( f i ( x ) + Mf j ( x ) ) ≥ λ f ( x ) + ∑ λ ij f i ( x * ) + Mf j ( x * ) ( ) k k i i i * i i j i i j≠ i j≠ i ⇒ λ ii f i ( x ) + ∑ λ ijf i ( x ) +M ∑ λ ijf j ( x ) ≥ λ ii f i ( x * ) + ∑ λ ijf i ( x * ) +M ∑ λ ijf j ( x * ) k k k k j≠ i j≠ i j≠ i j≠ i ⇒ ∑ λ ijf i ( x ) + M ∑ λ ijf j ( x ) ≥ ∑ λ ijf i ( x * ) + M ∑ λ ijf j ( x * ) k k k k =j 1 j≠ i =j 1 j≠ i ⇒ f i ( x ) + M ∑ λ ijf j ( x ) ≥ f i ( x * ) + M ∑ λ ijf j ( x * ) k k j≠ i j≠ i Lấy tổng hai vế bất đẳng thức với biến chạy là i ta được: ∑ fi ( x ) + M∑∑ λijf j ( x ) ≥ ∑ fi ( x* ) + M∑∑ λijf j ( x* ) k k k k k k i= 1 i= 1 j≠ i i= 1 i= 1 j≠ i k   k   ⇒ ∑ 1 + ∑ λ ij f j ( x ) ≥ ∑ 1 + ∑ λ ij f j ( x * ) . k k j=1 i≠ j  j=1 i≠ j   k  Ta có thể chuẩn hóa giá trị 1 + ∑ λij  để lấy tổng đến 1 chứa những số dương  i≠ j  λ i ,i = 1,.., k . Vậy x* là nghiệm tối ưu của bài toán ( P1 ) .  Định nghĩa 1.22[5] Cho Y ⊂  k và y ∈ Y 1. Nón tiếp xúc của Y tại y ∈ Y là: TY ( y ) = d ∈ yy k { | ∃{ t k } ⊂ , { y k } ⊂ Y saocho { y k } → y, t k ( y k − y ) → d } 2. Bao nón của Y là: cone ( Y ) = {αy : α ≥ 0, y ∈ Y} =  αY. α Mệnh đề 1.5[5] 1. Nón tiếp xúc TY ( y ) là một nón đóng.
13 = 2. Nếu Y là tập lồi thì TY ( y ) cl ( cone ( Y − y ) ) , chúng là nón lồi đóng. Chứng minh: 1. Ta có 0 ∈ TY ( y ) vì nếu y k= y, ∀k và TY ( y ) là một nón: cho α > 0, d ∈ TY ( y ) thì αd ∈ TY ( y ) . Lấy dãy {d l } ⊂ TY ( y ) , y ∈ Y và {d l } → d . Từ d l ∈ TY ( y ) , ∀l sẽ có những dãy {t l,k } ⊂ y, {yl,k } ⊂ Y thõa định nghĩa 1.12. Từ sự hội tụ ta cố định l, có những k l thỏa: t l,k ( y l,k − y ) − d l ≤ , ∀k ≥ k l , chúng ta cố định k l khi đó nếu l → ∞ thì dãy 1 l {t ( y l,k l l,k l } − y ) → d tức là d ∈ TY ( y ) .  2. Cho Y là tập lồi , y ∈ Y . Qua định nghĩa của bao đóng và bao nón, rõ ràng cl ( cone ( Y − y ) ) là nón lồi đóng. • Ta có: TY ( y ) ⊂ cl ( cone ( Y − y ) ) , thật vậy lấy d ∈ TY ( y ) , có dãy { t k } ⊂ y, { y k } ⊂ Y sao cho {y k } → y, t k ( y k − y ) → d . Từ t k ( y k − y ) ∈ α ( Y − y ) , α > 0 dẫn đến d ∈ cl ( cone ( Y − y ) ) . • Do TY ( y ) là tập đóng, ta chứng minh cone ( Y − y ) ⊂ TY ( y ) . Cho d ∈ cone ( Y − y ) tức là d = α ( y '− y ) với α ≥ 0, y ' ∈ Y . Ta định nghĩa y k :=1 −  y + y ' ∈ Y và t k =αk ≥ 0 . 1 1  k k  k −1  Khi đó : t k ( y k − y ) =αk   1  y + y ' − y  =α ( ( k − 1) y + y '− ky ) =α ( y '− y ) .  k k   Như vậy {y k } → y, t k ( y k − y ) → d dẫn đến d ∈ TY ( y ) . 
14 Định nghĩa 1.23[5] 1. (Borwein (1977)): Một nghiệm x ∈ X được gọi là nghiệm hữu hiệu ( chính thường theo định nghĩa Borwein nếu TY +  f ( x ) ∩ ( − k+ ) ={0} . k + ) 2. (Benson (1979)): Một nghiệm x ∈ X được gọi là nghiệm hữu hiệu ( ( )) chính thường theo định nghĩa Benson nếu cl cone Y +  k+ − f ( x ) ∩ ( − k+ ) ={0} . Định lý 1.5[5] 1. Nếu x ∈ X là nghiệm hữu hiệu chính thường theo định nghĩa Benson thì x là nghiệm hữu hiệu chính thường theo định nghĩa Borwein. 2. Nếu X là tập lồi và f k :  n →  là lồi thì cả hai định nghĩa Borwein và Benson là trùng nhau. Mệnh đề 1.6[5] Nếu x ∈ X là nghiệm hữu hiệu chính thường theo định nghĩa Borwein thì x là nghiệm hữu hiệu Pareto. Chứng minh: Giả sử x không là nghiệm hữu hiệu Pareto nên tồn tại d ∈  k+ , d ≠ 0 sao cho:=d f ( x ) − y với y ∈ Y .  1 Cho d k =1 −  d ∈  + và = t k k,= k k 1, 2,... .  k d f ( x ) − d → f ( x ) khi k → ∞ . f ( x ) − d + 1 − =  1 1 Khi đó: y + d= k  k k ( )    k 1  Và t k y + d k − f ( x ) = k  −d + 1 −  d  = −d → −d, k → ∞ .   ( ) Như vậy TY +  f ( x ) ∩ ( − k+ ) ≠ {0} , dẫn đến x không là nghiệm hữu hiệu k + chính thường theo định nghĩa Borwein (mâu thuẫn).