Tài liệu Phương pháp điều khiển tối ưu để giảm tác động các loại hóa chất độc hại dùng trong trồng trọt

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN LÊ THỊ MINH TÂN PHƯƠNG PHÁP ĐIỀU KHIỂN TỐI ƯU ĐỂ GIẢM TÁC ĐỘNG CÁC LOẠI HÓA CHẤT ĐỘC HẠI DÙNG TRONG TRỒNG TRỌT Chuyên nghành: Khoa học máy tính M· sè: 60.48.01 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ HUY THẬP Thái Nguyên - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan các số liệu và kết quả nêu trong Luận văn 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. Trừ các phần tham khảo đã được nêu rõ trong Luận văn. Tác giả Lê Thị Minh Tân Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Trước tiên, em xin bày tỏ lòng kính trọng và biết ơn sâu sắc của mình tới thầy Lê Huy Thập – Tiến sỹ, Nghiên cứu viên chính Viện Công nghệ thông tin, người đã tận tình giúp đỡ em hoàn thành luận văn tốt nghiệp này. Em xin bày tỏ sự biết ơn của mình tới các thầy, cô trong Viện Công nghệ thông tin và Khoa Công nghệ thông tin – Đại học Thái Nguyên đã tận tình truyền đạt kiến thức, phương pháp khoa học và kinh nghiệm cho em trong suốt những năm học vừa qua. Em cũng xin cảm ơn người thân, bạn bè, đồng nghiệp, những người đã nhiệt tình ủng hộ, giúp đỡ, động viên em trong suốt thời gian tiến hành nghiên cứu và thực hiện luận văn. Trong luận văn chắc chắn còn nhiều thiếu sót, hạn chế, em rất mong nhận được sự chỉ bảo, góp ý của các thầy cô và các bạn để có thể sửa chữa, hoàn thiện trong thời gian tới. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i MỤC LỤC DANH MỤC CÁC TỪ VIẾT TẮT ............................................................... iii DANH MỤC CÁC BẢNG ............................................................................ iii MỞ ĐẦU ....................................................................................................... 1 1. Lý do chọn đề tài .................................................................................... 1 2. Mục tiêu nghiên cứu và tính cấp thiết của đề tài ..................................... 1 3. Phạm vi nghiên cứu và ứng dụng ............................................................ 1 4. Ý nghĩa khoa học .................................................................................... 2 5. Phƣơng pháp nghiên cứu ........................................................................ 2 6. Cấu trúc của luận văn ............................................................................. 2 CHƢƠNG 1. TỔNG QUAN VỀ TỐI ƢU ...................................................... 3 1.1. Giới thiệu về bài toán tối ƣu ................................................................ 3 1.2. Giới thiệu một số dạng bài toán tối ƣu ................................................. 3 1.2.1. Bài toán vận tải (BTVT) ............................................................... 5 1.2.1.1. Phát biểu bài toán ................................................................... 5 1.2.1.2. Sự tồn tại nghiệm tối ƣu ......................................................... 7 1.2.1.3. Tiêu chuẩn nhận biết phƣơng án cực biên .............................. 7 1.2.2. Bài toán cái túi ............................................................................ 10 1.2.2.1. Phát biểu bài toán ................................................................. 10 1.2.2.2. Thuật toán giải bài toán cái túi ............................................. 10 1.2.3. Ứng dụng vào nghành nông nghiệp ............................................ 11 1.2.4. Bài toán quy hoạch phi tuyến và nghiệm tối ƣu của nó ............... 13 1.2.4.1. Phát biểu bài toán ................................................................. 13 1.2.4.2. Nghiệm tối ƣu ...................................................................... 15 CHƢƠNG 2. CÁC PHƢƠNG PHÁP ĐIỀU KHIỂN TỐI ƢU ..................... 19 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii 2.1. Giới thiệu khái quát phƣơng pháp giải bài toán điều khiển tối ƣu bằng phƣơng pháp nhân tử Lagrange ................................................................ 19 2.1.1. Giới thiệu .................................................................................... 19 2.1.2. Bài toán thiết kế hệ thống nối đất chống sét trong các công trình xây dƣ̣ng ............................................................................................... 20 2.1.3. Bài toán xây dựng mạng cấp và phân phối nƣớc tối ƣu ............... 22 2.2. Giới thiệu khái quát phƣơng pháp quy hoạch động Belman ............... 25 2.2.1. Phƣơng pháp phƣơng trình truy toán và các nguyên tắc cơ bản của quy hoạch động .................................................................................... 25 2.2.1.1. Bài toán phân phối một chiều và phƣơng pháp phƣơng trình truy toán ........................................................................................... 25 2.2.1.2. Các nguyên tắc cơ bản của quy hoạch động ......................... 27 2.2.2. Quá trình nhiều giai đoạn và phƣơng trình hàm .......................... 28 2.2.2.1. Quá trình nhiều giai đoạn ..................................................... 28 2.2.2.2. Xây dựng phƣơng trình hàm ................................................ 30 2.2.3. Sơ đồ tính ................................................................................... 31 CHƢƠNG 3. BÀI TOÁN ĐIỀU KHIỂN TỐI ƢU ĐỂ GIẢM TÁC ĐỘNG CỦA CÁC LOẠI HÓA CHẤT ĐỘC HẠI DÙNG TRONG TRỒNG TRỌT 32 3.1. Các lý luận và giả thiết để xây dựng bài toán ..................................... 32 3.2. Phát biểu bài toán điều khiển tối ƣu ................................................... 33 3.2.1. Các ký hiệu và dẫn luận .............................................................. 33 3.2.2. Phát biểu bài toán điều khiển tối ƣu ............................................ 40 3.3. Giải bài toán điều khiển tối ƣu ........................................................... 41 3.4. Phân tích mối quan hệ giữa các tham số ............................................ 43 CÀI ĐẶT THỬ NGHIỆM ............................................................................ 50 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................... 53 TÀI LIỆU THAM KHẢO ............................................................................ 54 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Diễn giải QHTT Quy hoạch tuyến tính BTVT Bài toán vận tải QHTS Quy hoạch tham số QHĐ Quy hoạch động QHPT Quy hoạch phi tuyến QHRR Quy hoạch rời rạc QHN Quy hoạch nguyên QHĐMT Quy hoạch đa mục tiêu DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 3.1 Loại, số lƣợng và chỉ số độc hại của thuốc trừ sâu 34 3.2 Loại, số lƣợng và đặc tính phá hoại của các loại 36 sâu bệnh 3.3 Số lƣợng sâu bệnh đƣợc thống kê theo năm 36 3.4 Số lƣợng sâu bệnh đƣợc thống kê theo năm đã 37 đƣợc xử lý Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Đã có một số mô hình nói về quan hệ giữa phát triển kinh tế và môi trƣờng nhƣ: [2], [6], [7],… đƣợc in vào các năm 1973, 1991,…. Nhƣng tất cả các công trình đã công bố trên chƣa đề cập đến tác động của thiên dịch vào môi trƣờng. Dựa vào các kết quả nghiên cứu mô hình, chúng ta có thể kịp thời đƣa ra giải pháp cải tạo công nghệ trồng trọt, công nghệ sản xuất và chiến lƣợc sử dụng thuốc trừ sâu và các loại hoá chất độc hại khác đồng thời với việc bảo vệ, phát triển số lƣợng, chất lƣợng thiên dịch nhằm để giảm lƣợng tồn dƣ thuốc trừ sâu, tránh thảm họa tràn ngập các chất thải hoá học trong môi trƣờng sống nhƣ nƣớc ngầm, sông ngòi, kênh rạch và không khí,…do đó tôi tiến hành nghiên cứu đề tài: “Phƣơng pháp điều khiển tối ƣu để giảm tác động các loại hóa chất độc hại dùng trong trồng trọt” nhằm bƣớc đầu nghiên cứu hƣớng giải quyết các vấn đề nói trên. 2. Mục tiêu nghiên cứu và tính cấp thiết của đề tài Luận văn đƣa ra mô hình đánh giá dƣ lƣợng thuốc trừ sâu dựa trên các chỉ tiêu nhƣ: sự phát triển dân số, nhu cầu lƣơng thực, sự phát triển của thiên dịch, cải tiến công nghệ sản xuất để tìm ra chiến lƣợc giảm tối đa sử dụng thuốc trừ sâu tức là giảm tối đa tác hại vào môi trƣờng sống. 3. Phạm vi nghiên cứu và ứng dụng Dùng phƣơng pháp thống kê (đặc biệt là phƣơng pháp bình phƣơng bé nhất) để tìm các tham số là các tốc độ tăng trƣởng dân số và thiên dịch và hệ số phân hủy của các loại hóa chất. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Trên cơ sở các tham số thu đƣợc, chúng ta nghiên cứu bài toán điều khiển tối ƣu. Sử dụng phƣơng pháp nhân tử Lagrange để giải bài toán điều khiển tối ƣu đã đặt ra. Từ đó tìm ra phƣơng pháp cải tiến công nghệ và phát triển thiên dịch để đạt đƣợc mục tiêu của bài toán. 4. Ý nghĩa khoa học Kết hợp giữa phƣơng pháp thống kê và bài toán điều khiển tối ƣu với các kiến thức trồng trọt, môi trƣờng, thiên dịch,… để đƣa ra một mô hình điều khiển mới phục vụ cho công tác nghiên cứu môi trƣờng. 5. Phƣơng pháp nghiên cứu - Sử dụng phƣơng pháp thống kê để tìm ra các tham số nhƣ: hệ số tăng trƣởng của dân số, tăng trƣởng của thiên dịch, tốc độ phân hủy của chất thải,… - Sử dụng hai phƣơng pháp quy hoạch động và phƣơng pháp giải tích để giải bài toán điều khiển tối ƣu. 6. Cấu trúc của luận văn MỞ ĐẦU CHƢƠNG 1. TỔNG QUAN VỀ ĐIỀU KHIỂN TỐI ƢU. CHƢƠNG 2. CÁC PHƢƠNG PHÁP ĐIỀU KHIỂN TỐI ƢU. CHƢƠNG 3. BÀI TOÁN ĐIỀU KHIỂN TỐI ƢU ĐỂ GIẢM TÁC ĐỘNG CỦA CÁC LOẠI HÓA CHẤT ĐỘC HẠI DÙNG TRONG TRỒNG TRỌT. CÀI ĐẶT THỬ NGHIỆM. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN. TÀI LIỆU THAM KHẢO. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 CHƢƠNG 1. TỔNG QUAN VỀ TỐI ƢU 1.1. Giới thiệu về bài toán tối ƣu Bài toán tối ƣu hóa tổng quát đƣợc phát biểu nhƣ sau: Cực đại hóa (cực tiểu hóa) hàm: f(x)  max (min) (1.1) Với các điều kiện: gi(x)( , =,  ) bi, i = 1, m (1.2) x  X  Rn (1.3) Bài toán (1.1) † (1.3) đƣợc gọi là một quy hoạch, hàm f(x) đƣợc gọi là hàm mục tiêu, các hàm gi(x), i = 1, m đƣợc gọi là các hàm ràng buộc, mỗi đẳng thức hoặc bất đẳng thức trong hệ (1.2) đƣợc gọi là một ràng buộc. Tập hợp:   D = x  X gi ( x)(, , )bi , i  1, m đƣợc gọi là miền ràng buộc (hay miền chấp nhận đƣợc). Mỗi điểm x = (x1, x2,...., xn)  D đƣợc gọi là một phƣơng án (hay một lời giải chấp nhận đƣợc). Một phƣơng án x*  D đạt cực đại (hay cực tiểu) của hàm mục tiêu, cụ thể là: f(x*)  f(x),  x  D (đối với bài toán max) f(x*)  f(x),  x  D (đối với bài toán min) đƣợc gọi là phƣơng án tối ƣu (lời giải tối ƣu). Khi đó giá trị f(x*) đƣợc gọi là giá trị tối ƣu của bài toán. 1.2. Giới thiệu một số dạng bài toán tối ƣu Một trong những phƣơng pháp hiển nhiên nhất để giải bài toán đặt ra là phƣơng pháp điểm diện: tính giá trị hàm mục tiêu f(x) trên tất cả các phƣơng án, sau đó so sánh các giá trị tính đƣợc để tìm ra giá trị tối ƣu và phƣơng án tối ƣu của bài toán. Tuy nhiên, cách giải quyết này khó có thể thực hiện đƣợc, Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 ngay cả khi kích thƣớc của bài toán (số biến n và số ràng buộc m) là không lớn, bởi vì tập D thông thƣờng gồm một số rất lớn các phần tử, trong nhiều trƣờng hợp còn là không đếm đƣợc. Vì vậy, phải có những nghiên cứu trƣớc về mặt lý thuyết để có thể tách ra từ bài toán tổng quát những lớp bài toán “dễ giải”. Các nghiên cứu lý thuyết đó thƣờng là: - Nghiên cứu các tính chất của các thành phần bài toán (hàm mục tiêu, các hàm ràng buộc, các biến số, các hệ số,…); - Các điều kiện tồn tại lời giải chấp nhận đƣợc; - Các điều kiện cần và đủ của cực trị; - Tính chất của các đối tƣợng nghiên cứu. Các tính chất của các thành phần của bài toán và đối tƣợng nghiên cứu giúp ta phân loại các bài toán. Một bài toán tối ƣu (quy hoạch toán học) đƣợc gọi là: - Quy hoạch tuyến tính (QHTT) nếu hàm mục tiêu f(x) và tất cả các hàm ràng buộc gi(x), i = 1, m là tuyến tính. Một trƣờng hợp riêng quan trọng của QHTT là bài toán vận tải (BTVT); - Quy hoạch tham số (QHTS) nếu các hệ số trong biểu thức của hàm mục tiêu và của các ràng buộc phụ thuộc vào tham số; - Quy hoạch động (QHĐ) nếu các đối tƣợng xét là các quá trình có nhiều giai đoạn nói chung, hay các quá trình phát triển theo thời gian nói riêng; - Quy hoạch phi tuyến (QHPT) nếu f(x) hoặc có ít nhất một trong các hàm gi(x) là phi tuyến hoặc cả 2 trƣờng hợp đó cùng xảy ra; - Quy hoạch rời rạc (QHRR) nếu miền ràng buộc D là tập rời rạc. Trong trƣờng hợp riêng khi các biến chỉ nhận giá trị nguyên ta có quy hoạch nguyên (QHN); Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 - Quy hoạch đa mục tiêu (QHĐMT) nếu trên cùng một miền ràng buộc ta xét các hàm mục tiêu khác nhau. 1.2.1. Bài toán vận tải (BTVT) 1.2.1.1. Phát biểu bài toán Có m địa điểm A1, A2, ......, Am cùng sản xuất một loại hàng hóa với các lƣợng hàng tƣơng ứng là a1, a2,….., am. Có n nơi tiêu thụ loại hàng đó B1, B2, ......, Bn với các yêu cầu tƣơng ứng là b1, b2, ......, bn. Để đơn giản ta sẽ gọi Ai là điểm phát i, i = 1, m Bj là điểm thu j, j = 1, n Hàng có thể chở từ một điểm phát bất kỳ (i) đến một điểm thu bất kỳ (j). Ký hiệu: cij – chi phí chuyên chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j); xij – lƣợng hàng chuyên chở từ i đến j. Bài toán đặt ra là: Xác định những đại lƣợng xij cho mọi con đƣờng (i, j) sao cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết là: m  n ai = i 1  bj j 1 tức là lƣợng hàng phát ra đúng bằng lƣợng hàng yêu cầu ở các điểm thu (điều kiện cân bằng thu phát). Dạng toán học của bài toán vận tải là: m n   cij xij  min i 1 j 1 (1.4) n  xij j 1 = ai, i = 1, m (1.5) m  xij i 1 = bj, j = 1, n (1.6) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 xij  0, i = 1, m , j = 1, n ai, bj >0; m  ai i 1 = (1.7) n  bj j 1 Giả sử ta cộng các phƣơng trình từ (m + 1) tới (m + n) rồi trừ đi tổng các phƣơng trình từ (2) tới (m) thì ta đƣợc phƣơng trình (1). Do đó số các phƣơng trình cực đại của hệ (1.5) + (1.6) không quá m + n -1. x11 + x12 + .... + x1n = a1 (1) x21 + x22 + ..... + x2n = a2 (2) ........... (*) xm1 + xm2 + ..... + xmn x11 = am (m) + x21 + .. + xm1 = b1 (m+1) + x22 +…..+ x2m x12 = b2 (m+2) ……….. x1n + x2n +……. + xmn = bn (m+n) Ký hiệu ma trận của hệ (*) là A. X = (x11, x12,......, xij,....., xmn) - vectơ cột mn thành phần C = (c11, c12,......, cij,....., cmn) - vectơ hàng mn thành phần P0 = (a1, a2, ....., am, b1, b2,...., bn) – vectơ cột vế phải Ta có thể đƣa bài toán vận tải về dạng: Min (1.8) AX = P0 (1.9) X0 (1.10) Ta gọi Pij là cột của ma trận A ứng với biến xij. Dễ thấy vectơ này có 2 thành phần bằng 1 tại dòng thứ i và dòng thứ m + j còn các thành phần khác bằng 0. Định nghĩa: Vectơ X thỏa (1.9), (1.10) gọi là một phƣơng án của BTVT. Một phƣơng án đạt cực tiểu (1.8) gọi là phƣơng án tối ƣu. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Một phƣơng án X gọi là phƣơng án cơ sở nếu các vectơ cột Pij của ma trận A ứng với các xij > 0 là độc lập tuyến tính. 1.2.1.2. Sự tồn tại nghiệm tối ƣu Định lý 1.1: Bài toán vận tải luôn có phƣơng án tối ƣu. Chứng minh : 1) Trƣớc hết ta chứng minh bài toán vận tải luôn có phƣơng án. 2) Sau đó chứng minh rằng miền ràng buộc giới nội. a) Đặt S = m a i 1 Ta thấy xij = n i = ai b j S b j 1 j 1 >0 , i = 1, m , j = 1, n lập thành 1 phƣơng án, vì rằng xij  0 n x j ij = m  xij = i 1 n  ai b j j 1 S m ai b j i 1 S  = ai , i = 1, m = bj , j = 1, n b) Vì các hệ số trong (1.5), (1.6) và các đại lƣợng trong ai, bj không âm và hữu hạn nên mọi xij đều bị chặn trên. Thực vậy, xij không thể lớn hơn các số tƣơng ứng ai hay bj. Vì vậy miền ràng buộc là khác rỗng và giới nội (ta có đa diện lồi). Đa diện này có một số hữu hạn đỉnh vì vậy theo thuật toán đơn hình, xuất phát từ một phƣơng án cực biên, sau một số hữu hạn bƣớc ta phải đi tới phƣơng án cực biên tối ƣu. 1.2.1.3. Tiêu chuẩn nhận biết phƣơng án cực biên Lập 1 bảng T gồm m hàng và n cột. Tại các ô (i, j) ta ghi các số c ij tƣơng ứng cho trƣớc (ghi vào góc ô) và các ƣớc lƣợng xij của phƣơng án X. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 bj b1 ... bj ... bn ai a1 ... ai xij cij .... am Một ô (i, j) mà xij > 0 gọi là ô sử dụng. Tập hợp các ô sau đây gọi là một dây chuyền trong T: (i1, j1), (i1, j2), (i2, j2),......, (is, js), (is, js+1) (1.11) (đi theo hàng trƣớc) Hoặc: (i1, j1), (i2, j1), (i2, j2),....., (is, js), (is+1, js) (1.12) (đi theo cột trƣớc) Mỗi cặp các ô liền nhau trong dây chuyền đƣợc xếp trong 1 hàng hoặc trong 1 cột. Dây chuyền đƣợc gọi là kín hay là 1 chu trình nếu: js+1 = j1 Hoặc: is+1 = i1 Gọi G là tập hợp các ô sử dụng:   G = (i, j ) xij  0 G  m  n  1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Một phƣơng án X của BTVT đã cho đƣợc gọi là không thoái hóa nếu G = m+n-1. Ngƣợc lại gọi là thoái hóa nếu G < m+n-1. Nếu một tập hợp con thực sự của G lập thành chu trình thì ta có một chu trình con của G. Định lý 1.2: Hệ thống vector Pij của BTVT là độc lập tuyến tính khi và chỉ khi các ô tƣơng ứng với các vector của hệ thống không tạo thành chu trình. Chứng minh.   Cần: Ký hiệu Pij = Pij (i, j )  G . Giả sử Pij là hệ độc lập tuyến tính, ta phải chứng minh G không lập thành chu trình. Bằng phản chứng, nếu có một chu trình tạo nên bởi các ô tƣơng ứng với một số vector của hệ Pij thì nó có dạng: (i1, j1), (i1, j2), (i2, j2),......, (is, js), (is, js+1) với js+1 = j1 Khi đó rõ ràng: Pi1j1 - Pi1j2 + Pi2j1 -......- Pisjs - Pisj1 = 0 Tức là hệ Pij phụ thuộc mâu thuẫn với giả thiết. Đủ: Giả sử G không lập thành chu trình. Ta phải chứng minh hệ P ij là độc lập tuyến tính. Bằng phản chứng giả sử Pij là phụ thuộc tuyến tính. Mỗi vector Pij có dạng: ( 1 , 2 ,.....,  i ,....,  m , m1 ,....,  m j ,....,  mn ) Với thành phần 1   m j = 1, còn các tọa độ khác bằng 0. Nếu hệ Pij phụ thuộc tuyến tính, tức là có một tổ hợp tuyến tính của các vector Pij = 0. Điều đó chứng tỏ rằng các ô (i, j) tƣơng ứng với hệ thống p ij lập thành chu trình. Điều này trái với giả thiết. Vậy hệ Pij là độc lập tuyến tính. Hệ quả: Vector X là phƣơng án cực biên khi và chỉ khi tập các ô sử dụng tƣơng ứng không lập thành chu trình. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Chứng minh. Thật vậy, coi BTVT là một QHTT thì X là phƣơng án cực biên khi và chỉ khi các vector Pij ứng với xij > 0 là độc lập tuyến tính. Theo định lý 1.2 thì điều đó xảy ra khi và chỉ khi tập các ô sử dụng tƣơng ứng không lập thành chu trình. 1.2.2. Bài toán cái túi 1.2.2.1. Phát biểu bài toán Một ngƣời du lịch muốn đem theo một cái túi nặng không quá b kg, có n loại đồ vật mà anh ta dự định đem theo. Mỗi đồ vật loại j có khối lƣợng a j kg và giá trị cj, ngƣời du lịch muốn chất vào túi các đồ vật sao cho tổng giá trị đồ vật đem theo là lớn nhất. Ký hiệu: xj là số loại đồ vật j sẽ chất vào trong túi. Ta có bài toán sau: n c x j  max (1.13) n  a j x j  b  j 1   x j  0, j  1, n   x j  nguyên, j  1, n  (1.14) j 1 j (1.15) (1.16) 1.2.2.2. Thuật toán giải bài toán cái túi Ta sẽ xây dựng thuật toán giải bài toán cái túi dựa trên phƣơng pháp quy hoạch động. Đối với mỗi số nguyên k và số  (k = 1, n ;   0, b ) ta định nghĩa hàm số: n  n  Fk(  ) = max  c j x j  a j x   x j  0 nguyên j  1, k   j 1 j 1  (1.17) Chú ý rằng khi k = n và  = b ta có bài toán xuất phát. Ở đây Fk(  ) là giá trị lớn nhất của hàm mục tiêu khi các đồ vật đƣợc chọn từ k loại đầu tiên và trọng lƣợng cái túi là  . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Ký hiệu Z+ là tập các số nguyên không âm        ak   Sk = 0,1,.....,      Trong đó ký hiệu   là phần nguyên của . ak  ak  Theo phƣơng trình truy toán ta có thể viết lại công thức (1.17) dƣới dạng: k 1  k 1  Fk(  )= max ck xk  max   c j x j  a j x j    ak xk , x j  Z  , j  1, k   j 1  j 1   = max ck xk  Fk 1 (  a k xk )  (1.18) Đặt F0(  ) = 0,   0, b (1.19) Khi k = 1 từ (1.18) và (1.19) ta có:        F1(k) = max c1x1 x1  0,1,...   = c1    ,   0, b  1   1  (1.20) Tiếp tục quá trình ta sẽ tính đƣợc Fk(  ), k = 1,   0, b . 1.2.3. Ứng dụng vào nghành nông nghiệp Một loạt những bài toán thực tế nông nghiệp đƣợc đƣa đến mô hình quy hoạch toán học, chẳng hạn đó là những bài toán về phân bổ hợp lý diện tích trồng trọt, về việc hợp lý hóa vỗ béo gia súc, về chuyên môn hóa sản xuất nông nghiệp, về sơ đồ làm việc của các máy nông nghiệp... ë đây chúng ta đƣa ra 2 bài toán: bài toán kiện toàn cấu trúc hợp lý nghành chăn nuôi và bài toán xác định cơ cấu gieo trồng cây lƣơng thực. Bài toán 1: Kiện toàn cấu trúc nghành chăn nuôi. Khả năng của chăn nuôi bị ràng buộc chủ yếu vào thức ăn. Trong những lý luận dƣới đây giả thiết rằng khẩu phần hợp lý để vỗ béo những loại gia súc khác nhau đã đƣợc xác định. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Việc mô hình hóa bài toán đòi hỏi những ký hiệu sau: xj - số đầu súc vật loại j (j = 1, 2, ...., n); pj - sản lƣợng nhận đƣợc từ một đầu súc vật loại j; bkj - khẩu phần thức ăn loại k đòi hỏi cho một đầu súc vật loại j (k = 1, 2, ....,s); bk - dự trữ thức ăn loại k. Bài toán dẫn đến việc tìm các đại lƣợng xj làm cực đại dạng tuyến tính. F(x) = n  pjxj j 1  max Với các ràng buộc: n  bkj x j  bk , k  1,2,...s  j 1  x  0, j  1,2,..., n  j Bài toán 2: Cơ cấu gieo trồng cây lƣơng thực. Trong những trƣờng hợp khi mà những yêu cầu về lƣơng thực cho ngƣời và về sản phẩm chăn nuôi đã cố định trƣớc xuất hiện bài toán chuyên môn hóa gieo trồng cây lƣơng thực. Cần phải xác định diện tích đƣợc dùng cho những loại cây lƣơng thực riêng sao cho với chi phí nhỏ nhất cũng thỏa mãn khẩu phần cần thiết của việc cung cấp lƣơng thực. Ở đây thƣờng kể đến những ràng buộc về dự trữ lao động, về trạm máy kéo, về nhiên liệu, phân bón, về thủy nông và những yếu tố khác bảo đảm lƣơng thực. Ta đƣa vào những ký hiệu sau: xj - lƣợng hecta ruộng dành cho cây lƣơng thực loại j, j = 1, 2, ...,n; d j - diện tích trồng trọt cực đại mà do những điều kiện tự nhiên (chất đất, khí hậu) có thể dành cho loại cây thứ j; dj - diện tích trồng trọt tối thiểu dùng cho cây lƣơng thực thứ j theo yêu cầu cơ cấu lƣơng thực; Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 aij - sản lƣợng thức ăn loại i trên một hecta trồng trọt loại cây thứ j, j = 1, 2, ...,m; ai - nhu cầu thức ăn loại i cần thiết để hoàn thành kế hoạch về tất cả sản phẩm lƣơng thực; bkj - khẩu phần tiêu hao, những yếu tố sản xuất loại k để khai thác 1 hecta ruộng dành cho loại cây lƣơng thực thứ j, k = 1, 2, ...,s; bk - dự trữ những yếu tố sản xuất loại k; cj - giá thành lƣơng thực loại j từ một hecta trồng trọt; xj - diện tích chung dành cho các loại cây lƣơng thực. Bài toán xác định cơ cấu tối ƣu trồng cây lƣơng thực nhƣ vậy sẽ quy về xác định những đại lƣợng xj (j = 1, 2, ....,n) sao cho dạng tuyến tính sau đạt cực tiểu: n F(x) = c x j 1 j j  min 1.2.4. Bài toán quy hoạch phi tuyến và nghiệm tối ƣu của nó 1.2.4.1. Phát biểu bài toán Bài toán QHPT tổng quát có thể diễn tả dƣới dạng: Min f(x); x  Rn (1.27)  g i ( x)  0; i  1,2,....., m  h j ( x)  0; j  1,2,....., p (1.28) (1.29) Trong đó ít nhất 1 trong các hàm f(x), {gi(x)}, {hj(x)} là phi tuyến. Trong 1 số trƣờng hợp, các ràng buộc đẳng thức, còn bất đẳng thức  có thể chuyển về bất đẳng thức  bằng cách nhân 2 vế với (-1). Nếu bài toán chỉ có dạng (1.27) thì ta có bài toán QHPT không ràng buộc. Có những khi ta gặp bài toán dạng nhƣ sau: Min f(x) ; x  M (1.30) M = {x  D g i ( x)  0; h j ( x)  0; i  1,2,....., m; j  1,2,...., p } Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên (1.31) http://www.lrc-tnu.edu.vn 14 Trong đó D là tập lồi trong Rn. Nếu các hàm f(x), {gi(x)}, {hj(x)} là những hàm lồi thì ta có quy hoạch lồi, là một trƣờng hợp riêng quan trọng của phi tuyến. Nếu hàm f(x) là một dạng toàn phƣơng, còn các ràng buộc là tuyến tính thì ta có quy hoạch toàn phƣơng lại là 1 trƣờng hợp riêng của quy hoạch lồi. Nhiều khi ngƣời ta biến đổi bài toán có ràng buộc về bài toán không có ràng buộc bằng cách dùng một hàm bổ trợ. Hàm bổ trợ này biểu diễn qua các hàm số của bài toán và bản thân nó trở thành hàm mục tiêu có các cực tiểu không điều kiện trong một miền nào đấy. Ngƣời ta thay đổi dần thông số, và chính bằng cách đó làm tăng ảnh hƣởng của các ràng buộc lên hàm bổ trợ và nhƣ vậy, ngƣời ta xây dựng đƣợc 1 dãy bài toán không có ràng buộc mà nghiệm của chúng hội tụ đến nghiệm của bài toán xuất phát. Để đơn giản ta nêu ra tƣ tƣởng cơ bản một cách hình thức. Xét bài toán: Min f(x); x  Rn (1.32) Gi(x)  0; i = 1, 2,...,m (1.33) Hàm bổ trợ điển hình không có ràng buộc có thể viết dƣới dạng:  x,  (t )  f ( x)  Trong đó: gi ( x) m  i (t )G i 1 t = thông số; i (t ) là các hệ số trọng. G(y) là hàm đơn điệu theo y mà trong ý nghĩa nào đó khá tốt khi y = 0. Thƣờng G(y) đƣợc chọn sao cho: G(y) > 0 với y < 0 G(y) = 0 với y  0 Hoặc: G(y)+  khi y0 Phép chọn đầu tiên thƣờng liên quan đến các thủ tục, trong đó các ràng buộc chỉ thỏa mãn đối với nghiệm tối ƣu tìm đƣợc, nghĩa là tận cùng các quá Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn