Luận văn Thạc sĩ Toán học: Bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu hàm phân thức a - phin

Chia sẻ: Quỳnh Quỳnh | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST

Báo xấu

255
lượt xem 39
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: Bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu hàm phân thức a - phin nhằm trình bày bài toán (VP), bài toán (P) và bài toán (WP), trình bày hai phương pháp cùng với hai thuật toán giải bài toán (WP). Mời bạn đọc cùng tham khảo.

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: Bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu hàm phân thức a - phin

VI N KHOA H C VÀ CÔNG NGH VI T NAM VI N TOÁN H C HOÀNG NG C TUY BÀI TOÁN T I ƯU TRÊN T P H U HI U C A BÀI TOÁN T I ƯU ĐA M C TIÊU HÀM PHÂN TH C A-PHIN Chuyên ngành: TOÁN NG D NG Mã s : 60.46.36 LU N VĂN TH C S TOÁN H C Ngư i hư ng d n khoa h c: GS.TSKH. LÊ DŨNG MƯU HÀ N I - NĂM 2011
i M cl c M cl c i L i c m ơn iii M đ u 1 1 Các ki n th c cơ b n v t p l i, hàm l i 5 1.1 T h pl i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 T p a-phin, t p l i đa di n . . . . . . . . . . . . . . . . . . . . 7 1.3 Nón l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Đ nh lý tách các t p l i đa di n . . . . . . . . . . . . . . . . . 15 1.5 Đ nh lý minimax . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Bài toán t i ưu véc-tơ phân th c a-phin 19 2.1 Bài toán t i ưu véc-tơ . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Hàm phân th c a-phin . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Bài toán t i ưu véc-tơ phân th c a-phin . . . . . . . . . . . . 23 3 Ti p c n quy ho ch song tuy n tính gi i bài toán t i ưu trên t p h u hi u c a bài toán t i ưu đa m c tiêu phân th c a-phin 28 3.1 Bài toán t i ưu trên t p h u hi u . . . . . . . . . . . . . . . 28 3.2 Phương pháp gi i . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 Phép tính c n theo đ i ng u Lagrange . . . . . . . . 35 3.2.2 Phép chia đôi đơn hình . . . . . . . . . . . . . . . . . 39
ii 3.2.3 Thu t toán d a trên cách tính c n Lagrange (Thu t toán LB) . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3 Phương pháp n i l ng . . . . . . . . . . . . . . . . . . . . . . 43 3.3.1 Bài toán n i l ng . . . . . . . . . . . . . . . . . . . . . 43 3.3.2 Phương pháp gi i . . . . . . . . . . . . . . . . . . . . . 44 3.3.3 Thu t toán n i l ng (Thu t toán RLB) . . . . . . . . 44 3.4 Ví d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 K T LU N CHUNG 49 Tài li u tham kh o 51
iii L i c m ơn Trong su t quá trình làm lu n văn, tôi luôn nh n đư c s hư ng d n và giúp đ c a GS. Lê Dũng Mưu (Vi n Toán h c Vi t Nam). Tôi xin chân thành bày t lòng bi t ơn sâu s c đ n Th y. Tôi xin c m ơn các quý th y, cô gi ng d y t i Vi n Toán h c, đã mang đ n cho tôi nhi u ki n th c b ích trong khoa h c và cu c s ng. Tôi xin chân thành c m ơn các b n đ ng nghi p, các b n đ ng môn đã giúp đ tôi trong th i gian h c t p t i Vi n Toán h c và trong quá trình hoàn thành lu n văn này. Hà N i, tháng 8-2011 Ngư i vi t Lu n văn Hoàng Ng c Tuy
1 M đ u Bài toán t i ưu đa m c tiêu, còn đư c g i là bài toán t i ưu véc-tơ đư c n y sinh trong quá trình phát tri n c a kinh t -xã h i, ph c v cho các ho t đ ng kinh t -xã h i. Ví d , m t công ty mu n tìm m t phương án s n xu t sao cho l i nhu n cao nh t, ch t lư ng s n ph m t t nh t, giá thành s n ph m r nh t nhưng l i ít nh hư ng t i môi trư ng nh t. Vi c l a ch n phương án s n xu t c a công ty trên d n t i vi c gi i m t bài toán t i ưu đa m c tiêu. Các m c tiêu c a bài toán t i ưu véc-tơ thư ng là đ c l p v i nhau, th m chí đ i kháng nhau (ch ng h n, n u gi m chi phí s n xu t thì khó đ m b o ch t lư ng, n u tăng l i nhu n thì khó đ m b o môi trư ng...). M t phương án t t nh t cho m c tiêu này thư ng thì không t t nh t đ i v i các m c tiêu khác, t c là phương án t t nh t cho t t c các m c tiêu (phương án lý tư ng) r t hi m khi x y ra. Đi u này d n t i m t khái ni m m i v nghi m c a bài toán t i ưu đa m c tiêu là nghi m h u hi u, nghi m h u hi u y u (hay nghi m Pareto, nghi m Pareto y u). Khái ni m này đư c đưa ra t cu i th k 19, nhưng t i ưu đa m c tiêu ch tr thành m t chuyên nghành toán h c và phá tri n m nh trong vòng 40 năm g n đây. M t b ph n quan tr ng c a t i ưu đa m c tiêu là t i ưu đa m c tiêu tuy n tính. Cho đ n nay, l p các bài toán t i ưu đa m c tiêu tuy n tính đã đư c nghiên c u g n như hoàn ch nh c v phương di n đ nh tính và đ nh lư ng. M c dù bài toán t i ưu đa m c tiêu phân th c a-phin (bài toán (VP)), còn đư c g i là bài toán t i ưu véc-tơ phân th c a-phin là s m r ng t nhiên c a bài toán t i ưu đa m c tiêu tuy n tính nhưng l p các bài toán t i ưu đa m c tiêu phân th c a-phin th c s r ng hơn l p các bài toán
2 t i ưu đa m c tiêu tuy n tính. Các k t qu nghiên c u đã cho th y r ng, t p nghi m h u hi u c a bài toán (VP) khác bi t và ph c t p hơn nhi u so v i t p nghi m h u hi u c a bài toán t i ưu đa m c tiêu tuy n tính, nhi u tính ch t c a trư ng h p tuy n tính không còn đúng cho trư ng h p phân th c a-phin. Nhi u v n đ nghiên c u c a l p các bài toán (VP) v n chưa có k t qu . Trong nhi u v n đ th c t v kinh t -xã h i, ngư i ta ph i gi i bài toán t i ưu trên t p h u hi u và h u hi u y u. Ví d , m t nhà máy bánh k o s n xu t n lo i s n ph m g m m t s lo i đư ng, m t s lo i bánh k o. S lư ng các s n ph m trên là x = (x1 , x2 , ..., xn ). Nhà máy mu n tìm m t phương án s n xu t s s n ph m x sao cho thu đư c l i nhu n cao nh t. Tuy nhiên, nhà máy cũng mu n có m t phương án s n xu t sao cho đ m b o v ngu n cung c p nguyên li u lâu dài. Như v y, thay vì tìm phương án s n xu t s s n ph m x∗ trên t p các phương án s n xu t ch p nh n đư c sao cho thu đư c l i nhu n cao nh t, nhà máy ph i tìm phương án s n xu t s s n ph m x0 sao cho thu đư c l i nhu n cao nh t trên t p các phương án s n xu t đ m b o vi c cung c p nguyên li u. T t nhiên, phương án s n xu t s s n ph m x0 thư ng không cho l i nhu n cao b ng phương án s n xu t s s n ph m x∗ nhưng phương án s n xu t s s n ph m x0 đ m b o đư c ngu n cung c p nguyên li u cho nhà máy s n xu t lâu dài. Vi c tìm phương án s n xu t s s n ph m x0 chính là vi c gi i bài toán c c đ i hàm l i nhu n trên t p h u hi u c a bài toán t i ưu véc-tơ tuy n tính. Bài toán t i ưu trên t p h u hi u và h u hi u y u thu c l p các bài toán t i ưu hai c p. Bài toán này đư c đưa ra l n đ u tiên vào năm 1972 và hi n nay đang r t đư c quan tâm vì nh ng ng d ng th c t c a nó. Bài toán t i ưu trên t p h u hi u c a bài toán (VP) (bài toán (P)) và bài toán t i ưu trên t p h u hi u y u c a bài toán (VP) (bài toán (WP)) là m t d ng c a bài toán t i ưu hai c p. Bài toán (P) và bài toán (WP) cũng là s phát tri n t nhiên c a bài toán t i ưu trên t p h u hi u và h u hi u y u c a bài toán t i ưu véc-tơ tuy n tính. Trong r t nhi u các ho t đ ng
3 kinh t -xã h i trên th c t hi n nay cũng đòi h i ph i gi i bài toán này. Ví d , m t công ty bánh k o có p nhà máy (đ t t i các đ a phương khác nhau), m i nhà máy s n xu t n lo i bánh k o khác nhau. Hàm l i nhu n f (x) c a công ty ph thu c vào phương án s n xu t s lư ng s n ph m x = (x1 , x2 , ..., xn ) (n lo i bánh k o). Công ty mu n tìm m t phương án s n xu t s lư ng s n ph m x sao cho l i nhu n thu đư c là cao nh t. Đ tuân th lu t b o v môi trư ng, công ty ph i tìm m t phương án s n xu t s lư ng s n ph m x sao cho t s gi a chi phí b o v môi trư ng c a m i nhà máy và t ng chi phí c a nhà máy y là nh nh t. Như v y, thay vì tìm c c đ i hàm f (x) trên t p các phương án s n xu t ch p nh n đư c, công ty ph i th c hi n bài toán c c đ i hàm f (x) trên t p h u hi u c a bài toán t i ưu véc-tơ phân th c a-phin (s đư c trình bày chương 3), t c là, tìm phương án s n xu t s lư ng s n ph m x0 sao cho thu đư c l i nhu n cao nh t trên t p các phương án s n xu t th a mãn yêu c u v lu t b o v môi trư ng. Hi n nay, bài toán (P) và bài toán (WP) đang đư c nhi u ngư i quan tâm nhưng vi c nghiên c u các bài toán này là r t khó khăn. Bài toán t i ưu trên t p h u hi u và h u hi u y u c a bài toán t i ưu đa m c tiêu tuy n tính cũng là nh ng bài toán khó và cũng m i đư c nghiên c u nhưng đã có m t s phương pháp gi i đư c công b . Trong khi đó, m i ch có m t s r t ít ý tư ng v thu t toán và thu t toán đ tìm nghi m c a bài toán (P) và bài toán (WP) đư c công b (xem [11], [14]). Vi c nghiên c u các bài toán (P) và bài toán (WP) g p r t nhi u khó khăn b i vì t p nghi m c a bài toán (VP) thư ng là không l i, không còn là h p c a m t s m t c a đa di n ràng bu c và có c u trúc ph c t p. M t khác, s khó khăn còn do các bài toán này m i đươc nghiên c u trong th i gian g n đây. H u h t các thu t toán đư c đưa ra đ u yêu c u t t c các đ nh c a kh i đa di n ràng bu c X ph i đư c bi t trư c. Do đó, các thu t toán này ch đư c xây d ng khi các đ nh c a X d tính toán. Trong khi đó, vi c tính toán t t c các đ nh c a X thư ng là r t khó. Thu t toán n i l ng đư c trình bày chương 3 ch đòi h i bi t trư c m t đ nh c a X, t ng đ nh m i c a X có
4 th đư c tính (n u c n) trong m i bư c l p c a th t c nhánh-c n. Vì th , chúng ta có th mong r ng thu t toán này tìm th y l i gi i t i ưu toàn c c mà không c n ph i tính t t c các đ nh c a X. M c đích chính c a lu n văn này là trình bày bài toán (VP), bài toán (P) và bài toán (WP), trình bày hai phương pháp cùng v i hai thu t toán gi i bài toán (WP). Lu n văn bao g m 3 chương. Chương 1: trình bày l i m t s ki n th c cơ b n v gi i tích l i như t p l i, t p l i đa di n, nón l i... và m t s đ nh lý là đ nh lý tách các t p l i đa di n, đ nh lý minimax, đ nh lý đ i ng u Lagrange. Chương 2: trình bày bài toán (VP), trình bày m t đ nh lý c a Malivert và h qu c a đ nh lý này v đi u ki n c n và đ c a nghi m h u hi u và h u hi u y u c a bài toán (VP). Chương 3: trình bày bài toán (P) và bài toán (WP), trình bày cách chuy n hai bài toán này v d ng d kh o sát hơn là (P Λ). Sau đó, trình bày hai phương pháp đ các gi i bài toán (WP) là phương pháp tính c n theo đ i ng u Lagrange và phương pháp n i l ng. V i m i m t phương pháp, chúng ta trình bày m t thu t toán và ch ng minh tính d ng c a các thu t toán này. Lu n văn này đư c hoàn thành t i Vi n Toán h c, Vi n Khoa h c t nhiên và Công ngh qu c gia, dư i s hư ng d n c a GS.TSKH Lê Dũng Mưu. M c dù tác gi đã h t s c c g ng, nhưng do th i gian có h n và kinh nghi m nghiên c u còn r t h n ch nên khó tránh kh i thi u sót. Tác gi mong đư c các Th y, các Cô và b n đ c góp ý.
5 Chương 1 Các ki n th c cơ b n v t p l i, hàm l i Trong chương này, chúng ta trình bày l i m t s khái ni m và k t qu c a gi i tích l i. Các khái ni m và các k t qu này h u h t đư c trích d n t các tài li u [1] và [12] và đư c s d ng cho các chương sau. 1.1 T h pl i Ta ký hi u Rn là không gian Euclid n-chi u trên trư ng s th c R, m i ph n t x ∈ Rn là m t véc tơ g m n-to đ là các s th c. M t đư ng th ng n i hai đi m (hai véc-tơ) a,b trong Rn là t p h p t t c các véc-tơ x ∈ Rn có d ng {x ∈ Rn | x = αa + βb, α, β ∈ R, α + β = 1} . Đo n th ng n i hai đi m a và b trong Rn là t p h p các véc-tơ có d ng {x ∈ Rn | x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} . T p l i là m t khái ni m cơ b n nh t c a gi i tích l i, nó đư c đ nh nghĩa như sau: Đ nh nghĩa 1.1. M t t p C ⊆ Rn đư c g i là m t t p l i, n u C ch a m t đo n th ng đi qua hai đi m b t kỳ c a nó. T c là C l i khi và ch khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ) y ∈ C.
6 Ta nói x là t h p l i c a các đi m (véc-tơ) x1 , ..., xk n u k k j x= λj x , λj ≥ 0 ∀j = 1, ..., k và λj = 1. j=1 j=1 Tương t , x là t h p a-phin c a các đi m (véc-tơ) x1 , ..., xk n u k k j x= λj x v i λj = 1. j=1 j=1 M nh đ 1.1. T p h p C l i khi và ch khi nó ch a m i t h p l i c a các đi m c a nó. T c là: C l i khi và ch khi k k 1 k ∀k ∈ N, ∀λ1 , ..., λk > 0 : λj = 1, ∀x , ..., x ∈ C ⇒ λj xj ∈ C. j=1 j=1 Ch ng minh. Đi u ki n đ là hi n nhiên t đ nh nghĩa. Ta ch ng minh đi u ki n c n b ng quy n p theo s đi m. V i k = 2, đi u c n ch ng minh suy ra ngay t đ nh nghĩa c a t p l i và t h p l i. Gi s m nh đ đúng v i k − 1 đi m. Ta c n ch ng minh m nh đ đúng v i k đi m. Gi s x1 , ..., xk ∈ C là t h p l i c a k đi m. T c là k k j x= λj x , λj > 0 ∀j = 1, ..., k và λj = 1. j=1 j=1 Đ t k−1 ξ= λj . j=1 Khi đó 0 < ξ < 1 và k−1 x= λj xj + λk xk j=1 k−1 λj j =ξ x + λ k xk . ξ j=1 Do k−1 λj =1 ξ j=1
7 λj và ξ > 0 v i m i j = 1, . . . , k − 1, nên theo gi thi t quy n p, đi m k−1 λj y= ∈ C. ξ j=1 Ta có x = ξy + λk xk . Do ξ > 0, λk > 0 và k ξ + λk = λj = 1 j=1 nên x là m t t p h p l i c a hai đi m y và xk đ u thu c C. V y x ∈ C 2 L p các t p l i là đóng v i các phép giao, phép c ng đ i s và phép nhân tích Decastes. C th ta có m nh đ sau: M nh đ 1.2. N u A, B là các t p l i trong Rn , C là l i trong Rm , thì các t p sau là l i: A ∩ B := {x | x ∈ A, x ∈ B} , λA + βB := {x | x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R} , A × C := {x ∈ Rm × Rn | x = (a, c) a ∈ A, c ∈ C} . Ch ng minh. D dàng đư c suy ra tr c ti p t đ nh nghĩa. 2 1.2 T p a-phin, t p l i đa di n T p a-phin (đa t p a-phin) đư c đ nh nghĩa như sau: Đ nh nghĩa 1.2. M t t p C đư c g i là t p a-phin n u nó ch a m i đư ng th ng đi qua hai đi m b t kỳ c a nó, t c là ∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ) y ∈ C. Như v y t p a-phin là m t trư ng h p riêng c a t p l i. Các không gian con, các phiêu ph ng v.v. . . là các trư ng h p riêng c a t p a-phin. M t ví d v t p a-phin là siêu ph ng đư c đ nh nghĩa dư i đây.
8 Đ nh nghĩa 1.3. Siêu ph ng trong không gian Rn là m t t p h p các đi m có d ng x ∈ R n aT x = α . trong đó a ∈ Rn là m t véc-tơ khác 0 và a ∈ R. Véc-tơ a thư ng đư c g i là véc-tơ pháp tuy n c a siêu ph ng. M t siêu ph ng s chia không gian ra hai n a không gian. N a không gian đư c đ nh nghĩa như sau: Đ nh nghĩa 1.4. N a không gian là m t t p h p có d ng x aT x ≥ α , trong đó a = 0 và α ∈ R. T p trên là n a không gian đóng. T p x aT x > α là n a không gian m . Như v y m t siêu ph ng chia không gian ra hai n a không gian, m i n a không gian v m t phía c a siêu ph ng. N u hai n a không gian này là đóng thì ph n chung c a chúng chính là siêu ph ng. M nh đ dư i đây cho th y t p a-phin chính là t nh ti n c a m t không gian con. M nh đ 1.3. (xem [1]) M = ∅ là t p a-phin khi và ch khi nó có d ng M = L + a v i L là m t không gian con và a ∈ M . Không gian con này đư c xác đ nh duy nh t. Ch ng minh. Gi s M là t p a-phin và a ∈ M . Khi đó L = M − a là m t không gian con. V y M = L + a. Ngư c l i, n u M = L + a, v i L là không gian con, thì v i m i x, y ∈ M, λ ∈ R, ta có (1 − λ) x + λy = a + (1 − λ) (x − a) + λ (y − a) . Do x − a và y − a đ u thu c L và do L là không gian con, nên
9 (1 − λ) (x − a) + λ (y − a) ∈ L. Vy (1 − λ) x + λy ∈ M. Suy ra M là t p a-phin. Không gian con L trên là duy nh t. Th t v y, n u M = a + L và M = a + L , thì L =M −a =a+L−a =L+ a−a . Do a ∈ M = a + L, nên a − a ∈ L. Suy ra L = L + a − a = L. 2 Không gian con L trong m nh đ trên đư c g i là không gian con song song v i M, ho c nói ng n g n hơn là không gian con c a M. Th nguyên (hay chi u) c a m t t p a-phin đư c đ nh nghĩa b i th nguyên c a không gian song song v i M và đư c ký hi u là dimM. M nh đ 1.4. (xem [1]) B t kỳ m t t p a-phin M ⊂ Rn có s chi u r đ u có d ng M = {x ∈ Rn | Ax = b} , (1.1) trong đó A là ma tr n c p (m × n), b ∈ Rm và rankA = n − r. Ngư c l i m i t p h p có d ng (1.1) v i rankA = n − r đ u là t p a-phin có s chi u là r. Ch ng minh. Gi s M là t p a-phin có s chi u là r và M = L + a v i a ∈ M . V y M = L − a là m t không gian con có s chi u là r. Theo đ i s tuy n tính, không gian con r-chi u này có d ng L = {x | Ax = 0} v i A là m t ma tr n c p (m × n) và rankA = n − r. T M = L + a, suy ra M = {x | A (x − a) = 0} = {x | Ax = Aa = b} . Ngư c l i, gi s M đư c cho b i (1.1). D ki m tra đư c r ng M là m t t p a-phin và không gian con c a M là t p {x | Ax = 0}. Do rankA = n − r, nên dimL = r. V y dimM = r. 2
10 Đ nh nghĩa 1.5. Các đi m x0 , x1 , ..., xk trong Rn đư c g i là đ c l p a-phin, n u bao a-phin căng b i chúng có s chi u là k. M nh đ dư i đây cho m t tính ch t đ c trưng c a các đi m đ c l p a-phin. M nh đ 1.5. Các đi u sau đây là tương đương: (i) Các đi m x0 , x1 , ..., xk đ c l p a-phin. (ii) V i m i i, các đi m xj − xi (j = 0, 1, ..., k; j = i) đ c l p tuy n tính trong Rn . (iii) Các đi m xj , 1 (j = 0, 1, ..., k) đ c l p tuy n tính trong Rn+1 . Ch ng minh. G i S là t p h p g m các đi m x0 , x1 , ..., xk và L là không con c a S. Không gi m t ng quát, cho i = 0, đ t y j = xj − x0 (j = 1, ..., k). k Hi n nhiên y j ∈ L v i m i j. Cho x = µj xj là m t t h p a-phin b t j=0 k k kỳ c a các đi m x0 , x1 , ..., xk . Do µj = 1, nên µ0 = 1 − µj . V y x = j=0 j=1 k x0 + µj y j . Suy ra S = x0 +span y 1 , ..., y k , trong đó span y 1 , ..., y k là ký j=1 hi u c a không gian con căng b i các đi m y 1 , ..., y k . Theo m nh đ 1.3, ta có L = span y 1 , ..., y k . V y dimL = k khi và ch khi các đi m y 1 , ..., y k đ c l p tuy n tính. Ch ng t (i) và (ii) là tương đương. S tương đương gi a (ii) và (iii) d dàng đư c ch ng minh, d a tr c ti p vào đ nh nghĩa đ c l p tuy n tính. 2 Đ nh nghĩa 1.6. M t t p h p S ⊆ Rn đư c g i là m t đơn hình (simplex) có th nguyên b ng k (ho c nói ng n g n là k-đơn hình), n u S là t h p l i c a k+1 véc-tơ đ c l p a-phin. Các véc-tơ này đư c g i là đ nh c a đơn hình. Ví d m t tam giác trong không gian 3 chi u là 2-đơn hình. T p h p sau: k k Sk := x∈R |x≥0, xj ≤ 1 j=1 đư c g i là đơn hình chu n t c trong Rk .
11 Đơn hình là m t trư ng h p riêng c a t p l i đa di n. T p l i đa di n đư c đ nh nghĩa như sau. Đ nh nghĩa 1.7. M t t p đư c g i là t p l i đa di n, n u nó là giao c a m t s h u h n các n a không gian đóng. Quy ư c: Giao c a m t h r ng các n a không gian đóng là Rn . Nh n xét 1.1. . (i) Rn , ∅ là các t p l i đa di n. (ii) T p l i đa di n là t p h p nghi m c a m t h h u h n các b t phương trình tuy n tính. D ng tư ng minh c a m t t p l i đa di n đư c cho như sau: D := x ∈ Rn aj , x ≤ bj , j = 1, ..., m . đó aj ∈ Rn , j = 1, m , bj ∈ R, i = 1, m. Ho c n u ký hi u A là ma tr n có m-hàng là các véc tơ aj v i j = 1, ..., m và véc-tơ bT = (b1 , ..., bm ), thì h trên vi t đư c là: D := {x ∈ Rn | Ax ≤ b} . Chú ý r ng, do m t phương trình a, x = b có th vi t m t cách tương đương dư i d ng hai b t phương trình a, x ≤ b và −a, x ≤ b nên t p nghi m c a m t h h u h n các phương trình và b t phương trình cũng là m t t p l i đa di n. Đ nh nghĩa 1.8. T p l i D đư c g i là h u h n sinh n u nó là bao l i c a m t s h u h n các đi m và các phương, t c là t n t i các đi m x1 , ..., xk ∈ Rn và các phương v 1 , ..., v s ∈ Rn sao cho
12 k s D= x| x = λi xi + µi v i , λ1 ≥ 0, ..., λk ≥ 0, i=1 j=1 k λi = 1, µ1 ≥ 0, ..., µs ≥ 0 . i=1 Đ nh lí 1.1. (xem [12]) M t t p l i là h u h n sinh khi và ch khi nó là t p l i đa di n. Ví d 1.1. D = {x ∈ R2 | x1 ≥ 2 , 0 ≤ x2 ≤ 4} là t p l i h u h n sinh. Th t v y, 2 D = {x ∈ R2 λi xi + µv v i λ1 , λ2 ≥ 0, λ1 + λ2 = 1, µ ≥ 0}, i=1 đó x1 = (2, 0)T , x2 = (2, 4)T và v = (1, 0)T . 2 Ví d 1.2. D = {x ∈ R2 | x2 + x2 ≤ 1} không ph i là t p l i h u sinh. 1 2 1.3 Nón l i Trong nhi u b môn toán ng d ng, khái ni m v nón có m t vai trò quan tr ng. Đ nh nghĩa 1.9. M t t p C đư c g i là nón n u ∀λ > 0, ∀x ∈ C ⇒ λx ∈ C. Theo đ nh nghĩa, ta th y r ng g c to đ có th thu c nón ho c không thu c nón. Dĩ nhiên m t nón không nh t thi t là m t t p l i. Ví d C := {x ∈ R | x = 0} là m t nón, nhưng không l i. M t nón đư c g i là nón nh n n u nó không ch a đư ng th ng. Khi đó ta nói đi m 0 là đ nh c a nón. M t nón đư c g i là nón l i n u nón đó là m t t p l i. N u nón l i này l i là m t t p l i đa di n thì ta nói nó là nón
13 l i đa di n. M t ví d đi n hình c a nón l i đa di n, thư ng đư c s d ng, là t p h p nghi m c a h b t phương trình tuy n tính đ ng nh t: {x | Ax ≥ 0 } , v i A là m t ma tr n th c c p h u h n (s dòng và s c t là h u h n). M nh đ 1.6. M t t p C là nón l i khi và ch khi nó có các tính ch t sau: (i) λC ⊆ C ∀λ > 0 (ii) C + C ⊆ C Ch ng minh. Gi s C là m t nón l i. Do C là m t nón, nên ta có (i). 1 Do C là m t t p l i, nên v i m i x, y ∈ C , thì 2 (x + y) ∈ C . V y theo (i), ta có x + y ∈ C . Ngư c l i, gi s có (i) và (ii). T (i) suy ra ngay C là m t nón. Gi s x, y ∈ C và λ ∈ [0, 1]. T (i) suy ra λx ∈ C và (1 − λ) y ∈ C . Theo (ii) có λx + (1 − λ) y ∈ C . V y C là m t nón l i. 2 M t s nón đi n hình. Dư i đây ta s xét m t s nón l i đi n hình thư ng đư c s d ng trong gi i tích l i. T p l i có m t s đ c trưng là: m t tia xu t phát t m t đi m thu c nó, thì ho c n m h n trong t p này ho c m t khi đã "ra kh i" t p này thì s không “tr l i”. Đ nh nghĩa 1.10. (xem [1]) Cho C là m t t p l i trong Rn . M t véc tơ y = 0 đư c g i là hư ng lùi xa c a C, n u m i tia xu t phát t m t đi m b t kỳ c a C theo hư ng y đ u n m tr n trong C, t c là: y là hư ng lùi xa khi và ch khi x + λy ∈ C ∀x ∈ C, ∀λ ≥ 0. M t hư ng lùi xa còn đư c g i là hư ng vô h n. Ta ký hi u t p h p c a t t c các hư ng lùi xa c a C cùng v i đi m g c là reC. T p h p này đư c g i là nón lùi xa c a C. Hi n nhiên n u C là m t t p b ch n, thì reC ch g m duy nh t là đi m g c. Chú ý r ng, n u C là m t t p l i đóng, thì trong đ nh nghĩa trên, thay vì đòi h i v i m i x ∈ C, ch c n đòi h i cho m t đi m x ∈ C. C th ta có m nh đ sau:
14 M nh đ 1.7. (xem [1]) Gi s C là m t t p l i đóng. Khi đó y là m t hư ng lùi xa c a C khi và ch khi x + λy ∈ C ∀λ ≥ 0, v i m t đi m x nào đó thu c C. Ch ng minh. Gi s x + λy ∈ C ∀λ > 0, v i x ∈ C . Khi đó, v i m i u ∈ C và m i µ > C , do C l i, ta có µ µ xλ := (x + λy) + 1− u ∈ C. λ+µ λ+µ Cho λ → ∞, do C đóng, ta th y u + µy ∈ C , v i m i u ∈ C và µ > 0. 2 Chú ý. Trong trư ng h p C không đóng, b đ trên không đúng. Ví d , trong R2 l y C := {x = (x1 , x2 ) | x1 > 0, x2 > 0} ∪ {0} . Hi n nhiên véc-tơ y = (0, 1) có tính ch t là m i tia xu t phát t m t đi m 0 = x ∈ C theo hư ng này đ n n m tr n trong C, nhưng n u xu t phát t x = 0 thì đi u này không đúng. Cho C ⊆ Rn là m t t p l i và x ∈ C . Ký hi u Nc (x) := {ω | ω, y − x ≤ 0 ∀y ∈ C} . Hi n nhiên 0 ∈ NC (x). Dùng đ nh nghĩa, d ki m tra đư c r ng NC (x) là m t nón l i đóng. Nón này đư c g i là nón pháp tuy n ngoài c a C t i x. T p −NC (x) đư c g i là nón pháp tuy n trong c a C t i x. Hi n nhiên −NC (x) := {ω | ω, y − x ≥ 0 ∀y ∈ C} . M t nón quan tr ng khác là nón đ i c c đư c đ nh nghĩa như sau: C ∗ := {ω | ω, x ≤ 0 ∀x ∈ C} . Hi n nhiên đây cũng là m t nón l i đóng ch a g c.
15 Cho C là m t t p l i khác r ng và x ∈ C . Ta nói d ∈ Rn là m t hư ng ch p nh n đư c c a C n u t n t i t0 > 0 sao cho x + td ∈ C v i m i 0 ≤ t ≤ t0 . D ki m tra th y t p t t c các hư ng ch p nh n đư c là m t nón l i ch a g c. Ta ký hi u nón này là FC (x) và g i là nón các hư ng ch p nh n đư c, ho c ng n g n là nón ch p nh n đư c. Nón này có th không đóng. Tuy nhiên, n u l y bao đóng, ta s đư c m t nón khác g i là nón ti p xúc c a C t i x. Ký hi u nón này là TC (x), thì FC (x) = TC (x). T đây suy ra TC (x) = d ∈ Rn ∃dk → d, ∃tk 0 : x + tk dk ∈ C ∀k . M nh đ sau đây d ràng đư c suy ra tr c ti p t các đ nh nghĩa. M nh đ 1.8. (xem [1]) Nón pháp tuy n và nón ti p xúc là đ i c c c a nhau. Ví d . Gi s t p l i C đư c cho b i C := x ∈ Rn aj , x ≤ bj , j = 1, ..., m . V i x ∈ C, đ t J (x) := j aj , x = b j và g i J(x) là t p ch s tích c c t i x. Khi đó TC (x) = x ∈ Rn aj , x ≤ 0, j ∈ J (x) ,     NC (x) = cone aj , j ∈ J (x) = y= λj aj | λj ≥ 0 .   j∈J(x) 1.4 Đ nh lý tách các t p l i đa di n B đ 1.1. (B đ Farkas, xem [12]) Cho a0 , ..., ak là các véc-tơ thu c không gian Euclid Rn , khi đó b t đ ng th c a0 , x ≤ 0 là h qu c a h b t đ ng th c ai , x ≤ 0 (i = 1, k)
16 khi và ch khi t n t i các s λ1 ≥ 0, ..., λk ≥ 0 sao cho k a0 = λi ai . i=1 Đ nh nghĩa 1.11. (xem [12]) Cho D1 , D2 là hai t p khác r ng. (i) Ta nói siêu ph ng H tách D1 và D2 n u D1 n m trong n a không gian đóng xác đ nh b i H, còn D2 n m trong n a không gian đóng kia. (ii) Ta nói siêu ph ng H tách th c s D1 và D2 n u D1 và D2 không đ ng th i thu c H. (iii) Ta nói siêu siêu ph ng H tách m ch D1 và D2 n u t n t i ε > 0 ¯ sao cho t p D1 + εBRn n m trong n a không gian m xác đ nh b i H, còn ¯ D2 + εBRn n m trong n a không gian m kia, ¯ đây BRn = {x| x ≤ 1} là hình c u đơn v trong Rn . Nh n xét 1.2. Gi s H = {x| a, x = α} , khi đó H tách m nh D1 và D2 n u t n t i ε > 0 sao cho ¯ D1 + εBRn ⊂ {x| a, x > α} và ¯ D2 + εBRn ⊂ {x| a, x < α} . Đ nh lí 1.2. (xem [12]) N u D1 và D2 là các t p l i đa di n, khác r ng, r i nhau trong không gian Euclid h u h n chi u, thì t n t i siêu ph ng tách m nh D1 và D2 . Đ nh lí 1.3. (xem [12]) N u D1 và D2 là các t p l i, khác r ng trong Rn , thì đi u ki n c n và đ đ t n t i m t siêu ph ng tách th c s D1 và D2 là riD1 ∩ riD2 = ∅; đó riD ký hi u cho ph n trong tương đ i c a D.