GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BẰNG PHƯƠNG PHÁP ĐƠN HÌNH 1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BTQHTT DẠNG CHÍNH TẮC . Ví dụ . Xét BTQHTT: Max z = 8x1 + 6x2, với các ràng buộc 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0 Đưa BTQHTT dạng chuẩn tắc trên về dạng chính tắc bằng các biến bù không âm x3 và x4 như sau: Max z = 8x1 + 6x2 + 0x3 + 0x4 với các ràng buộc 4x1 + 2x2 + x3 2x1 + 4x2 x1, x2, x3, x4. | Chương II GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BẰNG PHƯƠNG PHÁP ĐƠN HÌNH 1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BTQHTT DẠNG CHÍNH TẮC . Ví dụ . Xét BTQHTT Max z 8xi 6x2 với các ràng buộc 4x1 2x2 60 5 2x1 4x2 48 s. xi x2 0 Đưa BTQHTT dạng chuẩn tắc trên về dạng chính tắc bằng các biến bù không âm x3 và x4 như sau Max z 8x1 6x2 0x3 0x4 với các ràng buộc r4x1 2x2 x3 60 2x1 4x2 x4 48 x1 x2 x3 x4 0. Chú ý. BTQHTT có dạng chính tắc là BTQHTT với các biến không âm các ràng buộc có 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. Cách lập và biến đổi các bảng đơn hình Để 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ư trong bảng . 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 trên hình 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 loại II nào đượ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ó 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. 23 Bảng . Các bảng đơn hình giải BTQHTT Hệ số hàm mục tiêu Cj Biến cơ sở Phương án c1 8 c2 6 c3 0 c4 0 x1 x2 x3 x4 Bảng đơn hình bước 1 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 Aj cj - zj A1 8
