# Linear Programming - The Big M Method - Proof questions [closed]

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.

Q: 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(∞). Let V(M) be the optimal value of the approximating problem. Show that $V(M) \leqslant V(∞)$.

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(∞), and hence conclude that the big−M method will produce the right solution for large enough values of $M$.

## closed as off-topic by Edward Jiang, user296602, colormegone, user147263, user223391 May 8 '16 at 23:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Edward Jiang, Community, colormegone, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

## 1 Answer

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.