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