1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: More Linear Programming - DUality

  1. Sep 17, 2011 #1
    1. The problem statement, all variables and given/known data

    Consider the following LOP P:


    [tex]z = 3x_1 + x_2 -\frac{1}{2}x_3[/tex]


    [tex]2x_1 + x_2 + x_3 \leq 8[/tex]
    [tex]4x_1 + x_2 - x_3 \leq 10[/tex]
    [tex]x_1, x_2, x_3 \geq 0[/tex]

    1) Find a primal solution x and its objective value z = z(x)
    2) What is the LOP D that is Dual to P?
    3) Find a dual feasible solution y and its objective value w = w(y)
    4) What upper and lower bounds do question 1 and question 3 for the optimal value w* of the dual D?
    5) Is P unbounded? Why or why not?

    2. The attempt at a solution

    1) I was extremely lazy so I used x = (0,0,0)^t (I put the t because my prof does it all the time without any explanation - just like his lectures. He does the problem and never explains why)


    Basically I have to start with

    [a] [tex]z= 3x_1 + x_2 -\frac{1}{2}x_3 \leq (2x_1 + x_2 + x_3)y_1 + (4x_1 + x_2 - x_3)y_2 [/tex]


    [tex]w = 8y_1 + 10y_2 [/tex]

    The other inequalities follow. Basically from [a], I just had to compare the numbers in front and the inequality will pop up as

    [tex]3 \leq 2y_1 + 4y_2 + y_3[/tex]
    [tex]4 \leq y_2 - 3y_1 + y_3[/tex]

    3) Here is the thing that confuses me, in my notes my prof just wrote some values he came up to satisfy the inequalities. The book does that too.

    How in the word do you get these values?

    Is there a method to find these values? Like a quick way...

    Also what am I to assume y_1, y_2 and y_3? Since the x_1, x_2, x_3 >0, does that mean the y's are too?

    4) ?....
    Last edited: Sep 17, 2011
  2. jcsd
  3. Sep 17, 2011 #2

    Okay I just tried y = (0,0,9)^t and that seems to work

    w(0,0,9) = 0

    5) The upper and lower bounds are both 0...
  4. Sep 17, 2011 #3
    pLease help...
  5. Sep 18, 2011 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Go back to the textbook and read the appropriate sections.

    Your dual problem is wrong. In the dual problem we have: one dual variable for each constraint of the primal (excluding >= 0 constraints), and have one dual constraint for each variable of the primal. So, how many dual variables should you have? How many dual constraints?

  6. Sep 18, 2011 #5
    3 dual variables and two constraints? I have that?
  7. Sep 18, 2011 #6
    Oh wait my dual should be

    [tex]w = 8y_1 + 10y_2[/tex]

    [tex]3 \leq 2y_1 + 4y_2[/tex]

    [tex]1 \leq y_1 + y_2[/tex]

    [tex]\frac{-1}{2} \leq y_1 - y_3[/tex]
    Last edited: Sep 18, 2011
  8. Sep 18, 2011 #7
    So for 3), I tried y = (2,0,9) and I get that

    [tex]w(2,0,9) = 8(2) = 16[/tex]

    So for 4) my bounds are

    [tex]0 \leq z* \leq 16[/tex]?

    5) P is unbounded accoring to the inequality above?
  9. Sep 18, 2011 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What is y_3? Have you forgotten any other restrictions on the dual variables?

  10. Sep 18, 2011 #9
    [tex]w = 8y_1 + 10y_2[/tex]

    [tex]3 \leq 2y_1 + 4y_2[/tex]

    [tex]1 \leq y_1 + y_2[/tex]

    [tex]\frac{-1}{2} \leq y_1 - y_3[/tex]

    [tex]y_1, y_2, y_3 \geq 0[/tex]

    If this is right, then this is interesting because now all the other constraints and my w(y) do not have y_3!
    Last edited: Sep 18, 2011
  11. Sep 18, 2011 #10

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I give up.

  12. Sep 18, 2011 #11
    No nonon let me try again. editing
  13. Sep 18, 2011 #12
    I have three primal variables, x_1, x_2, x_3. So I need three constraints.

    I have two primal constraints, so I need two dual variables, y_1, y_2 (excluding the >= constraints)

    Oh wait I have a y_3...how did that get there
  14. Sep 18, 2011 #13
    No wait I just made one mistake

    [tex]w = 8y_1 + 10y_2[/tex]

    [tex]3 \leq 2y_1 + 4y_2[/tex]

    [tex]1 \leq y_1 + y_2[/tex]

    [tex]\frac{-1}{2} \leq y_1 - y_2[/tex] <=== this part

    [tex]y_1, y_2 \geq 0[/tex] <=== this part
  15. Sep 18, 2011 #14
    So one of my dual solution is y = (2,0)^t

    w(2,0) = 16 (unchanged)

    So my bounds are

    0 <= z* <=16
  16. Sep 18, 2011 #15
    Please dont' give up...
  17. Sep 18, 2011 #16
  18. Sep 18, 2011 #17

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Finally! Something correct at last.

  19. Sep 18, 2011 #18
    Are you saying my dual is still wrong then?
  20. Sep 18, 2011 #19
    Also I just chose that bound because it worked with all the inequalities, there are no unique bounds, but there are better bounds right? Is mine the best?
  21. Sep 18, 2011 #20
    OKay I just found that y = (1,5,0)^t is even better!
  22. Sep 18, 2011 #21
    Ray please come back for one more question...

    What is the bound for w*?

    EDIT: The bound is still the same, i.e. 0 <= w* <= 12

    I change to 12 because I used a new y optimum.

    Also for the last question. P is bounded by the inequality

    0 <= z* <= w* <=12

    0 <= z* <= 12

    EDIT2: I checked my notes, I don't think I am wrong. Thanks everyone!
    Last edited: Sep 18, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook