香港中文大学：《Design and Analysis of Algorithms》课程教学资源（辅导课件）tutorial 06

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

Example Want to build the strongest army for the 3160 Empires. Resources we have:9366 wood,7173 food,2131 gold 9366717321310/200 Imperial Age2的包a口【Wc2 Soldiers we can produce: 80 food 60 food 80 wood 75 gold 50 gold Power:1 Power:2 Power:3 How to maximize the power of our army?

• Want to build the strongest army for the 3160 Empires. • Resources we have: 9366 wood, 7173 food, 2131 gold • Soldiers we can produce: • How to maximize the power of our army? Example 80 food Power: 1 80 wood 50 gold Power: 3 60 food 75 gold Power: 2

9366 7173 2131地0/200 Imperial Age Ba口 Linear Program 。Variables: 80 food 60 food 80 wood 75 gold 50 gold -X units Power:1 Power:2 Power:3 X,units -X3 units max X1+2X2+3X3 Constraints subject to 80X1+60X2≤7173 Food supply is 7173 75x2+50X3≤2131 Wood supply is 9366 80x3≤9366 Gold supply is 2131 X1+X2+X3≤200 Max population is 200 X1,X2,X3≥0 。Objective Maximize the power of the army

80 food Power: 1 80 wood 50 gold Power: 3 60 food 75 gold Power: 2 Linear Program max subject to x1 + 2x2 + 3x3 80x1 + 60x2 ≤ 7173 75x2 + 50x3 ≤ 2131 80x3 ≤ 9366 x1+x2+x3 ≤ 200 x1 , x2 , x3 ≥ 0 • Variables: – x1 units – x2 units – x3 units • Constraints – Food supply is 7173 – Wood supply is 9366 – Gold supply is 2131 – Max population is 200 • Objective – Maximize the power of the army

Standard form max cTx subject to Ax≤b X≥0 C11+…+CnXn a111+.+01nXn≤b1 021X1+…+02nXn≤b2 am1X1+…+amnXn≤bm X1,X2,,Xn≥0

Standard form max subject to c Tx Ax ≤ b x ≥ 0 x1 , x2 , …, xn ≥ 0 a11 x1 + … + a1nxn ≤ b1 a21 x1 + … + a2nxn ≤ b2 … am1 x1 + … + amnxn ≤ bm c1 x1 + … + cn xn

Converting into standard form 。Constraints 011X1+.+01nXn≥b1 is equivalent to -011X1-…-01nXn≤-b1 011X1+…+01nXn=b1 is equivalent to -a11X1-…-01nXm≤-b1and011X1+.+01nXn≤b1

Converting into standard form • Constraints a11 x1 + … + a1nxn ≥ b1 is equivalent to -a11 x1 - … - a1nxn ≤ -b1 a11 x1 + … + a1nxn = b1 is equivalent to -a11 x1 - … - a1nxn ≤ -b1 and a11 x1 + … + a1nxn ≤ b1

Converting into standard form ·Constraints x free (free variables) is equivalent to X=xt-x and x*,x≥0

Converting into standard form • Constraints x free (free variables) is equivalent to x = x+ - x - and x + , x- ≥ 0