7. BỐN TRƯỜNG HỢP ĐẶC BIỆT TRONG QUY HOẠCH TUYẾN TÍNH (PHƯƠNG PHÁP ĐỒ THỊ)
7.4. Nhiều lời giải tối ưu (Alternate Optimal Solutions)
Tình trạng hai hay nhiều lời giải tối ưu xuất hiện rất thường hay xảy ra trong bài tốn qui hoạch tuyến tính. Trên đồ thị, khi đường thẳng thể hiện hàm mục tiêu cĩ độ dốc bằng một ràng buộc nào đĩ (đường đẳng lợi nhuận hay đẳng chi phí di chuyển song song hoặc
trùng với một đường ràng buộc) ta cĩ tình trạng nhiều lời giải tối ưu.
Thơng thường, bất cứ điểm nào nằm trên đoạn nối bởi 2 điểm gĩc tối ưu sẽ cho chúng ta một lời giải tối ưu của bài tốn.
Nĩi chúng, khi gặp phải bài tốn QHTT cĩ nhiều lời giải tối ưu, các người quản lý hay người ra quyết định cĩ thể chọn một một lời giải tối ưu cụ thể theo ý muốn của mình dựa trên sự kết hợp các biến ra quyết định.
Ví dụ: Một nhà quản lý của một cơng ty nhận ra sự hiện diện của hiện tượng nhiều lời giải tối ưu khi thành lập bài tốn QHTT như sau:
+ Hàm mục tiêu (Objective Fuction): Max Lợi nhuận Z = 3x1 + 2x2 (USD)
+ Ràng buộc (Constraints): 6x1 + 4x2 ≤24 x1 ≤3 x1, x2 ≥ 0
Quan sát đồ thị ta thấy, đường đẳng lợi nhuận thứ 1 ở mức 8 USD song song với đường ràng buộc 1. Tại mức lợi nhuận bằng 12 USD, đường đẳng lợi nhuận trùng với đường ràng buộc 1. Điều này cĩ nghĩa là tập hợp tất cả các điểm nằm trong đoạn thẳng AB đêu là nghiệm tối ưu của bài tốn. Trong trường hợp này, sự tồn tại nhiều lời giải tối ưu sẽ giúp cho nhà quản lý rất linh hoạt trong việc ra quyết định lựa chọn các phương án khác nhau nhưng đều cho cùng một mức lợi nhuận như nhau.
Hình 4.14. Bài tốn cĩ nhiều lời giải tối ưu