Phương pháp đơn hình giải bài toán quy hoạch tuyến tính 1. Mô hình quy hoạch tuyến tính . Phát biểu mô hì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 hoá | Chương II Phương pháp đơn hình giải bài toán quy hoạch tuyến tính 1. Mô hình quy hoạch tuyến tính . Phát biểu mô hì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 hoá cực đại hoá hay cực tiểu hoá hàm mục tiêu z f x c1x1 c2x2 . cnxn Max Min với các điều kiện ràng buộc a11x1 a12x2 . a1nxn b1 a2x1 a22x2 . a2nxn b2 . am1x1 am2x2 . amnxn bm Kx1 x2 . xn 0 điều kiện không âm . Ví dụ 1. Xét BTQHTT Max z 8x1 6x2 với các ràng buộc 4x1 2x2 60 2x1 4x2 48 x1 x2 0. 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ị . Hãy xác định phương án sản xuất đạt lợi nhuận lớn nhất biết lợi nhuận đơ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 I. 2. Phương pháp đồ thị Phương pháp đồ thị có ý nghĩa minh họa và giúp hiểu bản chất vấn đề. Bước 1 Vẽ miền các phương án khả thi còn gọi là miền ràng buộc 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 thoả mãn tất cả các ràng buộc đã có kể cả điều kiện không âm của các biến xem hình II. 1 . - Trước hết chúng ta vẽ đường thẳng có phương trình là 4x1 2x2 60 bằng cách xác định hai điểm thuộc đường thẳng x1 0 x2 30 và x1 15 x2 0 . Đường thẳng này 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 phần còn lại 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ẽ đường thẳng có phương trình là 2x1 4x2 48 bằng cách xác định hai điểm thuộc đường thẳng là x1 0 x2 12 và
