Question? Leave a message!




LINEAR PROGRAMMING

LINEAR PROGRAMMING
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:23-07-2017
Website URL
Comment
LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣ Lecture slides by Kevin Wayne Last updated on 5/15/17 10:33 AMLinear programming Linear programming. Optimize a linear function subject to
 linear inequalities. n T (P) max c x (P) max c x ∑ j j j=1 s. t. Ax = b n x ≥ 0 s. t. a x = b 1≤i≤m ∑ ij j i j=1 x ≥ 0 1≤ j≤n j € € 2Linear programming Linear programming. Optimize a linear function subject to
 linear inequalities. Generalizes: Ax = b, 2-person zero-sum games, shortest path,
 max flow, assignment problem, matching, multicommodity flow,
 MST, min weighted arborescence, … Why significant? Design poly-time algorithms. ・ Design approximation algorithms. ・ Solve NP-hard problems using branch-and-cut. ・ Ranked among most important scientific advances of 20th century. 3LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣ Reference: The Allocation of Resources by Linear Programming, Scientific American, by Bob BlandBrewery problem Small brewery produces ale and beer. Production limited by scarce resources: corn, hops, barley malt. ・ Recipes for ale and beer require different proportions of resources. ・ Corn
 Hops
 Malt
 Profit
 Beverage (pounds) (ounces) (pounds) () Ale (barrel) 5 4 35 13 Beer (barrel) 15 4 20 23 constraint 480 160 1190 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 ・ 5Brewery problem objective function Beer Ale Profit max 13A + 23B Corn s. t. 5A + 15B ≤ 480 Hops 4A + 4B ≤ 160 Malt 35A + 20B ≤ 1190 A , B ≥ 0 constraint € decision variable 6Reference 7LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Standard form LP "Standard form" LP. Input: real numbers a , c , b . ・ ij j i Output: real numbers x . ・ j n = decision variables, m = constraints. ・ Maximize linear objective function subject to linear inequalities. ・ n T (P) max c x (P) max c x ∑ j j j=1 s. t. Ax = b n x ≥ 0 s. t. a x = b 1≤i≤m ∑ ij j i j=1 x ≥ 0 1≤ j≤n j € € 2 Linear. No x , x y, arccos(x), etc. Programming. Planning (term predates computer programming). 9Brewery problem: converting to standard form Original input. max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 Standard form. € Add slack variable for each inequality. ・ Now a 5-dimensional problem. ・ max 13A + 23B s. t. 5A + 15B + S = 480 C 4A + 4B + S = 160 H 35A + 20B + S = 1190 M A , B , S , S , S ≥ 0 C H M 10 € Equivalent forms Easy to convert variants to standard form. T (P) max c x s. t. Ax = b x ≥ 0 € Less than to equality. x + 2y – 3z ≤ 17 ⇒ x + 2y – 3z + s = 17, s ≥ 0 Greater than to equality. x + 2y – 3z ≥ 17⇒ x + 2y – 3z – s = 17, s ≥ 0 Min to max. min x + 2y – 3z ⇒ max –x – 2y + 3z + – + – Unrestricted to nonnegative. x unrestricted ⇒ x = x – x , x ≥ 0, x ≥ 0 11LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Fundamental questions m×n m n n LP. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , α ∈ ℜ, does there exist x ∈ ℜ such that: 
 T Ax = b, x ≥ 0, c x ≥ α ? Q. Is LP in NP? Q. Is LP in co-NP? Q. Is LP in P? Q. Is LP in P ? ℜ Blum–Shub–Smale model Input size. n = number of variables. ・ m = number of constraints. ・ L = number of bits to encode input. ・ 13LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Brewery problem: feasible region Hops
 Malt
 4A + 4B ≤ 160 35A + 20B ≤ 1190 (0, 32) (12, 28) Corn
 5A + 15B ≤ 480 (26, 14) Beer Ale (0, 0) (34, 0) 15Profit Brewery problem: objective function (0, 32) (12, 28) 13A + 23B = 1600 (26, 14) Beer 13A + 23B = 800 Ale (0, 0) (34, 0) 13A + 23B = 442 16Brewery problem: geometry Brewery problem observation. Regardless of objective function coefficients, an optimal solution occurs at a vertex. (0, 32) (12, 28) vertex (26, 14) Beer Ale (0, 0) (34, 0) 17Convexity Convex set. If two points x and y are in the set, then so is
 λ x + (1− λ) y for 0 ≤ λ ≤ 1. not a vertex iff ∃ d ≠ 0 s.t. x ± d in set convex combination Vertex. A point x in the set that can't be written as a strict
 convex combination of two distinct points in the set. vertex x y convex not convex Observation. LP feasible region is a convex set. 18Purificaiton Theorem. If there exists an optimal solution to (P), then there exists one that is a vertex. T (P) max c x s. t. Ax = b x ≥ 0 Intuition. If x is not a vertex, move in a non-decreasing direction until you € reach a boundary. Repeat. x' = x + α d x + d x x - d 19Purificaiton Theorem. If there exists an optimal solution to (P), then there exists one that is a vertex. Pf. Suppose x is an optimal solution that is not a vertex. ・ There exist direction d ≠ 0 such that x ± d ∈ P. ・ A d = 0 because A(x ± d) = b. ・ T Assume c d ≤ 0 (by taking either d or –d). ・ Consider x + λ d, λ 0 : ・ Case 1. there exists j such that d 0 j Increase λ to λ until first new component of x + λ d hits 0. ・ x + λ d is feasible since A(x + λ d) = Ax = b and x + λ y ≥ 0. ・ x + λ d has one more zero component than x. ・ T T T T T c x' = c (x + λ d) = c x + λ c d ≤ c x. ・ d = 0 whenever x = 0 because x ± d ∈ P k k 20