Các mô hình và phần mềm tối ưu hoá và ứng dụng trong nông nghiệp

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 1 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 2 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 k e , jd ~ 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 3 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) X = (x1, x2, …, xn) 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 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 ý 4 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 DX ∈ , 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 : 5 x1 ≤ 80,88; x2 ≤ 75,78; x3 ≤ 64,89; x4 ≤ 64,89; x5 ≤ 10,50; x6 ≤ 64,89; x7 ≤ 64,89; x8 ≤ 16,50; x9 ≤ 45,30; x10 ≤ 5,50; x11 ≤ 8,5; x12 ≤ 6,80; 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,00; 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,5x5 + 8x6 + 3,5x7 +4,1x8+ 3,5x9 + 4,16x10 + 3,5x11 + 4x 12 + 12,1x13 + 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), 6 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 - Với mức đầu tư 40 - 50 tr đ/ ha: 40 ≤ TC < 50 - 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ư (tr/ha) 70 x1 35 – 45% 40 – 45% 40 – 45% 35 – 45% 35 – 40% x2 15 – 20% 17 – 25% 17 – 23% 15 – 20% 18 – 25% x3 15 – 20% 15 – 20% 15 – 20% 16- 19% 17 – 23% x4 10 – 15% 7 – 15% 8 – 15% 9 – 13% 10 – 15% X5 10 – 15% 10 – 15% 10 - 15% 9 - 15% 10 - 15% GO (tr/ ha) 106 NI (tr/ ha) - 38,1-38,3 38,3-37,5 37,5-36 - 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). 7 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 π/18 0,199269 0,550518 1,784628 1,670250 2π/18 0,170835 0,550590 1,782751 1,668853 3π/18 0,143343 0,550490 1,778826 1,663697 4π/18 0,112669 0,552073 1,770032 1,652171 5π/18 0,090986 0,551991 1,759350 1,639575 6π/18 0,066036 0,553576 1,745374 1,622823 7π/18 0,051284 0,554296 1,730174 1,602970 8π/18 0,039053 0,555262 1,713242 1,581813 9π/18 0,033773 0,556277 1,695605 1,560720 8 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 DX ∈ , 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 9 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ế