ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN LÊ NGỌC BIÊN ĐỐI NGẪU TRONG QUY HOẠCH PHÂN THỨC ĐA MỤC TIÊU Chuyên ngành : TOÁN GIẢI TÍCH Mã số: 60 46 01 02 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học: GS.TS Trần Vũ Thiệu Hà Nội- 2015 Mục lục MỞ ĐẦU KIẾN THỨC CHUẨN BỊ 1.1 Tập lồi tập đa diện lồi 1.2 Hàm lồi hàm phân thức afin 1.3 Hàm liên hợp 10 1.4 Bài toán tối ưu đa mục tiêu 11 ĐỐI NGẪU TRONG QUY HOẠCH PHÂN TUYẾN TÍNH 13 2.1 Bài toán quy hoạch phân tuyến tính 13 2.2 Bài toán đối ngẫu 14 2.3 Định lý đối ngẫu 15 2.4 Ví dụ minh họa 19 QUY HOẠCH PHÂN THỨC ĐA MỤC TIÊU 3.1 21 Bài toán gốc toán tham số hóa 21 3.1.1 Bài toán gốc 21 3.1.2 Tham số hóa theo Dinkelbach 22 3.2 Đối ngẫu Fenchel-Lagrange toán vô hướng 24 3.3 Đối ngẫu Fenchel-Lagrange đa mục tiêu 27 3.4 Ví dụ 35 KẾT LUẬN 38 TÀI LIỆU THAM KHẢO 38 MỞ ĐẦU Lý thuyết đối ngẫu toán tối ưu, với hay nhiều hàm mục tiêu, chủ đề quan trọng lý thuyết tối ưu hóa Lý thuyết đối ngẫu toán tối ưu với hàm mục tiêu hàm phân thức (tỉ số hai hàm số) phát triển mạnh mẽ vài chục năm gần Wolfe (1991), Weir - Mond (1989), Nakayama (1984), Jahn (1983) Wanka - Bot (2002) Trường hợp tối ưu phân thức Charnes Cooper ([6], 1962) nghiên cứu cho hàm mục tiêu phân tuyến tính Dinkelbach ([7], 1967) mối liên hệ toán phân thức toán tham số hóa Schaible ([9], 1976) đưa phép biến đổi cho phép xử lý toán phân thức Đáng ý Wanka Bot [10] đưa đối ngẫu liên hợp dựa cách tiếp cận nhiễu Sau tác giả [4], [5] nghiên cứu quan hệ khái niệm đối ngẫu qui hoạch phân thức Bot R I., Charesy R Wanka G ([3], 2006) xét quan hệ đối ngẫu cho lớp toán tối ưu phân thức đa mục tiêu cụ thể toán với nhiều hàm mục tiêu, mục tiêu tỉ số hàm lồi hàm lõm Trên thực tế, kiểu toán tạo lớp riêng có đặc điểm toán nói chung không lồi Kaul Lyall ([8], 1989) xây dựng toán đối ngẫu kết đối ngẫu cho toán tối ưu phân thức đa mục tiêu, với giả thiêt hàm khả vi Ohlendorf Tammer (1994) đưa đối ngẫu kiểu Fenchel cho toán tối ưu véctơ với hàm mục tiêu phân thức Để phát triển kiến thức giải tích học, chọn đề tài luận văn: "Đối ngẫu toán tối ưu phân thức đa mục tiêu" Mục đích luận văn tìm hiểu trình bày số kết có đối ngẫu toán qui hoạch phân thức, cụ thể đối ngẫu quy hoạch phân tuyến tính mục tiêu đối ngẫu toán quy hoạch phân thức đa mục tiêu không lồi Luận văn viết dựa chủ yếu tài liệu tham khảo [1] - [3] [7] Nội dung luận văn gồm ba chương • Chương “Kiến thức chuẩn bị”nhắc lại kiến thức tập lồi, tập lồi đa diện tính chất tập này; nhắc lại khái niệm hàm lồi, hàm afin tính chất đáng ý hàm afin, hàm liên hơp giới thiệu toán tối ưu đa mục tiêu số khái niệm có liên quan • Chương "Đối ngẫu quy hoạch phân tuyến tính"trình bày toán quy hoạch phân tuyến tính gốc đối ngẫu, kết lý thuyết đối ngẫu quy hoạch phân tuyến tính, tương tự quy hoạch tuyến tính Cuối chương nêu số ví dụ minh họa • Chương "Quy hoạch phân thức đa mục tiêu" trình bày cách tiếp cận tham số Dinkelbach ([7]) để đặt tương ứng toán ban đầu (gọi toán gốc) với toán tối ưu lồi, đa mục tiêu trung gian Sau vô hướng hóa toán đa mục tiêu trung gian xây dựng toán đối ngẫu đa mục tiêu tương ứng Trình bày kết tính đối ngẫu yếu, đối ngẫu mạnh đối ngẫu đảo cặp toán đối ngẫu Từ cho phép nhận đặc trưng đối ngẫu nghiệm hữu hiệu toán tối ưu phân thức đa mục tiêu ban đầu Do thời gian kiến thức hạn chế nên chắn luận văn có thiếu sót định, kính mong quí thầy cô bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.TS Trần Vũ Thiệu, tận tình giúp đỡ suốt trình làm luận văn Tác giả chân thành cảm ơn thầy giáo, cô giáo Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội, nhiệt tình giảng dạy tạo điều kiện thuận lợi trình tác giả học tập nghiên cứu Khoa Toán - Cơ - Tin học nhà trường Chương KIẾN THỨC CHUẨN BỊ Chương nhắc lại số kiến thức tập lồi, tập lồi đa diện, hàm lồi, hàm phân thức afin (tỉ số hai hàm tuyến tính afin), hàm liên hợp giới thiệu toán tối ưu đa mục tiêu khái niệm có liên quan Nội dung chương tham khảo chủ yếu từ tài liệu [1], [2] [3] 1.1 Tập lồi tập đa diện lồi A.Tập lồi khái niệm quan trọng dùng rộng rãi tối ưu hoá Định nghĩa 1.1 Tập C Rn gọi tập lồi C chứa trọn đoạn thẳng nối hai điểm thuộc Nói cách khác, tập C lồi λa+(1−λ)b ∈ C với a, b ∈ C ≤ λ ≤ Ví dụ 1.1 Các tập sau tập lồi: a) Tập afin, tức tập chứa trọn đường thẳng qua hai điểm thuộc b) Siêu phẳng, tức tập có dạng H = {x ∈ Rn : aT x = α, a ∈ Rn \ {0}, α ∈ R} c) Các nửa không gian đóng H1 = {x ∈ Rn : aT x ≤ α}, H2 = {x ∈ Rn : aT x ≥ α} d) Hình cầu đóng B(a, r) = {x ∈ Rn : ||x − a|| ≤ r}(a ∈ Rn , r > 0cho trước) Từ định nghĩa tập lồi trực tiếp suy số tính chất đơn giản sau đây: a) Giao họ tập lồi tập lồi (nhưng hợp không đúng!) b) Tổng hai tập lồi hiệu hai tập lồi tập lồi c) Nếu C ⊂ Rm , D ⊂ Rn tích C × D = {(x, y) : x ∈ C, y ∈ D} tập lồi Rm+n (Có thể mở rộng cho tích nhiều tập lồi) Định nghĩa 1.2 a) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + + λk ak với ∈ Rn , λi ≥ 0, λ1 +λ2 + +λk = 1, gọi tổ hợp lồi điểm a1 , a2 , , ak b) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + + λk ak với ∈ Rn , λi ≥ 0, gọi tổ hợp tuyến tính không âm hay tổ hợp nón điểm a1 , a2 , , ak Định nghĩa 1.3 Cho E tập Rn a) Giao tất tập afin chứa E gọi bao afin E , ký hiệu aff E Đó tập afin nhỏ chứa E b) Giao tất tập lồi chứa E gọi bao lồi E , ký hiệu conv E Đó tập lồi nhỏ chứa E Định nghĩa 1.4 a) Thứ nguyên (hay số chiều) tập afin M, ký hiệu dim M, thứ nguyên (số chiều) không gian song song với b) Thứ nguyên (hay số chiều) tập lồi C, ký hiệu dim C, thứ nguyên hay số chiều bao afin aff C B Tập lồi đa diện dạng tập lồi có cấu trúc đơn giản hay gặp lý thuyết tối ưu tuyến tính Định nghĩa 1.5 Một tập lồi mà giao số hữu hạn nửa không gian đóng gọi tập lồi đa diện Nói cách khác, tập nghiệm hệ hữu hạn bất phương trình tuyến tính: ai1 x1 + ai2 x2 + + ain xn ≤ bi , i = 1, 2, , m, (1.1) nghĩa tập x nghiệm Ax ≤ b với A = (aij ) ∈ Rm×n , b = (b1 , , bm )T Nhận xét 1.1 Do phương trình tuyến tính biểu diễn tương đương hai bất phương trình tuyến tính, nên tập nghiệm hệ (hữu hạn) phương trình bất phương trình tuyến tính tập lồi đa diện: ai1 x1 + ai2 x2 + + ain xn = bi , i = 1, 2, , k, ai1 x1 + ai2 x2 + + ain xn ≤ bi, i = k + 1, , m, Một tập lồi đa diện bị chặn (giới nội) không bị chặn (không giới nội) Một tập lồi đa diện bị chặn gọi đa diện lồi Các đa giác lồi theo nghĩa thông thường mặt phẳng hai chiều (tam giác, hình vuông, hình tròn, ) ví dụ cụ thể đa diện lồi R2 Định nghĩa 1.6 Tập lồi đa diện K ⊆ Rn gọi nón lồi đa diện K có thêm tính chất x ∈ K ⇒ λx ∈ K với x ∈ K λ ≥ 0.(Ví dụ nón Rn ) + Cho D tập lồi đa diện xác định hệ bất phương trình tuyến tính (1.1) Sau để đơn giản, ta giả thiết D không chứa đường thẳng (tức a, b ∈ D cho λa + (1 − λ)b ∈ D với λ ∈ R) Hai yếu tố tạo nên tập lồi đa diện D đỉnh cạnh vô hạn D Theo giải tích lồi, hiểu khái niệm sau Định nghĩa 1.7 Điểm x0 ∈ D gọi đỉnh D rank{ai : , x0 = bi } = n (với = (ai1 , , ain )T , i = 1, , m) Định nghĩa tương đương: x0 ∈ D đỉnh D x1 , x2 ∈ D, x1 = x0 x2 = x0 , λ ∈ (0, 1) cho x0 = λx1 + (1 − λ)x2 , nói cách khác: x0 điểm nằm đoạn thẳng nối hai điểm thuộc D Định nghĩa 1.8 Đoạn thẳng [x1 , x2 ], x1 = x2 , gọi cạnh hữu hạn D x1 , x2 đỉnh D rank{ai : , x1 = , x2 = bi } = n − Định nghĩa 1.9 Tia Γ = {x0 + λd : λ ≥ 0} ⊆ D, x0 ∈ D, d ∈ Rn , gọi cạnh vô hạn D rank{ai : , x = bi , ∀x ∈ Γ} = n − Để hiểu rõ tập lồi đa diện ta cần biết số khái niệm sau Định nghĩa 1.10 Véctơ d ∈ Rn , d = 0, gọi hướng lùi xa D ∃x0 ∈ D cho {x0 + λd : λ ≥ 0} ⊆ D Tập hợp hướng lùi xa D cộng với gốc tạo thành nón lồi đóng, gọi nón lùi xa D, ký hiệu rec D Định nghĩa 1.11 Hướng lùi xa d D gọi hướng cực biên không tồn hai hướng lùi xa khác d1 , d2 cho d = λ1 d1 + λ2 d2 với λ1 , λ2 > Có thể chứng minh tập lồi đa diện D không bị chặn rec D = {0}, nghĩa D có hướng lùi xa Trong toán tối ưu, ta thường gặp tập lồi đa diện có dạng S = {x ∈ Rn : Ax ≤ b, x ≥ 0}với A ∈ Rm×n , b ∈ Rm , tức S tập nghiệm không âm hệ (hữu hạn) bất phương trình tuyến tính Tập không chứa đường thẳng (do x ≥ 0) nên S có đỉnh Từ định nghĩa nêu cho thấy: a) Điểm x0 ∈ S đỉnh S hệ véctơ {ak : ak , x0 = bk }∪{ek : x0 k = 0} có hạng n b) Các hướng cực biên (chuẩn hóa) S nghiệm sở hệ Ay ≤ 0, eT y = 1, y ≥ 0, eT = (1, , 1) c) Giả sử tia Γ = {x0 + λd : λ ≥ 0}, x0 đỉnh d hướng cực biên S Khi Γ cạnh vô hạn S rank({ak : ak , x = bk , ∀x ∈ Γ} ∪ {ek : xk = 0, ∀x ∈ Γ}) = n − 1.2 Hàm lồi hàm phân thức afin Định nghĩa 1.12 a) f : C → R xác định tập lồi C ⊆ Rn gọi hàm lồi C với x1 , x2 ∈ C số thực λ ∈ [0, 1] ta có f [λx1 + (1 − λ)x2 ] ≤ λf (x1 ) + (1 − λ)f (x2 ) b) g : C → R gọi hàm lõm C f = −g hàm lồi C Sau số ví dụ quen thuộc hàm lồi với ∅ = C ⊆ Rn tập lồi: + Hàm chuẩn Euclid ||x|| = x, x , x ∈ Rn + Hàm định tập lồi C : δC (x) =  0 x ∈ C +∞ x ∈ C / + Hàm tựa C: sC (x) = sup y T x (cận xT y tập lồi C) y∈C + Hàm khoảng cách từ điểm x ∈ Rn tới C: dC (x) = inf y∈C x−y • Hàm phân thức afin thường gặp toán tối ưu Hàm có dạng f (x) = pT x + α p(x) = T , q(x) q x+β p, q ∈ Rn , α, β ∈ R dom f = {x ∈ Rn : q T x + β > 0} Ký hiệu S tập lồi cho q(x) = q T x + β = với x ∈ S Nếu q(x) có dấu khác S, tức có x, y ∈ S cho q T x + β > q T y + β < hàm q(x) liên tục nên tồn z ∈ [x, y], tức z ∈ S , cho q(z) = 0.Vì thế, không giảm tổng quát, ta giả thiết q(x) > với x ∈ S Trường hợp q(x) < với x ∈ S nhân tử số p(x) mẫu số q(x) hàm f(x) với (- 1) có q(x) > với x ∈ S Định lý sau nêu tính chất đơn điệu theo phương hàm phân thức afin Định lý 1.1 ([1], tr 78) f (x) = p(x) q(x) hàm đơn điệu đoạn thẳng nằm trọn tập lồi S = {x : q T x + β > 0} Chứng minh Lấy hai điểm tùy ý a, b ∈ S tính giá trị hàm f điểm x đoạn thẳng nối a b, tức x = λa + (1 − λ)b với ≤ λ ≤ Ta thấy f (x) = p[λa + (1 − λ)b] λp(a) + (1 − λ)p(b) = q[λa + (1 − λ)b λq(a) + (1 − λ)q(b) Đạo hàm f theo λ : df (x) = × dλ q (x) p(a) p(b) q(a) q(b) = p(a)q(b) − p(b)q(a) q (x) Dấu đạo hàm phụ thuộc dấu biểu thức [p(a)q(b) − p(b)q(a)] Vì thế, λ thay đổi đoạn [0, 1] hàm f(x) tăng giảm đồng số [a, b] Ta nhắc lại hàm khả vi f : Rn → R gọi giả lồi với x, y ∈ S ta có f (x)T (y − x) ≥ kéo theo f (y) ≥ f (x), nghĩa f (y) < f (x) f (x)T (y − x) < Hàm f gọi giả lõm −f giả lồi Định lý sau nêu tính chất quan trọng khác hàm phân thức afin Định lý 1.2 ([2], tr 703) Giả sử f (x) = pT x+α q T x+β S tập lồi cho (q T x + β) = S Khi đó, hàm f(x) vừa giả lồi, vừa giả lõm S Chứng minh Ta để ý q T x + β > với x ∈ S q T x + β < với x ∈ S , trái lại có a ∈ S, b ∈ S cho q T a + β > q T b + β < 0, có q T z + β = với z tổ hợp lồi a b, trái với giả thiết định lý Trước hết ta chứng minh f giả lồi Thật vậy, giả sử x, y ∈ S thỏa mãn Ta có Do f (x)T (y − x) ≥ Ta cần rõ f (y) ≥ f (x) (q T x + β)p − (pT x + α)q f (x) = (q T x + β)2 f (x)T (y − x) ≥ (q T x + β)2 > nên ≤ [(q T x + β)p − (pT x + α)q]T (y − x) = (pT y + α)(q T x + β) − (q T y + β)(pT x + α) Vì thế, (pT y + α)(q T x + β) ≥ (q T y + β)(pT x + α) Nhưng (q T x + β) (q T y + β) dương âm nên chia hai vế cho (q T x + β)(q T y + β) > ta nhận pT x + α pT y + α ≥ T , tức f (y) ≥ f (x) qT y + β q x+β Vì thế, f giả lồi Tương tự, chứng minh f (x)T (y − x) ≤ kéo theo f (y) ≤ f (x) Vì thế, f giả lõm định lý chứng minh 1.3 Hàm liên hợp Định nghĩa 1.13 Cho hàm tùy ý f : Rn → R ∪ {±∞} Hàm liên hợp f định nghĩa hàm f ∗ (p) = sup {pT x − f (x)}, p ∈ Rn (1.2) x∈Rn Thực ra, supremum (1.2) cần lấy x ∈ domf , f (x) = +∞ ∀x ∈ / dom f Hệ thức (1.2) gọi phép biến đổi Young - Fenchel Từ định nghĩa suy f ∗∗ (x) ≡ (f ∗ )∗ (x) = sup {pT x − f ∗ (p)}, x ∈ Rn p∈Rn Mệnh đề 1.1 f ∗ : Rn → R ∪ {±∞} hàm lồi, đóng 10 Điều kiện quy (CQ) p ri(domfk ) cho gi (x0 ) < 0, ∀i ∈ N gi (x0 ) ≤, ∀i ∈ L ∃x ∈ k=1 Định lý 3.4 (Đối ngẫu mạnh [12]) Nếu ν(Pµ,λ ) hữu hạn điều kiện quy (CQ) thỏa mãn toán (Dµ,λ ) có nghiệm tối ưu có hệ thức đối ngẫu mạnh ν(Pµ,λ ) = ν(Dµ,λ ) Định lý 3.5 (Điều kiện tối ưu) Giả sử có điều kiện quy (CQ) x ¯ nghiệm tối ưu (Pµ,λ ) Khi đó, tồn nghiệm tối ưu (r1 , , rp , s1 , , sp , v ) ¯ ¯ ¯ ¯ ¯ (Dµ,λ ) cho có điều kiện tối ưu sau đây: ∗ r (i) fk (¯) + fk (¯k ) = rk x, k = 1, , p x ¯T ¯ (ii) −µk hk (¯) + (−µk hk )∗ (¯k ) = sT x, k = 1, , p x s ¯k ¯ (iii) v T g(¯) = ¯ x ∗ vT g ¯ (iv) − p − T p λk (¯k + sk ) r ¯ = k=1 λk (¯k + sk ) r ¯ x ¯ k=1 Chứng minh Giả sử x nghiệm tối ưu (Pµ,λ ) Theo Định lý 3.4, tồn ¯ nghiệm tối ưu (r, s, v ) (Dµ,λ ) cho có hệ thức đối ngẫu mạnh ¯ ¯ ¯ p p λk (fk (¯) − µk hk (¯)) = − x x k=1 p ∗ λk fk (¯i ) − r k=1 λk (−µk hk )∗ (¯i ) s k=1 p T − v g ¯ ∗ − λk (¯k + sk ) r ¯ k=1 Từ p p ∗ λk fk (¯) − µk hk (¯) + fk (¯k ) + (−µk hk )∗ (¯k ) x x r s 0= T + (¯ g) v k=1 ∗ − λk (¯k + sk ) r ¯ k=1 Đẳng thức viết lại thành p ∗ λk (fk (¯) + fk (¯k ) − rk x) + −µk hk (¯) + (−µk hk )∗ (¯k ) − sT x x r ¯T ¯ x s ¯k ¯ 0= k=1 λk (¯k + sk ) r ¯ + k=1  T p x + v T g(¯) − infn  ¯ ¯ x x∈R λk (¯k + sk ) r ¯ k=1 26 T p  x + v T g(x) − v T g(¯) ¯ ¯ x Do λk ≥ 0, k = 1, , p, g(¯) ≤ 0, v ≥ nên cách áp dụng bất đẳng thức x ¯ Young - Fenchel ta thấy vế phải hệ thức lớn hay Do phải từ suy kết luận (i) - (iv) định lý 3.3 Đối ngẫu Fenchel-Lagrange đa mục tiêu Trong mục giới thiệu toán đối ngẫu (Dµ ) toán đa mục tiêu (Pµ ); µ ∈ Rp Bài toán đối ngẫu biểu diễn ngắn gọn theo hàm liên hợp thành phần hàm mục tiêu Với toán đối ngẫu này, định lý đối ngẫu yếu, đối ngẫu mạnh đối ngẫu đảo phát biểu chứng minh Sau kết dùng để nhận đặc trưng đối ngẫu nghiệm hữu hiệu toán phân thức ban đầu Trước nêu toán đối ngẫu đa mục tiêu (Pµ ) ta để ý viết (Dµ,λ ) dạng tương đương: p sup λk r,s,v∈Bµ,λ ∗ −fk (rk ) − −(µk hk )∗ (sk ) − ( k=1 T ∗ v g) pλk − pλk p λk (rk + sk ) k=1 Bµ,λ = {(r, s, v) : r = (r1 , , rp ), rk ∈ Rn , k = 1, , p, s = (s1 , , sp ), sk ∈ Rn , k = 1, , p, v ∈ Rm , v ≥ 0} Bằng cách đặt vk = v pλk với k = 1, , p, ta có p λk vk = v ≥ k=1 điều đưa tới toán đối ngẫu sau (Pµ ) v− (Dµ ) Ψ(µ) (r, s, v, λ, t) sup (r,s,v,λ,t)∈Bµ (µ) (µ) Ψ(µ) (r, s, v, λ, t) = Ψ1 (r, s, v, λ, t), , Ψp (r, s, v, λ, t) (µ) ∗ Ψk (r, s, v, λ, t) = −fk (rk ) − (−µk hk )∗ (sk ) T −(vk g)∗ − pλk p λj (rj + sj ) j=1 27 + tk , k = 1, , p T Tập ràng buộc xác định sau: p p (r, s, v, λ, t) : λ ∈ Bµ = p int(R+ ), λk vk ≥ 0, λk tk = k=1 k=1 biến đối ngẫu r = (r1 , , rp ), rk ∈ Rn , s = (s1 , , sp ), sk ∈ Rn , v = (v1 , , vp ), vk ∈ Rm , k = 1, , p, λ = (λ1 , , λp )T ∈ int(Rp ) t = (t1 , , )T ∈ Rp + Nghiệm hữu hiệu (Dµ ) định nghĩa tương tự (P) Định nghĩa 3.5 (Nghiệm hữu hiệu (Dµ )) Phần tử (¯, s, v , λ, t) ∈ Bµ r ¯ ¯ ¯ ¯ gọi nghiệm hữu hiệu (hay cực đại) (Dµ ) {Ψ(µ) (¯, s, v , λ, t) + Rp } ∩ Ψ(µ) (Bµ ) = {Ψ(µ) (¯, s, v , λ, t)} r ¯ ¯ ¯ ¯ r ¯ ¯ ¯ ¯ + Định lý 3.6 (Đối ngẫu yếu) Không tồn (r, s, v, λ, t) ∈ Bµ x ∈ A cho Ψ(µ) (r, s, v, λ, t) ≥ Φ(µ) (x)và Ψ(µ) (r, s, v, λ, t) = Φ(µ) (x) Chứng minh Giả sử có x ∈ A (r, s, v, λ, t) ∈ Bµ cho (µ) (µ) Φk (x) ≤ Ψk (r, s, v, λ, t), ∀k ∈ {1, ., p} p Φ(µ) (x) < Ψ(µ) (u, v, q, λ, t) với j ∈ {1, , p} Do λ ∈ int(R+ ) nên j j p p (µ) λk Φk (x) k=1 (µ) < (3.2) Ψk (u, v, q, λ, t) k=1 Theo bất đẳng thức Young - Fenchel ta nhận T −(vk g)∗ − pλk p λj (rj + sj ) T ≤ vk g(x) − j=1 − pλk T p λj (rj + sj ) x j=1 với k = 1, , p Áp dụng định nghĩa hàm liên hợp ta nhận (µ) − Φk ∗ ∗ (uk ) = −(fk + (−µk hk ))∗ (uk ) ≥ −fk (rk ) − (−µk hk )∗ (sk ) với rk , sk ∈ Rn thỏa mãn rk + sk = uk , k = 1, , p Do ta nhận đánh giá (µ) Ψk (r, s, v, λ, t) ≤− (µ) Φk ∗ T (uk ) + ti + vk g(x) + 28 pλk T p λj (rj + sj ) j=1 x với k = 1, , p Từ λ = (λ1 , , λp )T ∈ int(Rp ) suy + p p (µ) λk Ψk (r, s, v, λ, t) (µ) Φk ≤− p ∗ k=1 ∗ k=1 k=1 p p g(x) λi vi λk tk + + λk (uT x) k (uk ) + i=1 k=1 p (µ) ≤ λk Φk (x) k=1 mà hệ trực tiếp bất đẳng thức Young - Fenchel Φk , k = 1, , p kiện p ∗ p λk tk = k=1 λk vk g(x) ≤ k=1 Nhưng điều mâu thuẫn với hệ thức (3.2) Định lý chứng minh Định lý 3.7 (Đối ngẫu mạnh) Giả sử điều kiện quy (CQ) thỏa mãn x nghiệm hữu hiệu thực (Pµ ) Khi đó, tồn nghiệm hữu ¯ hiệu (¯, s, v , λ, t) ∈ Bµ (Dµ ) có hệ thức đối ngẫu mạnh, tức r ¯ ¯ ¯ ¯ Φ(µ) (¯) = Ψ(µ) (¯, s, v , λ, t) x r ¯ ¯ ¯ ¯ ¯ Chứng minh Do x nghiệm hữu hiệu thực (Pµ ) nên tồn λ ∈ ¯ int(Rp ) cho x nghiệm tối ưu toán ¯ + p (Pµ,λ ) ¯ inf x∈A k=1 ¯ λk (fk (x) − µk hk (x)) Do điều kiện (CQ) thỏa mãn nên theo Định lý 3.5, tồn nghiệm tối ưu ((˜, s, v ) ∈ Bµ,λ toán (Dµ,λ ) cho điều kiện tối ưu (i) - (iv) r ˜ ˜ ¯ ¯ Định lý 3.5 thỏa mãn Bây ta xây dựng nghiệm chấp nhận (¯, s, v , λ, t) toán r ¯ ¯ ¯ ¯ (Dµ ) sau Đặt r = r, s = s, λ vk = v với k = 1, , p, ¯ ˜ ¯ ˜ ¯ ¯ ˜ ¯ tk = (¯k + sk )T x + (¯k g)∗ r ¯ ¯ vT − pλk 29 p λj (rj + sj ) j=1 , ∀k = 1, , p Ta nhận thấy T p p ¯ r λk (¯k + sk ) ¯ ¯ ¯ λk tk = p x+ ¯ k=1 k=1 k=1 T p ¯ r λk (¯k + sk ) ¯ = p x+ ¯ k=1 k=1 ¯ ¯ λk ¯ v T g pλk T p ¯ r λk (¯k + sk ) ¯ = − pλk ¯ vT λk (¯k g)∗ p ¯ r λj (¯j + sj ) ¯ j=1 p ∗ ¯ r λj (¯j + sj ) ¯ − j=1 p ∗ T x + (¯ g) ¯ v ¯ r λk (¯k + sk ) ¯ − k=1 k=1 = (theo Định lý 3.5 (iv)) Hơn ta có p p ¯ ¯ λk vk = k=1 k=1 ¯ ˜ ˜ λk ¯ v = v ≥ pλik Điều chứng tỏ (¯, s, v , λ, t) ∈ Bµ r ¯ ¯ ¯ ¯ Hơn nữa, x (¯, s, v , λ, t) ¯ r ¯ ¯ ¯ ¯ (µ) ∗ Ψk (¯, s, v , λ, t) = −fk (¯k ) − (−µk hk )∗ (¯k ) r ¯ ¯ ¯ ¯ r s − (¯k g)∗ (− vT + (¯k + sk ) r ¯ ¯ pλk T p ¯ r λk (¯k + sk )) ¯ k=1 x + (¯k g)∗ (− ¯ vT ¯ pλk p ¯ r λk (¯k + sk )) ¯ k=1 ∗ = −fk (¯k ) − (−µk hk )∗ (¯k ) + (¯k + sk )T x r s r ¯ ¯ với k = 1, , p Từ Định lý 3.5 (i) - (ii), vế phải fk (¯) − µk hk (¯) suy x x (µ) (µ) Ψk (¯, s, v , λ, t) = Φk (¯), k = 1, , p r ¯ ¯ ¯ ¯ x Theo Định lý 3.6, ta có quan hệ đối ngẫu yếu, nghĩa (r, s, v , λ, t) nghiệm ¯ ¯ ¯ ¯ ¯ hữu hiệu (Dµ ) có quan hệ đối ngẫu mạnh (Pµ ) (Dµ ) Để thiết lập định lý đối ngẫu đảo theo bước Wanka Bot [10]), ta cần định nghĩa bổ đề nêu Với λ ∈ int(Rp ), ký hiệu + p Bλ = p λk vk ≥ 0, (r, s, v, t) : k=1 λk tk = k=1 30 , r = (r1 , , rp ), s = (s1 , , sp ), v = (v1 , , vp ), t = (t1 , , )T , rk ∈ Rp , sk ∈ Rp , vk ∈ Rm , tk ∈ R, k = 1, , p Ta định nghĩa M = {a ∈ Rp : ∃λ ∈ int Rp , ∃ (r, s, v, t) ∈ Bλ + p p cho (µ) λk Ψk (r, s, v, λ, t)} λ k ak = k=1 k=1 Hai bổ đề sau Wanka Bot chứng minh cho chủ đề khác (xem Mệnh đề [11]) Bổ đề 3.2 Ta có Ψ(µ) (Bµ ) ∩ Rp = M Chứng minh Từ định nghĩa trực tiếp suy Ψ(µ) (Bµ ) ∩ Rp ⊆ M Chỉ phải chứng minh bao hàm thức ngược lại Giả sử a ∈ M Do tồn λ ∈ int(Rp ) (r, s, v, t) ∈ Bλ cho + p p (µ) λ k ak = k=1 λk Ψk (r, s, v, λ, t) k=1 p p λk (−µk hk )∗ (sk ) ∗ λk fk (rk ) − =− k=1 k=1 p ∗ T λk vk g − k=1 − pλk p p λj (rj + sj ) + j=1 λk tk k=1 Đặt ¯ tk = ∗ ak + fk (rk ) + (−µk hk )∗ (sk ) + − pλk ∗ T vk g p λj (rj + sj ) j=1 p ¯ ¯ λk tk = 0, nghĩa (r, s, v, λ, t) ∈ Bµ Do Vậy với k=1, ,p Ta thấy k=1 ak = ∗ −fk (rk ) − (−µk hk )∗ (sk ) − ∗ T vk g − pλk p λj (rj + sj ) j=1 ¯ Kết a = Ψ(µ) (r, s, v, λ, t) ∈ Ψ(µ) (Bµ ) ta có bao hàm thức M ⊆ Ψ(µ) (Bµ )∩ Rp Đó điều cần chứng minh Bổ đề 3.3 a ∈ Rp nghiệm hữu hiệu M với a ∈ M có ¯ tương ứng với λa ∈ int(Rp ) (ra , sa , v a , ta ) ∈ Bλa thỏa mãn + p p λ a ak k¯ λ a ak k ≥ k=1 k=1 31 Chứng minh (xem [3], tr 195) Tiếp theo ta đề cập tới định lý đối ngẫu đảo Ta cần điều kiện sau Định nghĩa 3.6 Cho λ ∈ Rp Điều kiện (Cµ,λ ) thỏa mãn từ + p (µ) λk Φk (x) > −∞ inf x∈A k=1 suy tồn xλ ∈ A cho p p (µ) λk Φk (x) inf x∈A (µ) λk Φk (xλ ) = k=1 k=1 Định Lý đối ngẫu đảo (Pµ ) sau định lý mở rộng Định lý nêu [8] Định lý 3.8 Giả thiết điều kiện (CQ) thỏa mãn giả sử có điều kiện (Cµ,λ ) với λ ∈ int(Rp ) + (i) Giả sử (r, s, v , λ, t) nghiệp hữu hiệu (Dµ ) Khi ¯ ¯ ¯ ¯ ¯ a) Ψ(µ) r, s, v , λ, t ∈ cl Φ(µ) (A) + Rp ; ¯ ¯ ¯ ¯ ¯ + b) Tồn nghiệm hữu hiệu chân xλ ∈ A (Pµ ) cho ¯¯ p (µ) (µ) λk Φk (¯λ ) − Ψk x¯ r, s, v , λ, t ¯ ¯ ¯ ¯ ¯ = k=1 (ii) Hơn nữa, Φ(µ) (A) + Rp tập đóng tồn nghiêm hữu hiệu thực + x ∈ A (Pµ ) cho ¯ p p ¯ (µ) x ¯ λk Φk (¯λ ) k=1 ¯ (µ) x λk Φk (¯) = k=1 Φ(µ) (¯) = Ψ(µ) r, s, v , λ, t x ¯ ¯ ¯ ¯ ¯ Chứng minh a) Ký hiệu α = Ψ(µ) r, s, v , λ, t Do α cực đại Ψ(µ) (Bµ ) ¯ ¯ ¯ ¯ ¯ ¯ ¯ nên ta có α ∈ Ψ(µ) (Bµ ) ∩ Rp = M ¯ Giả sử α ∈ cl Φ(µ) (A) + Rp Khi đó, tồn λ1 ∈ Rp \ {0} số α ∈ R cho ¯ / + p p λ1 ak k¯ k=1 λ1 dk , ∀d ∈cl Φ(µ) (A) + Rp + k 0, vk ≥ 0, k = 1, 2, λi ti = 0, 2λ1 v1 = 2λ2 v2 = λ1 (5 − 2µ1 ) + λ2 (2 − 5µ2 i=1 Chọn µ = (2, )T ta thấy (v , λ, t) chấp nhận (Dµ ) với v = ¯ ¯ ¯ ¯ ¯ ¯ µ ¯ ¯ ¯ ¯ ¯ ( , )T , λ = (5, 2)T , t = (0, 0)T Hơn nữa, giá trị hàm mục tiêu Ψ(¯) v , λ, t = [0, 0]T cải tiến (theo nghĩa hữu hiệu) mà không vi phạm ràng buộc, nghĩa (v , λ, t) nghiệm hữu hiệu (Dµ ) Với µ = (2, )T hàm mục ¯ ¯ ¯ ¯ ¯ µ tiêu gốc Φ(¯) viết sau: x µ Φ(¯) (x) = −3x µ Ta thấy x = ∈ A phần tử thỏa mãn Φ(¯) (x) = [0, 0]T Rõ ràng, ¯ µ điều kiện (CQ) thỏa mãn, Cµ,λ với λ ∈ int(R2 ) Φ(¯) (A) + R2 ¯ + + tập đóng Theo Định lý 4.5, x = nghiệm hữu hiệu thực (Pµ ) Hơn ¯ ¯ nữa, ta có F (0) = 36 =µ ¯ định lý đảm bảo x nghiệm hữu hiệu thực theo nghĩa Geoff¯ rion (P) Tóm lại, chương trình bày kết nghiên cứu tác giả [3] đối ngẫu toán tối ưu phân thức đa mục tiêu, không lồi (P) Dùng cách tiếp cận tham số Dinkelbach, đưa (P) toán đa mục tiêu lồi (Pµ ) Trình bày cách xây dựng toán đối ngẫu toán tối ưu lồi này, dựa hàm liên hợp hàm tử số mẫu số thành phần mục tiêu, hàm ràng buộc kết đối ngẫu yếu, đối ngẫu mạnh đối ngẫu đảo cặp toán đối ngẫu Từ rút đặc trưng đối ngẫu nghiệm hữu hiệu toán tối ưu phân thức, đa mục tiêu không lồi ban đầu 37 KẾT LUẬN Luận văn đề cập tới số kết lý thuyết đối ngẫu quy hoạch phân tuyến tính mục tiêu tối ưu phân thức đa mục tiêu Đây chủ để có tính thời nhiều người quan tâm nghiên cứu Luận văn trình bày nội dung sau: Các kiến thức cần thiết giải tích lồi như: tập lồi, tập lồi đa diện, hàm lồi, hàm phân thức afin, hàm liên hợp giới thiệu toán tối ưu đa mục tiêu với khái niệm có liên quan Bài toán quy hoạch phân tuyến tính toán quy hoạch phân tuyến tính đối ngẫu tương ứng Các định lý đối ngẫu yếu, đối ngẫu thuận đối ngẫu đảo mối liên hệ nghiệm tối ưu toán gốc toán đối ngẫu tương ứng Một số kết quan hệ đối ngẫu cho lớp toán tối ưu phân thức đa mục tiêu, dựa cách tiếp cận tham số Dinkelbach, cách xây dựng toán đối ngẫu theo hàm liên hợp theo đối ngẫu Fenchen - Lagrange đa mục tiêu Đây kiến thức mới, chuyên sâu giải tích tối ưu hóa Tác giả hy vọng sau có có dịp tìm hiểu sâu chủ đề 38 Tài liệu tham khảo [1] Bajalinov E B (2003), Linear - Fractional Programming: Theory, Methods, Applications and Software Kluwer Academic Publishers [2] Bazara M.S et al (2006), Nonlinear Programming: Theory and Algorithms 3rd Edition A John Willey & Sons, Inc., Publication [3] Bot R I., Charesy R Wanka G (2006), Duality for multiobjective fractional programming problems, Nonlinear Analysis Forum 11(2), pp 185 – 201 [4] Bot R I., Wanka G (2004), An analysis of some dual problems in multiobjective optimization (I) Optimization, Volume 53, Number 3, Pages 281-300 [5] Bot R I., Wanka G (2004), An analysis of some dual problems in multiobjective optimization (II) Optimization, Volume 53, Number 3, Pages 301-324 [6] Charnes A,Cooper W W.(1962), Programming with linear fractional functionals Naval Research Logistics Quarterly, Volume 9, Pages 181-186 [7] Dinkelbach W (1967), On nonlinear fractional programming Management Science, Volume 13, Number 7, Pages 492-497 39 [8] Kaul R N., Lyall V (1989), A note on nonlinear fractional vector maximization OPSearch, Volume 26, Number 2, Pages 108-121, 1989 Schaible S (1976), Fractional rogramming I: Duality Management Science, Volume 22B, Pages 858-867 [9] Seshan C R (1980), On duality in linear fractional programming, Proc Indian Aead Sci (Math Sci.), Vol 80, N0 1, pp 35-42 [10] Wanka G., Bot R I (2002), A new duality approach for multi objective convex optimization problems Journal of Nonlinear and Convex Analysis, Volume 3, Number 1, Pages 41 - 57 [11] Wanka G., Bot R I (2002), On the relations between different dual problems in convex mathematical programming In: Chamoni P., Leisten R., Martin A., Minnemann J and Stadler A., editors, Operations Research Proceedings 2001, Pages 255 - 265, Springer-V erlag, Berlin 40