# Maximization problem with simplex method

1. May 11, 2017

### s3a

1. The problem statement, all variables and given/known data
Maximize the profit function P = 3x - y - 2z subject to the following

x - y - z ≤ 15
2x - y + 2z ≤ 50
2x + y + z ≤ 39

, where x ≥ 0, y ≥ 0, z ≥ 0.

2. Relevant equations
Simplex method / Simplex algorithm

3. The attempt at a solution
Hello to everyone who is reading this. :)

Here is my work:
https://pastebin.com/CT6cjMBu

As you can see from my work (in the above link), I get that max P = 51, which happens when (x_1, x_2, x_3) = (18, 0, 3).

However, the answer in the PDF says "Max P = 51 at (18, 3, 0)". Should it say (18, 0, 3), or am I the one that’s wrong? If I’m wrong, could someone please point out where my mistake is? Is this just a simple typo in the PDF with the answer?

Any input would be GREATLY appreciated!

2. May 11, 2017

### FactChecker

Substituting your numbers back in, I get P=48 and the solution is valid. Substituting their numbers back in, I get P=51 and the solution is feasible.

For both solutions, the first and last constraints are both active, but the book solution gets closer to the second constraint (less slack).

You probably should have pivoted again (or you pivoted one too many times). You should double check why you terminated.

Last edited: May 11, 2017
3. May 11, 2017

### StoneTemplePython

It occurs to me that doing simplex by hand is deeply unpleasant. I ran this LP quickly in Julia to corroborate the official solution.

It is not hard to confirm by hand that your answer is wrong, though. This is an idea that comes up many times in computing -- for a large class of problems, its easy to check the answer though perhaps a lot of work to get said answer.

Notice that the official solution of $P(18, 3, 0) = 3*18 - 3 - 2*0 = 51$. Your proposed solution of $P(18, 0, 3) = 3 * 18 - 0 -2*3 = 48$. It's also easy to verify that $(18, 3, 0)$ is legal according to the supplied constraints. From this we can be certain that your solution of $(18, 0, 3)$ is not correct. Proving that we cannot do better than $P(18, 3, 0)$, however takes a lot more work -- typically using duality.

I'm guessing that you flipped the y and z around on accident, and just need to 'unflip' them to have the correct answer.

4. May 11, 2017

### s3a

Thanks for the insightful comments. :)

It turns out that the problem was that I had to put the variable that's at the top of the matrix for the pivot column on the left of the matrix, whereas what I had incorrectly done is say to myself "This is the third row, so the i in x_i is 3.", but it should have been x_2, because the pivot was on the second column.

5. May 12, 2017

### Ray Vickson

The initial tableu is
$$\begin{array}{c|cccccc|r} \text{BV} &x&y&z&s_1&s_2&s_3&\text{rhs}\\ \hline P&-3&1&2&0&0&0&0\\ s_1&1&-1&-1&1&0&0&15\\ s_2&2&-1&2&0&1&0&50\\ s_3&2&1&1&0&0&1&39\\ \hline \end{array}$$
Here, BV stands for "basic variable", so the basic variables in the first tableau are $P, s_1, s_2, s_3.$

After the two simplex steps you outline I get the the new tableau:
$$\begin{array}{c|cccccc|r} \text{BV}&x&y&z&s_1&s_2&s_3&\text{rhs}\\ \hline P&0&0&1&5/3&0&2/3&51\\ x&1&0&0&1/3&0&1/3&18\\ s_2&0&0&3&-4/3&1&-1/3&17\\ y&0&1&1&-2/3&0&1/3&3\\ \hline \end{array}$$
The optimal basic solution is $(P,x,y,s_2) = (51,18,3,17)$ (basic variables) and $z=s_1=s_3=0$ (non-basic variables). To keep thing straight I recommend you append a column of basic-variable labels (called BV in my tableaux), and each time an old basic variable leaves and an old non-basic variable enters the new basis, the BV label is changed accordingly.

Last edited: May 12, 2017