Bài toán quy hoạch tuyến tính thực tế

Một xưởng làm hai loại sản phẩm A, B. Mỗi kg A cần $2$ kg nguyên liệu và $30$ giờ; mỗi kg B cần $4$ kg nguyên liệu và $15$ giờ. Xưởng có $200$ kg nguyên liệu và $1\,200$ giờ. Lãi $40$ nghìn đồng mỗi kg A, $30$ nghìn đồng mỗi kg B. Hỏi làm bao nhiêu kg mỗi loại để lãi lớn nhất?

Giải. Gọi $x$, $y$ là số kg A, B ($x, y \ge 0$). Ràng buộc:

Rút gọn (chia $2$ và chia $15$): $x + 2y \le 100$, $2x + y \le 80$. Lãi $F = 40x + 30y$ (nghìn đồng).

Đỉnh: $O(0;\,0)$; $y = 0$ với $2x + y = 80$: $(40;\,0)$; $x = 0$ với $x + 2y = 100$: $(0;\,50)$; $x + 2y = 100$ và $2x + y = 80$: nhân phương trình đầu với $2$ rồi trừ: $3y = 120$, $y = 40$, $x = 20$: $(20;\,40)$. Kiểm: $(40;0)$ thoả $x + 2y = 40 \le 100$; $(0;50)$ thoả $2x + y = 50 \le 80$.

Kết luận. Làm $20$ kg A và $40$ kg B, lãi lớn nhất $2\,000$ nghìn đồng (hai triệu đồng). Nhận xét: khi đó nguyên liệu dùng $2\cdot 20 + 4\cdot 40 = 200$ kg (hết) và giờ $30\cdot 20 + 15\cdot 40 = 1\,200$ (hết): cả hai ràng buộc cùng "chặt", đó là lí do tối ưu ở đỉnh cắt nhau.

Cần pha khẩu phần từ hai loại thức ăn. Mỗi kg loại A chứa $3$ đơn vị protein, $1$ đơn vị vitamin, giá $20$ nghìn đồng; mỗi kg loại B chứa $1$ đơn vị protein, $2$ đơn vị vitamin, giá $15$ nghìn đồng. Khẩu phần phải có ít nhất $9$ đơn vị protein và $8$ đơn vị vitamin. Mua bao nhiêu kg mỗi loại để chi phí nhỏ nhất?

Giải. $x$, $y$ là số kg A, B ($x, y \ge 0$). Ràng buộc: protein $3x + y \ge 9$; vitamin $x + 2y \ge 8$. Chi phí $F = 20x + 15y$ (nghìn đồng), cần nhỏ nhất.

Miền không bị chặn (bài 3, ví dụ 3) với các đỉnh $(0;\,9)$, $(2;\,3)$, $(8;\,0)$. Vì $a = 20 > 0$ và $b = 15 > 0$, $F$ tăng khi đi ra xa nên có min.

Kết luận. Mua $2$ kg loại A và $3$ kg loại B, chi phí nhỏ nhất $85$ nghìn đồng. Kiểm: protein $6 + 3 = 9$, vitamin $2 + 6 = 8$, vừa đủ cả hai.

Một tổ sản xuất hai loại hộp quà I và II, tính theo trăm hộp: $x$ trăm hộp I, $y$ trăm hộp II. Máy đóng gói chỉ chạy tối đa $8$ trăm hộp tổng cộng; công đoạn cắt tốn $x + 3y$ giờ, tối đa $18$ giờ; công đoạn dán tốn $3x + y$ giờ, tối đa $18$ giờ. Lãi $2$ triệu đồng mỗi trăm hộp I, $3$ triệu đồng mỗi trăm hộp II. Tìm phương án lãi lớn nhất.

Giải. Ràng buộc: $x + y \le 8$, $x + 3y \le 18$, $3x + y \le 18$, $x, y \ge 0$. Hàm mục tiêu $F = 2x + 3y$ (triệu đồng).

Ba đường $x + 3y = 18$ và $3x + y = 18$ cắt nhau ở $(4{,}5;\,4{,}5)$, nhưng điểm đó có $x + y = 9 > 8$ nên không thuộc miền; ràng buộc $x + y \le 8$ đã cắt mất góc đó. Các đỉnh của miền:

• $O(0;\,0)$.
• $y = 0$ với $3x + y = 18$: $(6;\,0)$ (thoả $x + y = 6 \le 8$).
• $x = 0$ với $x + 3y = 18$: $(0;\,6)$ (thoả $x + y = 6 \le 8$).
• $x + y = 8$ với $3x + y = 18$: trừ hai vế $2x = 10$, $(5;\,3)$ (thoả $x + 3y = 14 \le 18$).
• $x + y = 8$ với $x + 3y = 18$: trừ hai vế $2y = 10$, $(3;\,5)$ (thoả $3x + y = 14 \le 18$).

Kết luận. $3$ trăm hộp loại I và $5$ trăm hộp loại II, lãi lớn nhất $21$ triệu đồng.

Giữ nguyên các ràng buộc của ví dụ 1, nhưng nay lãi là $20$ nghìn đồng mỗi kg A và $40$ nghìn đồng mỗi kg B. Tìm lãi lớn nhất.

Giải. $F = 20x + 40y = 20(x + 2y)$. Tại các đỉnh: $F(0;\,0) = 0$; $F(40;\,0) = 800$; $F(0;\,50) = 2\,000$; $F(20;\,40) = 400 + 1\,600 = 2\,000$.

Hai đỉnh $(0;\,50)$ và $(20;\,40)$ cùng cho lãi lớn nhất $2\,000$ nghìn đồng, nên mọi điểm của cạnh nối chúng (nằm trên $x + 2y = 100$, vì $F = 20(x + 2y) = 2\,000$) đều tối ưu. Ví dụ $(10;\,45)$: $x + 2y = 100$ và $2x + y = 65 \le 80$, hợp lệ, lãi $200 + 1\,800 = 2\,000$. Ý nghĩa: mọi phương án dùng hết nguyên liệu (và không quá giờ máy) đều cho cùng lãi; nhà sản xuất chọn theo tiêu chí khác (ví dụ ít tốn giờ nhất).