Vận dụng Hệ bất phương trình bậc nhất hai ẩn để giải quyết một số bài toán quy hoạch tuyến tính


Vận dụng Hệ bất phương trình bậc nhất hai ẩn để giải quyết một số bài toán quy hoạch tuyến tính

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

Tìm giá trị lớn nhất (tương ứng, giá trị nhỏ nhất) của biểu thức $F(x;y)=Ax+By$ trên miền nghiệm $S$ của một hệ bất phương trình bậc nhất hai ẩn:

                                                                    \[S:\left\{ {\begin{array}{*{20}{c}} {{a_1}x + {b_1}y \leqslant {c_1}} \\ {{a_2}x + {b_2}y \leqslant {c_2}} \\ \cdots \\ {{a_n}x + {b_n}y \leqslant {c_n}} \end{array}} \right.\left( 1 \right)\]

ở đó $\text{A},\text{B}$ là hai số thực cho trước, không đồng thời bằng $0.$

Các bài toán như vậy gọi là bài toán quy hoạch tuyến tính hai biến. Biểu thức $F(x;y)$ ở trên gọi là hàm mục tiêu.

a) Mỗi bất phương trình trong hệ $\left( 1 \right)$ gọi là một ràng buộc. Nếu $\left( {{x}_{0}};{{y}_{0}} \right)$ là một nghiệm của hệ $\left( 1 \right)$ thì ta nói $\left( {{x}_{0}};{{y}_{0}} \right)$ là một phương án chấp nhận được hoặc phương án khả thi của bài toán. Tập các phương án chấp nhận được còn gọi là miền chấp nhận được. Nếu $F(x;y)$ đạt giá trị lớn nhất (tương ứng, giá trị nhỏ nhất) trên miền nghiệm $S$ tại $\left( {{x}_{0}};{{y}_{0}} \right)$ thì cặp $\left( {{x}_{0}};{{y}_{0}} \right)$ gọi là một phương án tối ưu của bài toán và giá trị $F\left( {{x}_{0}};{{y}_{0}} \right)$ gọi là giá trị tối ưu.

Nếu phương án chấp nhận được $\left( {{x}_{0}};{{y}_{0}} \right)$ là một đỉnh của miền nghiệm thì $\left( {{x}_{0}};{{y}_{0}} \right)$ gọi là một điểm cực biên hoặc phương án cực biên.

b) Bài toán quy hoạch tuyến tính trên được kí hiệu như sau:

                                                                  \[F(x;y)=Ax+By\to \max (\min )\]

với các ràng buộc

                                                                          \[\left\{ {\begin{array}{*{20}{c}} {{a_1}x + {b_1}y \leqslant {c_1}} \\ {{a_2}x + {b_2}y \leqslant {c_2}} \\ \cdots \\ {{a_n}x + {b_n}y \leqslant {c_n}} \end{array}} \right.\]

c) Trong hệ $\left( 1 \right),$ một số ràng buộc có thể được viết dưới dạng $ax+by\ge c.$

Bài toán quy hoạch tuyến tính với miền chấp nhận được là miền đa giác

Xét bài toán quy hoạch tuyến tính với tập các phương án chấp nhận được $S.$ Người ta chứng minh được rằng:

- Nếu $S=\varnothing$ thì bài toán không có phương án tối ưu.

- Nếu $S \neq \varnothing$ và là miền đa giác thì bài toán luôn có phương án tối ưu và phương án tối ưu là một trong các phương án cực biên.

Các bước giải bài toán quy hoạch tuyến tính với miền chấp nhận được là miền đa giác:

Bước 1. Đặt biến.

Bước 2. Xác định hàm mục tiêu.

Bước 3. Xác định hệ bất phương trình bậc nhát gồm tất cả các ràng buộc của bài toán.

Bước 4. Biểu diễn tập các phương án chấp nhận được. Tìm các phương án cực biên.

Bước 5. Tính giá trị của hàm mục tiêu tại các điểm cực biên, từ đó suy ra giá trị lớn nhất và giá trị nhỏ nhất của hàm mục tiểu rồi kết luận.

Ví dụ 1. Một nhà khoa học đã nghiên cứu về tác động phối hợp của hai loại vitamin $\text{A}$ và $\text{B}$ đối với cơ thể con người. Kết quả như sau:

i) Một người mỗi ngày cần từ 400 đến 1000 đơn vị vitamin cả $\text{A}$ lẫn $\text{B;}$

ii) Trong một ngày mỗi người có thể tiếp nhận không quá 600 đơn vị vitamin $\text{A}$ và không quá 500 đơn vị vitamin $\text{B;}$

