Consider the LPP $ \ Ax \leq b , \ \ x \geq 0 \ $ having $ \ infeasible \ $ solution and $ b \geq 0 \ $.
We then start $ Phase \ I $ of the Simplex method by working with an Auxiliary problem in the following form:
$ Max \ \ -x_0 \\ Subject \ \ to \ \ [-1 \ | \ A ] \begin{bmatrix}x_0 \\ x \end{bmatrix} \leq b , \ \ x_0, x \geq 0 , .........(1) $
Then ,
(i) Write the Dual of the problem $ \ (1) \ $
(ii) Give reasons why $ \ infeasible \ $ solution to the Original problem implies there exists $ \ y , \ \ with \ \ A^T y \geq 0 , \ \ y \geq 0 \ \ and \ \ b \cdot y <0 \ $.
Answer:
(i)
The Dual of $ \ (1) \ $ can be written as
$ Min \ \ b^T y \\ \begin{bmatrix} -1 \\ A^T \end{bmatrix} \ y \geq \begin{bmatrix} -1 \\ -1 \\ ... \end{bmatrix} \ $
Am I Right ?
How can I solve the part (ii) ?
