Giải bài toán quy hoạch tuyến tính:

\(F = 8x + 5y \to \max ,\min \)

với ràng buộc

\(\left\{ \begin{array}{l}2{\rm{x}} + y \le 8\\x \ge 0\\x \le 3\\y \ge 1\\y \le 5\end{array} \right.\)

Cho bài toán quy hoạch tuyến tính

\(F = 3x + 3y \to \max ,\min \)

có tập phương án \({\Omega }\) là miền tứ giác \(ABCD\) (được tô màu như Hình 5) với các đỉnh là \(A\left( {0;5} \right),\)\(B\left( {4;1} \right),C\left( {2;1} \right)\) và \(D\left( {0;2} \right)\).

a) Giải bài toán quy hoạch tuyến tính đã cho.

b) Hàm mục tiêu \(F\) đạt giá trị lớn nhất trên \({\Omega }\) tại bao nhiêu điểm? Giải thích.

Giải bài toán quy hoạch tuyến tính:

\(F = 25x + 10y \to \min \)

với ràng buộc

\(\left\{ \begin{array}{l}2{\rm{x}} - 3y \le 6\\x + y \ge 4\\x \ge 2\end{array} \right.\)

Giải bài toán quy hoạch tuyến tính:

\(F = 4x + 3y \to \max ,\min \)

với ràng buộc

\(\left\{ \begin{array}{l}x + 2y - 8 \le 0\\2x - y - 6 \le 0\\x \ge 0\\y \ge 1\end{array} \right.\)

Xét bài toán quy hoạch tuyến tính:

\(F = 2x + y \to \max ,\min \)

với ràng buộc

\(\left\{ \begin{array}{l}x + y - 4 \ge 0\\3x - y \ge 0\\x \ge 0\\y \ge 1\end{array} \right.\) (II)

Tập phương án \({\Omega }\) của bài toán là phần được tô màu trên Hình 3. Hai điểm \(A\left( {1;3} \right)\) và \(B\left( {3;1} \right)\) gọi là các đỉnh của \({\Omega }\).

Với giá trị \(F\) cho trước, xét đường thẳng \(d:2x + y = F\) hay \(d:y =  - 2x + F\).

Trả lời các câu hỏi sau để giải bài toán trên.

a) Tìm giá trị của \(F\) để đường thẳng \(d\) đi qua điểm \(A\left( {1;3} \right)\). Gọi giá trị tìm được là \({F_A}\).

b) Khi giá trị của \(F\) tăng (hoặc giảm) thì tung độ giao điểm của \(d\) với trục \(Oy\) thay đổi như thế nào? Khi đó, phương của đường thẳng \(d\) có thay đổi không?

c) Nếu \(F < {F_A}\) thì \(d\) và \({\Omega }\) có điểm chung không? Từ đó, chỉ ra giá trị nhỏ nhất của hàm mục tiêu \(F = 2x + y\) trên \({\Omega }\).

d) Với giá trị nào của \(F\) thì \(d\) và \({\Omega }\) có điểm chung? Hàm mục tiêu \(F = 2x + y\) giá trị lớn nhất trên \({\Omega }\) hay không?

Xét bài toán: Tìm giá trị lớn nhất và giá trị nhỏ nhất của biểu thức \(F = x + 2y\) với \(\left( {x;y} \right)\) là nghiệm của hệ bất phương trình

\(\left\{ \begin{array}{l}x - 2y + 4 \ge 0\\x + y - 5 \le 0\\x \ge 0\\y \ge 0\end{array} \right.\) (I)

Miền nghiệm \({\Omega }\) của hệ (I) là miền tứ giác \(OABC\) (được tô màu) trên Hình 1. Với giá trị \(F\) cho trước, xét đường thẳng \(d:x + 2y - F = 0\) hay \(y =  - \frac{x}{2} + \frac{F}{2}\).

Trả lời các câu hỏi sau để giải bài toán trên.

a) Với giá trị nào của \(F\) thì đường thẳng \(d\) đi qua điểm \(O\), điểm \(B\)?

b) Khi giá trị của \(F\) tăng (hoặc giảm) thì tung độ giao điểm của \(d\) với trục \(Oy\) thay đổi như thế nào? Khi đó, phương của đường thẳng \(d\) có thay đổi không?

