Given real numbers $a$ and $b$, consider the problem $\mathrm{P}$ of minimizing

$$f(x)=a x_{11}+2 x_{12}+3 x_{13}+b x_{21}+4 x_{22}+x_{23}$$

subject to $x_{i j} \geqslant 0$ and

$$\begin{array}{r} x_{11}+x_{12}+x_{13}=5 \\ x_{21}+x_{22}+x_{23}=5 \\ x_{11}+x_{21}=3 \\ x_{12}+x_{22}=3 \\ x_{13}+x_{23}=4 \end{array}$$

List all the basic feasible solutions, writing them as $2 \times 3$ matrices $\left(x_{i j}\right)$.

Let $f(x)=\sum_{i j} c_{i j} x_{i j}$. Suppose there exist $\lambda_{i}, \mu_{j}$ such that

$$\lambda_{i}+\mu_{j} \leqslant c_{i j} \text { for all } i \in\{1,2\}, j \in\{1,2,3\}$$

Prove that if $x$ and $x^{\prime}$ are both feasible for $\mathrm{P}$ and $\lambda_{i}+\mu_{j}=c_{i j}$ whenever $x_{i j}>0$, then $f(x) \leqslant f\left(x^{\prime}\right) .$

Let $x^{*}$ be the initial feasible solution that is obtained by formulating $\mathrm{P}$ as a transportation problem and using a greedy method that starts in the upper left of the matrix $\left(x_{i j}\right)$. Show that if $a+2 \leqslant b$ then $x^{*}$ minimizes $f$.

For what values of $a$ and $b$ is one step of the transportation algorithm sufficient to pivot from $x^{*}$ to a solution that maximizes $f$ ?