Lập trình tuyến tính Các khái niệm toán lớp 12 giúp tìm ra cực đại hoặc cực tiểu của các đại lượng khác nhau từ một loại bài toán tổng quát. Loại vấn đề này được gọi là vấn đề tối ưu hóa . Lập trình tuyến tính cho các khái niệm lớp 12 bao gồm tìm lợi nhuận tối đa, chi phí tối thiểu hoặc sử dụng tài nguyên tối thiểu, … Những lưu ý này được cung cấp ở đây để học sinh giúp các em trong quá trình ôn tập trong kỳ thi.
Trong bài viết này, hãy để chúng tôi hiểu kỹ thuật tối ưu hóa cho một vấn đề với sự trợ giúp của một ví dụ.
Các khái niệm về lập trình tuyến tính lớp 12
Trong lớp 12, các khái niệm lập trình tuyến tính được đề cập là:
- Giới thiệu
- Các bài toán lập trình tuyến tính và công thức toán học
- Một công thức toán học của các vấn đề
- Phương pháp đồ thị giải các bài toán lập trình tuyến tính
- Các dạng bài toán lập trình tuyến tính khác nhau
Các loại vấn đề lập trình tuyến tính khác nhau
Các dạng bài toán khác nhau trong bài toán lập trình tuyến tính có trong khái niệm lớp 12. Họ đang:
(i) Vấn đề sản xuất- Ở đây chúng tôi tối đa hóa lợi nhuận với sự trợ giúp của việc sử dụng tối thiểu tài nguyên.
(ii) Vấn đề Chế độ ăn uống- Chúng tôi xác định số lượng các chất dinh dưỡng khác nhau trong chế độ ăn uống để giảm thiểu chi phí sản xuất.
(iii) Vấn đề vận chuyển- Ở đây chúng tôi xác định lịch trình để tìm cách vận chuyển sản phẩm rẻ nhất vào thời gian tối thiểu.
Điều khoản của vấn đề lập trình tuyến tính
Tồn tại các thuật ngữ (hoặc thuật ngữ) cụ thể trong khi xây dựng và giải các bài toán lập trình tuyến tính. Hãy để chúng tôi xác định một số thuật ngữ quan trọng mà chúng tôi sẽ sử dụng ở đây.
Hàm mục tiêu: Một hàm tuyến tính có dạng Z = ax + by, trong đó a và b là hằng số, có giá trị cực tiểu hoặc cực đại được gọi là hàm mục tiêu tuyến tính.
Hãy xem xét một ví dụ, Z = 175x + 150y.
Đây là một hàm mục tiêu tuyến tính. Các biến x và y được gọi là biến quyết định.
Ràng buộc: Các bất đẳng thức tuyến tính hoặc phương trình hoặc các hạn chế đối với các biến của LPP (bài toán lập trình tuyến tính) được gọi là các ràng buộc. Các điều kiện x ≥ 0, y ≥ 0 được gọi là các giới hạn không âm.
Ví dụ, 5x + y ≤ 100; x + y ≤ 60 là các ràng buộc.
Bài toán tối ưu hóa: Bài toán tìm cách tối đa hóa hoặc tối thiểu hóa một hàm tuyến tính (ví dụ hai biến x và y) tuân theo các ràng buộc nhất định được xác định bởi một tập các bất đẳng thức tuyến tính được gọi là bài toán tối ưu hóa. Bài toán lập trình tuyến tính là dạng bài toán tối ưu hóa đặc biệt.
Vùng khả thi: Vùng chung được xác định bởi tất cả các ràng buộc đã cho bao gồm các ràng buộc không âm (x ≥ 0, y ≥ 0) của một bài toán lập trình tuyến tính được gọi là vùng khả thi (hay vùng lời giải) cho bài toán. Vùng không khả thi được gọi là vùng không khả thi.
Các giải pháp khả thi: Đây là các điểm trong và ngoài ranh giới của vùng khả thi đại diện cho các giải pháp khả thi của các khó khăn. Bất kỳ điểm nào nằm ngoài vùng khả thi được gọi là giải pháp không khả thi.
Giải pháp tối ưu (hoặc khả thi): Bất kỳ điểm nào trong vùng khả thi cho giá trị tối ưu (lớn nhất hoặc nhỏ nhất) của hàm mục tiêu được gọi là một giải pháp tối ưu.
Ghi chú:
- Điểm góc của vùng khả thi là giao điểm của hai đường ranh giới tạo thành vùng.
- Một vùng khả thi của một hệ bất đẳng thức tuyến tính nhất định được cho là bị giới hạn nếu nó có thể được bao trong một vòng tròn. Nếu không, nó không bị ràng buộc. Không bị ràng buộc có nghĩa là vùng khả thi có thể mở rộng vô thời hạn theo bất kỳ hướng nào.
Bài toán mẫu lớp 12 lập trình tuyến tính
Câu hỏi: Giải bài toán lập trình tuyến tính sau bằng đồ thị:
Thu nhỏ Z = 200 x + 500 y
tuân theo các ràng buộc:
x + 2y ≥ 10
3x + 4y ≤ 24
x ≥ 0, y ≥ 0
Giải pháp:
Hàm mục tiêu đã cho là:
Thu nhỏ Z = 200 x + 500 y…. (I)
Các hạn chế là:
x + 2y ≥ 10. (ii)
3x + 4y ≤ 24…. (Iii)
x ≥ 0, y ≥ 0…. (iv)
Đồ thị của các bất đẳng thức này là:
Vùng tô bóng trong hình (đồ thị trên) là vùng khả thi ABC được xác định bởi hệ thống các ràng buộc (ii), (iii) và (iv), được giới hạn.
Tọa độ của các điểm góc của vùng này (khả thi hoặc được tô bóng) cho biết A, B và C lần lượt là (0, 5), (4, 3) và (0, 6).
Bây giờ, chúng ta hãy đánh giá giá trị của Z = 200x + 500y tại những điểm này.
| Điểm góc | Giá trị tương ứng của Z |
| (0, 5) | 200 × 0 + 500 × 5 = 0 + 2500 = 2500 |
| (4, 3) | 200 × 4 + 500 × 3 = 800 + 1500 = 2300 (tối thiểu) |
| (0, 6) | 200 × 0 + 500 × 6 = 0 + 3000 = 3000 |
Do đó, giá trị nhỏ nhất của Z là 2300 tại điểm (4, 3).
Xem thêm:
