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

Tìm số nguyên không âm $x$, $y$ thoả $2x + 3y \le 14$, $4x + y \le 13$ sao cho $F = 4x + 5y$ lớn nhất.

Giải. Bước 1: bài toán thực. Các đỉnh: $O(0;\,0)$; $y = 0$ với $4x + y = 13$: $(3{,}25;\,0)$; $x = 0$ với $2x + 3y = 14$: $\bigl(0;\,\tfrac{14}3\bigr)$; hai bờ cắt nhau: từ $y = 13 - 4x$ thay vào $2x + 3(13 - 4x) = 14$ được $-10x = -25$, $x = 2{,}5$, $y = 3$: $(2{,}5;\,3)$. Giá trị $F$: $0$; $13$; $\tfrac{70}3 \approx 23{,}3$; $4\cdot 2{,}5 + 5\cdot 3 = 25$. Vậy max thực là $25$ tại $(2{,}5;\,3)$, không nguyên, và max nguyên $\le 25$.

Bước 2: kiểm các điểm nguyên lân cận. $(3;\,3)$: $2\cdot 3 + 3\cdot 3 = 15 > 14$, ngoài miền. $(3;\,2)$: $4\cdot 3 + 2 = 14 > 13$, ngoài miền. $(2;\,3)$: $4 + 9 = 13 \le 14$, $8 + 3 = 11 \le 13$: khả thi, $F = 8 + 15 = 23$. Nhưng chưa chắc đã tốt nhất.

Bước 3: duyệt theo $y$. Với mỗi $y$, $x$ lớn nhất là $\min\Bigl(\bigl\lfloor\tfrac{14 - 3y}2\bigr\rfloor,\ \bigl\lfloor\tfrac{13 - y}4\bigr\rfloor\Bigr)$ (vì hệ số $4$ của $F$ dương, $x$ càng lớn càng tốt):

($y \ge 5$ thì $3y \ge 15 > 14$, không có nghiệm.) Vậy $\max F = 24$ tại $(1;\,4)$. Kiểm: $2 + 12 = 14 \le 14$, $4 + 4 = 8 \le 13$, đúng.

Kiểm bằng hạ đường mức: $F = 25$ có điểm nguyên $(0;\,5)$ và $(5;\,1)$ trong góc phần tư, nhưng $(0;\,5)$ có $15 > 14$ và $(5;\,1)$ có $21 > 13$: đều ngoài miền. $F = 24$ có $(1;\,4)$: khả thi. Khớp.

Kết luận. $\max F = 24$ tại $(1;\,4)$, nhỏ hơn giá trị thực $25$, và không ở gần điểm làm tròn $(2{,}5;\,3)$ lắm (làm tròn thành $(2;\,3)$ chỉ được $23$).

Đoàn $130$ người cần thuê xe. Xe loại X chở $40$ người, giá $6$ triệu đồng; xe loại Y chở $25$ người, giá $4$ triệu đồng. Công ty chỉ có tối đa $4$ xe X và $6$ xe Y. Thuê thế nào để chi phí thấp nhất?

Giải. $x$, $y$ là số xe X, Y: $x, y$ nguyên, $0 \le x \le 4$, $0 \le y \le 6$, $40x + 25y \ge 130$. Chi phí $F = 6x + 4y$ (triệu).

Bài toán thực: đỉnh $(3{,}25;\,0)$ (từ $40x = 130$), $(4;\,0)$, $(0;\,5{,}2)$, $(0;\,6)$, $(4;\,6)$. $F$: $19{,}5$; $24$; $20{,}8$; $24$; $48$. Min thực $19{,}5$ tại $(3{,}25;\,0)$: không nguyên.

Duyệt theo $x$ (với $y$ nhỏ nhất thoả $25y \ge 130 - 40x$ và $y \le 6$):

Kết luận. Thuê $2$ xe X và $2$ xe Y: chở $80 + 50 = 130$ người đúng đủ, chi phí $20$ triệu, nhỏ nhất. Làm tròn lên $(4;\,0)$ (từ $3{,}25$) cho $24$ triệu; làm tròn xuống $(3;\,0)$ chở $120 < 130$ người, vi phạm ràng buộc.

Có bao nhiêu điểm nguyên thuộc miền nghiệm của $x \ge 0$, $y \ge 0$, $x + y \le 4$, $y - x \le 2$?

Giải. Ràng buộc theo $x$ cho mỗi $y$: $x \ge 0$, $x \le 4 - y$, $x \ge y - 2$.

Tổng $5 + 4 + 3 + 1 = 13$ điểm nguyên. (Miền có diện tích $7$; số điểm nguyên $13$ bao gồm cả điểm trên biên.)