Phương pháp xấp xỉ ngoài với kỹ thuật rẽ nhánh giải bài toán tối ưu toàn cục

- 11.2 Bài toán quy hoạch lồi với ràng buộc tích.
- 71.2.2 Dạng bài toán tương đương.
- 71.3 Bài toán tối ưu trên tập Pareto.
- 191.3.1 Giới thiệu bài toán.
- 191.3.2 Bài toán tương đương với (OPY.
- 232 Thuật toán giải bài toán quy hoạch lồi với ràng buộc tích 242.1 Cơ sở lý thuyết của thuật toán.
- 44i 3 Thuật toán giải bài toán tối ưu trên tập Pareto 513.1 Cơ sở lý thuyết của thuật toán.
- 533.2 Thuật toán giải Bài toán (OPG.
- Đây là hai bài toán tối ưu toàn cục cónhiều ứng dụng để giải quyết các bài toán nảy sinh từ thực tế.
- Bài toán này được gọi là Bài toán quy hoạch đamục tiêu.
- Đó là bài toán tối ưu một hàm thực trên tập nghiệm hữuhiệu của một bài toán quy hoạch đa mục tiêu.
- Nhiều tác giả đã đề xuấtcác thuật toán để giải bài toán này, chẳng hạn xem J.
- 213 - 233.Chương 3: "Thuật toán giải bài toán tối ưu trên tập Pareto" trìnhbày thuật toán do chúng tôi đề xuất để giải bài toán cực đại một hàm mục tiêucó dạng ϕ(f(x.
- trong đó ϕ là hàm đơn điệu tăng, trên tập nghiệm hữu hiệucủa bài toán quy hoạch lồi hai mục tiêu Vmin{f(x.
- Thông thường, người ta nghiên cứu Bài toán (P ) với giả thiết sau:Giả thiết 1.1.
- 0 với mọi x ∈ X.Bài toán (P ) là bài toán quy hoạch toàn cục.
- (1.2.1)7 Kí hiệu D là tập chấp nhận được của Bài toán (P.
- p.Trong trường hợp này, việc giải Bài toán (P ) quy được về việc giải một bàitoán quy hoạch lồimin f0(x),v.đ.k fi(x.
- p,x ∈ X.Kết quả sau sẽ mô tả mối quan hệ giữa Bài toán (S) và Bài toán (P ).Mệnh đề 1.4.9 (i) Điểm x∗là nghiệm tối ưu toàn cục của Bài toán (P ) khi và chỉ khi tồntại một điểm y∗thỏa mãn (x∗, y∗) là nghiệm tối ưu toàn cục của Bài toán(S).(ii) Bài toán (P ) không chấp nhận được khi và chỉ khi Bài toán (S) cũng khôngchấp nhận đượcChứng minh.
- (i) Vì Bài toán (P ) và Bài toán (S) có cùng hàm mục tiêu f0(x)không phụ thuộc vào y nên ta chỉ cần chứng minh rằng một điểm x là nghiệmchấp nhận được của Bài toán (P ) khi và chỉ khi tồn tại một điểm y sao cho (x, y)là nghiệm chấp nhận được của Bài toán (S).Thật vậy, giả sử điểm x là một phương án chấp nhận được của Bài toán (P ),tức là x ∈ X vàQpi=1fi(x.
- Thật vậy, giả sử phản chứng, Bài toán (S) chấp nhận được tức làtồn tại cặp (x, y) là nghiệm chấp nhận được của Bài toán (S).
- Khi đó theo ýchứng minh trên thì điểm x là nghiệm chấp nhận được của Bài toán (P.
- Mâuthuẫn với giả thiết Bài toán (P ) không chấp nhận được.Ngược lại, Bài toán (S) không chấp nhận được thì Bài toán (P ) cũng khôngchấp nhận được.
- Thật vậy, giả sử phản chứng, Bài toán (P ) chấp nhận được tứclà tồn tại điểm x là nghiệm chấp nhận được của Bài toán (P.
- Do đó, thay vì giải bài toán tối ưu không lồi (S) trênkhông gian Rn+p, người ta tách Bài toán (S) thành hai Bài toán (P (y)) và (MP ),trong đó Bài toán (P (y)) là một quy hoạch lồi trong không gian Rnvà Bài toán(MP ) là một quy hoạch không lồi trên không gian Rp.Với mỗi y ∈ Rp, bài toán quy hoạch lồi (P (y)) được phát biểu như saumin f0(x), (P (y))v.đ.k x ∈ M(y),trong đóM(y.
- p}.Giá trị tối ưu của bài toán này được ký hiệu là g(y).Dễ thấy rằng với mỗi y ∈ Rptập chấp nhận được M(y) là tập lồi compact.Thật vậy, với mỗi i = 1, 2.
- tứclà Bài toán (P (y)) không chấp nhận được, như thường lệ, người ta định nghĩag(y.
- +∞.Cho y thay đổi, ta có hàm sốg :Rp→ Ry 7→ g(y),trong đó g(y) là giá trị tối ưu của Bài toán (P (y.
- p, được xác định bởi (1.2.1).Ký hiệu vmlà giá trị tối ưu của Bài toán (MP.
- Vì vậy, Bài toán (MP ) luôn có nghiệm tối ưu (xemĐịnh lý 2.1 trong [1]).Mối quan hệ giữa các bài toán (P.
- f0(x) với mọi x ∈ M(y∗) tức x∗∈ Argmin(P (y∗)).Theo định nghĩa, giá trị tối ưu của Bài toán (P (y.
- g(y) với mọi y ∈ Gmhay y∗là nghiệm tối ưu của Bài toán (MP ).(ii) Theo Mệnh đề 1.4, Bài toán (P ) không chấp nhận được khi và chỉ khiBài toán (S) không chấp nhận được.
- Khi đó, không tồn tại cặp (x, y) sao chox ∈ M(y) và y ∈ Gm, tức Bài toán (S) không chấp nhận được.Theo Mệnh đề 1.7, việc giải Bài toán (P ) được tiến hành theo hai pha:Pha 1: Giải bài toán tối ưu không lồi (MP ) trên không gian Rpđược nghiệm tốiưu y∗;Pha 2: Xác định nghiệm tối ưu x∗của bài toán quy hoạch lồi (P (y.
- (1.2.17)Xem minh họa tập Gmbtrong trường hợp p = 2 ở Hình 1.5.Kết quả sau đây cho ta tính chất đặc sắc về nghiệm tối ưu của Bài toán(MP ).Mệnh đề 1.8.
- Giả sử ˆy là nghiệm tối ưu toàn cục của Bài toán (MP.
- Từ đó suy raλ ≤1(Qpi=1ˆyi)1/p.Do đó nghiệm tối ưu của Bài toán (T ) là λ∗=1(Qpi=1ˆyi)1/p.VìQpi=1ˆyi≤ 1 nên λ ≥ 1.
- g(ˆy).18 Vì ˆy là nghiệm tối ưu toàn cục của Bài toán (MP ) và y∗∈ Gmnên g(y∗) ≥g(ˆy).
- g(ˆy) hay y∗∈ Gmblà nghiệm tối ưu của Bài toán (MP ).Theo Mệnh đề 1.8, trong Pha 1 của lược đồ giải Bài toán (P ) thay vì Bàitoán (MP.
- (MPB)Chương 2 của luận văn sẽ giới thiệu chi tiết thuật toán nhánh cắt giải Bài toán(MP B) này.1.3 Bài toán tối ưu trên tập Pareto1.3.1 Giới thiệu bài toánCho a, b ∈ Rp.
- p, là các hàm tuyếntính và X là tập lồi đa diện khác rỗng thì Bài toán (CMOP ) được gọi là Bàitoán quy hoạch tuyến tính đa mục tiêu (LMOP ).Tương ứng với Bài toán (CMOP.
- x ∈ X},được gọi là tập giá trị (outcome set) của bài toán này.Định nghĩa 1.2.
- Điểm x0∈ X được gọi là nghiệm hữu hiệu của Bài toán(CMOP ) nếu f(x0) là một điểm hữu hiệu của tập giá trị Y , tức f(x0.
- Vì vậy, Bài toán (CMOP ) thuộc lớp bài toánkhó.
- Đó là bài toán tối ưu một hàm thực trên tập nghiệm hữuhiệu của bài toán quy hoạch đa mục tiêu.
- Do đó, đây là một bài toán có nhiềuứng dụng trong lý thuyết ra quyết định.
- Yamamoto [23].21 Luận văn này nghiên cứu bài toán tối ưu trên tập Paretomax h(x) v.đ.k.
- y ∈ YE.Mối liên hệ giữa hai Bài toán (PX) và (OPY) được chỉ ra trong mệnh đề dướiđâyMệnh đề 1.9.
- Điểm x∗là nghiệm tối ưu của Bài toán (PX) khi và chỉ khi tồntại điểm y∗với y∗≥ f(x∗) là nghiệm tối ưu của (OPY).Theo Mệnh đề 1.9, việc giải bài toán tối ưu trên tập Pareto (PX) cũng sẽđược tiến hành theo hai pha:Pha 1: Giải Bài toán (OPY) tìm nghiệm tối ưu y∗;Pha 2: Xác định điểm x∗∈ X thỏa mãn f(x.
- Khi đó, x∗là nghiệm tối ưucủa Bài toán (PX).Như đã biết, nếu f1, f2là các hàm tuyến tính thì tập ảnh Y là tập lồi.
- Tập điểm hữu hiệu của G trùng với tập điểm hữu hiệu của tậpgiá trị Y của Bài toán quy hoạch lồi đa mục tiêu (CMOP.
- tứcGE= YE.Theo Mệnh đề 1.10, Bài toán (OPY) tương đương với bài toánmax ϕ(y) (OPG)v.đ.k.
- p.Như đã phân tích ở Mục 1.2, Chương 1, việc giải Bài toán (P ) được tiếnhành theo hai pha:24 Pha 1: Tìm nghiệm tối ưu y∗của bài toán quy hoạch không lồimin{g(y.
- p}.Pha 2: Tìm nghiệm tối ưu x∗của bài toán quy hoạch lồi (P (y∗))min f0(x), (P (y∗))v.đ.k fi(x.
- p,x ∈ X.Theo Mệnh đề 1.7, ta có x∗là nghiệm tối ưu của bài toán quy hoạch lồivới ràng buộc tích (P ).Mục đích chính của chương này là trình bày thuật toán nhánh cắt giải Bàitoán (MP B) do H.P.
- Điều thú vị ở thuật toán này là khi thuậttoán kết thúc, ta nhận được đồng thời cả nghiệm y∗của Bài toán (MP B) và x∗của Bài toán (P.
- Nếu thuật toán không dừng thì bất kỳ điểm tụ nào của dãy {yTk,γ}cũng là một nghiệm tối ưu toàn cục của Bài toán (MP ).Chứng minh.
- Vì y ∈ H vàQpi=1yi= 1 nên y ∈ Gmbhay y là nghiệmchấp nhận được của Bài toán (MP ).Vì vmlà nghiệm tối ưu của Bài toán (MP ) mà y ∈ Gmbnên vm≤ g(y).
- Vậy y là nghiệm tối ưu toàn cục của Bài toán (MP ).Mệnh đề 2.3.
- Giải Bài toán (P ) như saumin f0(x)v.đ.k x ∈ X,f1(x)f2(x)f3(x.
- Ở Bước khởi tạo, đỉnh xác định v0,10của đơn hình T0,1đạtgiá trịv Nghiệm tối ưu của Bài toán (MP (T0,1)) đạt giá trị làyT giá trị của hàm mục tiêu tương ứng là g(yT0,1.
- Nhận thấy yT18,1thỏa mãn điều kiệnQ3i=1yi ε nên thuật toán dừng.Nghiệm tối ưu ε xấp xỉ của Bài toán (MP ) là yT và giá trị tối ưu tương ứng là g(yT18,1.
- Đồng thời, ta nhận đượcnghiệm tối ưu ε xấp xỉ của Bài toán (P ) làxT với giá trị tối ưu tương ứng là f0(xT18,1.
- Ở Bước khởi tạo, đỉnh xác định v0,10của đơn hình T0,1đạt giátrịv Nghiệm tối ưu của Bài toán (MP (T0,1)) đạt giá trị làyT giá trị của hàm mục tiêu tương ứng là g(yT0,1.
- Nhận thấy yT11,1thỏa mãn điều kiệnQ3i=1yi ε nên thuật toán dừng.Nghiệm tối ưu ε−xấp xỉ của Bài toán (MP ) là yT vàgiá trị tối ưu tương ứng là g(yT11,1.
- Đồng thời, ta nhận được nghiệmtối ưu ε-xấp xỉ của Bài toán (P ) làxT với giá trị tối ưu tương ứng là f0(xT18,1.
- Tụy trong [22] để minh họa cho thuậttoán xấp xỉ ngoài sử dụng các siêu hộp (polyblock) để giải bài toán cực đại hàmtuyến tính với ràng buộc đơn điệu.Ví dụ 2.3.
- Đồng thời, ta nhận được nghiệm tối ưu của Bài toán (P ) làxT với giá trị tối ưu tương ứng là f0(xT0,1.
- Cách xây dựng cácđơn hình, lược đồ rẽ nhánh rút gọn, tìm nghiệm tối ưu của các bài toán con,...cũng được trình bày đầy đủ.
- Sự hội tụ của thuậttoán đã được trình bày rõ.50 Chương 3Thuật toán giải bài toántối ưu trên tập ParetoXét bài toán tối ưu trên tập Paretomax h(x.
- Giả thiết các hàm fj, j = 1, 2, nhận giá trị dươngkhông làm giảm tính tổng quát của bài toán.
- R2+là tập giá trị của Bài toán (CMOP ).Pha 2: Giải hệf(x.
- (SPi)Dễ thấy αicũng là giá trị tối ưu của bài toán quy hoạch lồi min{fi(x.
- Rn+plà một nghiệm tối ưucủa bài toán (Pi) được cho bởimin yk(Pi)v.đ.k.
- λyO∈ G,λ ≥ 1.Theo định nghĩa của tập G, Bài toán (T (yO)) có thể viết dưới dạng tườngminh như saumin λ (T (yO))v.đ.k.
- m,λ ≥ 1.Dễ thấy Bài toán (T (yO)) là quy hoạch lồi với hàm mục tiêu tuyến tính vàluôn có nghiệm tối ưu.
- Gọi (x∗, λ∗)Tlà nghiệm tối ưu của Bài toán (T (yO.
- Rõràng α0là cận dưới tốt nhất hiện tại của Bài toán (OPG).
- Điểm chấp nhận được y∗∈ GE= YEđược gọi là nghiệm tối ưu ε−xấp xỉ của Bài toán (OPG) nếu tồn tại một cậntrên β∗của bài toán này thỏa mãnβ∗− ϕ(y.
- Khi đó ybestlà nghiệm tối ưu ε−xấpxỉ của Bài toán (OPG) và xbestlà nghiệm xấp xỉ của Bài toán (PX).
- Nghiệm tối ưu của Bài toán (P (S)) đạt tại cạnhyL, yRcủađơn hình S.Chứng minh.
- Gọi y∗là nghiệm tối ưu của bài toán max{ϕ(y)|y ∈ S}.
- ta cóy2=αd2−d1d2y1.Do đó, Bài toán P (S) có thể đưa về một bài toán cực đại hàm một biến trênmột khoảng đóng trong Rmax{θ(y1)|y`L1≤ y1≤ y`R1}, (P1(S))trong đóθ(y1.
- Theo lý luận trên, thay vì giải Bài toán (P (S.
- Nếu yopt1là nghiệm tối ưu của Bài toán (P (S1))thì yopt= (yopt1, yopt2) là nghiệm tối ưu của Bài toán (P (S.
- Đặt T0:= {S0,1} và U0:= S0,1;– Tìm giá trị tối ưu β(S0) của Bài toán P (S0.
- (Áp dụng lược đồ rẽ nhánh cho Skvới điểm chia yωk)– Đặt Sk1là 2−đơn hình sinh ra bởi hai điểm yLvà yR= yωkvà Sk2là2−đơn hình sinh ra bởi hai điểm yL= yωkvà yR;– Với mỗi i = 1, 2, tìm giá trị tối ưu β(Ski) của Bài toán (P (Ski.
- Thuật toán dừng sau hữu hạn bước và sinh ra nghiệm ε−xấp xỉcủa Bài toán (OPG).
- Khi ε = 0, chuỗi {yωk} có một điểm tụ là nghiệm tối ưutoàn cục của Bài toán (OPG).Chứng minh.
- Ký hiệu f∗là giá trị tối ưu của Bài toán (OPG).
- f∗.Vì y∗∈ GElà nghiệm chấp nhận được của Bài toán (OPG) nên suy ra y∗lànghiệm tối ưu toàn cục của Bài toán (OPG).3.3 Ví dụ minh họaVí dụ 3.1.
- Xét Bài toán (PX) vớih(x.
- (x1+ x2− 0.4)(x1+ 4x2+ 0.2),và XElà tập nghiệm hữu hiệu của Bài toán (CMOP.
- Bây giờ ta giải Bài toán (OPG) để tìmnghiệm ε−xấp xỉ với ε Bước khởi tạo: Giải Bài toán (SP1) và (SP2) được giá trị tối ưu tươngứng là α α Giải Bài toán (P1) và (P2) được các nghiệm tối ưu là(ˆx1, ˆy1.
- ĐặtT0:= {S0,1} và U0:= S0,1.Giải Bài toán P (S0) được giá trị tối ưu β(S0.
- Giải Bài toán (T (yO.
- Đặt S01là 2−đơn hình sinh ra bởi hai điểm yLvà yR= yω0,và S02là 2−đơn hình sinh ra bởi các điểm yL= yω0và yR.Giải Bài toán P (S01) và P (S02) nhận được các giá trị tối ưu tươngứng làβ(S01.
- Đặt S11là 2−đơn hình sinh ra bởi hai điểm yLvà yR= yω1,và S12là 2−đơn hình sinh ra bởi các điểm yL= yω1và yR.Giải Bài toán P (S11) và P (S12) nhận được các giá trị tối ưu tương68 ứng làβ(S11.
- {S2,1, S2,2, S2,3}......Sau 7 bước lặp, vì β7−α ε = 0.0001 nên thuật toán dừng vớinghiệm tối ưu ε−xấp xỉ của Bài toán (OPG) là ybest .
- Đồngthời ta có nghiệm tối ưu của bài toán (PX) tương ứng là xbest và giá trị tối ưu là ϕ(ybest.
- Xét bài toán PXđược cho dưới dạng saumax ϕ(f(x

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt