Simplex Method, Duality Problem

  • Thread starter Thread starter IsaacStats
  • Start date Start date
  • Tags Tags
    Duality Method
Click For Summary
SUMMARY

The discussion focuses on demonstrating that the solution x1=5/26, x2=5/2, x3=27/26 is optimal for the linear programming problem (LPP) defined by maximizing z=9x1+14x2+7x3 under specific constraints. The dual problem is presented as minimizing z'=6w1+12w2+6w3 with corresponding constraints. Participants emphasize the importance of correctly interpreting the primal and dual relationships, particularly regarding the coefficients in the constraints. The conversation highlights the necessity of verifying the primal and dual formulations to ensure accurate conclusions about optimality.

PREREQUISITES
  • Understanding of Linear Programming Problems (LPP)
  • Familiarity with the Simplex Method and its alternatives
  • Knowledge of Duality in Linear Programming
  • Ability to analyze and interpret mathematical constraints
NEXT STEPS
  • Study the properties of primal and dual relationships in linear programming
  • Learn about alternative methods to the Simplex Method for solving LPPs
  • Explore sensitivity analysis in linear programming
  • Review examples of optimality conditions in dual problems
USEFUL FOR

Students in operations research, mathematicians, and anyone involved in optimization problems, particularly those studying linear programming and duality concepts.

IsaacStats
Messages
11
Reaction score
0
Hello everyone, I have the following question:

Show without using the simplex method that
x1=5/26, x2=5/2, x3=27/26
is an optimal solution to the following LPP.

Maximize z=9x1+14x2+7x3 subject to
2x1+x2+3x3<= 6
5x1+4x2+x3<= 12
12x2 <= 5
x1,x2,x3 unrestricted.

=>
Dual is the following:

Minimize z'=6w1+12w2+6w3 subject to
2w1+5w2 >= 9
w1+4w2+2w3>= 14
3w1+w2 >= 7
w1,w2,w3 >= 0

I am lost regarding where I should proceed next. Looking for your guidance.
 
Physics news on Phys.org
As this appears to be a homework question, I have moved it to the Homework & Coursework section.
 
IsaacStats said:
Hello everyone, I have the following question:

Show without using the simplex method that
x1=5/26, x2=5/2, x3=27/26
is an optimal solution to the following LPP.

Maximize z=9x1+14x2+7x3 subject to
2x1+x2+3x3<= 6
5x1+4x2+x3<= 12
12x2 <= 5
x1,x2,x3 unrestricted.

=>
Dual is the following:

Minimize z'=6w1+12w2+6w3 subject to
2w1+5w2 >= 9
w1+4w2+2w3>= 14
3w1+w2 >= 7
w1,w2,w3 >= 0

I am lost regarding where I should proceed next. Looking for your guidance.

If the third primal right-hand-side is 5 (as written) the third dual objective coefficient is wrong. If the coefficient of x2 on the left of the third primal constraint is 12 (as written) the coefficient of w3 in the second dual constraint is wrong.

After deciding on correct statements of both the primal and dual problems, use the known properties of the relation between the primal and dual solution at optimality. For example, if a primal variable ##x_j## is ##> 0##, what can you say about the ##j##th dual constraint, etc.?