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

Quy hoạch tuyến tính là một phương pháp toán học được sử dụng rộng rãi trong nhiều lĩnh vực như kinh tế, quản lý, kỹ thuật để 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 tuyến tính. Bài 3 này sẽ tập trung vào việc sử dụng hệ bất phương trình bậc nhất hai ẩn để mô hình hóa và giải quyết các bài toán quy hoạch tuyến tính đơn giản.

1. Giới thiệu về Quy hoạch tuyến tính

Quy hoạch tuyến tính (Linear Programming - LP) là một kỹ thuật tối ưu hóa nhằm tìm ra giá trị lớn nhất hoặc nhỏ nhất của một hàm mục tiêu tuyến tính, tuân theo một tập hợp các ràng buộc tuyến tính. Các thành phần chính của một bài toán quy hoạch tuyến tính bao gồm:

• Hàm mục tiêu: Hàm cần tối ưu hóa (ví dụ: tối đa hóa lợi nhuận, tối thiểu hóa chi phí).
• Biến quyết định: Các biến đại diện cho các yếu tố cần quyết định (ví dụ: số lượng sản phẩm cần sản xuất).
• Ràng buộc: Các điều kiện giới hạn các giá trị của biến quyết định (ví dụ: nguồn lực có hạn).

2. Mô hình hóa bài toán bằng hệ bất phương trình bậc nhất hai ẩn

Để giải quyết một bài toán quy hoạch tuyến tính, bước đầu tiên là mô hình hóa bài toán bằng cách xác định hàm mục tiêu và các ràng buộc dưới dạng hệ bất phương trình bậc nhất hai ẩn. Ví dụ:

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 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ỗ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?

Mô hình hóa:

• Biến quyết định:
  • x: Số lượng sản phẩm A cần sản xuất.
  • y: Số lượng sản phẩm B cần sản xuất.
• Hàm mục tiêu: Tối đa hóa lợi nhuận Z = 30x + 40y
• Ràng buộc:
  • 2x + y ≤ 400 (Ràng buộc về nguyên liệu)
  • x + 2y ≤ 300 (Ràng buộc về công)
  • x ≥ 0, y ≥ 0 (Điều kiện không âm)

3. Giải bài toán quy hoạch tuyến tính bằng phương pháp đồ thị

Sau khi đã mô hình hóa bài toán, chúng ta có thể giải quyết nó bằng phương pháp đồ thị. 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 bất phương trình và xác định miền nghiệm là phần giao của các nửa mặt phẳng thỏa mãn tất cả các bất phương trình.
2. Xác định các đỉnh của miền nghiệm: Tìm tọa độ của các đỉnh 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ị của hàm mục tiêu tại mỗi đỉnh.
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 (đối với bài toán tối đa hóa) hoặc nhỏ nhất (đối với bài toán tối thiểu hóa).

4. Ví dụ minh họa

Với bài toán trên, sau khi vẽ miền nghiệm và tính giá trị hàm mục tiêu tại các đỉnh, ta thấy nghiệm tối ưu là x = 100, y = 200, với giá trị lợi nhuận tối đa là Z = 30(100) + 40(200) = 11000 nghìn đồng.

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

Quy hoạch tuyến tính có rất nhiều ứng dụng trong thực tế, bao gồm:

• Quản lý sản xuất: Lập kế hoạch sản xuất để tối đa hóa lợi nhuận hoặc tối thiểu hóa chi phí.
• Vận tải: Tìm đường đi ngắn nhất hoặc chi phí thấp nhất để vận chuyển hàng hóa.
• Tài chính: Quản lý danh mục đầu tư để tối đa hóa lợi nhuận hoặc giảm thiểu rủi ro.
• Lập kế hoạch: Phân bổ nguồn lực một cách hiệu quả.

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

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

• Bài tập 1: Một nông dân có 10 ha đất để trồng lúa và ngô. Để trồng 1 ha lúa cần 5 công nhân và 10 ngày công. Để trồng 1 ha ngô cần 3 công nhân và 5 ngày công. Nông dân có 40 công nhân và 60 ngày công. Hỏi nông dân nên trồng bao nhiêu ha lúa và bao nhiêu ha ngô để đạt lợi nhuận tối đa, biết rằng lợi nhuận từ mỗi ha lúa là 2 triệu đồng và từ mỗi ha ngô là 3 triệu đồng?
• Bài tập 2: Một công ty sản xuất hai loại sản phẩm X và Y. Để sản xuất một đơn vị sản phẩm X cần 2 giờ máy và 1 giờ công. Để sản xuất một đơn vị sản phẩm Y cần 1 giờ máy và 2 giờ công. Công ty có 100 giờ máy và 80 giờ công. Hỏi công ty nên sản xuất bao nhiêu sản phẩm X và Y để đạt lợi nhuận tối đa, biết rằng lợi nhuận từ mỗi đơn vị sản phẩm X là 5 nghìn đồng và từ mỗi đơn vị sản phẩm Y là 4 nghìn đồng?

Hy vọng bài học này đã giúp bạn hiểu rõ hơn về cách 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. Chúc bạn học tốt!