Homework Help: More Linear Programming - DUality

1. Sep 17, 2011

flyingpig

1. The problem statement, all variables and given/known data

Consider the following LOP P:

Max

$$z = 3x_1 + x_2 -\frac{1}{2}x_3$$

s.t.

$$2x_1 + x_2 + x_3 \leq 8$$
$$4x_1 + x_2 - x_3 \leq 10$$
$$x_1, x_2, x_3 \geq 0$$

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)

2)

[a] $$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$$

Then

$$w = 8y_1 + 10y_2$$

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

$$3 \leq 2y_1 + 4y_2 + y_3$$
$$4 \leq y_2 - 3y_1 + y_3$$

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) ?....
5)?..,

Last edited: Sep 17, 2011
2. Sep 17, 2011

flyingpig

4)

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

3. Sep 17, 2011

flyingpig

4. Sep 18, 2011

Ray Vickson

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?

RGV

5. Sep 18, 2011

flyingpig

3 dual variables and two constraints? I have that?

6. Sep 18, 2011

flyingpig

Oh wait my dual should be

$$w = 8y_1 + 10y_2$$

$$3 \leq 2y_1 + 4y_2$$

$$1 \leq y_1 + y_2$$

$$\frac{-1}{2} \leq y_1 - y_3$$

Last edited: Sep 18, 2011
7. Sep 18, 2011

flyingpig

So for 3), I tried y = (2,0,9) and I get that

$$w(2,0,9) = 8(2) = 16$$

So for 4) my bounds are

$$0 \leq z* \leq 16$$?

5) P is unbounded accoring to the inequality above?

8. Sep 18, 2011

Ray Vickson

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

RGV

9. Sep 18, 2011

flyingpig

$$w = 8y_1 + 10y_2$$

$$3 \leq 2y_1 + 4y_2$$

$$1 \leq y_1 + y_2$$

$$\frac{-1}{2} \leq y_1 - y_3$$

$$y_1, y_2, y_3 \geq 0$$

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
10. Sep 18, 2011

Ray Vickson

I give up.

RGV

11. Sep 18, 2011

flyingpig

No nonon let me try again. editing

12. Sep 18, 2011

flyingpig

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

13. Sep 18, 2011

flyingpig

No wait I just made one mistake

$$w = 8y_1 + 10y_2$$

$$3 \leq 2y_1 + 4y_2$$

$$1 \leq y_1 + y_2$$

$$\frac{-1}{2} \leq y_1 - y_2$$ <=== this part

$$y_1, y_2 \geq 0$$ <=== this part

14. Sep 18, 2011

flyingpig

So one of my dual solution is y = (2,0)^t

w(2,0) = 16 (unchanged)

So my bounds are

0 <= z* <=16

15. Sep 18, 2011

flyingpig

16. Sep 18, 2011

flyingpig

17. Sep 18, 2011

Ray Vickson

Finally! Something correct at last.

RGV

18. Sep 18, 2011

flyingpig

Are you saying my dual is still wrong then?

19. Sep 18, 2011

flyingpig

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?

20. Sep 18, 2011

flyingpig

OKay I just found that y = (1,5,0)^t is even better!

21. Sep 18, 2011

flyingpig

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