 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^{T}y=c_B$.

For any nonbasic column $a_j$, introduce $x_j=\epsilon >0$ while changing the basic vector from $u$ to $u-\epsilon G^{-1}{a}_j$. This stays feasible for sufficiently small $\epsilon$ because every $u_i>0$. Optimality at $u$ implies the objective slope $c_j-c_B^T{G}^{-1}{a}_j\le 0$. Therefore $a_j^{T}y\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}^{\ast }\ge 0$, the proposed $x^{\ast }$ is primal feasible andWeak duality, valid with unrestricted equality multipliers, proves $\boxed{x^{\ast }\text{ is optimal}}$. This also explains the stability of an optimal basis while its new basic coordinates remain nonnegative.