Bertsimas& Tsitsiklis Exercise $4\mathrm{.}5$

Exercise $4\mathrm{.}5$ Consider a linear programming problem in standard form and assume that the rows of A are linearly independent. For each one of the following statements, provide either a proof or a counterexample.

$($a$)$ Let $x^{**}$ be a basic feasible solution. Suppose that for every basis corresponding to $x^{**},$ the associated basic solution to the dual is infeasible. Then, the optimal cost must be strictly less that $c^{\text{'}}{x}^{**}.$

$($b$)$ The dual of the auxiliary primal problem considered in Phase I of the simplex method is always feasible.

$($c$)$ Let $p_i$ be the dual variable associated with the $i$ th equality constraint in the primal. Eliminating the $i$ th primal equality constraint is equivalent to introducing the additional constraint $p_i=0$ in the dual problem.

$($d$)$ If the unboundedness criterion in the primal simplex algorithm is satisfied, then the dual problem is infeasible.