iii) Do tác động phối hợp của hai loại vitamin trên, nên mỗi ngày, một người sử dụng số đơn vị vitamin $\text{B}$ không ít hơn một nửa số đơn vị vitamin $\text{A}$ nhưng không nhiều hơn ba lần số đơn vị vitamin $\text{A}.$

Biết rằng mỗi đơn vị vitamin $\text{A}$ có giá $90$ đồng và mỗi đơn vị vitamin $\text{B}$ có giá $75$ đồng. Tìm phương án dùng hai loại vitamin $\text{A}$ và $\text{B}$ thoả mãn các điều kiện ở trên sao cho chi phí rẻ nhất.

Giải. Bước 1. Gọi $x$ và $y$ lần lượt là số đơn vị vitamin $A$ và $B$ mà một người dùng mỗi ngày.

Bước 2. Chi phí mua vitamin là $F(x;y)=90x+75y$ đồng.

Bước 3. Hệ bất phương trình ràng buộc $x$ và $y$ là $\left\{ {\begin{array}{*{20}{l}} {0 \leqslant x \leqslant 600} \\ {0 \leqslant y \leqslant 500} \\ {400 \leqslant x + y \leqslant 1000} \\ {\dfrac{1}{2}x \leqslant y \leqslant 3x.} \end{array}} \right.$

Bước 4. Miền nghiệm của hệ bất phương trình này là miền lục giác $MNPQRS$ trong hình vẽ bên

Các điểm cực biên là \[M(100;300),N\left( \dfrac{500}{3};500 \right),P(500;500),Q(600;400),R(600;300),S\left( \dfrac{800}{3};\dfrac{400}{3} \right).\]

Bước 5. Bài toán yêu cầu tìm giá trị nhỏ nhất của $F(x;y)$ trên miền lục giác $MNPQRS.$

Ta biết rằng $F(x;y)$ đạt giá trị nhỏ nhất tại một trong các đỉnh của lục giác. Tính giá trị của $F(x;y)$ tại các đỉnh của lục giác ta được: \[F(100;300)=31500;F\left( \dfrac{500}{3};500 \right)=52500;F(500;500)=82500;\]

\[F(600;400)=84000;F(600;300)=76500;F\left( \dfrac{800}{3};\dfrac{400}{3} \right)=34000.\]

Giá trị nhỏ nhất của $F(x;y)$ bằng $31500$ tại $M(100;300).$ Phương án tối ưu là $(100;300).$ Vậy chi phí mua vitamin nhỏ nhất là $31500$ đồng khi $x=100$ và $y=300.$

Ví dụ 2. Một công ty sản xuất hai loại thực phẩm $X, Y.$ Nguyên liệu để sản xuất gồm ba loại là bột, đường và dầu thực vật, với lượng dự trữ tương ứng là $15$ tấn, $12$ tấn, $10$ tấn. Để sản xuất:

- $1$ tấn thực phẩm loại $X$ cần $0,5$ tấn bột, $0,5$ tấn đường, $0,2$ tấn dầu thực vật;

- $1$ tấn thực phẩm loại $Y$ cần $0,6$ tấn bột, $0,3$ tấn đường, $0,5$ tấn dầu thực vật.

Giá bán một tấn thực phẩm $X$ là $100$ triệu đồng, giá bán một tấn thực phẩm $Y$ là $112$ triệu đồng. Hỏi cần sản xuất mỗi loại thực phẩm bao nhiêu tấn để có doanh thu lớn nhất?

Giải. Gọi $x$ và $y$ lần lượt là số tấn thực phẩm $X$ và $Y$ cần sản xuất.

Số tiền bán thực phẩm thu được là $F(x ; y)=100 x+112 y$ triệu đồng.

Số tấn bột để sản xuất $x$ tấn thực phẩm $X$ và $y$ tấn thực phẩm $Y$ là $0,5 x+0,6 y.$

Số tấn đường để sản xuất $x$ tấn thực phẩm $X$ và $y$ tấn thực phẩm $Y$ là $0,5 x+0,3 y.$

Số tấn dầu thực vật để sản xuất $x$ tấn thực phẩm $X$ và $y$ tấn thực phẩm $Y$ là $0,2 x+0,5 y.$

Vì lượng nguyên liệu sử dụng không vượt quá lượng dự trữ nên ta có hệ:

\[\left\{ {\begin{array}{*{20}{l}} {0,5x + 0,6y \leqslant 15} \\ {0,5x + 0,3y \leqslant 12} \\ {0,2x + 0,5y \leqslant 10} \\ {x \geqslant 0,y \geqslant 0} \end{array}} \right.\]

Tập các phương án chấp nhận được là miền ngũ giác tô màu trong hình vẽ bên

Các đỉnh của miền nghiệm là \[O(0;0),A(0;20),B\left( \dfrac{150}{13};\dfrac{200}{13} \right),C(18;10),D(24;0)\text{. }\]

Ta có:$F(0;0)=100\cdot 0+112\cdot 0=0;F(0;20)=100\cdot 0+112\cdot 20=2240;$

$F\left( \dfrac{150}{13};\dfrac{200}{13} \right)=100\cdot \dfrac{150}{13}+112\cdot \dfrac{200}{13}=\dfrac{37400}{13};$

$F(18;10)=100\cdot 18+112\cdot 10=2920;F(24;0)=100\cdot 24+112\cdot 0=2400.$

Giá trị lớn nhất của $F(x;y)$ bằng $2920$ tại $C\left( 18;10 \right).$ Phương án tối ưu là $\left( 18;10 \right).$ Vậy doanh thu lớn nhất là $2920$ triệu đồng khi $x=18,\text{ }y=10.$

Ví dụ 3. Một công ty sơn sản xuất hai loại sơn là sơn nội thất và sơn ngoài trời. Nguyên liệu để sản xuất gồm hai loại $X$ và $Y$ với trữ lượng lần lượt là $6$ tấn và $8$ tấn. Để sản xuất một tấn sơn nội thất cần $2$ tấn nguyên liệu $X$ và $1$ tấn nguyên liệu $Y.$ Để sản xuất một tấn sơn ngoài trời cần $1$ tấn nguyên liệu $X$ và $2$ tấn nguyên liệu $Y.$ Qua nghiên cứu thị trường, công ty thấy rằng nhu cầu sơn nội thất không nhiều hơn sơn ngoài trời quá $1$ tấn và nhu cầu cực đại của sơn nội thất là $2$ tấn. Giá bán một tấn sơn nội thất là $60$ triệu đồng, một tấn sơn ngoài trời là $30$ triệu đồng. Công ty cần sản xuất mỗi loại sơn bao nhiêu tấn để doanh thu lớn nhất?

Giải. Bước 1. Gọi $x$ và $y$ lần lượt là số tấn sơn nội thất và sơn ngoài trời công ty cần sản xuất.

Bước 2. Doanh thu của công ty là $F(x ; y)=60 x+30 y$ (triệu đồng).

Bước 3. Hệ bất phương trình bậc nhất ràng buộc $x$ và $y$ là \[\left\{ {\begin{array}{*{20}{l}} {0 \leqslant x \leqslant 2} \\ {y \geqslant 0} \\ {2x + y \leqslant 6} \\ {x + 2y \leqslant 8} \\ {x \leqslant y + 1} \end{array}} \right.\]

Bước 4. Miền nghiệm của hệ bất phương trình này là miền lục giác $O A B C D E$ trong hình vẽ bên.

Các điểm cực biên là: $O(0 ; 0), A(1 ; 0), B(2 ; 1), C(2 ; 2), D\left(\dfrac{4}{3} ; \dfrac{10}{3}\right), E(0 ; 4).$

Bước 5. Bài toán yêu cầu tìm giá trị lớn nhất của $F(x ; y)$ trên miền lục giác $O A B C D E$.

Ta biết rằng, $F(x ; y)$ đạt giá trị lớn nhất tại một trong các đỉnh của lục giác. Tính giá trị của $F(x ; y)$ tại các đỉnh của đa giác ta được: $F(0 ; 0)=0 ; F(1 ; 0)=60 ; F(2 ; 1)=150 ; F(2 ; 2)=F\left(\dfrac{4}{3} ; \dfrac{10}{3}\right)=180 ; F(0 ; 4)=120.$

Chú ý rằng vì đường thẳng $C D$ có phương trình $2 x+y=6,$ nên với mọi điểm $M(x ; y)$ thuộc đường thẳng $C D$ ta đều có $F(x ; y)=60 x+30 y=30(2 x+y)=30 \cdot 6=180.$ Vậy biểu thức $F(x ; y)$ đạt giá trị lớn nhất bằng $180$ tại mọi điểm $M(x ; y)$ thuộc đoạn thẳng $C D.$ Như vậy bài toán có vô số phương án tối ưu, đó là toạ độ của tất cả các điểm thuộc đoạn thẳng $C D.$ Từ đó suy ra, công ty cần sản xuất $x$ tấn sơn nội thất và $y=6-2 x$ tấn sơn ngoài trời với $\dfrac{4}{3} \leq x \leq 2$ thì doanh thu lớn nhất.

Ví dụ 4. Để chế biến một hộp thực phẩm $A$ cần $0,2\text{ kg}$ cà chua và $0,1\text{ kg}$ thịt; một hộp thực phẩm $B$ cần $0,2\text{ kg}$ cà chua và $0,3\text{ kg}$ thịt. Lợi nhuận thu được từ $1$ hộp thực phẩm $A$ và $1$ hộp thực phẩm  lần lượt là $4000$ đồng và $5000$ đồng. Chị Hoa có $2\text{ kg}$ cà chua và $2\text{ kg}$ thịt để sản xuất các hộp thực phẩm $A$ và $B.$ Với lượng nguyên liệu như trên, lợi nhuận lớn nhất chị Hoa có thể thu được là bao nhiêu nghìn đồng?

Giải. Gọi $x,\text{ }y$lần lượt là số hộp thực phẩm $A,\text{ }B$ cần sản xuất.

Lợi nhuận thu được là $F\left( x;y \right)=4000x+5000y=1000\left( 4x+5y \right)$ đồng.

Ta có hệ điều kiện ràng buộc giữa $x,\text{ }y$ là $\left\{ \begin{array}{l}
x,y \ge 0\\
0,2x + 0,2y \le 2\\
0,1x + 0,3y \le 2
\end{array} \right..$

Miền nghiệm của hệ bất phương trình là miền tứ giác $OABC$ trên hình vẽ

Các điểm cực biên là $O\left( 0;0 \right),\text{ }A\left( 0;\dfrac{20}{3} \right),\text{ }B\left( 5;5 \right),\text{ }C\left( 10;0 \right).$

Ta có $F\left( 0;0 \right)=0,\text{ }F\left( 0;\dfrac{20}{3} \right)=\dfrac{100000}{3},\text{ }F\left( 5;5 \right)=45000,\text{ }F\left( 10;0 \right)=40000.$

Giá trị lớn nhất của $F(x;y)$ bằng $45000$ đồng tại $B\left( 5;5 \right).$ Phương án tối ưu là $\left( 5;5 \right).$ Vậy lợi nhuận lớn nhất chị Hoa có thể thu được là $45000$ đồng khi $x=y=5.$

Ví dụ 5. Một xưởng sản xuất bàn và ghế. Thời gian để một công nhân hoàn thiện $1$ chiếc bàn và $1$ chiếc ghế lần lượt là $120$ phút và $30$ phút. Xưởng có $4$ công nhân, mỗi công nhân làm việc không quá $6$ tiếng mỗi ngày. Biết rằng sản phẩm của xưởng luôn được tiêu thụ hết, mỗi chiếc bàn lãi $200$ nghìn đồng, mỗi chiếc ghế lãi $75$ nghìn đồng và số ghế không vượt quá $4$ lần số bàn. Trong một ngày sản xuất, xưởng có thể thu được lợi nhuận lớn nhất là bao nhiêu tiền? Viết câu trả lời theo đơn vị triệu đồng.

Giải. Gọi $x,\text{ }y$ lần lượt là số bàn và số ghế xưởng sản xuất trong một ngày.

Lợi nhuận trong một ngày của xưởng là $F\left( x;y \right)=0,2x+0,075y$ triệu đồng.

Ta có hệ điều kiện ràng buộc giữa $x,\text{ }y$ là $\left\{ \begin{array}{l}
x,{\rm{ }}y \ge 0\\
y \le 4x\\
2x + 0,5y \le 4 \times 6 = 24
\end{array} \right..$

Miền nghiệm của hệ là miền tam giác $OAB$ trên hình vẽ.

Các điểm cực biên là $O\left( 0;0 \right),\text{ }A\left( 6;24 \right),\text{ }B\left( 12;0 \right).$

Ta có $F\left( 0;0 \right)=0,\text{ }F\left( 6;24 \right)=3,\text{ }F\left( 12;0 \right)=2,4.$ Giá trị lớn nhất của $F(x;y)$ bằng $3$ triệu đồng tại $A\left( 6;24 \right).$ Phương án tối ưu là $\left( 6;24 \right).$ Vậy lợi nhuận lớn nhất của xưởng trong một ngày là chị Hoa có thể thu được là $3$ triệu đồng khi $x=6,\text{ }y=24.$

Ví dụ 6. Một cửa hàng chuyên về cà phê, có sẵn $75 \mathrm{~kg}$ cà phê Colombia nguyên chất và $120 \mathrm{~kg}$ cà phê thương hiệu của cửa hàng. Những thứ này sẽ được pha thành các gói cà phê $1 \mathrm{~kg}$ như sau: Một gói tiêu chuẩn có chứa $250 \mathrm{~g}$ cà phê Colombia nguyên chất và $750 \mathrm{~g}$ cà phê thương hiệu; một gói cao cấp chứa $500 \mathrm{~g}$ cà phê Colombia nguyên chất và $500 \mathrm{~g}$ cà phê thương hiệu.

a) Gọi $x$ là số gói cà phê tiêu chuẩn và $y$ là số gói cà phê cao cấp, hãy viết hệ bất phương trình bậc nhất mô tả số lượng gói có thể có của mỗi loại.

b) Biểu diễn hình học miền nghiệm của hệ bất phương trình bậc nhất nhận được ở câu a) và tìm các đỉnh của miền nghiệm.

c) Lợi nhuận của mỗi gói cà phê tiêu chuẩn là $30$ nghìn đồng và của mỗi gói cà phê cao cấp là $40$ nghìn đồng. Hỏi cần chuẩn bị bao nhiêu gói cà phê mỗi loại để lợi nhuận thu được là lớn nhất? Giả sử rằng tất cả các gói cà phê đã chuẩn bị đều có thể bán được.

Ví dụ 7. Một nhà máy sản xuất hai loại sản phẩm, mỗi sản phẩm yêu cầu sử dụng ba máy. Máy đầu tiên có thể được sử dụng nhiều nhất là $70$ giờ, máy thứ hai nhiều nhất là $40$ giờ và máy thứ ba nhiều nhất là $90$ giờ. Sản phẩm thứ nhất cần $2$ giờ trên máy $I,$ $1$ giờ trên máy $II$ và $1$ giờ trên máy $III;$ sản phẩm thứ hai cần $1$ giờ cho mỗi máy $I, II$ và $3$ giờ trên máy $III.$ Nếu lợi nhuận là $400$ nghìn đồng/đơn vị cho sản phẩm thứ nhất và $600$ nghìn đồng/đơn vị cho sản phẩm thứ hai, thì cần sản xuất bao nhiêu đơn vị mỗi sản phẩm để lợi nhuận thu được là lớn nhất?

Ví dụ 8. Một trung tâm tổ chức sự kiện có một phòng tổ chức lễ cưới với hai kiểu bàn ăn: bàn hình chữ nhật ngồi $6$ người với giá thuê $200$ nghìn đồng và bàn tròn ngồi $10$ người với giá thuê $300$ nghìn đồng. Anh Nam muốn thuê phòng để tổ chức đám cưới với $250$ khách mời. Căn phòng chỉ chứa được tối đa $35$ bàn các loại và chỉ có $15$ bàn hình chữ nhật. Hỏi anh Nam phải thuê mỗi loại bàn bao nhiêu để giảm thiểu tối đa chi phí mà vẫn đáp ứng được các yêu cầu trên?

Ví dụ 9. Một cơ sở sản xuất hai loại sữa chua $X$ và $Y.$ Nguyên liệu chính để sản xuất hai loại sữa chua này là dâu tây, sữa và đường. Để sản xuất một đơn vị sữa chua $X$ và một đơn vị sữa chua $Y$ cần lượng nguyên liệu như trong bảng:

Nguyên liệu Sữa chua X Sữa chua Y
Dâu tây 2 kg 3 kg
Sữa 2 kg 1 kg
Đường 0 kg 1 kg

Nguồn nguyên liệu dự trữ dâu tây, sữa và đường lần lượt là $1,2$ tấn; $0,8$ tấn và $0,3$ tấn. Giá bán mỗi đơn vị sữa chua $X$ và $Y$ lần lượt là $800$ nghìn đồng và $1,2$ triệu đồng. Cơ sở sản xuất cần sản xuất bao nhiêu đơn vị sữa chua $X$ và $Y$ để lợi nhuận thu được là lớn nhất?

Ví dụ 10. Một nhà máy hoá chất sản xuất hai hợp chất $X$ và $Y.$ Khi sản xuất một đơn vị hợp chất $X$ sẽ có $2 \mathrm{dm}^3$ khí $\mathrm{CO}$ (carbon monoxide) và $6 \mathrm{dm}^3$ khí $\mathrm{SO_2}$ (sulfur dioxide) phát tán ra môi trường. Khi sản xuất một đơn vị hợp chất $Y$ sẽ có $4 \mathrm{dm}^3$ khí $\mathrm{CO}$ và $3 \mathrm{dm}^3$ khi $\mathrm{SO}_2$ phát tán ra môi trường. Các yêu cầu về khí thải chỉ cho phép nhà máy phát thải ra môi trường mỗi tuần không quá $3000 \mathrm{dm}^3$ khí $\mathrm{CO}$ và không quá $5400 \mathrm{dm}^3$ khí $\mathrm{SO}_2.$ Nhà máy có thể bán hết tất cả các đơn vị hợp chất $X$ và $Y$ sản xuất ra với giá $36000$ đồng một đơn vị hợp chất $X$ và $24000$ đồng một đơn vị hợp chất $Y.$ Xác định số đơn vị hợp chất $X$ và $Y$ mỗi loại cần sản xuất trong một tuần để thu được lợi nhuận cao nhất mà vẫn đảm bảo các yêu cầu về khí thải môi trường.

Ví dụ 11. Chế độ ăn của một người yêu cầu mỗi ngày tối thiểu $400$ đơn vị vitamin, $500$ đơn vị khoáng chất và $1400$ đơn vị calo. Có hai loại thức ăn $F_1$ và $F_2;$ mỗi đơn vị $F_1$ giá $1200$ đồng và mỗi đơn vị $F_2$ giá $720$ đồng. Mỗi đơn vị thức ăn $F_1$ chứa $2$ đơn vị vitamin, $1$ đơn vị khoáng chất và $4$ đơn vị calo. Mỗi đơn vị thức ăn $F_2$ chứa $1$ đơn vị vitamin, $2$ đơn vị khoáng chất và $4$ đơn vị calo. Tìm chế độ ăn hỗn hợp $F_1$ và $F_2$ sao cho chi phí là ít nhất mà vẫn đảm bảo các yêu cầu về dinh dưỡng.

Ví dụ 12. Một hãng bán gà rán nghiên cứu thấy rằng để làm ra món gà rán có chất lượng tốt nhất thì thức ăn cho gà cần được bổ sung thêm $4$ loại vitamin $\mathrm{V} 1, \mathrm{~V} 2, \mathrm{~V} 3$ và $\mathrm{V} 4.$ Tổng lượng vitamin tối thiểu phải bổ sung cho mỗi $100 \mathrm{~g}$ thức ăn cho gà là: V1 cần 50 đơn vị, V2 cần 100 đơn vị, V3 cần 60 đơn vị và V4 cần 180 đơn vị. Có hai loại thức ăn $\mathrm{S} 1$ và $\mathrm{S} 2$ cung cấp 4 loại vitamin này. Loại $\mathrm{S} 1$ có giá 720 đồng một gam và mỗi gam $\mathrm{S} 1$ có chứa 5 đơn vị $\mathrm{V} 1,25$ đơn vị V2, 10 đơn vị $\mathrm{V} 3$ và 35 đơn vị V4. Loại $\mathrm{S} 2$ có giá 960 đồng một gam và mỗi gam $\mathrm{S} 2$ có chứa 25 đơn vị $\mathrm{V} 1,10$ đơn vị $\mathrm{V} 2,10$ đơn vị $\mathrm{V} 3$ và 20 đơn vị V4. Hỏi cần phải thêm vào 100 gam thức ăn cho gà mỗi loại $\mathrm{S} 1$ và $\mathrm{S} 2$ bao nhiêu gam để chi phí là thấp nhất mà vẫn đảm bảo dinh dưỡng cho gà?

Ví dụ 13. Một công ty cần thuê xe để chở $140$ người và $9$ tấn hàng. Nơi thuê xe có hai loại xe $A$ và $B,$ trong đó loại xe $A$ có $10$ chiếc và loại xe $B$ có $9$ chiếc. Một chiếc xe loại $A$ cho thuê với giá $4$ triệu đồng, một chié́c xe loại $B$ cho thuê với giá $3$ triệu đồng. Biết rằng mỗi xe loại $A$ có thể chở tối đa $20$ người và $0,6$ tấn hàng; mỗi xe loại $B$ có thể chở tối đa $10$ người và $1,5$ tấn hàng. Phải thuê bao nhiêu xe loại $A$ và bao nhiêu xe loại $B$ để chi phí bỏ ra là í nhất mà vẫn chở được hết hàng và người?

Ví dụ 14. Một công ty bán hàng toàn quốc đang lên kế hoạch tổ chức cuộc họp bán hàng tại Đà Nẵng. Giá vé máy bay khứ hồi thấp nhất từ Hà Nội đến Đà Nẵng là $2$ triệu đồng và giá vé khứ hồi thấp nhất từ Thành phố Hồ Chí Minh đến Đà Nẵng là $2,4$ triệu đồng. Có $28$ đại diện bán hàng ở Hà Nội và $22$ đại diện bán hàng ở Thành phố Hồ Chí Minh có thể đến Đà Nẵng dự cuộc họp này. Tổng cộng ít nhất $40$ đại diện bán hàng từ Hà Nội và Thành phố Hồ Chí Minh phải tham dự cuộc họp này với í nhất $12$ người từ Hà Nội và $16$ người từ Thành phố Hồ Chí Minh. Cần cử bao nhiêu đại diện bán hàng ở Hà Nội và bao nhiêu đại diện bán hàng ở Thành phố Hồ Chí Minh đến dự cuộc họp bán hàng ở Đà Nẵng để tổng chi phí vé máy bay là nhỏ nhất?

Bài toán quy hoạch tuyến tính với miền chấp nhận được không là miền đa giác

Xét bài toán quy hoạch tuyến tính với tập các phương án chấp nhận được $S$. Người ta chứng minh được rằng:
- Nếu bài toán có phương án tối ưu thì phương án tối ưu là một trong các phương án cực biên.
- Nếu hàm mục tiêu $F(x, y)=A x+B y$ có $A>0, B>0$ và các ràng buộc bao gồm $x \geq 0$, $y \geq 0$ và miền chấp nhận được không là miền đa giác thì $F(x ; y)$ có giá trị nhỏ nhất mà không có giá trị lớn nhất.

Ví dụ 1. Một chuyên gia dinh dưỡng dự định làm một thực đơn gồm hai loại thực phẩm chính $X$ và $Y.$ Biết rằng:

- Cứ $100$ gam thực phẩm $X$ chứa $2$ đơn vị chất béo, $1$ đơn vị carbohydrate và $4$ đơn vị protein.

- Cứ $100$ gam thực phẩm $Y$ chứa $3$ đơn vị chất béo, $3$ đơn vị carbohydrate và $3$ đơn vị protein.

Vị chuyên gia này muốn thức ăn phải cung cấp ít nhất $18$ đơn vị chất béo, $12$ đơn vị carbohydrate và $24$ đơn vị protein. Chuyên gia này phải làm thực đơn thế nào để chi phí mua nguyên liệu là rẻ nhất và vẫn đảm bảo các yêu cầu ở trên? Biết rằng $100$ gam thực phẩm $X$ có giá $20$ nghìn đồng và $100$ gam thực phẩm $Y$ có giá $25$ nghìn đồng.

Giải. Bước 1. Gọi $x$ và $y$ lần lượt là số trăm gam thực phẩm $X$ và $Y$ trong thực đơn.

Bước 2. Chi phí mua thực phẩm là $F(x ; y)=20 x+25 y$ (nghìn đồng).

Bước 3. Hệ bất phương trình ràng buộc $x$ và $y$ là \[\left\{ {\begin{array}{*{20}{l}} {x \geqslant 0,y \geqslant 0} \\ {2x + 3y \geqslant 18} \\ {x + 3y \geqslant 12} \\ {4x + 3y \geqslant 24} \end{array}} \right.\]

Bước 4. Miền nghiệm của hệ bất phương trình này là miền tô màu, không là miền đa giác, trong hình vẽ bên

Ở đây $d_1: 2 x+3 y=18 ; d_2: x+3 y=12 ; d_3: 4 x+3 y=24.$ Các điểm cực biên là $A(0 ; 8), B(3 ; 4), C(6 ; 2), D(12 ; 0).$

Bước 5. Bài toán yêu cầu tìm giá trị nhỏ nhất của $F(x ; y)$ trên miền nghiệm của hệ bất phương trình trên. Theo Nhận xét ở trên, $F(x ; y)$ có giá trị nhỏ nhất trên $S$ và đạt được tại một trong các điểm cực biên củ̉a miền chấp nhận được. Tính giá trị của $F(x ; y)$ tại các điểm cực biên ta được: $F(0 ; 8)=200 ; F(3 ; 4)=160 ; F(6 ; 2)=170 ; F(12 ; 0)=240.$

Vậy giá trị nhỏ nhất của $F(x ; y)$ trên miền $S$ là 160 đạt được tại $B(3 ; 4).$ Suy ra phương án tối ưu là $B(3 ; 4)$ và giá trị tối ưu là $160.$

Vậy chuyên gia thực phẩm cần mua $300$ gam thực phẩm $X$ và $400$ gam thực phẩm $Y$ thì chi phí mua thực phẩm sẽ ít nhất mà vẫn đảm bảo yêu cầu về dinh dưỡng.

Ví dụ 2. Một chủ trang trại cần sử dụng phân bón để chăm sóc cho một loại đậu tương. Loại đậu tương này cần ít nhất $18$ đơn vị đạm và ít nhất $6$ đơn vị phosphate. Ông chủ trang trại có thể sử dụng hai loại phân bón $X$ và $Y.$ Giá cả, hàm lượng đạm và hàm lượng phosphate có trong một tạ phân bón $X$ và một tạ phân bón $Y$ được cho bởi bảng sau:

Phân bón Số đơn vị đạm Số đơn vị phosphate Giá (triệu đồng)
$X$ $3$ $2$ $1,7$
$Y$ $6$ $1$ $1,2$

Hãy cho biết chủ trang trại cần phải mua bao nhiêu tạ phân bón $X,$ bao nhiêu tạ phân bón $Y$ để chi phí là thấp nhất mà vẫn đảm bảo chế độ dinh dưỡng cho loại đậu tương trên?

Giải. Gọi $x$ và $y$ lần lượt là số tạ phân phân bón $X$ và $Y$ cần phải mua.

Chi phí mua hai loại phân bón này là $F\left( x;y \right)=1,7x+1,2y$ (triệu đồng).

Hệ bất phương trình ràng buộc giữa $x$ và $y$ là $\left\{ \begin{gathered} x \geqslant 0,y \geqslant 0 \hfill \\ 3x + 6y \geqslant 18 \hfill \\ 2x + y \geqslant 6 \hfill \\ \end{gathered} \right..$

Miền nghiệm của hệ bất phương trình này là miền tô màu, không là miền đa giác, trong hình vẽ bên

Các điểm cực biên là $A\left( 0;6 \right),B\left( 2;2 \right),C\left( 6;0 \right).$ Và $F\left( 0;6 \right)=7,2;F\left( 2;2 \right)=5,8;F\left( 6;0 \right)=10,2.$

Vậy chủ trang trại cần mua $2$ tạ mỗi loại phân bón $X,\text{ }Y$ để chi phí mua thấp nhất là $5,8$ triệu đồng mà vẫn đảm bảo chế độ dinh dưỡng cho đậu tương.

Combo X Luyện thi 2025 Môn Toán (THPT, ĐG năng lực, ĐG tư duy) (2K7 – Chương trình SGK mới)

Link đăng ký: https://bit.ly/45sFkXS

PRO X: Luyện thi THPT 2025 Môn Toán (Luyện mọi dạng bài từ cơ bản đến 9 điểm)

XMAX: Luyện mọi dạng bài vận dụng cao Môn Toán 2025 (Mức 9+)

LIVE X: Tổng ôn kiến thức và chữa đề thi THPT 2025 Môn Toán (100 ngày)

Đăng ký cả Combo giảm trực tiếp 532.000 đồng học phí đến lúc thi chỉ còn: 2.268.000 đồng

Đăng ký cả Combo đối với học sinh đã tham gia các khoá PRO X11 giảm trực tiếp 800.000 đồng học phí đến lúc thi chỉ còn 2.000.000 đồng

Đăng ký cả Combo được tặng khoá học: XPLUS: LUYỆN GIẢI ĐỀ THI THPT 2024 MÔN TOÁN

Gồm khoảng 200 đề thi thử chọn lọc của các trường, sở giáo dục các năm gần đây và Bộ đề dự đoán do trực tiếp thầy Đặng Thành Nam biên soạn các năm 2024, 2023. Tất cả các đề đều có thi online tại Vted.vn và Lời giải chi tiết, một số đề gồm cả Video Live chữa đề.

Đăng ký cả Combo học sinh được tham gia nhóm LIVE: được học Livestream một số bài giảng chuyên đề của khoá PRO X, Vận dụng cao XMAX và Live Chữa đề ôn tập theo từng chủ đề, tổng kết chương và học kì. Thầy Nam bắt đầu Live vào đầu tháng 8, mỗi tuần hai buổi vào tối thứ 3 và thứ 5 hàng tuần.

Nhóm Live Combo X Luyện thi 2025 Môn Toán (2K7 - Chương trình SGK mới)

Khoá học PRO X và XMAX khai giảng từ ngày 20/06/2024 và Khoá học LIVE X khai giảng dự kiến 100 ngày trước thi hoặc sớm hơn vào tháng 12/2024.

Khoá học Biên soạn dựa trên:

Sách giáo khoa Toán 12 (tập 1, tập 2) (Kết Nối Tri Thức Với Cuộc Sống) - NXB GD Việt Nam

Sách giáo khoa Toán 12 (tập 1, tập 2) (Chân Trời Sáng Tạo) - NXB GD Việt Nam

Sách giáo khoa Toán 12 (tập 1, tập 2) (Cánh Diều) - NXB ĐH Sư Phạm

Các khoá học được sử dụng kể từ ngày đăng kí đến khi kì thi THPT 2025 kết thúc.

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Vted.

Đăng nhập
Vted
Xem tất cả