[proofplan]
We show that the current basis $B$ yields an optimal solution by proving that no feasible point can achieve a higher objective value. The argument decomposes the objective function into its value at the basic feasible solution plus a correction term involving the reduced costs and the non-basic variables. Since the reduced costs are all non-positive and the non-basic variables are all non-negative by feasibility, the correction term is non-positive, so no feasible point improves on $x^*$.
[/proofplan]
[step:Decompose the objective in terms of basic and non-basic variables]
Let $x$ be any feasible solution to the LP. Partition the variables into basic components $x_B$ and non-basic components $x_N$, so the constraint $Ax = b$ reads
\begin{align*}
A_B x_B + A_N x_N = b.
\end{align*}
Since $A_B$ is invertible (it is a basis matrix), we solve for the basic variables:
\begin{align*}
x_B = A_B^{-1} b - A_B^{-1} A_N x_N.
\end{align*}
Substituting into the objective function $f(x) = c_B^\top x_B + c_N^\top x_N$:
\begin{align*}
f(x) &= c_B^\top \bigl(A_B^{-1} b - A_B^{-1} A_N x_N\bigr) + c_N^\top x_N \\
&= c_B^\top A_B^{-1} b + \bigl(c_N^\top - c_B^\top A_B^{-1} A_N\bigr) x_N.
\end{align*}
The vector $\bar{c}_N^\top := c_N^\top - c_B^\top A_B^{-1} A_N$ is the vector of reduced costs of the non-basic variables. Therefore
\begin{align*}
f(x) = c_B^\top A_B^{-1} b + \bar{c}_N^\top x_N.
\end{align*}
[guided]
The objective function of a linear program can always be rewritten in terms of the non-basic variables alone, once we use the equality constraints to eliminate the basic variables. Why is this useful? Because the basic feasible solution $x^*$ has $x_N^* = 0$ by definition, so $f(x^*) = c_B^\top A_B^{-1} b$. Any other feasible point $x$ differs from $x^*$ only through the correction term $\bar{c}_N^\top x_N$, which we can bound using the sign of the reduced costs.
Concretely, the constraint $Ax = b$ partitions as $A_B x_B + A_N x_N = b$. Since $B$ is a basis, $A_B$ is an $m \times m$ invertible matrix, and we can solve:
\begin{align*}
x_B = A_B^{-1} b - A_B^{-1} A_N x_N.
\end{align*}
Substituting into the objective $f(x) = c_B^\top x_B + c_N^\top x_N$:
\begin{align*}
f(x) &= c_B^\top \bigl(A_B^{-1} b - A_B^{-1} A_N x_N\bigr) + c_N^\top x_N \\
&= c_B^\top A_B^{-1} b + \bigl(c_N^\top - c_B^\top A_B^{-1} A_N\bigr) x_N \\
&= f(x^*) + \bar{c}_N^\top x_N,
\end{align*}
where $\bar{c}_N^\top = c_N^\top - c_B^\top A_B^{-1} A_N$ is the reduced cost vector. This decomposition is the algebraic engine of the simplex method: the reduced costs measure the rate of change of the objective as each non-basic variable increases from zero.
[/guided]
[/step]
[step:Bound the correction term using non-positive reduced costs and non-negative variables]
At the basic feasible solution $x^*$, we have $x_N^* = 0$, so $f(x^*) = c_B^\top A_B^{-1} b$. For any feasible $x$, the non-negativity constraint $x \geq 0$ implies $x_N \geq 0$. By hypothesis, every component of the reduced cost vector satisfies $(\bar{c}_N)_j \leq 0$. Therefore
\begin{align*}
\bar{c}_N^\top x_N = \sum_{j \in N} (\bar{c}_N)_j \, (x_N)_j \leq 0,
\end{align*}
since each summand is the product of a non-positive number and a non-negative number.
[guided]
This is the decisive step. We need two ingredients:
1. **Non-positive reduced costs**: the hypothesis $\bar{c}_N \leq 0$ (component-wise) means that increasing any non-basic variable from zero can only decrease (or leave unchanged) the objective value.
2. **Non-negative non-basic variables**: feasibility requires $x \geq 0$, and in particular $x_N \geq 0$.
Combining these: each term $(\bar{c}_N)_j \cdot (x_N)_j$ in the sum $\bar{c}_N^\top x_N$ is the product of a non-positive factor and a non-negative factor, hence non-positive. The entire sum is therefore non-positive:
\begin{align*}
\bar{c}_N^\top x_N = \sum_{j \in N} (\bar{c}_N)_j \, (x_N)_j \leq 0.
\end{align*}
What would fail if some reduced cost were positive? If $(\bar{c}_N)_k > 0$ for some $k \in N$, then increasing $(x_N)_k$ from zero would make the correction term positive, potentially improving the objective. This is precisely the entering variable selection rule of the simplex method: the algorithm pivots on a variable with positive reduced cost to improve the solution.
[/guided]
[/step]
[step:Conclude that $x^*$ is optimal]
Combining the decomposition from the first step with the bound from the second step, for every feasible $x$:
\begin{align*}
f(x) = f(x^*) + \bar{c}_N^\top x_N \leq f(x^*).
\end{align*}
Since $f(x) \leq f(x^*)$ holds for all feasible $x$, the basic feasible solution $x^*$ attains the maximum of $f$ over the feasible set.
[/step]
