LPP auxiliary problem optimal solution

Question

Let's look at a linear programming problem $$\max\{\langle c,x\rangle \ \colon Ax=b, \ x\geq 0\}$$ and its auxiliary problem $$\max\{\langle \overline{c},\overline{x}\rangle\ \colon \overline{A}\overline{x}=b, \ \overline{x}\geq 0\}.$$ I want to prove that if the LPP feasible region is not empty, then there is $M_0$, such that for all $M\geq M_0$ the auxiliary problem has a solution and for the optimal solution $x_{n+1}=x_{n+2}=\ldots =x_{n+k}=0$.

For notation: $$\langle c,x\rangle =c_1x_1+c_2x_2+\ldots +c_nx_n,$$ $$x=(x_1,x_2,\ldots , x_n), \ \overline{x}=(x_1,x_2,\ldots ,x_n,x_{n+1},\ldots ,x_{n+k}) $$ $$\langle \overline{c},\overline{x}\rangle =\langle c,x\rangle -M(x_{n+1}+x_{n+2}+\ldots +x_{n+k}).$$ $$Ax=b\Leftrightarrow \begin{cases}a_{11}x_1+a_{12}x_2+\ldots +a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+\ldots +a_{2n}x_n=b_2\\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots +a_{mn}x_n=b_m \end{cases}$$ $$\overline{A}\overline{x}=b\Leftrightarrow \begin{cases}a_{11}x_1+a_{12}x_2+\ldots +a_{1n}x_n+x_{n+1}=b_1\\ a_{21}x_1+a_{22}x_2+\ldots +a_{2n}x_n+x_{n+2}=b_2\\ \ldots \\ a_{m1}x_1+a_{m2}x_2+ \ldots +a_{mn}x_n+x_{n+k}=b_m \end{cases}$$

Answer 1

Let $x$ be an optimal problem to the original problem with objective value $p := c^Tx$, and let $\tilde{x}$ be the vector $(x,0,0,\ldots,0)$ (the corresponding solution in the auxiliary problem), which is feasible and also yiels an objective value of $p$. Using revised simplex, the reduced cost of $x_{n+j}$ for $\tilde{x}$ is $c_B^T B^{-1} e_j - M$, with $e_j$ the $j^{th}$ unit vector. For $M_0 = \max_j \{ c_B^T B^{-1} e_j \}$, the reduced costs becomes negative for the extra variables, proving the solution $\tilde{x}$ is optimal with $x_{n+j}=0$.