Chương 4
QUI HOẠCH TUYẾN TÍNH DẠNG ĐẶC BIỆT
§1. QUI HOẠCH TUYẾN TÍNH VỚI BIẾN BỊ CHẶN TRÊN
1.1. Nội dung vấn đề
– Xét bài toán qui hoạch tuyến tính dạng bất kỳ (chính tắc, chuẩn tắc, tổng quát), trong đó một số hay tất cả các biến số có thêm ràng buộc sau đây, gọi là ràng buộc cận trên:
xju, tức là Jc {1, 2, …, n}, (1,1)
– Trong đó u, là hằng số dương cho trước biểu thị giá trị tối đa mà biến x, có thể nhận. Kinh nghiệm tính toán giải các bài toán qui hoạch tuyến tính bằng phương pháp đơn hình cho thấy thời gian giải phụ thuộc chủ yếu vào số ràng buộc chính m, còn các ràng buộc không âm (ràng buộc về dấu) có ảnh hưởng không đáng kể. Vì thế, nếu ghép thêm các ràng buộc cận trên (1.1) vào các ràng buộc chính sẽ làm tăng đáng kể thời gian tính toán. Để khắc phục nhược điểm này ta hãy tạm gác bỏ các ràng buộc cận trên khỏi các ràng buộc chính và sẽ xử lý chúng một cách riêng biệt, tương tự như đã làm đối với các ràng buộc về dấu. Việc tạm bỏ các ràng buộc cận trên như thế sẽ không ảnh hưởng tới kết quả giải, nếu như không có biến số nào tăng
