Consider the LP $\min cx $ subject to $a^i x = b_i $ $i=1,...,m$ and $x \geq0$ where $x$ is an n-vector. Let $x^*$ be an optimal solution to this LP. Let $\pi^*$ be the optimal solution to the dual. Prove that $x^*$ is also optimal to
\begin{align*} \min \; \;& (c-\pi_k^* a^k) x \\ &a^i x = b_i, i=1,...,m \\ &x \geq 0 \end{align*}
whre $\pi_k^*$ is kth component of the vector $\pi^*$
thoughts
We are given that $cx^* \leq cx $ for all $x$ feasible. By the duality theorem, we see that $\pi^* = x^*$. We need to prove that
$$ (c- \pi_k^* a^k ) x^* \leq (c- \pi_i^* a^i ) x $$
But, since $cx^* \leq cx$, then
$$ - \pi_k^* a^k x^* \leq - \pi_i^* a^i x \implies \pi_k^* a^k x^* \geq \pi_i^* a^i x$$
here I get stuck. Am I thinking about this problem correctly? or my approach leads nowhere?
The new problem is $$\min (c^T-\pi_k^*e_k^TA)x$$
subject to $$Ax=b$$
$$x \ge 0$$
and the corresponding dual is
$$\max y^Tb$$
subject to $$y^TA \le (c^T-\pi_k^*e_k^TA)$$
At $x^*$ which is feasible in the primal, the optimal value is evaluated to be $$(c^T-\pi_k^*e_k^TA)x^*=b^T\pi^{*}-\pi_k^*e_k^Tb$$
Let's check if $y^*=\pi^*-\pi_k^*e_k$ is feasible for the new dual problem.
We have $$y^{*T}A = (\pi^*-\pi_k^*e_k)^TA \le (c^T-\pi_k^*e_k^TA),$$
$y^*$ is indeed feasible and
$$y^{*T}b = (\pi^*-\pi_k^*e_k)^Tb$$
which is equal to the primal objective value evaluated at $x^*$. Hence by strong duality, $x^*$ remains optimal.