Bài 3: Quy hoạch tuyến tính — Tối ưu hóa bằng hệ BPT bậc nhất hai ẩn

I. Bài toán quy hoạch tuyến tính

1. Khái niệm

📋 Bài toán quy hoạch tuyến tính hai biến

Tìm giá trị lớn nhất hoặc nhỏ nhất của hàm mục tiêu: $f(x, y) = ax + by + c$ thỏa mãn hệ các ràng buộc gồm các bất phương trình/phương trình bậc nhất hai ẩn.

Tập các phương án chấp nhận được (feasible region): Miền nghiệm của hệ ràng buộc.
Phương án tối ưu: $(x_0, y_0)$ trong miền đó sao cho $f$ đạt cực trị.
Phương án cực biên (extreme points): Các đỉnh của đa giác miền nghiệm.

2. Định lý cơ bản

⚡ Định lý tối ưu tuyến tính

Nếu tập các phương án chấp nhận được là miền đa giác lồi khác rỗng và bị chặn, thì hàm mục tiêu $f(x, y) = ax + by$ luôn đạt giá trị lớn nhất và nhỏ nhất tại một trong các đỉnh (phương án cực biên) của đa giác đó.

⚠️ Lưu ý

Nếu miền nghiệm không bị chặn, hàm mục tiêu có thể không có cực đại (hoặc cực tiểu).
Không cần tính $f$ tại mọi điểm — chỉ cần tính tại các đỉnh của đa giác.

🔷 Dạng 1: Xác định miền nghiệm và các đỉnh của đa giác

📌 Phương pháp giải

Phương pháp:

Vẽ đường thẳng biên của từng BPT.
Xác định phần mặt phẳng thỏa từng BPT (thử điểm, VD: gốc $O(0,0)$ ).
Lấy phần chung → miền nghiệm của hệ.
Tìm các đỉnh bằng cách giải hệ phương trình từ 2 đường thẳng biên.

🔍 Ví dụ 1 — Xác định miền nghiệm

Xác định miền nghiệm $D$ của hệ: $\begin{cases} x + y \leq 6 \\ x \geq 0 \\ y \geq 0 \end{cases}$

💡 Xem lời giải

Đường thẳng $x + y = 6$ cắt các trục tại $A(6,0)$ và $B(0,6)$ .
$x \geq 0$ , $y \geq 0$ : phần tư thứ nhất.
Thử $O(0,0)$ : $0+0=0 \leq 6$ ✓ → miền chứa $O$ .

Miền nghiệm $D$ là tam giác $OAB$ (bao gồm cả biên), với các đỉnh: $O(0, 0),\quad A(6, 0),\quad B(0, 6)$

🔍 Ví dụ 2 — Hệ 4 BPT

Xác định các đỉnh của miền nghiệm: $\begin{cases} 2x + y \leq 8 \\ x + 2y \leq 7 \\ x \geq 0 \\ y \geq 0 \end{cases}$

💡 Xem lời giải

Các đường biên: $L_1: 2x+y=8$ ; $L_2: x+2y=7$ ; trục $Ox$ , $Oy$ .

Tìm các đỉnh:

$O(0, 0)$ : giao trục.
$A(4, 0)$ : $L_1 \cap Ox$ ( $2x=8 \Rightarrow x=4$ ).
$B(0, 3{,}5)$ : $L_2 \cap Oy$ ( $2y=7 \Rightarrow y=3{,}5$ ).
$C$ : giao $L_1 \cap L_2$ : giải $\begin{cases}2x+y=8\\x+2y=7\end{cases}$

Từ hệ: $3x = 9 \Rightarrow x = 3,\, y = 2$ . Vậy $C(3, 2)$ .

Các đỉnh: $O(0,0)$ , $A(4,0)$ , $C(3,2)$ , $B(0,3{,}5)$ .

📝 Thực hành — Dạng 1

Câu 1:Đỉnh nào sau đây KHÔNG thuộc miền nghiệm của $x + y \leq 4,\; x \geq 0,\; y \geq 0$?

Câu 2:Miền nghiệm của $2x + 3y \leq 12,\, x \geq 0,\, y \geq 0$ là:

