Quy hoạch tuyến tính

Trong toán học, quy hoạch tuyến tính (QHTT) (tiếng Anh: linear programming - LP) là bài toán tối ưu hóa, trong đó hàm mục tiêu (objective function) và các điều kiện ràng buộc đều là tuyến tính.

Trong bài toán này, cho một đa tạp (polytope) (chẳng hạn một đa giác hoặc một đa diện), và một hàm tuyến tính (affine) nhận giá trị thực

$$f(x_1, x_2, \dots, x_n) = a_1x_1 + a_2x_2 + \dots + a_nx_n + b + c$$ xác định trên đa tạp đó, mục đích là tìm một điểm trên đa tạp tại đó hàm có giá trị nhỏ nhất (hoặc lớn nhất). Các điểm như vậy có thể không tồn tại, nhưng nếu chúng tồn tại phải tìm được ít nhất một điểm.

Bài toán thực tế

Tiệm bánh của bạn

Giả sử bạn đang làm chủ một tiệm bánh nhỏ. Bạn sản xuất 2 loại bánh:

• Bánh Mì ($x_1$): Lãi 20.000đ/cái.
• Bánh Ngọt ($x_2$): Lãi 30.000đ/cái.

Nguồn lực có hạn (Ràng buộc):

• Bột: Bạn chỉ còn 10kg bột. Một bánh mì tốn 0.5kg, một bánh ngọt tốn 1kg.
• Thời gian: Bạn chỉ có 8 tiếng (480 phút). Một bánh mì tốn 10 phút, một bánh ngọt tốn 30 phút.

Câu hỏi: 

Bạn nên làm bao nhiêu bánh mì ($x_1$) và bao nhiêu bánh ngọt ($x_2$) để Lợi nhuận ($Z$) cao nhất?

Cách giải:

• Vẽ hai đường thẳng giới hạn lên đồ thị. Phần giao nhau giữa chúng và hai trục tọa độ tạo thành một đa giác gọi là vùng khả thi.
• Các đỉnh của đa giác này là: $A(0, 0)$, $B(0, 10)$, $C(20, 0)$, và điểm giao nhau $D(24, -)$ (tùy vào tính toán cụ thể).
• Thay tọa độ các đỉnh vào hàm $Z$. Điểm nào cho $Z$ lớn nhất chính là đáp án.Kết quả ví dụ này: Bạn sẽ tìm ra số lượng bánh tối ưu để máy móc và bột không bị lãng phí mà tiền thu về là nhiều nhất.

Vẽ đồ thị

Chúng ta chuyển bài toán trên thành hệ bất phương trình:

• Hàm mục tiêu: $Z = 20x_1 + 30x_2$ (đơn vị nghìn đồng)
• Ràng buộc bột: $0.5x_1 + 1x_2 \leq 10$
• Ràng buộc thời gian: $10x_1 + 30x_2 \leq 480$
• Điều kiện thực tế: $x_1, x_2 \geq 0$

Bài giải