More Linear Programming - DUality

In summary, the conversation discusses finding a primal solution and objective value for the LOP P, determining the dual problem D, finding a dual feasible solution and objective value, and discussing upper and lower bounds for the optimal value of the dual D. The conversation also touches on the question of whether P is unbounded and the process of finding values for the dual problem. The correct dual problem is determined to have three dual variables and two constraints, and the dual solution of y = (2,0)^t is found to have a bound of 0 <= w* <= 12.
  • #1
flyingpig
2,579
1

Homework Statement



Consider the following LOP P:

Max

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

s.t.

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

2)

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]

Then

[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) ?...
5)?..,
 
Last edited:
Physics news on Phys.org
  • #2
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
pLease help...
 
  • #4
flyingpig said:
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
 
  • #5
3 dual variables and two constraints? I have that?
 
  • #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:
  • #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?
 
  • #8
flyingpig said:
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]

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

RGV
 
  • #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:
  • #10
flyingpig said:
[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!

I give up.

RGV
 
  • #11
No nonon let me try again. editing
 
  • #12
Ray Vickson said:
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
 
  • #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
 
  • #14
So one of my dual solution is y = (2,0)^t

w(2,0) = 16 (unchanged)

So my bounds are

0 <= z* <=16
 
  • #15
Please dont' give up...
 
  • #16
Please...
 
  • #17
flyingpig said:
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
 
  • #18
Are you saying my dual is still wrong then?
 
  • #19
Ray Vickson said:
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?
 
  • #20
OKay I just found that y = (1,5,0)^t is even better!
 
  • #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:

Related to More Linear Programming - DUality

1. What is duality in linear programming?

Duality in linear programming refers to the relationship between the primal and dual LP problems. The dual problem is derived from the primal problem and provides a lower bound on the optimal objective value of the primal problem. This relationship is important because it allows us to solve the dual problem instead of the primal problem in some cases, making the solution process more efficient.

2. How is the dual problem formulated?

The dual problem is formulated by converting the primal problem into a maximization problem and then setting up a new objective function using the dual variables (which represent the constraints of the primal problem). The constraints of the dual problem are also derived from the constraints of the primal problem, but they are reversed in direction. The resulting dual problem is then solved using the simplex method or other optimization techniques.

3. What is the relationship between the optimal objective values of the primal and dual problems?

The optimal objective values of the primal and dual problems are always equal. This is known as the duality theorem. This means that if the optimal solution to the primal problem is x*, then the optimal solution to the dual problem is y* and the objective values of both problems are equal, i.e., cTx* = bTy*.

4. When is the dual problem useful?

The dual problem is useful in situations where the primal problem is difficult to solve or has a large number of variables and constraints. In these cases, solving the dual problem can be more efficient and can also provide insights into the structure of the primal problem. Additionally, the dual problem can be used to provide sensitivity analysis, i.e., how changes in the constraints or objective function of the primal problem affect the optimal solution.

5. Can both the primal and dual problems be infeasible or unbounded?

Yes, it is possible for both the primal and dual problems to be infeasible or unbounded. However, it is not possible for both to be infeasible at the same time. If the primal problem is infeasible, the dual problem will be unbounded and vice versa. This is known as complementary slackness and can be used to check the optimality of a solution to the primal and dual problems.

Similar threads

B General explicit solution to polynomial interpolation
    • General Math
Replies
3
Views
825
I Sampling theory and random sample
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
585
I Help finding a triangle inside a triangle
    • General Math
Replies
5
Views
2K
MHB Give a linear map that satisfies given properties
    • Calculus
Replies
3
Views
1K
Post-optimality analysis: Change in one of the constraints
    • Calculus and Beyond Homework Help
Replies
5
Views
1K
How Do Vector Spaces of Linear Maps Differ from Standard Vector Spaces?
    • Calculus and Beyond Homework Help
Replies
9
Views
1K
Integer programming model (alternating constraints)
    • Precalculus Mathematics Homework Help
Replies
5
Views
1K
MHB Determine vec {{x},{y},{3x+2y}} in R^3 form a vec space
    • Linear and Abstract Algebra
Replies
11
Views
2K
Linear Programming - Feasible sets?
    • Calculus and Beyond Homework Help
Replies
22
Views
4K
I Lipschitz continuity of vector-valued function
    • Calculus
Replies
3
Views
1K

Hot Threads

Recent Insights

Back
Top