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

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 - Giải chi tiết

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

Bài toán quy hoạch tuyến tính (Linear Programming - LP) là một bài toán tối ưu hóa, trong đó hàm mục tiêu và các ràng buộc đều là các hàm tuyến tính. Mục tiêu của bài toán là tìm ra giá trị của các biến số sao cho hàm mục tiêu đạt giá trị lớn nhất hoặc nhỏ nhất, đồng thời thỏa mãn tất cả các ràng buộc đã cho.

2. Các bước giải bài toán quy hoạch tuyến tính bằng phương pháp đồ thị

1. Xây dựng mô hình toán học: Xác định các biến số quyết định, hàm mục tiêu và các ràng buộc.
2. Biểu diễn các ràng buộc trên mặt phẳng tọa độ: Vẽ các đường thẳng tương ứng với các bất phương trình ràng buộc.
3. Xác định miền nghiệm: Miền nghiệm là tập hợp tất cả các điểm thỏa mãn tất cả các ràng buộc.
4. Tìm các đỉnh của miền nghiệm: Các đỉnh là giao điểm của các đường thẳng biên của miền nghiệm.
5. Tính giá trị hàm mục tiêu tại các đỉnh: Thay tọa độ của các đỉnh vào hàm mục tiêu để tìm ra giá trị lớn nhất hoặc nhỏ nhất.
6. Kết luận: Chọn đỉnh mà tại đó hàm mục tiêu đạt giá trị tối ưu.

3. Ví dụ minh họa

Bài toán: Một xí nghiệp sản xuất hai loại sản phẩm A và B. Để sản xuất một đơn vị sản phẩm A cần 2 kg nguyên liệu và 1 giờ công. Để sản xuất một đơn vị sản phẩm B cần 1 kg nguyên liệu và 2 giờ công. Xí nghiệp có 400 kg nguyên liệu và 300 giờ công. Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm A và B để thu được lợi nhuận tối đa, biết rằng lợi nhuận từ mỗi đơn vị sản phẩm A là 30 nghìn đồng và từ mỗi đơn vị sản phẩm B là 40 nghìn đồng?

Giải:

• Đặt biến: Gọi x là số đơn vị sản phẩm A cần sản xuất, y là số đơn vị sản phẩm B cần sản xuất.
• Hàm mục tiêu: Lợi nhuận Z = 30x + 40y (đơn vị: nghìn đồng).
• Ràng buộc:
• 2x + y ≤ 400 (nguyên liệu)
• x + 2y ≤ 300 (công)
• x ≥ 0, y ≥ 0 (điều kiện tự nhiên)

Biểu diễn trên mặt phẳng tọa độ:

Vẽ các đường thẳng 2x + y = 400, x + 2y = 300, x = 0, y = 0. Xác định miền nghiệm là tứ giác OABC với các đỉnh O(0,0), A(200,0), B(0,150), C là giao điểm của 2x + y = 400 và x + 2y = 300. Giải hệ phương trình này ta được C(100, 200).

Tính giá trị hàm mục tiêu tại các đỉnh:

• Z(0,0) = 0
• Z(200,0) = 30 * 200 + 40 * 0 = 6000
• Z(0,150) = 30 * 0 + 40 * 150 = 6000
• Z(100,200) = 30 * 100 + 40 * 200 = 11000

Kết luận: Xí nghiệp nên sản xuất 100 đơn vị sản phẩm A và 200 đơn vị sản phẩm B để thu được lợi nhuận tối đa là 11000 nghìn đồng.

4. Lưu ý khi giải bài toán quy hoạch tuyến tính

• Luôn kiểm tra kỹ các ràng buộc và đảm bảo rằng chúng là các bất phương trình tuyến tính.
• Vẽ chính xác các đường thẳng trên mặt phẳng tọa độ để xác định đúng miền nghiệm.
• Tính toán cẩn thận giá trị hàm mục tiêu tại các đỉnh của miền nghiệm.

5. Bài tập vận dụng

Các em hãy tự giải các bài tập tương tự để rèn luyện kỹ năng giải bài toán quy hoạch tuyến tính. Chúc các em học tốt!