Phương pháp · Quy hoạch khi biến là số nguyên · Toán 10

01Phương pháp giải theo dạng

Giải bài toán thực (bài 5, 6): vẽ miền, tìm đỉnh, giá trị tối ưu thực $F^*$ (làm cận).
Nếu đỉnh tối ưu thực là điểm nguyên: xong.
Nếu không, chọn một trong hai cách:
- Duyệt theo một ẩn: với mỗi giá trị nguyên của $y$ (hoặc $x$ ) trong khoảng cho phép, tìm các $x$ nguyên khả thi, tính $F$ (chọn $x$ tốt nhất cho mỗi $y$ ); lập bảng và so sánh.
- Hạ đường mức: thử $k = \lfloor F^*\rfloor, \lfloor F^*\rfloor - 1, \ldots$ cho đến khi có điểm nguyên khả thi.
Kiểm ràng buộc cho điểm kết luận (thế vào mọi bất phương trình).
Kết luận: giá trị tối ưu nguyên và điểm đạt.

Xác định khoảng giá trị nguyên của $y$ mà miền có điểm.
Với mỗi $y$ , đổi các bất phương trình thành khoảng cho $x$ ; lấy giao khoảng, đếm số số nguyên trong khoảng (từ $m$ đến $n$ có $n - m + 1$ số).
Cộng các hàng. Kiểm bằng cách vẽ lưới.

Lỗi	Vì sao sai	Cách tránh
Làm tròn nghiệm thực lên hoặc xuống	Có thể ra ngoài miền, hoặc không tối ưu	Kiểm ràng buộc, rồi duyệt
Chỉ kiểm điểm làm tròn mà không kiểm các điểm nguyên khác gần đỉnh	Tối ưu nguyên có thể ở điểm khác	Duyệt cả bảng theo một ẩn
Duyệt theo $y$ nhưng lấy $x$ theo nhầm hướng	Hệ số $F$ âm thì $x$ nhỏ mới tốt	Xét dấu hệ số của $x$ trong $F$ trước
Quên các điểm trên biên	Biên thuộc miền (dấu $\le$ )	Đếm cả hai đầu mút của khoảng
Đếm số nguyên trong $[m;\,n]$ là $n - m$	Phải là $n - m + 1$	Kiểm với khoảng nhỏ, ví dụ $[2;\,5]$ có $4$ số
Kết luận kết quả thực cho bài nguyên	Đề đòi nguyên	Đọc kĩ điều kiện của ẩn