HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ:

- GV yêu cầu HS hoàn thành HĐ 1.

+ GV có thể cho HS nhắc lại cách giải hệ bất phương trình bậc nhất hai ẩn đã học.

HS đặt ẩn, viết hàm mục tiêu, viết hệ bất phương trình các ràng buộc của bài toán, biểu diễn miền nghiệm, tính giá trị F tại các điểm cực biên, sử dụng kiến thức đã học về hệ bất phương trình bậc nhất hai ẩn.

- GV giới thiệu về bài toán quy hoạch tuyến tính.

- HS đọc, phát biểu lại bài toán quy hoạch tuyến tính hai biến, các khái niệm và thuật ngữ liên quan.

+ GV giới thiệu về cách viết ngắn gọn bài toán quy hoạch tuyến tính.

- HS đọc, tìm hiểu Ví dụ 1. HS nhận biết bài toán quy hoạch tuyến tính hai biến.

HS nêu lại các ràng buộc và cách biểu diễn miền nghiệm của hệ.

- HS quan sát Ví dụ 2. GV nhắc lại về cách viết ngắn gọn bài toán quy hoạch tuyến tính.

+ Nhận xét miền nghiệm hệ ở ví dụ 2? (miền nghiệm không là đa giác).

- GV giới thiệu về điểm cực biên, phương án cực biên.

- HS thực hiện Luyện tập 1.

+ Đặt ẩn: và lần lượt là số tấn nguyên liệu loại I và II. Từ dữ kiện về

+ Tìm các ràng buộc của .

+ Biểu diễn miền nghiệm: vẽ các đường thẳng, tìm điểm cực biên.

Bước 2: Thực hiện nhiệm vụ:

- HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, hoàn thành các yêu cầu, thảo luận nhóm.

- GV quan sát hỗ trợ.

Bước 3: Báo cáo, thảo luận:

- HS giơ tay phát biểu, lên bảng trình bày

- Một số HS khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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

HĐ 1:

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 OABC được tô màu trong hình vẽ dưới đây (Tính cả các cạnh của tứ giác). Với

d) Ta có:

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

Kết luận

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.

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.

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 (SGK -tr.25)

Ví dụ 2 (SGK -tr.25)

Chú ý:

• Trong Ví dụ 2, các điểm cũng được gọi là "đỉnh" của miền nghiệm S.

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

Luyện tập 1

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

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ:

- GV yêu cầu HS hoàn thành HĐ 2.

+ a) Điểm M phải thuộc đường thẳng nào? Điểm M thuộc miền nào trong hình vẽ?

Từ đó tìm tập hợp điểm M

+ b) Quan sát hình vẽ, tìm điều kiện bài toán.

+ c) Dựa vào điều kiện của m để tìm giá trị lớn nhất của F.

- GV dẫn dắt:

+ Với điều kiện của câu b thì đường thẳng chạy trên miền bị giới hạn bởi các đường thẳng nào? Đi qua những điểm cực biên của miền S không?

Từ đó dẫn dắt để thấy miền phương án chấp nhận được khác rỗng và là miền đa giác thì bài toá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.

- GV nhấn mạnh lại các bước giải bài toán quy hoạch tuyến tính.

- HS tìm hiểu Ví dụ 3. GV chỉ ra các bước chính được thực hiện.

- HS quan sát, tìm hiểu Ví dụ 4.

+ Tính giá trị F tại các điểm cực biên, ta thấy ,

+ Xét đường thẳng , đường thẳng này qua CD. Nên F bằng 180 tại mọi điểm thuộc đoạn CD. Vậy bài toán có vô số phương án tối ưu.

- HS làm Luyện tập 2, rồi kiểm tra chéo đáp án: Thực hành giải bài toán quy hoạch tuyến tính theo các bước.

Bước 2: Thực hiện nhiệm vụ:

- HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, suy nghĩ trả lời câu hỏi, hoàn thành các yêu cầu.

- GV: quan sát và trợ giúp HS.

Bước 3: Báo cáo, thảo luận:

- HS giơ tay phát biểu, lên bảng trình bày

- Một số HS khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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:

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 AB với

b)

Với // và luôn cắt trục tung tại điểm có tung độ

thì

Vậy

c) Ta có: , nên

Giá trị lớn nhất của trên miền S 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.

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

Ví dụ 3 (SGK -tr.27)

Ví dụ 4 (SGK -tr.28)

Luyện tập 2

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 x và y là:

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.