Study Guide
Math 339 Beamer Handout
-
University:
Whitman College -
Course:
MATH-339 | Operations Research Academic year:
2021
-
Views:
226
Pages:
32
Author:
Aditya Porter
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
March 7, 2022
1 / 32 Motivating Example
Example
max 6x1 +5x2
s.t. x1 +x2 ≤ 5
3x1 +2x2 ≤ 12
How about a linear combination?
y1 (x1
+x2 ) ≤ 5y1
+y2 (3x1
+2x2 ) ≤ 12y2
(y1 + 3y2 )x1 +(y1 + 2y2 )x2 ≤ 5y1 + 12y2
What needs to be true for this to give an upper bound? (The Dual)
min 5y1 + 12y2
s.t. y1 + 3y2 ≥ 6
y1 + 2y2 ≥ 5
with y1 , y2 ≥ 0.
March 7, 2022
2 / 32 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
Generalized, we have a “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.
March 7, 2022
3 / 32 The Primal and the Dual
max z = cT x
st Ax ≤ b
x≥0
⇐⇒
min w = bT y
st AT y ≥ c
y≥0
How many constraints are in the dual?
Same as number of variables in primal.
How many variables are in the dual?
Same as number of constraints in primal.
March 7, 2022
4 / 32 The Primal and the Dual
Every primal has a dual.
A maximum becomes a minimum (dual of dual is primal).
Variable in primal → constraint in dual.
Constraint in primal → variable in dual.
The RHS of primal → obj function coeffs in dual.
March 7, 2022
5 / 32 The Primal and the Dual
Self test: Create the Dual
max 2x1 +3x2 −x3
s.t. x1 +2x2 +x3 ≤ 1
x1 −x2 −x3 ≤ 5
⇐⇒
min y1 + 5y2
s.t. y1 + y2 ≥ 2
2y1 − y2 ≥ 3
y1 − y2 ≥ −1
March 7, 2022
6 / 32 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 .
March 7, 2022
7 / 32 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)
March 7, 2022
8 / 32 A Detailed Construction
Now a summary of the equations using a table:
x1 ≥ 0 x4 ≥ 0 x5 ≥ 0 x6 ≥ 0
4
2
−2
−8 ≤ 12
−4
−2
2
8 ≤ −12
−7
−5
5
6 ≤ −9
8
5
−5
−4 ≤ −12
−3
−7
7
9 ≤ −7
≥ −8 ≥ −5
≥5
≥4
This is standard form. This table is given in the form:
x
A b
c
⇒
min w = bT p
st AT p ≥ c
p≥0
Note that p has 5 variables (from the 5 constraints).
March 7, 2022
9 / 32 A Detailed Construction
Let p1 , . . . , p5 be the new vars; we have 4 constraints (we had 4 variables
in the primal).
min w = 12p1 − 12p2 − 9p3 + 10p4 − 7p5
4p1 − 4p2 − 7p3 + 8p4 − 3p5 ≥ −8
2p1 − 2p2 − 5p3 + 5p4 − 7p5 ≥ −5
−2p1 + 2p2 + 5p3 − 5p4 + 7p5 ≥ 5
−8p1 + 8p2 + 6p3 − 4p4 + 9p5 ≥ 4
p1 , p2 , p3 , p4 , p5 ≥ 0
In the next frame, we’ll start simplifying this system. Look to see what we
might do first.
March 7, 2022
10 / 32 A Detailed Construction
Variables p1 , p2 can be combined: p6 = p1 − p2 (now is URS).
Constraints 2 and 3 can be combined into equality.
Multiply first constraint by −1 to get positive b (next page).
min w = 12(p1 − p2 ) − 9p3 + 10p4 − 7p5
4(p1 − p2 ) − 7p3 + 8p4 − 3p5 ≥ −8
2(p1 − p2 ) − 5p3 + 5p4 − 7p5 ≥ −5
−2(p1 − p2 ) + 5p3 − 5p4 + 7p5 ≥ 5
−8(p1 − p2 ) + 6p3 − 4p4 + 9p5 ≥ 4
p1 , p2 , p3 , p4 , p5 ≥ 0
March 7, 2022
11 / 32 A Detailed Construction
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.
Let p7 = −p6 and p8 = −p4
p7 is URS, p8 ≤ 0, p3 , p5 ≥ 0.
March 7, 2022
12 / 32 A Detailed Construction
Changing notation slightly:
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
March 7, 2022
13 / 32 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
March 7, 2022
14 / 32 Use a Table and the Summary
Primal-Dual Table
max z = cT x
st Ax ≤ b
x≥0
⇐⇒
min w = bT y
st AT y ≥ c
y≥0
Main concerns:
If the inequalities in the primal are not normal, what happens in the dual?
If the variables are not normal in the primal, what happens in the dual?
(and vice-versa)
x1 ? x2 ? · · ·
y1 ?
y2 ?
..
.
xn ?
b1 ?
b2 ?
..
.
A
bm ?
ym ?
c1 ? c2 ? · · ·
cn ?
March 7, 2022
15 / 32 Use a Table and the Summary
Using a table
Starting problem:
min w = 8y1 + 5y2 + 4y3
s.t. 4y1 + 2y2 + 8y3
7y1 + 5y2 + 6y3
8y1 + 5y2 + 4y3
3y1 + 7y2 + 9y3
= 12
≥ 9 with y1 ≥ 0, y2 URS, y3 ≤ 0
≤ 10
≥7
(Asterisks mark things that are different than “normal”)
x1 ?
x2 ?
x3 ?
x4 ?
y1 ≥ 0
4
7
8
3 ?8
2
5
5
7 ?5
y2 urs(∗)
y3 ≤ 0(∗)
8
6
4
9 ?4
= 12(∗) ≥ 9 ≤ 10(∗) ≥ 7
March 7, 2022
16 / 32 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
March 7, 2022
17 / 32 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
March 7, 2022
18 / 32 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
March 7, 2022
19 / 32 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
March 7, 2022
20 / 32 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
March 7, 2022
21 / 32 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
March 7, 2022
22 / 32 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
March 7, 2022
23 / 32 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
March 7, 2022
24 / 32 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
March 7, 2022
25 / 32 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
March 7, 2022
26 / 32 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
March 7, 2022
27 / 32 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
March 7, 2022
28 / 32 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
March 7, 2022
29 / 32 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
March 7, 2022
30 / 32 Example 3
Last Example
Find the dual associated with the following primal:
max z = 3x1 + x2
st 2x1 + x2 ≤ 4
3x1 + 2x2 ≥ 6
4x1 + 2x2 = 7
x1 , x2 ≥ 0
March 7, 2022
31 / 32 Example 3
Solution:
x1 ≥ 0 x2 ≥ 0
y1 ≥ 0
2
1
≤4
y2 ≤ 0
3
2
≥ 6(∗)
y3 URS
4
2
= 7(∗)
≥3
≥1
max z = 4y1 + 6y2 + 7y3
st 2y1 + 3y2 + 4y3 ≥ 3
y1 + 2y2 + 2y3 ≥ 1
y1 ≥ 0, y2 ≤ 0, y3 URS
March 7, 2022
32 / 32
Related Documents
- Questions and Answers #1 Exponential Models
- Questions and Answers #1 Composite Functions
- Calculus II Exam 3: Review
- Questions and Answers #1 Complex Variables
- Question and Answers #93 Derivatives
- Questions and Answers #1 Alternate Coordinate Systems
- Questions and Answers #1 Algebra Foundations
- Questions and Answers #1 Integrals
- Questions and Answers #1 Equations
- Questions and Answers #1 Equations and Inequalities
- Questions and Answers #1 Applications of Integrals
- Questions and Answers #1 Antiderivatives
- Relations and functions
- Question and Answers #95 Derivatives
- Question and Answers #90 Derivatives
- Questions and Answers #9 Laplace Transform
- QA #1 Series
- QA #2 Series
- QA #3 Series
- Questions and Answers #7 Functions
Math 339 Beamer Handout
of 32
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document