I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance.
Question
It is possible to combine the two phases of the two-phase method into a single procedure by the big-M method. Given the linear program in standard form
minimize $c^Tx$ subject to $Ax=b$, $x>0$,
one forms the approximating problem
minimize $c^Tx+M\sum_{i=1}^{m}y_i$ subject to $Ax+y=b$, $x>0$, $y>0$.
In this problem $y=\left ( y_1,y_2,...,y_m \right )$ is a vector of artificial variables and $M$ is a large constant. The term $M\sum_{i=1}^{m}y_i$ serves as a penalty term for nonzero $y_i$’s.
If this problem is solved by the simplex method, show the following:
a) If an optimal solution is found with $y = 0$, then the corresponding $x$ is an optimal basic feasible solution to the original problem.
b) If for every $M > 0$ an optimal solution is found with $y \neq 0$, then the original problem is infeasible.
c) If for every $M > 0$ the approximating problem is unbounded, then the original problem is either unbounded or infeasible.
d) Suppose now that the original problem has a finite optimal value $V(\infty)$. Let $V(M)$ be the optimal value of the approximating problem. Show that $V(M) \leqslant V(\infty)$.
e) Show that for $M1 \leqslant M2$ we have $V(M1) \leqslant V(M2)$.
f) Show that there is a value $M_0$ such that for $M > M_0$, $V(M) = V(\infty)$, and hence conclude that the big−M method will produce the right solution for large enough values of $M$.
I didn't know it, I like this method.
a) If an optimal solution with $y=0$ is found, it is obviously a feasible solution of the original problem.
Let us assume the corresponding $x$ is not optimal regarding the original problem. Then, there would be a feasible $x_0$ such that $c^Tx_0<c^Tx$. Then, $(x_0,y)$ would be a feasible cheaper solution for the new problem. Which is absurd.
Hence $x$ is optimal regarding the original problem.
e) You are looking at a problem with the same constraints, but a cost function always more expensive, so $V(M_1)\leq V(M_2)$
d) The fact that e) is true and the original problem is bounded implies $V(n), n \in \mathbb{N}$ is a monotonous bounded series, so converges.