Câu 3:Hệ $x+y \leq 5,\, x-y \leq 1,\, x \geq 0,\, y \geq 0$. Số đỉnh của miền nghiệm bằng bao nhiêu?

🔷 Dạng 2: Tối ưu hóa hàm mục tiêu tuyến tính

📌 Phương pháp giải

Phương pháp (Phương pháp đỉnh):

Xác định tất cả các đỉnh của miền nghiệm.
Tính giá trị hàm mục tiêu $f(x,y) = ax + by$ tại mỗi đỉnh.
So sánh và kết luận:
- Giá trị lớn nhất → tối đa.
- Giá trị nhỏ nhất → tối thiểu.

🔍 Ví dụ 1 — Tối đa hóa lợi nhuận

Tìm giá trị lớn nhất của $f(x,y) = 3x + 2y$ với: $\begin{cases} x + y \leq 6 \\ 2x + y \leq 9 \\ x \geq 0,\; y \geq 0 \end{cases}$

💡 Xem lời giải

Tìm đỉnh:

$O(0,0)$ : giao hai trục.
$A(4{,}5, 0)$ : $2x+y=9 \cap Ox \Rightarrow x=4{,}5$ .
$B(0, 6)$ : $x+y=6 \cap Oy$ .
$C$ : $x+y=6$ và $2x+y=9 \Rightarrow x=3, y=3$ . Vậy $C(3,3)$ .

Tính $f$ tại các đỉnh:

Đỉnh	$f = 3x+2y$
$O(0,0)$	$0$
$A(4{,}5, 0)$	$13{,}5$
$C(3, 3)$	$9+6=15$
$B(0, 6)$	$12$

$\boxed{f_{\max} = 15 \text{ tại } C(3,3)}$

🔍 Ví dụ 2 — Bài toán sản xuất

Xưởng có 2 loại hàng $A$ và $B$ . Một đơn vị $A$ cần $2$ giờ công và lãi $300$ nghìn; một đơn vị $B$ cần $3$ giờ công và lãi $400$ nghìn. Ngày làm tối đa $12$ giờ công, sản xuất tối đa $5$ đơn vị $A$ và $4$ đơn vị $B$ . Lập bài toán và tìm kế hoạch cho lãi lớn nhất.

💡 Xem lời giải

Gọi $x$ = số đơn vị $A$ , $y$ = số đơn vị $B$ ( $x, y$ nguyên không âm).

Ràng buộc: $\begin{cases} 2x + 3y \leq 12 \\ x \leq 5 \\ y \leq 4 \\ x \geq 0,\; y \geq 0 \end{cases}$

Hàm mục tiêu: $f = 300x + 400y$ (nghìn đồng) → cực đại.

Tìm đỉnh (chọn đỉnh khả thi):

$x=5, y=4$ : $2(5)+3(4)=22 > 12$ → loại.
$x=0, y=4$ : $3(4)=12 \leq 12$ ✓ → $O_1(0,4)$ : $f=1600$ .
$x=5, y=0$ : $2(5)=10 \leq 12$ ✓ → $A(5,0)$ : $f=1500$ .
Giao $2x+3y=12$ và $x=5$ : $10+3y=12 \Rightarrow y=2/3$ (không nguyên, lấy $y=0$ ).
Giao $2x+3y=12$ và $y=4$ : $2x+12=12 \Rightarrow x=0$ → đã có.
$x=0, y=0$ : $f=0$ .

Kiểm tra các điểm:

Điểm	$f = 300x + 400y$
$(0,4)$	$1600$
$(5,0)$	$1500$
$(5, 2/3) \to$ lấy $(4,1)$ hợp lý	$1600$

Thực ra đỉnh thực của đa giác (không yêu cầu nguyên): $C(3,2)$ khi giao $2x+3y=12$ và thực tế. Nhưng do ràng buộc $x\leq5,y\leq4$ :

Đỉnh tối ưu: $(0;4)$ với $f = \mathbf{1600}$ nghìn đồng.

Kết luận: Không sản xuất $A$ , sản xuất $4$ đơn vị $B$ để đạt lãi cao nhất $1600$ nghìn đồng/ngày.

🔍 Ví dụ 3 — Tối thiểu hóa chi phí

