Courses

# Linear Programming Notes | EduRev

## : Linear Programming Notes | EduRev

``` Page 1

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Linear Programming
2
Linear Programming
Significance.
¦ Quintessential tool for optimal allocation of scarce resources,
among a number of competing activities.
¦ Powerful model generalizes many classic problems:
– shortest path, max flow, multicommodity flow, MST, matching,
2-person zero sum games
¦ Ranked among most important scientific advances of 20
th
century.
– accounts for a major proportion of all scientific computation
¦ Helps find "good" solutions to NP-hard optimization problems.
– optimal solutions (branch-and-cut)
– provably good solutions (randomized rounding)
3
Brewery Problem
Small brewery produces ale and beer.
¦ Production limited by scarce resources:  corn, hops, barley malt.
¦ Recipes for ale and beer require different proportions of resources.
How can brewer maximize profits?
¦ Devote all resources to beer:  32 barrels of beer   \$736.
¦ Devote all resources to ale:  34 barrels of ale  \$442.
¦ 7½ barrels of ale, 29½ barrels of beer  \$776.
¦ 12 barrels of ale, 28 barrels of beer  \$800.
Beverage
Corn
(pounds)
Malt
(pounds)
Hops
(ounces)
Beer 15 20 4
Ale 5 35 4
Profit
(\$)
23
13
Quantity 480 1190 160
4
Brewery Problem
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
Page 2

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Linear Programming
2
Linear Programming
Significance.
¦ Quintessential tool for optimal allocation of scarce resources,
among a number of competing activities.
¦ Powerful model generalizes many classic problems:
– shortest path, max flow, multicommodity flow, MST, matching,
2-person zero sum games
¦ Ranked among most important scientific advances of 20
th
century.
– accounts for a major proportion of all scientific computation
¦ Helps find "good" solutions to NP-hard optimization problems.
– optimal solutions (branch-and-cut)
– provably good solutions (randomized rounding)
3
Brewery Problem
Small brewery produces ale and beer.
¦ Production limited by scarce resources:  corn, hops, barley malt.
¦ Recipes for ale and beer require different proportions of resources.
How can brewer maximize profits?
¦ Devote all resources to beer:  32 barrels of beer   \$736.
¦ Devote all resources to ale:  34 barrels of ale  \$442.
¦ 7½ barrels of ale, 29½ barrels of beer  \$776.
¦ 12 barrels of ale, 28 barrels of beer  \$800.
Beverage
Corn
(pounds)
Malt
(pounds)
Hops
(ounces)
Beer 15 20 4
Ale 5 35 4
Profit
(\$)
23
13
Quantity 480 1190 160
4
Brewery Problem
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
5
Brewery Problem:  Feasible Region
Ale
Beer
(34, 0)
(0, 32)
Corn
5A + 15B £ 480
(12, 28)
(26, 14)
(0, 0)
Hops
4A + 4B £ 160
Malt
35A + 20B £ 1190
6
Brewery Problem:  Objective Function
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
13A + 23B = 800
13A + 23B = 1600
13A + 23B = 442
(26, 14)
Profit
(0, 0)
7
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
(26, 14)
(0, 0)
Extreme points
Brewery Problem:  Geometry
Brewery problem observation. Regardless of coefficients of linear
objective function, there exists an optimal solution that is an extreme
point.
8
Linear Programming
LP "standard" form.
¦ Input data: rational numbers c
j
, b
i
, a
ij
.
¦ Maximize linear objective function.
¦ Subject to linear inequalities.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
0
t. s.
max (P)
‡ £ •
x
b Ax
x c
Page 3

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Linear Programming
2
Linear Programming
Significance.
¦ Quintessential tool for optimal allocation of scarce resources,
among a number of competing activities.
¦ Powerful model generalizes many classic problems:
– shortest path, max flow, multicommodity flow, MST, matching,
2-person zero sum games
¦ Ranked among most important scientific advances of 20
th
century.
– accounts for a major proportion of all scientific computation
¦ Helps find "good" solutions to NP-hard optimization problems.
– optimal solutions (branch-and-cut)
– provably good solutions (randomized rounding)
3
Brewery Problem
Small brewery produces ale and beer.
¦ Production limited by scarce resources:  corn, hops, barley malt.
¦ Recipes for ale and beer require different proportions of resources.
How can brewer maximize profits?
¦ Devote all resources to beer:  32 barrels of beer   \$736.
¦ Devote all resources to ale:  34 barrels of ale  \$442.
¦ 7½ barrels of ale, 29½ barrels of beer  \$776.
¦ 12 barrels of ale, 28 barrels of beer  \$800.
Beverage
Corn
(pounds)
Malt
(pounds)
Hops
(ounces)
Beer 15 20 4
Ale 5 35 4
Profit
(\$)
23
13
Quantity 480 1190 160
4
Brewery Problem
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
5
Brewery Problem:  Feasible Region
Ale
Beer
(34, 0)
(0, 32)
Corn
5A + 15B £ 480
(12, 28)
(26, 14)
(0, 0)
Hops
4A + 4B £ 160
Malt
35A + 20B £ 1190
6
Brewery Problem:  Objective Function
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
13A + 23B = 800
13A + 23B = 1600
13A + 23B = 442
(26, 14)
Profit
(0, 0)
7
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
(26, 14)
(0, 0)
Extreme points
Brewery Problem:  Geometry
Brewery problem observation. Regardless of coefficients of linear
objective function, there exists an optimal solution that is an extreme
point.
8
Linear Programming
LP "standard" form.
¦ Input data: rational numbers c
j
, b
i
, a
ij
.
¦ Maximize linear objective function.
¦ Subject to linear inequalities.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
0
t. s.
max (P)
‡ £ •
x
b Ax
x c
9
LP:  Geometry
Geometry.
¦ Forms an n-dimensional
polyhedron.
¦ Convex: if y and z are feasible solutions, then so is ½y + ½z.
¦ Extreme point: feasible solution x that can't be written as ½y + ½z
for any two distinct feasible solutions y and z.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
z
y
z
y
Convex Not convex
Extreme
points
10
LP:  Geometry
Extreme Point Theorem. If there exists an optimal solution to
standard form LP (P), then there exists one that is an extreme point.
¦ Only need to consider finitely many possible solutions.
Greed.  Local optima are
global optima.
11
LP:  Algorithms
Simplex. (Dantzig 1947)
¦ Developed shortly after WWII in response to logistical problems:
used for 1948 Berlin airlift.
¦ Practical solution method  that moves from one extreme point to a
neighboring extreme point.
¦ Finite (exponential) complexity, but no polynomial implementation
known.
12
LP:  Polynomial Algorithms
Ellipsoid.  (Khachian 1979, 1980)
¦ Solvable in polynomial time:  O(n
4
L) bit operations.
– n = # variables
– L = # bits in input
¦ Theoretical tour de force.
¦ Not remotely practical.
Karmarkar’s algorithm.  (Karmarkar 1984)
¦ O(n
3.5
L).
¦ Polynomial and reasonably efficient
implementations possible.
Interior point algorithms.
¦ O(n
3
L).
¦ Competitive with simplex!
– will likely dominate on large problems soon
¦ Extends to even more general problems.
Page 4

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Linear Programming
2
Linear Programming
Significance.
¦ Quintessential tool for optimal allocation of scarce resources,
among a number of competing activities.
¦ Powerful model generalizes many classic problems:
– shortest path, max flow, multicommodity flow, MST, matching,
2-person zero sum games
¦ Ranked among most important scientific advances of 20
th
century.
– accounts for a major proportion of all scientific computation
¦ Helps find "good" solutions to NP-hard optimization problems.
– optimal solutions (branch-and-cut)
– provably good solutions (randomized rounding)
3
Brewery Problem
Small brewery produces ale and beer.
¦ Production limited by scarce resources:  corn, hops, barley malt.
¦ Recipes for ale and beer require different proportions of resources.
How can brewer maximize profits?
¦ Devote all resources to beer:  32 barrels of beer   \$736.
¦ Devote all resources to ale:  34 barrels of ale  \$442.
¦ 7½ barrels of ale, 29½ barrels of beer  \$776.
¦ 12 barrels of ale, 28 barrels of beer  \$800.
Beverage
Corn
(pounds)
Malt
(pounds)
Hops
(ounces)
Beer 15 20 4
Ale 5 35 4
Profit
(\$)
23
13
Quantity 480 1190 160
4
Brewery Problem
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
5
Brewery Problem:  Feasible Region
Ale
Beer
(34, 0)
(0, 32)
Corn
5A + 15B £ 480
(12, 28)
(26, 14)
(0, 0)
Hops
4A + 4B £ 160
Malt
35A + 20B £ 1190
6
Brewery Problem:  Objective Function
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
13A + 23B = 800
13A + 23B = 1600
13A + 23B = 442
(26, 14)
Profit
(0, 0)
7
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
(26, 14)
(0, 0)
Extreme points
Brewery Problem:  Geometry
Brewery problem observation. Regardless of coefficients of linear
objective function, there exists an optimal solution that is an extreme
point.
8
Linear Programming
LP "standard" form.
¦ Input data: rational numbers c
j
, b
i
, a
ij
.
¦ Maximize linear objective function.
¦ Subject to linear inequalities.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
0
t. s.
max (P)
‡ £ •
x
b Ax
x c
9
LP:  Geometry
Geometry.
¦ Forms an n-dimensional
polyhedron.
¦ Convex: if y and z are feasible solutions, then so is ½y + ½z.
¦ Extreme point: feasible solution x that can't be written as ½y + ½z
for any two distinct feasible solutions y and z.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
z
y
z
y
Convex Not convex
Extreme
points
10
LP:  Geometry
Extreme Point Theorem. If there exists an optimal solution to
standard form LP (P), then there exists one that is an extreme point.
¦ Only need to consider finitely many possible solutions.
Greed.  Local optima are
global optima.
11
LP:  Algorithms
Simplex. (Dantzig 1947)
¦ Developed shortly after WWII in response to logistical problems:
used for 1948 Berlin airlift.
¦ Practical solution method  that moves from one extreme point to a
neighboring extreme point.
¦ Finite (exponential) complexity, but no polynomial implementation
known.
12
LP:  Polynomial Algorithms
Ellipsoid.  (Khachian 1979, 1980)
¦ Solvable in polynomial time:  O(n
4
L) bit operations.
– n = # variables
– L = # bits in input
¦ Theoretical tour de force.
¦ Not remotely practical.
Karmarkar’s algorithm.  (Karmarkar 1984)
¦ O(n
3.5
L).
¦ Polynomial and reasonably efficient
implementations possible.
Interior point algorithms.
¦ O(n
3
L).
¦ Competitive with simplex!
– will likely dominate on large problems soon
¦ Extends to even more general problems.
13
LP Duality
Primal problem.
Find a lower bound on optimal value.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 0, 1, 0)  z*  ‡ 5.
¦ (x
1
, x
2
, x
3
, x
4
) = (2, 1, 1, 1/3)  z*  ‡ 15.
¦ (x
1
, x
2
, x
3
, x
4
) = (3, 0, 2, 0)  z*  ‡ 22.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 14, 0, 5)  z*  ‡ 29.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
14
LP Duality
Primal problem.
Find an upper bound on optimal value.
¦ Multiply 2
nd
inequality by 2:  10x
1
+ 2x
2
+ 6x
3
+ 16x
4
£ 110.
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 10x
1
+ 2x
2
+ 6x
3
+ 16x
4
£ 110.
¦ Adding 2
nd
and 3
rd
inequalities:  4x
1
+ 3x
2
+ 6x
3
+ 3x
4
£ 58.
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 4x
1
+ 3x
2
+ 6x
3
+ 3x
4
£ 58.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
15
LP Duality
Primal problem.
Find an upper bound on optimal value.
¦ Adding 11 times 1
st
inequality to 6 times 3
rd
inequality:
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 5x
1
+ x
2
+ 7x
3
+ 3x
4
£ 29.
Recall.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 14, 0, 5)  z*  ‡ 29.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
16
LP Duality
Primal problem.
General idea:  add linear combination (y
1
, y
2
, y
3
) of the constraints.
Dual problem.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
3 2 1 4 3 2 1 3 3 2 1
2 3 2 1 1 3 2 1
3 55 ) 5 8 3 ( ) 3 3 (
) 2 ( ) 5 (
y y y x y y y x y y y
x y y y x y y y
+ + £ - + + + + - + + + - + - +
0 , ,
3 5 8 3
5 3 3
1 2
4 5 t. s.
3 55 min
3 2 1
3 2 1
3 2 1
3 2 1
3 2 1
3 2 1
‡ ‡ - +
‡ + + - ‡ + + - ‡ - +
+ +
y y y
y y y
y y y
y y y
y y y
y y y
Page 5

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Linear Programming
2
Linear Programming
Significance.
¦ Quintessential tool for optimal allocation of scarce resources,
among a number of competing activities.
¦ Powerful model generalizes many classic problems:
– shortest path, max flow, multicommodity flow, MST, matching,
2-person zero sum games
¦ Ranked among most important scientific advances of 20
th
century.
– accounts for a major proportion of all scientific computation
¦ Helps find "good" solutions to NP-hard optimization problems.
– optimal solutions (branch-and-cut)
– provably good solutions (randomized rounding)
3
Brewery Problem
Small brewery produces ale and beer.
¦ Production limited by scarce resources:  corn, hops, barley malt.
¦ Recipes for ale and beer require different proportions of resources.
How can brewer maximize profits?
¦ Devote all resources to beer:  32 barrels of beer   \$736.
¦ Devote all resources to ale:  34 barrels of ale  \$442.
¦ 7½ barrels of ale, 29½ barrels of beer  \$776.
¦ 12 barrels of ale, 28 barrels of beer  \$800.
Beverage
Corn
(pounds)
Malt
(pounds)
Hops
(ounces)
Beer 15 20 4
Ale 5 35 4
Profit
(\$)
23
13
Quantity 480 1190 160
4
Brewery Problem
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
5
Brewery Problem:  Feasible Region
Ale
Beer
(34, 0)
(0, 32)
Corn
5A + 15B £ 480
(12, 28)
(26, 14)
(0, 0)
Hops
4A + 4B £ 160
Malt
35A + 20B £ 1190
6
Brewery Problem:  Objective Function
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
13A + 23B = 800
13A + 23B = 1600
13A + 23B = 442
(26, 14)
Profit
(0, 0)
7
Ale
Beer
(34, 0)
(0, 32)
(12, 28)
(26, 14)
(0, 0)
Extreme points
Brewery Problem:  Geometry
Brewery problem observation. Regardless of coefficients of linear
objective function, there exists an optimal solution that is an extreme
point.
8
Linear Programming
LP "standard" form.
¦ Input data: rational numbers c
j
, b
i
, a
ij
.
¦ Maximize linear objective function.
¦ Subject to linear inequalities.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
0
t. s.
max (P)
‡ £ •
x
b Ax
x c
9
LP:  Geometry
Geometry.
¦ Forms an n-dimensional
polyhedron.
¦ Convex: if y and z are feasible solutions, then so is ½y + ½z.
¦ Extreme point: feasible solution x that can't be written as ½y + ½z
for any two distinct feasible solutions y and z.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
z
y
z
y
Convex Not convex
Extreme
points
10
LP:  Geometry
Extreme Point Theorem. If there exists an optimal solution to
standard form LP (P), then there exists one that is an extreme point.
¦ Only need to consider finitely many possible solutions.
Greed.  Local optima are
global optima.
11
LP:  Algorithms
Simplex. (Dantzig 1947)
¦ Developed shortly after WWII in response to logistical problems:
used for 1948 Berlin airlift.
¦ Practical solution method  that moves from one extreme point to a
neighboring extreme point.
¦ Finite (exponential) complexity, but no polynomial implementation
known.
12
LP:  Polynomial Algorithms
Ellipsoid.  (Khachian 1979, 1980)
¦ Solvable in polynomial time:  O(n
4
L) bit operations.
– n = # variables
– L = # bits in input
¦ Theoretical tour de force.
¦ Not remotely practical.
Karmarkar’s algorithm.  (Karmarkar 1984)
¦ O(n
3.5
L).
¦ Polynomial and reasonably efficient
implementations possible.
Interior point algorithms.
¦ O(n
3
L).
¦ Competitive with simplex!
– will likely dominate on large problems soon
¦ Extends to even more general problems.
13
LP Duality
Primal problem.
Find a lower bound on optimal value.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 0, 1, 0)  z*  ‡ 5.
¦ (x
1
, x
2
, x
3
, x
4
) = (2, 1, 1, 1/3)  z*  ‡ 15.
¦ (x
1
, x
2
, x
3
, x
4
) = (3, 0, 2, 0)  z*  ‡ 22.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 14, 0, 5)  z*  ‡ 29.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
14
LP Duality
Primal problem.
Find an upper bound on optimal value.
¦ Multiply 2
nd
inequality by 2:  10x
1
+ 2x
2
+ 6x
3
+ 16x
4
£ 110.
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 10x
1
+ 2x
2
+ 6x
3
+ 16x
4
£ 110.
¦ Adding 2
nd
and 3
rd
inequalities:  4x
1
+ 3x
2
+ 6x
3
+ 3x
4
£ 58.
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 4x
1
+ 3x
2
+ 6x
3
+ 3x
4
£ 58.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
15
LP Duality
Primal problem.
Find an upper bound on optimal value.
¦ Adding 11 times 1
st
inequality to 6 times 3
rd
inequality:
z*   = 4x
1
+ x
2
+ 5x
3
+ 3x
4
£ 5x
1
+ x
2
+ 7x
3
+ 3x
4
£ 29.
Recall.
¦ (x
1
, x
2
, x
3
, x
4
) = (0, 14, 0, 5)  z*  ‡ 29.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
16
LP Duality
Primal problem.
General idea:  add linear combination (y
1
, y
2
, y
3
) of the constraints.
Dual problem.
0 , , ,
3 5 3 2
55 8 3 5
1 3 t. s.
3 5 4 max
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
‡ £ - + + - £ + + +
£ + - - + + +
x x x x
x x x x
x x x x
x x x x
x x x x
3 2 1 4 3 2 1 3 3 2 1
2 3 2 1 1 3 2 1
3 55 ) 5 8 3 ( ) 3 3 (
) 2 ( ) 5 (
y y y x y y y x y y y
x y y y x y y y
+ + £ - + + + + - + + + - + - +
0 , ,
3 5 8 3
5 3 3
1 2
4 5 t. s.
3 55 min
3 2 1
3 2 1
3 2 1
3 2 1
3 2 1
3 2 1
‡ ‡ - +
‡ + + - ‡ + + - ‡ - +
+ +
y y y
y y y
y y y
y y y
y y y
y y y
17
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
m i y
n j c y a
y b
i
j
m
i
i ij
m
i
i i
£ £ ‡ £ £ ‡   =
=
1 0
1 t. s.
min (D)
1
1
LP Duality
Primal and dual linear programs:  given rational numbers a
ij
, b
i
,c
j
, find
values x
i
, y
j
that optimize (P) and (D).
Duality Theorem (Gale-Kuhn-Tucker 1951, Dantzig-von Neumann 1947).
If (P) and (D) are nonempty then max = min.
¦ Dual solution provides certificate of optimality   decision version  ? NP ? co-NP.
¦ Special case:  max-flow min-cut theorem.
¦ Sensitivity analysis.
18
LP Duality:  Economic Interpretation
Brewer’s problem: find optimal mix of beer and ale to maximize profits.
Entrepreneur’s problem: Buy individual resources from brewer at
minimum cost.
¦ C, H, M = unit price for corn, hops, malt.
¦ Brewer won’t agree to sell resources if 5C + 4H + 35M  <  13.
0 ,
1190 20 35
160 4 4
480 15 5 t. s.
23 13 max (P)
‡ £ +
£ +
£ +
+
B A
B A
B A
B A
B A
0 , ,
23 20 4 15
13 35 4 5 t. s.
1190 160 480 min (D)
‡ ‡ + +
‡ + +
+ +
M H C
M H C
M H C
M H C
A* = 12
B* = 28
OPT = 800
C* = 1
H* = 2
M* = 0
OPT = 800
19
LP Duality:  Economic Interpretation
Sensitivity analysis.
¦ How much should brewer be willing to pay (marginal price) for
additional supplies of scarce resources?
! corn \$1, hops \$2, malt \$0.
¦ Suppose a new product "light beer" is proposed. It requires 2 corn,
5 hops, 24 malt. How much profit must be obtained from light beer
to justify diverting resources from production of beer and ale?
! At least 2 (\$1) + 5 (\$2) + 24 (0\$) =  \$12 / barrel.
20
Standard Form
Standard form.
Easy to handle variants.
¦ x + 2y - 3z  ‡ 17  -x - 2y + 3z  £ -17.
¦ x + 2y - 3z  =  17  x + 2y - 3z  £ 17,   -x - 2y + 3z  £ -17.
¦ min x + 2y - 3z  max  -x - 2y + 3z.
¦ x unrestricted  x = y - z,  y ‡ 0, z ‡ 0.
n j x
m i b x a
x c
j
i
n
j
j ij
n
j
j j
£ £ ‡ £ £ £   =
=
1 0
1 t. s.
max (P)
1
1
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!