(Solved): Problem 3 (The dual of a linear program in equational form). Consider the (primal) linear program i ...

Problem 3 (The dual of a linear program in equational form). Consider the (primal) linear program in equational form: (P) $\max {\mathbf{c}}^T\mathbf{x}$ s.t. $A\mathrm{x}=\mathbf{b},\mathrm{x}?0$ where $A?{\mathbb{R}}^{m\times n},\mathbf{b}?{\mathbb{R}}^m,\mathbf{c}?{\mathbb{R}}^n$ and the variable $\mathbf{x}$ ranges over ${\mathbb{R}}^n$. The dual linear program is (D) $\min {\mathbf{b}}^T\mathbf{y}$ s.t. $A^T\mathbf{y}?\mathbf{s}=\mathbf{c},\mathbf{s}?0$ where $\mathbf{y}$ ranges over ${\mathbb{R}}^m$ and $\mathbf{s}$ ranges over ${\mathbb{R}}^n$. (a) Show that for any feasible point (y,s) of (D), ${\mathbf{b}}^T\mathbf{y}$ gives an upper bound on the primal linear program (P). Hint: show that ${\mathbf{c}}^T\mathbf{x}?{\mathbf{b}}^T\mathbf{y}$ for any feasible point $\mathbf{x}$ of $(\mathrm{P})$. (b) Show that the linear program (D) is equivalent to $\min {\mathbf{b}}^T\mathbf{y}\text{ s.t. }{A}^T\mathbf{y}?\mathbf{c}$