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

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.

Các bài toán quy hoạch tuyến tính thường xuất hiện trong nhiều lĩnh vực khác nhau như kinh tế, quản lý, kỹ thuật, logistics,… Ví dụ, một doanh nghiệp có thể sử dụng bài toán 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. Mô hình toán học 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 thường được mô tả bằng các thành phần sau:

• Biến quyết định: Các biến số cần tìm giá trị tối ưu (ví dụ: x, y).
• Hàm mục tiêu: Hàm số tuyến tính cần tối ưu hóa (ví dụ: f(x, y) = 3x + 2y).
• Ràng buộc: 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 (ví dụ: x + y ≤ 5, x ≥ 0, y ≥ 0).

Mô hình toán học của một bài toán quy hoạch tuyến tính có dạng:

Tối ưu hóa (max hoặc min) f(x₁, x₂, …, x_n) = c₁x₁ + c₂x₂ + … + c_nx_n

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

1. a₁₁x₁ + a₁₂x₂ + … + a_1nx_n ≤ b₁
2. a₂₁x₁ + a₂₂x₂ + … + a_2nx_n ≤ b₂
3. …
4. a_m1x₁ + a_m2x₂ + … + a_mnx_n ≤ b_m
5. x_i ≥ 0, ∀ i = 1, 2, …, n

3. Vận dụng hệ bất phương trình bậc nhất hai ẩn để giải quyết bài toán quy hoạch tuyến tính

Trong trường hợp bài toán quy hoạch tuyến tính chỉ có hai biến quyết định (x và y), chúng ta có thể sử dụng phương pháp đồ thị để giải quyết. Các bước thực hiện như sau:

1. Vẽ miền nghiệm: Vẽ các đường thẳng tương ứng với các ràng buộc. Miền nghiệm là phần mặt phẳng thỏa mãn tất cả các ràng buộc.
2. Xác định 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.
3. 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ính giá trị tương ứng.
4. 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 hóa) hoặc nhỏ nhất (nếu tối thiểu hóa).

4. Ví dụ minh họa

Một xưởng may có 200 mét vải và 160 giờ máy. Để may một bộ quần áo loại A cần 1 mét vải và 2 giờ máy. Để may một bộ quần áo loại B cần 2 mét vải và 1 giờ máy. Hỏi xưởng may nên may bao nhiêu bộ quần áo loại A và loại B để có lợi nhuận cao nhất, biết rằng lợi nhuận của một bộ quần áo loại A là 30 nghìn đồng và của một bộ quần áo loại B là 50 nghìn đồng?

Giải:

Gọi x là số bộ quần áo loại A và y là số bộ quần áo loại B.

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

Ràng buộc:

• x + 2y ≤ 200 (vải)
• 2x + y ≤ 160 (máy)
• x ≥ 0
• y ≥ 0

(Giải chi tiết bằng phương pháp đồ thị và tìm ra nghiệm tối ưu)

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

(Liệt kê một số bài tập tương tự để học sinh tự luyện tập)

6. Kết luận

Bài học hôm nay đã giúp các em hiểu rõ về cách vận dụng hệ bất phương trình bậc nhất hai ẩn để giải quyết các bài toán quy hoạch tuyến tính. Hy vọng rằng các em sẽ áp dụng kiến thức này vào thực tế và đạt kết quả tốt trong học tập.