Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu không trơ

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ———————————– Phạm Thị Linh ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU KHÔNG TRƠN LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2022 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ———————————– Phạm Thị Linh ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU KHÔNG TRƠN LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số chuyên ngành: 9.12 NGƯỜI HƯỚNG DẪN KHOA HỌC : 1. Nguyễn Công Điều Hà Nội – 2022 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các kết quả viết chung với các tác giả khác đã được sự nhất trí của các đồng tác giả đưa vào Luận án. Các kết quả được nêu trong Luận án này là trung thực và chưa từng được ai công bố trong bất kỳ một công trình nào khác.

Tôi xin chịu trách nhiệm với những lời cam đoan của mình. Tác giả Phạm Thị Linh ii Lời cảm ơn Luận án được hoàn thành tại Viện Công nghệ Thông tin, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn tận tình của GS. Nguyễn Công Điều. Tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc nhất tới hai Thầy.

Tác giả cũng xin bày tỏ lòng biết ơn tới các thầy giáo, cô giáo của Viện Công nghệ Thông tin, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và nghiên cứu. Trong quá trình học tập, nghiên cứu tác giả đã được tham gia Seminar của Viện Toán học và Khoa học ứng dụng Thăng Long, Trường Đại học Thăng Long Hà Nội. Tác giả xin chân thành cảm ơn. Tác giả xin chân thành cảm ơn Ban giám hiệu, Khoa Khoa học Cơ bản và Bộ môn Toán - Tin của Trường Đại học Kinh tế và Quản trị Kinh doanh, nơi tác giả đang công tác đã tạo điều kiện thuận lợi trong suốt quá trình học tập và nghiên cứu.

Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc tới những người thân trong gia đình đã động viên, chia sẻ và khích lệ tác giả để tác giả có thể hoàn thành Luận án tiến sĩ của mình. Tác giả Phạm Thị Linh iii Mục lục Lời cam đoan ii Lời cảm ơn iii Mục lục iv Danh mục các ký hiệu và chữ viết tắt vi Mở đầu 1 Chương 1. Một số kiến thức chuẩn bị 18 1.1 Một số khái niệm cơ bản .2 Một số kết quả vô hướng hóa của Gong .3 Dưới vi phân suy rộng .4 Kết luận Chương 1. Điều kiện cần và điều kiện đủ cho nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu 25 2.1 Điều kiện cần .1 Điều kiện cần Fritz John .2 Điều kiện cần Kuhn-Tucker .3 Kết luận Chương 2.

Điều kiện cần và điều kiện đủ cho tựa nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục iv tiêu 41 3.1 Điều kiện cần .1 Điều kiện cần Fritz John .2 Điều kiện cần Kuhn-Tucker .3 Kết luận Chương 3. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với nghiệm hữu hiệu yếu 57 4.1 Bài toán đối ngẫu kiểu Mond-Weir .2 Bài toán đối ngẫu kiểu Wolfe .3 Kết luận Chương 4. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với tựa nghiệm hữu hiệu yếu 73 5.1 Bài toán đối ngẫu kiểu Mond-Weir .2 Bài toán đối ngẫu kiểu Wolfe .3 Kết luận Chương 5. 86 Kết luận và hướng nghiên cứu tiếp theo 88 Danh mục công trình của tác giả 90 Tài liệu tham khảo 91 v Danh mục các ký hiệu và chữ viết tắt X∗ Không gian tôpô đối ngẫu của X hx∗ , xi Giá trị của phiếm hàm x∗ ∈ X ∗ tại x ∈ X cl Bao đóng ∗ yếu conv Bao lồi intD Phần trong của D d(x, Q) Khoảng cách từ x ∈ X đến Q B(x; δ) Hình cầu mở tâm x bán kính δ f − (x; υ) Đạo hàm theo phương Dini dưới của f tại x theo phương v f + (x; υ) Đạo hàm theo phương Dini trên của f tại x theo phương v ∇f (x) Đạo hàm Fréchet của f tại x ∇G f (x) Đạo hàm Gâteaux của f tại x ∂ C f (x) Dưới vi phân Clarke của f tại x ∂ M P f (x) Dưới vi phân Michel-Penot của f tại x ∂ ∗ f (x) Dưới vi phân suy rộng của f tại x T (D; x) Nón tiếp tuyến Clarke của D tại x ∈ D N (D; x) Nón pháp tuyến Clarke của D tại x (MFP) Bài toán quy hoạch thương đa mục tiêu vi Mở đầu Các bài toán tối ưu có hàm mục tiêu là các hàm thương được gọi là bài toán quy hoạch thương.

Bài toán quy hoạch thương được nảy sinh từ các vấn đề kinh tế hoặc phi kinh tế. Đó chính là Bài toán cực đại lợi nhuận trên chi phí, Bài toán cực đại giá trên thời gian, Bài toán cực đại đầu ra trên đầu vào, Bài toán cực tiểu chi phí trên thời gian, Bài toán cực đại tỷ lệ tín hiệu trên tạp âm của bộ lọc quang phổ trong vật lý, Bài toán lên kế hoạch, Bài toán lập trình quy mô lớn,. Năm 1962, Charnes và Cooper [1] đã đưa ra bài toán quy hoạch thương. Từ đó, bài toán quy hoạch thương thu hút được sự chú ý và quan tâm của rất nhiều nhà nghiên cứu.

