Một số thuật toán giải bài toán tối ưu trên tập Pareto

- 91.1.2 Phát biểu bài toán.
- 231.2 Bài toán tối ưu trên tập Pareto.
- 242 Bốn trường hợp đặc biệt của bài toán tối ưu trên tậpPareto 272.1 Cơ sở lý thuyết.
- 483 Giải bài toán tối ưu trên tập Pareto bằng phương phápquy hoạch lồi lõm 503.1 Dạng tương đương của bài toán (P.
- 513.2 Dạng rút gọn của bài toán (3.1.
- 573.3 Phương pháp nhánh cận giải bài toán.
- 633.3.2 Thuật toán nhánh cận giải bài toán (3.5.
- Đây là bài toán khó và thuộc lớp bàitoán tối ưu toàn cục, tức là nghiệm tối ưu địa phương chưa chắc đã lànghiệm tối ưu toàn cục.
- Nhiều thuật5 toán theo các tiếp cận khác nhau đã được đề xuất để giải bài toán tối ưutrên tập Pareto (P.
- Trình bàymô hình toán học của bài toán quy hoạch tuyến tính đa mục tiêu(VP), một vài ví dụ thực tế, một số khái niệm và kết quả cơ bảnnhư điểm hữu hiệu, nghiệm hữu hiệu, điều kiện hữu hiệu và cấutrúc tập nghiệm của bài toán.
- Tiếp đó, giới thiệu mô hình toánhọc của bài toán tối ưu trên tập Pareto.• Chương 2 - "Bốn trường hợp đặc biệt của bài toán tối ưutrên tập Pareto".
- Chương này dành để trình bày cơ sở lý thuyếtvà các thuật toán giải bốn trường hợp đặc biệt của bài toán tối ưutrên tập Pareto với hàm mục tiêu tuyến tính do H.
- Sayin [6] đề xuất.• Chương 3 - "Giải bài toán tối ưu trên tập Pareto bằngphương pháp quy hoạch lồi lõm".
- Trướchết, Mục 1.1 sẽ trình bày mô hình toán học của bài toán quy hoạchtuyến tính đa mục tiêu (V P.
- p.Bài toán quy hoạch tuyến tính đa mục tiêu được phát biểu như sauMax Cx, x ∈ X, (V P )trong đó C là ma trận mục tiêu cấp p × n, p ≥ 2 với p hàng là cj∈Rn, j = 1.
- Tập lồi đa diện bịchặn được gọi là đa diện.Một điểm x0∈ X được gọi là một nghiệm hữu hiệu của bài toán (V P )nếu@x ∈ X : Cx ≥ Cx0và Cx 6= Cx0.10 Nghiệm hữu hiệu còn được gọi là nghiệm tối ưu Pareto.
- Ký hiệu XElàtập tất cả các nghiệm hữu hiệu của bài toán (V P ).1.1.3 Điều kiện hữu hiệuKý hiệu Rp+= {λ = (λ1.
- p}.Định lý sau đây cho phép ta tìm được một nghiệm hữu hiệu của bàitoán quy hoạch tuyến tính đa mục tiêu (V P ) thông qua việc giải mộtquy hoạch tuyến tính thông thường.Định lý 1.1 (Định lý vô hướng hóa) Điểm x0∈ X là nghiệm hữu hiệucủa bài toán (V P ) khi và chỉ khi tồn tại một véc tơ λ ∈ intRp+(tức làλ  0) sao cho x0là nghiệm tối ưu của bài toán quy hoạch tuyến tínhvô hướng saumax{hλ, Cxi, x ∈ X}.Cho A ⊂ Rn.
- {v ∈ Rn|hv, x − x0i ≤ 0, ∀x ∈ M}.Sau đây là điều kiện để một điểm x0∈ X là nghiệm hữu hiệu của bàitoán quy hoạch tuyến tính đa mục tiêu (V P ) được phát biểu theo ngônngữ nón pháp tuyến.Mệnh đề 1.1 Một điểm x0∈ X là nghiệm hữu hiệu của bài toán (V P )khi và chỉ khiNX(x0.
- Theo Định lý 1.1, x0là nghiệmhữu hiệu của bài toán (VP).
- m}|hai, x0i = bi}.Trong thực tế tính toán, người ta sử dụng dạng tương đương sau củaMệnh đề 1.1.13 Mệnh đề 1.3 Một điểm x0∈ X là nghiệm hữu hiệu của bài toán quyhoạch tuyến tính đa mục tiêu (V P.
- v3/∈ XE.Điều kiện hữu hiệu sau đây là công cụ cơ bản của thuật toán giải mộttrường hợp đặc biệt của bài toán tối ưu trên tập hữu hiệu.
- Rp.1.1.4 Điều kiện tồn tại nghiệmNhư là một hệ quả trực tiếp của Định lý 1.1, dễ thấy rằng nếu tập chấpnhận được X ⊂ Rncủa bài toán quy hoạch tuyến tính đa mục tiêu (V P )là đa diện, tức là tập lồi đa diện X bị chặn, thì bài toán (V P ) luôn cónghiệm hữu hiệu.
- x ∈ XE}, (P )trong đó f là hàm giá trị thực, đóng vai trò như hàm mục tiêu, và XElà tập nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêu(V P.
- XE.Điểm x0∈ XElà nghiệm tối ưu toàn cục hay nghiệm tối ưu của bài toán(P ) nếu f(x0.
- f(x) với mọi x ∈ XE.Bài toán (P ) được Philip đề xuất lần đầu tiên vào năm 1972.
- Sau đâylà tính chất nghiệm tối ưu của bài toán (P ) trong trường hợp hàm mụctiêu f(x) là hàm lõm.Định lý 1.4 Nếu f(x) là hàm lõm xác định trên Rnthì bài toán (P )đạt nghiệm tối ưu tại ít nhất một đỉnh hữu hiệu x0của bài toán (V P ),tức x0∈ XE∩ Xex.Chứng minh.
- Do tập chấp nhận được của bài toán (P ) là tập nghiệmhữu hiệu XEcủa bài toán quy hoạch tuyến tính đa mục tiêu (V P.
- Vậy bài toán (P ) sẽ đạt nghiệm tối ưu tại ít nhất một đỉnh củamột diện nào đó thuộc XE.
- Kết luận: Chương này đã giới thiệu các khái niệm và kết quả cơ bảnliên quan đến bài toán quy hoạch tuyến tính đa mục tiêu (V P ) và bàitoán tối ưu trên tập Pareto (P.
- Thuật toán giải bài toán (P )trong trường hợp hàm mục tiêu f(x) là hàm lõm do GS.
- Lê Dũng Mưuđề xuất [12] được giới thiệu ở Chương 3.26 Chương 2Bốn trường hợp đặc biệtcủa bài toán tối ưu trêntập ParetoXét bài toán tối ưu trên tập Paretomax{f(x.
- hd, xi, d ∈ Rn\ {0} và tập ràng buộc XElà tập nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêuMax Cx, x ∈ X, (V P )trong đó C là ma trận mục tiêu cấp p × n, p ≥ 2 với p hàng là cj∈Rn, j = 1.
- Vậy bài toán (PT)luôn có nghiệm tối ưu.
- Kí hiệu v là giá trị tối ưu của bài toán này.27 Mục đích của chương này là trình bày thuật toán do H.
- Cụ thể:• Trường hợp 1: Tập nghiệm hữu hiệu của bài toán quy hoạch tuyếntính đa mục tiêu (V P ) bằng tập chấp nhận được của bài toán(V P.
- Trong trường hợp này, bài toán (V P ) đượcgọi là hữu hiệu hoàn toàn.• Trường hợp 2: Hàm mục tiêu của bài toán (PT) có dạngf(x.
- Trường hợp 3: Bài toán quy hoạch tuyến tính đa mục tiêu (V P )có p = 2, tức nó là bài toán quy hoạch tuyến tính hai mục tiêu, vàf(x.
- hd, xi,trong đó d = wTC = w1c1+ w2c2, w1, w2∈ R.• Trường hợp 4: Bài toán quy hoạch tuyến tính nới lỏngmax{hd, xi, x ∈ X} (LPUB)28 có nghiệm tối ưu x∗là một nghiệm hữu hiệu của bài toán quyhoạch tuyến tính đa mục tiêu (V P.
- tức làx∗∈ Argmax(LPUB) và x∗∈ XE.Cơ sở lý thuyết để giải bốn trường hợp đặc biệt này của bài toán (PT)sẽ được trình bày ở Mục 2.1.
- Khi đó,nếu yI∈ Y thì YE= {yI}.Định lý 2.2 Giả thiết rằng nghiệm lý tưởng yIcủa bài toán (V P Y )nằm trong Y và d phụ thuộc tuyến tính vào các hàng của ma trận C.Khi đó, bất kỳ x0∈ XEđều là nghiệm tối ưu của bài toán (PT).33 Chứng minh.
- (2.2)Xét bài toán (P Y ) được phát biểu như saumax{hw, yi, y ∈ YE}.
- (P Y )Theo Mệnh đề 2.1, bài toán (P Y ) có một nghiệm tối ưu nằm trongYex∩ YE.
- Mặt khác, do yI∈ Y nên theo Mệnh đề 2.3, suy ra YE= {yI}.Vậy yI∈ Yexvà yIlà nghiệm tối ưu của bài toán (P Y ).Lấy tùy ý x0∈ XEvà đặt y0= Cx0.
- (2.3)Do hw, yIi là một hằng số, x0∈ XElấy tùy ý và từ (2.3), ta có bất kỳx0∈ XEđều là nghiệm tối ưu của bài toán (PT).
- Y .Hình 2.4Để tìm được nghiệm tối ưu của bài toán (PT), trước tiên, ta cần xác địnhtập nghiệm hữu hiệu XEcủa bài toán quy hoạch tuyến tính đa mục tiêu(V P ).Kiểm tra theo điều kiện nón pháp tuyến thấy rằng bài toán (V P ) có haiđỉnh hữu hiệu x và x .
- Tập nghiệm hữu hiệucủa bài toán (V P ) là cạnh [x0, x1], tức làXE= {x ∈ R3|x1= 1, x2= 1, 0 ≤ x3≤ 1}.
- Nghiệm tối ưu duynhất của bài toán (PT) là (x1)T Dưới đây trình bày kết quả liên quan đến các điều kiện đặc biệt trongTrường hợp 3.Định lý 2.3 Giả thiết rằng p = 2 và d phụ thuộc tuyến tính vào cáchàng của ma trận C.
- Khi đó, tồn tại nghiệm tối ưu x∗của bài toán (PT)thuộc Xexvà x∗cũng là nghiệm tối ưu của ít nhất một trong các quyhoạch tuyến tính (LPUB), (LP1), (LP2), trong đó với mỗi i = 1, 2, bàitoán (LPi) được phát biểu như saumax{hci, xi, x ∈ X}.
- Do Y là compact và miền chấp nhận đượccủa bài toán (P Y )max{hw, yi, y ∈ YE}.
- Vậy trong trường hợp này, y∗là nghiệm cực đại củacả hai bài toán (L1) và (L2.
- Vậy y∗là nghiệm cực đại của bài toán (L1).
- Tương tự như Trường hợp 2, y∗là nghiệm cực đại của bài toán (L2).
- Giả sử y∗không phải là nghiệm cực đại của bài toán (L1) hoặc (L2).
- Do y∗khôngphải là nghiệm cực đại của bài toán (L1) hoặc (L2) nên theolý thuyết quy hoạch tuyến tính, ta cói.
- Tacần chứng minh x∗là nghiệm tối ưu của bài toán (PT) và cũng là nghiệmtối ưu của ít nhất một trong các bài toán (LPUB), (LP1), (LP2).39 Theo Bổ đề 2.2 [i.
- Lấynghiệm tối ưu bất kỳ x0của bài toán (PT) và đặt Cx0= y0.
- Khi đóhd, x0i = wTCx0= hw, y0i≤ hw, y∗i= wTCx∗= hd, x∗i.Do x∗∈ XEvà x0là nghiệm tối ưu của bài toán (PT) nên x∗cũng phảilà nghiệm tối ưu của bài toán (PT).
- Ngoài ra, do y∗là nghiệm cực đạicủa ít nhất một trong ba bài toán (L1), (L2), và (L3) và dT= wTC nênx∗là nghiệm tối ưu của một trong các bài toán (LPUB), (LP1), (LP2).Nhận xét 2.5 Giả sử p = 2 và d phụ thuộc tuyến tính vào các hàng củama trận C.
- Khi đó, theo Định lý 2.3, có thể tìm được ít nhất một phươngán cực biên tối ưu của bài toán (PT) trong số các phương án cực biên tốiưu của các bài toán quy hoạch tuyến tính (LPUB), (LP1), (LP2).
- Tuynhiên, không phải tất cả các phương án cực biên tối ưu của bài toán (PT)đều là nghiệm tối ưu của một trong các bài toán (LPUB), (LP1), (LP2).Ví dụ 2.4 dưới đây sẽ minh họa cho nhận xét này.Ví dụ 2.4 Cho X = {x ∈ R3|0 ≤ xj≤ 1, j p = 2,C .
- 0 ≤ x2, x3≤ 1} (Hình 2.6),và bất kỳ điểm nào thuộc XEđều là nghiệm tối ưu của bài toán (PT).Hình 2.6Dùng thuật toán hình học, ta được nghiệm tối ưu của bài toán quy hoạchtuyến tính (LPUB) là nghiệm tối ưu của bài toán (LP1) là (1,1, 1), nghiệm tối ưu của bài toán (LP2) là (0, 0, 0).Xét (x0)T và (x1)T= (1, 0, 1).
- Khi đó, x0, x1∈ Xexvà x0, x1làcác nghiệm tối ưu của bài toán (PT).
- Xác định giá trị tối ưu θ của bài toán quy hoạch tuyếntính (LPCE).If θ = 0 Then bài toán (V P ) là hữu hiệu hoàn toàn, tức X = XE.Chuyển Bước 2.Else bài toán (V P ) không hữu hiệu hoàn toàn.
- Khi đó, x∗là nghiệmtối ưu của bài toán (PT) và v = UB.
- Kết thúc thuật toán.2.2.2 Trường hợp 2Hàm mục tiêu của bài toán (PT) có dạngf(x.
- (LPD)Nếu giá trị tối ưu γ của bài toán này bằng 0 thì d phụ thuộc tuyếntính vào các hàng của ma trận C.Ngược lại, bài toán (LPD) có tập chấp nhận được khác rỗng vàkhông bị chặn.
- Xác định giá trị tối ưu γ của bài toán bài toán quy hoạchtuyến tính (LPD).If γ = 0 Then d phụ thuộc tuyến tính vào các hàng của ma trậnC.
- Tìm giá trị tối ưu yIicủa các bài toán quy hoạch tuyếntínhmax{yi|y ∈ Y.
- Xét bài toán quy hoạch tuyến tính (LPI).If bài toán (LPI) có nghiệm tối ưu x0Then x0là nghiệm tối ưucủa bài toán (PT) và v = hd, x0i.
- Xác định giá trị tối ưu γ của bài toán quy hoạch tuyếntính (LPD).If γ = 0 Then d phụ thuộc tuyến tính vào các hàng của ma trậnC.
- t} là tập tất cả các phương án cực biêntối ưu của cả ba bài toán này.Với mỗi j = 1, 2.
- Khi đó, x∗∈ L thỏa mãnhd, x∗i = max{hd, xi|x ∈ L}là nghiệm tối ưu của bài toán (PT) và v = hd, x∗i.46 Nhận xét 2.6 Bước 2 của Thuật toán 2.3 đòi hỏi phải xác định tất cảcác phương án cực biên tối ưu của cả ba bài toán quy hoạch tuyến tính(LP1), (LP2) và (LPUB).Sau đây là các ví dụ số tính bởi chương trình viết bằng ngôn ngữ Dev-C.
- Khởi tạo j = 1.• Bước 2 Xác định giá trị tối ưu vxjcủa bài toán quy hoạch tuyếntính (LPxj).If vxj= 0 Then xjlà nghiệm tối ưu của bài toán (PT) vàv = UB = hd, xji.Kết thúc thuật toán.Else chuyển Bước 3.• Bước 3 Kiểm tra bài toán quy hoạch tuyến tính (LPUB) có tồn tạiphương án cực biên tối ưu xj+1/∈ {x1, x2.
- Kết thúc thuật toán.Kết luận: Trong chương này, ta đã tìm hiểu, phân tích và trình bày chitiết các thủ tục quy hoạch tuyến tính đơn giản để giải bốn trường hợpđặc biệt của bài toán tối ưu trên tập Pareto với hàm mục tiêu tuyếntính.
- X ⊂ Rnlà tập lồi đa diện khác rỗng.Chương này trình bày phương pháp quy hoạch lồi lõm giải bài toán tốiưu trên tập Pareto do GS.
- Lê Dũng Mưu [12] đề xuất.50 Mục 3.1 trình bày bài toán có dạng ràng buộc tuyến tính tương đươngvới bài toán tối ưu trên tập Pareto.
- Khi đóBổ đề 3.2 Nếu f là C-không giảm trên G(X) thì với bất kỳ số N > 0,bài toán (P ) là tương đương với bài toán saumax{f(x.
- Giả sử xNlà nghiệm tối ưu toàn cục của bài toán (3.1).Khi đó, xN∈ XE.Thật vậy, nếu xN/∈ XEthì tồn tại x0∈ X thỏa mãn Cx0≥ CxN, CxN6=Cx0.
- Nr(x0).Điều này mâu thuẫn với xNlà nghiệm tối ưu của bài toán (3.1).
- f(x), ∀x ∈ XE⊂ X,tức là xNlà nghiệm tối ưu toàn cục của bài toán (P ).Ngược lại, nếu x∗là nghiệm tối ưu toàn cục của bài toán (P ) thìf(x.
- Nr(xN).Như vậy, x∗là nghiệm tối ưu toàn cục của bài toán (3.1).
- Hình 3.2 minh họa Λ trong trường hợpp = 2.Hình 3.2Mệnh đề 3.3 [13]Với mỗi M > 0 đủ lớn, x ∈ XEkhi và chỉ khi tồn tạiλ ∈ Λ sao cho x là nghiệm tối ưu của bài toán tuyến tínhmax{λTCx : x ∈ X}.
- Λ × X} (3.2)và x∗∈ XEthì x∗là nghiệm của bài toán (P ).56 Chứng minh.
- (Pr(x))Gọi yxlà nghiệm tối ưu của bài toán (Pr(x.
- Do (λ∗, x∗) là nghiệm tối ưu toàn cục của bài toán (3.2) nênta cóf(x)−Nr(x.
- tức là x∗là nghiệm của bài toán(P.
- Kết luận: Từ kết quả trên cho thấy việc giải bài toán tối ưu trên tậpPareto (P ) có thể đưa về việc giải bài toán ràng buộc tuyến tính dạng(3.1) hoặc (3.2).
- Do tính lồi được bảo toàn qua phép57 biến đổi tuyến tính nên bài toán (3.2) trở thànhmax{f1(x.
- rkXj=1ujcj.Khi đó, bài toán (3.1) trở thànhmax{FN(u, v.
- Do s cũng làmột hàm lõm nên đây là bài toán tối ưu hóa đa cực trị.Chú ý rằng:i.
- (L(u0))Gọi h0là một nghiệm tối ưu của bài toán (L(u0.
- A1u + A2v + b ≤ 0}.Do f là hàm lõm nên nghiệm tối ưu của bài toán (3.5) nói chung làkhông đạt được tại đỉnh của miền chấp nhận được.Giả thiết rằng đã xây dựng được đa diện S0trong không gian biến uthỏa mãnP (X.
- Xét bài toán (3.5) đối với S, tức làβ(S.
- u ∈ S, A1u + A2v + b ≤ 0}.(P (S))Tách các biến u và v của bài toán (P (S)) thu được bài toán nới lỏngα(S.
- β(S).Thực chất, việc giải bài toán R(S) chính là giải quy hoạch lồi ràng buộctuyến tính (cực đại lõm) saumax{f(u, v.
- Cho ε ≥ 0 là sai số cho phép.Điểm chấp nhận được x được gọi là ε - nghiệm tối ưu của bài toán (3.5)nếuf∗− f(x.
- 1),trong đó f∗là giá trị tối ưu của bài toán (3.5).
- Hệ quả 3.2 Nếu ε > 0 thì thuật toán là hữu hạn.Kết luận: Chương này đã trình bày dạng ràng buộc tuyến tính tươngđương của bài toán tối ưu trên tập Pareto (P.
- Các thủ tục quy hoạch tuyến tính đơn giản để giải bốn trường hợpđặc biệt của bài toán tối ưu trên tập Pareto (P ) với hàm mục tiêutuyến tính.• Bài toán có dạng ràng buộc tuyến tính tương đương của bài toántối ưu trên tập Pareto (P

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