Primal/Dual Proof. I have a test tomorrow in one of my classes and I am trying to solve a proof in the practice problems. I am unsure how to start or what methods to use.
Consider the primal/dual pair of LP's
(P):
max cx
Ax=b
x>=0

(D):
min yb
yA>=c
y is free

Suppose that (P) and (D) have primal/dual solutions x* and y* with objective value z*. Show that for any vector t, if we change the constraints in the (P) to (P'):
max cx
Ax=b+t
x>=0

then (P') is either infeasible or has an optimal solution x' with objective value z'<=z*+y*t.
 A: If (P') is infeasible, then we have nothing to do.
Let $\mathbf{x'}$ be any feasible solution to the perturbed primal (P'), and $z=\mathbf{c}^T\mathbf{x'}$ be corresponding objective value.  (For consistency of the notations, we denote $\mathbf{x'^{*}}$ and $z'^*$ the optimal solution and objective value for (P') respectively.)
Consider $\mathbf{y^*}^TA\mathbf{x'}$.


*

*$\mathbf{y^*}^TA\mathbf{x'} \ge \mathbf{c}^T\mathbf{x'}=z'$ since we have $A^T\mathbf{y^*} \ge \mathbf{c}$ (from which we take transpose: $\mathbf{y^*}^T A \ge \mathbf{c}^T$) and $\mathbf{x'} \ge 0$ from (P').

*$\mathbf{y^*}^TA\mathbf{x'} = z^* + \mathbf{y^*}^T\mathbf{t}$


*

*$A\mathbf{x'}=\mathbf{b}+\mathbf{t}$ from (P').

*Multiply $\mathbf{y^*}^T$ on both sides of the above equation.
\begin{align}
\mathbf{y^*}^T A\mathbf{x'} = \mathbf{y^*}^T (\mathbf{b}+\mathbf{t})
\end{align}

*$z^*=\mathbf{y^*}^T\mathbf{b}$ as $\mathbf{y^*}$ is the optimal solution of (D).

*The RHS of the desired inequality appears.
\begin{align}
\mathbf{y^*}^T A\mathbf{x'} = z^* + \mathbf{y^*}^T \mathbf{t}
\end{align}



For any feasible solution $\mathbf{x'}$ to (P'), we have
$$z' \le \mathbf{y^*}^T A\mathbf{x'} = z^* + \mathbf{y^*}^T \mathbf{t}.$$
It remains to show the existence of an optimal solution.  We observe that (P') is bounded from the inequality we have just proved.  Therefore, (P') has an optimal solution $\mathbf{x'^*}$.
