1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximization problem with simplex method

  1. May 11, 2017 #1

    s3a

    User Avatar

    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. jcsd
  3. May 11, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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
  4. May 11, 2017 #3

    StoneTemplePython

    User Avatar
    Gold Member

    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.
     
  5. May 11, 2017 #4

    s3a

    User Avatar

    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.
     
  6. May 12, 2017 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Maximization problem with simplex method
  1. Maximization problem (Replies: 7)

  2. Simplex Problem (Replies: 1)

  3. Simplex method stuff (Replies: 12)

Loading...