Linear Programming (LP) (Chap.29)LP examplesChange a LP problem to standard formatLinear program in slack formFormatting problems as LPsSlide 6Example of max-flow problemFormatting Max-flow problem as LPsSlide 9Slide 10The Simplex algorithm for LPAn example of Simplex algorithmSimplex algorithm stepsSimplex algorithm exampleSlide 15Slide 16Slide 17Slide 18Simplex algorithm --PivotFormal Simplex algorithmRunning time of SimplexTwo variable LP problemsFind maximum via graphInteger linear program1Linear Programming (LP) (Chap.29)•Suppose all the numbers below are real numbers.•Given a linear function (called objective function)–f(x1, x2,…, xn)=c1x1+ c2x2+…+ cnxn=j=1n cjxj.•With constraints:j=1n aijxj bi for i=1,2,…,m and–xj0 for j=1,2,…,n. (nonnegativity)•Question: find values for x1, x2,…, xn, which maximize f(x1, x2,…, xn).•Or if change bi to bi , then minimize f(x1, x2,…, xn).2LP examples–Political election problem:•Certain issues: building roads, gun control, farm subsidies, and gasoline tax. •Advertisement on different issues•Win the votes on different areas: urban, suburban, and rural.•Goal: minimize advertisement cost to win the majority of each area. (See page 772, (29.6) –(29.10))–Flight crew schedule, minimize the number of crews:•Limitation on number of consecutive hours, •Limited to one model each month,…–Oil well location decision with maximum of oil output:•A location is associated a cost and payoff of barrels of oil.•Limited budget.3Change a LP problem to standard format•If some variables, such as xi,may not have nonnegativity constraints:–delete xi but introduce two variables xi' and xi'',–Replace each occurrence of xi with xi'-xi''.–Add constraints: xi'0 and xi'' 0.•There may be equality constraints:–Replace j=1n aijxj =bi with j=1n aijxj bi and j=1n aijxj bi .–Then change j=1n aijxj bi to j=1n -aijxj  -bi for minimization or j=1n aijxj bi to j=1n -aijxj -bi for maximization.4Linear program in slack form•Except nonnegativity constraints, all other constraints are equalities.•Change standard form to slack form:–If j=1n aijxj  bi, then introduce new variable s, and set: –si= bi - j=1n aijxj and si0. (i=1,2,…,m).–If j=1n aijxj  bi, then introduce new variable s, and set: –si= j=1n aijxj -bi and si0.•All the left-hand side variables are called basic variables, whereas all the right-hand side variables are called nonbasic variables.•Initially, s1, s1,…, sm basic variables, x1, x1,…, xn non-basic variables.5Formatting problems as LPs•(Single pair) Shortest path :–A weighted direct graph G=<V,E> with weighted function w: ER, a source s and a destination t, compute d which is the weight of the shortest path from s to t.–Change to LP:•For each vertex v, introduce a variable xv: the weight of the shortest path from s to v.•Maximize xt with the constraints:•xv  xu+w(u,v) for each edge (u,v)E, and xs =0.6Formatting problems as LPs•Max-flow problem:–A directed graph G=<V,E>, a capacity function on each edge c(u,v) 0 and a source s and a sink t. A flow is a function f : VVR that satisfies:•Capacity constraints: for all u,vV, f(u,v) c(u,v).•Skew symmetry: for all u,vV, f(u,v)= -f(v,u).•Flow conservation: for all uV-{s,t}, vV f(u,v)=0, or to say, total flow out of a vertex other s or t is 0, or to say, how much comes in, also that much comes out. –Find a maximum flow from s to t.7Example of max-flow problem8Formatting Max-flow problem as LPs•Maximize vV f(s,v) with constraints:•for all u,vV, f(u,v) c(u,v).•for all u,vV, f(u,v)= -f(v,u).•for all uV-{s,t}, vV f(u,v)=0.9Linear Programming (LP) (Chap.29)•Suppose all the numbers below are real numbers.•Given a linear function (called objective function)–f(x1, x2,…, xn)=c1x1+ c2x2+…+ cnxn=j=1n cjxj.•With constraints:j=1n aijxj bi for i=1,2,…,m and–xj0 for j=1,2,…,n. (nonnegativity)•Question: find values for x1, x2,…, xn, which maximize f(x1, x2,…, xn).•Or if change bi to bi , then minimize f(x1, x2,…, xn).10Linear program in slack form•Except nonnegativity constraints, all other constraints are equalities.•Change standard form to slack form:–If j=1n aijxj  bi, then introduce new variable s, and set: –si= bi - j=1n aijxj and si0. (i=1,2,…,m).–If j=1n aijxj  bi, then introduce new variable s, and set: –si= j=1n aijxj -bi and si0.•All the left-hand side variables are called basic variables, whereas all the right-hand side variables are called nonbasic variables.•Initially, s1, s1,…, sm basic variables, x1, x1,…, xn non-basic variables.11The Simplex algorithm for LP•It is very simple•It is often very fast in practice, even its worst running time is not poly.•Illustrate by an example.12An example of Simplex algorithm•Maximize 3x1+x2+2x3(29.56)•Subject to: –x1+x2+3x3  30 (29.57)–2x1+2x2+5x3  24 (29.58)–4x1+x2+2x3  36 (29.59)–x1, x2, x30 (29.60)•Change to slack form:–z= 3x1+x2+2x3(29.61)–x4=30- x1-x2-3x3 (29.62)–x5=24- 2x1-2x2-5x3 (29.63)–x6=36- 4x1-x2-2x3 (29.64)–x1, x2, x3, x4, x5, x6 013Simplex algorithm steps•Feasible solutions (infinite number of them): –A solution whose values satisfy constraints, in this example, –as long as all of x1, x2, x3, x4, x5, x6 are nonnegative. •basic solution: –set all nonbasic variables to 0 and compute all basic variables•Iteratively rewrite the set of equations such that–No change to the underlying LP problem.–The feasible solutions keep the same.–However the basic solution changes, resulting in a greater objective value each time:•Select a nonbasic variable xe whose coefficient in objective function is positive, •increase value of xe as much as possible without violating any of constraints, •xe is changed to basic and some other variable to nonbasic.14Simplex algorithm example•Basic solution: (x1,x2,x3,x4,x5,x6) =(0,0,0,30,24,36).–The result is z=3  0+0+2  0=0. Not maximum.•Try to increase the value of x1:–z= 3x1+x2+2x3(29.61)–x4=30- x1-x2-3x3 (29.62)–x5=24- 2x1-2x2-5x3 (29.63)–x6=36- 4x1-x2-2x3 (29.64)• 30: x4 will be OK; 12: x5; 9: x6. So only to 9.–Change x1to basic variable by rewriting