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

1. Giới thiệu chung 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.

Quy hoạch tuyến tính có ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, quản lý, kỹ thuật, vận tải,... Ví dụ, một công ty có thể sử dụng quy hoạch tuyến tính để tối ưu hóa lợi nhuận bằng cách quyết định lượng sản phẩm cần sản xuất và phân phối.

2. Các yếu tố của bài toán quy hoạch tuyến tính

• Biến quyết định: Là các biến số cần tìm giá trị tối ưu.
• Hàm mục tiêu: Là hàm tuyến tính cần tối ưu hóa (lớn nhất hoặc nhỏ nhất).
• Ràng buộc: Là các bất đẳng thức hoặc đẳng thức tuyến tính giới hạn giá trị của các biến quyết định.

3. Dạng tổng quát 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 có dạng tổng quát như sau:

Tối ưu hóa: Z = c₁x₁ + c₂x₂ + ... + c_nx_n

Với các 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.
• 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.

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

a. Phương pháp đồ thị:

Phương pháp này dựa trên việc vẽ các đường thẳng biểu diễn các ràng buộc trên mặt phẳng tọa độ. Vùng thỏa mãn các ràng buộc là vùng đa giác lồi. Sau đó, ta tìm các đỉnh của đa giác lồi và tính giá trị của hàm mục tiêu tại các đỉnh này. Đỉnh nào cho giá trị lớn nhất (hoặc nhỏ nhất) thì đó là nghiệm tối ưu.

b. Phương pháp Simplex:

Phương pháp Simplex là một thuật toán lặp, bắt đầu từ một nghiệm cơ bản ban đầu và di chuyển từ đỉnh này sang đỉnh khác của vùng đa giác lồi cho đến khi tìm được nghiệm tối ưu.

5. 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ó 100 kg nguyên liệu và 80 giờ công. Hỏi xí nghiệp nên sản xuất bao nhiêu sản phẩm A và B để đạt lợi nhuận tối đa, biết rằng lợi nhuận từ một đơn vị sản phẩm A là 30 nghìn đồng và từ một đơn vị sản phẩm B là 40 nghìn đồng?

Giải:

Đặt x là số lượng sản phẩm A cần sản xuất và y là số lượng sản phẩm B cần sản xuất.

Hàm mục tiêu: Z = 30x + 40y (lợi nhuận)

Các ràng buộc:

• 2x + y ≤ 100 (nguyên liệu)
• x + 2y ≤ 80 (công)
• x ≥ 0, y ≥ 0

Sử dụng phương pháp đồ thị hoặc phương pháp Simplex, ta tìm được nghiệm tối ưu là x = 20, y = 40. Vậy xí nghiệp nên sản xuất 20 sản phẩm A và 40 sản phẩm B để đạt lợi nhuận tối đa là 2800 nghìn đồng.

6. Kết luận

Bài 1. Bài toán quy hoạch tuyến tính là một kiến thức quan trọng trong chương trình Toán 12. Việc nắm vững kiến thức này sẽ giúp bạn giải quyết các bài toán tối ưu hóa trong thực tế một cách hiệu quả. Hy vọng bài học này đã cung cấp cho bạn những kiến thức hữu ích và giúp bạn hiểu rõ hơn về quy hoạch tuyến tính.