Nghiệm cơ sở của quy hoạch tuyến tính

Với $Ax=b$ có m hàng , chọn m cột độc lập làm cơ sở, đặt các biến còn lại bằng 0 rồi giải cho các biến cơ sở. Nếu nghiệm thu được không âm trong dạng chuẩn, đó là nghiệm cơ sở khả thi.

Lĩnh vực: Quy hoạch

Đị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.

Bài giảng dùng khái niệm này

• Quy hoạch tuyến tính và quy hoạch độngToán cho AI

Giải thích kỹ thuật

Liên hệ với đỉnh. Trong dạng chuẩn $Ax=b$, $x\ge 0$, giả sử $A$ có hạng hàng $m$. Một cơ sở chọn $m$ cột $A_B$. Nghiệm cơ sở đặt $x_N=0$ và giải $A_B{x}_B=b$. Khả thi đòi $x_B\ge 0$.

Một biến cơ sở bằng 0 tạo suy biến: Nhiều cơ sở có thể biểu diễn cùng một đỉnh. Không phải mọi lựa chọn $m$ cột đều , và nghiệm giải được vẫn có thể chứa thành phần âm. Nguồn: Bertsimas & Tsitsiklis, Introduction to Linear Optimization, chương 2.

Ví dụ

Chọn hai cột của hệ hai phương trình cho một vuông $2\times 2$ rồi giải hai biến cơ sở.

Khi nào cần dùng?

Mô tả các đỉnh của và hiểu cơ chế của simplex.

Câu hỏi ôn lại

Biến cơ sở có bắt buộc dương không?

Xem đáp án

Không. Một biến cơ sở có thể bằng 0 và khi đó nghiệm cơ sở bị suy biến.

Thuật ngữ liên quan

• Hệ phương trình tuyến tính
• Tập lồi
• Điểm và miền khả thi