Question? Leave a message!




LINEAR PROGRAMMING

LINEAR PROGRAMMING
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms FOUR TH EDITION reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLinear programming What is it? Problem-solving model for optimal allocation of scarce resources, among a number of competing activities that encompasses: Shortest paths, maxflow, MST, matching, assignment, ... can take an entire course on LP A x = b, 2-person zero-sum games, ... maximize 13A + 23B 5A + 15B 480 ≤ subject subject subject to the to the to the 4A + 4B ≤ 160 constraints constraints constraints 35A + 20B ≤ 1190 A , B ≥ 0 Why significant? Fast commercial solvers available. Ex: Delta claims that LP Widely applicable problem-solving model. saves 100 million per year. Key subroutine for integer programming solvers. 2Applications Agriculture. 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. Telecommunication. Network design, Internet routing. Sports. Scheduling ACC basketball, handicapping horse races. 3LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu Allocation of Resources by Linear Programming by Robert Bland Scientific American, Vol. 244, No. 6, June 1981Toy LP example: brewer’s problem Small brewery produces ale and beer. Production limited by scarce resources: corn, hops, barley malt. corn (480 lbs) hops (160 oz) malt (1190 lbs) Recipes for ale and beer require different proportions of resources. 13 profit per barrel 23 profit per barrel 5Toy LP example: brewer’s problem Brewer’s problem: choose product mix to maximize profits. 34 barrels × 35 lbs malt = 1190 lbs amount of available malt ale beer corn hops malt profit 34 0 179 136 1190 442 0 32 480 128 640 736 19.5 20.5 405 160 1092.5 725 goods are divisible 12 28 480 160 980 800 ? ? 800 ? corn (480 lbs) hops (160 oz) malt (1190 lbs) 13 profit per barrel 23 profit per barrel 6Brewer’s problem: linear programming formulation Linear programming formulation. Let A be the number of barrels of ale. Let B be the number of barrels of beer. ale beer profits maximize 13A + 23B 5A + 15B 480 corn ≤ subject subject subject to the to the to the 4A + 4B 160 hops ≤ constraints constraints constraints 35A + 20B 1190 ≤ malt A , B 0 ≥ 7Brewer’s problem: feasible region Inequalities define halfplanes; feasible region is a convex polygon. hops malt 4A + 4B ≤ 160 35A + 20B ≤ 1190 (0, 32) (12, 28) corn beer 5A + 15B ≤ 480 (26, 14) (0, 0) (34, 0) ale 8higher profit? Brewer’s problem: objective function (0, 32) (12, 28) 13A + 23B = 1600 beer (26, 14) 13A + 23B = 800 (0, 0) (34, 0) ale 13A + 23B = 442 7 9Brewer’s problem: geometry Optimal solution occurs at an extreme point. intersection of 2 constraints in 2d extreme point (0, 32) (12, 28) beer (26, 14) (0, 0) (34, 0) ale 10 7Standard form linear program Goal. Maximize linear objective function of n nonnegative variables, subject to m linear equations. 2 linear means no x , xy, arccos(x), etc. Input: real numbers a , c , b . ij j i Output: real numbers x . j primal problem (P) matrix version maximize c x + c x + … + c x T 1 1 2 2 n n maximize c x a x + a x + … + a x = b 11 1 12 2 1n n 1 subject subject A x = b subject subject subject subject a21 x1 + a22 x2 + … + a2n xn = b2 to the to the to the to the to the to the x ≥ 0 constraints constraints ⋮ ⋮ ⋮ ⋮ ⋮ constraints constraints constraints constraints a x + a x + … + a x = b m1 1 m2 2 mn n m x , x , … , x 0 1 2 n ≥ Caveat. No widely agreed notion of "standard form." 11Converting the brewer’s problem to the standard form Original formulation. maximize 13A + 23B 5A + 15B 480 ≤ subject subject subject to the to the to the 4A + 4B 160 ≤ constraints constraints constraints 35A + 20B 1190 ≤ A , B 0 ≥ Standard form. Add variable Z and equation corresponding to objective function. Add slack variable to convert each inequality to an equality. Now a 6-dimensional problem. maximize Z 13A + 23B − Z = 0 subject subject subject subject 5A + 15B + S SC C = 480 to the to the to the to the 4A + 4B + S S S = 160 H H H constraints constraints constraints constraints 35A + 20B + + S S = 1190 M M A , B , S S , S S S ,, S S 0 C C C C C M M ≥ 12Geometry Inequalities define halfspaces; feasible region is a convex polyhedron. A set is convex if for any two points a and b in the set, so is ½ (a + b). An extreme point of a set is a point in the set that can't be written as ½ (a + b), where a and b are two distinct points in the set. extreme point not convex convex Warning. Don't always trust intuition in higher dimensions. 13Geometry (continued) Extreme point property. If there exists an optimal solution to (P), then there exists one that is an extreme point. Good news: number of extreme points to consider is finite. Bad news : number of extreme points can be exponential local optima are global optima (follows because objective function is linear and feasible region is convex) Greedy property. Extreme point optimal iff no better adjacent extreme point. 14LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSimplex algorithm Simplex algorithm. George Dantzig, 1947 Developed shortly after WWII in response to logistical problems, including Berlin airlift. th Ranked as one of top 10 scientific algorithms of 20 century. never decreasing objective function Generic algorithm. Start at some extreme point. Pivot from one extreme point to an adjacent one. Repeat until optimal. How to implement? Linear algebra. 17Simplex algorithm: basis A basis is a 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 ⇒ BFS. basic feasible solution BFS ⇔ extreme point. basic infeasible B, S , S H M A, B, S M solution (0, 32) (12, 28) maximize Z A, B, S H (19.41, 25.53) 13A + 23B − Z = 0 subject subject subject subject 5A + 15B + SC = 480 beer A, B, S C to the to the to the to the (26, 14) 4A + 4B + SH = 160 constraints constraints constraints constraints 35A + 20B + S = 1190 M A , B , SC , SH , SM 0 ≥ ale A, S , S S , S , S H C H M C (34, 0) (0, 0) 18Simplex algorithm: initialization maximize Z basis = S , S , S C H M 13A + 23B − Z = 0 A = B = 0 subject subject subject subject Z = 0 5A + 15B + S = 480 C to the to the to the to the S = 480 C 4A + 4B + SH = 160 constraints constraints constraints constraints S = 160 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S 0 C H M ≥ one basic variable per row Initial basic feasible solution. Start with slack variables S , S , S as the basis. C H M no algebra needed Set non-basic variables A and B to 0. 3 equations in 3 unknowns yields S = 480, S = 160, S = 1190. C H M 19Simplex algorithm: pivot 1 maximize Z pivot basis = S , S , S C H M 13A + 23B − Z = 0 A = B = 0 subject subject subject subject Z = 0 5A + 15B + S = 480 C to the to the to the to the S = 480 C 4A + 4B + SH = 160 constraints constraints constraints constraints S = 160 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S 0 C H M ≥ which basic variable substitute B = (1/15) (480 – 5A – S ) and add B into the basis C does B replace? (rewrite 2nd equation, eliminate B in 1st, 3rd, and 4th equations) maximize Z basis = B, S , S H M (16/3) A − (23/15) S − Z = -736 C A = S = 0 C subject subject subject subject Z = 736 (1/3) A + B + (1/15) SC = 32 to the to the to the to the B = 32 (8/3) A − (4/15) S + S = 32 C H constraints constraints constraints constraints S = 32 H (85/3) A − (4/3) S + S = 550 C M S = 550 M A , B , S , S , S 0 C H M ≥ 20