= Solution
The expression $G^{-1}$ presupposes that $G$ is invertible; positivity of the stated optimal coordinates alone would not prove that, so use the nonsingularity implicit in this expression. Let $c_B$ be the first $m$ components of $c$ and set $y=G^{-T}c_B$. Then $G^Ty=c_B$.
For any nonbasic column $a_j$, introduce $x_j=\varepsilon>0$ while changing the basic vector from $u$ to $u-\varepsilon G^{-1}a_j$. This stays feasible for sufficiently small $\varepsilon$ because every $u_i>0$. Optimality at $u$ implies the objective slope $c_j-c_B^TG^{-1}a_j\le0$. Therefore $a_j^Ty\ge c_j$ for every such column, and the basic columns satisfy equality. Thus $y$ is dual feasible, independently of the right-hand side.
For $v=G^{-1}b^*\ge0$, the proposed $x^*$ is primal feasible and
$$
c^Tx^*=c_B^Tv=y^TGv=y^Tb^*.
$$
<Weak duality>, valid with unrestricted equality multipliers, proves $\boxed{x^*\text{ is optimal}}$. This also explains the stability of an optimal <basis> while its new basic coordinates remain nonnegative.
Back to article page
