Bài toán quy hoạch tuyến tính là gì?
Đây là bài toán tìm giá trị lớn nhất hoặc nhỏ nhất của một hàm mục tiêu bậc nhất F = ax + by, với x và y phải thoả một hệ bất phương trình bậc nhất hai ẩn. Nghiệm của hệ ràng buộc là một miền đa giác lồi trên mặt phẳng toạ độ.
Các bước giải
- Vẽ miền nghiệm của hệ bất phương trình ràng buộc — được một đa giác lồi.
- Tìm toạ độ các đỉnh của đa giác (giao của các đường biên).
- Tính F tại từng đỉnh bằng cách thay toạ độ vào ax + by.
- So sánh các giá trị để chọn GTLN hoặc GTNN cần tìm.
Vì sao cực trị luôn ở một đỉnh?
Với mỗi giá trị k, phương trình ax + by = k là một đường thẳng; khi k tăng, đường thẳng đó tịnh tiến song song về một phía. Đường mức cuối cùng còn chạm miền nghiệm sẽ tiếp xúc tại một đỉnh của đa giác. Do miền nghiệm lồi và bị chặn, F đạt cả cực đại lẫn cực tiểu tại các đỉnh — không cần thử vô hạn điểm bên trong.
Ứng dụng thực tế
Quy hoạch tuyến tính có mặt khắp nơi:
- 🏭 Lập kế hoạch sản xuất tối đa lợi nhuận với nguyên liệu hạn chế.
- 🚚 Vận tải, phân bổ nguồn lực với chi phí nhỏ nhất.
- 🥗 Bài toán khẩu phần ăn đủ chất mà rẻ nhất.
- 💼 Đầu tư danh mục để tối ưu lợi nhuận trong ràng buộc rủi ro.