Modification of a proof to work for an LP in inequality form

50 Views Asked by At

Suppose an LP is given in the inequality form : $\max\langle c,x\rangle$ subject to $Ax\leq b$. We call $x$ a basic feasible solution to this problem if there are $n$ linearly independent inequalities that are satisfied as equalities. I'm trying to show that $x$ is a BFS iff it's an extreme point of the feasible set $S=\left\{ x|Ax\leq b\right\}$. I saw a proof of the result that if $x$ is a BFS corresponding to the problem of an LP in equational form, then it's an extreme point of the feasible set. That can be seen, for example, at this link: http://www.stats.ox.ac.uk/~cmcd/lp/lp.pdf.

My question is, what modifications in this proof are necessary to make it work for an LP given in the form of inequalities?