Bài toán quy hoạch tuyến tính hai biến mô hình hóa việc phân bổ nguồn lực với các ràng buộc tuyến tính. Sau khi xác định miền nghiệm đa giác, giá trị lớn nhất hoặc nhỏ nhất của hàm mục tiêu đạt tại một đỉnh của miền khả thi.
Trước khi học phần này, bạn nên xem lại Cách đọc và mô hình hóa bài toán thực tế bằng hàm số để nắm các kiến thức nền liên quan.
Kiến thức cần nhớ
- Mỗi ràng buộc bậc nhất hai ẩn biểu diễn một nửa mặt phẳng.
- Miền khả thi là giao của tất cả các nửa mặt phẳng và điều kiện không âm nếu có.
- Hàm mục tiêu có dạng \(F=ax+by\).
- Với miền đa giác kín, chỉ cần tính F tại các đỉnh để tìm GTLN/GTNN.
Phương pháp giải theo từng bước
- Đặt hai biến đại diện cho hai loại sản phẩm/hoạt động.
- Chuyển các giới hạn nguồn lực thành hệ bất phương trình.
- Vẽ các đường biên và xác định miền giao.
- Tìm tọa độ các đỉnh, tính hàm mục tiêu tại từng đỉnh rồi chọn phương án tốt nhất.
Ví dụ 1
Bài toán: Miền có các đỉnh \((0,0),(4,0),(2,3),(0,5)\). Tối đa hóa \(F=3x+2y\).
Lời giải: Giá trị tại các đỉnh lần lượt 0,12,12,10. GTLN bằng 12, đạt tại \((4,0)\) và \((2,3)\).
Ví dụ 2
Bài toán: Tại sao không chỉ thử một điểm bên trong miền?
Lời giải: Hàm mục tiêu tuyến tính trên đa giác đạt cực trị tại ít nhất một đỉnh; thử điểm trong không bảo đảm tối ưu.
Lỗi thường gặp
- Vẽ sai phía của bất phương trình.
- Bỏ điều kiện \(x\ge0,y\ge0\) trong bài số lượng.
- Tính thiếu một đỉnh giao của hai đường biên.
Mẹo kiểm tra và trình bày
- Dùng điểm thử như O(0,0) để xác định nửa mặt phẳng nếu O không nằm trên đường biên.
- Lập bảng giá trị hàm mục tiêu tại các đỉnh để tránh sót.
Bài tự luyện
- Bài 1: Các đỉnh là (0,0),(3,0),(0,4), tối đa F=2x+y. Đáp án/Gợi ý: Giá trị 0,6,4 nên tối đa tại (3,0).
- Bài 2: Nếu hai đỉnh cho cùng GTLN, có thể có nhiều phương án tối ưu không? Đáp án/Gợi ý: Có; thậm chí cả đoạn nối hai đỉnh có thể tối ưu nếu hàm mục tiêu song song cạnh đó.
Học tiếp trong cùng chuyên đề
Bạn có thể xem thêm các bài trong Toán thực tế – Mô hình hóa.