Bài 1. Bài toán quy hoạch tuyến tính

Bài 1. Bài toán quy hoạch tuyến tính - Toán 12 Chân trời sáng tạo

Bài toán quy hoạch tuyến tính (Linear Programming - LP) là một phương pháp toán học để tối ưu hóa một hàm mục tiêu tuyến tính, với các ràng buộc là các bất đẳng thức tuyến tính và phương trình tuyến tính. Đây là một công cụ quan trọng trong nhiều lĩnh vực như kinh tế, quản lý, kỹ thuật và khoa học.

1. Khái niệm cơ bản

Một bài toán quy hoạch tuyến tính thường bao gồm các thành phần sau:

• Hàm mục tiêu: Là hàm số tuyến tính cần tối ưu hóa (tối đa hoặc tối thiểu). Ví dụ: f(x, y) = 3x + 2y
• Biến quyết định: Là các biến số cần tìm giá trị để tối ưu hóa hàm mục tiêu. Ví dụ: x, y
• Ràng buộc: Là các bất đẳng thức hoặc phương trình tuyến tính giới hạn miền giá trị của các biến quyết định. Ví dụ: x ≥ 0, y ≥ 0, x + y ≤ 5

2. Các bước giải bài toán quy hoạch tuyến tính

1. Xây dựng mô hình toán học: Xác định hàm mục tiêu, biến quyết định và các ràng buộc.
2. Biểu diễn 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 ràng buộc và xác định miền nghiệm.
3. 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 ràng buộc.
4. Tính giá trị hàm mục tiêu tại các đỉnh: Thay giá trị tọa độ của các đỉnh vào hàm mục tiêu.
5. Chọn nghiệm tối ưu: Chọn đỉnh mà tại đó hàm mục tiêu đạt giá trị lớn nhất (nếu tối đa) hoặc nhỏ nhất (nếu tối thiểu).

3. Ví dụ minh họa

Xét bài toán sau:

Tối đa hóa hàm mục tiêu: f(x, y) = 3x + 2y

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

• x ≥ 0
• y ≥ 0
• x + y ≤ 5
• 2x + y ≤ 8

Giải:

1. Vẽ các đường thẳng tương ứng với các ràng buộc trên mặt phẳng tọa độ.

2. Xác định miền nghiệm là tứ giác có các đỉnh A(0, 0), B(4, 0), C(3, 2), D(0, 5).

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

• f(A) = f(0, 0) = 0
• f(B) = f(4, 0) = 12
• f(C) = f(3, 2) = 13
• f(D) = f(0, 5) = 10

4. Nghiệm tối ưu là C(3, 2) với giá trị hàm mục tiêu lớn nhất là 13.

4. Ứng dụng của bài toán quy hoạch tuyến tính

Bài toán quy hoạch tuyến tính có nhiều ứng dụng thực tế, ví dụ:

• Lập kế hoạch sản xuất: Xác định lượng sản phẩm cần sản xuất để tối đa hóa lợi nhuận.
• Quản lý kho hàng: Xác định lượng hàng tồn kho tối ưu để giảm thiểu chi phí.
• Vận tải: Xác định tuyến đường vận chuyển tối ưu để giảm thiểu chi phí.
• Phân bổ nguồn lực: Phân bổ nguồn lực hạn chế một cách hiệu quả nhất.

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

• Đảm bảo mô hình toán học được xây dựng chính xác và đầy đủ.
• Vẽ chính xác miền nghiệm để tránh sai sót.
• Kiểm tra lại kết quả để đảm bảo tính hợp lý.

Hy vọng bài học này đã cung cấp cho các em những kiến thức cơ bản và hữu ích về bài toán quy hoạch tuyến tính. Chúc các em học tập tốt!