Giáo trình Vận trù học

Nội dung text: Giáo trình Vận trù học

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP HÀ NỘI PGS. TS. NGUYỄN HẢI THANH VẬN TRÙ HỌC Giáo trình cho ngành Tin học và Công nghệ thông tin Hà Nội − 2008
2. MỤC LỤC Trang LỜI NÓI ĐẦU 7 CHƯƠNG I. MỞ ĐẦU 9 1. Giới thiệu về Vận trù học / Khoa học quản lí 9 1.1. Vai trò của Vận trù học 9 1.2. Các bước áp dụng Vận trù học 10 1.3. Quá trình phát triển của Vận trù học 11 2. Các ứng dụng và phương pháp định lượng cơ bản của Vận trù học 12 2.1. Một số ứng dụng 12 2.2. Các phương pháp định lượng 14 2.3. Hệ thông tin quản lí 14 CHƯƠNG II. MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU 16 1. Mô hình quy hoạch tuyến tính 16 1.1. Phát biểu mô hình quy hoạch tuyến tính 16 1.2. Phương pháp đơn hình giải BTQHTT dạng chính tắc 19 1.3. Phương pháp đơn hình hai pha giải BTQHTT dạng tổng quát 23 1.4. Phương pháp cắt Gomory giải BTQHTT nguyên 29 1.5. Một số ứng dụng của phương pháp đơn hình 33 2. Mô hình quy hoạch tuyến tính đa mục tiêu 35 2.1. Các khái niệm cơ bản 35 2.2. Phương pháp tổng quát giải BTQHTT đa mục tiêu 37 2.3. Phương pháp thoả dụng mờ tương tác giải BTQHTT đa mục tiêu 39 2.4. Một ứng dụng của mô hình quy hoạch tuyến tính đa mục tiêu 44 3. Mô hình tối ưu phi tuyến đơn và đa mục tiêu 45 3.1. Một số khái niệm cơ bản 45 3.2. Một số phương pháp giải bài toán tối ưu phi tuyến đơn mục tiêu và ứng dụng 47 3.3. Một số phương pháp giải bài toán tối ưu phi tuyến đa mục tiêu và ứng dụng 51 Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 2
3. BÀI TẬP CHƯƠNG II 54 CHƯƠNG III. CÁC MÔ HÌNH MẠNG 57 1. Mô hình mạng vận tải 57 1.1. Phát biểu bài toán vận tải 57 1.2. Tạo phương án vận tải xuất phát 58 1.3. Phương pháp phân phối giải bài toán vận tải 60 1.4. Phương pháp phân phối cải biên giải bài toán vận tải 62 2. Mô hình mạng PERT 66 2.1. Các khái niệm cơ bản về PERT 66 2.2. Sơ đồ PERT với số liệu ngẫu nhiên 71 2.3. Điều chỉnh dự án khi kế hoạch một số hoạt động bị phá vỡ 73 2.4. Tính thời gian rút gọn tối ưu bằng phương pháp đơn hình 74 2.5. Áp dụng mạng PERT trong phân tích chi phí và quản lí tài chính dự án 75 3. Một số mô hình mạng khác 77 3.1. Bài toán cây khung tối thiểu 77 3.2. Bài toán tìm đường đi ngắn nhất và quy hoạch động 79 3.3. Mô hình mạng trung chuyển hàng 86 3.4. Bài toán tìm luồng cực đại 88 BÀI TẬP CHƯƠNG III 90 CHƯƠNG IV. GIỚI THIỆU LÍ THUYẾT MÔ PHỎNG VÀ MÔ HÌNH HÀNG CHỜ 96 1. Mục đích và các công cụ của mô phỏng 96 1.1. Khái niệm về mô phỏng ngẫu nhiên 96 1.2. Các công cụ chủ yếu của mô phỏng 97 1.3. Mô phỏng một số phân phối xác suất 98 2. Áp dụng mô phỏng ngẫu nhiên 101 2.1. Vai trò của phương pháp mô phỏng 101 2.2. Các bước cần tiến hành khi áp dụng mô phỏng 102 2.3. Một số ví dụ về áp dụng phương pháp mô phỏng 102 3. Một số vấn đề về mô hình hàng chờ 112 3.1. Một số yếu tố cơ bản của hệ thống hàng chờ 112
4. 3.2. Các chỉ số cần khảo sát 115 3.3. Tính toán các chỉ số 116 3.4. Áp dụng mô phỏng cho một số hệ thống hàng chờ 118 BÀI TẬP CHƯƠNG IV 127 CHƯƠNG V. PHÂN TÍCH MARKOV VÀ ỨNG DỤNG 131 1. Các khái niệm cơ bản về xích Markov 131 1.1. Một số định nghĩa 131 1.2. Ma trận xác suất chuyển trạng thái và phân phối dừng 132 1.3. Các tính chất và định lí 137 2. Một số ứng dụng của phân tích Markov 138 2.1. Tìm cân bằng thị phần 138 2.2. Chính sách thay thế vật tư thiết bị 138 2.3. Phân tích Markov trong dự báo thất thu cho các hợp đồng thực hiện trước 140 2.4. Tìm phân phối giới hạn cho một hệ thống kĩ thuật 142 2.5. Một ứng dụng của quá trình sinh−tử cho hệ thống hàngchờ 147 3. Mô phỏng xích Markov 149 3.1. Mô phỏng xích Markov thời gian rời rạc 149 3.2. Mô phỏng xích Markov thời gian liên tục 151 BÀI TẬP CHƯƠNG V 152 CHƯƠNG VI. MỘT SỐ MÔ HÌNH RA QUYẾT ĐỊNH VÀ ỨNG DỤNG 158 1. Ra quyết định trong môi trường bất định 158 1.1. Một số khái niệm cơ bản 158 1.2. Ra quyết định trong môi trường bất định nghiêm ngặt 160 1.3. Ra quyết định trong môi trường rủi ro 163 2. Phân tích quyết định Bayes 167 2.1. Phân tích quyết định Bayes dựa trên xác suất tiên nghiệm 167 2.2. Phân tích quyết định Bayes dựa trên xác suất hậu nghiệm 167 3. Cây quyết định và các bài toán quyết định nhiều giai đoạn 169 3.1. Bài toán quyết định nhiều giai đoạn 169 3.2. Phân tích Bayes sử dụng cây quyết định 171 4. Ra quyết định dựa trên tiêu chuẩn kì vọng thỏa dụng tối đa 174 Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 4
5. 4.1. Khái niệm hàm thỏa dụng 174 4.2. Tiêu chuẩn kì vọng thỏa dụng tối đa 175 5. Lí thuyết trò chơi và ứng dụng 179 5.1. Một số khái niệm cơ bản của lí thuyết trò chơi 179 5.2. Trò chơi hai người – tổng không với chiến lược thuần nhất 181 5.3. Trò chơi hai người – tổng không với chiến lược hỗn hợp 182 5.4. Lời giải bằng đồ thị cho các trò chơi cỡ 2×N hoặc M×2 186 5.5. Giới thiệu về trò chơi nhiều người 188 BÀI TẬP CHƯƠNG VI 190 CHƯƠNG VII. CÁC MÔ HÌNH QUẢN LÍ HÀNG DỰ TRỮ 193 1. Các khái niệm cơ bản 193 1.1. Các chức năng của việc dự trữ hàng 193 1.2. Hệ thống quản lí hàng dự trữ theo phân loại giá trị ABC 193 1.3. Mô hình quản lí hàng dự trữ tổng quát 194 2. Một số mô hình tất định trong quản lí hàng dự trữ 196 2.1. Mô hình tĩnh Wilson với một mặt hàng 196 2.2. Mô hình tĩnh một mặt hàng với dự trữ đệm 199 2.3. Mô hình tĩnh một mặt hàng với giá chiết khấu 200 2.4. Mô hình tĩnh nhiều mặt hàng với diện tích kho hạn chế 202 2.5. Mô hình động một mặt hàng N chu kì 204 3. Mô hình lập kế hoạch sản xuất N chu kì 207 3.1. Mô hình lập kế hoạch không cho phép nợ hàng 208 3.2. Mô hình lập kế hoạch cho phép nợ hàng 209 4. Một số mô hình xác suất trong quản lí hàng dự trữ 210 4.1. Mô hình xác suất với chế độ báo cáo theo dõi thường xuyên 210 4.2. Mô hình xác suất một chu kì 213 4.3. Mô hình xác suất nhiều chu kì 218 BÀI TẬP CHƯƠNG VII 224 PHẦN PHỤ LỤC 229 TÀI LIỆU THAM KHẢO 234
6. LỜI NÓI ĐẦU Vận trù học (Operations Research) được xem là một công cụ định lượng nền tảng của Khoa học quản lí mà trong đó các phương pháp và kĩ thuật của Toán học và các công cụ tính toán, lưu trữ và xử lí dữ liệu của Tin học được áp dụng để mô hình hóa, phân tích và tìm ra lời giải cho các bài toán quyết định, nhằm hỗ trợ bộ máy quản lí đưa ra các quyết định hợp lí nhất. Trên thế giới việc nghiên cứu và ứng dụng Vận trù học ngày càng phát triển sâu rộng với nhiều tạp chí chuyên ngành nổi tiếng, môn Vận trù học được giảng dạy với thời lượng khá lớn bao gồm nhiều nội dung phong phú và cấp thiết trong nhiều chương trình đào tạo đại học và cao học. Hiện nay, những môn học trang bị kiến thức cơ sở về kinh tế - quản lí nói chung và các phương pháp toán - tin ứng dụng trong mô hình hóa và phân tích các bài toán quyết định nói riêng được đưa vào giảng dạy trong các chương trình đào tạo đại học trong và ngoài nước. Đối với sinh viên các ngành Tin học, Công nghệ thông tin và Toán - Tin ứng dụng, khối kiến thức về kinh tế - quản lí là thực sự cần thiết cho các cương vị làm việc sau này, đặc biệt là cương vị CIO (Chief Information Officer - Giám đốc Thông tin). Trong chương trình đào tạo ngành Tin học của Khoa Công nghệ thông tin, Trường Đại học Nông nghiệp Hà Nội, khối kiến thức trên bao gồm Tối ưu hóa, Phân tích số liệu, Quản trị học, Các phương pháp toán kinh tế và Vận trù học. Giáo trình “Vận trù học” với thời lượng 60 tiết được biên soạn lần đầu nhằm trước hết phục vụ việc dạy và học môn học này cho sinh viên năm thứ ba hoặc năm thứ tư ngành Tin học. Hi vọng rằng, sau khi ra trường các kĩ sư Tin học sẽ áp dụng và triển khai các phương pháp vận trù học được một cách rộng rãi với nhiều hiệu quả thiết thực trong việc xây dựng các hệ thống thông tin quản lí và các phần mềm tính toán cho các bài toán quản lí, quản trị kinh doanh và kinh tế - công nghệ khác. Qua giáo trình này, sinh viên cần nắm được một số mô hình vận trù học cơ bản, biết cách vận dụng các phương pháp và kĩ thuật toán học, các quy trình tính toán khoa học thích hợp để phân tích và xử lí các mô hình đó. Các chủ đề trong giáo trình bao gồm: Một số mô hình tối ưu (Optimization Model) như các mô hình quy hoạch tuyến tính cũng như phi tuyến đơn và đa mục tiêu được đề cập tới trong Chương II. Chương III giới thiệu về các mô hình mạng (Network Model) với các bài toán về mạng vận tải, mạng PERT, về quy hoạch động áp dụng trong tìm đường đi ngắn nhất và bài toán tìm luồng cực đại. Một số ứng dụng của mô hình hàng chờ (Waiting Line Model) Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 6
7. và mô phỏng ngẫu nhiên (Stochastic Simulation) được trình bày trong Chương IV. Chương V giới thiệu các khái niệm cơ bản và ứng dụng của xích Markov (Markov Chain). Chương VI là các kiến thức cơ sở của lí thuyết quyết định (Decision Theory) như các quy tắc ra quyết định trong các môi trường bất định và rủi ro, phân tích quyết định Bayes, cây quyết định và lí thuyết trò chơi. Chương VII trình bày về mô hình quản lí hàng dự trữ (Inventory Management Model), một vấn đề quan trọng phát sinh trong quản lí tài nguyên và nguồn lực của các doanh nghiệp. Đây là các chủ đề chủ yếu nhất của môn Vận trù học mà sinh viên các ngành Tin học, Công nghệ thông tin và Toán - Tin ứng dụng tại các trường đại học nước ngoài bắt buộc phải học. Phần bài tập sau từng chương giúp sinh viên củng cố các kiến thức đã học và thực hành áp dụng các quy trình tính toán khoa học. Những sinh viên khá có thể tự học sâu thêm bằng cách thu thập tài liệu liên quan qua nhiều nguồn, đặc biệt trên Internet và viết các phần mềm nhỏ. Giáo trình cũng có thể được lấy làm tài liệu tham khảo hay dạy và học các phương pháp toán ứng dụng hay mô hình hóa cho các chuyên ngành như: Quản lí đất đai, Kinh tế nông nghiệp, Cơ điện và một số chuyên ngành quản lí − kinh tế − công nghệ khác ở bậc đại học hoặc cao học. Một số tài liệu người học có thể tham khảo thêm là: Gillet B. E., Introduction to Operations Research, McGraw Hill, New York, 1990; Taha H. A., Operations Research, MacMillan Publishing Company, New York, 1989; Levin R. I., Rubin D. S. and Stinson J. P., Quantitative approaches to management, McGraw Hill, New York, 1986; Phan Quốc Khánh, Vận trù học, Nxb Giáo dục, 2004; Tạp chí Ứng dụng Toán học, Hội Ứng dụng Toán học Việt Nam, 2003 - 2007. Trong quá trình biên soạn, tuy tác giả rất cố gắng nhưng có lẽ không tránh khỏi sai sót. Tác giả xin chân thành cảm ơn các ý kiến đóng góp chỉnh sửa bản thảo bài giảng môn học của các đồng nghiệp trong Khoa Công nghệ thông tin và sinh viên ngành Tin học các khóa K47, K48, K49, K50 của Trường Đại học Nông nghiệp Hà Nội và luôn mong muốn tiếp tục nhận được nhiều góp ý của các nhà khoa học, các giảng viên và sinh viên để cho giáo trình được hoàn chỉnh hơn, chính xác hơn và sinh động hơn. Hà Nội, ngày 10 tháng 10 năm 2008 Tác giả
8. Chương I MỞ ĐẦU 1. GIỚI THIỆU VỀ VẬN TRÙ HỌC VÀ KHOA HỌC QUẢN LÍ 1.1. Vai trò của Vận trù học Vận trù học (Operations Research − OR) là ngành học nghiên cứu về các hoạt động hợp lí. Việc tổ chức và tiến hành các hoạt động trong nhiều lĩnh vực như kinh tế, xã hội, quốc phòng, kinh doanh, sản xuất, dịch vụ đòi hỏi các nhà quản lí phải vận dụng một cách thích hợp các điều kiện cho phép để trù tính và đưa ra các quyết định. Đối với bộ máy quản lí các cấp trong các doanh nghiệp, tập đoàn, công ti , ra quyết định chính là trách nhiệm then chốt nhất. Quá trình ra quyết định được bắt đầu khi bộ máy quản lí phát hiện một vấn đề nào đó cần quan tâm tới. Sau đó, cần xác định rõ vấn đề, phát biểu mục tiêu phải hướng tới và các điều kiện hạn chế (còn gọi là các điều kiện ràng buộc) cũng như tìm kiếm và đánh giá các phương án. Cuối cùng, phải chọn ra một phương án hành động được coi là hợp lí hơn cả nhằm giải quyết vấn đề một cách tốt nhất. Năng lực của bộ máy quản lí được thể hiện ở khả năng phát hiện vấn đề và giải quyết bài toán quyết định phát sinh. Một quá trình ra quyết định chính là một quá trình phân tích và tổng hợp thông tin, có thể có hình thức định tính hay định lượng. Với cách tiếp cận định tính, người quản lí có thể dựa vào các nhận định chủ quan và kinh nghiệm sẵn có của mình để đưa ra quyết định. Trong một số trường hợp, cách tiếp cận này có tính “trực giác” nhưng cũng giúp đưa ra được quyết định đủ tốt. Tuy nhiên, trong rất nhiều trường hợp khác, cách tiếp cận định lượng sẽ có hiệu quả thật sự trong việc trợ giúp quá trình ra quyết định. Cách tiếp cận định lượng thường được nhà quản lí thực hiện trong các trường hợp sau: - Vấn đề đặt ra khá phức tạp bao gồm nhiều biến và do đó cần phải thiết lập mô hình toán học và sử dụng các công cụ định lượng để tìm ra được phương án giải quyết. - Các dữ liệu liên quan tới vấn đề cần khảo sát có dạng dữ liệu số và mục tiêu cần hướng tới có tính chất định lượng, chẳng hạn như cần nâng cao hay hạ thấp một chỉ số nào đấy. - Vấn đề đặt ra có tính chất “lặp”, tức là quá trình giải quyết vấn đề có thể bao gồm một số công đoạn/thủ tục lặp đi lặp lại nhiều lần và vì vậy, tiếp cận định lượng sẽ giúp người quản lí tiết kiệm thời gian cũng như chi phí. - Tiếp cận định lượng đã tỏ ra hữu hiệu trong một số tình huống tương tự hoặc khi người quản lí đã có kinh nghiệm và thành công trong việc giải quyết các vấn đề tương tự dựa trên tiếp cận định lượng. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 8
9. Có thể nói, Vận trù học là một công cụ định lượng nền tảng của Khoa học quản lí (Management Science − MS), mà trong đó các phương pháp và kĩ thuật của Toán học cũng như các công cụ tính toán, lưu trữ và xử lí dữ liệu của Tin học được áp dụng để mô hình hóa, phân tích và tìm ra lời giải cho các bài toán quyết định, nhằm hỗ trợ bộ máy quản lí đưa ra đưa ra được quyết định đúng đắn trong điều kiện nguồn lực và tài nguyên hạn chế. Vì vậy, Vận trù học có một vai trò rất quan trọng trong việc thiết lập các kế hoạch dài hạn, phát triển các chiến lược chủ đạo cũng như trong việc hỗ trợ các hoạt động diễn ra hàng ngày trong nhiều lĩnh vực. Vận trù học là một ngành học vừa có tính khoa học vừa có tính nghệ thuật. Với tư cách là một khoa học, Vận trù học nghiên cứu và thiết lập các mô hình toán học của các vấn đề phát sinh từ thực tế cũng như các phương pháp toán học/các thuật giải để giải quyết mô hình đặt ra. Tuy nhiên, Vận trù học cũng là một nghệ thuật, vì rằng sự thành công của quá trình ra quyết định phụ thuộc phần lớn vào tính sáng tạo và năng lực của các nhà phân tích quyết định. Việc thu thập số liệu, thiết lập mô hình và triển khai phương án tìm được trên thực tế phụ thuộc vào khả năng của chuyên gia hay nhóm chuyên gia làm Vận trù học trong việc khai thác được thông tin xác thực cũng như xây dựng được sự giao tiếp tin cậy với bộ máy quản lí. 1.2. Các bước áp dụng Vận trù học Các bước cơ bản khi áp dụng Vận trù học để thiết lập và giải quyết một mô hình phát sinh từ thực tế có thể được tóm lược như sau: − Khảo sát thực tế và phát hiện vấn đề. Tại bước này, cần áp dụng và hoàn thiện các kĩ năng như: biết lắng nghe, điều tra và khảo sát dữ liệu, biết phân tích các hoạt động thực tế cũng như phân biệt được các yếu tố quan trọng với các chi tiết thứ yếu. − Phân tích vấn đề và xây dựng mô hình. Trước hết cần xác định rõ mục tiêu nghiên cứu và định dạng rõ bài toán phát sinh và phương án giải quyết, từ đó xác định các yếu tố liên quan mà nhà quản lí có thể kiểm soát được. Nói cách khác, cần xác định mục tiêu và các điều kiện hạn chế/điều kiện ràng buộc dưới dạng định tính. Sau đó lựa chọn các biến quyết định và xây dựng mô hình toán học phù hợp, phản ánh được thực tế khách quan. − Thu thập số liệu đầu vào và xác định phương pháp giải quyết. Căn cứ mô hình đã xây dựng được cần thu thập các số liệu đầu vào cần thiết, độ tin cậy của số liệu đầu vào ảnh hưởng rất đáng kể tới kết quả đầu ra của mô hình. Với mô hình đã xây dựng được cần tìm ra một phương pháp giải quyết thích hợp dựa trên các phương pháp đã biết hoặc phát triển phương pháp mới. − Xác định quy trình giải/thuật giải và chọn lựa phương án hợp lí. Có thể giải mô hình bằng cách tính toán thông thường nhằm lựa chọn trong các phương án khả thi một hoặc một số phương án hợp lí hơn cả. Đối với các mô hình lớn, gồm nhiều biến quyết định và nhiều điều kiện ràng buộc cần lập trình và giải mô hình trên máy tính.
10. − Kiểm thử mô hình và đánh giá phương án tìm được. Trong trường hợp phương án tìm được kéo theo các kết quả bất thường về mặt tính toán hoặc không phù hợp với thực tế, cần kiểm tra và chỉnh sửa lại mô hình, rà soát lại các số liệu đầu vào cũng như các bước tính toán hay chọn lựa phương án. Sau đó giải lại mô hình để tìm ra phương án phù hợp hơn. − Triển khai phương án tìm được trên thực tế. Trong toàn bộ quá trình ra quyết định, chuyên gia Vận trù học cần quan hệ chặt chẽ với nhà quản lí, giải thích rõ ràng về tác dụng của mô hình đã đặt ra. Để phương án cuối cùng được triển khai trên thực tế, cần có báo cáo chi tiết giúp bộ máy quản lí hiểu rõ các hiệu quả thiết thực mà phương án có thể mang lại. Tuy nhiên, cũng cần nêu rõ các điều kiện đảm bảo cần thiết cũng như phân tích rõ các yếu tố lợi nhuận/chi phí/rủi ro của phương án. 1.3. Quá trình phát triển của Vận trù học Những tiến bộ nhân loại đạt được trong vài thế kỉ vừa qua và trong giai đoạn hiện tại có phần đóng góp quan trọng của các phương pháp khoa học trong việc giải quyết các vấn đề kinh tế, xã hội. Phương pháp luận khoa học, trước đây thường được biết tới trong các vấn đề của Khoa học tự nhiên, ngày nay ngày càng được ứng dụng rộng rãi trong các lĩnh vực của Khoa học quản lí như: lập kế hoạch, tổ chức và kiểm soát các hoạt động. Từ hàng vài nghìn năm trước, các hoạt động chế tạo và lắp ráp tàu biển tại Venice đã được tổ chức một cách khá khoa học. Vào cuối thế kỉ XIX, Frederick W. Taylor đã giải quyết thành công bài toán quan trọng của Kĩ nghệ công nghiệp (Industrial Engineering) lúc đó là chế tạo ra các loại xẻng để khai thác các loại quặng khác nhau với năng suất cao nhất. Cũng vào thời gian này, Henry L. Gantt giải quyết thành công bài toán lập tiến trình sản xuất (Production Scheduling) khi sản phẩm được chế tạo và hoàn thiện qua nhiều công đoạn. Dần dần, các nhà quản lí mở rộng các bài toán trong một số hoạt động kĩ nghệ công nghiệp sang các hoạt động khác của công ti như: khai thác và sử dụng các nguồn nguyên liệu, thuê và phát triển nhân lực, chính sách tài chính, bất động sản Các nhà khoa học tự nhiên, xã hội cũng bắt đầu quan tâm tới các bài toán quản lí và nhận thức được tầm quan trọng của việc giải quyết vấn đề một cách hệ thống, tầm quan trọng của các nghiên cứu liên ngành bao gồm khoa học cơ bản, kĩ nghệ và quản lí. Đó cũng là khởi nguồn của Khoa học quản lí. Từ đầu thế kỉ XX, Vận trù học/Khoa học quản lí đã được áp dụng khá rộng rãi trong nhiều lĩnh vực. Tại nước Anh vào năm 1914 - 1915 F. W. Lanchester đã xem xét các hoạt động quân sự một cách định lượng khi đưa ra phương pháp đánh giá sức mạnh quân sự thông qua số lượng bộ binh và hỏa lực. Còn tại Mĩ lúc đó, T. A. Edison nghiên cứu và mô phỏng các hoạt động hợp lí của tàu chiến trong tấn công và tiêu diệt các tàu ngầm. Vào năm 1917, nhà bác học người Đan Mạch A. K. Erlang cho công bố các công Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 10
11. trình về các hoạt động hợp lí trong hệ dịch vụ điện thoại và bưu điện, có tên gọi tổng quát là hệ thống hàng chờ (Waiting Line System). Năm 1915, Ford W. Harris công bố về cách xác định dung lượng lô hàng tối ưu trong bài toán quản lí hàng dự trữ (Inventory Management). Sau đó một loạt công trình được các tác giả khác tiếp tục công bố về các mô hình kiểm soát hàng dự trữ. Các ứng dụng của lí thuyết xác suất trong kiểm định chất lượng (Quality Control) cũng được đề cập tới trong các bài báo của Walter Shewhart. Mô hình quy hoạch tuyến tính (Linear Programming) được giáo sư Đại học Havard Wassily Leontieff áp dụng vào những năm 1930 để mô tả và phân tích toàn bộ nền kinh tế Mĩ. Các ứng dụng của Vận trù học trong kinh doanh lần đầu tiên được Horace C. Levinson phát triển trong giai đoạn 1920 - 1930 để nghiên cứu các mối quan hệ giữa doanh thu và quảng cáo, giữa thu nhập và địa điểm sinh sống của người tiêu dùng và các mặt hàng mua sắm. Sau năm 1945, Vận trù học tiếp tục được ứng dụng ngày càng rộng rãi trong nhiều lĩnh vực. Rất nhiều bài toán quản lí được giải quyết bằng phương pháp đơn hình (Simplex Method) do George B. Danzig đưa ra vào năm 1947. Các mô hình mạng (Network Model) được phát triển lần đầu vào năm 1958 với sự trợ giúp của công ti tư vấn Booz, Allen và Hamilton. Tại Việt Nam, từ nhiều năm trước đây các hoạt động giảng dạy và nghiên cứu về Vận trù học đã được tiến hành tại một số cơ sở đào tạo và nghiên cứu như Đại học Tổng hợp Hà Nội, Viện Toán học, Viện Điều khiển kinh tế Vận trù học được đưa vào ứng dụng thành công trong một số lĩnh vực như giao thông, thủy lợi, sản xuất nông nghiệp và công nghiệp, dịch vụ, quốc phòng, với các đóng góp của các giáo sư Hoàng Tụy, Trần Vũ Thiệu, Nguyễn Đình Ngọc, Nguyễn Quý Hỷ. Được thành lập vào năm 2002, Tạp chí Ứng dụng Toán học đã và đang công bố nhiều bài báo trong lĩnh vực Vận trù học. Ngày nay, tại nhiều nước trên thế giới, các Hội Vận trù học và các Viện Khoa học quản lí được thành lập, với nhiều tạp chí chuyên khảo nổi tiếng. Có thể giới thiệu ở đây một số tạp chí quốc tế như: Operations Research, Management Science, A.I.E.E. Transactions, C.O.R.S. Journal, Industrial Engineering, European Journal of Operational Research, Asia-Pacific Journal of Operational Research, Decision Sciences, Decision Support Systems. 2. CÁC ỨNG DỤNG VÀ PHƯƠNG PHÁP ĐỊNH LƯỢNG CƠ BẢN CỦA VẬN TRÙ HỌC 2.1. Một số ứng dụng Các ứng dụng cơ bản của Vận trù học có thể được phân loại theo các lĩnh vực sau đây: - Lập kế hoạch sử dụng các phương tiện, bao gồm: xác định quy mô và địa điểm xây dựng xí nghiệp, lập kế hoạch cho bệnh viện, các hệ thống cung ứng dịch vụ quốc tế, xác định số lượng phương tiện cần thiết, sắp xếp phương án vận chuyển, bố trí kho hàng, phân công nhiệm vụ.
12. - Chế tạo, sản xuất: kiểm soát hàng dự trữ, cân bằng sản xuất và tiếp thị, lập tiến trình sản xuất, đảm bảo ổn định sản xuất. - Xây dựng: phân phối các dự trữ tài nguyên cho các dự án, xác định số thành viên của các đội công tác, duy trì tiến trình công tác, lập tiến trình dự án. - Đặt hàng, mua nguyên liệu: chuyển giao vật liệu, chính sách mua hàng và đặt lại hàng tối ưu. - Tiếp thị: xác định chi phí tiếp thị, thời điểm giới thiệu sản phẩm mới, chọn lựa danh mục sản phẩm hỗn hợp. - Tài chính: chính sách cổ tức, phân tích đầu tư và chọn lựa danh mục đầu tư. - Kế toán: lập kế hoạch luồng tiền, chính sách tín dụng, lập kế hoạch cho chiến lược kế toán nợ. - Chính sách nhân lực: tuyển dụng nhân viên, lập kế hoạch nhân lực, lập tiến trình bồi dưỡng cán bộ, cân bằng các kĩ năng. - Nghiên cứu và phát triển: Kiểm soát các dự án nghiên cứu và phát triển, lập kế hoạch phát triển sản phẩm mới. Chúng ta hãy xem xét một cách chi tiết hơn vấn đề trên qua một vài ứng dụng điển hình của Vận trù học/Khoa học quản lí như sau: - Bài toán lập kế hoạch nhân lực. Một công ti cần thường xuyên duy trì 1000 nhân viên, trong số đó có 70% nhân viên “cũ” (đã làm việc tại công ti từ một năm trở lên) và 30% nhân viên “mới” (làm việc dưới một năm). Theo các kết quả thống kê có được, trong số nhân viên mới thông thường 50% bỏ việc trong vòng 4 tháng đầu, 20% bỏ việc trong vòng 4 tháng tiếp theo, 10% bỏ việc trong 4 tháng kế tiếp và chỉ có 20 % không bỏ việc trong năm đầu tiên vào làm việc. Trong số nhân viên cũ, thông thường hàng năm có 30% bỏ việc (tức là khoảng 10% cho mỗi kì 4 tháng). Vậy công ti cần xác định tỉ lệ tuyển nhân viên mới hàng năm như thế nào để: i) duy trì ổn định được lượng lao động, ii) giảm lượng lao động hàng năm theo một tỉ lệ định trước, iii) tăng lượng lao động hàng năm theo một tỉ lệ định trước. - Bài toán phân công nhiệm vụ. Một nhóm 3 kĩ sư A, B và C được phân công hoàn thành 3 nhiệm vụ 1, 2 và 3. Cần giao cho mỗi kĩ sư một nhiệm vụ sao cho tổng số ngày công thực hiện 3 nhiệm vụ trên là thấp nhất, biết rằng kĩ sư A có thể hoàn thành các nhiệm cụ 1, 2, 3 theo thứ tự trong vòng 2, 6 và 3 ngày, còn số ngày như vậy cho các kĩ sư B và C là 8,4, 9 và 5, 7, 8. Bằng cách liệt kê các phương án phân công nhiệm vụ (có tất cả 3! = 6 phương án phân công), có thể tìm được ngay phương án phân công tối ưu là: phân công cho kĩ sư A nhiệm vụ 3, kĩ sư B nhiệm vụ 2 và kĩ sư C nhiệm vụ 1. Tuy nhiên, nếu bài toán được mở rộng khi cần phân công 20 nhiệm vụ cho 20 kĩ sư thì Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 12
13. phương pháp liệt kê (với tất cả là 20! ≈ 2,433×1018 phương án phân công) tỏ ra rất kém tác dụng. Như vậy cần phải nghiên cứu một phương pháp khác để giải quyết bài toán phân công nghiệm vụ tổng quát. 2.2. Các phương pháp định lượng Các phương pháp định lượng cơ bản thường được sử dụng trong Vận trù học/Khoa học quản lí bao gồm: - Các phương pháp tối ưu giải mô hình quy hoạch tuyến tính và phi tuyến, quy hoạch động và quy hoạch đa mục tiêu. - Các kĩ thuật/thuật toán chuyên dụng giải các mô hình mạng như bài toán vận tải, bài toán tìm đường đi ngắn nhất, mô hình mạng PERT, bài toán tìm luồng cực đại. - Kĩ thuật mô phỏng giải các mô hình hàng chờ/dịch vụ công cộng. - Phân tích Markov ứng dụng trong kinh doanh và quản lí. - Các phương pháp chọn lựa quyết định dựa trên Lí thuyết quyết định và Lí thuyết trò chơi. - Các mô hình quản lí hàng dự trữ. Do thời lượng có hạn, một số phương pháp khác của Vận trù học như các phương pháp dự báo, hệ chuyên gia, khai phá dữ liệu và tri thức không được đề cập tới trong giáo trình này. 2.3. Hệ thông tin quản lí Các tiêu chuẩn về số liệu. Các phương pháp định lượng hay kĩ thuật tính toán được đề cập trên đây thường đòi hỏi các số liệu đầu vào phải đảm bảo các tiêu chuẩn sau: - Chính xác: số liệu phải không có sai sót. - Chi phí hiệu quả: chi phí thu thập số liệu thấp hơn giá trị chúng có thể mang lại. - Cập nhật: số liệu phản ánh đúng các điều kiện hiện tại. - Tin cậy: số liệu phát sinh kết quả không có gì bất thường. - Dễ sử dụng: số liệu có thể được sử dụng thân thiện mà không phải sửa đổi gì thêm. Các tiêu chuẩn trên đây có thể có tính chất “thỏa hiệp”, có nghĩa là nếu một tiêu chuẩn nào đó trở nên tốt hơn thì cũng dẫn tới một tiêu chuẩn khác xấu đi. Chẳng hạn, chi phí lấy số liệu thấp thường ảnh hưởng tới tính chính xác và độ tin cậy của số liệu. Tuy nhiên, năm tiêu chuẩn này luôn là mục tiêu cần “cực đại hóa” khi thu thập số liệu. Khái niệm hệ thông tin quản lí. Có thể coi hệ thông tin quản lí là một hệ thống các số liệu/dữ liệu được thu thập, tổ chức, phân tích, xử lí và lưu trữ trên máy tính/mạng máy tính dưới dạng thông tin hỗ trợ các quyết định quản lí. Để ứng dụng thành công các
14. phương pháp định lượng của Vận trù học, chúng ta luôn cần thiết lập được một hệ thông tin quản lí đủ tốt nhằm cung cấp các số liệu cần thiết cho mô hình toán học của vấn đề cần giải quyết. Rõ ràng rằng, các số liệu thô thu thập được trong bước khảo sát thực tế và phát hiện vấn đề được biến đổi một cách thích hợp thành thông tin hỗ trợ ra quyết định. Chẳng hạn, các số liệu thô về hệ số lợi nhuận của một loại sản phẩm được biến đổi thành hệ số lợi nhuận (trung bình)/đơn vị sản phẩm, là một dạng thông tin hỗ trợ việc lập kế hoạch sản xuất sản phẩm này. Máy tính/mạng máy tính có rất nhiều điểm mạnh như: tính chính xác, tính nhất quán, bộ nhớ lớn, xử lí được nhiều số liệu và phép toán phức tạp, làm việc theo các quy tắc và chương trình định sẵn. Tuy nhiên, để thiết lập một hệ thông tin quản lí hiệu quả, cần xác định được các dạng thông tin hỗ trợ cần thiết giúp phát huy tốt nhất các ưu điểm suy luận sáng tạo và linh hoạt của người ra quyết định. Một hệ thông tin quản lí “nhiều máy tính quá” thường dẫn đến phương án có tính cơ giới, sự phản ứng thiếu linh hoạt và quyết định ở phạm vi hẹp. Trái lại, một hệ thông tin quản lí “nhiều tính người quá” thường dẫn đến sự phản ứng chậm chạp và sự hạn chế trong việc sử dụng số liệu cũng như khả năng tìm kiếm và đánh giá các phương án thay thế. Đây chính là các vấn đề cần chú trọng khi các chuyên gia Vận trù học và Công nghệ thông tin cùng nhau xem xét và xây dựng một hệ thông tin quản lí. Hệ thông tin quản lí có thể được phân ra ba loại cơ bản: hệ thống cho đầu ra là các kiểu báo cáo, hệ thống trả lời các truy vấn dạng “what - if” và hệ hỗ trợ ra quyết định (Decision Support System - DSS). Các hệ hỗ trợ ra quyết định là loại hệ thông tin quản lí hoàn thiện nhất cho phép tích hợp quá trình ra quyết định tương tác người - máy tính với các cơ sở dữ liệu và các mô hình định lượng nhằm hỗ trợ trực tiếp việc đưa ra quyết định. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 14
15. Chương II MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU 1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 1.1. Phát biểu mô hình quy hoạch tuyến tính Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy hoạch tuyến tính hay bài toán quy hoạch tuyến tính (BTQHTT), mà trong đó chúng ta muốn tối ưu hóa (cực đại hóa hay cực tiểu hoá) hàm mục tiêu: z = c1x1 + c2x2 + cnxn → Max (Min), với các điều kiện ràng buộc: a11x1 + a12x2 + +a1nxn ≤ b1 a21x1 + a22x2 + +a2nxn ≤ b2 am1x1 + am2x2 + +amnxn ≤ bm x1, x2, , xn ≥ 0 (điều kiện không âm). Trong trường hợp tổng quát, BTQHTT có thể bao gồm các ràng buộc dạng ≥, ≤ hoặc dạng =, các biến có thể có dấu ≥ 0, ≤ 0 hoặc dấu tùy ý. Ví dụ 1: z = 8x1 + 6x2 → Max, với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. BTQHTT trên đây chính là một bài toán quyết định. Cần tìm các giá trị của các biến quyết định x1, x2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất hai loại sản phẩm I và II. Để sản xuất ra một đơn vị sản phẩm I cần có 4 đơn vị nguyên liệu loại A và 2 đơn vị nguyên liệu loại B, các chỉ tiêu đó cho một đơn vị sản phẩm loại II là 2 và 4. Lượng nguyên liệu dự trữ loại A và B hiện có là 60 và 48 (đơn vị). Bộ máy quản lí cần đưa ra quyết định nên lựa chọn phương án sản xuất nào để triển khai nhằm đạt lợi nhuận lớn nhất, biết lợi nhuận trên mỗi đơn vị sản phẩm bán ra là 8 và 6 (đơn vị tiền tệ) cho các sản phẩm loại I và II.
16. Phương pháp đồ thị giải BTQHTT hai biến Phương pháp đồ thị có ý nghĩa minh hoạ và giúp hiểu bản chất vấn đề. Bước 1: Vẽ miền ràng buộc/miền các phương án khả thi, là tập hợp các phương án khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ số (x1, x2) còn gọi là véc tơ nghiệm, thoả mãn tất cả các ràng buộc đã có (xem hình II.1). x2 30 4x1 + 2x2 = 60 1 A 8 B 4 2x1 + 4x2 = 48 C O 3 6 15 24 x1 Hình II.1. Phương pháp đồ thị giải bài toán quy hoạch tuyến tính − Trước hết chúng ta vẽ đồ thị 4x1 + 2x2 = 60 bằng cách xác định hai điểm trên đồ thị: (0, 30) và (15, 0). Đồ thị trên là một đường thẳng chia mặt phẳng làm hai nửa mặt phẳng: một phần gồm các điểm (x1, x2) thoả mãn 4x1 + 2x2 ≤ 60; một phần thoả mãn 4x1 + 2x2 ≥ 60. Ta tìm được nửa mặt phẳng thoả mãn 4x1 + 2x2 ≤ 60. − Tương tự, có thể vẽ đồ thị 2x1 + 4x2 = 48 bằng cách xác định hai điểm thuộc đồ thị (0, 12) và (24, 0). Sau đó tìm nửa mặt phẳng thoả mãn 2x1 + 4x2 ≤ 48. − Lúc này, giao của hai nửa mặt phẳng tìm được trên cho ta tập hợp các điểm (x1, x2) thoả mãn hai ràng buộc đầu tiên. Tuy nhiên, để thoả mãn điều kiện không âm của các biến, ta chỉ xét các điểm nằm trong góc phần tư thứ nhất. Vậy miền các phương án khả thi là miền giới hạn bởi tứ giác OABC. Bước 2: Trong miền (OABC) ta tìm điểm (x1, x2) sao cho z = 8x1 + 6x2 đạt giá trị lớn nhất. Cách 1: Dùng đường đồng mức. Tùy theo giá trị của x1, x2 mà z có mức giá trị khác nhau. − Vẽ đường đồng mức: 8x1 + 6x2 = c ở mức c = 24, (ta có thể chọn giá trị c bất kì, nhưng chọn c = 24 là bội số chung của 6 và 8 để việc tìm toạ độ các điểm cắt hai trục toạ độ thuận lợi hơn). Chúng ta dễ dàng tìm được hai điểm nằm trên đường đồng mức là (0, 4) và (3, 0). Các điểm nằm trên đường đồng mức này đều cho giá trị hàm mục tiêu z = 24. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 16
17. − Tương tự, có thể vẽ đường đồng mức thứ hai: 8x1 + 6x2 = 48 đi qua hai điểm (0, 8) và (6, 0). Chúng ta nhận thấy, nếu tịnh tiến song song đường đồng mức lên trên theo r hướng của véc tơ pháp tuyến n (8, 6) thì giá trị của hàm mục tiêu z = 8x1 + 6x2 tăng lên. Vậy giá trị z lớn nhất đạt được khi đường đồng mức đi qua điểm B(12, 6) (tìm được x1 = 12, x2 = 6 bằng cách giải hệ phương trình 4x1 + 2x2 = 60 và 2x1 + 4x2 = 48). Kết luận: Trong các phương án khả thi thì phương án tối ưu là (x1, x2) = (12, 6). Tại phương án này, giá trị hàm mục tiêu là lớn nhất zmax = 8 × 12 + 6 × 6 = 132. Nhận xét: Phương án tối ưu của bài toán trên (hay các BTQHTT khác, nếu có) luôn đạt được tại một trong các đỉnh của miền phương án khả thi D (là một tập lồi đa diện trong trường hợp BTQHTT tổng quát) hay còn gọi là các điểm cực biên (chính xác hơn, miền điểm cực biên là điểm thuộc miền D, mà không thể tìm được một đoạn thẳng nào cũng thuộc miền D nhận điểm đó là điểm trong). Nhận xét trên đây là một định lí toán học đã được chứng minh một cách tổng quát trong các giáo trình môn học Tối ưu hoá. Nói một cách hình ảnh, muốn đạt được phương án tối ưu cho các BTQHTT thì cần phải “mạo hiểm” đi xét các điểm cực biên của miền phương án khả thi. Cách 2: Từ nhận xét trên, để tìm phương án tối ưu ta chỉ cần so sánh giá trị của hàm mục tiêu tại các điểm cực biên của miền phương án. Tính giá trị z tại O(0, 0): z(0, 0) = 0; tại A(0, 12): z(0, 12) = 72; tại C(15,0): z(15, 0) = 120; tại B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. Vậy zmax = 132. Nhận xét: Muốn tìm phương án tối ưu của BTQHTT ta xuất phát từ một điểm cực biên nào đó, tìm cách cải thiện hàm mục tiêu bằng cách đi tới điểm cực biên kề nó. Tiếp tục như vậy cho tới khi tìm được phương án tối ưu. Trong trường hợp BTQHTT có phương án tối ưu thì quy trình giải này bao gồm hữu hạn bước (do số điểm cực biên là hữu hạn). Sơ đồ khối Bắt đầu Nhập dữ liệu Tìm điểm cực biên xuất phát Kiểm tra Sai Tìm điều kiện tối ưu điểm cực biên kề tốt hơn Đúng In và lưu trữ kết quả Dừng Hình II.2. Sơ đồ khối giải BTQHTT
18. Đối với BTQHTT đang xét, quy trình giải được minh hoạ như sau: O(0, 0) → A(0,12) → B(12,6) dừng z = 0 → z = 72 → z = 132 hoặc: O(0, 0) → C(15, 0) → B(12, 6) dừng z = 0 → z = 120 → z = 132. Quy trình giải BTQHTT tổng quát có sơ đồ khối giản lược như trình bày trên hình II.2. Trong sơ đồ trên, vì mục đích trình bày vấn đề đơn giản, chúng ta không đề cập tới các trường hợp khi BTQHTT có miền phương án là tập rỗng (lúc đó ta không tìm được phương án xuất phát) cũng như khi ta không tìm được điểm cực biên kề tốt hơn mặc dù điều kiện tối ưu chưa thoả mãn (lúc đó tập các giá trị hàm mục tiêu z không bị chặn). 1.2. Phương pháp đơn hình giải BTQHTT dạng chính tắc Đây là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ 1 trên đây, trước hết chúng ta cần đưa BTQHTT về dạng chính tắc bằng cách thêm vào các biến bù không âm x3 và x4 như sau: z = 8x1 + 6x2 + 0x3 + 0x4 → Max với các ràng buộc: 4x1 + 2x2 + x3 = 60 2x1 + 4x2 + x4 = 48 x1, x2, x3, x4 ≥ 0. Một cách tổng quát, BTQHTT dạng chính tắc là bài toán với các biến không âm, các ràng buộc với dấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi phương trình bắt buộc phải có một biến đứng độc lập với hệ số +1. Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trình bày trong bảng II.1. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình bước 1: − Cột 1 là cột hệ số hàm mục tiêu ứng với các biến cơ sở đã chọn. Phương án xuất phát có thể chọn là x1 = x2 = 0 (đây chính là điểm gốc toạ độ O(0, 0)), do đó x3 = 60, x4 = 48). Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên trong phương án chưa có đơn vị sản phẩm loại I hay II được sản xuất ra (chỉ “sản xuất” ra các lượng nguyên liệu dư thừa, ta cũng nói là các “sản phẩm” loại III và IV) và giá trị hàm mục tiêu z tạm thời bằng 0. Các biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại tương ứng chưa được sử dụng hết. Ta gọi các biến x3 và x4 là các biến cơ sở vì chúng có Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 18
19. giá trị lớn hơn 0 còn x1 và x2 là các biến ngoài cơ sở vì chúng có giá trị bằng 0. Với bài toán có hai ràng buộc, tại mỗi bước chỉ có hai biến cơ sở. − Cột 2 là cột các biến cơ sở. Trong cột 3 (cột phương án) cần ghi các giá trị của các biến cơ sở đã chọn. − Các cột tiếp theo là các cột hệ số trong các điều kiện ràng buộc tương ứng với các biến x1, x2, x3 và x4 của bài toán đã cho. Bảng II.1. Các bảng đơn hình giải BTQHTT Hệ số hàm mục c1 = 8 c2 = 6 c3 = 0 c4 = 0 Biến cơ sở Phương án tiêu cj x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng Δj = cj − zj Δ1 = 8 Δ2 = 6 Δ3 = 0 Δ4 = 0 8 x1 15 1 1/2 1/4 0 0 x4 18 0 3 −1/2 1 Hàng z z0 = 120 z1 = 8 z2 = 4 z3 = 2 z4 = 0 Hàng Δj = cj − zj Δ1 = 0 Δ2 = 2 Δ3 = −2 Δ4 = 0 8 x1 12 1 0 1/3 −1/6 6 x2 6 0 1 −1/6 1/3 Hàng z z0 = 132 8 6 5/3 2/3 Hàng Δj = cj − zj 0 0 −5/3 −2/3 Phân tích bảng đơn hình bước 1 − Hệ số ứng với biến x1 trên hàng thứ nhất là a11 = 4 có nghĩa là tỉ lệ thay thế riêng giữa một đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 (giải thích: xét phương trình/ràng buộc thứ nhất 4x1 + 2x2 + x3 = 60, x1 tăng một đơn vị thì x3 phải giảm bốn đơn vị nếu giữ nguyên x2). Tương tự ta có thể giải thích được ý nghĩa của các hệ số aij khác cho trên hàng 1 và hàng 2 trong bảng đơn hình bước 1. − Chúng ta xét hàng z của bảng đơn hình. Để tính z1, cần áp dụng công thức z1 = (cột hệ số của hàm mục tiêu) × (cột hệ số của biến x1) = 0×4 + 0×2 = (giá một đơn vị sản phẩm loại III)×(tỉ lệ thay thế riêng loại I/loại III) + (giá một đơn vị sản phẩm loại IV) × (tỉ lệ thay thế riêng loại I/loại IV) = tổng chi phí phải bỏ ra khi đưa thêm một đơn vị sản phẩm loại I vào phương án sản xuất mới = 0. Các giá trị zj, với j = 1, 2, 3, 4, được tính tương tự và chính là các chi phí khi đưa một thêm một đơn vị sản phẩm loại xj vào phương án sản xuất mới. Còn z0 là giá trị của hàm mục tiêu đạt được tại phương án đang xét: z0 = (cột hệ số của hàm mục tiêu)× (cột phương án) = 0×60 + 0×48 = 0.
20. − Trên hàng Δj cần ghi các giá trị Δj, j = 1, 2, 3, 4, tính theo công thức Δj = cj -zj = lợi nhuận trên một đơn vị sản phẩm - chi phí trên một đơn vị sản phẩm. Vậy Δj là "lãi biên"/một đơn vị sản phẩm khi đưa thêm một đơn vị sản phẩm loại j vào phương án sản xuất mới. Nếu Δj > 0 thì hàm mục tiêu còn tăng được khi ta đưa thêm các đơn vị sản phẩm loại j vào phương án sản xuất mới. Có thể chứng minh được Δj chính là đạo hàm riêng ∂z/∂xj của hàm mục tiêu z theo biến xj. Như vậy, x1 tăng lên 1 thì z tăng lên 8 còn x2 tăng lên 1 thì z tăng lên 6. Do Δ1 và Δ2 đều dương nên vẫn còn khả năng cải thiện hàm mục tiêu khi chuyển sang (hay “xoay sang”) một phương án cực biên kề tốt hơn (quay lại nhận xét ở phần giải bài toán bằng phương pháp đồ thị: điểm cực biên kề của điểm (0, 0) có thể là A(0, 12) hay C(15, 0)). Thủ tục xoay Bước 1: Chọn cột xoay là cột có Δj > 0 tức là chọn biến xj làm biến cơ sở mới do xj tăng kéo theo hàm mục tiêu tăng. Ở đây ta chọn đưa x1 vào (đánh dấu √ ở cột Δ1). Bước 2: Chọn hàng xoay để xác định đưa biến nào ra khỏi số biến cơ sở (vì tại mỗi bước số biến cơ sở là không thay đổi). Để chọn hàng xoay, ta thực hiện quy tắc “tỉ số dương bé nhất" bằng cách lấy cột phương án (60, 48)T chia tương ứng cho cột xoay (4, 2)T để chọn tỉ số bé nhất. Một điều cần chú ý là ta chỉ xét các tỉ số có mẫu số dương. Vì Min{60/4, 48/2} = 60/4 đạt được tại hàng đầu, nên ta đánh dấu √ vào hàng xoay là hàng đầu (hàng tương ứng với biến x3). Do đó cần đưa x3 ra khỏi các biến cơ sở. Bước 3: Chọn phần tử xoay nằm trên giao của hàng xoay và cột xoay. Bước 4: Xoay sang bảng đơn hình mới, xác định các biến cơ sở mới để điền vào cột biến cơ sở, đồng thời thay các giá trị trong cột hệ số hàm mục tiêu. Sau đó, tính lại các phần tử của hàng xoay bằng cách lấy hàng xoay cũ chia cho phần tử xoay để có hàng mới tương ứng. Bước 5: Các phần tử còn lại của bảng đơn hình mới được tính theo quy tắc "hình chữ nhật": (1)mới = (1)cũ - (2)cũ× (4)cũ/(3)cũ, trong đó (3) là đỉnh tương ứng với phần tử xoay (xem hình II.3). (2) (3) Chẳng hạn: (1)cũ = 4, 2(cũ) = 2 (3)cũ = phần tử xoay = 4, (4)cũ = 2 ⇒ (1)mới 2 = 4 − 2 × = 3. 4 (1) (4) Hình II.3. Quy tắc hình chữ nhật Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 20
21. Giải thích: Các bước xoay trên đây chỉ là phép biến đổi tương đương hệ phương trình 4x1 + 2x2 + x3 = 60 (a) 2x1 + 4x2 + x4 = 48 (b) để có hệ x1 + (1/2)x2 + (1/4)x3 = 15 (a’) 0x1 + 3x2 − (1/2)x3 + x4 = 18. (b’) bằng cách lấy phương trình (a) chia cho 4 (phần tử xoay) để có (a’), rồi lấy (b) trừ bớt 2 × (a)/4 để có (b’). Đây chính là nội dung của bước 4 và bước 5. Còn bước 3 sẽ đảm bảo rằng giá trị của các biến cơ sở mới không âm (x1 = 15, x4 = 18). Áp dụng thủ tục xoay cho các phần tử nằm trên hàng 1 và 2 của bảng đơn hình bước 1, sau đó tính các giá trị trên hàng zj và Δj tương tự như khi lập bảng đơn hình bước 1, chúng ta sẽ nhận được bảng đơn hình bước 2. Phân tích bảng đơn hình bước 2 Bảng bước 2 có thể được phân tích tương tự như bảng bước 1. Cần chú ý rằng lúc này ta đang ở vị trí của điểm C(15, 0) vì x1 = 15 còn x2 = 0; giá trị của hàm mục tiêu là z0 = 120 đã được cải thiện hơn so với bước 1. Ta thấy Δ2 = 2 > 0 nên còn có thể cải thiện hàm mục tiêu bằng cách chọn biến x2 làm biến cơ sở mới. Thực hiện các bước xoay sang phương án cực biên kề tốt hơn, chúng ta sẽ có bảng đơn hình bước 3. Phân tích bảng đơn hình bước 3 Tại bảng đơn hình bước 3 ta thấy điều kiện tối ưu đã được thoả mãn (Δj ≤ 0 ∀j=1, 2, 3, 4) nên không còn khả năng cải thiện phương án. Phương án tối ưu đã đạt được tại x1 = 12, x2 = 6, x3 = 0, x4 = 0, tức là tại điểm cực biên B(12, 6) với giá trị zmax = 132. Khung thuật toán đơn hình giải BTQHTT dạng chính tắc Sau đây là khung thuật toán của phương pháp đơn hình được phát biểu cho BTQHTT cực đại hóa dạng chính tắc. Bước khởi tạo - Tìm một phương án cực biên ban đầu. - Tính Δj = cj - zj, ∀j = 1, n , trong đó n là số biến của bài toán đang xét. Các bước lặp
22. Bước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu Δj = cj - zj ≤ 0, ∀j = 1, n đã được thoả mãn thì in/lưu trữ kết quả của bài toán và chuyển sang bước kết thúc. Bước 2: Nếu tồn tại một chỉ số j sao cho Δj > 0 thì tiến hành thủ tục xoay gồm năm bước đã biết, tính lại các Δj, ∀j = 1, n và quay lại bước 1 (Chú ý: Trong trường hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị chặn, in/lưu trữ kết quả của bài toán và chuyển sang bước kết thúc). Bước kết thúc. Dừng. Chú ý: - Đối với các BTQHTT cần cực tiểu hóa hàm mục tiêu thì điều kiện tối ưu (hay tiêu chuẩn dừng) là Δj ≥ 0 ∀j (nếu tồn tại j mà Δj ≤ 0 thì cần tiếp tục cải thiện hàm mục tiêu bằng cách chọn cột j làm cột xoay ). - Trong thực tiễn giải các BTQHTT dạng tổng quát có thể xảy ra trường hợp không tìm được phương án xuất phát. Lúc này có thể kết luận mô hình đã thiết lập có các điều kiện ràng buộc quá chặt chẽ, cần xem xét nới lỏng các điều kiện này. - Trong trường hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị chặn trên (đối với các BTQHTT dạng Max) hoặc không bị chặn dưới (đối với các BTQHTT dạng Min). Khi đó dừng quá trình giải và kết luận mô hình quy hoạch tuyến tính đã thiết lập không phù hợp với thực tế. 1.3. Phương pháp đơn hình hai pha giải BTQHTT dạng tổng quát Đưa BTQHTT về dạng chính tắc Ví dụ 1: (Trường hợp các ràng buộc đều có dấu ≤) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+ 2x≤ 60 ⎪ ⎨2x12+ 4x≤ 48 ⎪ ⎩x,x12≥ 0. Đưa BTQHTT về dạng chính tắc như đã biết bằng cách thêm hai biến bù (slack variables) x3 và x4. Ta có BTQHTT dạng chính tắc là: z = 8x1 + 6x2 + 0x3 + 0x4 → Max ⎧4x123+ 2x+= x 60 ⎪ ⎨2x124+ 4x+= x 48 ⎪ ⎩x,x,x,x1234≥ 0. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 22
23. Lúc này, trong hệ hai điều kiện ràng buộc đã có đủ hai biến đứng độc lập trong từng phương trình với hệ số +1, nên đã có thể tìm được phương án cực biên xuất phát để bắt đầu quá trình giải bài toán. Ví dụ 2: (Trường hợp có biến không dương) z = 8x1 − 6x2 → Max với các ràng buộc: ⎧4x123++≤ 2x x 60 ⎪ ⎨2x124++≤ 4x x 48 ⎪ ⎩x1234≥≤≥≥ 0,x 0,x 0,x 0. Lúc này muốn giải bài toán bằng phương pháp đơn hình ta phải đổi biến x'2 = −x2. Ta có BTQHTT với các biến đều không âm. z = 8x1 + 6x'2 → Max với các ràng buộc: ⎧4x123− 2x '+≤ x 60 ⎪ ⎨2x124− 4x '+≤ x 48 ⎪ ⎩x1234 ,x' ,x ,x≥ 0. Ví dụ 3: (Trường hợp có biến với dấu tuỳ ý) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+ 2x≤ 60 ⎪ ⎨2x12+ 4x≤ 48 ⎪ ⎩x0,x.12≥ có dấu tuỳ ý. Lúc này ta viết biến x2 dưới dạng x2 = x'2 − x''2 với ⎧x'22= max[0,x ] ⎧x'2 ≥ 0 ⎨ thì đảm bảo ⎨ ⎩x''22=− max[0, x ] ⎩x''2 ≥ 0. Các ràng buộc sẽ là ⎧4x1223+ 2x '−+= 2x '' x 60 ⎪ ⎨2x1224+−+= 4x ' 4x ' x 48 ⎪ ⎩x12 ,x' ,x'',x 234 ,x≥ 0. Bài toán với hàm mục tiêu là: z = 8x1 + 6x'2 − 6x''2 + 0x3 + 0x4 và các điều kiện ràng buộc trên là BTQHTT dạng chính tắc. Ví dụ 4: (Trường hợp có điều kiện ràng buộc với dấu ≥ hoặc dấu =)
24. z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+≤ 2x 60 ⎪ (a) ⎨2x12+≥ 4x 48 ⎪ ⎩x0,x0.12≥≥ Ta thêm các biến bù x3 (slack variable) mang dấu “+”, x4 (surplus variable) mang dấu “−” để có hệ điều kiện ràng buộc sau (lúc này hai ràng buộc đều có dấu =): ⎧4x123++= 2x x 60 ⎪ (b) ⎨2x124+−= 4x x 48 ⎪ ⎩x,x,x,x1234≥ 0. Phải thêm biến giả x5 (x5 gọi là lượng vi phạm của phương trình thứ hai) để được hệ điều kiện ràng buộc ⎧42xxx123++= 60 ⎪ (c) ⎨24xxxx1+−+= 245 48 ⎪ ⎩xxxxx12345,,,,≥ 0. Lúc này, đã có đủ hai biến đứng độc lập trong từng phương trình với hệ số +1, nên đã có thể tìm được phương án cực biên xuất phát để bắt đầu quá trình giải bài toán bằng phương pháp đơn hình với hàm mục tiêu là z = 8x1 + 6x2 + 0x3 + 0x4 − Mx5 → Max, trong đó M ≈ +∞ và biểu thức −Mx5 gọi là lượng phạt (đánh thuế). Bài toán đã được đưa về dạng chính tắc. Lượng vi phạm x5 càng lớn thì hàm mục tiêu càng giảm, giá trị của hàm mục tiêu chỉ có thể đạt Max khi x5 = 0. Kết luận: Bao giờ cũng đưa được BTQHTT bất kì (các biến có dấu tuỳ ý, các ràng buộc có thể ≤, ≥, =) về dạng chính tắc. Phương pháp đơn hình mở rộng Phương pháp đơn hình mở rộng còn gọi là phương pháp đánh thuế M được áp dụng để để giải BTQHTT có biến giả. Ví dụ 5: Sau khi thêm vào các biến bù và biến giả, BTQHTT trong ví dụ 4 được đưa về dạng chính tắc (trong hàm mục tiêu tất cả các biến giả đều có hệ số là -M nên bài toán được gọi là bài toán M). Max z = 8x1 + 6x2 +0x3 + 0x4 − Mx5 (trong đó M ≈ +∞) với các ràng buộc Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 24
25. ⎧4x123++= 2x x 60 ⎪ (c)⎨ 2x1245+−+= 4x x x 48 ⎪ ⎩x,x,x,x,x12345≥ 0. Cách 1: Có thể giải BTQHTT với các điều kiện ràng buộc (a) bằng phương pháp đồ thị để nhận được kết quả: phương án tối ưu là (x1 = 0, x2 = 30) và zmax = 180. Cách 2: Giải BTQHTT với các điều kiện ràng buộc (c) bằng cách lập bảng đơn hình như thông thường nhưng chú ý hệ số M ≈ +∞ (xem bảng II.2). Tại bảng đơn hình cuối cùng, ta thấy Δj ≤ 0 ∀j nên phương án tối ưu đã đạt được với x2 = 30, x4 = 72, các xj khác = 0 và zMax = 180. Chú ý: − Khi một biến giả đã được đưa ra khỏi cơ sở thì không bao giờ quay lại nữa. Do đó ta có thể xoá cột biến giả đó khỏi bảng đơn hình. − Nếu dấu hiệu dừng xuất hiện (Δj ≤ 0 ∀j) nhưng vẫn còn biến giả với giá trị dương trong số các biến cơ sở thì điều này chứng tỏ bài toán ban đầu không thể có phương án khả thi (có thể chứng minh bằng phản chứng). Bảng II.2. Các bảng đơn hình giải bài toán M Hệ số hàm mục Phương 8 6 0 0 −M Biến cơ sở tiêu án x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 −M x5 48 2 4 0 −1 +1 Hàng z z0 = −48M z1 = −2M z2 = −4M z3 = 0 z4 = M z5 = −M Hàng Δj Δ1 = 8+2M Δ2 = 6+4M Δ3 = 0 Δ4 = −M Δ5 = 0 0 x3 36 3 0 1 1/2 −1/2 6 x2 12 1/2 1 0 −1/4 1/4 Hàng z 72 3 6 0 −3/2 3/2 Hàng Δj 5 0 0 3/2 −M − 3/2 0 x4 72 6 0 2 1 −1 6 x2 30 2 1 1/2 0 0 Hàng z 180 12 6 3 0 0 Hàng Δj −4 0 −3 0 −M Phương pháp đơn hình hai pha Với ví dụ trên (xem bảng II.2) ta thấy quá trình giải chia làm hai pha: pha 1 nhằm giải bài toán M cho tới khi biến giả (x5) được đưa ra khỏi số biến cơ sở (lúc này có phương án cực biên xuất phát cho bài toán (b)) và pha 2 nhằm tìm phương án tối ưu cho bài toán (b).
26. Phương pháp đơn hình mở rộng như trình bày trên đây có khó khăn trong việc khai báo giá trị của hệ số M ≈ +∞ và tính toán các giá trị ∆j liên quan tới hệ số M. Để khắc phục các điểm này, chúng ta xét phương pháp đơn hình hai pha: pha 1 nhằm giải bài toán ω để tìm cách đưa các biến giả ra khỏi số biến cơ sở (lúc này có phương án cực biên xuất phát cho bài toán (b)) và pha 2 nhằm tìm phương án tối ưu cho bài toán (b). Ví dụ 6: Xét BTQHTT (bài toán 1) z = 8x1 + 6x2 → Max, với các ràng buộc: ⎧4x12+≤ 2x 60 ⎪ (a)⎨ 2x12+≥ 4x 48 ⎪ ⎩x,x12≥ 0, hay BTQHTT dạng chuẩn tắc (bài toán 2) tương đương với nó là: z = 8x1 + 6x2 +0x3 + 0x4 → Max, với các ràng buộc ⎧4x123++= 2x x 60 ⎪ (b)⎨ 2x124+−= 4x x 48 ⎪ ⎩x,x,x,x1234≥ 0. Để tìm phương án cực biên xuất phát cho BTQHTT dạng chuẩn tắc trên đây chúng ta cần thực hiện pha 1 (hàm mục tiêu ω là tổng của tất cả các biến giả). Pha 1: Giải bài toán ω (bài toán 3): ω = x5 → Min, với các ràng buộc ⎧4x123++= 2x x 60 ⎪ (c)⎨ 2x1245+−+= 4x x x 48 ⎪ ⎩x,x,x,x,x12345≥ 0. Bảng II.3. Các bảng đơn hình pha 1 Hệ số hàm Phương 0 0 0 0 1 Biến cơ sở mục tiêu án x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 1 x5 48 2 4 0 −1 +1 Hàng z z0 = 48 z1 = 2 z2 = 4 z3 = 0 z4 = −1 z5 = 1 Hàng Δj Δ1 = −2 Δ2 = −4 Δ3 = 0 Δ4 = 1 Δ5 = 0 0 x3 36 3 0 1 1/2 −1/2 0 x2 12 1/2 1 0 −1/4 1/4 Hàng z 0 0 0 0 0 0 Hàng Δj 0 0 0 0 1 Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 26
27. Như vậy trong ví dụ này, như trình bày trong bảng II.3, sau hai bước chúng ta đã tìm được phương án tối ưu cho bài toán ω. Một cách tổng quát khi giải xong bài toán ω có thể xảy ra ba trường hợp sau đây: − Trường hợp 1: Tìm được phương án tối ưu của bài toán ω với giá trị ωMin = 0, không chứa các biến giả trong số các biến cơ sở (như trong ví dụ trên). − Trường hợp 2: Tìm được phương án tối ưu của bài toán ω với giá trị ωMin = 0, có chứa các biến giả trong số các biến cơ sở (lúc này các biến giả nằm trong cơ sở đều có giá trị bằng 0). − Trường hợp 3: Tìm được phương án tối ưu của bài toán ω với giá trị ωMin > 0, có chứa các biến giả trong số các biến cơ sở (lúc này có một số biến giả nằm trong cơ sở đều có giá trị dương). Có thể chứng minh được rằng trong trường hợp 1, bài toán 2 có phương án cực biên xuất phát như tìm được trong bảng đơn hình tối ưu sau khi gạch bỏ đi tất cả các cột biến giả. Trong trường hợp 2, bài toán 2 có phương án cực biên xuất phát như tìm được trong bảng đơn hình tối ưu sau khi gạch bỏ đi tất cả các cột biến giả và các hàng chứa biến giả (các hàng bị gạch đi tương ứng với các phương trình phụ thuộc tuyến tính vào các phương trình còn lại trong hệ điều kiện ràng buộc của BTQHTT dạng chuẩn tắc). Còn trong trường hợp 3, BTQHTT dạng chính tắc không có phương án khả thi nên cũng không có phương án tối ưu. Trong các trường hợp 1 và 2, chúng ta cần chuyển sang pha 2 để tiếp tục đi tìm phương án tối ưu cho bài toán 2 từ phương án cực biên xuất phát tìm được bằng cách thay các hệ số hàm mục tiêu và tính lại các giá trị của hàng zj và hàng ∆j. Pha 2: Xét bài toán 2: z = 8x1 + 6x2 +0x3 + 0x4 → Max, với các ràng buộc ⎧4x123++= 2x x 60 ⎪ (b)⎨ 2x124+−= 4x x 48 ⎪ ⎩x,x,x,x1234≥ 0, Hay BTQHTT dạng chính tắc tương đương với nó: z = 8x1 + 6x2 +0x3 + 0x4 → Max, với các ràng buộc 1 ⎧3x123+++ 0x 3x2 x 4 = 36 ⎪ 11 (b′ )⎨ 24 x12++ x 0x 3 − x 4 = 12 ⎪ ⎩x,x,x,x1234≥ 0. Các bảng đơn hình của pha 2 được trình bày trong bảng II.4. Bảng II.4. Các bảng đơn hình pha 2 Hệ số hàm Biến Phương 8 6 0 0 mục
28. tiêu cơ sở án x1 x2 x3 x4 0 x3 36 3 0 1 1/2 6 x2 12 1/2 1 0 −1/4 Hàng z 72 3 6 0 −3/2 Hàng Δj 5 0 0 3/2 0 x4 72 6 0 2 1 6 x2 30 2 1 1/2 0 Hàng z 180 12 6 3 0 Hàng Δj −4 0 −3 0 Chú ý: So sánh các bảng II.3 và II.4 với bảng II.2, có thể thấy rằng phương pháp hai pha và phương pháp đơn hình mở rộng thực chất là hoàn toàn tương đương với nhau. Nhưng lập trình tính toán dựa trên phương pháp hai pha là dễ dàng hơn nhiều do tránh được việc khai báo giá trị của hệ số M ≈ +∞ và tính toán các giá trị ∆j không liên quan tới hệ số M. 1.4. Phương pháp cắt Gomory giải BTQHTT nguyên Ví dụ 7. Xét BTQHTT nguyên: Max z = x1 + 4x2 với các ràng buộc 2x1 + 4x2 ≤ 7 10x1 + 3x2 ≤ 15 x1, x2 ≥ 0 x1, x2 nguyên. Cần tìm các giá trị nguyên của các biến quyết định x1, x2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. Dạng tổng quát của BTQHTT nguyên cũng giống như dạng tổng quát của BTQHTT đã nêu trong mục 1.1, có bổ sung thêm điều kiện nguyên của các biến quyết định. Đưa BTQHTT nguyên trên đây về dạng chính tắc. Max z = x1 + 4x2 + 0x3 + 0x4, với các ràng buộc 2x1 + 4x2 + x3 = 7 (a) 10x1 + 3x2 + x4 = 15 x1, x2, x3, x4 ≥ 0 x1, x2, x3, x4 nguyên. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 28
29. Trước hết ta giải BTQHTT không nguyên tương ứng, tức là tạm thời bỏ qua điều kiện nguyên của các biến (xem bảng II.5). Bảng II.5. Các bảng đơn hình giải BTQHTT nguyên Hệ số hàm c1 = 1 c2 = 4 c3 = 0 c4 = 0 Biến cơ sở Phương án mục tiêu cj x1 x2 x3 x4 Bảng đơn hình bước 1 0 x3 7 2 4 1 0 0 x4 15 10 3 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng Δj = cj - zj Δ1 = 1 Δ2 = 4 Δ3 = 0 Δ4 = 0 Bảng đơn hình bước 2 4 x2 7/4 1/2 1 1/4 0 0 x4 39/4 17/2 0 - 3/4 1 Hàng z z0 = 7 z1 = 2 z2 = 4 z3 = 1 z4 = 0 Hàng Δj = cj - zj Δ1 = - 1 Δ2 = 0 Δ3 = - 1 Δ4 = 0 Như vậy, phương án tối ưu ở bước 2 chưa thỏa mãn điều kiện nguyên. Tại bảng đơn hình bước 2 của bảng II.5, BTQHTT nguyên đã được biến đổi tương đương về dạng sau: Max z = x1 + 4x2 + 0x3 + 0x4, với các ràng buộc 1 1 7 x1 + x2 + x3 = 2 4 4 17 3 39 (b) x1 + - x2 + x4 = 2 4 4 x1, x2, x3, x4 ≥ 0; x1, x2, x3, x4 nguyên. Xét phương trình (xem bảng đơn hình bước 2 của bảng II.5): 11711 7 xx+ += x ⇔ xxx+ +=. 24412 3 21324 4 Một cách tổng quát chúng ta có thể viết: xzxz+ = , trong đó JN là tập các rrjr∑ j0 jj∈ N chỉ số tương ứng với các biến ngoài cơ sở. Còn xr là biến cơ sở nằm trong phương trình đang xét. Giả sử zzf=+⎡⎤ với ⎡z ⎤ là phần nguyên và f là phần lẻ của z . Lúc rrrjjj⎣⎦ ⎣ rj ⎦ rj rj đó có: x++=+ ([z ] f )x [z ] f ⇔ x[z]x[z]ffx+ −=− . rrrjrr∑ jj 00 rrjrrxj∑∑j00j jj∈ N jj∈∈NN jj Vế trái bắt buộc là số nguyên theo điều kiện của BTQHTT nguyên nên vế phải phải là số nguyên nhỏ hơn 1 (do vế phải f < 1). Vậy vế phải luôn nhỏ hơn hoặc bằng 0. r0 Trong ví dụ trên ta có: x[z]x[z]ffx+−=−. Nếu đặt vế phải 22j22xj∑∑j00j j∈∈ {1,3} j {1,3} là - x5 (với điều kiện x5 nguyên và x5 ≥ 0) thì có phương trình mới sau đây:
30. 11 3 −fx + x =− f ⇔− x − x + x =− . ∑ 2jj0 5 2 1 3 5 j{1,3}∈ 24 4 Do phương trình trên đây là hệ quả của các điều kiện ràng buộc của BTQHTT nguyên, nên khi được bổ sung vào các điều kiện ràng buộc, miền phương án của BTQHTT nguyên không thay đổi và do đó BTQHTT nguyên được đưa về dạng sau: Max z = x1 + 4x2 + 0x3 + 0x4, với các ràng buộc 1 1 7 x1 + x2 + x3 = 2 4 4 17 3 39 (c) x1 + - x2 + x4 = 2 4 4 1 1 3 -x1 - x3 + x5 = − 2 4 4 x1, x2, x3, x4, x5 ≥ 0; x1, x2, x3, x4 nguyên. Lúc này, chúng ta có bảng đơn hình II.6 với phương án đối ngẫu khả thi (phương án đối ngẫu khả thi là phương án có thể không thỏa mãn điều kiện không âm của các biến, nhưng luôn thỏa mãn các điều kiện ràng buộc còn lại của BTQHTT và điều kiện Δj ≤ 0 với mọi chỉ số j). Chúng ta sẽ sử dụng thủ tục xoay của phương pháp đơn hình đối ngẫu để tìm phương án (đối ngẫu khả thi) tối ưu thỏa mãn điều kiện Δj ≤ 0 với mọi chỉ số j (xem bảng đơn hình bước 3 của bảng II.6). Chú ý: Thủ tục xoay trong phương pháp đơn hình đối ngẫu có năm bước, bao gồm: - Trước tiên chọn hàng xoay là hàng với biến xj có giá trị âm (thông thường với trị tuyệt đối lớn nhất, hoặc chọn ngẫu nhiên). - Sau đó chọn cột xoay theo quy tắc “tỉ số âm bé nhất” (ứng với tỉ số bé nhất trong các tỉ số có mẫu số âm được tạo ra bằng cách lấy hàng Δj “chia” cho hàng xj, chỉ xét các tỉ số có mẫu số âm). Nếu không tìm được cột xoay thì kết luận bài toán không có phương án khả thi. - Nếu tìm được cột xoay thì thực hiện ba bước tiếp theo của thủ tục xoay như trong phương pháp đơn hình giải BTQHTT. Bảng II.6. Các bảng đơn hình giải BTQHTT nguyên (tiếp) Hệ số hàm Biến cơ 1 4 0 0 0 Phương án mục tiêu sở x1 x2 x3 x4 x5 Bảng đơn hình bước 3 4 x2 7/4 1/2 1 1/4 0 0 0 x4 39/4 17/2 0 - 3/4 1 0 Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 30
31. 0 x5 - 3/4 - 1/2 0 - 1/4 0 1 zj 2 4 1 0 0 7 Δj - 1 0 - 1 0 0 Bảng đơn hình bước 4 4 x2 1 0 1 0 0 1 0 x4 - 3 0 0 - 5 1 17 1 x1 3/2 1 0 1/2 0 - 2 zj 1 4 1/2 0 2 11/2 Δj 0 0 - 1/2 0 - 2 Bảng đơn hình bước 5 4 x2 1 0 1 0 0 1 0 x3 3/5 0 0 1 - 1/5 - 17/5 1 x1 6/5 1 0 0 1/10 - 3/10 zj 1 4 0 1/10 37/10 26/5 Δj 0 0 0 - 1/10 - 37/10 Ta nhận thấy: phương án tối ưu chưa thỏa mãn điều kiện nguyên. Xét phương trình thứ 3 trong bảng đơn hình thứ 5 của bảng II.6 để làm cơ sở cho việc đưa vào điều kiện 17 1 ràng buộc bổ sung: −−+=−xxx . Sau đó, tiếp tục quá trình giải sử dụng 10456 10 5 phương pháp đơn hình đối ngẫu (xem bảng II.7): Bảng II.7. Các bảng đơn hình giải BTQHTT nguyên (tiếp) Hệ số hàm Biến cơ 1 4 0 0 0 0 Phương án mục tiêu sở x1 x2 x3 x4 x5 x6 Bảng đơn hình bước 6 4 x2 1 0 1 0 0 1 0 0 x3 3/5 0 0 1 - 1/5 - 17/5 0 1 x1 6/5 1 0 0 1/10 - 3/10 0 0 x6 - 1/5 0 0 0 - 1/10 - 7/10 1 zj 1 4 0 1/10 37/10 0 26/5 Δj 0 0 0 - 1/10 -37/10 0 Bảng đơn hình bước 7 4 x2 1 0 1 0 0 1 0 0 x3 1 0 0 1 0 - 2 - 2 1 x1 1 1 0 0 0 - 1 1 0 x4 2 0 0 0 1 7 - 10 zj 1 4 0 0 3 1 5 Δj 0 0 0 0 - 3 - 1
32. Phương án tối ưu ở bảng đơn hình bước 7 của bảng II.7 đã thỏa mãn điều kiện ∗ ∗ nguyên. Vậy phương án tối ưu của BTQHTT nguyên là x1 = 1, x2 = 1 và zmax = 5. Khung thuật toán cắt Gomory Xét BTQHTT nguyên Max z = c1x1 + c2x2 + + cnxn với hệ điều kiện ràng buộc ⎧a11 x 1 +++= a12 x 2 a 1n x n b 1 ⎪ ⎪a21 x 1 +++= a22 x 2 a 2n x n b 2 ⎨a x+++= a x a x b ⎪ m1 1 m2 2 mn n m ⎪ ⎩xjj≥∀= 0, x nguyên, j 1,n. Kí hiệu D là miền ràng buộc của BTQHTT không tính tới điều kiện nguyên của các biến. Lúc đó, khung thuật toán cắt Gomory có thể được phát biểu như sau cho BTQHTT nguyên dạng Max với D là giới nội khác rỗng. Bước khởi tạo Giải BTQHTT không nguyên tương ứng bằng phương pháp đơn hình để thu được phương án tối ưu x1. Đặt k = 1. Các bước lặp (bước lặp thứ k) Bước 1: Nếu xk có các tọa độ nguyên thì chuyển sang bước kết thúc. Bước 2: Nếu trái lại xk có ít nhất một toạ độ không nguyên thì cần chọn ra một biến cơ sở xr có giá trị không nguyên để xây dựng ràng buộc bổ sung. Bước 3: Giải bài toán thu được bằng phương pháp đơn hình đối ngẫu để tìm ra phương án tối ưu. Đặt k = k+1 và chuyển về bước 1 (Nếu trong quá trình giải không tìm được cột xoay thì kết luận BTQHTT nguyên ban đầu không có phương án khả thi). Bước kết thúc. In/lưu trữ kết quả và dừng. 1.5. Một số ứng dụng của phương pháp đơn hình Bài toán phân phối điện năng Có ba hộ phụ tải cần được cung cấp điện năng từ hai nguồn điện nằm cách xa nhau. Giá thành truyền tải một đơn vị điện năng từ nguồn i đến hộ tiêu thụ j là cij. Khả năng cung cấp điện năng của mỗi nguồn bị giới hạn bởi trữ lượng hiện có của chúng là A1 và A2. Nhu cầu tiêu dùng của các hộ tiêu thụ là B1, B2 và B3. Gọi xij là lượng điện năng Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 32
33. được đưa từ nguồn i tới hộ tiêu thụ j. Cần phải xác định các xij sao cho tổng chi phí là nhỏ nhất. Như vậy ta có BTQHTT sau: 23 z = ∑∑cxij ij → Min i1== j1 với các điều kiện ràng buộc là: x11 + x12 + x13 ≤ A1, x21 + x22 + x23 ≤ A2, x11 + x21 = B1, x12 + x22 = B2, x13 + x23 = B3, xij ≥ 0, ∀i = 1, 2 và ∀j = 1, 2, 3. Bài toán phân tải cho máy Một xí nghiệp có hai loại máy M1 và M2. Các loại máy này có thể sản xuất được ba loại sản phẩm P1, P2 và P3 với các năng suất là aij, chẳng hạn máy M1 sản xuất sản phẩm P2 với năng suất a12. Mỗi đơn vị sản phẩm mang lại lãi suất cj với j = 1, 2, 3. Mỗi tháng xí nghiệp phải sản xuất sản phẩm loại j không ít hơn bj đơn vị và không vượt quá dj đơn vị, j = 1, 2, 3. Hãy lập kế hoạch phân tải cho các máy sao cho đạt tổng lợi nhuận lớn nhất. Dễ thấy bài toán này dẫn tới BTQHTT sau: 32 z = ∑∑caxjijij → Max j1== i1 với các điều kiện ràng buộc: a11x11 + a21x21 ≥ b1, a12x12 + a22x22 ≥ b2, a13x13 + a23x23 ≥ b3, a11x11 + a21x21 ≤ d1, a12x12 + a22x22 ≤ d2, a13x13 + a23x23 ≤ d3, x11 + x12 + x13 ≤ m1, x21 + x22 + x23 ≤ m2, xij ≥ 0, i = 1, 2 và j = 1, 2, 3. (trong đó m1 và m2 là tổng thời gian chạy máy M1 và M2). Trong các lĩnh vực quy hoạch sản xuất hay quản lí kinh doanh, nói riêng trong ngành cơ khí và điện lực, BTQHTT được ứng dụng rất rộng rãi và mang lại hiệu quả cần thiết. Giải mô hình quy hoạch tuyến tính bằng các phần mềm tính toán Hiện nay có nhiều phần mềm tính toán giải BTQHTT khá hiệu quả như Excel, Lingo. Những phần mềm này rất thân thiện với người dùng. Tuy nhiên cần nhấn mạnh rằng, việc phát biểu được mô hình bài toán và phân tích, đánh giá được kết quả mới chính là những khâu quan trọng nhất trong phương pháp mô hình hoá. Sau đây, chúng ta dùng phần mềm Lingo để giải ví dụ đã xét ở trên. z = 8x1 + 6x2 → Max
34. với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. Để giải bài toán này, chúng ta cần cài đặt Lingo vào trong máy tính. Nhấn vào biểu tượng Lingo trên màn hình để vào cửa sổ Lingo. Sau đó thực hiện các lệnh Lingo: Menu > New > và gõ vào các dữ liệu của bài toán như hình II.4. Hình II.4. Nhập dữ liệu của bài toán quy hoạch tuyến tính trong Lingo Tiếp theo, cần nháy chuột vào nút LINGO và giải bài toán để thu được kết quả chi tiết như trên hình II.5. Hình II.5. Kết quả giải bài toán quy hoạch tuyến tính trong Lingo Kết quả chi tiết cho ta biết giá trị cực đại của hàm mục tiêu là 132 với phương án tối ưu là: x1 = 12, x2 = 6. Các giá trị tối ưu của các biến đối ngẫu là y1 = 5/3 và y2 = 2/3 (còn gọi là các giá ước định hay giá bóng Shadow Prices). Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 34
35. 2. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU 2.1. Các khái niệm cơ bản 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 để tối ưu hóa đồ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 tối ưu đa mục tiêu. Như vậy, chúng ta cần phải tối ưu hóa (cực đại hóa hoặc cực tiểu hóa 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. Có thể nói, BTQHTT đa mục tiêu là BTQHTT mà trong đó chúng ta phải tối ưu hóa cùng một lúc nhiều mục tiêu. 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. Hiện tại các tài liệu, sách chuyên khảo, tạp chí cập nhật về lĩnh vực liên ngành Toán − Tin, Khoa học quản lí. Công nghệ thông tin, đề cập 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à khoa học và kĩ sư thực hành quan tâm. Bài toán tối ưu đa mục tiêu mà trong đó miền ràng buộc D là tập lồi đa diện và các mục tiêu zi = fi(X), với i = 1, 2, , p, là các hàm tuyến tính xác định trên D, được gọi là bài toán quy hoạch tuyến tính đa mục tiêu. Khi đó, ta có mô hình toán học sau đây được gọi là mô hình quy hoạch tuyến tính đa mục tiêu: n Max CX với ràng buộc X ∈ D ⊂ R , trong đó: C là ma trận cấp p × n, D = {X = (x1, n m x2, , xn) ∈ R : AX ≤ B}, A là ma trận cấp m×n và B ∈ R . Ví dụ 1: z1 = f1(X) = 8x1 + 6x2 → Max z2 = f2(X) = x1 + 3x2 → Max T trong đó X = (x1, x2) , với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. Ta có thể viết bài toán này dưới dạng ma trận như sau: Max CX với ràng buộc 2 T T X ∈ D = {X∈ R : AX ≤ B}, trong đó X = (x1, x2) , B = (60, 48, 0, 0) , còn
36. ⎡4 2⎤ ⎢ ⎥ ⎡⎤86 ⎢2 4⎥ C = ⎢⎥, A = . ⎣⎦13 ⎢−1 0⎥ ⎢ ⎥ ⎣ 0 −1⎦ Khái niệm then chốt trong tối ưu hóa đa mục tiêu là khái niệm phương án tối ưu Pareto, còn gọi là phương án hữu hiệu (efficient solution). Định nghĩa 1: Một phương án tối ưu Pareto X* có tính chất sau đây: − 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. − 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 (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 (fj(X) xấu hơn fj(X ), j ≠ i). Phương án X ∈ D được gọi là phương án Pareto yếu nếu 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 (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 không tốt hơn (fj(X) không tốt hơn fj( X ), j ≠ i). Như vậy, một phương án tối ưu Pareto cũng là tối ưu Pareto yếu, điều ngược lại không nhất thiết luôn đúng. Để nhận biết tập phương án tối ưu Pareto chúng ta cần tới các khái niệm sau: Trước hết xét nón nón β cảm sinh bởi các véc tơ gradient c1, c2, , cp của các hàm mục tiêu, c1, c2, , cp chính là các véc tơ hàng của ma trận C. Cho x ∈ D. Tập điểm trội tại x là tập ≥ ≥ n Dx = { x } ⊕ C , với C = {x = (x1, x2, , xn) ∈ R : Cx ≥ 0, Cx ≠ 0} là nón đối cực (được kí hiệu là α trên hình II.6 trong ví dụ đang xét). Lúc đó, có thể chứng minh được: x ∈ D là phương án tối ưu Pareto khi và chỉ khi Dx ∩ D = { x }. Xét lại ví dụ đã cho trên đây. x2 c1(1,3) c (8,6) 2 O A(0, 12) α G B(12, 6) C(15,0) Trường Đại học Nông nghiOệp Hà Nội – Giáo trình Vận trù học 36 Hình II.6. Minh hoạ hình học BTQHTT hai mục tiêu
37. Miền các phương án khả thi D (miền giới hạn bởi tứ giác ABCD) được biểu thị trên hình II.6, c1(8, 6) là véc tơ gradient và hướng tăng của mục tiêu 1, còn c2(1, 3) là véc tơ gradient và hướng tăng của mục tiêu 2. Trên hình II.6, chúng ta có thể thấy nón β là nón cảm sinh bởi các véc tơ c1 và c2. Xét điểm G ∈ AB, dễ dàng xác định được nón đối cực α và tập điểm trội tại G. Dễ thấy, tập hợp P tất cả các phương án tối ưu Pareto bao gồm các điểm nằm trên đoạn AB với A(0, 12) và B(12, 6). 2.2. Phương pháp tổng quát giải BTQHTT đa mục tiêu Đị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 (hoặc một số) phương án tốt nhất (thoả mãn 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. Trong ví dụ trên, tuỳ theo cơ cấu ưu tiên của người ra quyết định, chúng ta có thể chọn ra một hoặc một số điểm tối ưu Pareto nằm trên AB làm phương án tối ưu của bài toán. 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 nhằm tìm ra phương án tối ưu Pareto thoả mãn nhất 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 nhiều biến là khá khó và mất nhiều thời gian. 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 trung gian vừa tìm được, 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.
38. Định nghĩa 3: Phương pháp giải bài toán tối ưu đa mục tiê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. 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 có 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: cho biết các thông tin nào máy tính phải đưa ra 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 hóa 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. Cho tới thời điểm hiện nay, hàng chục phương pháp giải BTQHTT đa mục tiêu đã được đề cập tới trong các tạp chí chuyên ngành, mà đa số chúng đều có những ứng dụng rất thành công trong nhiều lĩnh vực, như phương pháp tham số, phương pháp nón pháp tuyến, phương pháp véc tơ cực đại, phương pháp trọng số tương tác của Chebysev. Phương pháp thoả dụng mờ tương tác giải BTQHTT đa mục tiêu do Nguyễn Hải Thanh đề xuất có một số ưu điểm cho phép: − Quy các thứ nguyên khác nhau của các hàm mục tiêu về cùng một thang đo độ thoả mãn của người ra quyết định. − Tạo ra một quá trình tương tác người − máy tính để tìm được nhiều phương án tối ưu Pareto (hay phương án tối ưu Pareto yếu) đem lại nhiều lựa chọn cho người ra quyết định. 2.3. Phương pháp thoả dụng mờ tương tác giải BTQHTT đa mục tiêu Bước khởi tạo i) Nhập số liệu cho các hàm mục tiêu tuyến tính zi (i = 1, 2, , p) và m điều kiện ràng buộc. Giải BTQHTT cho từng mục tiêu zi (i = 1, 2, , p) với miền ràng buộc D được xác định bởi m ràng buộc ban đầu để thu được các phương án tối ưu x1, x2, , xp (nếu với một mục tiêu nào đó bài toán không cho phương án tối ưu thì cần xem xét để chỉnh sửa lại các điều kiện ràng buộc ban đầu). ii) Tính giá trị các hàm mục tiêu tại p phương án x1, x2, , xp và lập bảng pay−off. B w B Xác định giá trị cận trên zi và giá trị cận dưới zi của mục tiêu zi (i =1, 2, , p), với zi i w j = zi(x ) và zi = Min {zi(x ): j = 1, 2, , p}. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 38
39. iii) Xác định các hàm thoả dụng mờ μ1(z1), μ2(z2), , μp(zp) cho từng mục tiêu theo w zzii− công thức: μ=ii(z )Bw , i = 1, 2, , p. zzii− 1 2 p (k) B iv) Đặt: SP = {x , x , , x }, k = 1 và ai = zi với i = 1, 2, , p. Các bước lặp (xét bước lặp thứ k) Bước 1: i) Xây dựng hàm thoả dụng tổ hợp từ các hàm thoả dụng trên: u = w1μ1(z1) + w2μ2(z2) + + wpμp(zp) → Max Trong đó: w1, w2, , wp là các trọng số (phản ánh tầm quan trọng của từng hàm thoả dụng trong thành phần hàm thoả dụng tổ hợp) được người giải lựa chọn thoả mãn điều kiện: w1 + w2 + + wp = 1 và 0 ≤ w1, w2, , wp ≤ 1. ii) Giải BTQHTT với hàm thoả dụng tổ hợp với m ràng buộc ban đầu và p ràng (k) buộc bổ sung zi(x) ≤ ai , i = 1, 2, , p, để tìm được phương án tối ưu của bước lặp thứ (k) k là x và giá trị của các hàm mục tiêu zi cũng như của các hàm thoả dụng μi(zi) (với i =1, 2, , p). Bước 2: i) Nếu μmin = Min {μi(zi): i = 1, 2, , p} bé hơn một ngưỡng t nào đó (t được lựa chọn trong đoạn [0, 1] và có thể được sửa chỉnh lại trong quá trình giải bài toán) thì phương án tìm được x(k) không được chấp nhận. Trong trường hợp trái lại, phương án (k) x được chấp nhận vào tập SP các phương án tối ưu Pareto (tối ưu Pareto yếu) cần xem (k) xét nếu x ∉ SP. ii) Nếu người giải bài toán còn muốn tiếp tục mở rộng tập SP thì đặt k = k + 1. Nếu k > L1 hoặc số lần bước lặp liên tiếp tập SP không được mở rộng vượt quá L2 (k) B (L1 và L2 được người giải tùy chọn) thì đặt ai = zi với i = 1, 2, , p và chọn ngẫu (k) w B nhiên một chỉ số h ∈ {1, 2, , p} để đặt lại giá trị cắt a h ∈ ( zh , zh ]. Quay về bước 1. iii) Nếu người giải bài toán không muốn mở rộng tập SP thì chuyển sang bước 3. Bước 3: i) Loại khỏi tập SP các phương án bị trội. ii) Kết thúc. Ví dụ 2: Giải BTQHTT hai mục tiêu. z1 = 8x1+ 6x2 → Max
40. z2 = x1 + 3x2 → Max với các ràng buộc: 4x1 + 2x2 ≤ 60 (D) 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. a. Bước khởi tạo i) Giải BTQHTT cho từng mục tiêu trong ví dụ trên ta có hai bài toán: z1 = 8x1 + 6x2 → 1 Max với điều kiện ràng buộc (D) cho phương án tối ưu x (12, 6) và Max z1 = 132; 2 z2 = x1 + 3x2 → Max cho phương án tối ưu x (0, 12) và Max z2 = 36. ii) Lập bảng pay−off cho các mục tiêu Phương án Xi z1 z2 X1(12, 6) 132 30 X2(0, 12) 72 36 W B W Dựa trên thông tin của bảng pay−off, ta có z1 = 72, z1 = 132; còn z2 = 30, B z2 = 36. Do đó, đoạn biến thiên cần xét cho z1 là [72, 132] và cho z2 là [30, 36]. iii) Thiết lập các hàm thoả dụng mờ ứng với hai mục tiêu đã cho như sau: zz− w z72− z 72 z μ (z ) = 11= 1 = 1 − = 1 − 1,2 11 Bw 60 zz11− 132− 72 60 60 Hàm thoả dụng mờ trên đây phụ thuộc vào z1, nên phụ thuộc vào (x1, x2). Khi có một phương án khả thi (x1, x2) ta tính được độ thoả dụng μ1 (z1 ) đối với mục tiêu z1. Tương tự đối với z2 ta có hàm thoả dụng mờ: zz− w z30− z μ (z ) = 22= 2 = 2 − 5. 22 Bw zz22− 36− 30 6 1 2 (1) (1) iv) Tập SP ban đầu là {x , x }. Đặt k = 1, ta có a1 = 132, a 2 = 36. b. Các bước lặp Bước 1: i) Lập hàm thoả dụng tổ hợp u = w1 μ11(z ) + w2 μ22(z ) , trong đó w1, w2 là các trọng số thoả mãn 0 ≤ w1, w2 ≤ 1 và w1 + w2 = 1. Chọn w1 = 0,5 và w2 = 0,5 thì có u = 0,5 z z z z ( 1 − 1,2) + 0,5 ( 2 − 5) = ( 1 + 2 ) − 3,1. 60 6 120 12 Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 40
41. ⎧⎫zz ii) Để cực đại hóa hàm thoả dụng tổ hợp, ta chỉ cần tìm Max ⎨⎬12+ . Vậy ⎩⎭120 12 z z chúng ta cần giải bài toán: Max u = 1 + 2 với các ràng buộc (D), hay bài toán 120 12 tương đương: z = 120u/18 = x1 + 2x2 → Max, với các ràng buộc (D). Giải BTQHTT này ta sẽ có kết quả x(1) = (0, 12). Bước 2: (1) 2 i) Rõ ràng x ≡ x . Vậy tập SP chưa được mở rộng. ii) Nếu người giải muốn tiếp tục mở rộng tập SP thì đặt k = 2 và quay về bước 1. Quá trình giải được tiếp tục. (2) (2) Trong bước lặp thứ 2, đặt w1 = 0,8, w2 = 0,2, a1 = 132 và a 2 = 36 sẽ thu được (2) 1 phương án x (12, 6) ≡ x . Do đó tập SP vẫn chưa được mở rộng. (3) (3) Trong bước lặp thứ 3, đặt w1 = 0,8, w2 = 0,2, a1 = 120 và a 2 = 36 sẽ thu được (3) 1 2 phương án x (9,6; 7,2) mà tại đó z1 = 120 và z2 = 31,2. Tập Sp lúc này là tập {x , x , x(3)}. (4) (4) Trong bước lặp thứ 4, đặt w1 = 0,2, w2 = 0,8, a1 = 132 và a 2 = 35 sẽ thu được (4) 1 2 (3) phương án x (2; 11) mà tại đó z1 = 82 và z2 = 35. Tập Sp lúc này là tập {x , x , x , x(4)}. Giả sử người giải không muốn tiếp tục mở rộng tập SP thì chuyển sang bước 3. Bước 3: i) Trong các phương án thuộc tập SP không có phương án nào bị trội. ii) Kết thúc với tập SP các phương án cần xem xét. Các phương án này đều là phương án tối ưu Pareto hay tối ưu Pareto yếu. Phần mềm giải bài toán quy hoạch tuyến tính đa mục tiêu Phần mềm giải BTQHTT đa mục tiêu MOD phiên bản 2.0 được xây dựng dựa trên phương pháp thoả dụng mờ và được tích hợp vào Hệ hỗ trợ ra quyết định phục vụ quy hoạch sử dụng đất DSSLUP phiên bản 2.0. Được xây dựng trên ngôn ngữ lập trình C#, phần mềm có thể dễ dàng được nâng cấp, bổ sung hoặc sử dụng lại trong một số ứng dụng khác. Phần mềm sử dụng hệ quản trị cơ sở dữ liệu SQL server, thuận lợi cho việc quản lí và tích hợp với các phần mềm và các hệ thống thông tin - dịch vụ khác. Các chức năng chính của phần mềm bao gồm: − Chức năng nhập dữ liệu: Nhập dữ liệu bài toán từ tệp dữ liệu bản đồ (sử dụng dữ liệu bản đồ MapInfo).
42. − Chức năng lưu trữ và xuất dữ liệu: Dữ liệu được lưu và quản lí trong cơ sở dữ liệu SQL Server, đồng thời cũng có thể được đưa ra tệp dữ liệu bản đồ (Sử dụng MapInfo). − Giải bài toán: theo dõi bảng pay−off và giải theo phương pháp trọng số, có sử dụng ràng buộc cắt để tìm thêm phương án bổ sung vào tập các phương án tối ưu Pareto cần xem xét. Sau khi cài đặt phần mềm, để thiết lập bài toán cần chọn Cơ sở dữ liệu > Tạo bảng dữ liệu nhằm tạo số biến, mục tiêu và số ràng buộc cho bài toán. Sau đó chọn Cơ sở dữ liệu > Cập nhật dữ liệu nhằm cập nhật dữ liệu cho các bảng mục tiêu và ràng buộc, bao gồm các hệ số, các quan hệ ràng buộc và chỉ ra các mục tiêu nào là Max/Min. Để giải bài toán chọn Giải bài toán QHTT > Giải bài toán và chọn bài toán cần giải từ cửa sổ danh sách các bảng mục tiêu và bảng ràng buộc. Để xem thông tin Pay-Off thì chọn nút Bảng Pay-Off. Nhập các trọng số vào cửa sổ Nhập trọng số, sau đó bấm nút Giải đa mục tiêu. Muốn tạo giá trị cắt miền ràng buộc chọn mục tiêu cần cắt trong cửa sổ Nhập giá trị cắt, chọn mức cần cắt và chọn nút Giải phương pháp cắt để giải bài toán theo phương pháp cắt. Để lưu các phương án tối ưu Pareto (sau khi đã loại các phương án bị trội), chọn nút Lưu phương án. Ví dụ 3: Giải BTQHTT ba mục tiêu. z1 = x1 − 2x2 + 3x4 → Max z2 = −3x1 + 6x2 − 9x4 → Max z3 = 5x1 + x2 + 2x3 → Max với các ràng buộc: −2x1 + x3 ≤ 6 x1 + x2 + 5x3 ≤ 6 6x1 + 5x2 − 3x3 ≤ 6 − x3 + 4x4 ≤ 8 x1, x2, x3, x4 ≥ 0. Như vậy, ở đây chúng ta muốn cực đại hóa đồng thời ba hàm mục tiêu trên miền D các phương án khả thi thoả mãn đồng thời bốn ràng buộc và điều kiện không âm của các biến. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 42
43. Hình II.7. Nhập dữ liệu, tính bảng pay - off và các phương án Trên hình II.7, màn hình giao diện cho biết: − Sau khi đã nhập dữ liệu, máy tính thực hiện tính các giá trị của bảng pay−off để cho biết các giải giá trị quan tâm của z1 là [-3,43; 8,14], của z2 là [-24,41; 10,29] và của z3 là [3,43; 9,09]. Dựa trên các thông tin này, máy tính sẽ thiết lập các hàm thoả dụng 1 2 cho từng mục tiêu. Tập SP ban đầu bao gồm các phương án x (1,45; 0; 0,91; 2,23), x (0; 1,71; 0,86; 0), x3(1,45; 0; 0,91, 0). (1) (1) (1) − w1 = 0,2, w2 = 0,3, w3 = 0,5 với a1 = 8,14, a 2 = 10,29 và a3 = 9,09, máy tính (1) tìm ra phương án x (1,45; 0; 0,91; 0) với các giá trị hàm mục tiêu là z1 = 1,45, z2 = − (1) 3 4,36 và z3 = 9,09. Phương án x trùng với phương án x . (2) Để tiếp tục quá trình giải, chúng ta chọn w1 = 0,8, w2 = 0,1, w3 = 0,1 với a1 = 6, (2) (2) (2) a 2 = 10,29 và a3 = 9,09, máy tính sẽ tìm ra phương án x (1,45; 0; 0,909; 0) với các giá trị hàm mục tiêu là z1 = 6, z2 = − 18 và z3 = 9,09. (3) (3) (3) Chọn w1 = 0,1, w2 = 0,8, w3 = 0,1 với a1 = 8,14, a 2 = 8 và a3 = 9,09, máy tính (3) tìm ra phương án x (0,23; 1,45; 0,87, 0) với các giá trị hàm mục tiêu là z1 = −2,67, z2 = 8 và z3 = 4,31.
44. (4) (4) (4) Chọn w1 = 0,2, w2 = 0,3, w3 = 0,5 với a1 = 8,14, a 2 = 5 và a3 = 5, máy tính tìm (1) ra phương án x (0,4; 1,2; 0,87, 0) với các giá trị hàm mục tiêu là z1 = −2,07, z2 = 6,22 và z3 = 5. 2.4. Một ứng dụng của mô hình quy hoạch tuyến tính đa mục tiêu Xét mô hình quy hoạch tuyến tính đa mục tiêu đánh giá hiệu quả sử dụng đất và lao động trên địa bàn cấp xã. Để 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. Dựa vào cơ cấu cây trồng xã năm 1999, các biến quyết định 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 hóa là: z1 = 4,48x1 + 4,2x2 + 2,59x3 + 0,98x4 + 5,8x5 + 15,61x6 + 29,67x7 + 39,21x8 + 116,58x9 + 105,13x10, z2 = 0,6205x1 + 0,5915x2 +0,465x3 + 0,1583x4 + 0,7065x5 + 0,5864x6 + 1,2996x7 + 1,2735x8 + 1,1726x9 + 1,756x10, z3 = 0,0217x1 + 0,0206x2 + 0,0154x3 + 0,0045x4 + 0,0248x5 + 0,0109x6 + 0,0241x7 + 0,0349x8 + 0,09x9 + 0,0811x10, z4 = 206x1 + 204x2 + 168x3 + 216x4 + 234x5 + 1428x6 + 1232x7 + 1124x8 + 1296x9 + 1296x10, z5 = 0,7x1 + 0,778x2 + 1,273x3 + 1,75x4 + x5 + 0,368x6 + 0,875x7 + 3x8 + 3x9 + 3x10, 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. 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 + x10 = 18. Điều kiện để có lợi nhuận là: Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 44
45. 4,48x1 + 4,2x2 + 2,59x3 + 0,98x4 + 5,8x5 + 15,61x6 + 29,67x7 + 39,21x8 + 116,58x9 + 105,13x10 > 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,14x1 + 4,98x2 + 3,77x3 ≥ 1700,5. Điều kiện không âm của các biến: xi (i = 1, 2, , 10) ≥ 0. Mô hình trên đây đã được giải quyết thành công bằng phần mềm giải BTQHTT đa mục tiêu MOD phiên bản 2.0. 3. MÔ HÌNH TỐI ƯU PHI TUYẾN ĐƠN VÀ ĐA MỤC TIÊU 3.1. Một số khái niệm cơ bản Mô hình tối ưu tổng quát Mô hình tối ưu tổng quát, hay bài toán tối ưu tổng quát, có dạng: F(X) → Min (Max) với X ∈ D ⊂ Rn. Ở đây F(X) 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(X) là hàm vô hướng thì ta có mô hình tối ưu đơn mục tiêu, còn nếu F là hàm véc tơ thì có mô hình tối ưu đa mục tiêu. D được gọi là miền ràng buộc hay miền phương án khả thi, thường được biểu diễn bởi các đẳng thức và/hoặc các bất đẳng thức. Mô hình tối ưu phi tuyến đơn mục tiêu Dạng chính tắc của bài toán tối ưu một mục tiêu được biểu diễn như sau: n f(X) → Min (Max), X = (x1, x2, , xn)∈ R , 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 (iii) ai ≤ xi ≤ bi, i = 1, 2, , n. Trong trường hợp hoặc hàm mục tiêu f(X) hoặc có ít nhất một trong các hàm ràng buộc gj(X), j = 1, 2, , m, là hàm phi tuyến, chúng ta có bài toán tối ưu phi tuyến. Khi tất cả các toạ độ xi đều bắt buộc nhận các giá trị nguyên, i = 1, 2, , n thì ta có bài toán tối ưu nguyên. Còn nếu chỉ có một số toạ độ (nhưng không phải tất cả các toạ độ) bắt buộc nhận giá trị nguyên thì ta có bài toán tối ưu hỗn hợp nguyên. 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 tối ưu trên đây có thể viết gọn hơn như sau:
46. f(X) → Min (Max) với X ∈ D. Lúc này, đối với bài toán cực tiểu hoá, 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 nào đó của X* thì X* được gọi là phương án tối ưu địa phương. Một cách tương tự, ta có thể định nghĩa khái niệm phương án tối ưu toàn cục hoặc địa phương cho bài toán cực đại hoá. Nếu chúng ta chỉ quan tâm tới việc tìm kiếm phương án tối ưu toàn cục thì ta có bài toán tối ưu toàn cục. Trong các bài toán tối ưu phi tuyến ứng dụng nói chung, trong lĩnh vực cơ khí − điện lực nói riêng, phương án tối ưu toàn cục có một ý 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 quy nhiều chiều, ta thường thu được hàm mục tiêu f(X) có dạng phi tuyến. 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 tối ưu nguyên và hỗn hợp nguyên. Mô hình tối ưu phi tuyến đa mục tiêu Mô hình tối ưu đa mục tiêu có dạng: zj = fj(X) → Min (Max), 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 (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. 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 tối ưu phi tuyến đa mục tiêu. Đối với bài toán tối ưu phi tuyến đa mục tiêu chúng ta cũng có khái niệm phương án tối ưu Pareto như đã trình bày trong mục 2 đối với BTQHTT đa mục tiêu. Cũng như đối với các BTQHTT đa mục tiêu, phương pháp giải bài toán tối ưu phi tuyến đa mục tiê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. 3.2. Một số phương pháp giải bài toán tối ưu phi tuyến đơn mục tiêu và ứng dụng Các phương pháp giải bài toán tối ưu toàn cục Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 46
47. Các phương pháp giải bài toán tối ưu toàn cục phi tuyến đơn mục tiêu được phân ra thành hai lớp: phương pháp tất định (deterministic methods) và phương pháp ngẫu nhiên (stochastic methods). Phương pháp tất định sử dụng các tính chất giải tích của hàm mục tiêu và các hàm ràng buộc. Một số dạng bài toán tối ưu toàn cục với những tính chất giải tích nhất định của hàm mục tiêu và các hàm ràng buộc có thể giải được bằng các phương pháp tất định thích hợp, chẳng hạn như: phương pháp đường dốc nhất, phương pháp Newton (cho các bài toán tối ưu phi tuyến không có ràng buộc), phương pháp quy hoạch toàn phương, quy hoạch tách, quy hoạch lồi, quy hoạch d.c (cho các bài toán tối ưu phi tuyến có ràng buộc) Trong các trường hợp đó phương án tối ưu toàn cục có thể tìm được sau một số hữu hạn bước tính toán với độ chính xác chọn trước. Tuy nhiên, đối với nhiều lớp bài toán tối ưu toàn cục phương pháp tất định tỏ ra không có hiệu quả. Trong khi đó, các phương pháp ngẫu nhiên như: phương pháp đa khởi tạo (multistart), mô phỏng tôi luyện (simulated annealing), thuật giải di truyền (genetic algorithm), có thể áp dụng để giải các bài toán tối ưu toàn cục dạng bất kì, không đòi hỏi các tính chất đặc biệt của hàm mục tiêu hay các hàm ràng buộc. Các phương pháp ngẫu nhiên đặc biệt tỏ ra có hiệu quả đối với các bài toán tối ưu phi tuyến nguyên và hỗn hợp nguyên. Tuy nhiên, các phương pháp này thường chỉ cho phương án “gần” tối ưu khá tốt sau một số hữu hạn bước mà không kiểm soát được độ chính xác của phương án tìm được. Giải bài toán tối ưu phi tuyến bằng thuật giải RST2ANU Thuật giải RST2ANU, được đưa ra bởi C. Mohan và Nguyễn Hải Thanh nhằm giải các bài toán tối ưu toàn cục phi tuyến dạng tổng quát với các biến liên tục, các biến nguyên và cho các bài toán hỗn hợp nguyên. Thuật giải này là thuật giải tìm kiếm ngẫu nhiên có điều khiển, có kết hợp thuật toán mô phỏng tôi luyện (SA). Thuật giải RST2ANU là thuật giải lặp, bao gồm hai pha: pha cục bộ và pha toàn cục, được phát biểu một cách ngắn gọn cho bài toán tối ưu chính tắc dạng cực tiểu hóa như sau. Trong pha toàn cục, một số lượng thích hợp đủ lớn các phương án khả thi được được phát sinh ra một cách ngẫu nhiên và lưu trữ trong mảng có tên A. Đánh dấu hai điểm có giá trị hàm mục tiêu lớn nhất và nhỏ nhất tương ứng là M và L. Trong pha cục bộ, các phương án được xử lí nhằm thu được giá trị tốt hơn của hàm mục tiêu. Trong pha này, thuật giải xác định X là điểm được nội suy bậc hai dựa trên phương án L và hai phương án khác được chọn ngẫu nhiên trong mảng A. Nếu như X là phương án khả thi thì với f(X) ≤ f(M), M sẽ được thay thế bởi X trong mảng A; còn với f(X) > f(M), M sẽ được thay thế bởi X với xác suất p= exp(−β(f(X)−f(M))/(f(X)−f(L))), trong đó β > 0 là tham số được lựa chọn thích hợp. Nếu X không phải là phương án khả thi, bỏ qua X và chọn hai phương án khác trong A một cách ngẫu nhiên rồi cùng với L tiếp tục sinh ra phương án mới. Quá trình cứ thế tiếp diễn như vậy cho tới khi tập hợp
48. các phương án trong A sẽ có xu hướng co cụm lại xung quanh một phương án tối ưu toàn cục. Phần mềm RST2ANU 1.0 được xây dựng dựa trên thuật giải được trình bày trên đây. Quá trình xây dựng phương pháp tính toán tối ưu, thuật giải, cài đặt trên ngôn ngữ C và sau này là ngôn ngữ Visual C++ 6.0 cũng như chạy thử nghiệm kéo dài gần tám năm cho thấy phần mềm có độ tin cậy rất cao trong việc tìm ra các phương án tối ưu toàn cục. Phần mềm đã được kĩ sư Đặng Xuân Hà đóng gói tránh sao chép và có giao diện thân thiện đối với người sử dụng, có thể dùng để giải các bài toán lớn khi được cài đặt trên hệ máy tính mạnh. Ví dụ 1: Giải bài toán tối ưu phi tuyến hỗn hợp nguyên. 0,6 0,6 0,4 , z = x1 + x2 + x3 + 2x4 + 5x5 − 4x3 - x6 → Min với các ràng buộc: x2 − 3x1 − 3x4 = 0; x3 − 2x2 − 2x5 = 0; 4x4 - x6 = 0; x1 + 2x4 ≤ 4; x2 + x5 ≤ 4; x3 + x6 ≤ 6; x1 ≤ 3; x2 ≤ 4; x3 ≤ 4; x4 ≤ 1; x5 ≤ 2; x6 ≤ 6; x1, x2, x3, x4, x5, x6 ≥ 0; x4, x5, x6 là các biến nguyên. Hướng dẫn sử dụng phần mềm RST2ANU Chương trình được gói gọn trong một file chạy duy nhất mang tên rst2anu1.0.exe. Khi bắt đầu khởi động chương trình, người dùng sẽ được hỏi mã đăng kí sử dụng chương trình. Mỗi người dùng sẽ được cấp một mã đăng kí và phải có mã đăng kí mới sử dụng được chương trình, do đó chương trình không thể bị sao chép. Sau khi nhập mã đăng kí, người dùng có thể nhập bài toán một cách dễ dàng (xem hình II.8) với: − NX là số biến của bài toán. − XINT xác định biến nguyên và biến không nguyên. Như trong hình trên, XINT = 0,0,0,1,1,1 cho biết ba biến đầu là biến liên tục, ba biến sau là biến nguyên. − FX là xâu xác định hàm ràng buộc, được nhập theo cú pháp của Evaluate Expression. Các biến được viết bằng kí hiệu “X” có kèm theo chỉ số. Chẳng hạn, X1 là biến thứ nhất, X5 là biến thứ 5. − Nếu bài toán tối ưu là bài toán tìm cực tiểu thì lựa chọn ô MIN và ngược lại chọn ô MAX với bài toán tìm cực đại. − Feas xâu cho biết các hàm ràng buộc, được nhập cách nhau bởi dấu chấm phảy hoặc xuống dòng. Các xâu này cũng tuân theo cú pháp của EvaluateExpression. Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 48
49. − Rules là các xâu chỉ ra các luật. Ở đây, một luật có thể coi như là một lệnh gán giá trị của một biến bởi giá trị của một biểu thức các biến khác. − MINX là mảng xác định cận dưới cho các biến, các giá trị viết cách nhau bởi dấu phảy (,). − MAXX là mảng xác định cận trên cho các biến, các giá trị viết cách nhau bởi dấu phảy (,). Hình II.8. Màn hình giao diện sau khi nhập xong dữ liệu − NA là kích thước của mảng A (có thể chọn tuỳ ý, tối thiểu là 2(n + 1) với n là số biến của bài toán). − MAX RANDOM là số lần cố gắng tối đa để tìm một phương án chấp nhận được bằng phương pháp ngẫu nhiên. − ITERLAST, ISLAST, IFLAST là các giới hạn về số vòng lặp, số lần thất bại trong việc cải thiện giá trị hàm mục tiêu, số lần thất bại trong việc nội suy phương án mới chấp nhận được. − Epsilon1, epsilon2 là các số dương đủ nhỏ nhằm xác định tiêu chuẩn co cụm của mảng A theo thuật giải. − Beta là hằng số sử dụng trong công thức tính xác xuất thay thế một phương án tốt hơn trong mảng A bởi một phương án tồi hơn. − Prob file và Res file là các tệp đầu vào và tệp kết quả. Có thể soạn sẵn tệp bài toán đầu vào rồi nạp bài toán. Cũng có thể lưu một bài toán đã nhập ra tệp.
50. Chạy chương trình RST2ANU Sau khi nhập bài toán hay nạp bài toán từ tệp, có thể chạy chương trình bằng cách kích chuột vào nút RUN. Trong khi chạy chương trình, ô trạng thái ở phía trên nút RUN sẽ xuất hiện dòng chữ SEARCHING. Khi thuật giải chạy xong thì ô trạng thái sẽ trở về READY cho biết đã sẵn sàng cho các bài toán tiếp theo. Mọi thông tin về phần mềm và cách sử dụng sẽ được biết nếu kích chuột vào nút ABOUT. Sau khi chạy xong chương trình, kết quả chạy sẽ được xem trực tiếp khi kích chuột vào nút RESULTS và có thể lưu ra file văn bản, bao gồm phương án tối ưu, giá trị hàm mục tiêu, mảng A, có cấu trúc như trên hình II.9. Hình II.9. Cấu trúc file kết quả Như vậy, bài toán đã được giải xong, với kết quả: x1 = 2/3, x2 = 2, x3 = 4, x4 = 0, x5 = 0, x6 = 0 và giá trị tối ưu của hàm mục tiêu là −11,95913. Một ứng dụng của thuật giải RST2ANU Chúng ta có thể sử dụng phần mềm RST2ANU để 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 + lcosϕ2 + l 3cosϕ3 + l4cosϕ4 - xC1 = 0; ’’ r sinϕ1 + lsinϕ2 + l 3sinϕ3 + l4sinϕ4 - yC1 = 0; ’ r cosϕ1 + lcosϕ2 + l 3cos(ϕ3 − α) + l5cosϕ5 - xD1 = 0; Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 50
51. ’ r sinϕ1 + lsinϕ2 + l 3sin(ϕ3 − α) + l5sinϕ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 RST2ANU giải hệ phương trình phi tuyến, chúng ta cho ϕ1 = kπ/8 (k = 0, , 9) và thiết lập hàm mục tiêu sau đây: ’’ 2 ’’ z = (rcosϕ1 + lcosϕ2 + l 3cosϕ3 + l4cosϕ4 - xC1) + (rsinϕ1 + lsinϕ2 + l 3 sinϕ3 + 2 ’ 2 l4sinϕ4 - yC1) + (rcosϕ1 + lcosϕ2 + l 3cos(ϕ3 − α) + l5cosϕ5 - xD1) + (rsinϕ1 + lsinϕ2 + ’ 2 l 3sin(ϕ3 − α) + l5sinϕ5 - yD1) → Min. Kết quả được cho trong bảng II.8 với zmin = 0. Bảng II.8. 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 3.3. Một số phương pháp giải bài toán tối ưu phi tuyến đa mục tiêu và ứng dụng Chúng ta trình bày hai phương pháp tương tác người - máy tính giải bài toán tối ưu phi tuyến đa mục tiêu. Phương pháp PRELIME (PREference Level Interactive Method) hay còn gọi là phương pháp tương tác dựa trên mức ưu tiên do C. Mohan và Nguyễn Hải Thanh đề xuất. Còn phương pháp trọng số quy chuẩn là do Andrezj Osyczka đề xuất. Các phương pháp này đều thuộc lớp 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 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.
52. − 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 hóa 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. Bài toán thiết kế trục máy Bài toán có hai mục tiêu sau: − Mục tiêu 1 là cực tiểu hóa thể tích của trục máy 2 2 3 f1(X) = 0,785[x1(6400 − x2 ) + (1000 − x1)(1000 − x2 )] (mm ) − Mục tiêu 2 là cực tiểu hóa độ nén tĩnh của trục 9 −5 1 1 3 10 f2(X) = 3,298×10 [( 7 4 − 8 4 )x1 + 8 4 ] (mm/N). 4,096×10 − x2 10 − x2 10 − x2 Trong đó, X= (x1, x2) là véc tơ quyết định hay véc tơ phương án, với x1, x2 là các biến quyết định sau: x1 − độ dài phần giáp nối trục (giả thiết x1 ≤ 1000), x2 − đường kính trong của trục. Các thông số khác đã được thể hiện trong các hàm mục tiêu f1(X) và f2(X). Chúng ta cần chọn các giá trị cho các biến quyết định (còn gọi là các biến thiết kế) x1, x2 để tối ưu hóa đồng thời các mục tiêu 1 và 2 trong các điều kiện ràng buộc sau: 6 9,78×10 x1 g1(X) = 180 − 7 4 ≥ 0, 4,096×10 − x2 g2 (X) = 75,2 − x2 ≥ 0, g3 (X) = x2 − 40 ≥ 0, g4 (X) = x1 ≥ 0. Trong các điều kiện trên, điều kiện thứ nhất nảy sinh do yêu cầu sau: Một mặt, trục máy phải chịu đựng được tới mức tối đa lực Fmax = 12000N. Mặt khác, độ nén kết nối cho phép là 180N/mm. Các điều kiện còn lại là dễ hiểu. Việc phát biểu bài toán tối ưu đa mục tiêu dưới dạng toán học (chính là việc lập mô hình toán học cho vấn đề phát sinh từ thực tế) là một khâu rất quan trọng nhằm mô tả tốt nhất hành vi của hệ thống đang được xem xét, mặt khác nhằm tìm ra được các phương pháp tối ưu hóa có hiệu quả để đi tới một phương án đủ tốt và mang lại lợi ích. Sau đây, chúng ta hãy phân tích vắn tắt hai phương pháp giải bài toán thiết kế trục máy đã nêu ra ở trên. Phương pháp trọng số quy chuẩn Trong yếu tố cấu thành thứ nhất, hàm tổ hợp các mục tiêu cho bởi f(X) = ω1f1(X) + ω2 f2(X), trong đó ω1, ω2 là các trọng số không âm ứng với các hàm f1(X) và f2(X), ω1 + ω2 = 1. Do giá trị của hàm f1(X) thường lớn gấp rất nhiều lần giá trị của hàm f2(X), Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 52
53. −6 ω1 và ω2 được quy chuẩn như sau: f(X) = ω1'f1(X) + ω2'f2(X), với ω1' = ω1.10 /2,961 ; +3 ω2' = ω2.10 /0,338. Ở yếu tố cấu thành thứ hai, trong các bước lặp trung gian, người ra quyết định thay đổi lần lượt các cặp trọng số (ω1, ω2) với các giá trị là (0,2; 0,8), (0,8; 0,2), (0,6; 0,4) và (0,4; 0,6). Cặp trọng số cuối cùng cho phương án tối ưu Pareto thoả mãn nhất là 6 −3 x1 = 237,1 và x2 = 68,2, với f1(X) = 3,529 × 10 ; f2(X) = 0,437 × 10 . Còn ở yếu tố cấu thành thứ ba, tác giả Andrezj Osyczka đã sử dụng thuật toán tối ưu dò tìm ngẫu nhiên. Phương pháp tương tác dựa trên mức ưu tiên PRELIME Trước hết, ở yếu tố cấu thành thứ nhất, hai mục tiêu f1(X) và f2(X) được chuyển thành hai hàm (liên) thuộc mờ phản ánh độ thoả mãn của người ra quyết định đối với từng mục tiêu. Các hàm thuộc mờ này là các hàm tuyến tính từng khúc, được viết dưới dạng giản lược như sau cho một số điểm nội suy: μ1 6 1 0 nếu f1 ≥ 6,594 × 10 = a1 6 μ1 = 0,5 nếu f1 = 4 × 10 = b1 0,5 6 1 nếu f1 ≤ 2,944 × 10 = c1 f1 O c1 b1 a1 μ2 −3 1 0 nếu f2 ≥ 0,499 × 10 = a2 −3 μ2 = 0,5 nếu f2 = 0,450 × 10 = b2 0,5 −3 1 nếu f2 ≤ 0,338 × 10 = c2 c O 2 b2 a2 Đồ thị của các hàm thuộc mờ cho ở các hình vẽ trên. Phân tích hàm thuộc mờ μ1, ta thấy: người ra quyết định sẽ có độ thoả mãn 0 đối với mọi phương án làm cho f1 ≥ 6,594 6 6 6 × 10 ; độ thoả mãn 1 nếu f1 ≤ 2,944 × 10 ; và độ thoả mãn 0,5 nếu f1 = 4×10 . Độ thoả −6 mãn 0,5 được coi là độ thoả mãn tối thiểu và mức f1 = 4× 10 = b1 được gọi là mức ưu tiên tương ứng đối với mục tiêu f1. Tương tự chúng ta có thể phân tích về hàm thuộc μ2 và mức ưu tiên b2. Sau đó, hàm thoả dụng tổ hợp dạng Max−Min được thiết lập cho hai hàm mục tiêu riêng rẽ trên dưới dạng: Max{Min[μ1, μ2]} nhằm tìm ra phương án thoả dụng (x1, x2) trong miền ràng buộc của bài toán. Đối với yếu tố cấu thành thứ hai, người ra quyết định sẽ căn cứ vào thông tin do máy tính đưa ra để điều chỉnh các mức ưu tiên b1 và b2. Thay đổi các cặp mức ưu tiên
54. 6 −3 6 −3 (b1, b2) từ (4×10 ; 0,45×10 ) sang (3,6×10 ; 0,435×10 ), sẽ nhận được phương án sau 6 −3 (x1, x2) = (235,67 ; 67,67) với (f1, f2) = (3,58×10 ; 0,433×10 ). Trong yếu tố cấu thành thứ ba, các tác giả đã dùng thuật toán tìm kiếm ngẫu nhiên có điều khiển RST2ANU kết hợp với thuật toán mô phỏng tôi luyện (SA) để tìm ra các phương án tối ưu Pareto cho các bài toán trung gian thông qua việc giải bài toán tối ưu phi tuyến đơn mục tiêu dạng Max{Min[μ1, μ2]}. BÀI TẬP CHƯƠNG II 1. Với ví dụ trong mục 1.2 chương I, hãy áp dụng phương pháp đơn hình để đi theo quy trình 0 → A→ B nhằm đạt tới zmax. 2. Giải BTQHTT sau đây: z = 6x1 + 8x2 → Max, với các ràng buộc 3x1 + 3x2 ≤ 6 5x1 + 3x2 ≤ 8 x1, x2 ≥ 0. 3. Một xí nghiệp sản xuất hai loại sơn: sơn nội thất và sơn ngoại thất từ hai loại nguyên liệu A và B. Lượng dự trữ tối đa các loại nguyên liệu trên cho mỗi ngày là 6 tấn và 8 tấn. Để sản xuất một tấn sơn nội thất cần sử dụng 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, còn để sản xuất một tấn sơn ngoại thất cần sử dụng 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Ngoài ra, kết quả khảo sát thị trường cho biết: nhu cầu hàng ngày về sơn nội thất không vượt quá 1 tấn so với nhu cầu hàng ngày về sơn ngoại thất và nhu cầu sơn nội thất tối đa trên một ngày cũng chỉ giới hạn ở mức 2 tấn. Cho biết giá bán trên thị trường là 2000 một tấn sơn nội thất và 3000 USD một tấn sơn ngoại thất. Hãy xác định số lượng sơn nội thất và ngoại thất xí nghiệp cần sản xuất hàng ngày để đạt được tổng doanh thu lớn nhất. 4. Giải mô hình quy hoạch tuyến tính sau đây phát sinh từ vấn đề quy hoạch nhà ở và công viên cho một khu đô thị: z = 10000x1 + 15000x2 + 20000x3 → Max với các ràng buộc Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học 54