Một mô hình bài toán tối ưu hóa có bao nhiêu thành phần

Trường Đại học Nông nghiệp I Hà Nội Khoa Công nghệ thông tin PGS.TS. NGUYỄN HẢI THANH CÁC MÔ HÌNH VÀ PHẦN MỀM tối ưu hoá và ứng dụng trong nông nghiệp (bài giảng điện tử trong khuôn khổ dự án CNTT) HÀ NỘI, THÁNG 10 NĂM 2007 MỤC LỤC CHƯƠNG I. ỨNG DỤNG MỘT SỐ MÔ HÌNH TỐI ƯU TRONG NÔNG NGHIỆP 3 1. MÔ HÌNH QUY HOẠCH ĐƠN MỤC TIÊU 3 1.1. Mô hình tối ưu một mục tiêu (tuyến tính và phi tuyến) 3 1.2. Các ví dụ minh hoạ bài toán tối ưu một mục tiêu 4 2. MÔ HÌNH QUY HOẠCH ĐA MỤC TIÊU TUYẾN TÍNH VÀ PHI TUYẾN 8 2.1. Giới thiệu bài toán quy hoạch đa mục tiêu 8 2.2. Các khái niệm cơ bản của bài toán tối ưu đa mục tiêu 9 2.3. Các ví dụ minh hoạ bài toán quy hoạch đa mục tiêu 10 CHƯƠNG II. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BẰNG PHƯƠNG PHÁP ĐƠN HÌNH 23 1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BTQHTT DẠNG CHÍNH TẮC 23 1.1. Ví dụ 23 1.2. Thuật toán đơn hình cho BTQHTT dạng chính tắc 27 2. PHƯƠNG PHÁP ĐƠN HÌNH HAI PHA GIẢI BTQHTT TỔNG QUÁT 28 2.1. Ví dụ 28 2.2. Thuật toán đơn hình hai pha giải BTQHTT dạng tổng quát 30 3. GIẢI CÁC BÀI TOÁN TỐI ƯU TRÊN MICROSOFT EXCEL 32 3.1. Giải BTQHTT 32 3.2. Giải bài toán quy hoạch phi tuyến có ràng buộc tuyến tính 34 3.3. Một số ví dụ khác 36 4. GIẢI BTQHTT TRONG LINGO 36 5. GIẢI BTQHTT BẰNG PHẦN MỀM QHTT 38 CHƯƠNG III. BÀI TOÁN QUY HOẠCH PHI TUYẾN 40 1. PHƯƠNG PHÁP RST2ANU GIẢI BÀI TOÁN TỐI ƯU PHI TUYẾN TOÀN CỤC HỖN HỢP NGUYÊN 40 1.1. Đặt vấn đề 40 1.2. Thuật giải tìm kiếm ngẫu nhiên có kiểm soát RST2ANU 41 1. 3. Một số nhận xét về phiên bản nâng cấp của phần mềm 43 2. MỘT SỐ VÍ DỤ ÁP DỤNG RST2ANU 44 2.1. Bài 1: Bài toán xác định tham số sàng phân loại 44 2.2. Bài 2: Bài toán xác định cơ cấu đầu tư chăn nuôi cá 46 1 3. TÍCH HỢP RST2ANU VỚI MATLAB 48 3.1. Nhập từ bàn phím 48 3.2. Nhập từ tệp 50 CHƯƠNG IV. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU BẰNG PHƯƠNG PHÁP THOẢ DỤNG MỜ 52 1. CÁC KHÁI NIỆM CƠ BẢN 52 1.1. Phát biểu mô hình 52 1.2. Phương án tối ưu Pareto 53 1.3. Phương pháp thoả dụng mờ giải BTQHTT đa mục tiêu 54 2. GIẢI BTQHTT ĐA MỤC TIÊU BẰNG CHƯƠNG TRÌNH MÁY TÍNH MULTIOPT 59 2.1. Ví dụ 59 2.2. Bài toán quy hoạch đất xã Nhân Chính 63 2.3. Bài toán quy hoạch đất xã Trâu Quỳ 70 CHƯƠNG V. MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU PHI TUYẾN ĐA MỤC TIÊU 71 1. BÀI TOÁN TỐI ƯU PHI TUYẾN TRONG MÔI TRƯỜNG MỜ / NGẪU NHIÊN 71 1.1. Phát biểu bài toán và phương pháp mức ưu tiên 71 1.2. Xử lý các ràng buộc 72 1.3. Xử lý các mục tiêu 74 ~ 1.4. Sử dụng thông tin pay-off để đoán nhận e k , d j 77 1.5. Mô hình tất định tương đương của bài toán 79 1.6. Khái niệm tối ưu hoá PL-Pareto 79 2. THUẬT GIẢI TƯƠNG TÁC LẶP PRELIME VÀ MỘT SỐ ỨNG DỤNG 80 2.1. Phát biểu thuật giải 80 2.2. Bài toán Chakraborty 81 2.3. Bài toán xác định cơ cấu đầu tư cho các hộ chăn nuôi cá 87 2.4. Bài toán quy hoạch sử dụng đất trên địa bàn huyện Trùng Khánh 88 CHƯƠNG VI. KẾT LUẬN VÀ ĐỀ XUẤT MỘT SỐ HƯỚNG NGHIÊN CỨU 92 1. ÁP DỤNG CÁC MÔ HÌNH TỐI ƯU TRONG NÔNG NGHIỆP 92 2. NGHIÊN CỨU ÁP DỤNG VÀ ĐỀ XUẤT CÁC PHƯƠNG PHÁP TỐI ƯU 92 3. XÂY DỰNG CÁC PHẦN MỀM TỐI ƯU 93 4. XÂY DỰNG HỆ HỖ TRỢ RA QUYẾT ĐỊNH CÀI ĐẶT TRÊN MẠNG MÁY TÍNH 94 DANH MỤC TÀI LIỆU THAM KHẢO 96 2 Chương I ỨNG DỤNG MỘT SỐ MÔ HÌNH TỐI ƯU TRONG NÔNG NGHIỆP Tối ưu hoá là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng đến hầu hết các lĩnh vực, trong đó có nông nghiệp. Trong thực tế, việc tìm ra giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng. Phương án tối ưu là những phương án tốt nhất, tiết kiệm chi phí, tài nguyên, sức lực mà lại cho hiệu quả cao. Có thể phát biểu mô hình (bài toán) tối ưu tổng quát như sau: F(X) ÆMax (Min) với X ∈ D được gọi là miền ràng buộc. F ở đây có thể là một hàm vô hướng hay hàm véc tơ, tuyến tính hay phi tuyến. Trong trường hợp F là hàm vô hướng thì ta có mô hình quy hoạch (tối ưu) đơn mục tiêu, còn nếu F là véc tơ thì có mô hình quy hoạch (tối ưu) đa mục tiêu. X có thể là một biến đơn lẻ hay một tập hợp nhiều biến tạo thành một vectơ hay thậm chí là một hàm của nhiều biến khác. Biến có thể nhận các giá trị liên tục hay rời rạc. D là miền ràng buộc của X, thường được biểu diễn bởi các đẳng thức, bất đẳng thức, và được gọi là miền phương án khả thi hay phương án chấp nhận được. 1. MÔ HÌNH QUY HOẠCH ĐƠN MỤC TIÊU 1.1. Mô hình tối ưu một mục tiêu (tuyến tính và phi tuyến) Dạng chính tắc của bài toán tối ưu toàn cục một mục tiêu được biểu diễn như sau: Max (Min) f(X) với: X = (x1, x2, …, xn) (i) gj(X) ≤ 0, j = 1, 2, …, k, (ii) gj(X) = 0, j = k+1, k+2, …, m, Trong các bài toán thực tế có thể bổ sung các ràng buộc dạng: (iii) ai ≤ xi ≤ bi, i = 1, 2, …, n. Hàm mục tiêu f(X) và các hàm ràng buộc gj(X) với j=1,2, …,m có thể là tuyến tính hay phi tuyến.Véc tơ X có thể bao gồm các thành phần rời rạc hay liên tục hoặc là sự kết hợp giữa các thành phần rời rạc và các thành phần liên tục. Các dạng khác của bài toán tối ưu một mục tiêu đều có thể đưa về dạng chính tắc theo những quy tắc nhất định. Nếu ký hiệu D là miền các phương án (miền ràng buộc) cho bởi các ràng buộc (i), (ii) và/hoặc (iii) thì bài toán trên đây có thể viết gọn hơn như sau: f(X) → Max (Min) với X ∈ D. Lúc này, X* ∈ D được gọi là phương án tối ưu toàn cục nếu ∀ X∈D ta luôn có: f(X*) ≤ f(X). Trong trường hợp f(X*) ≤ f(X) chỉ đúng với ∀X∈D trong một lân cận của X* thì X* được gọi là phương án tối ưu địa phương. Trong trường hợp có ít nhất một trong các hàm mục tiêu hay ràng buộc là hàm phi tuyến, chúng ta có bài toán quy hoạch phi tuyến. Trong các bài toán tối ưu phi tuyến ứng dụng nói chung, và trong nông nghiệp nói riêng, lời giải tối ưu toàn cục có một ý 3 nghĩa quan trọng. Chẳng hạn trong thiết kế máy nông nghiệp, sau khi dùng phương pháp phân tích hồi qui nhiều chiều, ta thường thu được hàm mục tiêu f(X) có dạng phi tuyến. Các bài toán tối ưu toàn cục cũng có thể nảy sinh trong quy hoạch kinh tế - sinh thái vùng, hay xác định cơ cấu đất canh tác - cây trồng. Bài toán đặt ra là phải tìm được phương án tối ưu toàn cục. Có rất nhiều phương pháp giải các lớp bài toán tối ưu phi tuyến, nhưng chưa có phương pháp nào tỏ ra hữu hiệu cho mọi bài toán tối ưu phi tuyến, đặc biệt là các bài toán có các biến nhận các giá trị liên tục cũng như nguyên. Trong trường hợp tất cả các hàm mục tiêu cũng như ràng buộc đều là các hàm tuyến tính, chúng ta có BTQHTT. Trái với bài toán quy hoạch phi tuyến, BTQHTT có thể giải bằng một số phương pháp tối ưu quen biết (như phương pháp đơn hình cải biên, phương pháp hai pha, phương pháp điểm trong v.v…) và được sử dụng rộng rãi trong quy hoạch sử dụng đất cũng như nhiều lĩnh vực của kinh tế và quản trị kinh doanh nông nghiệp. Đặc biệt, khi các ràng buộc đều cho ở dạng bất đẳng thức với dấu ≤ thì ta có mô hình tối ưu (quy hoạch tuyến tính) một mục tiêu sau: Min CX với ràng buộc X ∈ D , trong đó: C là véc tơ ∈ Rn D = { X ∈ Rn : AX ≤ B, X ≥ 0 } với A là ma trận cấp m × n và B ∈ Rm 1.2. Các ví dụ minh hoạ bài toán tối ưu một mục tiêu Bài toán quy hoạch sử dụng đất (Mô hình tối ưu tuyến tính một mục tiêu giải bài toán quy hoạch sử dụng đất trên địa bàn xã Đông Dư, huyện Gia Lâm, tỉnh Hà Nội) Chúng ta xét mô hình tối ưu một mục tiêu với mục tiêu cần cực đại hoá là hiệu quả kinh tế. Để thiết lập mô hình, trước hết chọn các biến quyết định. Dựa vào kết quả các dữ liệu đã thu được, ta chọn các biến quyết định như sau: xj với j = 1, 2, …, 18 là diện tích các loại cây trồng ( theo thứ tự là: lúa xuân, lúa mùa, ngô xuân, ngô đông, ngô bao tử đông, lạc xuân, đậu xanh xuân, đậu tương đông đất chuyên màu, đậu tương đông đất ba vụ, dưa chuột xuân, dưa chuột bao tử, mướp đắng xuân, rau mùi tàu, rau gia vị, đậu cô ve đông, ớt xuân, cà chua xuân, cà chua đông), x19 là diện tích ao hồ thả cáao cá, xj với j = 20, …, 24 là số đầu vật nuôi trong năm (trâu, bò, lợn, gia cầm). x24 là số công lao động thuê ngoài, x25 là lượng tiền vốn vay ngân hàng. Lúc đó chúng ta có bài toán tối ưu tuyến tính một mục tiêu với 33 ràng buộc (chưa kể điều kiện không âm của các biến) như sau: Hiệu quả kinh tế: f(X) = 4306,14 x1 + 4168,73 x2 + 3115,21 x3 + 3013,11 x4 + 4158,68 x5+ 4860,91 x6 + 4295,31 x7 + 3706,11 x8 + 3788,25 x9+ 12747,31 x10+ 12752,96 x11 + 12064,81 x12 + 79228,88 x13 + 35961,31 x14 + 10823,91 x15+ 7950,16 x16 + 7928,06 x17 +5738, 46 x18 + 11129,50 x19 + 429,00 x20 + 674,00 x21+ 219,50 x22+ 11,10 x23– 15,50 x24 – 0,12 x25 → Max Với các ràng buộc sau đây : 4 x1 ≤ 80,88; x2 ≤ 75,78; x3 ≤ 64,89; 64,89; x7 ≤ 64,89; x8 ≤ 16,50; x9 ≤ 45,30; 6,80; x13 ≤ 13,70; x14 ≤ 14,50; x15 ≤ 4,80; 10,20; x19 ≤ 33,11; x20 ≤ 40,00; x21 ≤ 180,00; x4 ≤ 64,89; x5 ≤ 10,50; x6 ≤ x10 ≤ 5,50; x11 ≤ 8,5; x12 ≤ x16 ≤ 4,50; x17 ≤ 4,20; x18 ≤ x22 ≤ 4280; x23 ≤ 18800; x5 + x9 + x11 + x13 + x18 ≤ 45,30; x3 + x6 + x7 + x10 + x 12 + x16 + x17 ≤ 64,89; x4 + x8 + x14+ x15 ≤ 64,89; x1 + x13 ≤ 80,88; x2 + x13 ≤ 75,88; 205,5x1 + 150x3 + 75,75x4 + 75x5 + 225,5x6 + 221,5x7 + 102,7x8+ 100,75x9 +360 x10 +140x11 + 385x 12 + 1833,6x13 + 1446,3x14+210,25 x15 + 410,5x16 +360,5 x17 + 176x18 + 67x19 +20x20 + 16x21 + 9x22 + 0,3x23 - x24 ≤ 226149,00; 201,5x2 + 150x3 + 75,25x4 + 102,7x8+ 100,75x9 + 140x11 + 2475,4x13 + 1446,3x14+ 210,25x15 + 176x18 + 58x19 + 16x20 + 12x21 + 7x22 + 0,2x23 - x24 ≤ 152190,00; 2871,89x1 +2691,89 x2 + 2243,62x3 + 2243,66x4 + 3630,89x5 + 4780,06x6 + 2229,11x7 + 2401,41x8+ 2326,88x9 + 16440,61x10 + 16058,39x11 +15960,61x 12 + 68494,59x13 + 23146,11x14+ 13676,26x15 +6061,76x16 + 11083,11x17 + 10391,89x18 + 18058x19 + 1223x20 + 1098,5x21 + 624,5x22 + 12x23 - x24 ≤ 3881500; + 3,5x11 + 4x 12 + 12,1x13 + 3,5x5 + 8x6 + 3,5x7 +4,1x8+ 3,5x9 + 4,16x10 14,4x14+ 3,42x15 + 11,58x16 + 8x17 + 7,5x18 -3 x20 –2x21 - 0,95x22 – 0,0052x23 ≤ 0; 5,1x1 + 4,96x2 + 3,85x3 + 3,8x4 ≥ 921,25; Điều kiện không âm của các biến: ∀xj ≥ 0 ( j = 1, 2, …, 25). Bằng phần mềm thương phẩm thích hợp có sẵn Lingo hay sử dụng Solver của Excel (xem chương II) có thể tìm được phương án tối ưu của bài toán trên như sau: x1=67,18, x2=62,08, x3=25,32, x4=45,59, x5=10,50, x6=3,37, x9=2,40, x10=6,50, x11=8,50, x12=6,50, x13=13,70, x14=14,50, x15=4,80, x16=4,50, x17=4,20, x18=10,20, x19=33,11, x20=40,00, x21=180, x22=4280, x23=18800, x25=230701010,78. Hiệu quả kinh tế cực đại đạt được là 4270,36. Bài toán tối ưu hoá giá trị sản xuất (Mô hình tối ưu phi tuyến một mục tiêu giải bài toán tối ưu hoá giá trị sản xuất trên một héc ta nuôi cá tại huyện Văn Giang, tỉnh Hưng Yên) Sử dụng số liệu điều tra 112 hộ nuôi cá vùng đồng trong đê thuộc 4 xã Văn Giang, Hưng Yên, chúng tôi chạy mô hình hồi quy tương quan trong Excel và nhận được kết quả hàm sản xuất Cobb – Douglas như sau (cần cực đại hoá): Z = f(X) = 19,375 x10,236 x20,104 x30,096 x40,056 x50,056 e0,168 x6 e0,066 x7 →Max trong đó: z : Giá trị sản xuất bình quân triệu/ ha/năm (GO), x1 : Chi phí giống bình quân 1 ha 1 năm (tr/ ha), x2 : Chi phí thức ăn bình quân 1 ha 1 năm (tr/ ha), 5 x3 : Chi phí lao động bình quân 1 ha 1 năm (tr/ ha), x4 : Chi phí khấu hao và thuê đất bình quân 1 ha 1 năm (tr/ ha), x5 : Các chi phí khác bình quân 1 ha 1 năm (tr/ ha), x6 , x7: Biến giả định về hình thức nuôi, x6 = 1 đối với nuôi chuyên canh, x6 = 0 đối với nuôi tổng hợp, x7 = 1 với hình thức nuôi 1 loại cá chính kết hợp với các loại cá khác, x7 = 0 với hình thức nuôi 2 loại cá chính kết hợp với các loại cá khác. Với từng mức đầu tư/ tổng chi phí TC ta có các ràng buộc: - Với mức đầu tư dưới 40 tr đ/ ha: TC < 40 40 ≤ TC < 50 - Với mức đầu tư 40 - 50 tr đ/ ha: - Với mức đầu tư 50 – 60 tr đ/ ha: 50 ≤ TC < 60 - Với mức đầu tư 60 - 70 tr đ/ ha: 60 ≤ TC < 70 - Với mức đầu tư trên 70 tr đ/ ha: TC ≥ 70 trong đó: x1 + x2 + x3 + x4 + x5 = TC . Với hình thức nuôi ta có: x6+ x7 = 1 (x6 , x7 chỉ nhận các giá trị 0 hoặc 1). Trên đây là bài toán tối ưu phi tuyến, với 5 biến liên tục và 2 biến nguyên. Sử dụng phần mềm RST2ANU (xemchương III) để giải bài toán tối ưu phi tuyến toàn cục hỗn hợp nguyên đã thiết lập trên đây ta có kết quả trong bảng I.1. Bảng I.1. Kết quả cơ cấu đầu tư tối ưu vùng đồng Đầu tư < 40 40 – 50 50 – 60 (tr/ha) x1 35 – 45% 40 – 45% 40 – 45% x2 15 – 20% 17 – 25% 17 – 23% x3 15 – 20% 15 – 20% 15 – 20% x4 10 – 15% 7 – 15% 8 – 15% X5 10 – 15% 10 – 15% 10 - 15% GO (tr/ ha) < 78,1 78,1 – 88,3 88,3 – 97,5 NI (tr/ ha) 38,1-38,3 38,3-37,5 60 – 70 > 70 35 – 45% 15 – 20% 16- 19% 9 – 13% 9 - 15% 97,5– 106 37,5-36 35 – 40% 18 – 25% 17 – 23% 10 – 15% 10 - 15% > 106 - Việc thực hiện cơ cấu đầu tư tối ưu làm giá trị sản xuất (GO) cũng như thu nhập ròng (NI = GO - TC) ở từng mức đầu tư tăng lên rõ rệt so với thực tế sản xuất tại địa phương. Đặc biệt, mức đầu tư 50 tr/ha cho ta thu nhập hỗn hợp cao nhất 38,3 tr/ha, lớn hơn 8 tr/ha so với hiện tại không áp dụng cơ cấu đầu tư tối ưu cũng như hình thức nuôi thích hợp. Tại mức đầu tư này, cơ cấu đầu tư tối ưu là x1 từ 19,6 – 21,5 triệu (39,2 – 42,2%); x2 từ 8,6 - 9,8 triệu (17,2 – 19,6%); x3 từ 8,6 – 9,9 triệu ( 17,2 – 19,8%); x4 từ 4,7 – 6,4 triệu (9,4 – 12,8%); x5 từ 4,9 – 6,3 triệu (9,8 –12,6%) với hình thức nuôi chuyên canh (x6=1). 6 Kết quả áp dụng phần mềm RST2ANU (xem chương III) tại mức đầu tư 50 triệu đồng/ha cho phương án tối ưu sau: zmax=88,360733với x1=21,498072, x2=9,528987, x3=8,758034, x4=5,138906, x5=5,076000, x6=1,000000, x7=0,000000. Bài toán tối ưu thông số sàng phân loại (Mô hình tối ưu phi tuyến một mục tiêu giải quyết vấn đề tính toán một số thông số hình học và động học của cơ cấu sàng phân loại dao động) Trong ví dụ này chúng tôi chỉ xin nêu vắn tắt một ứng dụng của mô hình tối ưu phi tuyến một mục tiêu trong việc tìm nghiệm của hệ phương trình phi tuyến sau phát sinh trong việc tính toán một số thông số hình học và động học của cơ cấu sàng phân loại dao động (cần chú ý rằng nhiều phương pháp tính toán thông dụng khác của giải tích số đã tỏ ra không hiệu quả): r cosϕ1 + l cosϕ2 + l’’3 cosϕ3 + l4 cosϕ4 – xC1 = 0; r sinϕ1 + l sinϕ2 + l’’3 sinϕ3 + l4 sinϕ4 – yC1 = 0; r cosϕ1 + l cosϕ2 + l’3 cos(ϕ3 - α)+ l5 cosϕ5 – xD1 = 0; r sinϕ1 + l sinϕ2 + l’3 sin(ϕ3 - α)+ l5 sinϕ5 – yD1 = 0. Trong hệ phi tuyến trên các thông số đã biết là: r = 0,05m; l=0,30m; l’’3 = 0,15m; l’3 = 1,075m; l3 = 1,025m; l4 = 0,50m; l5 = 0,40m; xC1 = 0,365m; yC1 = 0,635m; xD1 = 1,365m; yD1 = 0,635m; α = π/8. Để sử dụng phần mềm tính toán tối ưu phi tuyến RST2ANU giải hệ phương trình phi tuyến cho ϕ = kπ/8 (k=0,…, 9), trước hết chúng ta cần thiết lập cực tiểu hoá hàm mục tiêu sau: z = (r cosϕ1 + l cosϕ2 + l’’3 cosϕ3 + l4 cosϕ4 – xC1)2 + (r sinϕ1 + l sinϕ2 + l’’3 sinϕ3 + l4 sinϕ4 – yC1)2+ (r cosϕ1 + l cosϕ2 + l’3cos(ϕ3 - α)+ l5 cosϕ5 – xD1)2 + (r sinϕ1 + l sinϕ2 + l’3sin(ϕ3 - α)+ l5sinϕ5 – yD1)2 Æ Min Kết quả được cho trong bảng I.2 với zmin = 0. Bảng I.2. Kết quả tính toán giá trị các thông số của sàng phân loại ϕ1 ∈ [0,2π] ϕ2 ∈ [0,π] ϕ3 ∈ [0,π] ϕ4 ∈ [0,π] ϕ5 ∈ [0,π] 0 0,226128 0,551311 1,783873 1,666775 0,199269 0,550518 1,784628 1,670250 π/18 0,170835 0,550590 1,782751 1,668853 2π/18 0,143343 0,550490 1,778826 1,663697 3π/18 0,112669 0,552073 1,770032 1,652171 4π/18 0,090986 0,551991 1,759350 1,639575 5π/18 0,066036 0,553576 1,745374 1,622823 6π/18 0,051284 0,554296 1,730174 1,602970 7π/18 0,039053 0,555262 1,713242 1,581813 8π/18 0,033773 0,556277 1,695605 1,560720 9π/18 7 2 MÔ HÌNH QUY HOẠCH ĐA MỤC TIÊU TUYẾN TÍNH VÀ PHI TUYẾN 2.1. Giới thiệu bài toán quy hoạch đa mục tiêu Trong các bài toán kỹ thuật, công nghệ, quản lý kinh tế, nông nghiệp v.v... nảy sinh từ thực tế, chúng ta thường phải xem xét đồng thời một lúc nhiều mục tiêu. Các mục tiêu này thường là khác về thứ nguyên, tức là chúng được đo bởi các đơn vị khác nhau. Những tình huống như vậy tạo ra các bài toán đa mục tiêu. Người kỹ sư / người ra quyết định lúc này cần phải tối ưu hoá (cực đại hoá hoặc cực tiểu hoá tuỳ theo tình huống thực tế) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả các mục tiêu đã đặt ra. Tuy nhiên, các mục tiêu này thường đối chọi cạnh tranh với nhau. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số mục tiêu khác. Vì vậy việc giải các bài toán tối ưu đa mục tiêu, tức là tìm ra một phương án khả thi tốt nhất theo một nghĩa nào đó, thực chất chính là một bài toán ra quyết định. Có thể thấy lại ở đây một lần nữa khẳng định " Tối ưu hoá chính là một công cụ định lượng chủ yếu nhất của quá trình ra quyết định". Hiện tại các tài liệu, sách chuyên khảo, tạp chí cập nhật về các lĩnh vực liên ngành giữa Toán, Vận trù học, Khoa học Quản lý, Tin học, Công nghệ, Kinh tế, Nông nghiệp... đề cập rất nhiều tới bài toán tối ưu đa mục tiêu. Vấn đề nghiên cứu cơ sở lý thuyết, thuật toán, lập mô hình, xây dựng hệ máy tính trợ giúp quyết định, và áp dụng các mô hình tối ưu đa mục tiêu cho các quá trình công nghệ, quản lý... là một vấn đề liên ngành được rất nhiều nhà nghiên cứu khoa học và kĩ sư thực hành quan tâm. Mô hình tối ưu đa mục tiêu có dạng sau đây: Min fj(X), X = (x1, x2, …, xn) j = 1, 2, …, p (p ≥2) với: (i) gj(X) ≤ 0, j = 1, 2, …, k, (ii) gj(X) = 0, j = k+1, k+2, …, m, Trong các bài toán thực tế có thể bổ sung các ràng buộc đạng: (iii) ai ≤ xi ≤ bi, i = 1, 2, …, n. Trong mô hình này, ta có p mục tiêu cần tối ưu hoá, các hệ số của các hàm mục tiêu và ràng buộc nói chung được giả sử là các giá trị thực xác định (cũng gọi là giá trị rõ). Trong trường hợp có ít nhất một trong các hàm mục tiêu hay các hàm ràng buộc là hàm phi tuyến, chúng ta có bài toán quy hoạch đa mục tiêu phi tuyến. Còn nếu tất cả các hàm mục tiêu và các hàm ràng buộc đều là hàm tuyến tính, chúng ta có mô hình quy hoạch tuyến tính đa mục tiêu với dạng chính tắc như sau: Min CX với ràng buộc X ∈ D , trong đó: C là ma trận cấp p×m D = { X ∈ Rn : AX ≤ B, X ≥ 0 } với A là ma trận cấp m x n và B ∈ Rm 8 2.2. Các khái niệm cơ bản của bài toán tối ưu đa mục tiêu Khái niệm then chốt trong tối ưu hoá đa mục tiêu là khái niệm phương án tối ưu Pareto. Định nghĩa 1: Một phương án tối ưu Pareto X* có tính chất sau đây: i) Trước hết nó phải thuộc vào miền các phương án khả thi của bài toán, tức là phải thoả mãn tất cả các ràng buộc: X* ∈ D. ii) Với mọi phương án khả thi khác X ∈ D mà có một mục tiêu nào đó tốt hơn (tồn tại chỉ số i sao cho fi(X) tốt hơn fi(X*)) thì cũng phải có ít nhất một mục tiêu khác xấu hơn (tồn tại j ≠ i sao cho fj(X) xấu hơn fj (X*)). Nói một cách khác, không tồn tại một phương án khả thi nào X ∈ D có thể trội hơn X trên tổng thể. * Định nghĩa 2: Giải bài toán tối ưu toàn cục đa mục tiêu là chọn ra từ tập hợp P các phương án tối ưu Pareto của bài toán một (một số) phương án tốt nhất theo một nghĩa nào đó dựa trên cơ cấu ưu tiên của người ra quyết định. Các phương án như vậy còn được gọi là phương án thoả dụng. Cách 1: Bằng một phương pháp tối ưu toán học thích hợp tìm ra tập hợp P tất cả các phương án tối ưu Pareto. Người ra quyết định sẽ đề ra cơ cấu ưu tiên của mình đối với tập P. Lúc này các phương pháp toán chẳng hạn như giải tích phân loại, các phương pháp lọc v.v… được áp dụng để tìm ra phương án tối ưu cho bài toán đa mục tiêu ban đầu. Cách 2: Việc tìm tập hợp P trong trường hợp các bài toán tối ưu phi tuyến là khá khó, nếu không nói là không thể tìm được. Vì vậy, so với cách 1, cách 2 sẽ tiến hành theo trình tự ngược lại. Trước hết người ra quyết định sẽ đề ra cơ cấu ưu tiên của mình. Dựa vào cơ cấu ưu tiên đó, các mục tiêu sẽ được tổ hợp vào một mục tiêu duy nhất, tiêu biểu cho hàm tổng tiện ích của bài toán. Bài toán tối ưu với hàm mục tiêu tổ hợp này sẽ được giải bằng một phương pháp tối ưu toán học thích hợp, để tìm ra một (hoặc một số) phương án tối ưu Pareto. Lúc này, người ra quyết định sẽ chọn ra trong số các phương án tối ưu Pareto đó một phương án tốt nhất. Chúng ta sẽ tiếp tục phân tích cách thứ 2. Rõ ràng, người ra quyết định không thể đề ra cơ cấu ưu tiên của mình một cách chính xác ngay từ đầu. Trong quá trình giải bài toán, trong mỗi bước lặp, sau khi xem xét lại cơ cấu ưu tiên đã đề ra, cũng như phương án tối ưu trung gian, người ra quyết định có thể dựa vào các thông tin đó để thay đổi lại cơ cấu ưu tiên của mình. Sau đó, quá trình giải lại được tiếp tục, cho tới khi một phương án tối ưu cuối cùng được đưa ra. Định nghĩa 3: Phương pháp giải bài toán tối ưu dựa trên sự trợ giúp của hệ máy tính, nhằm giúp người ra quyết định từng bước thay đổi các quyết định trung gian một cách thích hợp để đi tới một phương án tối ưu Pareto thoả mãn nhất, được gọi là phương pháp tương tác người - máy tính. Cho tới thời điểm hiện nay, hàng chục phương pháp giải tương tác bài toán tối ưu đa mục tiêu đã được đề cập tới trong các tạp chí chuyên ngành, và đa số chúng đều 9 có những ứng dụng rất thành công trong nhiều lĩnh vực. Một trong các lớp phương pháp quan trọng và khá thuận tiện cho người sử dụng là phương pháp tương tác người máy tính giải bài toán tối ưu đa mục tiêu với các yếu tố cấu thành sau: - Cơ cấu ưu tiên của người ra quyết định và hàm tổ hợp tương ứng. - Kiểu tương tác người - máy tính: các thông tin nào máy tính phải đưa ra lại trong các bước lặp trung gian, và cách thay đổi các thông số của cơ cấu ưu tiên từ phía người ra quyết định. - Kỹ thuật tối ưu toán học được xây dựng dựa trên lý thuyết tối ưu hoá nhằm tìm ra các phương án tối ưu Pareto cho các bài toán cần giải trong các bước lặp trung gian. 2.3. Các ví dụ minh hoạ bài toán quy hoạch đa mục tiêu Bài toán xác định cơ cấu cây trồng (Mô hình quy hoạch tuyến tính đa mục tiêu giải quyết vấn đề đánh giá hiệu quả sử dụng đất và xác định cơ cấu cây trồng xã Nhân Chính, huyện Lý Nhân, tỉnh Hà Nam) Trong nhiều mô hình quy hoạch đất, cũng như xây dựng cơ cấu cây trồng hợp lý các mô hình tối ưu được sử dụng rộng rãi. Ở nước ngoài, cũng như ở Việt Nam các phương pháp mô hình toán như vậy đã đem lại hiệu quả cao trong việc quản lý sử dụng đất cũng như việc bố trí một cơ cấu cây trồng thích hợp. Tuy nhiên đa số các mô hình tối ưu đó là mô hình một mục tiêu. Ngày nay, mô hình toán tối ưu nhiều mục tiêu được áp dụng trong nhiều lĩnh vực, đặc biệt trong lĩnh vực quản lý kinh tế, thiết kế chế tạo. Ví dụ này trình bày một cách áp dụng mô hình tối ưu nhiều mục tiêu cho bài toán xác định cơ cấu cây trồng - sử dụng đất trên địa bàn một xã vùng đồng bằng sông Hồng. Bài toán tối ưu nhiều mục tiêu nhằm đạt tới việc tối ưu hoá (cực đại hoá ) các mục tiêu sau : - Hiệu quả kinh tế của việc bố trí cơ cấu cây trồng và sử dụng đất. - Độ thích hợp tổng thể của cơ cấu cây trồng. - Hiệu quả môi trường. Bài toán có những điều kiện ràng buộc như sau về mặt sử dụng đất và cơ cấu cây trồng: Qua nghiên cứu về đất, toàn bộ diện tích canh tác được chia ra làm M loại. Còn kết quả nghiên cứu về trồng trọt cho phép áp dụng trên các loại đất đó N công thức luân canh, được đánh giá ở hai mức thích hợp. Độ thích hợp là 1 nếu công thức luân canh là thích hợp và là 2 nếu công thức luân canh ít thích hợp. Ký hiệu diện tích đất loại k là bk với k = 1, 2, ... M ; còn xijk (các biến quyết định) là diện tích luân canh công thức i (i = 1, 2, ..., N) với độ thích hợp j (j = 1, 2) trên đất loại k. Đặt aịjk là hệ số của xijk trong ràng buộc về diện tích đất loại k, ta sẽ có aijk = 0 nếu ta không áp dụng công thức luân canh i cho đất loại k; và aijk = 1 nếu công thức luân canh i được áp dụng cho đất loại k. Vậy các điều kiện ràng buộc của bài toán là : 10 2 ⎧ N ⎪ ∑ ∑ a i j k x i j k = b k ( k = 1, 2, ..., M ) ⎨ i =1 j =1 ⎪X ∀i, ∀j , ∀k ⎩ i jk ≥0 Ký hiệu cịjk là hệ số lợi nhuận trên một đơn vị diện tích của công thức luân canh i trên đất loại k với độ thích hợp j, thì mục tiêu về hiệu quả kinh tế được viết như sau : M N 2 k =1 i =1 j =1 ∑ ∑ ∑c a i j k xi j k → Max i jk (Mục tiêu 1 : Cực đại hoá lợi nhuận tổng) Để cực đại hoá độ thích hợp tổng thể, cần cực đại hoá tổng diện tích công thức luân canh có độ thích hợp loại 1. Vậy ta có mục tiêu sau : M N k =1 i =1 ∑∑ ai 1 k xi 1 k → Max (Mục tiêu 2 : Cực đại hoá độ thích hợp tổng thể) Một mục tiêu nữa cần xem xét, như trên đã nói, là hiệu quả môi trường của cơ cấu cây trồng - sử dụng đất. Đây là một vấn đề thực tiễn, tuy nhiên các đánh giá về môi trường rất khó định lượng. Để xác định hệ số môi trường cho các công thức luân canh, chúng tôi dùng phương pháp tổng hợp ý kiến chuyên gia. Mỗi chuyên gia sẽ đưa ra đánh giá của mình về hiệu quả môi trường cho các công thức luân canh ở các mức : Tốt, khá, trung bình, xấu. Sau đó các mức đó sẽ được định lượng bởi các số 100, 75, 50 và 25. Tỉ lệ % các ý kiến cho từng mức đánh giá sẽ được coi là xác suất thực nghiệm của các giá trị trên. Và do đó mỗi công thức luân canh thứ i sẽ ứng với một cặp số mi (kỳ vọng) và σi (độ lệch tiêu chuẩn) của phân phối thực nghiệm thu được. Thay cho các ~ = ( m - 3σ , m , m + 3σ) phân phối xác suất thực nghiệm, ta sẽ xem xét hệ số mờ m i i i i i của hiệu quả môi trường cho công thức luân canh thứ i. Do đó mục tiêu hiệu quả môi trường là mục tiêu mờ được viết như sau: M N 2 k =1 i =1 j =1 ∑ ∑ ∑ m~ a i i jk xi j k → Max (Mục tiêu 3 : Cực đại hoá hiệu quả môi trường) Tóm lại ta có mô hình tối ưu (mờ) ba mục tiêu sau đây : M N 2 k =1 i =1 j =1 M N k =1 i =1 M N 2 k =1 i =1 j =1 ∑ ∑ ∑c ∑∑ a i j k xi j k → Max i jk ai 1 k xi 1 k → Max ∑ ∑ ∑ m~ a i i jk xi j k → Max 11 2 ⎧ N Với các ràng buộc : ⎪ ∑ ∑ a i j k x i j k = bk ( k = 1, 2, ..., M ) ⎨ i =1 j =1 ⎪X ∀i , ∀ j , ∀ k ⎩ i jk ≥0 Việc xử lý mục tiêu mờ (mục tiêu cực đại hoá hiệu quả môi trường) được tiến hành bằng cách cực đaị hoá hiệu quả môi trường với hệ số rõ mi và có thể kèm thêm một ràng buộc bổ sung : M N 2 k =1 i =1 j =1 ∑ ∑ ∑ (m i − ε i ) a i j k xi j k ≥ e Ở đây εi được tuỳ ý chọn thoả mãn điều kiện : 0 < εi < 3σi . Thông thường ta chọn εi = 90% × 3σi hay εi = 2,7 σi. Còn số e là một số được lựa chọn thích hợp từ những thông tin có thể khai thác từ bài toán trên (chẳng hạn từ thông tin của bảng payoff), thường gọi là ngưỡng tối thiểu có thể chấp nhận của mục tiêu. Mô hình tối ưu (mờ) ba mục tiêu chính là một mô hình ra quyết định nhiều mục tiêu, và được giải bằng phương pháp đối thoại người ra quyết định - máy tính, nhằm giúp người ra quyết định từng bước tìm hiểu và thích nghi với các thông tin nội tại của mô hình, để cuối cùng đi tới một lời thoả mãn nhất. Các mục tiêu của mô hình được chuyển sang các mục tiêu mờ phản ánh độ thoả dụng của người ra quyết định. Đây là một cách làm rất hợp lý, bởi vì các đơn vị đo khác nhau của các mục tiêu được chuyển vào đơn vị thống nhất đo độ thoả dụng của người ra quyết định. Đây cũng là một lợi thế của tối ưu mờ (Fuzzy Optimization) bên cạnh rất nhiều ưu điểm khác. Số liệu thực tế qua khảo sát cơ cấu cây trồng, sử dụng đất ở địa phương Qua khảo sát thực tế các số liệu về các mặt sau được thu thập: - Hiệu quả kinh tế của một số công thức luân canh (bảng I.3). - Bố trí cơ cấu cây trồng theo các đơn vị đất (bảng I.4). - Số liệu về 15 loại đơn vị đất với các đặc tính đã được khảo sát (bảng I.5). - Tổng hợp các phiếu đánh giá hiệu quả môi trường một số công thức luân canh áp dụng cho vùng đồng bằng sông Hồng (bảng I.6). Bảng I.3. Hiệu quả kinh tế một số công thức trồng trọt luân canh Công thức Giá trị SX Năng suất Chi phí Yêu cầu lao Giá trị trồng trọt (ngànđ/ha) (tạ/ha) trung gian động tăng thêm (ngàn đ) (công/ha) (ngàn/ha) I.Bí xanh 36634 457,92 9431 730 27203 Cà chua 39000 65,00 5879 554 33121 Su hào 16064 200,80 4109 517 11955 Tổng 91698 19419 1801 72279 II.Bí xanh 36634 457,92 9431 730 27203 Cà chua 39000 65,00 5879 554 33121 Bắp cải 15050 215,00 4173 462 10877 Tổng 90684 19483 1746 71201 III.Bí xanh 36634 457,92 9431 730 27203 Bí xanh 31948 399,35 10056 758 21892 12 Bắp cải Tổng IV. L.xuân TQ L.mùa sớm Su hào Su hào Tổng V. L.xuân TQ L.mùa TQ Hành Tây Tổng VI. L.xuân TQ Lúa mùa Dưa chuột Tổng VII. L.xuân TQ L.mùa TQ Khoai tây Tổng VIII. Cà chua Lúa mùa Bắp cải Tổng IX. Lúa xuân Lúa mùa Tổng X. Bí xanh Lúa mùa Bắp cải Tổng XI. Bí xanh Lúa mùa Khoai tây Tổng 15050 83632 11223 8796 16060 14898 66,00 43,98 146,00 186,23 4173 23660 3557 3601 4048 4837 462 1950 310 277 59972 7666 5195 12012 10061 50987 11223 11700 25178 66,00 65,00 209,82 16043 3557 3468 7201 1319 310 310 695 34934 7666 8232 17977 48101 11223 11700 10139 66,00 65,00 207,79 14226 3557 3468 7737 1315 310 310 450 33875 7666 8232 2402 66,00 65,00 169,34 14762 3557 3468 6213 1070 310 310 425 18300 7666 8232 19188 13238 5879 3468 4173 13520 3557 3468 7025 9431 3468 4173 17072 9431 3468 6213 19112 1045 554 310 462 1326 310 310 620 310 310 462 1082 310 310 425 1465 35086 4621 8232 10877 23730 7666 8232 15898 27203 8232 10877 46312 27203 8232 19188 54623 33062 11223 11700 25401 48324 10500 11700 15050 37250 11223 11700 22923 36634 11700 15050 63384 36634 11700 25401 73735 215,00 105,00 65,00 215,00 66,00 65,00 66,00 65.00 215,00 457,92 65,00 169,34 Bảng I.4. Bố trí cơ cấu cây trồng theo các đơn vị đất 1. (92,87 ha) VII. Lúa xuân - Lúa mùa - Khoai tây (2) VIII. Cà chua - Lúa mùa - Bắp cải (1) X. Bí xanh - Lúa mùa - Bắp cải (1) 2 (27,62) X. Bí xanh - Lúa mùa - Bắp cải (2) I. Bí xanh - Cà chua - Su hào (1) III. Bí xanh - Bí xanh - Bắp cải (1) 3, 4, 13, 14 (41,52) II. Bí xanh - Cà chua - Bắp cải (1) I. Bí xanh - Cà chua - Su hào (1) XI. Bí xanh - Lúa mùa - Khoai tây (2) 13 5, 6, 7 (163,15 ha) 8, 15 (16,49) IX. Lúa xuân - Lúa mùa - ải (2) VII. Lúa xuân - Lúa mùa - Khoai tây (2) V. Lúa xuân - Lúa mùa - Hành tây (2) X. Bí xanh - Lúa mùa - Bắp cải (1) 9, 10, 11 (85,02ha) VII. Lúa xuân - Lúa mùa - Khoai tây (1) V. Lúa xuân - Lùa mùa - Hành tây (1) IV. Lúa xuân-Lúa mùa-Su hào-Su hào (2) 12 (48,49) III. Bí xanh - Bí xanh - Bắp cải (1) X. Bí xanh - Lúa mùa - Bắp cải (2) Ghi chú : (1) Thích hợp (2) Kém thích hợp Bảng I.5. Diện tích đơn vị đất đai 1 92,87 ha 9 43,88 ha 2 27,62 10 8,85 3 5,42 11 32,29 4 12,02 12 48,49 5 99,89 13 14,03 6 27,96 14 10,05 7 35,30 15 8,41 8 8,08 Bảng I.6. Tổng hợp phiếu đánh giá hiệu quả môi trường của một số công thức luân canh áp dụng cho vùng đồng bằng sông Hồng Công thức Công thức Mức độ luân canh Tốt (%) Khá (%) T.B (%) Xấu (%) 1 Bí xanh-Cà chua-Su hào 45,4 27,3 27,3 2 Bí xanh-Cà chua-Bắp cải 45,4 18,2 36,4 3 Bí xanh-Bí xanh-Bắp cải 36,4 36,4 27,2 4 LX-LM sớm-Su hào-Su hào 72,7 18,2 9,1 5 Lúa xuân-LM sớm-Hành tây 72,7 18,2 9,1 6 Lúa xuân-LM sớm-Dưa chuột 54,5 27,3 18,2 7 Lúa xuân-Lúa mùa-Khoai tây 81,8 18,2 8 Cà chua-Lúa mùa sớm-Bắp cải 27,3 45,4 27,3 9 Lúa xuân-Lúa mùa 45,4 36,4 18,2 10 Bí xanh-Lúa mùa sớm-Bắp cải 27,3 54,5 18,2 11 Bí xanh-LM sớm-Khoai tây 27,3 45,4 27,3 Thiết lập mô hình đa mục tiêu xác định cơ cấu cây trồng Để có thể chọn những công thức trồng trọt phù hợp với điều kiện đất đai, đồng thời đảm bảo đạt hiệu quả mong muốn, cần xét ba mục tiêu sau: i) Hiệu quả kinh tế, ii) Độ thích hợp đất đai, iii) Hiệu quả môi trường. Tiến hành thiết lập mô hình, trước hết chọn các biến quyết định. Dựa vào kết quả các dữ liệu đã thu được, đặt tên các biến như sau: x1 (x112): diện tích trồng các loại cây công thức 1, ở độ thích hợp đất (1) trên khu đất (2) x2 (x113): diện tích trồng các loại cây công thức 1, ở độ thích hợp đất (1) trên khu đất (3) x3 (x213): diện tích trồng các loại cây công thức 2, ở độ thích hợp đất (1) trên khu đất (3) 14 x4 (x312): diện tích trồng các loại cây công thức 3, ở độ thích hợp đất (1) trên khu đất (2) x5 (x317): diện tích trồng các loại cây công thức 3, ở độ thích hợp đất (1) trên khu đất (7) x6 (x516): diện tích trồng các loại cây công thức 5, ở độ thích hợp đất (1) trên khu đất (6) x7 (x716): diện tích trồng các loại cây công thức 7, ở độ thích hợp đất (1) trên khu đất (6) x8 (x811): diện tích trồng các loại cây công thức 8, ở độ thích hợp đất (1) trên khu đất (1) x9 (x914): diện tích trồng các loại cây công thức 9, ở độ thích hợp đất (1) trên khu đất (4) x10 (x10,11): diện tích trồng các loại cây công thức 10, ở độ thích hợp đất (1) trên khu đất (1) x11 (x10,15): diện tích trồng các loại cây công thức 10, ở độ thích hợp đất (1) trên khu đất (5) x12 (x426): diện tích trồng các loại cây công thức 4, ở độ thích hợp đất (2) trên khu đất (6) x13 (x525): diện tích trồng các loại cây công thức 5, ở độ thích hợp đất (2) trên khu đất (5) x14 (x721): diện tích trồng các loại cây công thức 7, ở độ thích hợp đất (2) trên khu đất (1) x15 (x725): diện tích trồng các loại cây công thức 7, ở độ thích hợp đất (2) trên khu đất (5) x16 (x10,22): diện tích trồng các loại cây công thức 10, ở độ thích hợp đất (2) trên khu đất (2) x17 (x10,27): diện tích trồng các loại cây công thức 10, ở độ thích hợp đất (2) trên khu đất (7) x18 (x11,23): diện tích trồng các loại cây công thức 1, ở độ thích hợp đất (2) trên khu đất (3). Với các số liệu thực tế thu được qua khảo sát, chúng tôi có mô hình tối ưu (mờ) sau đây : Mục tiêu 1: z1 = 72279(x112 + x113) + 71201x213 + 59972 (x312 + x317) + 34934 x426 + 33875 (x516 + x525 ) + 35086 (x716 + x721 + x725) + 23730 x811 + 15898 x914 + 46312 (x10, 11 + x10, 15 + x10, 22 + x10, 27) + 54623 x11, 23 → Max Mục tiêu 2 : z2 = x112 + x113 + x213 + x312 + x317 + x516 + x716 + x811 + x914 + x10, 11 + x10, 15 → Max ~ (x + x ) + m ~ (x + x ) + m ~ x + m ~ (x ~ x + m Mục tiêu 3 : z = m 3 1 112 113 2 213 3 312 317 4 426 5 516 ~ (x + x + x ) + m ~ x + m ~ x +m ~ (x + x525 ) + m 716 721 725 10, 11 + x10, 15 + x10, 22 + x10, 27) 7 8 811 9 914 10 ~ x + m 11 11, 23 → Max Với các ràng buộc sau đây : x721 + x811 + x10, 11 = 92,87 (ha); x112 + x312 + x10, 22 = 27,62; x113 + x213 + x11, 23 = 41,52; x914 = 163,15; x525 + x725 + x10, 25 = 16,49; x426 + x516 + x716 = 85,02; x317 + x10, 27 = 48,49; xịk ≥ 0 ∀i, ∀j , ∀k. ~ được xác định như sau : Ở mô hình trên m 1 Trước hết ta tính m1 = 27,3% × 25 + 27,3% × 50 + 45,4% × 75 σ1 = 27,3% × 25 2 + 27,3% × 50 2 + 45,4% × 75 2 − m 12 ~ = (m - 3σ , m , m + 3σ ). Tương tự có thể tính được các hệ Sau đó có : m 1 1 1 1 1 1 số mờ khác. Do đó mục tiêu 3 được được thay bởi: Mục tiêu 3 : z3 = 54,525(x112 + x113) + 52,25x213 + 52,3(x312 + x317) + 90,9 x426 + 84,075(x516 + x525 ) + 95,375(x716 + x721 + x725) + 75x811 + 81,8x914 + 77,275(x10, 11 + x10, 15 + x10, 22 + x10, 27) + 77,275x11, 23 → Max 15 Các bước giải bài toán tối ưu cơ cấu cây trồng Tiến hành giải bài toán trên bằng phần mềm MULTIOPT (xem chương IV) theo các bước sau: Trước hết, nhằm giúp người ra quyết định xác định hàm thoả dụng, bài toán tối ưu cho từng mục tiêu riêng rẽ (như vậy có ba bài toán tối ưu một mục tiêu) sẽ ~ đối được giải quyết. Riêng mục tiêu về hiệu quả môi trường sẽ lấy mi thay thế cho m i với mọi công thức canh tác i. Màn hình máy tính sẽ thông báo về ba lời giải tối ưu cho ba bài toán, ký hiệu là X , X , và X3. 1 2 X1 : x112 = 27,62; x113 = 41,52 ; x312 = 48,49 ; x716 = 85,02 ; x914 = 163,15; x10, 11 = 92,87 và x10, 15 = 16,49 (các biến khác có giá trị bằng 0). X2 : x112 = 27,62 ; x113 = 41,52 ; x317 = 48,49 ; x516 = 85,02 ; x811 = 92,87; x914 = 163,15; x10, 15 = 16,49 (các biến khác có giá trị bằng 0). X3 : x716 = 85,02 ; x721 = 92,87 ; x725 = 16,49 ; x914 = 163,15 ; x10, 22 = 27,62; x10, 23 = 48,49 và x11, 23 = 41,52 (các biến khác có giá trị bằng 0). Lúc này ta có thông tin pay- off cho ở bảng I.7. Bảng I.7. Thông tin pay- off Phương án Mục tiêu 1 Mục tiêu 2 Mục tiêu 3 X1 18544625,75 475,16 36218,401 X2 16344476,19 475,16 35039,98 3 X 15206528,66 248,17 40985,02 Dựa trên các thông tin pay-off trên, máy tính sẽ giúp người ra quyết định xây dựng được các hàm thoả dụng cho các mục tiêu đã đặt ra. Các hàm đó còn gọi là các hàm liên thuộc mờ (fuzzy membership functions). Chẳng hạn hàm thoả dụng cho mục tiêu hiệu quả kinh tế là : Z1 − Z1w → Max μ1 (z1) = B Z1 − Z1w Với z1B (tốt nhất) = 18544625,75 z1w (xấu nhất) = 15206528,66. Sau khi có các hàm thoả dụng, hàm liên hợp (aggregation function) được thiết lập cho các hàm thoả dụng đó để có mục tiêu sau : w1 μ1(z1) + w2 μ2 (z2) + w3 μ3 (z3) → Max Với w1 + w2 + w3 = 1, 0 ≤ w1 , w2 , w3 ≤ 1 Các hệ số w1 , w2 , w3 được gọi là các trọng số phản ánh tầm quan trọng của từng hàm thoả dụng thành phần trong hàm liên hợp. Bằng cách thay đổi giá trị w1 , w2 , w3, người ra quyết định có thể tìm ra được các phương án thoả dụng thích hợp (có tính chất tối ưu Pareto yếu). Xem xét các phương án đó cùng với độ thoả dụng đạt được cho từng mục tiêu (có thể dựa vào phương pháp ra quyết định tập thể - group decision making) người ra quyết định có thể đi tới một quyết định hợp lý về cơ cấu cây trồng - sử dụng đất như trong bảng I.8. 16 Đơn vị đất 1 2 3; 4; 14; 13 5; 6; 7 8; 15 9; 10; 11 12 Bảng I.8. Kết quả lựa chọn phương án tối ưu Khu Diện Phương án 1 Phương án 2 Phương án 3 vực tích (ha) 1 92.,8 Bí xanh Cà chua Lúa xuân 7 (xuân) – (đông) – LM – (TQ) - LM LM – bắp bắp cải (TQ) – khoai cải tây 2 27,6 Bí xanh Bí xanh Bí xanh 2 (xuân) – cà (xuân) – cà (xuân) – LM chua (hè chua (hè thu)- – bắp cải thu)- su hào su hào 3 41,5 Bí xanh Bí xanh Bí xanh 2 (xuân) – cà (xuân) – cà (xuân) – LM chua (hè chua (hè thu)- – khoai tây thu)- su hào su hào 4 163, Lúa xuân – Lúa xuân – Lúa xuân – 15 lúa mùa lúa mùa lúa mùa 5 16,4 Bí xanh Bí xanh Lúa xuân 9 (xuân) – (xuân) – LM – (TQ) - LM LM – bắp bắp cải (TQ)– khoai cải tây 6 85,0 2 Lúa xuân (TQ) - LM (TQ) – khoai tây 7 48,4 Bí xanh 9 (xuân)- bí xanh (mùa)bắp cải Trong bảng I.8, chúng ta có: Bí xanh (xuân) – LM – bắp cải Bí xanh (xuân) - bí xanh (mùa)bắp cải Phương chọn án Bí xanh (xuân) – LM – bắp cải Bí xanh (xuân) – cà chua (hè thu)- su hào Bí xanh (xuân) – cà chua (hè thu)- su hào Lúa xuân – lúa mùa Bí xanh (xuân) – LM – bắp cải (6.51234 ha) LX TQ) – LM (TQ)– khoai tây (9.97766 ha) Lúa xuân Lúa xuân (TQ) (TQ) - LM - LM (TQ)– (TQ)– khoai khoai tây tây Bí xanh Bí xanh (xuân) – LM (xuân)- bí xanh – bắp cải mùa)- bắp cải Phương án 1: Các công thức trồng trọt cho hiệu quả kinh tế cao nhất. Phương án 2: Các công thức trồng trọt cho hiệu quả cao nhất về mức độ thích nghi đất đai. Phương án 3: Các công thức trồng trọt cho hiệu quả môi trường cao nhất . Phương án cho ở cột phương án chọn là phương án thoả dụng ứng bộ giá trị các trọng số: w1 = 0.4, w2 = 0.2, w3 = 0.4 khi sử dụng phần mềm MULTIOPT. Bài toán đánh giá hiệu quả sử dụng đất và lao động (Mô hình quy hoạch tuyến tính đa mục tiêu giải quyết vấn đề đánh giá hiệu quả sử dụng đất và lao động trên địa bàn xã Trâu Quỳ, huyện Gia Lâm, tỉnh Hà Nội) 17 Để quy hoạch sử dụng đất, đồng thời đảm bảo đạt hiệu quả môi trường, cần xem xét năm mục tiêu sau: i) Tổng lợi nhuận, ii) Hiệu quả sử dụng vốn, iii) Giá trị ngày công lao động, iv) Số công lao động, vi) Hiệu quả môi trường. Để tiến hành giải bài toán, trước hết phải chọn các biến quyết định. Dựa vào cơ cấu cây trồng xã năm 1999, các biến sau được lựa chọn: x1 : Diện tích trồng lúa xuân (ha), x2 : Diện tích trồng lúa mùa (ha), x3 : Diện tích trồng ngô (ha), x4 : Diện tích trồng đậu tương (ha), x5 : Diện tích trồng khoai tây (ha), x6 : Diện tích trồng rau (ha), x7 : Diện tích trồng mùi (ha), x8 : Diện tích trồng táo (ha), x9 : Diện tích trồng nhãn (ha), x10 : Diện tích trồng xoài (ha). Các mục tiêu cần cực đại hoá là: z1 = 4,48 x1 + 4,2 x2 + 2,59 x3 + 0,98 x4 + 5,8 x5 + 15,61 x6 + 29,67 x7 + 39,21 x8 + 116,58 x9 + 105,13 x10 z2 = 0,6205 x1 + 0,5915 x2 +0,465 x3 + 0,1583 x4 + 0,7065 x5 + 0,5864 x6 + 1,2996 x7 + 1,2735 x8 + 1,1726 x9 + 1,756 x10 z3 = 0,0217 x1 + 0,0206 x2 + 0,0154 x3 + 0,0045 x4 + 0,0248 x5 + 0,0109 x6 + 0,0241 x7 + 0,0349 x8 + 0,09 x9 + 0,0811 x10 z4 = 206 x1 + 204 x2 + 168 x3 + 216 x4 + 234 x5 + 1428 x6 + 1232 x7 + 1124 x8 + 1296 x9 + 1296 x10 z5 = 0,7 x1 + 0,778 x2 + 1,273 x3 + 1,75 x4 + x5 + 0,368 x6 + 0,875 x7 + 3 x8 + 3 x9 + 3 x10 Với các ràng buộc sau (về cơ cấu diện tích đất canh tác): x1≤ 189,6407; x2 ≤ 189,6407; x3 ≤ 17,4931; x4 ≤ 17,4931; x5 ≤17,4931; x6 ≤189,6407; x7 ≤ 17,4931; x8 ≤18; x9 ≤18; x10 ≤ 18. Diện tích trồng rau trên cả đất ba vụ và đất chuyên màu: x6 ≥ 26,4 Diện tích đất trồng cây vụ đông trên đất ba vụ: x3 + x4 + x5 + x6 + x7 = 43,8931 x10 Diện tích đất trồng các cây ăn quả trên đất trồng cây hàng năm khác: x8 + x9 + = 18 Điều kiện để có lợi nhuận là: 4,48 x1 + 4,2 x2 + 2,59 x3 + 0,98 x4 + 5,8 x5 + 15,61 x6 + 29,67 x7 + 39,21 x8 + 116,58 x9 + 105,13 x10 > 0 Điều kiện về sản lượng lương thực: Các cây lương thực của xã gồm lúa xuân, lúa mùa và ngô: 5,14 x1 + 4,98 x2 + 3,77 x3 ≥ 1700,5 Điều kiện không âm của bài toán: xi (i = 1, 2, …, 10) ≥ 0. Bảng I.9 cho phép so sánh kết quả sử dụng đất canh tác xã Trâu quỳ năm 1999 với các phương án tối ưu thu được khi áp dụng phần mềm MULTIOPT (xem chương IV ). 18 Bảng I.9. So sánh kết quả sử dụng đất canh tác STT 1 Các chỉ tiêu Kết quả thực tế Kết quả mô hình Lúa xuân 189,64 189,64( x1) Lúa mùa 189,64 189,64(x2) Ngô 2,53 0,00 0,82 0,00 0,91 0,00 27,73 26,40(x6) 12,4 17,49(x7) Táo 9,27 0,00 Nhãn 4,85 0,00 Xoài 3,88 18,00(x10) Diện Đậu tương tích các Khoai tây cây Rau trồng Mùi 2 Tổng thu nhập 8538,62 9364,92 3 Tổng chi phí 4750,00 4895,38 4 Tổng lợi nhuận 3788,47 4469,54(z1) 5 Hiệu quả sử dụng vốn 288,19 299,67(z2) 6 Tổng số công lao động 154462 160331(z3) 7 Giá trị ngày công lao động 9,74 10,19(z4) 8 Môi trường 360,72 359,31(z5) ( Giá trị các trọng số: w1= 0,1; w2 = 0,1; w3 = 0,2; w4 = 0,2; w5 = 0,4 ). Tối ưu hoá kết quả và hiệu quả kinh tế chăn nuôi cá(Mô hình quy hoạch phi tuyến đa mục tiêu giải quyết vấn đề tối ưu hoá kết quả và hiệu quả kinh tế chăn nuôi cá của các hộ nông dân nuôi cá tại huyện Văn Giang, tỉnh Hưng Yên) Việc các hộ nuôi cá quyết định nên sản xuất như thế nào, mức đầu tư bao nhiêu phụ thuộc chủ yếu vào những lợi thế và tiềm lực kinh tế của từng nông hộ. Những nông hộ có nhiều lao động dư thừa chú trọng đến thu nhập hỗn hợp hơn thu nhập ròng, còn những hộ có sẵn nguồn thức ăn tận dụng trong gia đình mà không mất tiền mua thì lại xem trọng giá trị sản xuất hơn. Chính vì vậy, cần không chỉ quan tâm đến giá trị sản xuất mà còn cần quan tâm cả đến thu nhập hỗn hợp và thu nhập ròng. Do đó, phải giải quyết bài toán tối ưu ba mục tiêu sau: i) Tối đa hoá giá trị sản xuất cá trên một ha (z1 → Max), 19