c) Với điều kiện nào của \(F\) thì đường thẳng \(d\) và miền nghiệm \({\Omega }\) có điểm chung?

d) Từ đó, chỉ ra giá trị lớn nhất và giá trị nhỏ nhất của biểu thức \(F = x + 2y\) trên miền nghiệm \({\Omega }\). Biểu thức \(F\) đạt được các giá trị đó tại điểm nào?

Trong 100 g thịt bò loại I có chứa 21 g protein và 3,5 g lipid; 100 g thịt bò loại II có chứa 18 g protein và 10,5 g lipid. Biết rằng thịt bò loại I có giá 220 nghìn đồng/kg thì thịt bò loại II có giá 210 nghìn đồng/kg. Để có lượng thực phẩm từ hai loại thịt bò trên cung cấp ít nhất 630 g protein và 210 g lipid, cần mua khối lượng bao nhiêu cho mỗi loại thịt bò loại I và II sao cho chi phí thấp nhất?

Một dây chuyền của nhà máy sản xuất đá xây dựng dự định sản xuất hai loại sản phẩm A và B. Thời gian để dây chuyền sản xuất 100 tấn sản phẩm loại A và 100 tấn sản phẩm loại B lần lượt là 2 giờ và 3 giờ. Do nhu cầu thị trường, xí nghiệp sản xuất sản lượng sản phẩm loại A không ít hơn 3 lần sản lượng sản phẩm loại B. Sản phẩm loại A cho lợi nhuận là 5 triệu đồng/100 tấn; sản phẩm loại B cho lợi nhuận 9 triệu đồng/100 tấn.

Trong thời gian không quá 6 giờ làm việc của dây chuyền, cần sản xuất bao nhiêu tấn sản phẩm loại A, bao nhiêu tấn sản phẩm loại B để thu được lợi nhuận cao nhất?

Xét tình huống thương nhân thu mua trái cây ở Bài toán mở đầu (trang 6).

a) Nếu gọi \(x,y\) (tính theo tấn) lần lượt là khối lượng trái cây loại A và B được thương nhân thu mua thì \(x\) và \(y\) phải thoả mãn hệ bất phương trình bậc nhất hai ẩn nào?

b) Từ đó, phát biểu bài toán quy hoạch tuyến tính tìm khối lượng thu mua mỗi loại trái cây để thu được lợi nhuận cao nhất. Giải bài toán đó.

Giải bài toán quy hoạch tuyến tính:

\(F = 10x + 20y \to \min \)

với ràng buộc

