More Linear Programming - DUality

[flyingpig]

Homework Statement

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)

Basically I have to start with

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

 

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

 

[flyingpig]

pLease help...

 

[Ray Vickson]

pLease help...

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

 

[flyingpig]

3 dual variables and two constraints? I have that?

 

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

 

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

 

[Ray Vickson]

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

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

RGV

 

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

 

[Ray Vickson]

$$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!

I give up.

RGV

 

[flyingpig]

No nonon let me try again. editing

 

[flyingpig]

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

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

 

[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

 

[flyingpig]

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

w(2,0) = 16 (unchanged)

So my bounds are

0 <= z* <=16

 

[flyingpig]

Please dont' give up...

 

[flyingpig]

Please...

 

[Ray Vickson]

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

w(2,0) = 16 (unchanged)

So my bounds are

0 <= z* <=16

Finally! Something correct at last.

RGV

 

[flyingpig]

Are you saying my dual is still wrong then?

 

[flyingpig]

Finally! Something correct at last.

RGV

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?

 

[flyingpig]

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

 

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