Tìm giá trị nhỏ nhất của $g(x,y) = x + 2y$ với: $\begin{cases} x + y \geq 3 \\ 2x + y \geq 4 \\ x \geq 0,\; y \geq 0 \end{cases}$

💡 Xem lời giải

Tìm đỉnh:

$A(3,0)$ : $x+y=3 \cap Ox$ .
$B(0,4)$ : $2x+y=4 \cap Oy$ .
$C$ : $x+y=3$ và $2x+y=4 \Rightarrow x=1, y=2$ . Vậy $C(1,2)$ .
$(4,0)$ : $2x+y=4 \cap Ox$ .

Miền nghiệm là phần không bị chặn (nằm trên cả hai đường thẳng).

Tính $g$ tại các đỉnh:

Đỉnh	$g = x+2y$
$A(3,0)$	$3$
$C(1,2)$	$5$
$B(0,4)$	$8$

$\boxed{g_{\min} = 3 \text{ tại } A(3,0)}$

📝 Thực hành — Dạng 2

Câu 1:Hàm $f(x,y) = 2x+y$ đạt giá trị lớn nhất tại đỉnh nào của tam giác $O(0,0)$, $A(4,0)$, $B(0,3)$?

Câu 2:Tìm min của $f = x+3y$ trên miền tam giác đỉnh $O(0,0)$, $A(6,0)$, $B(0,4)$:

Đúng / Sai

Câu 3Bài toán QHTT: max $f=5x+3y$ với $x+y\leq 4$, $x\geq0$, $y\geq0$. Xét tính đúng sai:

a)Miền nghiệm là tam giác có đỉnh $O(0,0)$, $A(4,0)$, $B(0,4)$

b)$f_{max}$ đạt tại $A(4,0)$

c)$f_{max} = 20$

d)$f_{max}$ cũng đạt tại $B(0,4)$

Câu 4:Tìm min của $f=2x+5y$ với $x+2y \geq 4$, $x\geq0$, $y\geq0$.

📝 Bài tập tự luận — Quy hoạch tuyến tính

Câu 1. Tìm giá trị lớn nhất và nhỏ nhất của $f(x,y) = 3x + 4y$ với: $x \geq 0,\; y \geq 0,\; x + y \leq 5,\; x + 2y \leq 8$

Câu 2. Một nông dân có $12$ ha đất để trồng lúa và ngô. Mỗi ha lúa cần $6$ triệu chi phí, sinh lợi $10$ triệu; mỗi ha ngô cần $4$ triệu, sinh lợi $7$ triệu. Ngân sách tối đa $60$ triệu. Lập và giải bài toán tối ưu để lợi nhuận lớn nhất.

Câu 3. Nhà máy sản xuất hai loại sản phẩm $P_1$ và $P_2$ . Mỗi đơn vị $P_1$ cần $1$ kg nguyên liệu $A$ , $2$ kg nguyên liệu $B$ và sinh lãi $5$ triệu. Mỗi đơn vị $P_2$ cần $3$ kg nguyên liệu $A$ , $1$ kg nguyên liệu $B$ và sinh lãi $4$ triệu. Có sẵn $12$ kg nguyên liệu $A$ và $8$ kg nguyên liệu $B$ . Lập và giải bài toán tìm kế hoạch sản xuất cho lãi lớn nhất.

Câu 4. Tìm giá trị nhỏ nhất của $f(x,y) = 2x + y$ với: $x + y \geq 4,\; x + 3y \geq 6,\; x \geq 0,\; y \geq 0$

Câu 5. (Nâng cao) Một công ty vận tải có 2 loại xe: xe tải lớn (tải $10$ tấn, tiêu thụ $20$ lít dầu/chuyến) và xe tải nhỏ (tải $5$ tấn, tiêu thụ $10$ lít dầu/chuyến). Cần chuyển ít nhất $100$ tấn hàng. Kho có $220$ lít dầu. Biết số xe lớn không quá $8$ chiếc. Tìm cách điều phối xe để số chuyến xe ít nhất (mỗi loại xe chạy $1$ chuyến).

🎯

Luyện tập trắc nghiệm

Câu hỏi ngẫu nhiên từ ngân hàng đề — kiểm tra kiến thức ngay!

🚀 Làm bài trắc nghiệm →

Miễn phí · Không giới hạn lần làm