For given positive real numbers $\left(c_{i j}: i, j \in\{1,2,3\}\right)$, consider the linear program

$$P: \operatorname{minimize} \sum_{i=1}^{3} \sum_{j=1}^{3} c_{i j} x_{i j},$$

subject to $\sum_{i=1}^{3} x_{i j} \leqslant 1$ for all $j, \quad \sum_{j=1}^{3} x_{i j} \geqslant 1$ for all $i$,

and $x_{i j} \geqslant 0$ for all $i, j$.

(i) Consider the feasible solution $x$ in which $x_{11}=x_{12}=x_{22}=x_{23}=x_{31}=x_{33}=1 / 2$ and $x_{i j}=0$ otherwise. Write down two basic feasible solutions of $P$, one of which you can be sure is at least as good as $x$. Are either of these basic feasible solutions of $P$ degenerate?

(ii) Starting from a general definition of a Lagrangian dual problem show that the dual of $P$ can be written as

$$D: \operatorname{maximize}_{\lambda_{i} \geqslant 0, \mu_{i} \geqslant 0} \sum_{i=1}^{3}\left(\lambda_{i}-\mu_{i}\right) \quad \text { subject to } \lambda_{i}-\mu_{j} \leqslant c_{i j} \text { for all } i, j .$$

What happens to the optimal value of this problem if the constraints $\lambda_{i} \geqslant 0$ and $\mu_{i} \geqslant 0$ are removed?

Prove that $x_{11}=x_{22}=x_{33}=1$ is an optimal solution to $P$ if and only if there exist $\lambda_{1}, \lambda_{2}, \lambda_{3}$ such that

$$\lambda_{i}-\lambda_{j} \leqslant c_{i j}-c_{j j}, \quad \text { for all } i, j$$

[You may use any facts that you know from the general theory of linear programming provided that you state them.]