Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Linear ProgrammingReference: The Allocation of Resources by Linear Programming, Scientific American, by Bob Bland.2Linear ProgrammingWhat is it?! Quintessential tool for optimal allocation of scarce resources,among a number of competing activities.! Powerful and general problem-solving method that encompasses:– shortest path, network flow, MST, matching– Ax = b, 2-person zero sum gamesWhy significant?! Widely applicable.! Fast commercial solvers: CPLEX, OSL.! Powerful modeling languages: AMPL, GAMS.! Ranked among most important scientific advances of 20th century.! Dominates world of industry.see ORF 307Ex: Delta claims saving $100 million per year using LP3ApplicationsAgriculture. Diet problem.Computer science. Compiler register allocation, data mining.Electrical engineering. VLSI design, optimal clocking.Energy. Blending petroleum products.Economics. Equilibrium theory, two-person zero-sum games.Environment. Water quality management.Finance. Portfolio optimization.Logistics. Supply-chain management.Management. Hotel yield management.Marketing. Direct mail advertising.Manufacturing. Production line balancing, cutting stock.Medicine. Radioactive seed placement in cancer treatment.Operations research. Airline crew assignment, vehicle routing.Physics. Ground states of 3-D Ising spin glasses.Plasma physics. Optimal stellarator design.Telecommunication. Network design, Internet routing.Sports. Scheduling ACC basketball, handicapping horse races.4Brewery Problem: A Toy LP ExampleSmall brewery produces ale and beer.! Production limited by scarce resources: corn, hops, barley malt.! Recipes for ale and beer require different proportions of resources.How can brewer maximize profits?! Devote all resources to ale: 34 barrels of ale ! $442.! Devote all resources to beer: 32 barrels of beer ! $736.! 7.5 barrels of ale, 29.5 barrels of beer ! $776.! 12 barrels of ale, 28 barrels of beer ! $800.BeverageCorn(pounds)Malt(pounds)Hops(ounces)Beer (barrel) 15 204Ale (barrel) 5 354Profit($)2313Limit 480 11901605Brewery Problem ! max 13A + 23Bs. t. 5A + 15B " 4804 A + 4B " 16035A + 20B " 1190A , B # 0AleBeerCornHopsMaltProfit6Brewery Problem: Feasible RegionAleBeer(34, 0)(0, 32)Corn5A + 15B " 480Hops4A + 4B " 160Malt35A + 20B " 1190(12, 28)(26, 14)(0, 0)7Brewery Problem: Objective Function13A + 23B = $80013A + 23B = $160013A + 23B = $442(34, 0)(0, 32)(12, 28)(26, 14)(0, 0)ProfitAleBeer8(34, 0)(0, 32)(12, 28)(0, 0)(26, 14)Brewery Problem: GeometryBrewery problem observation. Regardless of objective functioncoefficients, an optimal solution occurs at an extreme point.extreme pointAleBeer9Standard Form LP"Standard form" LP.! Input: real numbers aij, cj, bi.! Output: real numbers xj.! n = # nonnegative variables, m = # constraints.! Maximize linear objective function subject to linear inequalities.Linear. No x2, xy, arccos(x), etc.Programming. Planning (term predates computer programming).! (P) max cjxjj=1n"s. t. aijxjj=1n"= bi1 # i # mxj$ 0 1 # j # n! (P) max cTxs. t. Ax = bx " 010Brewery Problem: Converting to Standard FormOriginal input.Standard form.! Add slack variable for each inequality.! Now a 5-dimensional problem.! max 13A + 23Bs. t. 5A + 15B " 4804 A + 4B " 16035A + 20B " 1190A , B # 0! max 13A + 23Bs. t. 5A + 15B + SC= 4804 A + 4B + SH= 16035A + 20B + SM= 1190A , B , SC, SH, SM" 011Geometry.! Inequality: halfplane (2D), hyperplane (kD).! Bounded feasible region: convex polygon (2D), convex polytope (kD).Convex set. If two points a and b are in the set, then so is !(a + b).Extreme point. A point in the set that can't be written as !(a + b),where a and b are two distinct points in the set.Geometryconvex not convexextremepoint12GeometryExtreme point property. If there exists an optimal solution to (P),then there exists one that is an extreme point.Consequence. Only need to consider finitely many possible solutions.Challenge. Number of extreme points can be exponential!Greedy property. Extreme point is optimaliff no neighboring extreme point is better.local optima are global optiman-dimensional hypercube13Simplex AlgorithmSimplex algorithm. [George Dantzig, 1947]! Developed shortly after WWII in response to logistical problems,including Berlin airlift.! One of greatest and most successful algorithms of all time.Generic algorithm.! Start at some extreme point.! Pivot from one extreme point to a neighboring one.! Repeat until optimal.How to implement? Linear algebra.never decreasing objective function14Simplex Algorithm: BasisBasis. Subset of m of the n variables.Basic feasible solution (BFS). Set n - m nonbasic variables to 0,solve for remaining m variables.! Solve m equations in m unknowns.! If unique and feasible solution ! BFS.! BFS # extreme point.AleBeerBasis{A, B, SM }(12, 28){A, B, SC }(26, 14){B, SH, SM }(0, 32){SH, SM, SC }(0, 0){A, SH, SC }(34, 0)! max 13A + 23Bs. t. 5 A + 15B + SC= 4804 A + 4B + SH= 16035A + 20B + SM= 1190A , B , SC, SH, SM" 0Infeasible{A, B, SH }(19.41, 25.53)15Simplex Algorithm: InitializationBasis = {SC, SH, SM}A = B = 0Z = 0SC = 480SH = 160SM = 1190! max Z subject to13A + 23B " Z = 05A + 15B + SC= 4804A + 4B + SH= 16035A + 20B + SM= 1190A , B , SC, SH, SM# 016! max Z subject to163A "2315SC" Z = "73613A + B +115SC= 3283A "415SC+ SH= 32853A "43SC+ SM= 550A , B , SC, SH, SM# 0Basis = {B, SH, SM}A = SC = 0Z = 736B = 32SH = 32SM = 550Simplex Algorithm: Pivot 1Substitute: B = 1/15 (480 – 5A – SC)Basis = {SC, SH, SM}A = B = 0Z = 0SC = 480SH = 160SM = 1190! max Z subject to13A + 23B " Z = 05A + 15B + SC= 4804A + 4B + SH= 16035A + 20B + SM= 1190A , B , SC, SH, SM# 017Simplex Algorithm: Pivot 1Why pivot on column 2?! Each unit increase in B increases objective value by $23.! Pivoting on column 1 also OK.Why pivot on row 2?! Preserves feasibility by ensuring RHS $ 0.! Minimum ratio rule: min { 480/15, 160/4, 1190/20 }.! max Z subject to13A + 23B " Z = 05A + 15B + SC= 4804A + 4B + SH= 16035A + 20B + SM= 1190A , B , SC, SH, SM# 0Basis = {SC, SH, SM}A = B = 0Z = 0SC = 480SH = 160SM = 119018Simplex Algorithm: Pivot 2! max Z subject to163A "2315SC" Z = "73613A + B +115SC= 3283A "415SC+ SH= 32853A "43SC+ SM= 550A , B , SC, SH, SM# 0! max Z subject to" SC" 2 SH" Z = "800B +110SC+18SH= 28A "110SC+38SH= 12"256SC"858SH+ SM= 110A , B , SC, SH, SM# 0Substitute: A = 3/8 (32 + 4/15 SC – SH)Basis = {B, SH, SM}A
View Full Document
Unlocking...