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. 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) –Cal 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 spenthours# yield%daily u 32 1021Subject to 3000 capital2 18Maximize d d u  x xx x x 16.410: MIT, Fall 2003 Example 1: Graphical Representation x2 x1 A1 A2 Answer depends upon gradient orientation Cost function 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 182213 1222 41 d d d xx x x 16.410: MIT, Fall 2003 Example 2, Ct’d x2 x1 Feasible region 0 41 dx (4,0) (4,3) (2,6)(0,6) 182213 d xx 1222 dx 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 11 11111 11 tt d d  n mnmnm nn nn xx bxaxa bxaxa xcxcZ   nn xcxcZ  ...Minimize 11 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 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) 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. 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 182213 1222 41 d d d xx 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 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 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. 16.410: MIT, Fall 2003 Simplex algorithm analysis Does every pivot step decrease cost? Answer: almost yes! Min:z -8x4 = 20 Cost has not decreased! This is a degenerate basis, with one basic variable (x4) having value zero Min:z +8x2 = 20 x3 +2/3x4 +1/3x5 = 4 4 ÷2/3 = 6 x2 +x4 = 0 0 ÷ 1 = 0 x1 -2/3x4+1/3x5 = 2 2 ÷ -2/3 Not valid -2/3x2+ x3 +1/3x5 = 4 x2 +x4 = 0 x1 +2/3x2 +1/3x5 = 2 16.410: MIT, Fall 2003 Simplex algorithm analysis If there are no degenerate bases (true in random instances of LP), then it is impossible to return to a basis that has already been visited, because the objective function must decrease at every step If there are degenerate bases, it is possible to cycle, which would mean that the same series of bases repeats as you pivot, so one could pivot forever. Smart rules about disambiguating ties in the lowest cost coefficient test and minimum positive ratio test can rule out possibility of infinite cycling Number of pivot steps < Number of corner point solutions 16.410: MIT, Fall 2003 Simplex algorithm analysis With n variables, each bounded >0, <1, there are 2 n corner point feasible solutions Pathological examples force examination of all of these Each pivot (Gaussian elimination) takes m n time Simplex algorithm is exponential in worst-case analysis, yet is remarkably successful in practice In fact, linear programming can be solved in polynomial time by interior point methods. Recently these have become competitive in practice with simplex.