- 91.3 Bài toán quy hoạch đa mục tiêu lồi suy rộng. - 563.2 Thuật toán giải bài toán quy hoạch tích lõm mở rộng (GIMP. - 78i 4 Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu 834.1 Thuật toán giải bài toán (QP) với ϕ là hàm tựa lõm. - 854.1.1 Phân hoạch và bài toán con. - 944.2 Thuật toán giải bài toán (DP) với ϕ là hàm đơn điệu tăng. - (xem Bài toán quy hoạch đa mục tiêu được phát biểu dưới dạngMin f (x. - Nhiều thuật toánđã được đề xuất để giải bài toán (P). - Bài toán quy hoạch tích được phátbiểu như sauminp∏j =1fj(x), v.đ.k. - Bài toán (MP) được gọi là bàitoán quy hoạch tích tuyến tính, ký hiệu là (LMP), khi f1. - Bài toán quy hoạch đa mục tiêu lồi suy rộngMin f (x. - Bài toán quy hoạch tích lồi suy rộng tương ứng với bài toán (GMOP)minm∏j =1fj(x), v.đ.k. - Hai bài toán tối ưu trên tập nghiệm hữu hiệu XEcủa bài toán quy hoạch haimục tiêu lồi. - Bài toán này được H.P. - Mục 3.2 dành để trình bày thuật toán giải bài toán (GIMP). - 0.Mặt khác, x = 0 không phải là nghiệm tối ưu của bài toán min{h(x. - Điểm x0∈ X đượcgọi là nghiệm hữu hiệu của bài toán (GMOP) nếu f (x0) là một điểm hữu hiệu củaY , tức f (x0. - WMinY, thì ta gọi x0là nghiệm hữu hiệu yếu của bài toán (GMOP). - pocủa bài toán (P2(vk)) cũng là hàm giảlồi trên X. - Cho wklà một điểm hữu hiệu yếu của Y+và xklà một nghiệm hữuhiệu yếu của bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) thỏa mãnf (xk. - Theo điều kiệnđủ trong Định lý 1.4 cho bài toán ((Pλk. - Xét bài toán (P(v)) và bài toán (P(b)).Với mỗi nghiệm chấp nhận được (x,t) của bài toán (P(b. - Xét bài toán (GMOP) (Ví dụ 5.7 [30. - Xét bài toán (GMOP) (Ví dụ 4.2 [28. - Xét bài toán (GMOP) (Ví dụ 2 [61. - Xét bài toán (GMOP) (Ví dụ 5.10 [30. - Xét bài toán (GMOP), trong đó hàm f (x. - Xét bài toán (GMOP) (xem [41. - Bài toán quy hoạch tích lồi suy rộngminm∏j =1fj(x), v.đ.k. - Mục3.2 được dành để trình bày thuật toán giải bài toán (GIMP). - Thuật toán Solve(GMPY) có thể được xem nhưlà một ứng dụng trực tiếp của thuật toán hướng pháp tuyến Solve(GMOP) giải bàitoán quy hoạch đa mục tiêu lồi suy rộng (GMOP).Hai trường hợp đặc biệt của bài toán quy hoạch tích lồi suy rộng (GMP) là bàitoán quy hoạch tích tuyến tính (LMP) với f1. - và bài toán (CMP), chẳng hạn xem N.V. - y∗, cũng là một nghiệm tối ưu của bài toán (GMP).Theo Bổ đề 3.1, thay vì giải bài toán (GMP) hay (GMPt), ta xét bài toánmin ϕ(y) =p∏j =1yjv.đ.k. - ϕ(vk), (3.3)và ta có vklà nghiệm tối ưu của bài toán (3.3). - Do đó, ¯yklà một nghiệm tối ưu của bài toán (GMPY). - Xét bài toán (GMP) trong đó f (x. - Do đó, có thể áp dụng thuật toán Solve(GMPY) giải bài toán trong ví dụnày. - (3.5)Bài toán (GIMP) là bài toán liên quan gần gũi nhất với bài toán quy hoạch tíchlõm mở rộng (GIMP). - Giả sử y∗là một nghiệm tối ưu toàn cục của bài toán (GIMPY), tứclà ϕ(y. - Nếu y∗là một nghiệm tối ưu toàn cục của bài toán (GIMPY) thìđiểm bất kỳ x∗∈ X thỏa mãn f (x. - Mặt khác, vì y∗là một nghiệm tối ưu toàncục của bài toán (GIMPY) nên ϕ(y. - ϕ( f (x)) với mọi x ∈ X,tức x∗là nghiệm tối ưu của bài toán (GIMPX).Theo Mệnh đề 3.1, việc giải bài toán (GIMPY) có thể đưa về việc giải bài toán saumaxϕ(y) v.đ.k. - (SP(E ))Sau đây, ta sẽ thiết lập thủ tục để tính một cận trên α = α(E ) cho bài toán con(SP(E. - Dễ thấy, bài toán (SP(E. - ϕ(zr+t(z`− zr)).Khi đó, bài toán (SP(E. - trở thành bài toán tối ưu một biến saumaxψ(t) v.đ.k. - MaxY−là một nghiệm chấp nhận được của bài toán (EPY. - (3.9)Giả sử ˆz là một nghiệm tối ưu của bài toán nới lỏng saumaxϕ(z) v.đ.k. - Mọi nghiệm tối ưu toàn cục của bài toán (RP(E. - 0 ≤ t ≤ 1.Khi đó bài toán (RP(E. - trở thành bài toán tối ưu một biến saumaxφ(t) v.đ.k. - ϕ(ˆz) là một cận trên củabài toán (SP(E )).Thủ tục tính cận trên của bài toán con (SP(E. - Nếu bài toán(RP(E. - Giải bài toán (P2sub) để xác định nghiệm tối ưu topt;If topt> 0 Then Đặt ˆz = z∗+topt(zr− z∗);Else Đặt ˆz = z∗+topt(z∗− z`).72 Bước 3.Đặt id = 0. - E ∈ Rk},trong đó α(E ) là cận trên của bài toán (SP(E. - Khi đó, αk= α(Ek) là cận trêncủa bài toán (EPY. - Gọi ˆzklà nghiệm tối ưu của bài toán (SP(E. - Nếu biết z ∈ MaxY−thì ϕ(z) là một cậndưới của bài toán (EPY. - (Phân nhánh)(2.1) Giải bài toán (Pro(z. - (Cập nhật và Loại bỏ)(3.1) Với mỗi i ∈ {1,2}, giải bài toán ( RP(E. - ϕ(ˆzki) (cận trên của bài toán (SP(E. - Đặt αk:= α(Ek)Giải bài toán (Pro(z. - limk→∞α(Ek) là mộtcận trên của bài toán (EPY−) hay z∗là một nghiệm tối ưu của bài toán (EPY. - Xét bài toán (GIMP) như sau:max (x1− x2+ 4. - Tập tất cả các nghiệm hữu hiệu của bài toán này làXE= {x0∈ X |6 ∃x ∈ X sao cho f (x0. - ¯yđều là một nghiệm hữu hiệu của bài toán (CBOP), tức ¯x ∈ XE. - Y , trong đó yIilà giá trị tối ưu của bài toán quy83 hoạch lồi min{ fi(x. - Rn+plà một nghiệm tối ưu của bài toán (S Pi) đượccho bởimin yk(SPi)v.đ.k. - Do (4.1) và định nghĩa, việcgiải bài toán (QP) và bài toán (DP) có thể đưa về việc giải hai bài toán trên khônggian ảnh tương ứng làminϕ(y) v.đ.k. - (DPY+)Dễ thấy nếu y∗là nghiệm tối ưu của bài toán (QPY+) (t.ư., bài toán (DPY+) thìmỗi điểm x∗∈ X thỏa mãn y∗≥ f (x∗) là một nghiệm tối ưu của bài toán (QP)(t.ư., bài toán (DP. - Giải bài toán quy hoạchlồi với hàm mục tiêu tuyến tínhminhvnew,yi v.đ.k. - Xét bài toán con (SP(yL,yR)) của bài toán (QPY+)min ϕ(y) v.đ.k. - Vì vậy,giá trị tối ưu của bài toán nới lỏngmin ϕ(y) v.đ.k. - y ∈ S(yL,yR) (RP(yL,yR))là một cận dưới của bài toán con (S P(yL,yR. - Nếu y∗∈ {yL,yR} thì y∗cũng là một nghiệm tối ưu của bài toán(SP(yL,yR)) và giá trị tối ưu của (SP(yL,yR)) là ϕ(y. - ϕ(y∗) là một cận dưới của giá trị tối ưu của bài toán con(SP(yL,yR. - Dạng tường minh của bài toán(BP0) làminhvnew,yiv.đ.k. - Điểm y∗∈ MinY+được gọi là một nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+) nếu có một cận dướiβ∗của bài toán (QPY+) thỏa mãn |ϕ(y. - và một nghiệmtối ưu xbestkcủa bài toán (QP). - y∗là nghiệm tối ưu của bài toán (CBMP). - Nói cách khác, bài toán (CBMP) có thể được giải thông qua việc giải bàitoán (QP) với ϕ(y. - Xét bài toán (QP) được cho bởi Benson H.P. - Nghiệm tối ưuε−xấp xỉ của bài toán (QPY+) là ybest và nghiệm tối ưu xấp xỉtương ứng của bài toán (QP) là xbest Tvà giá trị tốiưu ε−xấp xỉ của bài toán (QP) là h(xbest. - Xét bài toán (QP) với f1(x. - Nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+)là ybest và nghiệm tối ưu xấp xỉ của bài toán (QP) là xbest T. - Giá trị tối ưu ε-xấp xỉ của bài toán (QP) là h(xbest. - Ta thu được nghiệmtối ưu ε-xấp xỉ ybest của bài toán (QPY. - Trong [87], thuật toán giải bài toán này dừngsau 6 bước lặp với nghiệm tối ưu xấp xỉ x T.Ví dụ 4.4. - Xét bài toán (QP) trong đó ϕ(y. - Khi đó, ta thu đượcybestlà nghiệm tối ưu ε−xấp xỉ của bài toán (DPY+) và xbestlà nghiệm xấpxỉ của bài toán (DP). - R2+nên nghiệmtối ưu của bài toán (DP(S(yL,yR. - Giải bài toán (SPi) với i = 1,2 để xác định hai điểm hữuhiệu đầu tiên ˆy1, ˆy2∈ MinY+và hai nghiệm hữu hiệu ˆx1, ˆx2tương ứng vớiˆy1, ˆy If ˆy1≡ ˆy2Then Thuật toán dừng, ˆy1là nghiệm tối ưu của bài toán (DPY+) vàˆx1là nghiệm tối ưu của bài toán (DP);(0.3) If ϕ(ˆy1. - S0∈ Tk};(1.2) Đặt αk:= α(Sk,¯η) (cận trên tốt nhất hiện tại);(1.3) If αk−βk≤ ε(|βk|+1) Then Thuật toán dừng (ybestlà nghiệm tối ưu ε−xấpxỉ của bài toán (DPY. - xbestlà nghiệm tối ưu xấp xỉ của bài toán (DP))Else Đặt Sk= Sk,¯η.Bước 2. - Ký hiệu f∗là giá trị tối ưu của bài toán (DPY. - Xét bài toán (DP) với h(x. - Giải bài toán (T (yO. - Thuật toán dừng sau 7 bước lặp với nghiệm tối ưu ε−xấp xỉ của bài toán(DPY+) là ybest . - Xét bài toán (DP) được cho dưới dạng saumax ϕ( f (x. - x ∈ X},i = 1,2 và XElà tập nghiệm hữu hiệu của bài toán(CBOP), trong đófi(x. - Thuật toán nhánh cận kết hợp xấp xỉ ngoài giải bài toán cực đại hàmh(x
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt