Quy hoạch tuyến tính thực tế · Toán 10

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

Lãi lớn nhất, chi phí nhỏ nhất

Mục tiêu

Chuyển một bài toán lời văn (sản xuất, pha chế, khẩu phần) thành hệ bất phương trình cùng một hàm mục tiêu $F = ax + by$ .
Giải bằng miền nghiệm và các đỉnh, kết luận bằng lời có đơn vị.
Nhận biết bài lãi lớn nhất (ràng buộc dạng $\le$ ) và bài chi phí nhỏ nhất (ràng buộc dạng $\ge$ ), và trường hợp có nhiều phương án tối ưu.

Khởi động

Một xưởng có lượng nguyên liệu và số giờ máy cố định, làm được hai loại sản phẩm với lãi khác nhau. Làm nhiều loại lãi cao thì hết nguyên liệu; làm nhiều loại tiêu hao ít thì thừa tiền lãi. Có vô số cách chia, nhưng chỉ một (hoặc một cạnh) cho lãi cao nhất. Ngược lại, một trại nuôi cần đủ dinh dưỡng với chi phí thấp nhất: ăn rẻ mà thiếu chất thì hỏng, đủ chất mà đắt thì lỗ. Cả hai tình huống đều là quy hoạch tuyến tính hai ẩn: đặt ẩn, viết ràng buộc là các bất phương trình bậc nhất, tìm cực trị của một hàm bậc nhất trên miền nghiệm. Bài 5 đã cho công cụ; bài này lo phần "dịch" từ lời văn.

01Kiến thức cần nhớ

1. Ba thành phần của bài toán

Thành phần	Là gì	Ví dụ
Ẩn	số lượng cần quyết định, $x$ , $y$ (kèm đơn vị)	số kg sản phẩm A, B
Ràng buộc	các bất phương trình về tài nguyên, yêu cầu; luôn có $x \ge 0$ , $y \ge 0$	nguyên liệu $\le 200$ kg
Hàm mục tiêu	đại lượng cần lớn nhất (lãi, doanh thu) hoặc nhỏ nhất (chi phí, thời gian): $F = ax + by$	lãi $40x + 30y$

Miền nghiệm của hệ ràng buộc gọi là miền các phương án khả thi: mỗi điểm là một cách làm hợp lệ. Phương án tối ưu là điểm của miền cho $F$ lớn nhất (hoặc nhỏ nhất). Theo bài 5, nó nằm ở đỉnh.

2. Cách đọc đề: bảng dữ kiện

Mỗi ràng buộc ứng với một tài nguyên (nguyên liệu, giờ máy, vốn, mặt bằng) hoặc một yêu cầu tối thiểu (protein, tổng số). Nên lập bảng: mỗi hàng một tài nguyên, mỗi cột một loại sản phẩm, cột cuối là giới hạn. Hệ số ở hàng $i$ chính là hệ số của bất phương trình thứ $i$ .

Tài nguyên	Sản phẩm A ( $x$ )	Sản phẩm B ( $y$ )	Giới hạn
Nguyên liệu (kg)	$2$	$4$	$\le 200$
Thời gian (giờ)	$30$	$15$	$\le 1\,200$
Lãi (nghìn đồng)	$40$	$30$	cần cực đại

Bảng dữ kiện của ví dụ 1: mỗi hàng của bảng cho một bất phương trình (hệ số ở các cột A, B, giới hạn ở cột cuối), riêng hàng lãi cho hàm mục tiêu; thêm hai điều kiện x ≥ 0, y ≥ 0.

3. Hai kiểu quen thuộc

Kiểu "lãi lớn nhất": tài nguyên hữu hạn, ràng buộc dạng $\le$ . Miền thường là đa giác bị chặn, có cả max và min (min thường tại $O$ , vô nghĩa). Quan tâm max.
Kiểu "chi phí nhỏ nhất": yêu cầu tối thiểu, ràng buộc dạng $\ge$ . Miền không bị chặn, hệ số chi phí dương nên có min, không có max. Quan tâm min.

Tương tácXưởng

P (10; 10)

(10 kg A, 10 kg B)

nguyên liệu:

60 \leq 200

thời gian máy:

450 \leq 1200

giờ

F = 40 x + 30 y = 700

nghìn đồng

lãi tối ưu: 2000 nghìn đồng

○ còn kém tối ưu 1300 nghìn đồng

Kéo điểm P để thử một phương án: thanh tài nguyên đầy dần, chạm vạch trần thì hết; vượt vạch là vi phạm. So lãi của bạn với lãi tối ưu, rồi bấm “Đặt P tại đỉnh tối ưu”. Đổi sang khẩu phần để thấy bài chi phí nhỏ nhất.

02Tóm tắt

Ba thành phần: ẩn, ràng buộc (kèm $x, y \ge 0$ ), hàm mục tiêu.
Lập bảng dữ kiện tài nguyên để đọc hệ số ràng buộc; rút gọn.
Lãi lớn nhất: ràng buộc $\le$ , miền bị chặn. Chi phí nhỏ nhất: ràng buộc $\ge$ , miền không bị chặn, hệ số dương nên có min.
Giải: miền, đỉnh, bảng $F$ , kết luận bằng lời đủ đơn vị.
Cạnh cùng giá trị tối ưu $\Rightarrow$ nhiều phương án tối ưu.

Tiếp theoPhương pháp →