Quy hoạch tuyến tính khi biến là số nguyên

Điểm $(x;\,y)$ với $x$, $y$ đều là số nguyên gọi là điểm nguyên (điểm trên mắt lưới). Bài toán nguyên: tìm điểm nguyên của miền nghiệm làm $F$ lớn nhất (hay nhỏ nhất). Trên miền nghiệm có thể chỉ có hữu hạn điểm nguyên (nếu miền bị chặn), ta có thể xét hết.

Vì vậy bài toán thực cho ta một cận: ví dụ nếu max thực là $25$, thì max nguyên không thể vượt $25$.

Điểm tối ưu thực nằm ở đỉnh, tức giao của hai bờ. Điểm nguyên gần đó có thể:

• nằm ngoài miền (vi phạm một ràng buộc);
• nằm trong miền nhưng cho $F$ kém xa các điểm nguyên khác;
• không phải điểm nguyên tối ưu, vì tối ưu nguyên có thể ở rất xa đỉnh thực (khi đường mức gần song song với một cạnh).

Cách nhìn đẹp nhất: đường mức $F = k$ trượt từ vị trí tối ưu thực xuống dần. Với mỗi $k$ nguyên (nếu hệ số $a$, $b$ nguyên thì $F$ nhận giá trị nguyên tại điểm nguyên), kiểm xem trên đường $ax + by = k$ có điểm nguyên thuộc miền không. Giá trị $k$ đầu tiên (lớn nhất) mà có là $\max F$ nguyên. Cách này nhanh khi hệ số lớn, và cho thấy rõ vì sao đáp án không ở sát đỉnh thực.

• Điểm nguyên: cả $x$ và $y$ nguyên. Max nguyên $\le$ max thực; min nguyên $\ge$ min thực.
• Làm tròn đỉnh thực dễ ra ngoài miền hoặc không tối ưu.
• Hai cách giải: duyệt theo một ẩn (lập bảng), hoặc hạ đường mức từ $F^*$.
• Luôn kiểm điểm kết luận vào mọi ràng buộc.
• Đếm điểm nguyên: theo từng hàng $y$, số số nguyên trong $[m;\,n]$ là $n - m + 1$.