麻省理工学院：《自制决策制造原则》英文版 Courtesy or Eric Feron and Sommer

Courtesy or Eric Feron and Sommer Gentry. Used with permission. Introduction to Linear Programming Eric Feron (updated Sommer Gentry) 16410 Fall 2003 Novemeber 12. 2003 16410: MIT. Fall 2003 Historical aspects .Historical contributor: G Dantzig, late 1940s(Now at Stanford University. Realize many real-world design problems can be formulated as linear programs and solved efficiently Finds algorithm, the Simplex method to solve LPs. As of 1997, still best algorithm for most applications o important for world economy that any new algorithmic development on LP's is likely to make the Front Page of major newspapers(e.g. NY times, Wall Street Journal). Example: 1979 L. Khachyan's adaptation of ellipsoid algorithm. N. Karmarkar's new interior-point algorithm. a remarkably practical and theoretical framework LPs eat a large chunk of total scientific computational power expended today. It is crucial for economic success of most distribution/transport industries and to .Now becomes suitable for real-time applications 16410: MIT. Fall 2003

16.410: MIT, Fall 2003 Introduction to Linear Programming Eric Feron (updated Sommer Gentry) 16.410 Fall 2003 Novemeber 12, 2003 16.410: MIT, Fall 2003 Historical aspects •Historical contributor: G. Dantzig, late 1940’s (Now at Stanford University. Realize many real-world design problems can be formulated as linear programs and solved efficiently. Finds algorithm, the Simplex method to solve LP’s. As of 1997, still best algorithm for most applications. •So important for world economy that any new algorithmic development on LP’s is likely to make the Front Page of major newspapers (e.g. NY times, Wall Street Journal). Example: 1979 L. Khachyan’s adaptation of ellipsoid algorithm, N. Karmarkar’s new interior-point algorithm. •A remarkably practical and theoretical framework: LPs eat a large chunk of total scientific computational power expended today. It is crucial for economic success of most distribution/transport industries and to manufacturing. •Now becomes suitable for real-time applications. Courtesy or Eric Feron and Sommer Gentry. Used with permission

Examples of Linear programs .Example 1: Revenue maximization problem Wage is $8/hour Stock Profit is daily %yield #hours spent x capital 30 and number of hours spent is never greater than 10 hours/day (3 hours Max on stock market) Call xl the number of hours spent work, x2 the number of hours spent working on the stock market. Problem formulation Maximize 8x1+x2x capital 3000 Subject to xl+x2≤10 2≤3 Our first Lp 16410: MIT. Fall 2003 Example 1: Graphical Representation Al Cost function Answer depends upon gradient orientation 16410: MIT. Fall 2003

16.410: MIT, Fall 2003 Examples of Linear programs •Example 1: Revenue maximization problem. Wage is $8 / hour Stock Profit is and number of hours spent is never greater than 10 hours/day (3 hours Max on stock market) – Call x1 the number of hours spent @ work, x2 the number of hours spent working on the stock market. •Problem formulation: Our first LP capital 30 # hoursspent daily % yield u 2 3 Subject to 1 2 10 3000 2 capital Maximize 8 1 d  d u  x x x x x 16.410: MIT, Fall 2003 Example 1: Graphical Representation x2 x1 A1 A2 Answer depends upon gradient orientation Cost function

Example 2: Resource Allocation An aircraft company makes two aircraft engines. Engine parts are made at three plants: A, B, c Engine I is made of elements produced in A and C Engine 2 is made of elements of B and C .Plants A, B, C have limited throughput .What mix of product I and 2 will bring maximum profit? Another resource allocation problem 16410: MIT. Fall 2003 Example 2 Ct'd Add'l data Plant ProductionProduction Production time C Profit/ Is300.000s500.000 x1: of Engine 1 :2 Engine 2 Profit (in KKKS): 3x1+ 5x2 Constraints:xl≤4 2x2<12 3x1+2x2≤18 16410:MI,Fall2003

16.410: MIT, Fall 2003 Example 2: Resource Allocation An aircraft company makes two aircraft engines. Engine parts are made at three plants: A, B, C. – Engine 1 is made of elements produced in A and C – Engine 2 is made of elements of B and C •Plants A,B, C have limited throughput •What mix of product 1 and 2 will bring maximum profit? Another resource allocation problem. 16.410: MIT, Fall 2003 Example 2 Ct’d • Add’l data: x1: # of Engine 1 x2: # Engine 2 Profit (in KKK$): 3x1 + 5x2 Constraints: Plant Production time per engine 1 Production time per engine 2 Production time Available Per week A 1 0 4 B 0 2 12 C 3 2 18 Profit/ engine $300,000 $500,000 3 1 2 2 18 2 2 12 1 4  d d d x x x x

Example 2. Ct'd pt=363x1+2x2≤18 2x2<12 (0,6 (2,6) region 1.6 16410: MIT. Fall 2003 Standard Linear Programming Model Z: Overall measure of performance xj: Activity level for product j c: Marginal improvement of Z associated with product j bi: Available resource I I to produce General LP: Maximize z-C.x Subject to a,1 ≤b1 xI <6 x1≥0,…,xn≥0 Standard form for LP: Minimize Z=-Cx-.-Cr 16410: MIT. Fall 2003

16.410: MIT, Fall 2003 Example 2, Ct’d x2 x1 Feasible region 0 x1 d 4 (4,0) (4,3) (0,6) (2,6) 3x1 2x2 d18 2x2 d12 1 1.6 Zopt=36 16.410: MIT, Fall 2003 Standard Linear Programming Model • Notations: – Z: Overall measure of performance – xj: Activity level for product j – cj: Marginal improvement of Z associated with product j – bi: Available resource I – aij: Amount of resource I to produce j. • General LP: • Standard form for LP. 0, , 0. ... Subject to ... Maximize ... 1 1 1 11 1 1 1 1 1 t t   d   d   n m mn n m n n n n x x a x a x b a x a x b Z c x c x   n n Minimize Z c x ... c x 1 1

Standard form of lp other forms of lps Arbitrary signs on ci, bj, aij, xi. Equality constraints Require technicalities but may be cast in standard form Feasible/unfeasible solutions The set of solutions that satisfy all the constraints is said feasible. It is the intersection of many half planes(m of them) with the positive orthant(what's that? ) It's a polytope. 16410: MIT. Fall 2003 Graphical Depiction of LP constraints xI>0 and x2>0 and constra and constraint 2 and constraint 3 16410:MI,Fall2003

16.410: MIT, Fall 2003 Standard form of LP •Other forms of LPs: – Arbitrary signs on ci, bj, aij, xi. – Equality constraints – Require technicalities but may be cast in standard form •Feasible/unfeasible solutions The set of solutions that satisfy all the constraints is said feasible. It is the intersection of many half planes (m of them) with the positive orthant (what’s that?). It’s a polytope. 16.410: MIT, Fall 2003 Graphical Depiction of LP constraints x1 x2 and x2>0 and constraint 1 and constraint 2 and constraint 3 x1>0

This is not an lp and x2>0 and constraint 1 and constraint 2 or constraint 3 16410: MIT. Fall 2003 Some vocabulary(ct'd) Ⅴ ocabulary Polytope may be empty: No feasible solutions Polytope may be unbounded: possibility for infinite optimal costs Sure signs of problem misunderstanding Infeasible set of constraints Nonstandard LP) 16410:MI,Fall2003

16.410: MIT, Fall 2003 This is not an LP! x1 x2 and x2>0 and constraint 1 and constraint 2 or constraint 3 x1>0 16.410: MIT, Fall 2003 Some vocabulary (ct’d) • Vocabulary – Polytope may be empty: No feasible solutions – Polytope may be unbounded: possibility for infinite optimal costs – Sure signs of problem misunderstanding Infeasible set of constraints (Nonstandard LP)

LP Assumptions Proportionality Does twice the activity result in twice the profit, or twice the shipment size result in twice the cost? Additivity Does opening a store in Cambridge and one in Boston result in the sum of projected profits? Divisibility Can you manufacture half an aircraft? Certainty What do we really know about the problem? 16410: MIT. Fall 2003 Addressing these issues Divisibility is a real problem in decision-making LPs is the solution. Some important nteger programs luckily are also solvable as LPs Theorem: The solution to any transportation problem with integer supplies and demands is integer Transportation problems include the class of assignment problems Uncertainty in the data is a huge problem. The right way to address it is either by sensitivity analysis if the data might be off by small amounts or by multiple case analysis if the scenarios range widely 16410: MIT. Fall 2003

16.410: MIT, Fall 2003 LP Assumptions • Proportionality – Does twice the activity result in twice the profit, or twice the shipment size result in twice the cost? • Additivity – Does opening a store in Cambridge and one in Boston result in the sum of projected profits? • Divisibility – Can you manufacture half an aircraft? • Certainty – What do we really know about the problem? 16.410: MIT, Fall 2003 Addressing these issues • Divisibility is a real problem in decision-making LPs; integer programming is the solution. Some important integer programs luckily are also solvable as LPs! – Theorem: The solution to any transportation problem with integer supplies and demands is integer. – Transportation problems include the class of assignment problems. • Uncertainty in the data is a huge problem. The right way to address it is either by sensitivity analysis if the data might be off by small amounts or by multiple case analysis if the scenarios range widely

SIMPLEX method of solving LPs Maximize 3 x+5x2 10 16410: MIT. Fall 2003 Basis solution to a system of equations Standard()form: min z-3x1-5x' 0 4 +x4 6 3x1+2x2 +x5=18 The variables whose coefficients are an identity matrix are X3, x4, X5. These are slack variables, and at this step in the Simplex method they are also the basic variables The other variables are nonbasic and are set to zero at this corner point. Let x1=0, x2=0 So x3=4, x4=6, and x5=18. At each basic solution you can read the values of basic variables off the equations 16410: MIT. Fall 2003

16.410: MIT, Fall 2003 SIMPLEX method of solving LPs • Maximize 3x1 + 5x2, subject to x1 > 0, x2 > 0 • Standard (= ) form: min z-3x1 -5x2 = 0 x1 +x3 = 4 x2 +x4 = 6 3x1+2x2 +x5 =18 x1, x2, x3, x4, x5 > 0 3 1 2 2 18 2 2 12 1 4  d d d x x x x 16.410: MIT, Fall 2003 Basis solution to a system of equations • Standard (= ) form: min z-3x1 -5x2 = 0 x1 +x3 = 4 x2 +x4 = 6 3x1+2x2 +x5 =18 • The variables whose coefficients are an identity matrix are x3, x4, x5. These are slack variables, and at this step in the Simplex method they are also the basic variables • The other variables are nonbasic and are set to zero at this corner point. Let x1=0, x2=0. • So x3=4, x4=6, and x5=18. At each basic solution you can read the values of basic variables off the equations

Pivot ste Choose most negative reduced cost: z-3x1-5x2 2 Choose smallest positive ratio test 4 blank +x4 66÷1=6 3x1+2x2 +x5=1818÷2=9 So pivot on row 2, which means: set the coefficient of x2 in row 2 to 1, and eliminate x2 from the objective and the other constraint rows 16410: MIT. Fall 2003 Pivot step Choose most negative reduced cost: Z-3x1 +5x4=-30 So pivot on column x1 Choose smallest positive ratio test 2 +x4 6 blank 2x4+x5=66÷3=2 So pivot on row 3, which means: set the coefficient of x1 in row 3 to l, and eliminate xl from the objective and the other constraint rows 16410:MI,Fall2003

16.410: MIT, Fall 2003 Pivot step • Choose most negative reduced cost: z -3x1 -5x2 • So pivot on column x2 • Choose smallest positive ratio test: x1 +x3 = 4 blank x2 +x4 = 6 6 ÷1 = 6 3x1+2x2 +x5 =18 18 ÷ 2 = 9 • So pivot on row 2, which means: set the coefficient of x2 in row 2 to 1, and eliminate x2 from the objective and the other constraint rows 16.410: MIT, Fall 2003 Pivot step • Choose most negative reduced cost: z -3x1 +5x4 = -30 • So pivot on column x1 • Choose smallest positive ratio test: x1 +x3 = 4 4 ÷ 1 = 4 x2 +x4 = 6 blank 3x1 -2x4+x5 = 6 6 ÷ 3 = 2 • So pivot on row 3, which means: set the coefficient of x1 in row 3 to 1, and eliminate x1 from the objective and the other constraint rows

Pivot ste Choose most negative reduced cost: z +3x4 +X5=-36 No more improvement in z possible because all reduced costs are positive Read off solution 3+2/3x4+1/3x5=4 +x4 XI 2/3x4+1/3x5=2 Z=-36, so original objective is 36. x1=2, x 2=6, X3=4 Positive slack variable x3 indicates that original constrain xl <4 is not tight; the other two constraints are tight 16410: MIT. Fall 2003 Simplex algorithm steps Convert to standard form Add slack variables Pivot choose most negative reduced cost (identifies new basic variable) choose lowest positive ratio in ratio test eliminate new basic variable from objective and all rows except lowest positive ratio in ration test row Stop if optimal and read solution. Otherwise, pivot again 16410:MI,Fall2003

16.410: MIT, Fall 2003 Pivot step • Choose most negative reduced cost: z +3x4 +x5 = -36 • No more improvement in z possible because all reduced costs are positive • Read off solution: x3 +2/3x4 +1/3x5 = 4 x2 +x4 = 6 x1 -2/3x4+1/3x5 = 2 • z = -36, so original objective is 36. x1=2, x2=6, x3=4 • Positive slack variable x3 indicates that original constraint x1 < 4 is not tight; the other two constraints are tight 16.410: MIT, Fall 2003 Simplex algorithm steps • Convert to standard form • Add slack variables • Pivot – choose most negative reduced cost (identifies new basic variable) – choose lowest positive ratio in ratio test – eliminate new basic variable from objective and all rows except lowest positive ratio in ration test row • Stop if optimal and read solution. Otherwise, pivot again