CSCI 3160 Design and Analysis of Algorithms Tutorial 6 Fei Chen
CSCI 3160 Design and Analysis of Algorithms Tutorial 6 Fei Chen
Outline ·Linear Programming -Standard form -Problem modeling -Algorithm ·Duality 。Application
Outline • Linear Programming – Standard form – Problem modeling – Algorithm • Duality • Application
Linear Programming Constraint Optimization Linear constraints Linear objective function max 。Example X1+2X2+3X3 subject to 80x1+60x2≤7173 75x2+50x3≤2131 80x3≤9366 X1+X2+X3≤200 X1,2,X3≥0
Linear Programming • Constraint Optimization – Linear constraints – Linear objective function • Example max subject to x1 + 2x2 + 3x3 80x1 + 60x2 ≤ 7173 75x2 + 50x3 ≤ 2131 80x3 ≤ 9366 x1+x2+x3 ≤ 200 x1 , x2 , x3 ≥ 0
Linear Programming In LP,the feasible region is a convex polytope bounded by many half planes (constraints) By linearity,the optimal solution must locate at the extreme points There are finite number of points to try 160 1+2<a50 140 120 100 x1+2x2c=170 80 1、9=4900 32ca180 40 20 0 50 90 10 130
Linear Programming • In LP, the feasible region is a convex polytope bounded by many half planes (constraints) • By linearity, the optimal solution must locate at the extreme points – There are finite number of points to try
Simplex method Start from any vertex of the polytope look for a better neighbor and move to it. Until the current vertex is better than all of its neighbors ·For LP local optimal台global optimal because the feasible region is convex Profit $1900 300 Optimal solution 200 $1400 100 $0 $200 0 100 200 Starting vertex-
Simplex method • Start from any vertex of the polytope • look for a better neighbor and move to it. • Until the current vertex is better than all of its neighbors • For LP local optimal ⇔ global optimal – because the feasible region is convex