\(\left\{ \begin{array}{l}20{\rm{x}} + 5y \ge 40\\16{\rm{x}} + 60y \ge 120\\x - y \le 3\\x \ge 0\\y \ge 0\end{array} \right.\)

Một cơ sở đóng thuyền thủ công cần 10 giờ lao động để đóng một thuyền loại A và 15 giờ lao động để đóng một thuyền loại B. Mỗi tuần cơ sở bố trí được tối đa 120 giờ lao động cho việc đóng hai loại thuyền này. Qua thực tế, người ta thấy mỗi tuần cơ sở bán được tối đa 6 thuyền loại A và tối thiểu 2 thuyền loại B. Mỗi thuyền loại A, loại B cho lợi nhuận lần lượt là 0,5 triệu đồng và 0,7 triệu đồng. Mỗi tuần cơ sở nên đóng bao nhiêu thuyền mỗi loại để có thể thu được lợi nhuận cao nhất?

Để làm một chiếc bánh bao loại X cần 100 g bột mì và 60 g thịt nạc vai. Để làm một chiếc bánh bao loại Y cần 150 g bột mì và 30 g thịt nạc vai. Có thể làm được nhiều nhất bao nhiêu chiếc bánh bao từ 3 kg bột mì và 1,2 kg thịt nạc vai có sẵn? Biết rằng không thiếu các nguyên liệu khác để làm bánh.

Hàm lượng các vi chất (chất vi lượng) calcium, phosphorus và iron chứa trong 100 g hai loại thực phẩm X và Y được cho ở bảng sau:

Từ hai loại thực phẩm X và Y, người ta muốn tạo ra một lượng thực phẩm hỗn hợp chứa ít nhất 2000 mg calcium, 3000 mg phosphorus, 48 mg iron. Cần chọn bao nhiêu gam mỗi loại thực phẩm X và Y sao cho lượng thực phẩm hỗn hợp có khối lượng nhỏ nhất?

Giá trị lớn nhất của biểu thức \(F\left( {x;y} \right) = 5x - 2y\) trên miền \({\Omega }\) ở Hình 1 là

A. 3.

B. 22.

C. 18.

D. 20.

Giá trị nhỏ nhất của biểu thức \(F\left( {x;y} \right) = 5x + 2y\) trên miền \({\Omega }\) ở Hình 2 là

A. 11.

B. 17.

C. 7.

D. 20.

Một nhà phân phối có thể thuê tối đa 3 chiếc xe tải loại A và 8 chiếc xe tải loại B để vận chuyển 100 chiếc máy giặt từ nhà máy sản xuất đến nơi tiêu thụ. Mỗi xe loại A chở được tối đa 20 máy giặt với giá cước 3 triệu đồng mỗi chuyến, mỗi xe loại B chở được tối đa 10 máy giặt với giá cước 2 triệu đồng mỗi chuyến. Nếu mỗi xe chỉ chở nhiều nhất một chuyến, số tiền cước tối thiểu (triệu đồng) mà nhà phân phối phải trả là

A. 19.

B. 17.

C. 15.

D. 25.

Giải bài toán quy hoạch tuyến tính:

\(F = 40x + 15y \to \max ,\min \)

với ràng buộc

\(\left\{ \begin{array}{l}5{\rm{x}} + 3y \le 15\\x + 3 \le 3y\\x \ge 0\end{array} \right.\)

Giải bài toán quy hoạch tuyến tính:

\(F = 3x + 5y \to \min \)

với ràng buộc

\(\left\{ \begin{array}{l}2{\rm{x}} - y + 4 \ge 0\\4{\rm{x}} + 3y \ge 12\\2{\rm{x}} - 3y \le 6\end{array} \right.\)

Thức ăn chăn nuôi A gồm 60% bột ngô và 40% bột đậu nành, thức ăn chăn nuôi B gồm 80% bột ngô và 20% bột đậu nành. Hiện tại xí nghiệp sản xuất chỉ còn 2,4 tấn bột ngô và 1,2 tấn bột đậu nành. Với số nguyên liệu này, xí nghiệp đó nên sản xuất khối lượng bao nhiêu mỗi loại sản phẩm A và B để thu được lợi nhuận cao nhất? Biết rằng A cho lợi nhuận 2 triệu đồng/tấn và B cho lợi nhuận 1,8 triệu đồng/tấn.

Hàm lượng protein, lipid và glucid (tính theo gam) trong 100 g mỗi loại thực phẩm A và B được cho bởi bảng sau:

Từ hai loại thực phẩm A và B, người ta muốn tạo ra một lượng thực phẩm chứa ít nhất 480 g protein, 90 g lipid và 2400 g glucid. Biết rằng một kilôgam mỗi loại thực phẩm A và B có giá lần lượt là 80 nghìn đồng, 100 nghìn đồng. Cần chọn bao nhiêu kilôgam mỗi loại thực phẩm A và B để chi phí thấp nhất?

Người ta dự định dùng hai loại nguyên liệu để chiết xuất ít nhất 140 kg chất X và 9 kg chất Y. Từ mỗi tấn nguyên liệu loại I giá 4 triệu đồng có thể chiết xuất được 20 kg chất X và 0,6 kg chất Y. Từ mỗi tấn nguyên liệu loại II giá 3 triệu đồng, có thể chiết xuất được 10 kg chất X và 1,5 kg chất Y. Cơ sở cung cấp nguyên liệu chỉ có thể cung cấp không quá 10 tấn nguyên liệu loại I và không quá 9 tấn nguyên liệu loại II.

Phải dùng bao nhiêu tấn nguyên liệu mỗi loại để chi phí mua nguyên liệu là ít nhất mà vẫn đáp ứng được các yêu cầu đặt ra ở trên?

a) Đặt ẩn và viết bài toán quy hoạch tuyến tính diễn tả yêu cầu của bài toán trên.

b) Biểu diễn tập các phương án chấp nhận được và tìm các phương án cực biên.

Trong bài toán mở đầu, gọi x và y lần lượt là số kilôgam sản phẩm loại I và loại II cần sản xuất.

a) Kí hiệu F(x; y) là lợi nhuận của xí nghiệp khi sản xuất x kg sản phẩm loại I và y kg sản phẩm loại II. Viết biểu thức tính F(x; y) theo x và y.

b) Lập hệ bất phương trình bậc nhất hai ẩn ràng buộc x và y thỏa mãn yêu cầu của bài toán.

c) Biểu diễn trên mặt phẳng toạ độ để thấy rằng miền nghiệm của hệ bất phương trình tìm được trong ý b là một miền tứ giác. Tìm toạ độ các đỉnh của miền tứ giác này.

d) Tính giá trị của F(x; y) tại các đỉnh của miền tứ giác tìm được trong ý b, từ đó dự đoán về mức lợi nhuận cao nhất.

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à ít nhất mà vẫn chở được hết hàng và người?

Ta giải bài toán Tình huống mở đầu.

Từ HĐ1 ta có bài toán quy hoạch tuyến tính sau:

F(x; y) = 40x + 30y → max

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

\(\left\{ \begin{array}{l}x + 2y \le 100\\2x + y \le 80\\x \ge 0,y \ge 0\end{array} \right.\)

Miền chấp nhận được S của bài toán là miền tứ giác tô màu trong Hình 2.3.

a) Tìm tập hợp các điểm M(x; y) thỏa mãn F(x; y) = 40x + 30y = 1 200.

b) Với mỗi số thực m xét đường thẳng d_m­: 40x + 30y = m.

Từ hình vẽ, tìm điều kiện của m để d_m ∩ S ≠ ∅.

c) Từ câu b suy ra giá trị lớn nhất của F(x; y) trên miền S, từ đó suy ra lời giải của bài toán.

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 X và một tạ phân Y được cho bởi bảng sau:

Hãy cho biết cần phải mua bao nhiêu tạ phân loại X, bao nhiêu tạ phân loại 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 bài toán quy hoạch tuyến tính sau:

F(x; y) = x + 2y → min

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

\(\left\{ \begin{array}{l}x \ge 0,y \ge 0\\x + y \ge 1\\2{\rm{x}} + 4y \ge 3\end{array} \right.\)

Xét bài toán quy hoạch tuyến tính

F(x; y) = 3x + 4y → min

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

\(\left\{ \begin{array}{l}x \ge 0,y \ge 0\\x + 2y \ge 4\\x + y \ge 3\end{array} \right.\)

a) Kiểm tra lại rằng miền S tô màu trong Hình 2.6 là miền chấp nhận được của bài toán.

b) Tìm tập hợp các điểm M(x; y) thoả mãn

F(x; y) = 3x + 4y = 12.

c) Với mỗi số thực m, xét đường thẳng

d_m: 3x + 4y = m.

Từ hình vẽ, tìm điều kiện của m để d_m ∩ S ≠ ∅.

d) Từ phần c suy ra giá trị nhỏ nhất của F(x; y) trên miền chấp nhận được. Chứng tỏ rằng, giá trị nhỏ nhất này chính là giá trị của F(x; y) tại một điểm cực biên của miền chấp nhận được.

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.

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 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:

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?

Một nhà máy hóa 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 dm³ khí CO (carbon monoxide) và 6 dm³ khí SO₂ (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 dm³ khí CO và 3 dm³ khí SO₂ 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á 3 000 dm³ khí CO và không quá 5 400 dm³ khí SO₂. 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á 36 000 đồng một đơn vị hợp chất X và 24 000 đồ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.

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à 1 400 đơn vị calo. Có hai loại thức ăn F₁ và F₂ mỗi đơn vị F₁ giá 1 200 đồng và mỗi đơn vị F₂ giá 720 đồng. Mỗi đơn vị thức ăn F₁ 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₂ chứa 1 đơn vị vitamin, 2 đơn vị khoáng chất và 4 đơn vị calo. Tìm chế độ hỗn hợp F₁ và F₂ sao cho chi phí là ít nhất mà vẫn đảm bảo các yêu cầu về dinh dưỡng.