Integer programs solvable as LP Sommer gentry November 18.2003 Transportation problem Sources and sinks connected by links Objective: Minimize shipment cost 地 pittsburgh Detroit 40 widgets 20 widgets Baltimore Atlant 20 widgets 30 widget Denver 15 widgets 75 widgets S9 50 widgets
Integer programs solvable as LP Sommer Gentry November 18, 2003 Transportation problem • • 50 widgets Baltimore Detroit Atlanta Denver Pittsburgh Boston Houston 20 widgets 30 widgets 75 widgets 40 widgets 20 widgets 15 widgets $9 $7 $4 Sources and sinks connected by links Objective: Minimize shipment cost
Assignment problem Persons and tasks connected by links Objective: Minimize total task time minutes Carburetor Manny 4 minutes Valves Mo 9 minutes Fluid Transportation LP Maximize z=c1x1+…+C1nxn+C21x21+…+Cn1xn1+…+ CX Subject to x1+x12…+x1n=a1 Supplies x+x +x +x=b Demands xn+x2n+…+xm=b ∑a=∑b ≥0 ≥0
Assignment problem • • Manny Valves Moe Jack Carburetor Tires Fluids 9 minutes 7 minutes 4 minutes Transportation LP , ... ... ... Subject to ... Maximize ... ... ... 11 1 2 11 21 1 1 1 2 11 12 1 1 11 11 1 1 21 21 1 1 t t ¦ ¦ mn i j n n mn n m m m mn m n n n n n mn mn x x a b x x x b x x x b x x x a x x x a Z c x c x c x c x c x Supplies Demands Persons and tasks connected by links Objective: Minimize total task time 0, 0
Courtesy of Sommer Gentry. Used with permission Basis theory every basis contains the same number of variables as the number of constraints. The simplex algorithm only searches feasible bases by design but any set of m variables is not guaranteed to form a feasible basis subject to 2/3x2+x3+1/3x5=4 4 x1+2/3x2 +3x5=-2 x1>0,…,x5>0 Find a starting basic feasible solution The simplex algorithm examples shown so far have all less-than inequalities. In these cases the starting feasible basis is obvious: all the slack variables are basic and the others non-basic. How can we find a feasible basis if given equality constraints? Maximize Z=c1x1+…+Cnx Subject to aux +.+aux=b an1x1+…+amxn=bn x1≥0,,xn≥0
Basis theory • as the number of constraints. The simplex algorithm only searches feasible bases by design, but any set of m variables is not guaranteed to form a feasible basis. subject to: -2/3x2+ x3 +1/3x5 = 4 x2 +x4 = 0 x1 +2/3x2 + 3x5 = -2 x1 >0, …, x5 >0 Find a starting basic feasible solution • have all less-than inequalities. In these cases the starting feasible basis is obvious: all the slack variables are basic and the others non-basic. How can we find a feasible basis if given equality constraints? , ... Subject to ... Maximize ... 1 1 1 11 1 1 1 1 1 t t n m mn n m n n n n x x a x a x b a x a x b Z Every basis contains the same number of variables The simplex algorithm examples shown so far 0, 0. c x c x Courtesy of Sommer Gentry. Used with permission
Answer: write this as a new Lp! Add to each equation one artificial variable Objective: Minimize the sum of the artificial variables. Multiply by -l if necessary to find positive b Minimize z xn+1+…+xn+m Subject to aux,+.+a,x, +ru, amIx +x=b x1≥0,,xn≥0,xn+1≥0.x+m≥0. Phase i of simplex algorithm The new LP on the previous slide is phase I of the general simplex algorithm. Note that an inconsistent system of equations will be revealed as such by a positive Phase I optimum. Thus, LP can function as a check for consistency of linear systems of equations Phase Ii uses as a starting basis the feasible corner point solution found in Phase I
Answer: write this as a new LP! • artificial variable. Objective: Minimize the sum of the artificial variables. bi , 0 0. ... Subject to ... Minimize ... 1 1 1 1 11 1 1 1 1 1 t t t t n n n m m mn n n m m n n n n n m x x x x a x a x x b a x a x x b Z x x Phase I of simplex algorithm • general simplex algorithm. Note that an inconsistent system of equations will be revealed as such by a positive Phase I optimum. Thus, LP can function as a check for consistency of linear systems of equations. • point solution found in Phase I. Add to each equation one – Multiply by –1 if necessary to find positive 0, 0, The new LP on the previous slide is phase I of the Phase II uses as a starting basis the feasible corner
Transportation Basis There are m+n equations in a transportation problem, but one row is dependent so there are m+n-1 rows in each simplex tableau Theorem: All bases are triangular. with mn-(m+n-1) nonbasic variables set to zero, equations can be reordered triangularly Theorem: If supplies and demands are Integers, every corner point solution Is Integer Integer basic feasible solutions X+r.trntx j j +x+x 41 x;+x21…+x2 j ++ru=a nk +x+x nl
Transportation Basis • m+n equations in a transportation problem, but one row is dependent so there are m+n-1 rows in each simplex tableau. • mn-(m+n-1) zero, equations can be reordered triangularly. • integers, every corner point solution is integer. Integer basic feasible solutions mk ml kl n ij ik jk ml kl m jk ij lk jk ml kl x x x b x x x x x a x x x x x x a ... ... 1 There are Theorem: All bases are triangular. – with nonbasic variables set to Theorem: If supplies and demands are