Tài liệu Khoá luận tốt nghiệp toán Cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc

TRƯỜNG ĐẠI HỌC s ư PH Ạ M HÀ NỘI 2 KHOA TOÁN N G U Y ỄN TH Ị VÂN CẤU TRÚC VÀ TÍNH cực TIẾU SAC YEU CỦA TẬP NGHIỆM PARETO TRONG T ố i ưu ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC K H Ó A L U Ậ N T Ố T N G H IỆ P Đ Ạ I H Ọ C C h u y ê n n g à n h : G iả i tíc h H à N ộ i - 2015 TRƯỜNG ĐẠI HỌC s ư P H Ạ M HÀ NỘI 2 KHOA TOÁN N G U Y ỄN T H Ị VÂN CẤU TRÚC VÀ TÍNH cực TIỂU SAC YEU c ủ a TẬP NGHIỆM PARETO TRONG T ố i ưu ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC K H Ó A L U Ậ N T Ố T N G H IỆ P Đ Ạ I H Ọ C C h u y ê n n g à n h : G iả i tíc h Người hướng dẫn khoa học T hS N guyễn V ăn T uyên H à N ộ i - 2015 LỜI CẢM ƠN Em xin chân th àn h cảĩii ƠĨ1 Thầy giáo Nguyễn Văn Tuyên đã tận tình hướng dẫn, giúp đỡ em trong suốt thời gian thực hiện khóa luận. Em xin chân th àn h cảrri Ơ11 các thầy, các cô trong tổ giải tích-khoa Toán, trường Đại học SƯ phạm Hà Nội 2 đã tạo rriọi điều kiện giúp đỡ erri hoàn th àn h khóa luận Iiày. Em xin chân th àn h cảrri ơn gia đình và bạn bè đã tạo rriọi điều kiện th u ân lợi cho em trong quá trình thực hiện khóa luận. E m xin chân thành cảm ơn. Hà Nội, tháng 05 năm 2015 Sinh vicn Nguyễn Thị Vân LỜI CAM Đ OAN Em xin cam đoan, dưới sự hướng dẫn của Thầy giáo Nguyễn Văn Tuyên khóa luận " C ấ u t r ú c v à t í n h cự c tiể u sắc y ế u c ủ a t ậ p n g h iệ m P a r e t o t r o n g tố i ư u đ a m ụ c tiê u tu y ế n t í n h từ n g k h ú c " được hoàn th àn h không trù n g với b ất kỳ dề tài nào khác. Trong quá trìn h hoàn th àn h khóa luận, em đã thừ a kế những th àn h tựu của các Iihà khoa học với sự trâ n trọng và biết ƠĨ1 . Hà Nội, tháng 05 năm 2015 Sinh viên Nguyễn Thị Vân M ục lục M ở đầu 1 1 3 2 B à i t o á n t ố i ưu v e c t o r 1.1. M ộ t số k h á i Iiiệm cơ b ả n .................................................................................................................. 3 1.2. Q u a n hộ h a i ngôi và q u a n hộ t h ứ tự ........................................................................................ 8 1.3. Đ iểm h ữ u h i ệ u ..................................................................................................................................... 10 1.4. Sự tồ n tạ i c ủ a đ iểm h ữ u h i ệ u ....................................................................................................... 13 1.5. B à i to á n tối Ưu v e c to r ( V O P ) 14 ....................................................................................................... C ấ u t r ú c và t ín h cự c t i ể u sắ c y ế u c ủ a t ậ p n g h i ệ m P a r e t o t r o n g t ố i Ưu đ a m ụ c t iê u t u y ế n t ín h t ừ n g k h ú c 16 2.1. Đ ặ t b à i to á n 16 2.2. C ấ u tr ú c của t ậ p n g h iệ m P a r e t o 2.3. ........................................................................................................................................ ............................................................................................... 18 2.2.1. T rư ờ n g hợ p k h ô n g lồi ........................................................................................................ 18 2.2.2. T rư ờ n g hợ p l ồ i ....................................................................................................................... ‘23 T í n h cực tiểu sắc yếu to à n cục ................................................................................................... 26 K ế t lu ậ n 30 Tài liệu t h a m k h ả o 31 MỞ ĐẦU Tối ưu đa mục ticu tuyến tính được nghicn cứu rộng rãi và được áp dụng đổ giải quyết nhiều vấn đề khác nhau trong kinh tế, tổ chức khoa học, năng lượng ... Ta biết rằng họ các hàm tuyến tính từng khúc lớn hơn họ các hàm tuyến tính và tồn tại m ột lớp rộng các hàm có thẻ xấp xỉ bằng các hàrri tuyến tính từng khúc. Vì thế việc nghiên cứu các bài toán tối ưu đa mục tiêu tuyến tính từng khúc càng có ý nghĩa quan trọng hơn. Một trong các vấn đề quan trọng Iihất khi nghiên cứu m ột bài toán tối ưu vector đó là nghiên cứu cấu trúc của tậ p nghiệm của bài toán Iiày. Định lí Arrow, Brakin và Blaclwell cổ điển (Định lí ABB) phát biểu rằng: “ Với bài toán tối ưu đa mục tiêu tuyến tính bất kì trong khôny gian định chuẩn hữu hạn chiều, tập nghiệm Pareto và Pareto yếu là hợp của hữu hạn các đa diện và liên thông đoạừ\ Gần đây Yang [14] đã đưa ra m ột số mở rộng cho định lý này cho bài toán tối ưu đa mục ticu tuyến tính từng khúc không gian định chuẩn vô hạn chiều. Một vấn đề quan trọng khác khi nghiên cứu bài toán tối ưu vector đó là nghiên cứu các th u ậ t toán để giải bài toán này. Như chúng ta đã biết, khái niệm cực tiểu sắc yếu toàn cục (global weak sharp minima) của bài toán tối ưu vô hướng được đề xuất bởi Burke và Ferris [8] và được sử dụng để chứĩig m inh tiêu chuẩn dừĩig hữu hạn của m ột vài th u ật toán, như th u ậ t toán gradien và các th u ậ t toán chiếu gradien. Sau Iiày, khái Iiiệm quan trọng này được p h át triển và áp dụng trong nhiều lĩnh vực (xem [9, 10, 11]). Một khái Iiiệm liên quan gọi là tính cực tiểu sắc cũng dược một vài tác giả nghicn cứu (xem [12]). Tính cực tiểu sắc yếu toàn cục của tập nghiệm Pareto yếu của rnột bài toán tối ưu đa mục tiêu tuyến tính trong không gian định chuẩn hữu hạn chiều được nghiên cứu bởi Deng và Yang [13]. Kết quả này được mở Khoá luận tốt nghiệp Nguyễn Thị Vân rộng trong [14] cho bài toán lồi đa mục ticu tuyến tính từng khúc trong không gian định chuẩn bằng cách sử dụng các tính chất đặc trưng của tập nghiệm P areto yếu được thiết lập trong [1]. Mục đích của khóa luận này là trình bày các kết quả trong bài báo [19]. Các kết quả Iiày là m ột mở rộng Định lí ABB cho trường hợp tập nghiệm P areto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn hữu hạn chiều và áp dụng Ĩ1 Ó dể th iết lập tính cực tiểu sắc yếu toàn cục cho một bài toán lồi đa mục tiêu tuyến tính từng khúc. Khóa luận được chia th àn h hai chương: Chương 1 giới thiệu m ột số kiến thức cơ bản về tối ưu vector. Chương 2 chúng ta chứng m inh rằng tập nghiệm Paret.o của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn hữu hạn chiều là hợp của hữu hạn các đa diện nửa đóng. Cũng trong phần này ta chỉ ra rằng, nếu hàm mục tiêu là lồi theo nón, thì tập nghiệm Pareto là hợp của hữu hạn các đa diện và liên thông đoạn. Cuối cùng, chúng ta thiết lập tính cực tiểu sắc yếu toàn cục với tập nghiệm P areto của bài toán lồi đa mục tiêu tuyến tính từng khúc. 2 C hương 1 B ài toán tố i ưu vector 1.1. Một số khái niệm cơ bản Giả sử E là Đ ịn h không gian tuyến tính, M là tập các sốthực. n g h ĩa 1.1. Tập A c E được gọi là lồi, nếu: Vx'i,x ' 2 € A\ VA 6 E : 0 ^ A ^ 1 =7* Ax‘x ~\~ (1—A)x‘ọ £ A. V í d ụ 1.1. Các nửa không gian là các tập lồi. Hình tam giác, hình tròn trong m ặt phang là các tậ p lồi. Hình cầu đơn vị trong không gian Banach là tập lồi... Đ ịn h n g h ĩa 1.2. Giả sử A c X . Tương giao của tấ t cả các tập lồi chứa A được gọi là bao lồi của tập A, kí hiệu là co Ả. N h ậ n x é t 1.1. a) coA là m ột tập lồi. Đó là tập lồi bé n h ất chứa A\ b) A lồi khi và chỉ khi A = COA. Đ ịn h n g h ĩa 1.3. Tập c c E được gọi là nón có đỉnh tại 0 nếu: V.T e c , VA > 0 => Xx e c. c được gọi là nón có đỉnh tại Xo, nếu c — Xo là nón cóđỉnh tại 0. Khoá luận tốt nghiệp Nguyễn Thị Vân Đ ịn h n g h ĩa 1.4. Nón c có đỉnh tại 0 được gọi là nón lồi, liến c là m ột tập lồi, nghĩa là: V.T, y EC, VA, n > 0 => Xx + ịẲ,y e c. V í d ụ 1.2. Các tập sau đây trong R n: { f i , Ỉ 2 , - , ỉ » e R " : í . > 0 , í = l , . . . , n} (nón o rth an t không âm) (nón o rth an t dương) là các nón lồi có đỉnh tại 0. Đó là nón lồi quan trọng trong R n. Ngoài ra, nếu cho D c là một nón lồi, nón cực dương của D được xác định bởi: D* := {x* e R m :< x \ x > ^ 0,Vx € D ) . Cho a j ) € Mm,a ^ D b khi và chỉ khi a —b G D ; a ^ 0 khi và chỉ khi (lị ^ 0, i = 1 , ra.Kí hiệu M™ := {x e M™ : .T ^ 0} và cho g : X —> R r". Hàrri g được gọilà D- giống lồi trên s c X khi và chỉ khi : Vx’i,x‘9 G s, Vtt £ [0,1], 6 5*. sao cho (1 - a )# (x i) + ac/(x2) - g(x) e D. Điều này đượcbiết đến trong [13] rằng g là m ột hàm D- giống lồi khi và chỉ khi tập g(S) + D là lồi. Đ ịn h n g h ĩa 1.5. Tập A c R n được gọi là tập affine, nếu (1 — X^x -\- \ y Á ị \ ị x , y £ A, VA (E M) 4 Khoá luận tốt nghiệp Nguyễn Thị Vân Đ ịn h n g h ĩa 1.6. Tương giao của tấ t cả các tập affine chứa tập A c R n được gọi là bao affine của Ả và kí hiệu là a f f A . Đ ịn h n g h ĩa 1.7. P hần trong tương đối của tập A c M"' là phần trong của A trong a f f A (bao affine); kí hiệu là riA Các điểm thuộc riẨ được gọi là điểm trong tương đối của tập A. N h ậ n x é t 1.2. int A := {x £ Mn : > 0, X + e№ c Ả ) , r i A := {x e 0 , f f A : 36 > 0, (x + eB) n a f f A c Ả ) , trong đó B là hình cầu đơn vị đóng trong R n. Tiếp theo chúng ta sẽ đi xem xét m ộ t số nón thường gặp Cho c là nón lồi trong không gian vector tôpô E. Kí hiệu l(C) := c n ( - C ) (phần tuyến tính của C); clc (bao đóng của ơ ); rriột tập con A c E, A c là phần bù của A trong E , nghĩa là A c = E \ A . Đ ịn h n g h ĩa 1.8. Chúng ta nói I1 ÓĨ1 c là: (a) Nhọn Iiếu l(C) = 0; (b) Nón sắc nếu bao đóng của Ĩ1 Ó là nhọn; (c) Nón có giá chặt nếu C \ l ( C ) là được chứa trong m ột nửa không gian mở th u ần Iihất; (đ) Nón đúng Iiếu (clC) + C \ l ( C ) c c , hoặc tương đương clC + C \ l ( C ) C C\ l ( C) . V í d ụ 1.3. theo định nghĩa 1.8 1. Cho Mn là không gian Euclid n-chiều. Khi đó, nón orthant không ârri Wị gồm tấ t cả các vectơr của W l với t.oạ độ không âm là nón lồi, sắc, đóng, có giá chặt và là nón đúng. 5 Khoá luận tốt nghiệp Nguyễn Thị Vân Tập {0} cũng là m ột nón, nhưng là nón tầm thường. Tập là hợp của 0 và các vector với t.oạ độ đầu tiên dương là m ột nón đúng, nhọn, có giá chặt nhưng không là nón sắc. B ất kì nửa không gian đóng thuần n h ất là nón đúng, có giá chặt nhưng không là IIÓII nhọn. 2. Cho íì là không gian vectơr gồm tấ t cả dãy X = { x n} số thực. Cho c = {x e ũ : xn ^ 0,Vn}, thì c là nón nhọn, lồi. Tuy nhicn, ta chưa biết nón c là nón đúng hoặc nón sắc vì ta chưa biết tôpô xác định trcn không gian này. 3. Nón thứ tự từ điển: Cho lp = 51 ^ p < °°- € íỉ : ||a;|| = Kí hiệu c là hợp của 0 và các dãy rrià số hạng đầu tiên khác không của dãy là dương. Đây là một, nón lồi, CÒ11 gọi là nón th ứ tự từ điển. Nó là nón nhọn nhưng không là nón đúng và cũng không phải là nón có giá chặt. M ệ n h đ ề 1.1. Nón c là đúng khi và chỉ khi một trong các các điều kiện sau thoả mãn: (a) c là đóng; (b) C \ l ( C ) là mở, khác rỗng; (c) c là hợp của 0 và giao của các nửa không gian ĨĨIỞ và nửa không gian đóng trong E. Chứng minh, (a) Hiển nhicn, (b) Nếu C \ l ( C ) mở thì i n t c Ỷ 0 và i n t c = C\ l ( C) . Do đó, ta có clC + C \ l ( C ) = (cl C) + i n t e C c , hay c là nón đúng. 6 Khoá luận tốt nghiệp Nguyễn Thị Vân (c) Giả sử С = {0} u (n { H \ : Л G Л}), ở dây H\ là nửa không gian dóng hoặc II1 Ở trong E. Nếu tấ t cả H\ là đóng thì điều này tươĩig đương với С là dóng. Do đó, ta có thể giả sử ít Iihất Iiiột nửa không gian là 1 I1 Ở thì 1(C) — {0} và b £ C \ l ( C ) khi và chỉ khi b G Hx, v \ £ Л. Hơn thế nữa, ta thấy a £ clC khi và chỉ khi a G c lH \,V A G A ncn cl Hx + H X G H\. Vậy H\ là mở hoặc đóng thì a + b e ơ , a £ с , h G C \ l ( C) . Mệnh đề được chứng minh. □ Đ ịn h n g h ĩa 1.9. Cho m ột nón с trong không gian E. Một tập в ç E sinh ra nón С và viết с — cone(B) nếu С — {tb : b G t ^ 0} . Hơn nữa, nếu В không chứa 0 và với mỗi с G с , с Ỷ 0) tồn tại duy nhất b E В, t > 0 sao cho с = tb thì в được gọi là cơ sỏ của с . Khi в là rnột tập hữu hạn, cone(conv(B)) được gọi là m ột nón đa diện. N h ậ n x é t 1.3. Rõ ràng trong không gian hữu hạn chiều m ột nón có cở sở là lồi, đóng bị chặn khi và chỉ khi nó là nhọn, đóng. Tuy nhicn nó không đúng trong không gian vô hạn chiều. M ệ n h đ ề 1.2. Nếu E là không gian Hausdorff thì một nón với một cư sở lồi, đóng bị chặn là nón đóng, nhọn vì vậy nó là nón đúng. Chứng minh. Trước hết ta chỉ ra rằng с là đóng. Cho dãy {ca } là m ột lưới từ С hội tụ tới c. Do В là m ột cơ sở ncn tồn tại m ột lưới {ba } từ в và một lưới { t a } các số dương m à ca = taba . Dễ thấy t a là bị chặn. T h ật vậy, giả sử ngược lại l i mt a = (X). Vì E là không gian Hausdorff liên lưới |/ ; tt = 7^1 hội tụ tới 0. Hơn thế nữa в là đóng, dẫn tới m âu thuẫn: 0 = limba G в . Bằng cách này, ta có thề giả sử { t a } hội tụ tới điểrn t 0 ^ 0. Nếu t 0 = 0 thì từ tính bị chặn của £>, l i mt aba = 0. Do đó с = 0 và hiển nhiên с G с . Nếu t 0 > 0, ta có thể giả sử ta > 6, Va, 6 > 0. T ừ bn = 7*'ữ ^ hôi tu tới J*0 và 7 Khoá luận tốt nghiệp hơn nữa B đóng liên vector Nguyễn Thị Vân *0 G B. Do đó c G c và c đóng nêĩi c nhon là hiển nhiên. 1.2. □ Quan hệ hai ngôi và quan hệ thứ tự Cho m ột tập hợp E tuỳ ý, rriột quan hệ hai ngôi trong E được định nghĩa bởi rnột tập coil B của tập hợp tích E X E. Điều này có nghĩa là m ột phần tử X € E có quan hệ với y (E E liến 0 ,2 /) e B. Đ ịn h n g h ĩa 1.10. Cho B là m ột quan hệ hai ngôi trong E. Ta nói quan hệ này là: xạ Iiếu ( x, x) 6 B với mọi X G E ; (a) P hản (b) Đối xứng nếu(.T, y) £ B suy ra (?/, x) G B với mỗi .T, y £ E; (c) Bắc cầu nếu (x, y) G B , ( y , z) G B suy ra (x, z) G B với X, y, z 6 B; (d) Đầy đủ hoặc licn thông nếu {x, y) G B hoặc (y,x) G B với mỗi x , y G E , x Ỷ ỉ/; (e) Tuyến tính trong trường hợp E là không gian vector thực nếu (x, y) € B suy ra (tx + z, ty + z) 6 B với mọi X, y, z G E , t > 0; (f) Đóng trong trường hợp E là không gian vcctor tôpô, nếu nó là đóng như m ột tập COĨ1 của không gian tích E X E. Để làm rõ định nghĩa này chúng ta xem xét m ột sốví dụ cổ điển san. Cho E là rriột cộng đồng dân CƯ của m ột th àn h phố và chúng ta định nghĩa quan hệ hai ngôi như sau (số dân cư được gán bởi X, y, z,...) 1. {x,y) G Bị nếu X, y là những người tuổi cao hoặc có tuổi. 2. (x, y ) (E B 2 nếu X, y là hai giới tính khác nhau. 3. (x, y) G B 3 nếu X, y là những người có họ. 8 Khoá luận tốt nghiệp Nguyễn Thị Vân Ta thấy rằng Bị là phản xạ, bắc cầu, không đối xứng, đầy đủ. B 2 không phản xạ, đối xứng, không bắc cầu, không đầy đủ. E>3 là phản xạ, khôĩig bắc cầu, đối xứng, không đầy đủ. Đ ịn h n g h ĩa 1.11. Q uan hệ hai ngôi là m ột quan hệ th ứ tự nếu nó là phản xạ, bắc cầu. T h ậ t vậy, nếu B là m ột quan hệ th ứ tự m à là tuyến tính trong m ột khôĩig gian vector thì tập c = {x G E : (x-,0) 6 B } là rriột nón lồi. Hơn nữa, nếu B là không đối xứng thì c lại, là nhọn. Ngược mỗi nón lồi trong E cho m ột quan hệ hai ngôi B c = {(.T, y) e E X E : X - y e C } là phản xạ, bắc cầu và tuyến tính. Ngoài ra, nếu c là nhọn thì Bc là không đối xứng. Bây giờ, chúng ta sẽ xét rriột vài th ứ tự sinh ra bởi các nón lồi. Đôi khi chúng ta viết: X y th ay cho X — y E c ; hoặc X ^ y nếu nó chắc chắn là quan hệ hai ngôiđược định nghĩa bởi C; X > c y nếu X y yà không phải là y hay là X (E y + C \ l ( C) . Khi ỉ n t c X, 0, x ^$>c y nghĩa là X >K y với K = {0} u i n t c . V í d ụ 1.4. 1. Cho R n và tập c = MỊ. Thì Bc là phản xạ, bắc cầu, tuyến tính, đóng, không đối xứng nhưng không đầy đủ. Cho X = (Xị , {yu-: Un) e IRn: 9 x n) , y = Khoá luận tốt nghiệp Nguyễn Thị Vân X ^ c y khi và chỉ khi Xi ^ ịji với i = 1,..., II; X >c y khi và chỉ khi Xi ^ Ui với i = 1,..., n và ít nhất một bất đẳng thức là ngặt; X ^ c y khi và chỉ khi Xi > ĩji với mọi i = 1 ,..., II. 2. Trong R 2. Nếu c = (M ^o) thì B c là phản xạ, bắc cầu, tuyến tính, đóng và đối xứng. Trong trường hợp này X y khi và chỉ khi hai th àn h phần của các vector trùng nhau. T hứ tự này không đầy đủ. 3. Nón th ứ tự từ điển là m ột quan hệ phản xạ, bắc cầu, tuyến tính đầy đủ trong lp. 1.3. Điểm hữu hiệu Cho E là không gian vector tôpô thực với quan hệ th ứ tự ( ^ ) được sinh bởi một nón lồi c . Đ ịn h n g h ĩa 1.12. Cho A là m ột tập COĨ1 khác rỗng của E. Ta nói rằng: (a) X € A là m ột điểm hữu hiệu lí tưởng (hoặc cực tiểu lí tưởng) của A tương ứng với c nếu y ^ V// £ A; Tập các điềm cực tiểu lí tưởng của A được kí hiệu là IE(A\ C); (b) X € A là điểm hữu hiệu (cực tiểu-Pareto hoặc cực tiểu) của A tương ứng với c nếu X ^ y, y £ A thì y ^ x; Tập các điổrri hữu hiộu của A kí hiộu là E(A\C)\ (c) X G A là điểm hữu hiệu thực sự (toàn cục) của A tương ứng với c Iiếu tồn tại rriột nón lồi K Ỷ E V(3i i n t K D C \ l ( C ) sao cho X £ E( A\ K) ; Tập các điổrri hữu hiộu toàn cục của A được kí hiộu là Pr E( A\ C) ; ((1) Giả sử i n t c 7^ 0, X (E -A là m ột điểm hữu hiệu yếu của A tương ứng với 10 Khoá luận tốt nghiệp Nguyễn Thị Vân c nếu X G E ( A I {0} u i n t c ); Tập các điềm hữu hiệu yếu của A kí hiệu là W E( A\ C) . V í d ụ 1.5. Cho: A = { ( ^ ỉ/) e K2 : X2 + ỉ/2 < l,ỉ/ < 0} u { ( x, y) : X > 0,0 > y > - 1 } ; B = AU { ( - 2, - 2)}. Nếu cho c = M ị, ta có: I E( B) = Pr E( B) = E( B) = WE ( B ) = { ( - 2 , -2 ) } ; I E( A) = 0, P rE (A ) = { (x , ỳ) G M2 : X2 + ý 1 = E(A) = PrE( A) u {(0, -1)} u {(-1,0)}, WE(A) = E(A) X, 0 > y } , 1, 0 > u {(x,y) : y = - l , x }. > 0 Bây giờ cho c — (M1, 0) c R 2. Ta có : I E( B) = 0, P r E ( B ) = E( B) = W E ( B ) = B, I E ( A ) = 0, P r E ( A ) = E( A) = W E ( A ) = A. Từ định nghĩa của các điềm hữu hiệu, ta có mệnh đề sau: M ệ n h đ ề 1.3. Cho A c E thì : (a) X € I E( Á) khi và chỉ khỉ X ^ A và A C x + C; (b) X 6 E( Á) khi và chỉ khi A n (x — C) c X+ l(C) hoặc tương đương: Ẹ y G A sao cho X > y. Đặc biệt khi c là nhọn, X GE( Á) A n (x —C) — khi và chỉ khi {a;}; (c) Khi c 7 ^ E , x G W E ( A ) khi và chỉ khi A c \ ( x — i n t c ) = 0 hoặc tương đương với Ịầy (E Ả sao cho X y. M ệ n h đ ề 1.4. Cho tẠp khác rỗng A c E có: 11 Khoá luận tốt nghiệp Nguyễn Thị Vân P r E ( A ) c E( A) c W E ( A ) . Hơn nữa, nếu I E( A) Ỷ 0 thì I E( A) — E( A) và nó là tập một điểm khi c là nhọn. Chứng minh. Lấy X (E Pr E ( A ) . Nếu X ị E( Á) có y ^ A v ầ x — y € C\ l { C ) . Lâý nón lồi K, K Ỷ E với i n t K c C \/(C ) và X e £ ( Ẩ |iO - Thì X — y £ i n t K c K \ l ( K ) . Điều này rnâu thuẫn với a: € ^(AỊìỷT) suy ra PrE( A) c £(Ấ). Lấy X G E(A). Nếu X Ệ W E ( A ) theo Mộnh đề 1.3 tồn tại y € A sao cho .X—y E i n t c . Do c Ỷ E, i n t c c C \ l ( C ) liên ta có X—7/ £ C \/(C ).Đ iều này m âu th u ẫn với X e E(A). Vậy i£(i4) c W E ( A ) . Rõ ràng I E ( Á ) c E( A) . Nếu I E ( Á ) Ỷ 05 ch° thì X G E(Á). Cho y 6 i£(-A) th ì ỉ/ > X vì vậy X ^ ỉ/. Lấy m ột điểm bất kì 2 € cổ z ^ X vì X G I E( A) suy ra z ^ y \k y E I E( A) . Do đó I E( A) = E(A). Ngoài ra, nếu c là nhọn X ^ ỉ/ và y > X chỉ có thể xảy ra trường hợp X — y. Vậy I E( A) là tập m ột điểm. □ Đ ịn h n g h ĩa 1.13. Cho X £ E. Tập Ẩ n ( x - C ) được gọi là rriột nhát cắt A tại X và kí hiệu Ax . M ệ n h đ ề 1.5. Cho X e E với Ax 7^ 0. Ta cỏ : (a) I E { A X) c /£ ( A ) nếu I E( A) Ỷ 0; (b) E ( A X) c ^ (A ) (tương tự cho W E ) . Chứng minh, (a) Cho J/ G I E ( A X) và 2 € I E cố Ax c y + c và Ẩ c 2 + c . Thì 2: £ i4a; vầ z — y € l ( C ) suy ra A C z -|-C = |/- |-2 — = Do đó y £ I E( A) . 12 — £/ H- C*. Khoá luận tốt nghiệp Nguyễn Thị Vân (b) Giả sử y 6 E ( A X). Theo Mệnh đề 1.4 có Ax n (y — C) c y + l(C) suy ra y —c A c X —c nên n y - c c Ả n (y - C) n (x - C) c Ax n (y - C) c y + l(C). Do đó y £ E(A). Chứng m inh tương tự cho w E . □ N h ậ n x é t 1.4. Q uan hệ P r E ( A x) c P r E ( A ) nói chung không đúng trừ một số trường hợp đặc biệt. 1.4. Sự tồn tại của điểm hữu hiệu Đ ịn h n g h ĩa 1.14. Cho lưới { x a : a G 1} từ E được gọi là lưới giảm (tương ứng với C) nếu xa > c với a, Ị3 € I; Ị3 > a. Đ ịn h n g h ĩa 1.15. Cho Ả c E đitợc gọi là C- đầy đủ (tương ứng C- đầy đủ m ạnh) nếu nó không có phủ dạng {(.7;0: — CỈCỴ : a G 1} (tương ứng {(xtt — C Ỵ : a £ /} ) với {.Ttt} là một lưới giảm trong A. Đ ịn h lý 1.1. Giả sử c là một nón lồi đúng và A là một tập khác rỗng trong E. Thì E( A\ C) Ỷ 0 khi' và chỉ khỉ A có một nhát cắt C- đầy đủ và khác rỗng. Chứng minh. Nếu E( A\ C) Ỷ 0 thì mọi điểm của tập này cho ta m ột nhát cắt C- dầy đủ vì không tồn tại lưới giảm. Ngược lại, cho Ax khác rỗng là m ột n h át cắt C- đầy đủ của A. Theo Mệnh đề 1.5 thì ta chỉ cần chứng m inh E ( A X\C) Ỷ 0- Xét tập p bao gồm tấ t cả các lưới giảm trong A. Vì A Ỷ 0 suy ra p / 0. Với a, b G p ta viết a >- b nếu b c tí. Rõ ràng (>-) là quan hộ th ứ tự trong p , và một xích bất kì trong p đều có cận trcn. T h ậ t vậy, giả sử £ A} là m ột xích trong p . Gọi B là tập tấ t cả các tập 13 Khoá luận tốt nghiệp C0Ĩ1 hữu hạn B của A Nguyễn Thị Vân được sắp thứ tự bởi bao hàm và đặt aB = u {aa; a € B} . Và ữ0 = u ! jB G 5} . Thì a0 là m ột phần tử của p và a0 y aa với mọi a 6 A Iighĩa là a0 là m ột cậĩi trên của xích Iiày. Áp dụng bổ đề Zorn, tồn tại phần tử 1ỚĨ1 Iihất của p , kí hiệu là a* = {xữ : a G 1} G p . Bây giờ, giả sử ngược lại E ( A X\C) = 0. Chúng ta sẽ chứng minh {(xa — cl CỴ : a £ 1} phủ Ax. Ta chỉ ra với mỗi y € Ax có a G / m à (xa — cl CỴ chứa y. Giả sử phản chứng y G x a —c/C ,V a £ I. Vì E ( A X\C) = 0 có z € A x với y > c z. Do tính đúng của c ncn X — a > c z , (a G /). Them 2: vào lưới a* ta th ấy rằng lưới này không thổ lớn nhất, dẫn tới m âu thuẫn. Vậy định lí được chứng minh. 1.5. □ Bài toán tối ưu vector (VOP) Cho X là Iĩiột tập COĨ1 khác rỗng của m ột không gian tôpô và m ột ánh xạ đa trị từ F là X vào E , ở đây E là không gian vector tôpô thực được sắp th ứ tự bởi nón lồi c . X ét VOP : min F(x) với ràng buộc X € X . Điểm X E X được gọi là tối ưu (cực ticu hoặc hữu hiệu) của VOP nếu F ( x ) n E { F ( X ) \ C ) ^ Q . Ỡ đây F ( X ) là hợp của các tập F(x) trên X . Các phần tử của E( F( x) \ C) được gọi là giá trị tối ưu của VOP. Tập các điểm hữu hiệu của 14