VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————o0o——————– PHẠM THỊ LAN ĐỐI CỰC CỦA TẬP LỒI ĐA DIỆN VÀ ÁP DỤNG VÀO BÀI TOÁN TỐI ƯU VECTO TUYẾN TÍNH HAI CẤP LUẬN VĂN THẠC SĨ TOÁN HỌC Ngành: Toán ứng dụng Mã số: 60 46 01 12 Người hướng dẫn: GS TSKH Lê Dũng Mưu Hà Nội - 2015 Mục lục Mở đầu 1 Một số kiến thức sở 1.1 Tập lồi đa diện 1.2 Hàm affine 11 Tập hữu hiệu Pareto toán tối ưu vector tuyến tính 15 2.1 Bài toán tối ưu vector tuyến tính 15 2.1.1 Nón pháp tuyến tập lồi đa diện 16 2.1.2 Nón chuẩn tắc âm tập lồi đa diện 22 2.1.3 Diện nghiệm hữu hiệu 25 Thuật toán nón pháp tuyến xác định tập hữu hiệu 31 2.2 Phương pháp tập đối cực giải toán tối ưu tập Pareto 3.1 Các phương pháp giải 38 40 3.1.1 Mô tả dạng cực đại hàm lồi 40 3.1.2 Mô tả dạng qui hoạch lồi-lõm 44 3.2 Thuật toán xấp xỉ giải toán tối ưu tập Pareto 47 Kết luận 54 Tài liệu tham khảo 55 i Mở đầu Trong thực tế, người thường xuyên phải giải toán tối ưu đồng thời nhiều mục tiêu lúc điều kiện, hoàn cảnh Hoạt động kinh tế-xã hội đặt toán tối ưu Thí dụ tìm phương án sản xuất cho lợi nhuận cao nhất, chất lượng tốt nhất, giá thành rẻ ảnh hưởng đến môi trường sống Rõ ràng, dù muốn hay giải toán với nhiều mục tiêu lúc Tuy nhiên, phương án tốt tất mục tiêu có Trái lại thường gặp trường hợp phương án tốt mục tiêu lại không tốt với mục tiêu khác Điều dẫn tới toán tối ưu đa mục tiêu Khi hàm mục tiêu tuyến tính tập chấp nhận tập lồi đa diện ta nhận lớp toán tối ưu vector tuyến tính Đây toán áp dụng nhiều tối ưu đa mục tiêu Do không gian giá trị toán không thứ tự toàn phần (nôm na "được khác") nên khái niệm nghiệm tối ưu thông thường hàm biến không thích hợp Thay vào khái niệm nghiệm hữu hiệu hay điểm Pareto Cho đến nay, có nhiều tác giả đưa thuật toán để xác định tập nghiệm hữu hiệu toán này, chẳng hạn N.T.B Kim D.T Luc [17], Philip [18], An, Muu Tao [2], Thach, Konno Yokota [20] Tuy nhiên, khối MỞ ĐẦU lượng tính toán thuật toán để xác định toàn tập nghiệm hữu hiệu toán tối ưu vector tuyến tính tăng nhanh kích thước toán tăng Hơn thực tế, việc lựa chọn nghiệm tối ưu Pareto không đủ Do đó, người định thường dựa vào tiêu chuẩn để chọn lựa phương án tốt tập Pareto Tiêu chuẩn thêm vào coi thước đo để so sánh đánh giá mức độ hữu hiệu điểm Pareto Mục đích luận văn trình bày tập hữu hiệu Pareto toán tối ưu vector tuyến tính thuật toán sử dụng tập đối cực để giải toán tối ưu vector tuyến tính tập Pareto Ngoài phần Mở đầu, Phụ lục, phần trích dẫn tài liệu tham khảo, nội dung luận văn trình bày ba chương: Chương 1: Một số kiến thức sở: Chương nhắc lại kiến thức sử dụng chương sau, bao gồm số khái niệm giải tích lồi Chương 2: Tập hữu hiệu Pareto toán tối ưu vector tuyến tính: Chương trình bày số kết tập hữu hiệu toán tối ưu vector tuyến tính, khái niệm nón pháp tuyến, nón chuẩn tắc âm tập lồi đa diện, diện nghiệm hữu hiệu, cấu trúc tập nghiệm, thuật toán nón pháp tuyến xác định tập hữu hiệu Chương 3: Phương pháp tập đối cực giải toán tối ưu tập Pareto: Chương trình bày phương pháp giải toán tối ưu tập Pareto mô tả dạng toán cực đại hàm lồi toán qui hoạch lồi-lõm áp dụng thuật toán sử dụng tập đối cực để giải toán tối ưu tập Pareto MỞ ĐẦU Luận văn hoàn thành Viện Toán học, Viện Hàn lâm Khoa học Công nghệ Việt Nam, hướng dẫn tận tâm chu đáo GS TSKH Lê Dũng Mưu Tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy, thầy định hướng đề tài, truyền thụ kiến thức giúp hoàn thiện luận văn Tôi xin chân thành cảm ơn Viện Toán học, Trung Tâm Đào tạo sau Đại học tạo điều kiện thuận lợi cho suốt thời gian học làm luận văn cao học Tôi xin bày tỏ lòng cảm ơn chân thành tới thầy cô giáo Viện Toán học, suốt thời gian học tập nghiên cứu, tận tình giảng dạy, truyền đạt nhiều kiến thức quan trọng, giúp đem lại tảng cần có cho bước tương lai tốt Mặc dù cố gắng luận văn chắn nhiều sai sót Kính mong nhận cảm thông, góp ý thầy cô bạn đọc để luận văn hoàn thiện Hà Nội, tháng 08 năm 2015 Tác giả Phạm Thị Lan Chương Một số kiến thức sở Chương nhắc lại số kiến thức sở cần dùng chương sau Mục 1.1 nhắc lại định nghĩa tính chất tập lồi đa diện, đối cực tập lồi đa diện Mục 1.2 trình bày số kết hàm lồi hàm affine, cực đại hàm lồi Các kết giải tích lồi tổng hợp Hiền, Mưu, Điển [1] Một số kết không ghi trích dẫn mục tìm thấy Rockafellar [19] 1.1 Tập lồi đa diện Định nghĩa 1.1 Ký hiệu: R = R ∪ {−∞, +∞} Cho C ⊆ Rn tập lồi f : C → R Miền hữu dụng f đĩnh nghĩa sau: domf := {x ∈ C|f (x) < +∞} Một hàm f gọi thường domf = ∅ f (x) > −∞ với x Tập đồ thị f định nghĩa sau: epif := {(x, µ) ∈ C × R| µ ≥ f (x)} Chương Một số kiến thức sở Định nghĩa 1.2 Một tập C ⊆ Rn gọi tập lồi C chứa đoạn thẳng qua hai điểm Tức C lồi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C Bao lồi C ⊂ Rn giao tất tập lồi chứa C Ký hiệu coC convC Định nghĩa 1.3 Một tập C gọi tập affine chứa đường thẳng qua hai điểm nó, tức ∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C Bao affine C ⊂ Rn tập affine nhỏ chứa C ký hiệu af f (C) Vậy tập affine trường hợp riêng tập lồi Định nghĩa 1.4 Điểm tương đối C ký hiệu riC định nghĩa sau: riC := {a ∈ C| ∃B : (a + B) ∩ af f C ⊂ C}, B lân cận mở gốc Định nghĩa 1.5 Một tập gọi tập lồi đa diện, giao số hữu hạn nửa không gian đóng Như vậy, tập lồi đa diện tập hợp nghiệm hệ hữu hạn bất phương trình tuyến tính Dạng tường minh tập lồi đa diện cho sau: D := {x ∈ Rn | , x ≤ bi , i = 1, , m} Nếu tập lồi đa diện bị chặn gọi đa diện lồi Chương Một số kiến thức sở Định nghĩa 1.6 Một tập C gọi nón ∀λ > 0, ∀x ∈ C ⇒ λx ∈ C Một nón gọi nón lồi đồng thời tập lồi Nếu nón lồi lại tập lồi đa diện, ta nói nón lồi đa diện Sau điều kiện cần đủ để tập ∅ = K ⊂ Rn nón lồi Mệnh đề 1.1 ∅ = K ⊂ Rn nón lồi K + K ⊂ K, µK ⊂ K, µ ≥ Ta gọi k k n λi , λi ≥ 0, i = 1, , k}, K = cone{a , , a } = {v ∈ R |v = i=1 nón sinh vector a1 , , ak ∈ Rn Ví dụ 1.1 Trong không gian Rn , tập hợp Rn + = {x ∈ Rn : xi ≥ 0, i = 1, 2, , n}, Rn − = {x ∈ Rn : xi ≤ 0, i = 1, 2, , n}, nón lồi Định nghĩa 1.7 Cho E ⊆ Rn ( không thiết lồi) Tập E ∗ := {y ∈ Rn | y T x ≤ ∀x ∈ E}, gọi tập đối cực E Từ định nghĩa nón, dễ thấy E nón, tập đối cực E trở thành E ∗ := {y ∈ Rn | y T x ≤ ∀x ∈ E} Chương Một số kiến thức sở Ví dụ 1.2 Nếu E không gian tập đối cực E không gian vuông góc với E Tức E ∗ = E T = {y ∈ Rn | y T x = ∀x ∈ E} Mệnh đề 1.2 (xem Mệnh đề 7.1, [1]) (i) Tập đối cực E ∗ E tập lồi đóng chứa gốc E ⊆ F F ∗ ⊆ E ∗ (ii) E ⊆ E ∗∗ Nếu E lồi, đóng chứa gốc E = E ∗∗ (iii) ∈ intE E ∗ bị chặn Chứng minh (i) E ∗ lồi đóng, chứa gốc giao nửa không gian đóng chứa gốc Điều khẳng định (i) suy trực tiếp từ định nghĩa (ii) E ⊆ E ∗∗ suy trực tiếp từ định nghĩa Bây ta giả sử E lồi, đóng chứa gốc Do E ⊆ E ∗∗ , nên ta cần E ∗∗ ⊆ E Thật vậy, trái lại, tồn u ∈ E ∗∗ \ E Do E lồi đóng u ∈ / E, nên theo định lý tách mạnh [1], tồn y = thỏa mãn y, x ≤ ≤ y, u , ∀x ∈ E Từ bất đẳng thức đầu suy y ∈ E ∗ y, u ≤ 1, u ∈ E ∗∗ , mâu thuẫn với bất đẳng thức sau Vậy E = E ∗∗ (iii) Trước hết ta tập đối cực hình cầu Br : tâm 0, bán kính r hình cầu B 1r : tâm 0, bán kính 1r Thật vậy, dễ thấy khoảng cách từ đến siêu phẳng y, x = ||y|| ||y|| Vậy y ∈ (Br )∗ ≥ r Điều tương đương với y ∈ B 1r Chứng tỏ (Br )∗ = B 1r Do ∈ intE tồn r > cho Br ⊂ E Điều tương đương với E ∗ ⊂ (Br )∗ = B 1r Tương đương với việc E ∗ tập bị chặn Trong trường hợp tập lồi đa diện cho tường minh hệ bất Chương Một số kiến thức sở đẳng thức tuyến tính, ta có công thức tường minh tập đối cực Giả sử P tập lồi đa diện cho P := {x| , x ≤ bi , i = 1, , m}, x0 ∈ P Giả sử x0 = Như bi ≥ vơi i Giả sử bi ≥ với i = 1, , p bi = với i = p + 1, , m Bằng cách chia cho bi > 0, ta viết P := {x| , x ≤ 1, i = 1, , p, , x ≤ 0, i = p+1, , m} (1.1) Mệnh đề 1.3 (xem Mệnh đề 7.3, [1]) Giả sử P tập lồi đa diện cho (1.1) Khi đối cực P tập Q = co{0, a1 , , ap } + cone{ap+1 , , am } Chứng minh Theo định nghĩa Q, phần tử thuộc Q tổ hợp lồi điểm 0, a1 , , ap tổ hợp không âm điểm ap+1 , , am Vậy với y ∈ Q, ta có biểu diễn p m j y= ζj aj , λj a + j=1 j=p+1 với p λj ≥ 0, ζj ≥ ∀j, λj ≤ j=1 Nhân tích vô hướng với x, ta có p m j x, y = λj aj , x , ∀x ∈ P λj a , x + j=1 j=p+1 Do aj , x ≤ với j = 1, , p aj , x ≤ với j = p + 1, , m, nên từ suy x, y ≤ với x ∈ P với y ∈ Q Suy Q ⊆ P ∗ Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto Giả sử x ∈ S(N ) ∩ XE xN điểm thuộc S(N ) Thì ϕ(CxN ) − N r(xN ) ≥ ϕ(Cx ) − N r(x ), ϕ(Cx ) − N r(x ) ≥ ϕ(CxN ) − N r(CxN ) Cộng vế với vế hai bất đẳng thức ta có (N − N )(r(xN ) − r(x )) ≥ Vì N < N nên r(xN ) ≤ r(x ) = (vì x ∈ XE ) Do theo Bổ đề 3.5, ta có xN ∈ XE Lý luận tương tự ta có: S(N ) ∩ XE = ∅ ≤ N < N ∗ Giả sử x1 x2 nghiệm tối ưu toàn cục Bài toán (3.4) (3.5) ϕ(Cx1 ) = ϕ(Cx1 )−N r(x1 ) ≤ ϕ(Cx2 )−N r(x2 ) (3.7) Chú ý rằng, y nghiệm toán qui hoạch tuyến tính max{e(Cz − Cx2 ) : Cz ≥ Cx2 , z ∈ X}, (3.8) y ∈ XE Thật vậy, y ∈ X, Cy ≥ Cy, Cy ≥ Cx2 Do e(Cy − Cx2 ) ≥ e(Cy − Cx2 ) Vì y nghiệm (3.8) nên Cy = Cy , tức y ∈ XE Do r(y) = Với u∗ ∈ ∂ϕ(C(x2 )) có ϕ(y) − N r(y) − [ϕ(Cx2 ) − N r(x2 )] = ϕ(Cy) − ϕ(Cx2 ) + N r(x2 ) ≥ u∗ (Cy − Cx2 ) + N e(Cy − Cx2 ) = (N e + u∗ )(Cy − Cx2 ) ≥ 0, (3.9) bất đẳng thức cuối suy từ định nghĩa N Cy ≥ Cx2 Vì y ∈ XE , có ϕ(Cx1 ) ≥ ϕ(Cy) Từ điều (3.9) suy ϕ(Cx1 ) ≥ ϕ(Cx2 )N r(x2 ), 43 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto với (3.7) cho thấy ϕ(Cx1 ) = ϕ(Cx2 ) − N r(x2 ) Hơn nữa, từ (3.9) ϕ(Cx1 ) ≥ ϕ(Cy) (vì y ∈ XE ) có (N e + u∗ )(Cy − Cx2 ) = Vì N e + u∗ > Cy ≥ Cx2 suy Cy = Cx2 Do x2 ∈ XE Vì vậy, từ phần (i) có N > N ∗ suy x2 ∈ XE∗ Trong trường hợp đặc biệt, ϕ tổ hợp tuyến tính hàng C, từ mệnh đề có hệ sau p i=1 ωi ui Hệ 3.7 Nếu ϕ(u) = N > max{−ωi , i = 1, , p} > Thì nghiệm tối ưu toàn cục toán (3.5) nghiệm tối ưu toàn cục toán (3.4) 3.1.2 Mô tả dạng qui hoạch lồi-lõm Nhiều toán hàm mục tiêu ràng buộc hàm yên ngựa xét [15, 16] Trong phần này, chứng tỏ tối ưu hóa tập hữu hiệu mô tả toán qui hoạch lồi-lõm Giả sử S p−đơn hình cho p p S := {s ∈ R : s ≥ e, sj ≤ M } j=1 Theo Philip [18], thấy với M đủ lớn, vector x hữu hiệu tồn vector s ∈ S cho sCx = max{sCy : y ∈ X} Rõ ràng, với s ∈ S toán qui hoạch tuyến tính max{sCy : y ∈ X}, 44 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto tương đương với max{λCy : y ∈ X}, λ = s/ p j=1 sj Do đó, kết tương tự cho đơn hình Λ cho p p Λ := {λ = (λ1 , , λp ) ∈ R : λj ≥ 1/M ∀j, λj = 1} j=1 Như trước, với số N > ta định nghĩa max{ϕ(Cx)−N (g(λ)−λCx) : x ∈ X, λ ∈ S}, (3.10) g(λ) = max{λCy : y ∈ X} Rõ ràng, g lồi tuyến tính khúc Do đó, (3.10) toán qui hoạch lồi-lõm, ϕ lồi Gọi S0 (N ) tập nghiệm (3.10) Giả sử S1 (N ) := {xN : ∃λN ∈ S, (λN , xN ) ∈ S0 (N )}, N1∗ := sup{N ≥ : S1 (N ) ∩ XE = ∅}, (3.11) h(λ, x) := g(λ) − λCx = max{ λ, Cy − Cx : y ∈ X} y Bổ đề 3.6 (xem Bổ đề 3.1, [14]) (i) h hàm lồi-tuyến tính khúc h(λ, x) ≥ 0, ∀λ ∈ S, ∀x ∈ X (ii) x ∈ XE x ∈ X tồn λ ∈ S cho h(λ, x) = (iii) h(λ, x) ≥ r(x) với λ ∈ S, x ∈ X Chứng minh (i) g lồi cực đại họ hàm affine X đa diện, g lồi tuyến tính khúc Do đó, h hàm lồi-tuyến tính khúc Tính không âm h suy từ định nghĩa (ii) Theo Philip [18], x ∈ XE tồn λ ∈ S cho λCx ≥ λCy, ∀y ∈ X 45 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto Từ định nghĩa g suy λCx ≥ g(λ) Có nghĩa h(λ, x) ≤ Mà h không âm, h(λ, x) = (iii) Giả sử yx nghiệm toán qui hoạch tuyến tính r(x) Thì r(x) := max{ e, Cy − Cx : Cy ≥ Cx, y ∈ X} = e, Cyx − Cx y Vì yx ∈ X, Cyx ≥ Cx λ ≥ e, từ định nghĩa h(λ, x) có h(λ, x) ≥ λ, Cyx − Cx ≥ e, Cyx − Cx = r(x) Mệnh đề 3.13 (xem Mệnh đề 3.1, [14]) Nếu N > N0∗ := |u∗ |− ∀u∗ = (u∗1 , , u∗p ) ∈ ∂ϕ(C(X)) nghiệm tối ưu toàn cục Bài toán (3.10) nghiệm tối ưu toàn cục Bài toán (3.4) Chứng minh Giả sử N > N0∗ xN ∈ S(N ) Vì xN ∈ S(N ), nên ϕ(xN ) − N r(xN ) ≥ ϕ(x) − N r(x) ∀x ∈ X Vì N > N0∗ , theo Mệnh đề 3.11 ta có xN ∈ XE Do theo (ii) Bổ đề 3.7, tồn λN ∈ S h(λN , xN ) = Từ điều r(x) ≤ h(λ, x) suy ϕ(xN ) − N h(λN , xN ) ≥ ϕ(x) − N h(λ, x), ∀λ ∈ S, ∀x ∈ X Nghĩa (λN , xN ) nghiệm (3.10) 46 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto 3.2 Thuật toán xấp xỉ giải toán tối ưu tập Pareto Theo kết thu từ phần trước, giải Bài toán (3.5) cực đại hàm lồi X hàm lồi-lõm S × X Khi áp dụng kĩ thuật tối ưu toàn cục phép xấp xỉ phương pháp nhánh cận để giải toán quy gặp khó khăn nảy sinh từ việc hàm mục tiêu toán định nghĩa G(X) số M xuất định nghĩa đơn hình S phải xác định Chúng ta biết chi phí tính toán phương pháp tối ưu toàn cục tăng nhanh theo chiều không gian, phép tối ưu toàn cục thực Xét Bài toán (3.5), với x ∈ G(X) lấy u = Cx s(u) = r(x) s(u) := max{e(v − u) : v ≥ u, v ∈ C(X)} Bài toán (3.5) viết sau max{ΦN (u) := ϕ(u)−N s(u) : u ∈ C(X)} (3.12) Vì hàm mục tiêu ΦN (3.12) không định nghĩa khắp nơi, nên để giải (3.12) phải có thuật toán thực miền C(X) Giả sử ∈ G(X) Ω ⊂ G(X) cho ΦN (x) ≤ ΦN (0) = −N r(0) ≤ với x ∈ Ω Do Ω ⊆ ΦN,0 := {x ∈ Rn : ΦN (x) ≤ ΦN (0)} với ΦN,0 tập mức Trong thuật toán xấp xỉ trong, xây dựng dãy đa diện to dần {Pl } dãy {xl } ⊂ X thỏa mãn Pl ⊆ ΦN,l := {x ∈ Rn : ΦN (x) ≤ ΦN (xl )}, ∀l 47 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto Nếu có bước lặp j mà thỏa mãn bao hàm thức X ⊂ Pl , xj nghiệm tối ưu toàn cục Thật vậy, giả sử điểm xuất phát đỉnh x0 X, ví dụ x0 = P0 = Ω ⊂ ΦN,0 Trong bước lặp l, ta xét X ⊂ Pl Nếu thỏa mãn, xj nghiệm tối ưu toàn cục Trái lại, ta xác định điểm xl+1 ∈ X đa diện Pl+1 cho Pl+1 ⊂ ΩN,l+1 , cách sử dụng phép đối cực tập lồi đa diện sau Theo định nghĩa tập đối cực [1], X ⊂ Pl Pl∗ ⊂ X ∗ Nhắc lại đối cực Z ∗ tập lồi Z định nghĩa Chương Z ∗ = {u : u, z ≤ ∀z ∈ Z} Ta có P0∗ = cone(c1 , , ck ) Giả sử V (Pl∗ ) R(Pl∗ ) tập đỉnh tập hướng cực biên Pl∗ Vì X bị chặn, theo [19] biết Pl∗ ⊂ X ∗ max{ u, x : x ∈ X} ≤ ∀u ∈ V (Pl∗ ), max{ u, x : x ∈ X} ≤ ∀u ∈ R(Pl∗ ) Do đó, Pl∗ X ∗ phải tồn ul+1 ∈ V (Pl∗ ) ∪ R(Pl∗ ) cho ul+1 , xl+1 > ul+1 ∈ V (Pl∗ ), ul+1 , xl+1 > ul+1 ∈ R(Pl∗ ), đó, xl+1 ∈ X nghiệm tối ưu toán qui hoạch tuyến tính max{ ul+1 , x : x ∈ X} Do đó, theo định nghĩa tập đối cực xl+1 ∈ / (Pl∗ )∗ = Pl Chúng ta lặp lại thủ tục với Pl+1 = conv(Pl ∪ {xl+1 }) Theo [19] Định lý 48 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto 3.3, ta có ∗ Pl+1 = Pl∗ ∩ {u : xl+1 , u ≤ 1} ∗ Vì vậy, đỉnh hướng cực biên Pl+1 tính toán từ Pl∗ phương pháp có [11 Chương 2] Chú ý rằng, theo [19 Hệ 16.4] ta có: dimPl∗ = n − linealityPl = k Bởi linealityPl = linealityP0 = n − k Do đó, đỉnh hướng cực biên Pl∗ tính toán không gian tuyến tính tạo nên vector {ci , i = 1, , k} Thuật toán mô tả chi tiết sau Thuật toán Bước khởi tạo: Đặt P0 = Ω = {x ∈ X : ΦN (x) ≤ ΦN (0)}, V (P0∗ ) = {0}, R(P0∗ ) = {ci : i = 1, , k}, x0 = u0 = 0, l = Bước lặp thứ l : Bước 1: Với u ∈ V (Pl∗ ) ∪ R(Pl∗ ) cố định ta giải toán qui hoạch tuyến tính max{ u, x : x ∈ X}, để tìm nghiệm tối ưu x(u) (do đó, x(u) ∈ V (X)) Bước 2: a) Nếu u, x(u) ≤ ∀u ∈ V (Pl∗ ), u, x(u) ≤ ∀u ∈ R(Pl∗ ), 49 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto dừng: ul nghiệm tối ưu toàn cục b) Trái lại, chọn ul+1 ∈ V (Pl∗ ) ∪ R(Pl∗ ) xl+1 ∈ argmax{ ul+1 , x : x ∈ X} cho ul+1 , xl+1 > ul+1 ∈ V (Pl∗ ), ul+1 , xl+1 > ul+1 ∈ R(Pl∗ ) Bước 3: Lấy ∗ Pl+1 := Pl∗ ∩ {t = (t1 , , tk ) : ti xl+1 , ci ≤ 1} i=1,k Bước 4: Khi thực bước lặp i với xl+1 tìm điểm chấp nhận khác Bài toán (3.7) Giả sử ul+1 điểm chấp nhận tốt ∗ ∗ ) Tăng l lên đến bước lặp l ), R(Pl+1 Tính V (Pl+1 Nhận xét 3.2 Do P0 ⊂ Φ0 theo cách xác định ul , nên Pl ⊂ Φl với l Do đó, thuật toán dừng bước lặp l ul nghiệm tối ưu toàn cục Ngoài ra, điểm chấp nhận xl+1 phát sinh bước lặp l đỉnh X Vì xl+1 ∈ / Pl xl+1 ∈ Pl+1 với l, số lần lặp bị chặn số đỉnh X Do đó, thuật toán hữu hạn Nhận xét 3.3 Khối lượng tính toán thuật toán nằm việc xác định đỉnh hướng cực biên đa diện tạo từ đa diện cho cộng với siêu phẳng cắt Ví dụ 3.4 Xét toán tối ưu vector tuyến tính max{Cx : x ∈ X}, với C= 0 X = {(x1 , x2 ) ∈ R2 : x1 + x2 ≤ 1, x1 ≥ 0, x2 ≥ 0} 50 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto Cho ϕ(x1 , x2 ) = 2x1 − x2 hàm tuyến tính Giải: Ta có: ϕ(Cx) = 2x1 − x2 y 2x -x = XE X Ω Hình 3.2 Ta xét toán tối ưu tập Pareto sau max{2x1 − x2 : x ∈ XE } Với e = (1, 1) lấy x0 = (0, 0), ta tính e(Cy − Cx0 ) = y1 + y2 với y ∈ X Trước tiên, ta giải toán sau r(0) = max{y1 + y2 }, y 51 x Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto với điều kiện {y1 + y2 ≤ 1, y1 ≥ 0, y2 ≥ 0} Dễ dàng thấy r(0) = Theo Hệ 3.7, lấy N = Xét toán sau max{ΦN (x) = 2x1 − x2 − : x ∈ X} Ta có: ΦN (0) = −2 Tập mức có dạng: ΦN,0 = {x = (x1 , x2 ) ∈ X : 2x1 − x2 ≤ 0} Đặt P0 ⊂ Ω = ΦN,0 = {x = (x1 , x2 ) ∈ X : 2x1 − x2 ≤ 0} Giả sử lấy P0 = {0} Do P0 X nên ta tìm x1 ∈ X\P0 Lấy x1 = (0, 1) P1 = conv(P0 ∪ {x1 }) = {x = (x1 , x2 ) ∈ X : ≤ x2 ≤ 1} Do P1 X nên ta tìm x2 ∈ X\P1 Lấy x2 = (1, 0) P2 = conv(P1 ∪ {x2 }) = X Suy x2 = (1, 0) nghiệm tối ưu toàn cục Vậy toán ban đầu đạt giá trị lớn x2 = (1, 0) Kết luận chương Chương trình bày phương pháp xấp xỉ để giải toán tối ưu tập Pareto Để giải toán tối ưu vector tuyến tính quy toán qui hoạch lồi-lõm toán cực đại hàm lồi Sau đó, áp dụng kĩ thuật xấp xỉ để tìm nghiệm hữu hiệu cho toán quy Mục 3.1 trình bày cách mô tả toán tối ưu hàm tuyến tính tập nghiệm hữu hiệu Pareto dạng toán qui hoạch lồi-lõm toán cực đại hàm lồi Mục 3.2 trình thuật toán sử dụng tập đối cực để giải toán tối ưu tập Pareto Điểm nhấn thuật toán phép toán tính đỉnh cạnh cực biên đa diện lồi bước lặp thực không gian tạo nên 52 Chương Phương pháp tập đối cực giải toán tối ưu tập Pareto hàng độc lập ma trận lập nên từ mục tiêu toán tối ưu vector tuyến tính Số hàng độc lập thường nhỏ nhiều so với số biến định toán 53 Kết luận Luận văn trình bày toán tối ưu vector tuyến tính, số kết tập nghiệm Pareto toán tối ưu vector tuyến tính phương pháp tập đối cực giải toán tối ưu vector tuyến tính tập Pareto Các nội dung là: Nhắc lại kiến thức bản, bao gồm số khái niệm giải tích lồi, tập lồi đa diện, hàm lồi, hàm affine, cực đại hàm lồi Trình bày số kết toán tối ưu vector tuyến tính, tính chất tập nghiệm hữu hiệu thuật toán nón pháp tuyến xác định tập hữu hiệu Trình bày phương pháp tập đối cực giải toán tối ưu tập Pareto, cách quy toán tối ưu hàm tuyến tính tập Pareto dạng cực đại hàm lồi áp dụng thủ tục xấp xỉ để tìm nghiệm tối ưu toán quy 54 Tài liệu tham khảo [1] Nguyễn Văn Hiền, Lê Dũng Mưu Nguyễn Hữu Điển (2015), Nhập môn giải tích lồi ứng dụng, NXB ĐH Quốc Gia, Hà Nội [2] An, Le T., Tao Pham D., Muu Le D (1996), "D C Optimization Approach for Optimizing over the Efficient Set", Operations Research Letters 19, pp 117-128 [3] Benson H.P (1991), "An All-Linear Programming Relaxation Algorithm for Optimizing over the Efficient Set", J of Global Optimization 1, pp 83-104 [4] Benson H.P (1992), "A Finite, Nonadjacent Extreme Point Search Algorithm for Optimization over the Efficient Set", J of Optimization Theory and Application 73, pp 47-63 [5] Benson H.P (1993), "A Bisection-Extreme Point Search Algorithm for Optimizing over the Efficient Set in the Linear Dependence Case", J of Global Optimization, 3, pp 95-111 [6] Bolintineanu, S (1993), "Minimization of a Quasi-concave Function over an Efficient Set", Mathematical Programming 61, pp 89-110 [7] Dauer, J P., and Fosnaugh, T.A (1995), "Optimization over the Efficient Set", Journal of Global Optimization 7, pp 261-277 55 TÀI LIỆU THAM KHẢO [8] D.T.Luc (1989), Theory of Vector Optimization, Springer-Verlag, Berlin [9] Fulop, J (1994), "A Cutting Plane Algorithm for Linear Optimization over the Efficient Set", In S Komlosi, T.Rapcsak and S Schaible eds., Generalized Convexity, Springer, Berlin, pp 374-385 [10] Hoang Tuy (1997), Convex Analysis and Global Optimization, Kluwer Academic Publishers, Dordrecht, Boston, London [11] Horst, R., and Tuy, H (1996), Global Optimization (Deterministic Approaches), Springer-Verlag, Berlin [12] Horst, R., and Thoai, N V (1996), "Utility Function Programs and Optimization over the Efficient Set in Multiple Objective Decision Making" Universitat Trier, Forschungsberich Nr, 03 [13] Isermann H and Steuter R.E (1987), "Computational Experience Concerning Pazoff Tabbles and Minimum Criterion Values over the Efficient Set" European J of Operations Research 33, pp 91-97 [14] Luc L.T., Muu L.D (2001), Global Optimization Approach to Optimizing over the Efficient Set in Peter Gritzmann, Reiner Horst, Ekkehard Sachs, Rainer Tichatschke (Eds.), Recent Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Springer [15] Muu, Le D., and Oettli, W (1991), "Method for Minimizing a Convex-Concave Function Over a Convex Set", J of Optimization Theory and Applications 70, pp 377-384 56 TÀI LIỆU THAM KHẢO [16] Muu, Le D (1993), "An Algorithm for Solving Convex Programs with and Additional Convex-Concave Constraints", Mathematical Programming 61, pp 75-87 [17] N.T.B Kim and D.T.Luc (2000), "Normal Cones to a Polyhedral Convex Set and Generating Efficient Faces in Linear Multiple Objective Programming", Acta Mathematica Vietnamica, 25(1), pp 101124 [18] Philip J (1972), "Algorithms for the Vector Maximization Problem" Mathematical Programming 2, pp 207-229 [19] Rockafellar R.T (1970), Convex Analysis, Princeton University Press, Princeton New Jersey [20] Thach, P.T., Konno, H., and Yokota, D (1976), "Dual Approach to Optimization on the Set of Pareto-Optimal Solutions" Journal of Optimization Theory and Applications 88, pp 689-707 57