What is wrong with this linear program $\max z = 3x_1+2x_2$?

Question

I solved a linear program. It is wrong. The answer is that $(x_1,x_2) = (50,75)$ and the maximum value is $300$, but instead I am getting $(x_1,x_2) = (50,100)$ and the maximum being $350$. Why is that?

---

Solve

$$\max z = 3x_1+2x_2$$

$$\begin{cases} x_1 \le 50\\ x_2\le 100\\ 2x_1+4x_2\le 400\\ x_1,x_2 \ge 0 \end{cases}$$

Transform the inequalities...

$$\begin{cases} x_1 + x_3 = 50\\ x_2 + x_4 = 100\\ 2x_1+4x_2 + x_5 = 400 \end{cases}$$

We have the matrix:

$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 50 \\ 0 & 1 & 0 & 1 & 0 & 100 \\ 2 & 4 & 0 & 0 & 1 & 400 \\ -3 & -2 & 0 & 0 & 0 & -z \end{bmatrix}$$

The pivot is $[1,1]$. We perform:

$$-2r_1+r_3 , 3r_1+r_4$$

$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 50 \\ 0 & 1 & 0 & 1 & 0 & 100 \\ 0 & 4 & -2 & 0 & 1 & 300 \\ 0 & -2 & 3 & 0 & 0 & 150 - z \end{bmatrix}$$

The pivot is $[2,2]$. We perform:

$$-4r_2 + r_3 , 2r_2+r_4$$

$$\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 50 \\ 0 & 1 & 0 & 1 & 0 & 100 \\ 0 & 0 & -2 & -4 & 1 & -100 \\ 0 & 0 & 3 & 2 & 0 & 350 - z \end{bmatrix}$$

We have the optimal solution $(50,100,0,0,-100)$. Evaluate it on the function:

$3(50)+2(100) = 350$ is the maximum value.

Answer 1

In the second step, you should pivot around $[3,2]$ instead, since $\frac{300}{4}<\frac{100}{1}$.

You get a wrong answer because you have a negative entry in the last column, and using your values for $x_1$ and $x_2$, you will have to set the two slack variables $x_3$ and $x_4$ equal to $0$. In the third row, this results in $x_5=-100$, which contradicts $x_5\geq 0$.

Answer 2

See my solution. I think it will help you