Luận văn Một lớp các phương pháp giải bài toán tối ưu nhiều mục tiêu

Trang 7 CHƯƠNG I: KIẾN THỨC CƠ SỞ 1.1 Quan hệ thứ tự trong không gian. Trong Toán học, quan hệ hai ngôi là sự kết hợp hai phần tử bất kỳ trong cùng một tập hợp hoặc với các phần tử của tập hợp khác. Quan hệ hai ngôi được sử dụng trong nhiều nhánh khác nhau của toán học như trong số học ta có các quan hệ: lớn hơn hoặc bằng, bằng… Trong hình học ta có các quan hệ: đồng dạng, đối xứng, song song,… Trong lý thuyết đồ thị ta có các quan hệ: kề nhau, liên thông,...Quan hệ hai ngôi cũng được sử dụng trong khoa học máy tính, nhất là trong các mô hình quan hệ cơ sở dữ liệu như: các quan hệ: một – nhiều, nhiều – nhiều. Trong lý thuyết tối ưu nhiều mục tiêu quan hệ thứ tự hai ngôi có ý nghĩa rất quan trọng trong việc đưa ra các khái niệm về nghiệm tối ưu. Thông qua các khái niệm này ta lựa chọn nghiệm nào là nghiệm tốt nhất cho bài toán. 1.2 Các định nghĩa Xuất phát từ khái niệm tích Đề-cát của hai tập hợp là một tập hợp các cặp có thứ tự của hai tập hợp A, B bất kỳ. ܣݔܤ = { (ܽ,ܾ)| ܽ ∈ ܣ ; ܾ ∈ ܤ } Một cách tổng quát, một quan hệ n ngôi là một tập hợp bất kỳ của các bộ n-thứ tự từ n tập hợp. Chúng ta chỉ xét trường hợp đơn giản nhất là quan hệ hai ngôi trên một tập hợp. Điều này có nghĩa là tập hợp của các cặp có thứ tự, ứng với các phần tử của mỗi cặp là thuộc cùng một tập hợp A. Định nghĩa 1: Quan hệ hai ngôi trên tập A là tập hợp con R của ܣ ݔ ܣ. Ta gọi đơn giản là quan hệ hai ngôi. Ký hiệu: aRb hoặc R(a,b) hoặc (a,b) ∈ R gọi là "a R-quan hệ b" Ví dụ 1.2: xét tập hợp S = {1, 2, 3, 4, 5, 6, 7, 8} thì quan hệ “ < ” tập hợp của các cặp có thứ tự: {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8), (6, 7), (6, 8), (7, 8)} Trang 8 Quan hệ hai ngôi R tương ứng với hàm đặc trưng ோܲ:ܣ × ܤ → {ࢀ࢛࢘ࢋ,ࡲࢇ࢒࢙ࢋ} Định nghĩa 2: Quan hệ ngược là một quan hệ 2 ngôi R:AxB được xác định bởi: ܴିଵ ∶≡ {(ܾ,ܽ)|(ܽ,ܾ) ܴ}. Ví dụ 1: ܽ} = >. Ví dụ 2: Nếu xét quan hệ R: “Người” x “ăn” được định nghĩa bởi: a R b  a ăn b, b R−1 a  b thì được ăn bởi a Định nghĩa 3: Cho R là một quan hệ 2 ngôi trên tập A, khi đó R gọi là: i. Phản xạ nếu (a, a) ∈ R, ∀ܽ ∈ ܣ ( hoặc là ܽ  ܣ (ܴܽܽ) ) Ví dụ 3: Các quan hệ =, `có cùng tính chất toán học’,  =,,, … là phản xạ ii. Phi phản xạ nếu (ܽ,ܽ) ∉ ܴ, ∀ܽ ∈ ܣ hoặc là ܽܣ ( ܴܽܽ ) Ví dụ 4: Quan hệ , ‘có tính chất toán học khác nhau’,  là phi phản xạ. iii. Đối xứng nếu ∀ܽ,ܾ ∈ ܣ sao cho (ܽ, ܾ) ∈ ܴ ⟹ (ܾ,ܽ) ∈ ܴ Ví dụ 5: Quan hệ “ = ” là đối xứng. iv. Phản xứng nếu ∀ܽ,ܾ ∈ ܣ sao cho (ܽ,ܾ) ∈ ܴ ⟹ (ܾ,ܽ) ∉ ܴ Ví dụ 6: Quan hệ “ < ” là phản xứng. v. Phi đối xứng nếu ∀ܽ,ܾ ∈ ܣ sao cho (ܽ,ܾ) ∈ ܴ ݒà (ܾ, ܽ) ∈ ܴ ⟹ ܽ = ܾ Ví dụ 7: các quan hệ , ,  là Phi đối xứng vi. Bắc cầu nếu ∀ܽ,ܾ, ܿ ∈ ܣ sao cho (ܽ, ܾ) ∈ ܴ ݒà (ܾ, ܿ) ∈ ܴ ⟹ (ܽ, ܿ) ∈ ܴ Ví dụ 8: Quan hệ “ ≥, , = “ là bắc cầu. vii. Phủ định bắc cầu nếu ∀ܽ, ܾ, ܿ ∈ ܣ sao cho (ܽ,ܾ) ∉ ܴ ݒà (ܾ, ܿ) ∉ ܴ ⟹ (ܽ, ܿ) ∉ ܴ Ví dụ 9: Nếu “ chó sói ăn cừu ” và “ cừu ăn cỏ ” nhưng “ sói không ăn cỏ ” thì quan hệ “ ăn ” là phủ định và bắc cầu viii. Phản bắc cầu nếu: ∀ܽ, ܾ, ܿ ∶ ܴܾܽ ⋀ܾܴܿ ⟹ ¬ܴܽܿ Trang 9 Ví dụ 10: Nếu “ A quen B “ và “ B quen C “ nhưng “ A chưa chắc quen C “ thì quan hệ “quen” là phản bắc cầu ix. Liên hợp nếu ∀ܽ, ܾ ∈ ܣ sao cho ܽ ≠ ܾ ⟹ (ܽ, ܾ) ∈ ܴ hoặc (ܾ, ܽ) ∈ ܴ Ví dụ 11: cho A = là tập các số chẳn. thì quan hệ chia hết là liên hợp. x. Liên hợp mạnh nếu ∀ܽ, ܾ ∈ ܣ ⟹ (ܽ,ܾ) ∈ ܴ hoặc (ܾ,ܽ) ∈ ܴ Ví dụ 12 : Cho A = N. Thì quan hệ >, <,…là liên hợp mạnh. Định lý 4: R là đối xứng khi và chỉ khi R = R−1, Chứng minh:  Giả sử R là đối xứng. Thì: (x,y)  R  (y,x)  R  (x,y)  R−1  Giả sử R = R−1 Thì: (x,y)  R  (x,y)  R−1  (y,x)  R Định nghĩa 5: Cho R là một quan hệ 2 ngôi trên A khi đó: i. R được gọi là quan hệ tương đương nếu R có tính chất phản xạ, đối xứng và bắc cầu. ii. R được gọi là tiền thứ tự nếu R có tính chất phản xạ và bắc cầu. Ví dụ 13: =; “các tập tương đương”; “chia hết”; mod… Trong trường hợp quan hệ R là tiền thứ tự thì cặp (A,R) được gọi là tập tiền thứ tự. Để tiện ta thay đổi quan hệ R là ≼ . Do đó ta quy ước viết: ܽ ≼ ܾ thay cho (a, b) ∈ ≼ ܽ ⋠ ܾ thay cho (a, b) ∉ ≼ với bất kỳ một quan hệ ≼ là tiền thứ tự nào thì cũng có quan 2 quan hệ khác mà ta định nghĩa chúng như sau: ݔ ≺ ݕ ⟺ ݔ ≺ ݕ ݒà ݕ ≰ ݔ (1.9) ݔ ~ ݕ ⟺ ݔ ≼ ݕ ݒà ݕ ≼ ݔ (1.10) Mệnh đề 6: Cho ≼ là một tiền thứ tự trên tập A. Khi đó:  Quan hệ ≺ định nghĩa trong (1.9) là phi phản xạ và bắc cầu.  Quan hệ ~ định nghĩa trong (1.10) là quan hệ tương đương. Trang 10 Mệnh đề 7:  Một quan hệ hai ngôi phản xứng là phi phản xạ.  Một quan hệ hai ngôi bắc cầu và phi phản xạ là phản xứng. Định nghĩa 8: Một quan hệ hai ngôi ≼ trên A là:  Tiền thứ tự tổng quát nếu ≼ là phản xạ, bắc cầu và liên hợp.  Thứ tự tổng quát nếu ≼ là tiền thứ tự tổng quát phi đối xứng. Như quan hệ ≤ đối với số nguyên là thứ tự tổng quát.  Thứ tự yếu chặt nếu ≼ là phản xứng và phủ định bắc cầu. Mệnh đề 9: Nếu ≼ là tiền thứ tự tổng quát trên A, khi đó quan hệ ≺là thứ tự yếu chặt. Nếu ≺ là thứ tự yếu chặt trên A, khi đó ≼ định nghĩa bởi: ݔ ≼ ݕ ⟺ ݔ ≺ ݕ hoặc (ݔ ⊀ ݕ và ݕ ⊀ ݔ ) (1.11) là tiền thứ tự tổng. Định nghĩa 10: Quan hệ hai ngôi ≼ được gọi là thứ tự từng phần nếu là phản xạ, bắc cầu và phi đối xứng. Định nghĩa 11: Quan hệ hai ngôi ≼ được gọi là thứ tự từng phần chặt nếu ≼ là phản xứng và bắc cầu ( hoặc ≼ là phi phản xạ và 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 Euclid_Rn. Khi đó ta có một số thứ tự trên Rn. Kí hiệu Định nghĩa Tên gọi ݔ ≤ ݕ ݔ < ݕ ݔ ≪ ݕ ݔ ≤௅௘௫ ݕ ݔ ≤ெ௢ ݕ Nếu ݔ௜ ≤ ݕ௜ với i= 1,..,n Nếu ݔ௜ ≤ ݕ௜ với i= 1,..,n; ݔ ≠ ݕ Nếu ݔ௜ < ݕ௜ với i= 1,..,n Nếu ݔ௞ < ݕ௞ hoặc x = y Nếu max௜ୀଵ,…,௡{ݔ௜} ≤ max௜ୀଵ,…,௡{ݕ௜} 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ự. Trang 11 Định nghĩa 12: Một tập con ܭ ⊆ ܴ௡ được gọi là nón nếu: ߣݔ ∈ ܭ với mọi ݔ ∈ ܭ và ߣ ∈ ܴ, ߣ > 0 Ví dụ 14: K = ܴାଶ = {ݔ ∈ ܴଶ | ݔ௜ ≥ 0, ݅ = 1,2} là nón. Định nghĩa 13: Nón k trong Rn gọi là:  Không tầm thường nếu ܭ ≠ ∅ và ܭ ≠ ܴ௡  Lồi nếu ߙݔଵ + (1− ߙݔଶ) ∈ ܭ với mọi ݔଵ,ݔଶ ∈ ܭ và 0 < ߙ < 1  Nhọn nếu ܭ ∩ (−݇) ⊂ {0} Mệnh đề 14: Cho một quan hệ thứ tự ≼ trên ܴ௡, ta định nghĩa tập: ܭ≼ = { ݕ − ݔ | ݔ ≼ ݕ} Khi đó ܭ≼ là nón. Chứng minh: Cho ݑ ∈ ܭ≼ khi đó: u = y – x với ݔ,ݕ ∈ ܴ௡ ⟹ ݔ ≼ ݕ ⟹ ߣݔ ≼ ߣݕ với ߣ > 0 Do đó: ߣݑ = ߣ(ݔ − ݕ) = ߣݔ − ߣݕ ∈ ܭ≼ với ߣ > 0 Định lý 15: Cho ≼ một quan hệ 2 ngôi trên ܴ௡ là phép nhân vô hướng. Khi đó: i. 0 ∈ ܭ≼ nếu ≼ là Phản xạ ii. ܭ≼ lồi nếu ≼ là Bắc cầu iii. ܭ≼ nhọn nếu ≼ là Phi đối xứng Chứng minh: (i): Giả sử quan hệ: ≼ là Phản xạ Khi đó: ݔ ≼ ݕ với ݔ ∈ ܴ௡ ⟹ ݔ − ݔ = 0 ∈ ܭ≼ (ii): Giả sử quan hệ ≼ là Bắc cầu và Cho ݑ, ݒ ∈ ܭ≼ Nên: ݑ − 0 ∈ ܭ≼ và 0 − ݒ ∈ −ܭ≼ Điều này có nghĩa là: 0 ≼ ݑ và −ݒ ≼ 0 .Mà ≼ là Bắc cầu ⟹−ݒ ≼ ݑ Do đó: ݑ − ݒ = ݑ + ݒ ∈ ܭ tức là K lồi (iii): Giả sử ta có 0 ≠ ݑ ∈ ܭ≼ . Thì ݑ = ݕ − ݔ ∈ ܭ≼ và –ݑ = ݔ − ݕ ∈ ܭ≼ với ݔ,ݕ ∈ ܴ௡ Do 0 ≠ ݑ nên ݔ ≼ ݕ và ݕ ≼ ݔ nhưng ݔ ≠ ݕ. Điều này vô lý. Trang 12 Định nghĩa 16: Cho K là nón. Ta định nghĩa thứ tự theo nón ≼௄ là: ݔ ≼௄ ݕ ⟺ ݕ − ݔ ∈ ܭ (1.12) Mệnh đề 17: Cho K là nón và thứ tự theo nón ≼௄ trong (1.12) là phép nhân vô hướng và cộng trong Rn. Hơn nữa: 1. ≼௄ là phản xạ nếu 0 ∈ ܭ 2. ≼௄ là bắc cầu nếu K lồi 3. ≼௄ là phi đối xứng nếu K nhọn Chứng minh: Cho ݔ, ݕ, ݖ ∈ ܴ௡ và 0 < ߣ ∈ ܴ với ݔ ≼௄ ݕ Ta có: ݕ − ݔ ∈ ܭ Do K là nón nên: ߣ(ݔ − ݕ) ∈ ܭ ஽௘௙ሳልሰ ߣݔ ≼௄ ߣݕ Và ݔ ≼௄ ݕ nghĩa là: ݕ − ݔ = (ݖ + ݕ)− (ݔ + ݖ) Do đó: (ݖ+ ݕ) ≼௄ (ݔ + ݖ) (1). Cho ݔ ∈ ܴ௡ . Khi đó ݔ − ݔ = 0 ∈ ܭ ⟺ ݔ ≼௄ ݔ (2). Cho ݔ ≼௄ ݕ và ݕ ≼௄ ݖ khi đó : ݕ − ݔ ∈ ܭ và ݖ − ݕ ∈ ܭ Do K lồi nên: ݕ − ݔ + ݖ − ݕ = ݖ − ݔ ∈ ܭ ஽௘௙ሳልሰ ݔ ≼௄ ݖ (3). Cho ݔ, ݕ ∈ ܴ௡ với ݔ ≼௄ ݕ và ݕ ≼௄ ݔ . Khi đó ta có: ݕ − ݔ ∈ ܭ và ݔ − ݕ ∈ ܭ. ݕ − ݔ ∈ ܭ(−ܭ) = {0}. Do đó: y = x 1.3 Giới thiệu bài toán tối ưu nhiều mục tiêu: Có rất nhiều lớp khác nhau để biểu diễn cho bài toán tối ưu nhiều mục tiêu. Trong phạm vi luận văn này ta sẽ biểu diễn bài toán tối ưu nhiều mục tiêu dưới dạng sau: ܯ݅݊{ ଵ݂(ݔ), … , ௞݂(ݔ) } (Pଵ) Sao cho: ݔ ∈ ܺ Trong đó:  x là biến quyết định. ܺ = { ݔ ∈ R୬ |݃௝(ݔ) ≤ 0; ℎ௝(ݔ) = 0 với ݆ = 1, … , ݌ < ݊ } là không gian quyết định.  fi : Rn  R với i = 1,…, k là các hàm mục tiêu. Đặt: Y = { y = ( ଵ݂(ݔ), … , ௞݂(ݔ))  R୩ } là không gian hàm mục tiêu. Trang 13 HÌNH 2 Định nghĩa 18: Một nghiệm ݔ∗ ∈ ܺ của bài toán (P1) được gọi là nghiệm lý tưởng nếu: ௜݂(ݔ∗) ≤ ௜݂(ݔ) ∀ݔ ∈ ܺ , ݅ = {1, …݇} 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 19: Một nghiệm ݔ = (ݔଵ,ݔଶ, … , ݔ௡) được gọi là trội hơn nghiệm ݕ =(ݕଵ,ݕଶ, … ,ݕ௡) ký hiệu là: ݔ ≤ ݕ , nếu: ൜ ௜݂(ݔ) ≤ ௜݂(ݕ) ݅ ∈ {1, … , ݇} ∃ ݆ ∈ {1, … , ݊} ௝݂(ݔ) < ௝݂(ݕ) Định nghĩa 20: ݔ = (ݔଵ,ݔଶ, … , ݔ௡) được gọi là nghiệm không trội hơn nghiệm ݕ = (ݕଵ,ݕଶ, … ,ݕ௡) nếu: ∀ݔ ∈ ܺ, ∄ݕ ∈ ܺ ݏܽ݋ ܿℎ݋: ݕ ≻௑ ݔ 1.4 Các khái niệm tối ưu. 1.4.1 Tối ưu Pareto: Định nghĩa 21: Một điểm ݔ∗ ∈ ܺ được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm ݔ ≠ ݔ∗ ∈ ܺ sao cho x trội hơn ݔ∗ . Nghĩa là: ݂(ݔ) < ݂(ݔ∗) KHÔNG GIAN QUYẾT ĐỊNH KHÔNG GIAN MỤC TIÊU Trang 14 Tính chất 22: 1. Nếu x* là nghiệm tối ưu Pareto thì ݂(ݔ∗) gọi là điểm hữu hiệu 2. Nếu ݔଵ, ݔଶ ∈ ܺ và ݂(ݔଵ) ≤ ݂(ݔଶ) thì ta gọi x1 trội hơn x2 và ݂(ݔଵ) trội hơn ݂(ݔଶ) 3. Tập tất cả các nghiệm tối ưu Pareto ݔ∗ ∈ ܺ và tập các điểm hữu hiệu. ݕ = ݂(ݔ∗) ∈ ܻ lần lượt là: ࢄ࢖ࢇ࢘ và ࢅࢋࢌࢌ Định nghĩa 23: Các định nghĩa tương đương khác. x* là nghiệm tối ưu Pareto nếu: 1. Không tồn tại một nghiệm ݔ ∈ ܺ sao cho: f(x) trội hơn f(x*) 2. Không tồn tại một nghiệm ݔ ∈ ܺ sao cho: ݂(ݔ)− ݂(ݔ∗) ∈ −ܴା௄ \ {0} 3. ݂(ݔ)− ݂(ݔ∗) ∈ ܴ௄\{−ܴା௄ \ {0}} ∀ݔ ∈ ܺ 4. ݂(ܺ) ∩ (݂(ݔ∗) − ܴା) = {݂(ݔ∗)} 5. Không tồn tại ݂(ݔ) ∈ ݂(ܺ)\{݂(ݔ∗)} sao cho: ݂(ݔ) ∈ ݂(ݔ∗)− ܴା௄ 6. ݂(ݔ) ≤ ݂(ݔ∗) với ݔ ∈ ܺ nghĩa là: ݂(ݔ) = ݂(ݔ∗) 1.4.2 Nghiệm tối ưu Pareto chặt và yếu. Hình 3a Minh hoạ cho định nghĩa: 1, 4 và 5 Hình 3b Minh hoạ cho định nghĩa: 2 và 3 ݂(ݔ∗) ݂(ܺ) ݂(ݔ) ݂(ݔ∗ − ܴା௄) ௘ܻ௙௙ ௘ܻ௙௙ −ܴା ௄ ݂(ܺ)− ݂(ݔ∗) ݂(ݔ∗) Trang 15 Định nghĩa 24: Nghiệm ݔ∗ ∈ ܺ được gọi là một nghiệm tối ưu yếu Pareto nếu không tồn tại một nghiệm ݔ ∈ ܺ sao cho: ݂(ݔ) ≪ ݂(ݔ∗) ݅ = {1, …݇} Khi đó: Điểm ݕ = ݂(ݔ∗) ∈ ܻ gọi là điểm hữu hiệu yếu. Tập nghiệm tối ưu Pareto yếu và tập các điểm hữu hiệu yếu lần lượt ký hiệu là: ࢄ࢝ି࢖ࢇ࢘ và ࢅ࢝ିࢋࢌࢌ Định nghĩa 25: Nghiệm ݔ∗ ∈ ܺ được gọi là một nghiệm tối ưu chặt Pareto nếu không tồn tại một nghiệm ݔ ∈ ܺ và ݔ ≠ ݔ∗ sao cho: ݂(ݔ) ≤ ݂(ݔ∗). Khi đó: Tập nghiệm tối ưu Pareto chặt ký hiệu là: ࢄ࢙ି࢖ࢇ࢘ Từ định nghĩa ta nhận xét rằng:  ࢅࢋࢌࢌ ⊂ ࢅ࢝ିࢋࢌࢌ  ࢄ࢙ି࢖ࢇ࢘ ⊂ ࢄ࢖ࢇ࢘ ⊂ ࢄ࢝ି࢖ࢇ࢘ Định nghĩa 26: Cho ܺ ⊂ ࡾ࢔, một ánh xạ ݂:ܺ → ܴ và ݔ̅ ∈ ܺ. ܭℎ݅ đó: i. ܮஸ(݂(࢞ഥ)) = { ݔ ∈ ܺ | ࢌ(࢞) ≤ ࢌ(࢞ഥ)} được gọi là tập mức của ࢌ tại ࢞ഥ ii. ܮୀ(݂(࢞ഥ)) = { ݔ ∈ ܺ | ࢌ(࢞) = ࢌ(࢞ഥ)} được gọi là mặt mức của ࢌ tại ࢞ഥ iii. ܮழ(݂(࢞ഥ)) = ܮஸ(݂(࢞ഥ))\ܮୀ(݂(࢞ഥ)) = { ݔ ∈ ܺ | ࢌ(࢞) < ݂(࢞ഥ)} được gọi là tập mức chặt của ࢌ tại ࢞ഥ . Nhận xét: Từ định nghĩa ta nhận thấy: ܮୀ(݂(࢞ഥ)) ⊂ ܮஸ(݂(࢞ഥ)) Định lý 27: Cho ݔ∗ ∈ ܺ và định nghĩa ݕ௤ = ௤݂(ݔ∗) khi đó: i. ݔ∗ là nghiệm tối ưu Pareto chặt nếu và chỉ nếu: ሩܮஸ(௞ ௤ୀଵ ݕ௤) = {ݔ∗} ii. ݔ∗ là nghiệm tối ưu Pareto nếu và chỉ nếu: ሩܮஸ(௞ ௤ୀଵ ݕ௤) =ሩܮୀ(௞ ௤ୀଵ ݕ௤) Trang 16 iii. ݔ∗ là nghiệm tối ưu Pareto yếu nếu và chỉ nếu: ሩܮழ(௞ ௤ୀଵ ݕ௤) = ∅ Chứng minh: (1): “ ݔ∗ là nghiệm tối ưu Pareto chặt ” không tồn tại một nghiệm ݔ ∈ ܺ và ݔ ≠ ݔ∗ sao cho: ݂(ݔ) ≤ ݂(ݔ∗). không tồn tại một nghiệm ݔ ∈ ܺ và ݔ ≠ ݔ∗ sao cho: ௤݂(ݔ) < ௤݂(ݔ∗) với ݍ = 1,݇തതതതത không tồn tại một nghiệm ݔ ∈ ܺ và ݔ ≠ ݔ∗ sao cho: ݔ ∈ሩܮஸ(௞ ௤ୀଵ ݕ௤) ⟺ሩܮஸ(௞ ௤ୀଵ ݕ௤) = {ݔ∗} (2): ” ݔ∗ là nghiệm tối ưu Pareto: “ không tồn tại một nghiệm ݔ ∈ ܺ sao cho: ௤݂(ݔ) < ௤݂(ݔ∗) với ݍ = 1,݇തതതതത và ௝݂(ݔ) < ௝݂(ݔ∗) với j = {1, … , k} không tồn tại một nghiệm ݔ ∈ ܺ sao cho: ݔ ∈ሩܮஸ(௞ ௤ୀଵ ݕ௤) và ݔ ∈ ܮழ൫ݕ௝൯ với ݆ = {1, … , ݇} ⟺ሩܮஸ(௞ ௤ୀଵ ݕ௤) =ሩܮୀ(௞ ௤ୀଵ ݕ௤) (3):” ݔ∗ là nghiệm tối ưu Pareto yếu” không tồn tại một nghiệm ݔ ∈ ܺ sao cho: ௤݂(ݔ) < ௤݂(ݔ∗) với ݍ = 1, kതതതതത không tồn tại một nghiệm ݔ ∈ ܺ sao cho: Trang 17 ݔ ∈ሩܮழ(௞ ௤ୀଵ ݕ௤) ⟺ሩܮழ(௞ ௤ୀଵ ݕ௤) = ∅ 1.4.3 Nghiệm tối ưu Pareto chính thường và điểm hữu hiệu chính thường. Theo định nghĩa tối ưu Pareto ta nhận thấy rằng nếu ݔ∗ là một nghiệm tối ưu Pareto thì nó không cho phép cải thiện giá trị của một hàm mục tiêu trong khi vẫn duy trì giá trị của các hàm mục tiêu khác. Do đó để cải thiện một hay nhiều giá trị của hàm mục tiêu này ta buộc phải làm “giảm” giá trị của các hàm mục tiêu khác đã được chấp nhận mà ta gọi đây là sự thỏa hiệp. Sự thỏa hiệp giữa các tiêu chuẩn này được đo bằng cách tính toán việc giảm giá trị của hàm mục tiêu ௝݂ trên đơn vị tăng về mặt giá trị của hàm mục tiêu ௝݂. Định nghĩa 28: (Geoffrion 1986) ݔ∗ ∈ ܺ được gọi là tối ưu Pareto chính thường theo Geoffrion nếu ݔ∗ là nghiệm tối ưu Pareto và nếu có một số M > 0 sao cho: mỗi ݅ ݒà ∀ ݔ ∈ ܺ thỏa mãn ௜݂(ݔ) < ௜݂(ݔ∗) và tồn tại một chỉ số j sao cho ௝݂(ݔ∗) < ௝݂(ݔ). Hơn nữa: ௜݂(ݔ∗)− ௜݂(ݔ) ௝݂(ݔ)− ௝݂(ݔ∗) ≤ ܯ Khi đó giá trị hàm mục tiêu đạt được tương ứng tại ݔ∗ là: ݕ∗ = ݂(ݔ∗) gọi là điểm hữu hiệu chính thường. Nhận xét: Một nghiệm tối ưu Pareto chính thường có biên thỏa hiệp giữa tất cả các hàm mục tiêu. Ta xét bài toán lồi sau đây: min ௫∈௑ ෍ߣ௜ ௜݂ ௞ ௜ୀଵ (ݔ) ( ଶܲ) Thì ( ଶܲ) gọi là bài toán trọng tổng số. Trong đó: ߣ௜ với ݅ = 1, … ,݇ là các trọng số không âm đối với các hàm mục tiêu và ෍ߣ௜ ௞ ௜ୀଵ = 1 Trang 18 Định lý 29 (Geoffrion 1968): Cho ߣ௜ > 0 với ݅ = 1, … ,݇ với ∑ ߣ௜௞௜ୀଵ = 1. Nếu ݔ∗ là nghiệm tối ưu Pareto của bài toán ( ଶܲ) khi đó ݔ∗ là nghiệm tối ưu Pareto chính thường. Chứng minh: Cho ݔ∗ là nghiệm tối ưu Pareto của bài toán ( ଶܲ). Để thấy rằng ݔ∗ là nghiệm tối ưu Pareto ta giả sử rằng tồn tại ݔᇱ ∈ ܺ với ݂(ݔᇱ) 0 với ݅ = 1, … , ݇ và ௜݂(ݔᇱ)− ௜݂(ݔ∗) hàm ý sự mâu thuẫn rằng: ෍ߣ௜ ௜݂ ௞ ௜ୀଵ (ݔᇱ) <෍ߣ௜ ௜݂௞ ௜ୀଵ (ݔ∗) Để thấy rằng ݔ∗ là nghiệm tối ưu Pareto chính thường, ta chọn một số M thích hợp sao cho có một sự thỏa hiệp lớn hơn M dẫn đến sự mâu thuẫn vối tính tối ưu của ݔ∗ đối với bài toán tổng trọng số. Cho ܯ = (ܳ − 1) max ௜,௝ ߣ௝ߣ௜ Giả sử ݔ∗ không là nghiệm tối ưu Pareto chính thường. Tức là tồn tại một i và ݔ ∈ ܺ sao cho ௜݂(ݔ∗) ܯ ቀ ௝݂(ݔ)− ௝݂(ݔ∗)ቁ ∀݆ sao cho: ௝݂(ݔ∗) < ௝݂(ݔ) Do đó: ௜݂(ݔ∗)− ௜݂(ݔ) > ௞ିଵఒ೔ ߣ௝ ቀ ௝݂(ݔ)− ௝݂(ݔ∗)ቁ ݅ ≠ ݆ bằng cách chọn M. Nhân hai vế của bất đẳng thức trên với ఒ೔ ௞ିଵ rồi sau đó lấy tổng hai vế ta được: ෍ ߣ௜ ݇ − 1 ௝ஷ௜ ൫ ௜݂(ݔ∗)− ௜݂(ݔ)൯ >෍ߣ௝ ቀ ௝݂(ݔ)− ௝݂(ݔ∗)ቁ ௝ஷ௜ ⟹ ߣ௜൫ ௜݂(ݔ∗)− ௜݂(ݔ)൯ >෍ߣ௝ ௝݂(ݔ)−෍ߣ௝ ௝݂(ݔ∗) ௝ஷ௜௝ஷ௜ ⟹ ߣ௜ ௜݂(ݔ∗) +෍ߣ௝ ௝݂(ݔ∗) ௝ஷ௜ > ߣ௜ ௜݂(ݔ) +෍ߣ௝ ௝݂(ݔ) ௝ஷ௜ Trang 19 ෍ߣ௜ ௜݂(ݔ∗) >௞ ௜ୀଵ ෍ߣ௜ ௜݂(ݔ)௞ ௜ୀଵ Điều này mâu thuẫn với tính tối ưu của ݔ∗ đối với bài toán (∗). Do đó giả sử của chúng ta là sai và ݔ∗ là nghiệm tối ưu Pareto chính thường. Định lý 30: Cho ܺ ⊂ ܴ௡ là một tập lồi và giả sử rằng ℎ௜: ܴ௡⟶ ܴ là hàm lồi, ݅ = 1, kതതതതത. Khi đó bất đẳng thức ℎ௜ 0 sao cho ∑ ߣ௜௞௜ୀଵ = 1 và ∀ݔ ∈ ܺ thỏa mãn: ෍ߣ௜ ௞ ௜ୀଵ ℎ௜(ݔ) ≥ 0 Định lý 31 (Geoffrion 1968): Cho ܺ ⊂ ܴ௡ là một tập lồi và giả sử rằng ௜݂: ܺ ⟶ ܴ là ánh xạ lồi. Khi đó ݔ∗ ∈ ܺ là nghiệm tối ưu Pareto chính thường nếu và chỉ nếu ݔ∗ là nghiệm tối ưu đối với bài toán (∗) với .ߣ௜ > 0 với ݅ = 1, kതതതതത Chứng minh: Do định lý 30 chúng ta chỉ cần chứng minh điều kiện cần của định lý này là đủ. Cho ࢞∗ là nghiệm tối ưu Pareto chính thường. Nghĩa là có một số M > 0 sao cho: ∀݅ = 1, kതതതതത thì hai bất đẳng thức sau không có nghiệm: ቐ ௜݂(ݔ) ≤ ௜݂(ݔ∗) ௜݂(ݔ∗)− ௜݂(ݔ) ௝݂(ݔ)− ௝݂(ݔ∗) ≤ ܯ ⟺ ௜݂(ݔ) +ܯ ௝݂(ݔ) < ௜݂(ݔ∗) +ܯ ௝݂(ݔ∗) ∀݆ ≠ ݅ Tính chất của hàm lồi mà chúng ta phát biểu trong định lý 31 trên nghĩa là đối với hai bất đẳng thức thứ i như vậy, tồn tại ߣ௝௜ ≥ 0, ݆ = 1, kതതതതത với ∑ ߣ௜ ௞ ௜ୀଵ = 1 sao cho ∀ ݔ ∈ ܺ ta được: ߣ௜ ௜ ௜݂(ݔ) +෍ߣ௝௜൫ ௜݂(ݔ) +ܯ ௝݂(ݔ)൯ ௜ஷ௝ ≥ ߣ௜ ௜ ௜݂(ݔ∗) +෍ߣ௝௜൫ ௜݂(ݔ∗) +ܯ ௝݂(ݔ∗)൯ ௜ஷ௝ Trang 20 ⟹ ߣ௜ ௜ ௜݂(ݔ) +෍ߣ௝௜ ௜ஷ௝ ௜݂(ݔ) +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ) ≥ ߣ௜௜ ௜݂(ݔ∗) +෍ߣ௝௜ ௜ஷ௝ ௜݂(ݔ∗) +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ∗) ⟹ ෍ߣ௝௜ ௜݂(ݔ)௞ ௜ୀଵ +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ) ≥෍ߣ௝௜ ௜݂(ݔ∗)௞ ௜ୀଵ +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ∗) ⟺ ௜݂(ݔ) +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ) ≥ ௜݂(ݔ∗) +ܯ෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ∗) Lấy tổng hai vế của bất đẳng thức trên với biến chạy là i ta được: ෍ ௜݂(ݔ)௞ ௜ୀଵ +ܯ෍෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ)௞ ௜ୀଵ ≥෍ ௜݂(ݔ∗)௞ ௜ୀଵ +ܯ෍෍ߣ௝௜ ௜ஷ௝ ௝݂(ݔ∗)௞ ௜ୀଵ ⟹ ෍ቌ1 +ܯ෍ߣ௝௜ ௜ஷ௝ ቍ ௞ ௜ୀଵ ௝݂(ݔ) ≥෍ቌ1 +ܯ෍ߣ௝௜ ௜ஷ௝ ቍ ௞ ௜ୀଵ ௝݂(ݔ∗) ∀ ݔ ∈ ܺ .Chúng ta chuẩn hóa giá trị ൫1 +ܯ∑ ߣ௝௜௜ஷ௝ ൯, để ta lấy tổng đến 1 và có ߣ௜௜ >0 với ݅ = 1, kതതതതത với ࢞∗ là nghiệm tối ưu của bài toán (∗) Định nghĩa 32: Cho ܻ ⊂ ܴ௡ và ݕ ∈ ܻ, khi đó: 1. Nón tiếp xúc của Y tại y là: ௒ܶ(ݕ) = { ݀ ∈ ܴ௞ | ∃ (ݐ௞) ⊂ ܻ ݏܽ݋ ܿℎ݋ (ݕ௞ → ݕ) và ݐ௞(ݕ௞ − ݕ)→ ݀} 2. Bao của nón Y là: ܿ݋݊݁(ܻ) = {ߙݕ |ߙ ≥ 0, ݕ ∈ ܻ} =ራߙܻ ఈ Định nghĩa 33 (Borwein 1977): Nghiệm ݔො ∈ ܺ được gọi là nghiệm tối ưu Pareto chính thường nếu: ܶ௒ାோశ಼(݂(ݔො)) ∩ (−ܴା௄) = {0} Định nghĩa 34 (Benson 1979): Nghiệm ݔො ∈ ܺ được gọi là nghiệm tối ưu Pareto chính thường nếu: ݈ܿ(ܿ݋݊݁൫ܻ + ܴା௄ − ݂(ݔො)൯ ∩ (−ܴା௄) = {0} Trang 21 Định lý 35 (Benson 1979): Nghiệm ݔො ∈ ܺ được gọi là nghiệm tối ưu Pareto chính thường theo định nghĩa của Geoffrion nếu và chỉ nếu ݔො là nghiệm tối ưu Pareto chính thường theo định nghĩa của Benson. Chứng minh: Chiều thuận “⟹” Giả sử ݔො là nghiệm tối ưu Pareto, nhưng không phải là tối ưu Pareto chính thường theo định nghĩa của Benson. Khi đó ta có: ݀ ≠ 0 và ݀ ∈ ݈ܿ ൬ܿ݋݊݁ ቀܻ + ܴାொ − ݂(ݔො)ቁ൰ሩ−ܴା௄ Không mất tính tổng quát ta giả sử rằng: ݀ଵ < −1, ݀௜ ≤ 0, ݅ = 2, … ,ܳ . Do đó có một chuỗi (ݐ௞) ⊂ ܴା\{0}, (ݔ௞) ⊂ ܺ, (ݎ௞) ⊂ ܴା sao cho: ݐ௞(݂(ݔ௞) + ݎ௞ − ݂(ݔො))→ ݀ Chọn một chuỗi con nếu cần thiết ta giả sử rằng: ෠ܳ = {݅ ∈ {1, … ,ܳ}| ௜݂(ݔ௞) > ௜݂(ݔො) } là giống nhau với mọi k và khác rỗng. Cho M > 0. Từ sự hội tụ, ta đạt được sự tồn tại của k0 sao cho với mỗi ݇ ≥ ݇଴ ta có: ଵ݂(ݔ௞)− ଵ݂(ݔො) < − ଵଶ௧ೖ (1) ௜݂(ݔ௞)− ௜݂(ݔො) ≤ ଵଶெ௧ೖ với ݅ = 2, … ,ܳ (2) Vì ݐ௞ → ∞, cho ݅ ∈ ෠ܳ ta có: 0 < ௜݂(ݔ௞)− ௜݂(ݔො) ≤ 12ܯݐ௞ ∀݇ ≥ ݇଴ (3) Do đó từ: (1) và (3) chúng ta có: ଵ݂(ݔො)− ଵ݂(ݔ௞) ௜݂(ݔ௞)− ௜݂(ݔො) > 12ݐ௞12ܯݐ௞ = ܯ (4) Vì M được chọn tùy ý nên ݔො không là nghiệm tối ưu Pareto theo định nghĩa Geoffrion. Chiều nghịch “ ” Trang 22 Giả sử rằng ݔො là nghiệm tối ưu Pareto, ݔො không là nghiệm tối ưu Pareto theo định nghĩa Geoffrion. Cho ܯ௞ > 0 là một chuỗi số thực và không bị chặn. Không mất tính tổng quát ta giả sử rằng với mỗi ܯ௞ có ݔ௞ ∈ ܺ ݏܽ݋ ܿℎ݋ ଵ݂(ݔ௞) < ଵ݂(ݔො) và ଵ݂(ݔො)− ଵ݂(ݔ௞) ௜݂(ݔ௞)− ௜݂(ݔො) > ܯ௞ ∀݅ ∈ {2, … ,ܳ} với ௜݂(ݔ௞) > ௜݂(ݔො) Chọn một chuỗi con nếu cần thiết ta giả sử rằng: ෠ܳ = {݅ ∈ {1, … ,ܳ}| ௜݂(ݔ௞) > ௜݂(ݔො) } là hằng với mỗi k và khác rỗng. Chúng ta xây dựng một chuỗi thích hợp (ݐ௞) và (ݎ௞) sao cho giới hạn của: ݐ௞(݂(ݔ௞) + ݎ௞ − ݂(ݔො)) → ݀ ∈ ݈ܿ ൬ܿ݋݊݁ ቀܻ + ܴାொ − ݂(ݔො)ቁ൰ሩ(−ܴା௄) Đặt: ݐ௞ = ൫ ଵ݂(ݔො)− ଵ݂(ݔ௞)൯ିଵ ⟹ ݐ௞ > 0, ∀݇ ݎ௞ ∈ ܴାொ với: ݎ௜ ௞ = ൜ 0, ݅ = 1, ݅ ∈ തܳ ଵ݂(ݔො)− ଵ݂(ݔ௞), ݊݃ượܿ ݈ạ݅ Từ đó bằng tính toán ta được: ݐ௞൫ ௜݂(ݔ௞) + ݎ௜௞ − ௜݂(ݔො)൯ ቐ= −1 ݅ = 1= 0 ݅ ≠ 1 và ݅ ∉ തܳ ∈ (0,ܯ௞ିଵ) ݅ ∈ തܳ (4) Chuỗi này là hội tụ khi cho ܯ௞ → ∞ và ݀ ∈ ܴொ trong đó: ݀௜ = lim ௞→ஶ ݐ௞൫ ௜݂(ݔ௞) + ݎ௜௞ − ௜݂(ݔො)൯ với ݅ = 1, … ,ܳ Do đó từ (4) ݀ଵ = −1; ݀௜ = 0; ݅ ≠ 1, ݅ ∉ തܳ ; ݀௜ = 0, ݅ ∈ തܳ Vì ݀ = (−1,00, … ,0) ∈ ݈ܿ ൬ܿ݋݊݁ ቀ݂(ܺ) + ܴାொ − ݂(ݔො)ቁ൰⋂(−ܴା௄) Nên ݔො không là nghiệm tối ưu Pareto chính thường theo định nghĩa Benson Định nghĩa 36 (Kuhn và Tucker 1951) Nghiệm ݔො ∈ ܺ được gọi là nghiệm tối ưu Pareto chính thường nếu ݔො là nghiệm tối ưu Pareto và không tồn tại một ℎ ∈ ܴ௡ thỏa mãn:  〈∇ ௜݂(ݔො),ℎ〉 ≤ 0, ∀݅ =