University:
Whitman College
Course:
MATH-339 | Operations Research
Academic year:

2022
Views:

325

Pages:

24
Author:

krugerdaggtx

Motivating Example Example max 6x1 +5x2 s.t. x1 +x2 ≤ 5 3x1 +2x2 ≤ 12 with x1 , x2 ≥ 0. Find an upper bound to the maximum. Using constraint 2 (multiply by 3): 6x1 + 5x2 ≤ 9x1 + 6x2 ≤ 36 Using constraint 1 (multiply by 6): 6x1 + 5x2 ≤ 6x1 + 6x2 ≤ 30 October 21, 2015 1 / 24 Motivating Example Example max 6x1 +5x2 s.t. x1 +x2 ≤ 5 3x1 +2x2 ≤ 12 with x1 , x2 ≥ 0. Find an upper bound to the maximum. We could take a linear combination of the constraints: x1 + x2 ≤ 5 + 2(3x1 + 2x2 ) ≤ 12 · 2 7x1 + 5x2 ≤ 29 October 21, 2015 2 / 24 Motivating Example More generally: y1 (x1 +x2 ) ≤ 5y1 +y2 (3x1 +2x2 ) ≤ 12y2 (y1 + 3y2 )x1 +(y1 + 2y2 )x2 ≤ 5y1 + 12y2 This gives us The Dual: min 5y1 + 12y2 s.t. y1 + 3y2 ≥ 6 y1 + 2y2 ≥ 5 with y1 , y2 ≥ 0. October 21, 2015 3 / 24 The Primal and the Dual We showed that the primal, dual are: max 6x1 +5x2 s.t. x1 +x2 ≤ 5 3x1 +2x2 ≤ 12 ⇐⇒ min 5y1 + 12y2 s.t. y1 + 3y2 ≥ 6 y1 + 2y2 ≥ 5 So what would it be for the “normal” max problem: max z = cT x st Ax ≤ b x≥0 ⇐⇒ min w = bT y st AT y ≥ c y≥0 Note: b may have negative values in this construction. October 21, 2015 4 / 24 The Primal and the Dual max z = cT x st Ax ≤ b x≥0 ⇐⇒ min w = bT y st AT y ≥ c y≥0 Notes: Every primal has a dual. A maximum becomes a minimum (dual of dual is primal). Obj Func Coeffs in primal converted to RHS of constraints in dual. RHS of Constraints in primal converted to Obj Func Coeffs in dual. October 21, 2015 5 / 24 A Detailed Construction An example with non-“normal” issues. Find the dual for: min 8x1 + 5x2 + 4x3 s.t. 4x1 + 2x2 + 8x3 7x1 + 5x2 + 6x3 8x1 + 5x2 + 4x3 3x1 + 7x2 + 9x3 = 12 ≥9 ≤ 10 ≥7 x1 ≥ 0, x2 URS, x3 ≤ 0 We’ll put this system into “normal form”: Change the min to a max. Multiply Constraints 2 and 4 by −1. Change = into inequalities. Find substitutions for x2 , x3 . October 21, 2015 6 / 24 A Detailed Construction First three issues: max s.t. −8x1 −5x2 −4x3 4x1 −4x1 −7x1 8x1 −3x1 +2x2 −2x2 −5x2 +5x2 −7x2 +8x3 −8x3 −6x3 +4x3 −9x3 ≤ 12 ≤ −12 ≤ −9 ≤ 10 ≤ −7 x1 ≥ 0, x2 URS, x3 ≤ 0 Last issue: Let x2 = x4 − x5 and x3 = −x6 (with all these new vars non-neg) October 21, 2015 7 / 24 A Detailed Construction We now have a “normal” primal: max s.t. −8x1 −5x4 +5x5 +4x6 4x1 −4x1 −7x1 8x1 −3x1 +2x4 −2x4 −5x4 +5x4 −7x4 −2x5 +2x5 +5x5 −5x5 +7x5 −8x6 +8x6 +6x6 −4x6 +9x6 ≤ 12 ≤ −12 ≤ −9 ≤ 10 ≤ −7 x1 , x4 , x5 , x6 ≥ 0 October 21, 2015 8 / 24 A Detailed Construction From which we get the dual. Let p1 , . . . , p5 be the new vars. Using the “normal” primal to dual conversion, we get the following for the dual: min w = st 12p1 −12p2 4p1 −4p2 2p1 −2p2 −2p1 +2p2 −8p1 +8p2 −9p3 +10p4 −7p3 +8p4 −5p3 +5p4 +5p3 −5p4 +6p3 −4p4 −7p5 −3p5 −7p5 +7p5 +9p5 ≥ −8 ≥ −5 ≥5 ≥4 with p1 , p2 , p3 , p4 , p5 ≥ 0 Constraints 2 and 3 can be combined. Variables p1 , p2 always appear together as p1 − p2 . Multiply constraint 1 by −1 to get a positive b: October 21, 2015 9 / 24 A Detailed Construction Let p6 = p1 − p2 . We now have: min w = 12p6 −4p6 −2p6 −8p6 −9p3 +7p3 +5p3 +6p3 +10p4 −8p4 −5p4 −4p4 −7p5 +3p5 ≤ 8 +7p5 = 5 +9p5 ≥ 4 with p6 URS, and p3 , p4 , p5 ≥ 0. Since p6 and p4 only appear in the constraints with a negative coefficient, convert them to negative constraints. Here, we’ll convert to x: Let x1 = −p6 , x2 = p3 , x3 = −p4 and x4 = p5 . October 21, 2015 10 / 24 A Detailed Construction The dual is (converting to a MAX): max z = 12x1 + 9x2 + 10x3 + 7x4 s.t. 4x1 + 7x2 + 8x3 + 3x4 ≤ 8 2x1 + 5x2 + 5x3 + 7x4 = 5 8x1 + 6x2 + 4x3 + 9x4 ≥ 4 x1 URS, x2 ≥ 0, x3 ≤ 0, x4 ≥ 0 October 21, 2015 11 / 24 A Detailed Construction Summary of the Conversion: max z = s.t. 12x1 + 9x2 + 10x3 + 7x4 4x1 + 7x2 + 8x3 + 3x4 ≤ 8 2x1 + 5x2 + 5x3 + 7x4 = 5 8x1 + 6x2 + 4x3 + 9x4 ≥ 4 x1 URS, x2 ≥ 0, x3 ≤ 0, x4 ≥ 0 min w = 8y1 + 5y2 + 4y3 s.t. 4y1 + 2y2 + 8y3 7y1 + 5y2 + 6y3 8y1 + 5y2 + 4y3 3y1 + 7y2 + 9y3 = 12 ≥9 ≤ 10 ≥7 y1 ≥ 0, y2 URS, y3 ≤ 0 October 21, 2015 12 / 24 Summary Summary: Primal: max ≤ constraint ≥ constraint Equality constraint ≥ 0 variable ≤ 0 variable URS variable Dual: min ≥ 0 variable ≤ 0 variable URS variable ≥ constraint ≤ constraint Equality constraint normal normal normal October 21, 2015 13 / 24 Use a Table and the Summary Using a table (*=Not “normal”) min w = 8y1 + 5y2 + 4y3 s.t. 4y1 + 2y2 + 8y3 7y1 + 5y2 + 6y3 8y1 + 5y2 + 4y3 3y1 + 7y2 + 9y3 = 12 ≥9 ≤ 10 ≥7 y1 ≥ 0, y2 URS, y3 ≤ 0 x1 ? x2 ? x3 ? x4 ? y1 ≥ 0 4 7 8 3 ?8 y2 urs(∗) 2 5 5 7 ?5 y3 ≤ 0(∗) 8 6 4 9 ?4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 14 / 24 Use a Table and the Summary Using a table x1 ? x2 ? x3 ? x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 ?5 y3 ≤ 0(∗) 8 6 4 9 ?4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 15 / 24 Use a Table and the Summary Using a table x1 ? x2 ? x3 ? x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ?4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 16 / 24 Use a Table and the Summary Using a table x1 ? x2 ? x3 ? x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 17 / 24 Use a Table and the Summary Using a table x1 URS x2 ? x3 ? x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 18 / 24 Use a Table and the Summary Using a table x1 URS x2 ≥ 0 x3 ? x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 19 / 24 Use a Table and the Summary Using a table x1 URS x2 ≥ 0 x3 ≤ 0 x4 ? y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 20 / 24 Use a Table and the Summary Using a table x1 URS x2 ≥ 0 x3 ≤ 0 x4 ≥ 0 y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 October 21, 2015 21 / 24 Use a Table and the Summary Using a table- Here are Primal and Dual x1 URS x2 ≥ 0 x3 ≤ 0 x4 ≥ 0 y1 ≥ 0 4 7 8 3 ≤8 y2 urs(∗) 2 5 5 7 =5 y3 ≤ 0(∗) 8 6 4 9 ≥4 = 12(∗) ≥ 9 ≤ 10(∗) ≥ 7 max z = s.t. 12x1 + 9x2 + 10x3 + 7x4 4x1 + 7x2 + 8x3 + 3x4 ≤ 8 2x1 + 5x2 + 5x3 + 7x4 = 5 8x1 + 6x2 + 4x3 + 9x4 ≥ 4 x1 URS, x2 ≥ 0, x3 ≤ 0, x4 ≥ 0 min w = 8y1 + 5y2 + 4y3 s.t. 4y1 + 2y2 + 8y3 7y1 + 5y2 + 6y3 8y1 + 5y2 + 4y3 3y1 + 7y2 + 9y3 = 12 ≥9 ≤ 10 ≥7 y1 ≥ 0, y2 URS, y3 ≤ 0 October 21, 2015 22 / 24 Example 2 Example 2 Use a table to write the dual: max z = 2x1 + x2 st x1 + x2 = 2 2x1 − x2 ≥ 3 x1 − x2 ≤ 1 x1 ≥ 0, x2 urs x1 ≥ 0 x2 urs(∗) y1 ? 1 1 = 2(∗) y2 ? 2 −1 ≥ 3(∗) y3 ? 1 −1 ≤1 ?2 ?1 y1 urs y2 ≤ 0 y3 ≥ 0 x1 ≥ 0 x2 urs(∗) 1 1 = 2(∗) 2 −1 ≥ 3(∗) 1 −1 ≤1 ≥2 =1 October 21, 2015 23 / 24 Example 2 Use a table to write the dual: max z = 2x1 + x2 st x1 + x2 = 2 2x1 − x2 ≥ 3 x1 − x2 ≤ 1 x1 ≥ 0, x2 urs y1 urs y2 ≤ 0 y3 ≥ 0 x1 ≥ 0 x2 urs(∗) 1 1 = 2(∗) 2 −1 ≥ 3(∗) 1 −1 ≤1 ≥2 =1 min w = 2y1 + 3y2 + y3 st y1 + 2y2 + y3 ≥ 2 y1 − y2 − y3 = 1 y1 urs, y2 ≤ 0, y3 ≥ 0 October 21, 2015 24 / 24

Math 339 Handouts

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock