Giáo án điện tử chuyên đề Toán 12 kết nối Bài 3: 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

KHỞI ĐỘNG

Một xí nghiệp sản xuất hai loại sản phẩm I và II. Mỗi kilôgam sản phẩm loại I cần 2 kg nguyên liệu và 30 giờ làm, đem lại mức lợi nhuận 40 nghìn đồng. Mỗi kilôgam sản phẩm loại II cần 4 kg nguyên liệu và 15 giờ làm, đem lại mức lợi nhuận là 30 nghìn đồng. Xí nghiệp có 200 kg nguyên liệu và tối đa 1 200 giờ làm việc.

Hãy đặt kế hoạch sản xuất để xí nghiệp có mức lợi nhuận cao nhất.

CHUYÊN ĐỀ 2: ỨNG DỤNG TOÁN HỌC ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN TỐI ƯU

BÀI 3: 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 TÓA QUY HOẠCH TUYẾN TÍNH

NỘI DUNG BÀI HỌC

1. Giới thiệu bài toán quy hoạch tuyến tính hai biến

2. 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

3. 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

1. GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN

• HĐ1. Trong bài toán mở đầu, gọi và 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.

Giải:

a) Lợi nhuận đem lại từ kg sản phẩm loại I là nghìn đồng.

Lợi nhuận đem lại từ kg sản phẩm loại II là nghìn đồng.

Vậy lợi nhuận của xí nghiệp khi sản xuất kg sản phẩm loại I và kg sản phẩm loại II là:

b) Hệ bất phương trình:

c) Vẽ đường thẳng

Miền nghiệm của hệ bất phương trình trong ý b là miền tứ giác được tô màu trong hình vẽ bên (Tính cả các cạnh của tứ giác).

Với

Giải:

d) Ta có:

Dự đoán mức lợi nhuận cao nhất là 2 triệu đồng.

Giải:

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

ở đó 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 ở trên gọi là hàm mục tiêu.

Kết luận

Chú ý

a) Mỗi bất phương trình trong hệ (1) gọi là một ràng buộc. Nếu là một nghiệm của hệ (1) thì ta nói 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 đạt giá trị lớn nhất (tương ứng, giá trị nhỏ nhất) trên miền nghiệm tại thì cặp gọi là một phương án tối ưu của bài toán và giá trị gọi là giá trị tối ưu.

Chú ý

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

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

c) Trong hệ (1), một số ràng buộc có thể được viết dưới dạng

Ví dụ 1. 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ải:

a) triệu đồng.

b) Số tấn bột để sản xuất tấn thực phẩm X và tấn thực phẩm Y là .

Số tấn đường để sản xuất tấn thực phẩm X và tấn thực phẩm Y là .

Số tấn dầu thực vật để sản xuất tấn thực phẩm X và tấn thực phẩm Y là

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

Giải:

c) Tập các phương án chấp nhận được là miền ngũ giác tô màu trong Hình 2.1.

Ta có:

Ví dụ 2. Xét bài toán:

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

a) Biểu diễn tập nghiệm của hệ các ràng buộc trên mặt phẳng toạ độ.

b) Gọi là giao điểm của đường thẳng với đường thẳng và trục . Tính giá trị tại các điểm và .

Giải:

a) Tập nghiệm của hệ các ràng buộc là miền không bị chặn được tô màu như trong Hình 2.2.

b) Toạ độ giao điểm của hai đường thẳng và là

Toạ độ giao điểm của đường thẳng và trục là

Ta có:

Chú ý

• Trong Ví dụ 2, các điểm cũng được gọi là "đỉnh" của miền nghiệm .
• Nếu phương án chấp nhận được là một đỉnh của miền nghiệm thì được gọi là một điểm cực biên hoặc phương án cực biên.

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.

Luyện tập 1

Giải:

Gọi và lần lượt là số tấn nguyên liệu loại I và II.

Ta có hệ bất phương trình:

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

Chi phí mua nguyên liệu là

(triệu đồng).

2. 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

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

Miền chấp nhận được 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 thoả mãn

b) Với mỗi số thực xét đường thẳng . Từ hình vẽ, tìm điều kiện của để .

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

Giải:

a) Theo bài, , hay

Vẽ đường thẳng

Nếu xét thỏa mãn các ràng buộc bài toán thì: Tập hợp điểm thỏa mãn yêu cầu đề bài là đoạn thẳng với

b) Với // và luôn cắt trục

Vậy

c) Ta có:

nên

Giá trị lớn nhất của trên miền là

Vậy lợi nhuận cao nhất mà xí nghiệp đạt được là 2 000 nghìn đồng, tức 2 triệu đồng khi sản xuất 20 kg sản phẩm loại I và 40 kg sản phẩm loại II.

