The following linear program is a special case of the transportation problem (taken from Linear Programming: Methods and Applications by Saul I. Gass):
It is not hard to guess that $x_{11}=5,x_{12}=0,x_{13}=0,x_{21}=3,x_{22}=5,x_{23}=2$ yields an optimal solution with objective value $26$. We are asked (in Problem 9) to prove that this solution is optimal.
Suggested Solution: Assume towards a contradiction that this solution is not optimal, then either of $x_{12}$ or $x_{13}$ is positive. Assume without loss of generality that $x_{12}>0$ and define \begin{align*} y_{11}&=x_{11}+1 &y_{12}&=x_{12}-1 &y_{13}&=x_{13}\\ y_{21}&=x_{21} - 1 &y_{22}&=x_{22}+1 &y_{23}&=x_{23} \end{align*} Note that $y$ is a feasible solution, and achieving objective value \begin{align*} c^Ty&=y_{11}+2y_{12}+4y_{13}+3y_{21}+2y_{22}+y_{23}\\ &=\left(x_{11}+1\right)+2\left(x_{12}-1\right)+4x_{13}+3\left(x_{21}-1\right)+2\left(x_{22}+1\right)+x_{23}\\ &=x_{11}+2x_{12}+4x_{13}+3x_{21}+2x_{22}+x_{23}-2\\ &=c^Tx-2 \end{align*} i.e., $c^Ty<c^Tx$, contradicting the optimality of $x$.
However, this solution seems to be very specific. So I wanted to ask maybe you have comments or suggestions for a more elegant solution. At this point in the book, the reader is not introduced to the notation of duality.
Nevertheless, if someone is interested in the dual:
\begin{align*} &\max_{z\in\mathbb{R^5}} &5z_{1}+10z_{2}+8z_{3}+5z_{4}+2z_{5}\\ &\mathrm {s.b.t.} &z_{1}+z_{3}&\le1\\ & &z_{1}+z_{4}&\le2\\ & &z_{1}+z_{5}&\le4\\ & &z_{2}+z_{3}&\le3\\ & &z_{2}+z_{4}&\le2\\ & &z_{2}+z_{5}&\le1 \end{align*} taking $z_1=z_4=0,z_2=2,z_3=1,z_5=-1$ yields an optimal target value 26 (as promised by the strong duality theorem this equals the minimum value of the primal LP).