Luận văn Quy hoạch đa mục tiêu

gọi là các hàm ràng buộc. : , 1,2,...,if X i p→ = được gọi là các hàm mục tiêu ( objective function ), ( ) ( ) ( ) ( )( )1 2, ,..., pf x f x f x f x= được gọi là vectơ hàm mục tiêu ( vector objective function ). Ký hiệu ( )Y f X= là ảnh của tập khả thi qua ánh xạ f được, không gian chứa Y được gọi là không gian mục tiêu ( objective space ). 13 Từ “min” ở đây được hiểu theo nghĩa chúng ta muốn tối ưu tất cả các mục tiêu cùng một lúc. Thực tế là các hàm mục tiêu có ràng buộc chặt chẽ nhau, một phương án để các mục tiêu đều đạt được giá trị tốt nhất hầu như không thể tìm được. Điều này sẽ được phân tích kỹ hơn trong mục tiếp theo. Hình 2.2.1. Không gian quyết định và không gian mục tiêu Căn cứ vào các hàm mục tiêu, các hàm ràng buộc, tập khả thi, ta có những loại bài toán QHĐMT như sau: Định nghĩa 2.2.1. Khi tất cả các hàm mục tiêu và các hàm ràng buộc của tập khả thi là tuyến tính thì bài toán QHĐMT được gọi là bài toán quy hoạch tuyến tính đa mục tiêu (QHTTĐMT). Nếu có ít nhất một trong các hàm mục tiêu hoặc các hàm ràng buộc là phi tuyến, bài toán QHĐMT được gọi là bài toán quy hoạch phi tuyến đa mục tiêu (QHPTĐMT). Định nghĩa 2.2.2. Bài toán QHĐMT được gọi là bài toán QHĐMT lồi nếu tất cả các hàm mục tiêu là hàm lồi và tập khả thi là tập lồi. 2.3 Những khó khăn đối với bài toán tối ưu đa mục tiêu Để làm rõ vấn đề, ta xét bài toán tối ưu với hai mục tiêu sau: 14 ( ) ( )( )1 2,min x X f x f x ∈ Trong đó ( ) ( ) [ ]21 2, 1 , 1,1f x x f x x X= = − = − . Với từng mục tiêu riêng rẽ ta có ( )1 0min x X f x ∈ = khi 1 0x = ( )2 0min x X f x ∈ = khi 2 1x = Tuy nhiên, không có bất kỳ phương án *x nào thuộc X thỏa ( ) ( ) ( ) ( )* *1 1 2 2,f x f x f x f x≤ ≤ với mọi x X∈ Như vậy, câu hỏi đặt ra ở đây là như thế nào là một phương án tối ưu của một bài toán QHĐMT? Hình 2.3.1. Đồ thị của các hàm số 2y x= và 1y x= − Để trả lời cho câu hỏi trên, ta trở lại với bài toán QHĐMT trong trường hợp tổng quát. Với x X∈ , ta có ( )f x là một vectơ trong p . Do đó, để chỉ ra như thế nào là 15 một phương án tối ưu của bài toán QHĐMT ta cần một công cụ để so sánh các vectơ với nhau. Thứ tự từng phần thường được sử dụng trong trường hợp này. Tuy nhiên, đây là thứ tự không toàn phần, hai vectơ bất kỳ không phải lúc nào cũng có thể so sánh được. 2.4 Các khái niệm tối ưu Trước khi trình bày các khái niệm về tối ưu trong tối ưu đa mục tiêu ta nêu ra một số thứ tự trong không gian Euclide p . Lấy ( ) ( )1 1 1 1 2 2 2 21 2 1 2, ,..., , , ,..., pp py y y y y y y y= = ∈ và nếu 1 2y y≠ ta đặt { }1 2*: min : k kk k y y= ≠ . Tên và các ký hiệu trong bảng sau sẽ được sử dụng trong luận văn này. Ký hiệu Định nghĩa Tên 1 2y y≤ 1 2y y≤ 1 2y y< 1 2 lexy y≤ 1 2 MOy y≤ 1 2 , 1, 2,...,k ky y k p≤ = 1 2 1 2, 1, 2,..., ; k ky y k p y y≤ = ≠ 1 2 , 1, 2,...,k ky y k p< = * * 1 2 1 2 or k k y y y y< = 1 2 1,..., 1,..., max maxk kk p k ny y= =≤ Thứ tự từng phần yếu Thứ tự từng phần Thứ tự từng phần chặt Thứ tự kiểu từ điển Thứ tự Max Với các thứ tự theo từng phần ( chặt, yếu ), ta định nghĩa các tập con của p như sau : • { }: , 0p py R y≥ = ∈ ≥ , nón không âm của p • { } { }: , 0 \ 0p p py R y≥ ≥= ∈ ≥ =  • { }: , 0 intp p py R y> ≥= ∈ > =  , nón dương của p 16 Ta đi vào định nghĩa các phương án tối ưu trong bài toán QHĐMT Định nghĩa 2.4.1. Điểm khả thi xˆ X∈ được gọi là điểm hữu hiệu (efficient solution) nếu không tồn tại x X∈ thỏa ( ) ( )ˆf x f x≤ . Nếu xˆ hữu hiệu thì ( )ˆf x được gọi là điểm không trội (nondominated point). Tập tất cả các điểm hữu hiệu xˆ X∈ ký hiệu EX và được gọi là tập hữu hiệu (efficient set). Tập tất cả các điểm không trội ( )ˆ ˆy f x Y= ∈ , với ˆ Ex X∈ , ký hiệu NY và được gọi là tập không trội (nondominated set). Một vài định nghĩa khác về điểm hữu hiệu, tuơng đương với định nghĩa trên, thường được sử dụng trong những ngữ cảnh thích hợp sẽ được nêu ra sau đây. xˆ X∈ là hữu hiệu nếu 1. Không tồn tại x X∈ thỏa ( ) ( )ˆk kf x f x≤ , 1,2,...,k p= và ( ) ( )ˆi if x f x≤ với i nào đó thuộc { }1,2,..., p . 2. Không tồn tại x X∈ thỏa ( ) ( ) { }ˆ \ 0pf x f x ≥− ∈− 3. ( ) ( ) { }( )ˆ \ \ 0p pf x f x ≥− ∈ −  với mọi x X∈ 4. ( ) ( )( ) ( ){ }ˆ ˆpf X f x f x≥− =  5. Không tồn tại ( ) ( ) ( ){ }ˆ\f x f X f x∈ với ( ) ( )ˆ pf x f x ≥∈ − 6. ( ) ( )ˆf x f x≤ với x X∈ thì ( ) ( )ˆf x f x= . Từ những định nghĩa trên cho ta sự mô tả về hình học của điểm hữu hiệu và không trội như trong hình 2.4.1. Ta xét bài toán được xét ở mục 2.3 ( ) ( )( )1 2,min x X f x f x ∈ 17 với ( ) ( ) [ ]21 2, 1 , 1,1f x x f x x X= = − = − . Để tìm ảnh của tập khả thi ( )Y f X= trong trường hợp này ta tính 1f theo 2f . Ta có [ ]2 21 , 0,2x f f= − ∈ . Suy ra [ ]21 2 2(1 ) , 0,2f f f= − ∈ Hình 2.4.1. Sự mô tả về mặt hình học của điểm không trội Hình 2.4.2. Đồ thị mô tả sự biểu diễn của 1f qua 2f Như vậy, trong bài toán này ta có [ ]0,1EX = và ( ) [ ]{ }2 2,1 , 0,1NY x x x= − ∈ ∈ 18 Định nghĩa 2.4.2. Điểm xˆ X∈ được gọi là hữu hiệu yếu ( weakly efficient ) nếu không tồn tại x X∈ thỏa ( ) ( )ˆf x f x< , nghĩa là ( ) ( )ˆk kf x f x< với mọi 1,k p= . Khi đó, điểm ( )ˆ ˆy f x= được gọi là điểm không trội yếu ( weakly nondominated ). Điểm xˆ X∈ được gọi là hữu hiệu chặt ( strictly efficient ) nếu không có ˆ,x X x x∈ ≠ thỏa ( ) ( )ˆf x f x≤ . Điểm không trội yếu, điểm hữu hiệu yếu và điểm hữu hiệu chặt lần lượt được ký hiệu , ,wN wE sEY X X . Từ định nghĩa ta có N wNY Y⊂ và sE E wEX X X⊂ ⊂ . Hình 2.4.3. Sự mô tả về mặt hình học của wNY Như đối với điểm hữu hiệu, điểm hữu hiệu yếu cũng có một vài định nghĩa tương đương. xˆ X∈ được gọi là điểm hữu hiệu yếu khi và chỉ khi: 1. Không có x X∈ thỏa ( ) ( )ˆ p pf x f x int ≥ >− ∈ =  2. ( )( )ˆ pf x Y>− =∅  19 Theo định nghĩa, một điểm hữu hiệu không cho phép ta giảm giá trị của một mục tiêu trong khi giữ lại các giá trị tương tự của các mục tiêu khác. Như vậy, giá trị của một hoặc một vài mục tiêu giảm xuống chỉ có thể đạt được khi giá trị của ít nhất một mục tiêu khác tăng lên. Điều này gọi là sự thỏa hiệp. Những thỏa hiệp giữa các mục tiêu có thể được đo lường bằng việc tính toán sự tăng lên của mục tiêu if nói lên phần đơn vị giảm xuống trong mục tiêu jf . Điều này đưa đến khái niệm về điểm hữu hiệu chính thường. Định nghĩa 2.4.3. Điểm xˆ X∈ được gọi là hữu hiệu chính thường ( properly efficient ) nếu nó hữu hiệu và tồn tại một số thực 0M > sao cho với mọi cặp i và x X∈ thỏa ( ) ( )ˆi if x f x< thì tồn tại một chỉ số j thỏa ( ) ( )ˆj jf x f x< và ( ) ( ) ( ) ( ) ˆ ˆ i i j j f x f x M f x f x − ≤ − . Nếu xˆ X∈ là điểm hữu hiệu chính thường thì ( )ˆ ˆy f x= được gọi là điểm không trội chính thường ( properly nondominated point ). Tập các điểm hữu hiệu chính thường và tập các điểm không trội chính thường lần lượt được ký hiệu là pEX và pEY . 2.5 Tối ưu đơn mục tiêu và đa mục tiêu: những khác biệt Trong bài toán tối ưu đơn mục tiêu, công việc chỉ là tìm một phương án tốt nhất cho mục tiêu đó. Do đó, trong các thuật toán của bài toán tối ưu đơn mục tiêu, một phương án mới sẽ được chấp nhận nếu nó có giá trị mục tiêu tốt hơn phương án cũ. Đối với bài toán tối ưu đa mục tiêu, việc giải bài toán thường hướng đến tìm tập hữu hiệu. Tuy nhiên, chúng ta chỉ cần một phương án cuối cùng cho bài toán nên sẽ có sự chọn lựa từ những phương án nằm trong tập hữu hiệu và ở đây có sự thỏa hiệp giữa các mục tiêu. Do đó, quá trình giải bài toán tối ưu đa mục tiêu có sự phối hợp 20 giữa nhà phân tích ( một người hoặc một chương trình máy tính chịu trách nhiệm về mặt toán học của bài toán ) và người ra quyết định ( một người hoặc một nhóm người cung cấp thông tin cho bài toán và lựa chọn phương án sau cùng ). Đó là sự khác biệt cơ bản của tối ưu đơn mục tiêu và đa mục tiêu. 21 Chương 3. Quy hoạch đa mục tiêu: các phương pháp giải 3.1 Phương pháp tổng trọng số ( the weighted sum method ) Ý tưởng của phương pháp là mỗi mục tiêu được nhân với một trọng số , 0i iλ λ∈ ≥ với mọi { }1,2,...,i p∈ sau đó cực tiểu hóa tổng của các hàm mục tiêu đã nhân với từng trọng số. Nghĩa là, việc giải bài toán QHĐMT ( ) ( ) ( )( )1 2, ,...,min p x X f x f x f x ∈ được chuyển về việc giải bài toán đơn mục tiêu có dạng: ( ) 1 min p k k x X k f xλ ∈ = ∑ (3.1.1) Các trọng số ứng với mỗi mục tiêu được chọn phụ thuộc vào tầm quan trọng của các mục tiêu trong bài toán và thường được chuẩn hóa 1 1 p k k λ = =∑ . Định lý 3.1.1. Nếu xˆ là phương án tối ưu của bài toán (3.1.1) thì ˆ wEx X∈ Chứng minh: Ta chứng minh bằng phản chứng. Lấy xˆ là một phương án tối ưu của bài toán (3.1.1). Giả sử xˆ không hữu hiệu yếu. Khi đó tồn tại x X∈ thỏa ( ) ( )ˆi if x f x với ít nhất một i nên ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = <∑ ∑ . Điều này trái với giả thiết xˆ là phương án tối ưu của bài toán (3.1.1). Vậy ˆ wEx X∈ .  Định lý 3.1.2. Nếu xˆ là một phương án tối ưu của bài toán (3.1.1) với các trọng số dương { }( )0, 1,2,...,i i pλ > ∀ ∈ thì ˆ Ex X∈ . 22 Chứng minh: Lấy xˆ X∈ là một phương án tối ưu của bài toán (3.1.1) với các trọng số dương. Giả sử xˆ không hữu hiệu. Nghĩa là tồn tại x X∈ sao cho ( ) ( )ˆi if x f x≤ với mọi 1,2,...,i p= và có ít nhất một bất đẳng thức là chặt. Vì { }0, 1,2,...,i i pλ > ∀ ∈ do đó ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = <∑ ∑ . Điều này trái với giả thiết xˆ X∈ là một phương án tối ưu của bài toán (3.1.1). Vậy xˆ là hữu hiệu.  Định lý 3.1.3. Nếu xˆ là phương án tối ưu duy nhất của bài toán (3.1.1) thì ˆ Ex X∈ . Chứng minh: Lấy xˆ là phương án tối ưu duy nhất của bài toán (3.1.1). Giả sử xˆ không hữu hiệu. Khi đó tồn tại x X∈ sao cho ( ) ( )ˆi if x f x≤ với mọi 1,2,...,i p= và có ít nhất một bất đẳng thức là chặt. Do các trọng số là không âm nên ta có ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = ≤∑ ∑ . Do xˆ là phương án tối ưu duy nhất của bài toán (3.1.1) nên ˆ,x X x x′ ′∀ ∈ ≠ ta có ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = ′<∑ ∑ . Rõ ràng hai bất đẳng thức trên là mâu thuẩn nhau. Vậy ˆ Ex X∈ .  Định lý 3.1.4. Cho X là tập lồi, , 1,2,...,kf k p= là các hàm lồi. Nếu ˆ Ex X∈ thì tồn tại 1 , 1 p p k k λ λ≥ = ∈ =∑ sao cho xˆ là phương án tối ưu của bài toán (3.1.1) Chứng minh: xem Miettinen (1999) trang 89. Theo định lý 3.1.4 tất cả các điểm hữu hiệu của bài toán QHĐMT lồi đều có thể tìm được thông quan phương pháp tổng trọng số. Hình 3.1.1 cho sự diễn giải về mặt hình học của định lý 3.1.1 Sau đây ta đưa ra mối liên hệ giữa phương án tối ưu của bài toán (3.1.1) và điểm hữu hiệu chính thường. 23 Hình 3.1.1. Phương pháp tổng trọng số với bài toán lồi Định lý 3.1.5. ( Geoffrion (1968) ). Lấy 0, 1,2,...,k k pλ > = với 1 1 p k k λ = =∑ là các trọng số dương. Nếu xˆ là phương án tối ưu của (3.1.1) thì xˆ là điểm hữu hiệu chính thường. Chứng minh: Lấy xˆ là một phương án tối ưu của (3.1.1). Trước tiên ta chỉ ra xˆ là hữu hiệu. Giả sử có x X′∈ với ( ) ( )ˆf x f x′ ≤ . Do các trọng số 0kλ > và { } ( ) ( )ˆ1,2,..., : i ii p f x f x′∃ ∈ < dẫn đến điều tương phản: ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = ′ <∑ ∑ Để chỉ ra rằng xˆ hữu hiệu chính thường, lấy ( ) , : 1 max j i j i M p λ λ = − 24 Giả sử xˆ không hữu hiệu chính thường. Thì có { }1,2,...,i p∈ và x X∈ thỏa ( ) ( )ˆi if x f x − với mọi { }1,2,...,j p∈ thỏa ( ) ( )ˆj jf x f x< . Vì vậy ( ) ( ) ( ) ( )( )1ˆ ˆi i j j j i pf x f x f x f xλ λ − − > − Với mọi j i≠ . Suy ra ( ) ( )( ) ( ) ( )( )ˆ ˆ 1 i i i j j jf x f x f x f xp λ λ− > − − ( ) ( )( ) ( ) ( )( )ˆ ˆ 1 i i i j j j j i j i f x f x f x f x p λ λ ≠ ≠ ⇒ − > − −∑ ∑ ( ) ( ) ( ) ( )ˆ ˆi i i i j j j j j i j i f x f x f x f xλ λ λ λ ≠ ≠ ⇒ − > −∑ ∑ ( ) ( ) 1 1 ˆ p p j j j j j j f x f xλ λ = = ⇒ >∑ ∑ trái với tính tối ưu của xˆ đối với bài toán (3.1.1). Do đó xˆ là hữu hiệu chính thường.  Định lý 3.1.6. ( Geoffrion (1968)). Cho nX ⊂  là tập lồi và :kf X →  là các hàm lồi với 1,2,...,k p= . Thì xˆ là hữu hiệu chính thường nếu và chỉ nếu xˆ là một phương án tối ưu của (3.1.1) với các trọng số 0, 1,2,...,k k pλ > = . Chứng minh: Do định lý 3.1.5 ta chỉ phải chứng minh điều kiện cần. Lấy xˆ X∈ là hữu hiệu chính thường. Theo định nghĩa, tồn tại số dương M thỏa với mọi 1,2,...,i p= hệ 25 ( ) ( ) ( ) ( ) ( ) ( ) ˆ ˆ ˆ i i i j i j f x f x f x Mf x f x Mf x j i < + < + ∀ ≠ không có lời giải. Theo định lý 1.2.5, tồn tại các số 0, 1,2,...,ik k pλ ≥ = với 1 1 p i k k λ = =∑ sao cho với mọi x X∈ ta có ( ) ( ) ( )( ) ( ) ( ) ( )( )ˆ ˆ ˆi i i ii i k i k i i k i k k i k i f x f x Mf x f x f x Mf xλ λ λ λ ≠ ≠ + + ≥ + +∑ ∑ ( ) ( ) ( ) ( ) ( ) ( )ˆ ˆ ˆi i i i i ii i k i j j i i k i j j k i j i k i j i f x f x M f x f x f x M f xλ λ λ λ λ λ ≠ ≠ ≠ ≠ ⇔ + + ≥ + +∑ ∑ ∑ ∑ ( ) ( ) ( ) ( ) 1 1 ˆ ˆ p p i i i i k i j j k i j j k j i k j i f x M f x f x M f xλ λ λ λ = ≠ = ≠ ⇔ + ≥ +∑ ∑ ∑ ∑ ( ) ( ) ( ) ( )ˆ ˆi ii j j i j j j i j i f x M f x f x M f xλ λ ≠ ≠ ⇔ + ≥ +∑ ∑ Ta có bất đẳng thức như vậy với mọi 1,2,...,i p= . Lấy tổng các bất đẳng thức đó theo chỉ số i ta được ( ) ( ) ( ) ( ) 1 1 ˆ ˆ p p i i i j j i j j i j i i j i f x M f x f x M f xλ λ = ≠ = ≠     + ≥ +        ∑ ∑ ∑ ∑ ( ) ( ) ( ) ( ) 1 1 1 1 ˆ ˆ p p p p i i i j j i j j i i j i i i j i f x M f x f x M f xλ λ = = ≠ = = ≠ ⇔ + ≥ +∑ ∑∑ ∑ ∑∑ ( ) ( ) 1 1 ˆ1 1 p p i i k k k k k i k k i k M f x M f xλ λ = ≠ = ≠     ⇔ + ≥ +        ∑ ∑ ∑ ∑ Với mọi x X∈ . 26 Ta có thể chuẩn hóa các giá trị 1 , 1,2,...,ik i k M k pλ ≠   + =    ∑ để chúng có tổng bằng một. Như vậy ta sẽ được các trọng số dương , 1,2,...,i i pλ = sao cho xˆ là lời giải tối ưu của (3.1.1).  3.2 Phương pháp ε - ràng buộc ( theε - constraint method ) Bên cạnh phương pháp tổng trọng số, phương pháp ε - ràng buộc được biết đến như một phương pháp nổi tiếng giải các bài toán QHĐMT. Không có sự tổng hợp các mục tiêu, mà chỉ một trong các mục tiêu gốc được cực tiểu hóa, trong khi các mục tiêu khác được chuyển thành các ràng buộc. Thay cho vệc xét bài toán ( ) ( ) ( )( )1 2, ,...,min p x X f x f x f x ∈ Ta xét bài toán sau và được ký hiệu là ( )jP ε ( ) ( ) 1,2,..., min j x X k k f x f x k p k jε ∈ ≤ = ≠ Với , 1,2,..., , k k p k jε ∈ = ≠ . Thành phần jε không liên quan đến ( )jP ε . Hình 2.3.1 mô tả phương pháp ε − ràng buộc cho bài toán hai mục tiêu,mục tiêu 2f được giữ lại để cực tiểu hóa, 1f được chuyển thành ràng buộc. Trường hợp cận trên đặt ra cho 1f là 1 aε , bài toán ( )2P ε không có phương án tối ưu. Trường hợp các cận trên đặt ra cho 1f là 1 1 1, , b c dε ε ε phương án tối ưu của các bài toán tương ứng lần lượt là B, C, D. Mệnh đề 3.2.1. Nếu xˆ là một phương án tối ưu của ( )jP ε , thì xˆ là hữu hiệu yếu. 27 Chứng minh: Giả sử ˆ wEx X∉ . Thì có x X∈ thỏa ( ) ( )ˆk kf x f x< với mọi 1,2,...,k p= . Đặc biệt ( ) ( )ˆj jf x f x< và ( ) ( )ˆk k kf x f x ε< ≤ với k j≠ , suy ra x là điểm khả thi của ( )jP ε . Điều này trái với xˆ là phương án tối ưu của ( )jP ε .  Hình 3.2.1. Phương pháp ε − ràng buộc Mệnh đề 3.2.2. Nếu xˆ là phương án tối ưu duy nhất của ( )jP ε với j nào đó. Thì ˆ sEx X∈ ( và vì vậy ˆ Ex X∈ ). Chứng minh: Giả sử có x X∈ với ( ) ( )ˆf x f x≤ . Điều này đồng nghĩa với ( ) ( )ˆj jf x f x≤ và ( ) ( )ˆk k kf x f x ε≤ ≤ với mọi k j≠ . Do đó x cũng là một phương án tối ưu của ( )jP ε . Tính duy nhất của xˆ suy ra ˆx x= . Kết quả trên chỉ ra rằng ( ) ( ){ }ˆ: 1x X f x f x∈ ≤ = Vậy ˆ sEx X∈ .  28 Định lý 3.2.3. Điểm khả thi xˆ X∈ là hữu hiệu nếu và chỉ nếu có một ˆ pε ∈ thỏa xˆ là một phương án tối ưu của ( )jP ε với mọi 1,2,...,j p= . Chứng minh: " "⇒ Lấy ( )ˆ ˆf xε = . Giả sử xˆ không là phương án tối ưu của ( )jP ε với j nào đó. Thì phải có x X∈ với ( ) ( )ˆj jf x f x< và ( ) ( )ˆk k kf x f xε≤ = với mọi k j≠ . Nghĩa là ˆ Ex X∉ , vô lý. " "⇐ Giả sử ˆ Ex X∉ . Thì có một chỉ số { }1,2,...,j p∈ và x X∈ thỏa ( ) ( )ˆj jf x f x< đồng thời ( ) ( )ˆk kf x f x≤ với k j≠ . Vì thế xˆ không thể là một lời giải tối ưu của ( )jP ε thỏa ( )ˆk kf x ε≤ với k j≠ .  Định lý 3.2.3 chỉ ra rằng với việc lựa chọn ε thích hợp, mọi lời giải hữu hiệu có thể tìm được. Tuy nhiên, như chứng minh đã chỉ ra, các jε này bằng giá trị của mục tiêu tại điểm hữu hiệu mà ta muốn tìm. Một sự xác nhận hoặc kiểm tra tính hữu hiệu thích hợp hơn là việc tìm ra lời giải hữu hiệu. Định lý sau đây chỉ ra mối liên hệ giữa phương pháp tổng trọng số và phương pháp ε - ràng buộc. Định lý 3.2.4. ( Chankong và Haimes (1983)). 1. Giả sử xˆ là một phương án tối ưu của ( ) 1 min p k k x X k f xλ ∈ = ∑ . Nếu 0jλ > thì tồn tại εˆ thỏa xˆ cũng là một phương án tối ưu của ( )jP ε . 29 2. Giả sử X là tập lồi và : nkf →  là các hàm lồi. Nếu xˆ là một phương án tối ưu của ( )jP ε với j nào đó thì tồn tại ˆ pλ ≥∈ sao cho xˆ là một lời giải tối ưu của ( ) 1 ˆ p k k x X k f xmin λ ∈ = ∑ . Chứng minh: 1. Đặt ( )ˆ ˆf xε = . Từ tính tối ưu của xˆ đối với bài toán tổng trọng số ta có ( ) ( )( ) 1 ˆ 0 p k k k k f x f xλ = − ≥∑ với mọi x X∈ Giả sử xˆ không tối ưu đối với bài toán ( )jP ε với các thành phần bên phải là εˆ thì 'x X∃ ∈ thỏa ( ) ( )ˆ'j jf x f x< và ( ) ( )ˆ'k kf x f x≤ với k j≠ . Do đó ( ) ( )( ) ( ) ( )( )ˆ ˆ' ' 0j j j k k k k j f x f x f x f xλ λ ≠ − + − <∑ ( ) ( )( ) 1 ˆ 0 p k k k k f x f xλ = ′⇒ − <∑ Điều này vô lý. 2. Giả sử xˆ là phương án tối ưu của ( )jP ε . Khi đó không có x X∈ thỏa ( ) ( )ˆj jf x f x< và ( ) ( )ˆk k kf x f x ε≤ ≤ với k j≠ . Sử dụng tính lồi của kf và định lý 1.2.5 chỉ ra rằng có ˆ pλ ≥∈ thỏa ( ) ( )( ) 1 ˆ ˆ 0 p k k k k f x f xλ = − ≥∑ với mọi x X∈ . Vì ˆ pλ ≥∈ ta được ( ) ( ) 1 1 ˆ ˆ ˆ p p k k k k k k f x f xλ λ = = ≥∑ ∑ với mọi x X∈ 30 λˆ là vectơ trọng số cần tìm.  3.3 Phương pháp lai ( The hybrid method ) Ta có thể kết hợp phương pháp tổng trọng số và phương pháp ε - ràng buộc. Trong trường hợp đó, bài toán vô hướng để được giải có một tổng trọng số mục tiêu và các ràng buộc trên tất cả các mục tiêu. Lấy 0x X∈ là một điểm tùy ý. Ta xét bài toán ( ) ( ) ( ) 1 0 min , 1,2,..., p k k k k k f x f x f x k p x X λ = ≤ = ∈ ∑ (3.3.1) ở đây pλ ≥∈ . Định lý 3.3.1. Lấy pλ >∈ . Điểm 0x X∈ là phương án tối ưu của bài toán (3.3.1) nếu và chỉ nếu 0 Ex X∈ . Chứng minh: " "⇐ Lấy 0x X∈ là hữu hiệu. Thì không có x X∈ thỏa ( ) ( )0f x f x≤ . Vì vậy, bất kỳ một phương án khả thi nào của (3.3.1) sẽ thỏa ( ) ( )0f x f x= và cũng là một phương án tối ưu. " "⇒ Lấy 0x là một phương án tối ưu của (3.3.1). Nếu có x X∈ thỏa ( ) ( )0f x f x≤ , các trọng số dương chỉ ra rằng ( ) ( ) 1 1 ˆ p p k k k k k k f x f xλ λ = = <∑ ∑ 31 Vậy 0x là hữu hiệu. 3.4 Phương pháp co giản ràng buộc ( The elastic constraint method ) Đối với phương pháp ε - ràng buộc ta không có kết quả về điểm hữu hiệu chính thường. Thêm vào đó, bài toán ( )jP ε có thể khó giải trong thực hành vì có thêm các ràng buộc ( )k kf x ε≤ . Với mục đích giải quyết bài toán này ta có thể “nới lỏng” các ràng buộc này bằng việc cho phép chúng được vi phạm và việc có thể bị phạt bất kỳ sự vi phạm nào trong hàm mục tiêu. Ehrgott và Ryan đã sử dụng ý tưởng này để pháp triển sự co giản ràng buộc vô hướng ( ) ( ) min 0 j k k k j k k k k f x s f x s k j s k j x X µ ε ≠ + − ≤ ≠ ≥ ≠ ∈ ∑ (3.4.1) ở đây 0,k k jµ ≥ ≠ . Nếu ( )ˆ ˆ,x s là một phương án tối ưu của (3.4.1), thì không mất tính tổng quát ta có thể giả sử ( ){ }ˆ ˆax 0,k k ks m f xε= − . Mệnh đề 3.4.1. Nếu ( )ˆ ˆ,x s là một phương án tối ưu của (3.4.1) với 0µ ≥ thì ˆ wEx X∈ . Chứng minh: Giả sử xˆ không hữu hiệu yếu. Thì có x X∈ thỏa ( ) ( )ˆk kf x f x< với 1,2,...,k p= . Thì ( )ˆ,x s là một phương án khả thi đối với (3.4.1) và có giá trị mục tiêu bé hơn của ( )ˆ ˆ,x s .  Mệnh đề 3.4.2. Nếu xˆ là duy nhất trong một phương án tối ưu của (3.4.1), thì ˆ sEx X∈ . 32 Chứng minh: Giả sử có x X∈ thỏa ( ) ( )ˆk kf x f x≤ , 1,2,...,k p= . Thì ( )ˆ,x s là một phương án khả thi đối với (3.4.1). Vì giá trị hàm mục tiêu của ( )ˆ,x s không lớn hơn của ( )ˆ ˆ,x s , tính duy nhất của xˆ chỉ ra ˆx x= . Suy ra ( ) ( ){ }ˆ: 1x X f x f x∈ ≤ = Vậy ˆ sEx X∈ .  Hệ quả sau đây có được từ mệnh đề 3.4.2 với ( )ˆ ˆ, 0f x sε = = và kµ = ∞ với mọi 1,2,...,k p= . Hệ quả 3.4.3. Lấy ˆ Ex X∈ . Thì tồn tại , 0ε µ ≥ và sˆ thỏa ( )ˆ ˆ,x s là một phương án tối ưu của (3.4.1) với mọi { }1,2,...,j p∈ . Định nghĩa 3.4.4. Tập không trội NY được gọi là ổn định ngoài ( externally stable) nếu với mỗi \ Ny Y Y∈ tồn tại ˆ Ny Y∈ thỏa ˆ py y ≥∈ + . Định lý 3.4.5. Cho NY ổn định ngoài , ˆ pEx X∈ . Thì với mỗi { }1,2,...,j p∈ , có ˆ, , jsε µ với jkµ < ∞ với mọi k j≠ thỏa ( )ˆ ˆ,x s là một phương án tối ưu của (3.4.1) với mọi 1pµ −∈ , jµ µ≥ . Chứng minh: Ta chọn ( )ˆ: , 1,2,...,k kf x k pε = = . Vì vậy ta có thể chọn ˆ 0s = . Lấy { }1,2,...,j p∈ . Vì xˆ là hữu hiệu chính thường nên có 0M > thỏa với mọi x X∈ mà ( ) ( )ˆj jf x f x< thì tồn tại k j≠ thỏa ( ) ( )ˆk kf x f x< và ( ) ( ) ( ) ( ) ˆ ˆ j j k k f x f x M f x f x − < − . Ta xác định jµ bởi { }ax ,0jk m Mµ = với mọi k j≠ 33 Lấy x X∈ và ps∈ thỏa ( ){ } ( ) ( ){ }ˆmax 0, ax 0,k k k k ks f x m f x f xε= − = − với mọi k j≠ . Ta cần chỉ ra rằng ( ) ( ) ( )ˆ ˆ ˆj k k j k k j k j k j f x s f x s f xµ µ ≠ ≠ + ≥ + =∑ ∑ (3.4.2) Trước tiên, ta có thể giả sử Ex X∈ trong (3.4.2). Nếu không, ta có ' Ex X∈ với ( ) ( )'f x f x≤ ( vì NY là ổn định ngoài) và 's với ( ){ }' ax 0, 'k k ks m f x ε= − . Vì 's s≤ ta được ( ) ( )''j k k j k k k j k j f x s f x sµ µ ≠ ≠ + ≤ +∑ ∑ với bất kỳ 0µ ≥ . Và khi đó ta chứng minh (3.4.2) bằng việc thay x bởi x′ và ks bởi ks′ . Bây giờ, ta lấy Ex X∈ . Xét trường hợp ( ) ( )ˆj jf x f x≥ . Thì ( ) ( ) ( )ˆ ˆ ˆ0j k k j j k k k j k j f x s f x f x sµ µ ≠ ≠ + > + = +∑ ∑ với bất kỳ 0µ ≥ Ta xét trường hợp ( ) ( )ˆj jf x f x . Do cả xˆ và x đều hữu hiệu, ( )I x ≠ ∅ . Hơn nữa, với ( ) ,k I x k j∉ ≠ ta có ( ) ( ){ }ˆax 0, 0k k ks m f x f x= − = . Lấy ( )'k I x∈ thì ( ) ( ) ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ' ' ' ' ' ' ' ˆ ˆ ˆ ˆ ˆ ˆ ˆ j j k k j k k k j k j j j j k k I x k k j j j k k k j j j k k k k f x s f x s f x f x f x s f x f x f x f x f x s f x f x f x f x f x f x f x f x f x µ µ ≠ ≠ ∈ + ≥ + − ≥ + − − ≥ + − − = + − − ∑ ∑ ∑ ( ) ( )ˆ ˆ ˆj j k k k j f x f x sµ ≠ = = +∑ 34 Điều này suy ra từ jk kµ µ≥ , định nghĩa của j kµ , tính không âm của tất cả các phần tử ( ) ( )ˆk k ks f x f x= − với ( )k I x∈ và ˆ 0s = . 3.5 Phương pháp Benson ( Benson’s method ) Ý tưởng phương pháp là đưa ra phương án ban đầu 0x X∈ , nếu nó chưa hữu hiệu, đưa ra một lời giải khác trội hơn. Để làm như thế, biến lệch không âm ( ) ( )0k k kl f x f x= − được giới thiệu và tổng cực đại của chúng. Kết quả này thu được x trội hơn 0x nếu nó tồn tại, và mục tiêu đó đảm bảo rằng nó là hữu hiệu, đẩy x xa 0x đến mức có thể. ( ) ( ) 1 0 max 0 1,2,..., 0 p k k k k k l f x l f x k p l x X = − − = = ≥ ∈ ∑ (3.5.1) Điều trước tiên trong việc giải (3.5.1) là kiểm tra tính hữu hiệu của 0x . Định lý 3.5.1. Phương án khả thi 0x X∈ là hữu hiệu nếu và chỉ nếu giá tri mục tiêu tối ưu của (3.5.1) bằng 0. Chứng minh: " "⇐ Lấy ( ),x l là một phương án tối ưu của (3.5.1). Vì 0, 1,2,...,kl k p≥ = và đặt ( ) ( )0k k kl f x f x= − ta có ( ) ( ) 1 0 0 0 1,2,..., 1,2,..., p k k k k k l l k p f x f x k p = = ⇔ = = ⇔ = = ∑ 35 Vì vậy, nếu giá trị tối ưu là 0, và x X∈ thỏa ( ) ( )0f x f x≤ ta phải có ( ) ( )0f x f x= , nghĩa là 0x là điểm hữu hiệu. " "⇒ Ngược lại, 0x hữu hiệu thì tập khả thi của (3.5.1) chỉ có các phần tử ( ),x l với x X∈ và ( ) ( )0f x f x= và vì vậy 0l = .  Mệnh đề 3.5.2. Nếu bài toán (3.5.1) có một phương án tối ưu ( )ˆˆ,x l ( giá trị mục tiêu tối ưu hữu hạn ) thì ˆ Ex X∈ . Chứng minh: Giả sử Ex X∉ . Thì có 'x X∈ thỏa ( ) ( )ˆ'k kf x f x≤ với mọi 1,2,...,k p= và ( ) ( )ˆ'j jf x f x< với ít nhất một { }1,2,...,j p∈ . Ta đặt ( ) ( )0:l f x f x′ ′= − thì ( ),x l′ ′ là khả thi đối với (3.5.1) vì ( ) ( ) ( ) ( )' 0 0 ˆˆ 0k k k k k kl f x f x f x f x l′= − ≥ − = ≥ Hơn nữa, 1 1 ˆ p p k k k k l l = = ′ >∑ ∑ vì ˆj jl l′ > . Điều này không thể vì ( )ˆˆ,x l là phương án tối ưu của (3.5.1).  Định lý 3.5.3. ( Benson ( 1978) ). Giả sử các hàm , 1,2,...,kf k p= lồi và nX ⊂  là một tập lồi. Nếu (3.5.1) không có giá trị mục tiêu tối ưu