Phương pháp giải một số lớp bài toán tối ưu đa mục tiêu và ứng dụng

- Giới thiệu bài toán tối ưu đa mục tiêuTrong những năm 50 của thế kỷ 20, Quy hoạch đa mục tiêu, hay còn được gọi là Tốiưu đa mục tiêu hoặc Tối ưu véc tơ, đã trở thành một chuyên ngành toán học, thu hútsự quan tâm của nhiều tác giả và được phát triển mạnh mẽ suốt gần 70 năm qua.
- Bài toán quyhoạch đa mục tiêu được phát biểu dưới dạngMin f (x.
- Hausdorff đề xuất.Bài toán (MOP) được gọi là bài toán quy hoạch đa mục tiêu lồi, ký hiệu là(CMOP), nếu X là tập lồi và f1.
- Như đã biết, (LMOP) làtrường hợp đơn giản nhất của bài toán (MOP) nói chung và (CMOP) nói riêng.Theo tiếp cận trên không gian quyết định (decision space), việc giải bài toán(MOP) được xem như việc xác định toàn bộ hay một phần của tập nghiệm hữu hiệuXEhoặc tập nghiệm hữu hiệu yếu XW E.
- Theo định nghĩa, YEvà YW Etương ứng là tập điểm hữu hiệu và tậpđiểm hữu hiệu yếu của tập ảnh Y = f (X) của tập chấp nhận được X qua ánh xạ f .Lý do chính cho hướng tiếp cận này là: i) Các bài toán tối ưu đa mục tiêu nảy sinhtrong thực tế thường có số hàm mục tiêu p nhỏ hơn rất nhiều so với số biến n, hay thứnguyên của không gian ảnh Rpnhỏ hơn rất nhiều so với thứ nguyên của không gian1 quyết định Rn.
- (1998)).Trong tối ưu đa mục tiêu, việc nghiên cứu để giải bài toán quy hoạch đa mục tiêutuyến tính (LMOP) có thể xem gần như hoàn chỉnh.
- Đã có nhiều cuốn sách chuyênkhảo về bài toán (LMOP) (xem Luc D.T.
- Rấtnhiều thuật toán đã được đề xuất theo cả hai hướng tiếp cận trên không gian quyếtđịnh và không gian ảnh để giải bài toán này bằng nhiều phương pháp khác nhau nhưphương pháp đơn hình đa mục tiêu, phương pháp tham số, phương pháp vô hướnghóa, phương pháp nón pháp tuyến, phương pháp xấp xỉ ngoài hoặc kết hợp của cácphương pháp đó, chẳng hạn xem Zeleny M.
- (2012),...Với bài toán quy hoạch đa mục tiêu lồi và không lồi, đã có một số thuật toán đượcđề xuất.
- để sinh một phầntập nghiệm hữu hiệu hay hữu hiệu yếu của bài toán.
- (1999) đã phânloại chi tiết và so sánh các phương pháp hiện có để giải các bài toán quy hoạch đamục tiêu phi tuyến.
- Các phương pháp để sinh ra tập xấp xỉ của tập nghiệm hữu hiệuvà tập ảnh hữu hiệu được thống kê trong Ruzika S., Wiecek M.M.
- (2005).Hai bài toán tối ưu toàn cục quan trọng có liên quan chặt chẽ đến bài toán quyhoạch đa mục tiêu là bài toán tối ưu một hàm thực trên tập nghiệm hữu hiệu của bàitoán quy hoạch đa mục tiêu (gọi tắt là Bài toán tối ưu trên tập nghiệm hữu hiệu) vàbài toán quy hoạch tích cũng như các dạng mở rộng của nó.Bài toán tối ưu trên tập nghiệm hữu hiệu có mô hình toán học như saumin h(x) v.đ.k.
- Việc giải bài toán này có ý nghĩa đặc biệt vì nó giúp1Từ sau đây đến hết luận án, cụm từ "tương ứng" sẽ được viết tắt là "t.ư.".2 ta chọn được nghiệm hữu hiệu tốt nhất theo một tiêu chuẩn nào đó mà không nhấtthiết phải xác định được toàn bộ tập nghiệm hữu hiệu.
- Bài toán (P)do Philip J.
- Nhiều thuật toán đã được đềxuất để giải bài toán (P).
- Đây cũng là lớp các bài toán tối ưu toàn cục khó và thú vị nên đã thu hút sựquan tâm đặc biệt của nhiều tác giả.
- Bài toán quy hoạch tích được phát biểu như sauminp∏j=1fj(x), v.đ.k.
- Tương tựnhư cách phân loại các bài toán quy hoạch đa mục tiêu, nếu X là tập lồi đóng và cáchàm f1.
- Bài toán (MP) được gọi là bài toán quy hoạch tích tuyến tính, kýhiệu là (LMP), khi f1.
- Matsui T.(1996) đã chỉ ra rằng, ngay cả trường hợp đơn giản nhất của bài toán (MP), tức là bàitoán (LMP) với p = 2 và X là đa diện khác rỗng, cũng thuộc lớp bài toán NP−khó.Hiện nay đã có nhiều thuật toán được đề xuất để giải bài toán quy hoạch tích tuyếntính (LMP) (xem Konno H., Kuno T.
- Theo hiểu biết của tác giả, mặc dù có nhiều ứng dụng thựctiễn nhưng có rất ít công trình nghiên cứu bài toán quy hoạch tích mở rộng.3 2.
- Mục đích nghiên cứu và ý nghĩa của đề tàiNhư đã trình bày, mặc dù bài toán quy hoạch đa mục tiêu lồi và các vấn đề liên quanđã được nghiên cứu tương đối hoàn chỉnh nhưng cho đến nay vẫn còn rất ít thuật toángiải bài toán tối ưu đa mục tiêu lồi suy rộng (xem Wiecek M.M., Ehrgott M., EngauA.
- Hơn nữa, do nhu cầu ứng dụng, việc nghiên cứu xây dựng các thuật toánhiệu quả để giải bài toán quy hoạch đa mục tiêu lồi suy rộng, bài toán quy hoạch tíchmở rộng, cũng như bài toán tối ưu trên tập nghiệm hữu hiệu là các vấn đề thời sự vàluôn cần đầu tư nhiều công sức.
- Luận án này nghiên cứu và đề xuất các thuật toánmới để giải các bài toán sau:1.
- 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.
- x ∈ X, (GMP)trong đó các hàm số fj: Rn→ R, j = 1,...,m và tập chấp nhận được X được giả thiếtnhư trong phát biểu của bài toán (GMOP).3.
- Bài toán quy hoạch tích lõm mở rộngmax Φ(x.
- Bài toán quy hoạch tích mở rộng liên quan gần gũi nhấtvới bài toán (GIMP) đã được nghiên cứu trong Jaumard B., Meyer C., Tuy H.
- (1997).Trong trường hợp đặc biệt, khi k = 2, đã có một số thuật toán hữu hiệu được đề xuấtđể giải bài toán (GIMP) (xem Ashtiani A.M.M., Ferreira P.A.V.
- Theo hiểu biết của chúng tôi, cho đến nay, hầu như chưa có thuật toán nàođược đề xuất để giải bài toán (GIMP) trong trường hợp tổng quát.4.
- 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 hai mụctiêu lồi.
- Dạng hàm mục tiêu h(x) =ϕ( f (x)) với hàm số thực ϕ : Y → R xuất hiện nhiều trong các bài toán nảy sinh từ4 thực tế và cũng đã được nhiều tác giả quan tâm nghiên cứu, chẳng hạn Kim N.T.B.,Muu L.D.
- và danh sách tài liệu tham khảo kèm theo.Ngoài các bài toán trên, chúng tôi đã nghiên cứu và đề xuất thuật toán giải bài toánmax g(x.
- “Bài toán quy hoạch đa mục tiêu lồi suy rộng” dành để giới thiệu môhình toán học của bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) cùng mộtsố khái niệm và kết quả cơ bản liên quan.
- “Thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mục tiêu lồisuy rộng” đề xuất một thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mụctiêu lồi suy rộng (GMOP), trong đó sử dụng kỹ thuật xấp xỉ ngoài trên không gianảnh để xác định tập nghiệm hữu hiệu yếu θ−xấp xỉ của bài toán (GMOP).
- Đây là một đóng góp quan trọng về mặt lý thuyếtcho các phương pháp xấp xỉ ngoài giải bài toán quy hoạch đa mục tiêu vì chưa cócông trình nào trước đây chứng minh chặt chẽ được tính chất này.
- “Thuật toán giải một số bài toán quy hoạch tích mở rộng” đưa ra cácthuật toán theo tiếp cận trên không gian ảnh để giải hai bài toán quy hoạch tích: Bàitoán quy hoạch tích lồi suy rộng (GMP) và Bài toán quy hoạch tích lõm mở rộng(GIMP).
- Thuật toán giải bài toán (GMP) được thiết lập dựa trên mối quan hệ củabài toán (GMP) và bài toán (GMOP) tương ứng với nó, và cũng được xem như làmột ứng dụng của thuật toán giải bài toán (GMOP) đã thiết lập ở Chương 2.
- Bằngcác biến đổi thích hợp, việc giải bài toán (GIMP) được đưa về việc giải bài toán cựcđại một hàm đơn điệu tăng trên tập các điểm hữu hiệu của một tập lồi đóng trong R2.Các tính toán thử nghiệm chứng tỏ thuật toán đề xuất là hiệu quả.Chương 4.
- “Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu” đề xuất cácthuật toán trên không gian ảnh để giải hai bài toán (QP) và (DP).
- Bằng cách biến đổicác bài toán gốc về bài toán tương đương trên không gian ảnh và tận dụng cấu trúcđặc biệt của tập ảnh hữu hiệu và tính chất đặc thù của các hàm mục tiêu, chương nàyđề xuất một thuật toán nhánh cận giải bài toán (QP) và một thuật toán nhánh cận kếthợp với lược đồ xấp xỉ ngoài giải bài toán (DP).Việc đánh số của các chương, mục, định lý.
- trong bản tóm tắt này được giữ nguyênnhư ở trong luận án.5 Chương 1BÀI TOÁN QUY HOẠCH ĐA MỤC TIÊU LỒI SUY RỘNGTất cả các bài toán được nghiên cứu trong luận án này đều liên quan gần gũi đếnbài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) và trường hợp riêng của nó làbài toán quy hoạch đa mục tiêu lồi (CMOP).
- Chương này giới thiệu mô hình toánhọc của bài toán (GMOP) cùng một số khái niệm và kết quả cơ bản liên quan.1.1 Hàm lồi suy rộngCho tập lồi khác rỗng S ⊆ Rn.
- Định lý KKT sau đây đóng vai trò quan trọng trongviệc thiết lập cơ sở lý thuyết của thuật toán giải bài toán quy hoạch đa mục tiêu lồisuy rộng được trình bày trong Chương 2.Định lý 1.4.
- Ký hiệu MinQ và MaxQ lầnlượt là tập tất cả các điểm hữu hiệu theo nghĩa cực tiểu và cực đại của Q,MinQ.
- Q = {q∗}}.Ký hiệu WMinQ và WMaxQ lần lượt là tập tất cả các điểm hữu hiệu yếu theonghĩa cực tiểu và cực đại của Q,WMinQ.
- Một tập compact khácrỗng thì luôn có điểm hữu hiệu và điểm hữu hiệu yếu (xem Luc D.T.
- {q∗∈ Q |6 ∃q ∈ Q : q∗− θ > q}.Điểm q∗∈ Rpđược gọi là điểm hữu hiệu yếu θ−xấp xỉ ngoài (theo nghĩa cực tiểu)của tập Q ⊆ Rpnếu q∗+ θ ∈ WMin(Q,θ).Cho một tập đóng khác rỗng Q ⊂ Rpvà một điểm q∗∈ Q.
- Khi đó, tập điểm hữu hiệu MinQ là liên thông và tập điểm hữu hiệuyếu WMinQ là tập liên thông đường.1.3 Bài toán quy hoạch đa mục tiêu lồi suy rộngChương 2 của luận án xét bài toán quy hoạch đa mục tiêu lồi suy rộngMin f (x.
- Dễ thấy, bài toán quy hoạch đa mục tiêu lồi (CMOP) khif và g là các hàm véc tơ lồi và bài toán quy hoạch đa mục tiêu tuyến tính (LMOP)khi f và g là hàm véc tơ tuyến tính là hai trường hợp đặc biệt của bài toán (GMOP).8 Ký hiệu Y = f (X.
- Tập các nghiệm hữu hiệu và tập các nghiệm hữu hiệu yếu của bàitoán (GMOP) lần lượt được ký hiệu là XE,XW E,XE= {x0∈ X | f (x0.
- Tập YEvà YW Elần lượt được gọi là tập ảnh hữu hiệu và tập ảnh hữu hiệu yếu của (GMOP).Kết quả sau là hệ quả trực tiếp của Định lý 1.7.Mệnh đề 1.9.
- Với giả thiết Y+= Y + Rplà tập lồi, ta có YElà liên thông và YW Elàliên thông đường.Ký hiệu XE,θvà XW E,θlần lượt là tập các nghiệm hữu hiệu θ −xấp xỉ và tập cácnghiệm hữu hiệu yếu θ −xấp xỉ của bài toán (GMOP) và được định nghĩa làXE,θ:= {x0∈ X | f (x0.
- WMin(Y , θ )}.Chương 2THUẬT TOÁN HƯỚNG PHÁP TUYẾN GIẢI BÀI TOÁNQUY HOẠCH ĐA MỤC TIÊU LỒI SUY RỘNGXét bài toán quy hoạch đa mục tiêu lồi suy rộngMin f (x) v.đ.k.
- Đặc biệt, nếu bài toán (GMOP) làmột bài toán quy hoạch đa mục tiêu tuyến tính thì sau hữu hạn bước lặp, với ε = 0,ta nhận được tập YW Evà tập XW E.2.1 Xác định điểm ảnh hữu hiệu yếu và hướng pháp tuyếnXác định hai điểm lý tưởng ymvà yMcủa tập Y .
- 0.Bài toán (P(vk)) có nghiệm tối ưu duy nhất (xk,tk).
- Bài toán (P(vk)) tương đương với bài toánmin max(fj(x.
- (P2(vk))Đây là bài toán cực tiểu một hàm giả lồi trên tập lồi.
- Vì vậy, bài toán (P2(vk)) có thểgiải được bằng các thuật toán của quy hoạch lồi.Định lý 2.1.
- Cho wk∈ WMinY+và xklà nghiệm hữu hiệu yếu của bài toán (GMOP)thỏa mãn f (xk.
- EO là tập các điểm hữu hiệu yếuθ−xấp xỉ ngoài của tập Y.
- EY là tập các điểm hữu hiệu yếu của tập ảnh Y .Thuật toán Solve(GMOP)Bước 0.
- Bk.Định lý 2.3 chỉ ra rằng Yinvà Youttương ứng là các tập xấp xỉ trong và tập xấp xỉngoài của Y.Hơn nữa, tất cả các điểm hữu hiệu yếu của Yinđều là điểm hữu hiệu yếu θ −xấp xỉcủa Y, hay WMinYin⊆ WMin(Y,θ), và tất cả các điểm hữu hiệu yếu của Youtđềulà điểm hữu hiệu yếu θ−xấp xỉ ngoài của Y, hay WMinYout+ θ ⊆ WMin(Y,θ).Dựa trên tập Yout, ta thiết lập được tập xấp xỉ ngoài EX của tập nghiệm hữu hiệuyếu XW Ecủa bài toán (GMOP).
- ¯y}.Hơn nữa, EX bao gồm các nghiệm hữu hiệu yếu θ- xấp xỉ của bài toán (GMOP) vàcũng chứa toàn bộ tập nghiệm hữu hiệu yếu XW E(Hệ quả 2.1).2.3 Sự hội tụ của thuật toánKết quả sau chỉ ra rằng các đa diện Bk,k = 0, 1.
- Hơn nữa, nếu bài toán (GMOP) là quy hoạch đa11 mục tiêu tuyến tính thì thuật toán dừng sau một số hữu hạn bước ngay cả khi ε = 0,và khi đó XW E≡ EX ≡ XW E,θ.2.4 Tính toán thử nghiệmViệc tính toán thử nghiệm thuật toán Solve(GMOP) được thực hiện trên máylaptop HP Pavilion 1.8Ghz, RAM 2GB sử dụng mã nguồn được viết trên ngôn ngữMatlab 2009a.
- Để tiện kiểm định, kết quả tính toán giải bài toán (GMOP)bằng thuật toán Solve(GMOP) được so sánh với một số kết quả đã công bố.
- Kết quả tínhtoán của Ví dụ 2.7 và 2.8 với dữ liệu đầu vào được sinh ngẫu nhiên đã chứng tỏ tínhhiệu quả của thuật toán.Chương 3THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN QUY HOẠCH TÍCH MỞ RỘNG3.1 Thuật toán giải bài toán quy hoạch tích lồi suy rộngXét bài toán quy hoạch tích lồi suy rộngminm∏j=1fj(x), v.đ.k.
- 0.Như thường lệ, bài toán (GMP) được xét với giả thiết fj(x.
- Do đó, tập ảnh Y = f (X) của bài toán (GMP) thỏa mãn Y+⊂ intRp+.Bài toán quy hoạch tích trên không gian ảnh tương ứng với bài toán (GMP) làmin ϕ(y) =p∏j=1yjv.đ.k.
- Giá trị tối ưu của (GMP) và bài toán (3.2) là như nhau.
- y∗thì y∗∈ WMinY và x∗∈ Argmin(GMP).Theo Bổ đề 3.1, thay vì giải bài toán (GMP) hay bài toán (3.2), ta xét bài toánmin ϕ(y) =p∏j=1yjv.đ.k.
- Đa diện Bk+1được xác định như mô tả ở Bước 2 và Bước 3 của thuật toán Solve(GMOP).Quá trình xây dựng dãy đa diện {Bk} sẽ đồng thời sinh ra hai dãy cận trên và cậndưới của bài toán (GMPY) và cho phép ta nhận được nghiệm và giá trị tối ưu xấp xỉcủa bài toán (GMPY).
- Điểm ¯y được gọi là mộtnghiệm ε-xấp xỉ của bài toán (GMPY) nếu tồn tại một cận dưới¯β của bài toán nàysao cho¯α −¯β ≤ ε.
- ¯y, trong đó ¯y làmột nghiệm ε-xấp xỉ của bài toán (GMPY), là một nghiệm ε-xấp xỉ của (GMP).Tại mỗi bước lặp k điển hình, cận dưới tốt nhất hiện tại của bài toán (GMPY) làβk= min{ϕ(y.
- Giải bài toán (P(vk)) và nhận được một nghiệm tối ưu (xk,tk);Đặt yk= f (xk), wk= yO+tk(vk− yO) và EY = E Y ∪ {yk};Xác định ¯yk∈ EY thỏa mãn ϕ(¯yk.
- Nếu ε > 0 thì thuật toán dừng sau hữu hạn bước lặp và sinh ra mộtnghiệm ε-xấp xỉ của bài toán (GMPY).
- Nếu ε = 0 thì hoặc là thuật toán dừng sau13 hữu hạn bước và sinh ra một nghiệm chính xác của bài toán (GMPY), hoặc là nó sinhra một dãy { ¯yk} sao cho {ϕ( ¯yk)} hội tụ tới giá trị tối ưu của bài toán (GMPY).Nhận xét 3.2.
- Dãy { ¯yk} mô tả trong Định lý 3.1 không nhất thiết phải hội tụ nhưngdo Y là tập compact nên nó chứa một dãy con hội tụ và mỗi điểm tụ của nó làmột nghiệm tối ưu của bài toán (GMPY).
- ¯yklà một nghiệm tối ưu của bài toán (GMP).Thuật toán được cài đặt bằng ngôn ngữ Matlab và thực hiện trên máy laptop HPPavilion 1.8Ghz, RAM 2GB.
- Kết quả tính toán của Ví dụ 3.1, trong đó hàm f khônglồi và X là đa diện khác rỗng, đã chứng tỏ tính đúng đắn của thuật toán.3.2 Thuật toán giải bài toán quy hoạch tích lõm mở rộng (GIMP)Xét bài toán quy hoạch tích lõm mở rộngmaxx∈X Φ(x.
- Dễ thấy rằng ϕ làhàm liên tục, đơn điệu tăng trên Y = f (X).Xét bài toán trên không gian ảnh tương ứng với bài toán (GIMPX)maxϕ(y) v.đ.k.
- (GIMPY)Nhắc lại rằng, tập tất cả các điểm hữu hiệu theo nghĩa cực đại của Y được địnhnghĩa bởi MaxY.
- y∗thì x∗∈Argmax(GIM PX).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ánmaxϕ(y) v.đ.k.
- Dễ thấy, véc tơ dstart= (0,1) và dend= (1,0) lần lượt là cácvéc tơ pháp tuyến của siêu phẳng tựa của Y−tại zstartvà zend.3.2.1 Các thao tác cơ bản của lược đồ nhánh cậna) Cận trên của bài toán conXét hai điểm z`,zr∈ MaxY−thỏa mãn zr1> z`1và z`2> zr2, và E ⊆ MaxY−làđường cong duy nhất nối z`với zr.
- Xét bài toán conmaxϕ(z) v.đ.k.
- (SP(E ))Dễ thấy, bài toán (SP(E.
- Giả sử ˆzlà một nghiệm của bài toán nới lỏng saumaxϕ(z) v.đ.k.
- Mọi nghiệm tối ưu của bài toán (RP(E.
- Bài toán (RP(E.
- 0 ≤ t ≤ 1.Gọi toptlà một nghiệm của bài toán (P2sub).
- ϕ(ˆz) là mộtcận trên của bài toán (EPY−).Thủ tục tính cận trên của bài toán con (SP(E.
- Giải bài toán (P2sub) để xác định nghiệm tối ưu topt;If topt> 0 Then ˆz = z∗+topt(zr− z.
- Giải bài toán (P1sub) để xác định nghiệm tối ưu topt;Đặt ˆz = zr+topt(z`− zr).b) Phân hoạch và chia nhánhCho Q ⊂ R2.
- E ∈ Rk}, trong đó α(E ) là cận trên của bài toán(SP(E.
- Khi đó, αk= α(Ek) là cận trên của bài toán (EPY.
- Gọi ˆzklà nghiệmtối ưu của bài toán (SP(E.
- Theo cách xây dựng, bài toán (SP(E.
- vớiE = Ekthuộc vào Trường hợp 3, tức là id = 1 và ˆzk∈ (zI− R2+) \Y−.Theo Nhận xét 3.3, nghiệm tối ưu ˆpkcủa bài toán (Pro(z

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