Quy hoạch tuyến tính (LP)

Bài toán cực tiểu hoặc cực đại một hàm affine với các ràng buộc bất đẳng thức và đẳng thức affine, chẳng hạn $min{c}^{T}x$ với $Gx⪯h$, $Ax=b$. là một . Khi đa diện có đỉnh và giá trị tối ưu hữu hạn, có một nghiệm là đỉnh. Mọi LP đều đưa được về dạng chuẩn $min{c}^{T}x$ với $Ax=b$, $x⪰0$.

Lĩnh vực: Tối ưu hóa

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Giải thích kỹ thuật

Hình học. Tập mức của $c^{T}x$ là những vuông góc với $c$, và nghiệm là điểm của xa nhất theo hướng $-c$. Có bốn khả năng: Nghiệm duy nhất tại đỉnh, cả một mặt là tập nghiệm, không bị chặn dưới khi đa diện kéo dài theo một hướng $r$ có $c^{T}r<0$, hoặc bất khả thi.

Chuyển về dạng chuẩn. Thêm $s⪰0$ cho mỗi bất đẳng thức và viết mỗi biến tự do thành $x^{+}-x^{-}$ với $x^{+},x^{-}⪰0$. Nhiều bài toán không trông tuyến tính cũng là LP: Tâm Chebyshev, cực tiểu hàm tuyến tính từng khúc, cận chặt cho khi chỉ biết vài thông tin tuyến tính về phân phối, và quy hoạch phân tuyến tính sau một phép đổi biến. Nguồn: Convex Optimization, §4.3.

Ví dụ

Tìm hình tròn lớn nhất nằm trong một đa giác, tức tâm Chebyshev, là một LP với ba biến: Hai tọa độ của tâm và bán kính.

Khi nào cần dùng?

Lập kế hoạch, phân bổ, khớp dữ liệu theo chuẩn ${\ell }_1$ hoặc ${\ell }_{\mathrm{\infty }}$, và làm bài toán con trong nhiều thuật toán.

Câu hỏi ôn lại

Một LP có thể có đúng hai nghiệm tối ưu không?

Xem đáp án

Không. Tập nghiệm của một bài toán lồi là , nên một LP có không, một, hoặc vô số nghiệm.

Thuật ngữ liên quan

• Đa diện và đơn hình
• Nghiệm cơ sở của quy hoạch tuyến tính
• Quy hoạch toàn phương (QP và QCQP)