Tối ưu tuyến tính trên miền đa giác

Khám phá: Chọn cách dùng nguồn lực

Một quầy hội chợ làm hai loại phần ăn. Gọi $x$ và $y$ lần lượt là số mẻ của mỗi loại. Quầy có giới hạn về thời gian chuẩn bị và số lượt đóng gói, nên không phải cặp $(x;y)$ nào cũng thực hiện được. Nếu mỗi mẻ loại thứ nhất thu được $3$ điểm doanh thu, mỗi mẻ loại thứ hai thu được $2$ điểm, làm sao chọn kế hoạch để doanh thu lớn nhất?

Ta sẽ biểu diễn các kế hoạch làm được thành một miền trên mặt phẳng, tìm các đỉnh của miền ấy, rồi so sánh doanh thu tại các đỉnh.

Kiến thức trọng tâm

Quan sát miền đa giác và các đỉnh $O$, $A$, $B$, $C$; đọc giá trị biểu thức tại từng đỉnh để nhận ra điểm cho doanh thu lớn nhất.

Ví dụ có lời giải

Ví dụ 1. Tìm doanh thu lớn nhất

Hai loại phần ăn phải thỏa mãn các giới hạn:

$$x\ge 0,\qquad y\ge 0,\qquad x+y\le 6,\qquad 2x+y\le 8.$$

Doanh thu được tính bằng $F(x,y)=3x+2y$. Tìm doanh thu lớn nhất.

1. Tìm các đỉnh miền nghiệm. Trên trục hoành, $y=0$, nên $x\le 6$ và $2x\le 8$; đỉnh xa nhất trên trục này là $(4;0)$. Trên trục tung, $x=0$, nên $y\le 6$; đỉnh xa nhất trên trục này là $(0;6)$. Giao của hai đường biên $x+y=6$ và $2x+y=8$ thỏa mãn $x=2$, $y=4$, nên có đỉnh $(2;4)$. Cùng với gốc tọa độ, các đỉnh là $(0;0)$, $(4;0)$, $(2;4)$, $(0;6)$.

2. Tính doanh thu tại các đỉnh. Lần lượt nhận được $F(0,0)=0$, $F(4,0)=12$, $F(2,4)=14$, $F(0,6)=12$.

3. Kết luận. Doanh thu lớn nhất là $14$ điểm, đạt được khi làm $2$ mẻ loại thứ nhất và $4$ mẻ loại thứ hai.

Ví dụ 2. Tìm chi phí nhỏ nhất

Một nhóm cần làm ít nhất $4$ mẻ và không quá $6$ mẻ tổng cộng. Gọi $x,y$ là số mẻ của hai loại, với $x\ge 0$, $y\ge 0$. Chi phí tính theo biểu thức $C(x,y)=2x+3y$. Tìm chi phí nhỏ nhất.

1. Miền nghiệm thỏa mãn $4\le x+y\le 6$, cùng với $x\ge 0$, $y\ge 0$. Các đỉnh là $(0;4)$, $(0;6)$, $(6;0)$, $(4;0)$.

2. Tính chi phí tại các đỉnh: $C(0,4)=12$, $C(0,6)=18$, $C(6,0)=12$, $C(4,0)=8$.

3. Vậy chi phí nhỏ nhất là $8$, đạt tại $(4;0)$.

Ví dụ 3. Khi có nhiều phương án tối ưu

Xét miền nghiệm ở Ví dụ 2 và biểu thức $H(x,y)=x+y$. Vì các điểm trong miền có $4\le x+y\le 6$, giá trị lớn nhất của $H$ là $6$. Giá trị này đạt tại hai đỉnh $(0;6)$, $(6;0)$ và tại mọi điểm trên cạnh nối hai đỉnh ấy.

Lỗi hay gặp và mẹo nhớ

• Lỗi: Tính giá trị biểu thức tại một vài điểm nhìn thấy trên hình rồi kết luận. Mẹo: Liệt kê đủ tất cả các đỉnh trước khi so sánh.

• Lỗi: Lấy giao điểm của hai đường biên nhưng quên kiểm tra điểm có thuộc miền nghiệm không. Mẹo: Thay tọa độ giao điểm vào các bất phương trình của hệ.

• Lỗi: Cho rằng chỉ có một phương án tối ưu. Mẹo: Nếu nhiều đỉnh cho cùng giá trị, hãy kiểm tra xem biểu thức có không đổi trên cạnh nối các đỉnh đó không.

Tự kiểm tra nhanh

1. Giao điểm của hai đường thẳng $x+y=5$ và $2x+y=8$ có tọa độ là bao nhiêu?

2. Với các đỉnh $(0;0)$, $(4;0)$, $(2;4)$, $(0;6)$, tìm giá trị lớn nhất của $G(x,y)=x+2y$ tại các đỉnh.

3. Nếu hai đỉnh của miền nghiệm cùng cho giá trị lớn nhất, cần kiểm tra thêm điều gì để biết có cả một cạnh gồm các phương án tối ưu?