1

Let $P:= \{Ax = b, x \geq 0\} $ be a polyhedron in standard form, where $$A = \begin{bmatrix} 1 & -2 & 1 & 0 & 0\\ 2 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1\\ \end{bmatrix} \text{ and } b = \begin{bmatrix} 4 \\ 18 \\ 10 \end{bmatrix}$$ Find two infeasible basic solutions and two basic feasible solutions of $P.$

I know that for a infeasible basic solution, the solution has to contain a negative (is this true in general?) so considering $B_1 = \begin{bmatrix} A_3 & A_1 &A_5 \end{bmatrix}$ and $B_2 = \begin{bmatrix} A_2 & A_4 & A_5 \end{bmatrix}$ gives the respective solutions $$x_{B_1} = B_1^{-1}b= \begin{bmatrix} 9 & 0 &-5 & 0 & 10 \end{bmatrix}^T$$ and $$x_{B_2} = B_2^{-1}b= \begin{bmatrix} 0 & -2 & 0 & 20 & 12 \end{bmatrix}^T$$ which are the infeasible basic solutions. I am having hard time using this same approach to find a basic feasible solution such that the solution $x\geq 0.$ What is the best way to solve this problem?

holala
  • 733
  • use the two-phase method (or enumerate all 6-choose-3 combinations, it's really not that many) – LinAlg Sep 18 '20 at 00:54

1 Answers1

1

Consider $$B_3 = \begin{bmatrix} A_3 & A_4 & A_5 \end{bmatrix} = I_3$$ and $$B_4 = \begin{bmatrix} A_2 & A_3 & A_4 \end{bmatrix} $$ to obtain the basic feasible solutions $$x_{B_3} = B_3^{-1}b= \begin{bmatrix} 0 & 0 &4 & 18 & 10 \end{bmatrix}^T$$ and $$x_{B_4} = B_4^{-1}b= \begin{bmatrix} 0 & 10 &24 & 8 & 0 \end{bmatrix}^T.$$ Since $x \geq 0,$ we have a basic feasible solution.

Ab2020
  • 127