Tài liệu Bài toán tối ưu đa mục tiêu tuyến tính.

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HẢI HÀ BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH Chuyên ngành: Toán ứng dụng Mã số: 62 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS. TS. Nguyễn Năng Tâm Thái Nguyên - Năm 2014 1 LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm. Tác giả xin được bày tỏ lòng biết ơn chân thành sâu sắc tới PGS. TS. Nguyễn Năng Tâm, người đã tận tình hướng dẫn về phương hướng, nội dung và phương pháp nghiên cứu trong suốt quá trình nghiên cứu, thực hiện và hoàn thành luận văn. Tác giả cũng xin gửi lời cảm ơn chân thành tới Ban Giám Hiệu Trường Đại học khoa học - Đại học Thái Nguyên, phòng sau Đại Học đã tạo điều kiện rất thuận lợi về mọi mặt cho tác giả trong quá trình tác giả học tập, nghiên cứu và hoàn thành luận văn. Thái Nguyên, tháng 10 năm 2014. Tác giả Nguyễn Thị Hải Hà 2 CÁC KÝ HIỆU THƯỜNG DÙNG Rn không gian Euclid n-chiều hx, yi tích vô hướng của x , y k.k chuẩn Euclid trong Rn intS miền trong của tập hợp S Rn+ nón orthan dương trong Rn f :X→Y Ánh xạ từ X vào Y IM in(A) Tập hữu hiệu lý tưởng của A M in(A) Tập hữu hiệu của A W M in(A) Tập hữu hiệu yếu của A (M OLP ) Bài toán tối ưu đa mục tiêu tuyến tính IS(X, f ) Tập cực tiểu lý tưởng của (MOLP) S(X, f ) Tập cực tiểu của (MOLP) W S(X, f ) Tập cực tiểu yếu của (MOLP) 3 Mục lục Mở đầu 1 1 Những kiến thức chuẩn bị 3 1.1 Tập lồi và tính chất . . . . . . . . . . . . . . . . . . . . . 3 1.2 Tập affine . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Điểm trong và điểm trong tương đối . . . . . . . . . . . . . 9 1.5 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Tính chất cực trị . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Quan hệ thứ tự từng phần và điểm hữu hiệu . . . . . . . . 11 2 Bài toán tối ưu đa mục tiêu tuyến tính 16 2.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Một số khái niệm nghiệm . . . . . . . . . . . . . . . . . . . 20 2.4 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . . . 22 2.5 Vô hướng hóa . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6 Tính chất của tập nghiệm . . . . . . . . . . . . . . . . . . 28 Kết luận 33 Mở đầu 1. Lý do chọn đề tài Tối ưu đa mục tiêu tuyến tính [2], [4], [5] có nhiều ứng dụng trong lý thuyết cũng như trong các bài toán thực tế. Lý thuyết tối ưu đa mục tiêu tuyến tính đã và đang được nhiều tác giả quan tâm nghiên cứu [4] và những tài liệu được trích dẫn trong đó. Sau một thời gian học Cao học, với mong muốn tìm hiểu sâu hơn về toán ứng dụng, tôi chọn đề tài: "Bài toán tối ưu đa mục tiêu tuyến tính" để nghiên cứu. 2. Mục đích nghiên cứu Mục đích nghiên cứu nhằm nắm được các định nghĩa, định lí, tính chất của "Bài toán tối ưu đa mục tiêu tuyến tính" và các ứng dụng của bài toán liên quan đến các vấn đề thực tiễn. Qua đó, giúp củng cố các kiến thức đã được học như: giải tích lồi trong không gian Rn , không gian affine, giải tích hàm,. . . 3. Nhiệm vụ nghiên cứu Hệ thống hoá các các kiến thức cơ sở liên quan đến bài toán. 2 Hệ thống hóa những nội dung cơ bản của bài toán "Bài toán tối ưu đa mục tiêu tuyến tính”. 4. Phương pháp nghiên cứu Sử dụng các kiến thức cơ bản của giải tích trong Rn . 5. Đóng góp của luận văn Đã trình bày được một cách tương đối có hệ thống về nội dung Bài toán tối ưu đa mục tiêu tuyến tính. 6. Cấu trúc luận văn Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận văn có 2 chương: Chương 1: Trình bày một số kiến thức cơ bản về giải tích lồi, quan hệ thứ tự từng phần và một số khái niệm điểm hữu hiệu để sử dụng trong những phần sau. Chương 2: Trình bày một số nội dung của Bài toán tối ưu đa mục tiêu tuyến tính bao gồm có sự tồn tại nghiệm, tính chất của tập nghiệm và vô hướng hóa. 3 Chương 1 Những kiến thức chuẩn bị Chương này trình bày một số khái niệm và kết quả sẽ sử dụng trong các phần sau. Nội dung trong chương này được lấy từ [1],[2],[3] và [4]. 1.1 Tập lồi và tính chất Định nghĩa 1.1. Một tập M trong không gian Rn được gọi là tập lồi nếu ∀a, b ∈ M, ∀λ ∈ [0; 1] thì: x = λa + (1 − λ) b ∈ M. Nói cách khác, nếu M là tập lồi thì nó chứa đoạn thẳng nối hai điểm bất kỳ của nó. n Nếu x ∈ R , x = n P i=1 n i λi x , λi > 0, n P λi = 1 thì x được gọi là tổ hợp lồi i=1 của x1 , x2 , ..., xn ∈ R . Mệnh đề 1.1. Tập M ⊂ Rn là lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi của các phần tử thuộc M. 4 Định lý 1.1. Nếu M , N là hai tập lồi trong Rn thì các tập sau cũng là lồi: (i) M ∩ N; (ii) λM + βN := {x = λa + βb : a ∈ M, b ∈ N ; λ, β ∈ R} . Dễ thấy, giao của một họ bất kỳ các tập lồi cũng là tập lồi. Định nghĩa 1.2. Cho S ⊂ Rn . Giao của tất cả các tập lồi trong Rn chứa S là một tập lồi và được gọi là bao lồi của S ký hiệu: convS. Rõ ràng, convS là tập lồi nhỏ nhất chứa S. Định lý 1.2. Bao lồi của tập S ⊂ Rn chứa tất cả các tổ hợp lồi của các phần tử của nó. 1.2 Tập affine Định nghĩa 1.3. Tập M ⊂ Rn được gọi là tập affine nếu ∀x, y ∈ M, t ∈ R ta có: tx + (1 − t)y ∈ M. Dễ thấy mọi tập affine đều là tập lồi. Định nghĩa 1.4. Đường thẳng đi qua 2 điểm a, b ∈ Rn là tập hợp tất cả các điểm x trong Rn có dạng: x = λa + (1 − λ) b, ∀λ ∈ R. 5 Đoạn thẳng đi qua 2 điểm a, b ∈ Rn ký hiệu là [a, b], là tập: {x ∈ Rn : x = λa + (1 − λ) b, 0 6 λ 6 1} . Định lý 1.3. Nếu M là tập affine khác rỗng trong Rn thì tồn tại không gian véc tơ con W của Rn sao cho M = a + W , trong đó a ∈ M . Định nghĩa 1.5. Nếu M là tập affine khác rỗng trong Rn và W là không gian con của Rn sao cho M = a + W , trong đó a ∈ M thì W được gọi là không gian con song song với M , số chiều của W được gọi là số chiều của tập affine M . Định nghĩa 1.6. Cho một tập S bất kỳ của Rn . Giao của tất cả các tập affine trong Rn chứa S là một tập affine. Ta gọi giao đó là bao affine của S, ký hiệu aff S. Dễ thấy aff S là tập affine nhỏ nhất chứa S. Định nghĩa 1.7. Cho a ∈ Rn , a 6= 0 và α ∈ R. Ta gọi tập: H = {x ∈ Rn : ha, xi = α} là một siêu phẳng (xác định bởi a và α). Siêu phẳng là một tập affine có số chiều bằng (n − 1) và có thể chứng minh được mọi tập affine có số chiều bằng (n − 1) đều là siêu phẳng xác định bởi a và α nào đó. Ví dụ 1.1. Trong R2 , mọi đường thẳng đều là một siêu phẳng. Trong R3 , mọi mặt phẳng đều là siêu phẳng. 6 Định nghĩa 1.8. Cho a ∈ Rn \ {0}, α ∈ R. Tập hợp x = {(x1 , x2 , . . . , xn ) ∈ Rn | ha, xi 6 α} được gọi là nửa không gian đóng. Tập hợp x = {(x1 , x2 , . . . , xn ) ∈ Rn | ha, xi < α} được gọi là nửa không gian mở. 1.3 Tập lồi đa diện Định nghĩa 1.9. Tập lồi đa diện là giao của một số hữu hạn các nửa không gian đóng. Nói cách khác, tập lồi đa diện là tập nghiệm của một hệ bất đẳng thức tuyến tính có dạng: hai , xi 6 bi , i = 1, 2, ..., n, trong đó ai ∈ Rn , bi ∈ R. Một tập lồi đa diện bị chặn thì được gọi là đa diện lồi . Một tập lồi đa diện là bao lồi của một số hữu hạn điểm và một số hữu hạn đoạn thẳng. Một đa diện lồi là bao lồi của một số hữu hạn điểm. Cho một tập lồi đa diện M , tập con F ⊂ M được gọi là diện nếu: x ∈ F, a, b ∈ M, 0 < λ < 1, x = λa + (1 − λ) b ∈ F ⇒ a, b ∈ F. 7 Nói cách khác, F là một diện của M nếu F chứa một điểm trong (hoặc điểm tương đối) của một đoạn thẳng nào đó của M thì F chứa trọn cả đoạn thẳng đó. Một diện có thứ nguyên là 0 được gọi là một đỉnh hay điểm cực biên, cạnh là diện có thứ nguyên bằng 1. Cho C là một tập lồi đa diện, một điểm x0 ∈ C được gọi là điểm cực biên (hay đỉnh) nếu nó không chứa bất kỳ một đoạn thẳng nào của C nhận x0 làm điểm trong của đoạn thẳng đó, tức là không tồn tại 2 điểm phân biệt a, b ∈ C sao cho: x0 = λa + (1 − λ) b, 0 < λ < 1. Với tập lồi đa diện, một đỉnh của diện cũng chính là đỉnh của tập đó. Một tập hữu hạn (n+1) điểm u0 , u1 , u2 , ..., un ∈ Rn được gọi là độc lập affine khi và chỉ khi (u1 − u0 ), (u2 − u1 ), ..., (un − u0 ) là độc lập tuyến tính. Nếu (n+1) điểm u0 , u1 , u2 , ..., un ∈ Rn là độc lập affine thì bao lồi của nó được gọi là một n-đơn hình với các đỉnh u0 , u1 , u2 , ..., un . Định lý 1.4. Cho S ⊂ Rn và ánh xạ f : S → Rn . Khi đó, nếu S là tập lồi và f là ánh xạ tuyến tính thì ảnh f (S) của S qua ánh xạ f cũng là tập lồi . Nhắc lại rằng có thể đồng nhất ma trận C cấp (m × n) chính là ánh xạ tuyến tính từ Rn → Rm . Xét ánh xạ tuyến tính f : Rn → Rm , ta có định lý sau: Định lý 1.5. Nếu X là tập lồi đa diện thì f (X) cũng là tập lồi đa diện. 8 Hơn nữa, nếu X là đa diện lồi thì f (X)là bao lồi của ảnh các đỉnh của X. Định nghĩa 1.10. Tập K ⊂ Rn được gọi là một nón đỉnh a nếu: ∀x ∈ K, ∀λ > 0 thì xλ = a + λ (x − a) ∈ K. Nếu K là nón với đỉnh a = 0 thì ta nói đơn giản K là một nón. Định nghĩa 1.11. Cho B ⊂ Rn và K là một nón trong K ⊂ Rn . Ta nói B sinh ra nón K và viết K = cone(B) nếu K = {tb | b ∈ B, t ≥ 0}. Nếu 0 ∈ / B và với mọi c ∈ K, c 6= 0 tồn tại duy nhất b ∈ B, t > 0 sao cho c = tb thì ta nói B là một đáy của K. Khi B là tập hữu hạn, cone(conv(B)) được gọi là nón đa diện. Định nghĩa 1.12. Nón lùi xa của tập X ⊆ Rn , X 6= ∅ là nón : Re c (X) = ∩ {clcone (X ∩ V ) : V ⊂ B} . Với B là lọc của điểm vô cùng ∞. Mệnh đề 1.2. [4] Cho X ⊂ Rn . Khi đó, véc tơ a ∈ Rec(X) khi và chỉ khi với mọi V có dạng Rn \ W với W là tập đóng và lân cận mở U của 0 trong Rn ta có: cone(a + U ) ∩ X ∩ V 6= ∅. 9 1.4 Điểm trong và điểm trong tương đối Định nghĩa 1.13. Cho tập A bất kỳ, một điểm x0 gọi là điểm trong của A nếu: ∃ε > 0 : B (x0 , ε) = {x ∈ Rn : kx − x0 k < ε} ⊂ A. Tập hợp các điểm trong của tập A được ký hiệu là intA. Điểm x0 được gọi là điểm trong tương đối nếu ∃ε > 0 : B (x0 , ε) ∩ af f A ⊂ A. Ký hiệu: ri A là tập tất cả các điểm trong tương đối của A. Định nghĩa 1.14. Giả sử A là tập lồi trong Rn , véc tơ y 6= 0 được gọi là hướng lùi xa của A nếu : ∀x ∈ A, ∀λ > 0 : x + λy ∈ A. Tập hợp tất cả các hướng lùi xa của A và vec tơ 0 lập thành một nón và gọi là nón lùi xa của A và được ký hiệu là Rec(A). Định lý 1.6. (i) Mọi tập lồi đa diện không chứa trọn một đường thẳng đều có ít nhất một đỉnh; (ii) Mọi tập lồi đa diện A có đỉnh bằng tập hợp các x có dạng : x= X i∈I trong đó: P λi ai + X βj bj . j∈J λi = 1 , λi ; βj > 0 , ∀i, j ; ai là các đỉnh, bj là phương của i∈I các cạnh vô hạn của A. Nói cách khác, A = D + Rec(A) trong đó D là một đa diện. 10 Định nghĩa 1.15. i) Hai tập khác rỗng A, B ⊂ Rn là được tách bởi siêu phẳng P = {x ∈ Rn : ha, xi = α, a ∈ Rn \ {0} , α ∈ R} nếu inf ha, xi > α > sup ha, yi ; x∈A y∈B ii) Hai tập A, B được gọi là tách mạnh (tách hẳn , tách chặt) bởi siêu phẳng P = {x ∈ Rn : ha, xi = α, a ∈ Rn \ {0} , α ∈ R} nếu inf ha, xi > α > sup ha, yi . x∈A y∈B Định lý 1.7. Cho A là một tập lồi đóng và x0 ∈ / A. Lúc đó tồn tại một siêu phẳng tách hẳn A và x0 . 1.5 Hàm lồi Định nghĩa 1.16. Một hàm f xác định trên tập lồi A được gọi là hàm lồi trên A nếu ∀x, y ∈ A, 0 6 λ 6 1 ta có : f (λx + (1 − λ) y) 6 λf (x) + (1 − λ) f (y) . Hàm f được gọi là lồi chặt nếu : f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) ; 11 ∀x, y ∈ A, 0 < λ < 1. Hàm f được gọi là lõm (lõm chặt) nếu -f lồi (lồi chặt). Hàm f được gọi là tựa lồi trên A nếu ∀λ ∈ R tập mức : {x ∈ A : f (x) 6 λ} là tập lồi. Hàm f được gọi là tựa lõm nếu -f là tựa lồi . 1.6 Tính chất cực trị Cho ∅ = 6 D ∈ Rn , f : D → R (không nhất thiết lồi), ta có định nghĩa : Định nghĩa 1.17. Một điểm x∗ ∈ D được gọi là cực tiểu địa phương của f trên D, nếu tồn tại một lân cận mở U của x∗ sao cho f (x∗ ) 6 f (x) , ∀x ∈ D ∩ U. Một điểm x∗ ∈ D được gọi là cực tiểu tuyệt đối của f trên D nếu f (x∗ ) 6 f (x) , ∀x ∈ D. Định lý 1.8. Mọi điểm cực tiểu địa phương của một hàm lồi trên một tập lồi đều là điểm cực tiểu tuyệt đối. Định lý 1.9. Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên . 1.7 Quan hệ thứ tự từng phần và điểm hữu hiệu Cho X là một tập khác rỗng. 12 Định nghĩa 1.18. Ta gọi mỗi tập con R ⊂ X × X là một quan hệ hai ngôi trên X. Nếu (x, y) ∈ R thì ta viết xRy và nói x quan hệ R với y. Định nghĩa 1.19. Cho R là một quan hệ hai ngôi trên X. Ta nói R: i) Phản xạ nếu (x, x) ∈ R, ∀x ∈ X; ii) Bắc cầu nếu (x, y) ∈ R, (y, z) ∈ R thì (x, z) ∈ R. Định nghĩa 1.20. Một quan hệ hai ngôi R trên X được gọi là một thứ tự từng phần nếu nó phản xạ và bắc cầu. Nếu R là thứ tự từng phần trên X và nếu (x,y) ∈ R thì ta viết: x 6R y hoặc đơn giản x 6 y và nói là "x nhỏ hơn hoặc bằng y". Khi ấy thay vì viết R ta viết 6. Định nghĩa 1.21. Cho (6) là thứ tự từng phần trên Rm . Ta nói thứ tự 6 là tuyến tính nếu x 6 y kéo theo tx 6 ty với mỗi t>0 và x+z 6 y+z với mỗi z ∈ Rm . Định nghĩa 1.22. Với x = (x1 , x2 , ..., xm ) và y = (y1 , y2 , ..., ym ) thuộc Rm . Ta định nghĩa: i) x 6 y nếu xi 6 yi , ∀i = 1, 2, . . . , m; ii) x < y nếu x 6 y iii) x  y nếu xi < yi , ∀i = 1, 2, . . . , m. và x 6= y; 13 Khi đó, x 6 y là một thứ tự từng phần trên Rm . Dễ thấy x 6 y khi và m chỉ khi y − x ∈ Rm + . Ta gọi thứ tự này là thứ tự xác định bởi nón R+ . Định nghĩa 1.23. n Cho Rn và thứ tự 6 xác định bởi nón Rm + . Cho A ⊂ R là tập khác rỗng. Ta nói: i) x ∈ A là điểm hữu hiệu lí tưởng hoặc cực tiểu lí tưởng của A nếu x 6 y, ∀y ∈ A; ii) x ∈ A là điểm hữu hiệu hoặc cực tiểu Pareto của A nếu y 6 x với một y ∈ A nào đó thì y ≥ x; iii) x ∈ A là điểm hữu hiệu yếu của A nếu không tồn tại y ∈ A để y  x. Tập tất cả các điểm hữu hiệu lí tưởng của A, tập tất cả các điểm hữu hiệu của A và tập tất cả các điểm hữu hiệu yếu của A được kí hiệu lần lượt là IM in(A), M in(A) và W M in(A). Các kết quả sau đây là những trường hợp riêng của những kết quả tổng quát trong [4]: Định lý 1.10. Cho A ⊂ Rn là tập khác rỗng. Khi đó, M in(A) ⊂ W M in(A). Hơn thế, nếu IM in(A) 6= ∅ thì IM in(A) = M in(A). Chứng minh. Để chứng minh M in(A) ⊂ W M in(A), 14 lấy x ∈ M in(A) và đặt K là hình nón sinh bởi 0 và intRn+ . Giả sử rằng y ∈ A và y − x ∈ K. Chúng ta chỉ ra x − y ∈ K và điều này suy ra x ∈ W M in(A). Thật vậy, nếu x = y thì hiển nhiên ta có điều phải chứng minh. Nếu x 6= y và y − x ∈ K thì x − y ∈ int Rn+ . (1.1) Vì x ∈ M in(A) và K ⊆ Rn+ , x − y ∈ K suy ra x 6 y. Nói cách khác, y − x ∈ Rn+ . Điều này và (1.1) chỉ ra 0 ∈ int Rn+ , nghĩa là intRn+ = K và do đó x − y ∈ K . Tiếp theo, rõ ràng IM in (A) ⊆ M in (A) . Nếu IM in(A) khác rỗng, thì ta giả sử x là một trong những phần tử của nó. Khi đó, với mỗi y ∈ M in (A), y > x kéo theo x > y . Tính bắc cầu của quan hệ thứ tự cho ta z > y với mọi z ∈ A. Điều đó nghĩa là y ∈ IM in (A) và do đó IM in(A) trùng M in(A). Định lý 1.11. Nếu A ⊂ Rn là tập compact khác rỗng thì M in(A) 6= ∅. Định lý 1.12. Cho A là một tập đa diện trong Rn . Khi đó, M in(A) khác rỗng khi và chỉ khi: Re c (A) ∩ −Rn+ = {0} . Định nghĩa 1.24. 15 Cho f : Rn → Rm , ta nói f không giảm tại x ∈ Rn (đối với cặp nón (Rn+ , Rm + )) nếu x − y ∈ Rn+ suy ra f (x) − f (y) ∈ Rm +. Ta nói rằng f không giảm nếu nó không giảm tại mọi x ∈ Rn . Ta nói f là tăng chặt nếu nó không giảm và x − y ∈ int(Rn+ ) suy ra f (x) − f (y) ∈ int(Rm + ). 16 Chương 2 Bài toán tối ưu đa mục tiêu tuyến tính Chương này trình bày một số nội dung về bài toán tối ưu đa mục tiêu tuyến tính. Những kiến thức được trình bày trong chương được tham khảo chủ yếu từ [2] và [4]. 2.1 Khái niệm Trong thực tế cùng một lúc người ta thường theo đuổi nhiều mục tiêu khác nhau. Ví dụ khi lựa chọn mua nhà ở, chúng ta phải tính đến nhiều yếu tố: giá cả, môi trường, tiện nghi. Thường nhà rẻ hơn thì môi trường hay tiện nghi kém hơn. Điều đó dẫn đến mô hình bài toán tối ưu đa mục tiêu. Để hiểu rõ hơn về bài toán tối ưu đa mục tiêu, ta xét một số ví dụ sau: Ví dụ 1. (Tối ưu phương án thiết kế nhà ở) Giả sử trong thiết kế nhà ở, cách bố trí các phòng như một số thông số và ràng buộc được cho trước.Vấn đề phải xác định các thông số còn lại