What exactly is a basis matrix in LPP?

Question

I'm studying simplex for solving a LPP. $A$ is a $m\times n$ matix. $$Ax=b$$Then the book says:

Let $x$ be a basic feasible solution to the standard form problem. Let $$B(1), B(2),\cdots B(m)$$ be the indices of the basic variables and let $$B=[A_{B(1)}\cdots A_{B(m)}]$$ be the corresponding basis matrix.

I can't understand what's this $B$ a basis for. Thanks!

Siong Thye Goh · Accepted Answer · 2019-03-18T11:55:17.677

2

Note that the columns of $B$ are independent and the columns of $B$ indeed span $\mathbb{R}^m$.

We can always solve $$Bx_B=b$$ for any given $b$.

edited Mar 18 '19 at 11:55

answered Mar 18 '19 at 11:39

Siong Thye Goh

149,520
20
88
149

Ya, true. But since we are in $\mathbb{R}^n$, why do we care about $\mathbb{R}^m$? – Ankit Kumar Mar 18 '19 at 11:56
2

the BFS of the standard form of LP has this property that $n-m$ entries are $0$ for sure, those are the non-basic variables. Those potentially non-zero positions are obtained by solving the linear system above. – Siong Thye Goh Mar 18 '19 at 12:00
Okay. I got it, thanks! – Ankit Kumar Mar 18 '19 at 12:01

What exactly is a basis matrix in LPP?

1 Answers1