Toán lớp 12: Chuyên đề — Bài 3: Vận dụng hệ bất phương trình bậc nhất hai ẩn để giải bài toán quy hoạch tuyến tính

Mục tiêu bài học

• Chọn biến và lập được hàm mục tiêu tuyến tính cùng hệ ràng buộc/điều kiện không âm từ bối cảnh.
• Biểu diễn và kiểm tra được miền khả thi là giao các nửa mặt phẳng.
• Xác định được các đỉnh cần xét và giá trị hàm mục tiêu tại các phương án ứng viên trong trường hợp đơn giản.
• Kết luận và kiểm tra được phương án tối ưu theo đơn vị, tính khả thi; nhận biết mô hình vô nghiệm hoặc thiếu ràng buộc rõ ràng.

Kiến thức cần nhớ

• Mô hình gồm biến, hàm mục tiêu tuyến tính, ràng buộc tuyến tính, điều kiện không âm/đơn vị.
• Miền khả thi là giao mọi nửa mặt phẳng; mọi ứng viên phải thỏa tất cả ràng buộc.
• Trên đa giác khả thi hữu hạn, giá trị tối ưu tuyến tính đạt tại ít nhất một đỉnh nếu tồn tại.
• Kết luận phải nêu phương án và kiểm vô nghiệm/thiếu ràng buộc; không dùng thuật toán đơn hình hoặc đối ngẫu.

Khởi động và dự đoán

• Khởi động: Sản phẩm A dùng 2 giờ, B dùng 1 giờ; tối đa 8 giờ; x,y là số lượng không âm. Viết ràng buộc thời gian. Hãy dự đoán kết quả, ghi điều kiện cần kiểm rồi mới xem lời giải.

Thuật ngữ và kí hiệu

D: miền khả thi F: hàm mục tiêu (x,y): biến quyết định kèm đơn vị

Công thức, điều kiện và ý nghĩa

Biểu thức	Điều kiện	Ý nghĩa
F=ax+by	a,b là hệ số mục tiêu; x,y có nghĩa/đơn vị đã nêu — (x,y) thuộc miền khả thi D — Nếu D rỗng hoặc không bị chặn theo hướng mục tiêu, không tuyên bố có giá trị tối ưu hữu hạn.	So sánh F tại các đỉnh của đa giác D.
D=⋂ các nửa mặt phẳng ràng buộc	mỗi bất phương trình được dịch đúng từ ngữ cảnh — thường x≥0,y≥0 và các giới hạn khác — Một điểm thỏa vài nhưng không thỏa tất cả ràng buộc không thuộc D.	Xác định toàn bộ phương án khả thi.

Tự kiểm tra kiến thức nền

• Sau khi tìm các đỉnh cần làm gì?
• Hai ràng buộc mâu thuẫn dẫn tới kết luận nào?

Khung lập luận và chứng minh

• Ghi rõ giả thiết, kết luận, miền của biến và điều kiện của từng công thức.
• Mỗi biến đổi phải chỉ ra là tương đương hay chỉ là hệ quả; trường hợp hệ quả phải thử lại.
• Đối chiếu từng bước với định nghĩa, điều kiện công thức và kết luận của bài.
• Kiểm trường hợp biên và đối chiếu bằng một cách độc lập trước khi kết luận.

Trường hợp biên cần nhớ

• Nếu D rỗng hoặc không bị chặn theo hướng mục tiêu, không tuyên bố có giá trị tối ưu hữu hạn.
• Một điểm thỏa vài nhưng không thỏa tất cả ràng buộc không thuộc D.
• Ngoài phạm vi bài: thuật toán đơn hình.
• Ngoài phạm vi bài: đối ngẫu.
• Ngoài phạm vi bài: quy hoạch nguyên tổng quát.
• Ngoài phạm vi bài: tối ưu phi tuyến.

Phản ví dụ chống học máy móc

• Một điểm cho giá trị mục tiêu rất lớn nhưng nằm ngoài D không phải phương án tốt; tính tối ưu luôn bị ràng buộc bởi tính khả thi.

Ứng dụng và mô hình thực tế

• Dùng mô hình của bài để phân tích một phương án thực tế; phải công khai giả định, đơn vị, giới hạn và rủi ro.

Minh họa trực quan

Miền khả thi và hàm mục tiêu

Miền xanh là giao mọi ràng buộc; chỉ các đỉnh thuộc miền được đưa vào so sánh.

x≥0

y≥0

x+y≤4

2x+y≤5

F=3x+2y; đạt giá trị lớn nhất tại (1;3), F=9

Ví dụ giải từng bước

Ví dụ 1

Sản phẩm A dùng 2 giờ, B dùng 1 giờ; tối đa 8 giờ; x,y là số lượng không âm. Viết ràng buộc thời gian.

1. 1 Mỗi A đóng góp 2x giờ.
2. 2 Mỗi B đóng góp y giờ.
3. 3 Tổng không vượt 8 và x,y≥0.

Đáp án: 2x+y≤8, x≥0, y≥0.

Tự kiểm: Thế x=2,y=3 cho 7 giờ, là phương án khả thi theo ràng buộc này.

Ví dụ 2

Tối đa F=3x+2y trên miền có các đỉnh (0,0),(4,0),(2,3),(0,4).

1. 1 Tính F lần lượt 0,12,12,8.
2. 2 Giá trị lớn nhất là 12.
3. 3 Có hai đỉnh cùng đạt.

Đáp án: F_max=12 tại (4,0) và (2,3); nếu toàn cạnh nối chúng khả thi và F không đổi thì mọi điểm cạnh ấy cũng tối ưu.

Tự kiểm: Kiểm trực tiếp giá trị ở từng đỉnh; không bỏ nghiệm tối ưu không duy nhất.

Ví dụ 3

Hệ có x≥2 và x≤1. Miền khả thi ra sao?

1. 1 Hai điều kiện áp cùng biến.
2. 2 Không có số thực vừa ≥2 vừa ≤1.
3. 3 Giao hai miền rỗng.

Đáp án: Bài toán vô nghiệm khả thi; không có phương án tối ưu.

Tự kiểm: Mâu thuẫn 2≤x≤1 là bất khả.

Ví dụ 4

Kiểm điểm (2,1) có thuộc D: x≥0,y≥0,x+y≤4,2x+y≤5 không.

1. 1 Hai tọa độ không âm.
2. 2 x+y=3≤4.
3. 3 2x+y=5≤5.

Đáp án: (2,1) thuộc miền khả thi D.

Tự kiểm: Điểm thỏa đủ bốn ràng buộc, kể cả một ràng buộc tại biên.

Lỗi sai thường gặp

• Sai lầm cần tránh: Chỉ vẽ từng nửa mặt phẳng mà không lấy giao.
• Sai lầm cần tránh: Bỏ x,y≥0 khi ngữ cảnh đòi hỏi.
• Sai lầm cần tránh: Chọn điểm không thỏa tất cả ràng buộc.
• Sai lầm cần tránh: Dùng thuật toán ngoài phạm vi bài.