Giáo trình Vật trù học: Phần 1

Chia sẻ: Codon_11 Codon_11 | Ngày: | Loại File: PDF | Số trang:98

Thêm vào BST

Báo xấu

78
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các bạn cùng tìm hiểu cuốn "Giáo trình Vật trù học" của PGS.TS Nguyễn Hải Thanh dành cho các bạn sinh viên ngành Tin học và Công nghệ thông tin. Ở phần 1 cuốn giáo trình tập trung trình bày các vấn đề cơ bản về vật trù học; một số mô hình và phương pháp tối ưu; các mô hình mạng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Vật trù học: Phần 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
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 http://www.ebook.edu.vn 2
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
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 http://www.ebook.edu.vn 4
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
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 http://www.ebook.edu.vn 6
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ả
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 http://www.ebook.edu.vn 8
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.
− 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 http://www.ebook.edu.vn 10
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ụ.
- 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 http://www.ebook.edu.vn 12
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
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 http://www.ebook.edu.vn 14
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.
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 http://www.ebook.edu.vn 16
− 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
Đố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 http://www.ebook.edu.vn 18
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.
− 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 http://www.ebook.edu.vn 20