Tuy nhiên phần lớn các kết quả mang tính lý thuyết và xét trên tập chấp nhận được là tập lồi tùy ý hay khối đa điện lồi tùy ý [2] – [14]. Giả sử f, g, hk (k = 1, 2, · · · , m) là các hàm trên tập D của không gian Euclide n chiều Rn. Xét hàm f (x) q(x) = (1) g(x) trên tập S = {x ∈ D : hk (x) 6 0, k = 1, · · · , m}, (2) trong đó, g(x) dương trên D. Ta có, Bài toán quy hoạch phi tuyến: (P ) : sup{q(x) : x ∈ S} (3) được gọi là Bài toán quy hoạch thương một mục tiêu.

Ta có một số dạng khác của Bài toán quy hoạch thương một mục tiêu như: sup{ min qi (x) : x ∈ S} (4) 16i6p 1 và p nX o sup qi (x) : x ∈ S , (5) i=1 trong đó, qi (x) = fi (x)/gi (x), gi (x) > 0. (6) Nếu f, g là các hàm affine và S là đa diện lồi thì (P) được gọi là bài toán quy hoạch thương tuyến tính. Bài toán này có dạng n cT x + α o sup T : Ax 6 b, x > 0 , (7) d x+β trong đó, c, d ∈ Rn , α, β ∈ R, T là ký hiệu phép chuyển vị, A là ma trận cấp m × n và b ∈ Rm. Bài toán (P) được gọi là bài toán quy hoạch thương bậc hai nếu f, g là các hàm bậc hai và S là đa diện lồi.

Bài toán (P) được gọi là bài toán quy hoạch thương lõm nếu f là hàm lõm trên D và g, hk là các hàm lồi trên D, D là một tập lồi. Nếu giảm bớt các giả thiết về tính lồi hoặc tính lõm thì bài toán quy hoạch thương một mục tiêu được gọi là bài toán không lõm suy rộng và được nhiều tác giả quan tâm trong tối ưu toàn cục. Xét Bài toán (3): Bài toán này nảy sinh từ các vấn đề kinh tế hoặc phi kinh tế. Sau đây, ta sẽ trình bày một số ứng dụng của bài toán này trong các lĩnh vực kinh tế, phi kinh tế và một số lĩnh vực khác.

Gilmore và Gomory đã phân tích bài toán chia cổ phần trong ngành công nghiệp giấy [16]. Nhóm nghiên cứu này đã chỉ ra rằng việc giảm tỷ lệ nguyên liệu thô được thực hiện là tối ưu hơn việc giảm thiểu lượng nguyên liệu bị hao hụt. Bài toán chia cổ phần này là bài toán quy hoạch thương tuyến tính. Hoskins và Blom [17] đã sử dụng bài toán quy hoạch thương một mục tiêu để phân tích giảm chi phí lao động.

2 Bài toán quy hoạch thương phi tuyến bậc hai lõm xuất phát từ bài toán lựa chọn danh mục đầu tư được đề xuất bởi Ziemba, Parkan và Brooks-Hill [18]. Ohlson và Ziemba [19] đã xét bài toán n cT x o max :x∈S , (8) (xT Cx)γ trongđó, c ∈ Rn dương, C là ma trận xác định dương cấp n × n và 1 γ ∈ 0,. Ở đây c và C được xác định bởi vectơ lợi nhuận kỳ vọng 2  1 e và ma trận phương sai-hiệp phương sai V. Với γ ∈ 0, thì tử số 2 không phải là hàm lồi và do đó Bài toán (8) không phải là bài toán quy hoạch thương lõm [20]–[22].

Mao [23], Faaland và Jacobs [24] đã sử dụng bài toán quy hoạch thương tuyến tính trong việc lựa chọn các danh mục đầu tư. Những ứng dụng khác của bài toán quy hoạch thương một mục tiêu trong kế hoạch tài chính được đề xuất bởi Uberti [25] với bài toán cho thuê. Konno và Inori [26] đã tối ưu hóa kỳ hạn trung bình hoặc năng suất trung bình trong giao dịch trái phiếu bằng bài toán quy hoạch thương một mục tiêu. Dantzig, Blattner và Rao [27] đã phân tích bài toán thương một mục tiêu để xác định hành trình cho các con tàu hoặc máy bay trong đó một chu trình trong mạng lưới sẽ được xác định trước để giảm thiểu tỷ lệ chi phí theo thời gian.

Kydland [28] đã nghiên cứu về bài toán vận chuyển hàng hóa với việc tối ưu hóa lợi nhuận trên mỗi đơn vị thời gian. Cả bài toán chi phí và bài toán thời gian đều phụ thuộc vào lượng hàng hóa. Nếu doanh thu là hàm tuyến tính cũng như chi phí và thời gian là các hàm tuyến tính thì đã có kết quả nghiên cứu đối với bài toán quy hoạch thương tuyến tính. Derman [29], Klein [30] đã nghiên cứu về quy trình ngẫu nhiên để cực tiểu chi phí/thời gian.

Charnes, Cooper và Rhodes [31] đã sử dụng bài toán quy hoạch thương tuyến tính để đánh giá hoạt động của các tổ chức phi lợi nhuận 3 trong các bài toán công cộng và đưa ra một loạt các quyết định. Các quyết định này được chọn dựa vào cực đại tỷ số của đầu ra/đầu vào. Một ví dụ khác về cực đại đầu ra/đầu vào được đưa ra bởi Stancu- Minasian [32].