stu735101155.gnomio.com

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

${\displaystyle f(x_1,x_2,\dots ,x_n)=a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_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.