Giải:

• 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 . Người ta chứng minh được rằng:
• Nếu thì bài toán không có phương án tối ưu.
• Nếu 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.

Nhận xét

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

• Một người mỗi ngày cần từ 400 đến 1 000 đơn vị vitamin cả A lẫn B;
• Trong một ngày mỗi người có thể tiếp nhận không quá 600 đơn vị vitamin A và không quá 500 đơn vị vitamin B;
• 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 B không ít hơn một nửa số đơn vị vitamin A nhưng không nhiều hơn ba lần số đơn vị vitamin A.

Giải:

Bước 1. Gọi và 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à (đồng).

Bước 3. Hệ bất phương trình ràng buộc và là

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 trong Hình 2.4.

Giải:

Các điểm cực biên là:

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

Ta biết rằng đạ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 tại các đỉnh của lục giác ta được:

Giải:

Giá trị nhỏ nhất của bằng tại

Phương án tối ưu là

Vậy chi phí mua vitamin nhỏ nhất là đồng khi và .

Bây giờ ta sẽ xét một tình huống mà phương án tối ưu của bài toán đạt được tại vô số điểm trên miền chấp nhận được.

Ví dụ 4. 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 và 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à:

(triệu đồng).

Giải:

Bước 3. Hệ bất phương trình bậc nhất ràng buộc và là

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 trong Hình 2.5.

Các điểm cực biên là:

Giải:

Bước 5. Bài toán yêu cầu tìm giá trị lớn nhất của trên miền lục giác .

Ta biết rằng, đạ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 tại các đỉnh của đa giác ta được:

Chú ý rằng vì đường thẳng có phương trình , nên với mọi điểm thuộc đường thẳng ta đều có .

Vậy biểu thức đạt giá trị lớn nhất bằng tại mọi điểm thuộc đoạn thẳng

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 .

Từ đó suy ra, công ty cần sản xuất tấn sơn nội thất và tấn sơn ngoài trời với

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?

Luyện tập 2

Giải:

Gọi lần lượt là số xe loại A và loại B cần thuê.

Chi phí thuê xe là: (triệu đồng).

Hệ ràng buộc và là:

Giải:

Tập các phương án chấp nhận được là miền tứ giác với

Giá trị nhỏ nhất là

Vậy phải thuê 5 xe loại A và 4 xe loại B để chi phí bỏ ra là ít nhất (32 triệu đồng) mà vẫn chở được hết hàng và người.

3. 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

• HĐ3. Xét bài toán quy hoạch tuyến tính

a) Kiểm tra lại rằng miền 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 thoả mãn .

d) Từ phần c suy ra giá trị nhỏ nhất của 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 tại một điểm cực biên của miền chấp nhận được.

c) Với mỗi số thực , xét đường thẳng . Từ hình vẽ, tìm điều kiện của để .

Giải:

a) Biểu diễn miền nghiệm của các bất phương trình trong hệ ràng buộc ta thấy rằng miền tô màu trong Hình 2.6 là miền chấp nhận được của bài toán.

b) Vẽ đường thẳng

Vậy tập hợp điểm thỏa mãn yêu cầu đề bài là tập hợp các điểm nằm trên đoạn thẳng , với

Giải:

c) Ta có:  song song với

Vậy .

d) Ta có: ,

Theo b, nên .

Vậy giá trị nhỏ nhất của trên miền là .

Ta có các điểm cực biên của miền là:

Vậy giá trị nhỏ nhất của trên miền chính là giá trị của tại điểm cực biên có tọa độ của miền chấp nhận được.

Nhận xét

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 . 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 có và các ràng buộc bao gồm và miền chấp nhận được không là miền đa giác thì có giá trị nhỏ nhất mà không có giá trị lớn nhất.

Ví dụ 5. (Bài toán khẩu phần ăn) 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.

Giải:

Bước 1. Gọi và 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à (nghìn đồng).

Bước 3. Hệ bất phương trình ràng buộc và là

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 2.7.

Ở đây

Các điểm cực biên là

Giải:

Bước 5. Bài toán yêu cầu tìm giá trị nhỏ nhất của trên miền nghiệm của hệ bất phương trình trên.

Theo Nhận xét ở trên, có giá trị nhỏ nhất trên 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 tại các điểm cực biên ta được:

Vậy giá trị nhỏ nhất của trên miền là đạt được tại

Suy ra phương án tối ưu là và giá trị tối ưu là .

Vậy chuyên gia thực phẩm cần mua gam thực phẩm X và 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.

------------------------------

----------------- Còn tiếp ------------------