Maximization problem with simplex method

[s3a]

Homework Statement

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.

Homework Equations

Simplex method / Simplex algorithm

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!

 

[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.

 

[StoneTemplePython]

Homework Statement

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.

Homework Equations

Simplex method / Simplex algorithm

The Attempt at a Solution

Hello to everyone who is reading this. :)

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

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

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!

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.

 

[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.

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

Simplex method / Simplex algorithm

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!

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.