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 - Chuyên đề Toán 12 Chân trời sáng tạo

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à các điều kiện không âm. Đâ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. Định nghĩa bài toán quy hoạch tuyến tính

Một bài toán quy hoạch tuyến tính (BQTHT) có dạng tổng quát như sau:

Hàm mục tiêu: Max/Min Z = c₁x₁ + c₂x₂ + ... + c_nx_n

Ràng buộc:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂
...
a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m
x₁, x₂, ..., x_n ≥ 0

Trong đó:

Z là hàm mục tiêu cần tối ưu hóa (max hoặc min).
x₁, x₂, ..., x_n là các biến quyết định.
c₁, c₂, ..., c_n là các hệ số của hàm mục tiêu.
a_ij là các hệ số của các ràng buộc.
b_i là các giá trị của các ràng buộc.

2. Các thành phần của bài toán quy hoạch tuyến tính

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

Biến quyết định: Các biến cần tìm giá trị để tối ưu hóa hàm mục tiêu.
Hàm mục tiêu: Hàm cần tối ưu hóa (max hoặc min).
Ràng buộc: Các điều kiện giới hạn giá trị của các biến quyết định.
Miền khả thi: Tập hợp tất cả các giá trị của các biến quyết định thỏa mãn các ràng buộc.

3. Phương pháp giải bài toán quy hoạch tuyến tính

Có nhiều phương pháp để giải bài toán quy hoạch tuyến tính, trong đó phổ biến nhất là:

Phương pháp đồ thị: Áp dụng cho bài toán có hai biến quyết định.
Phương pháp Simplex: Áp dụng cho bài toán có nhiều biến quyết định.

4. Ví dụ minh họa

Xét bài toán sau:

Max Z = 3x₁ + 2x₂

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

x₁ + x₂ ≤ 4
2x₁ + x₂ ≤ 5
x₁, x₂ ≥ 0

Sử dụng phương pháp đồ thị, ta có thể tìm ra nghiệm tối ưu là x₁ = 1.5, x₂ = 2.5, với giá trị hàm mục tiêu Z = 9.

5. Ứng dụng của quy hoạch tuyến tính

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 một cách hiệu quả để đạt được mục tiêu tối ưu.

6. Bài tập luyện tập

Để củng cố kiến thức, bạn hãy giải các bài tập sau:

Giải bài toán quy hoạch tuyến tính sau: Max Z = 2x₁ + 3x₂ với các ràng buộc: x₁ + x₂ ≤ 5, x₁ ≥ 0, x₂ ≥ 0.
Một công ty sản xuất hai loại sản phẩm A và B. Mỗi sản phẩm A cần 2 giờ máy và 1 giờ nhân công, mỗi sản phẩm B cần 1 giờ máy và 2 giờ nhân công. Công ty có 100 giờ máy và 80 giờ nhân công. Lợi nhuận từ mỗi sản phẩm A là 30 đô la và từ mỗi sản phẩm B là 40 đô la. Hãy lập kế hoạch sản xuất để tối đa hóa lợi nhuận.

Hy vọng bài học này đã cung cấp cho bạn 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 bạn học tập tốt!