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
Proof: All bases are triangular Lemma: Some row has exactly one basic variable Assume each row has at least two basic variables Let k be the number of bas variables Then there are at least 2n basic variables in the supplies section, and at least 2m basic variables in the demands section thus k >2n. k>2m, so k >m+n. But since there are only m+n- independent equations, there is a contradiction Proof: All bases are triangular Lemma: Exclusion of any redundant equation from the original system leaves an equation in exactly one basic variable Drop some equation as redundant, say, the last demand equation Let k' be the new number of basic variables. Again make the contrary assumption to get k>2(n-1) k>2m. There was at least one basic entry in the equation excluded, so k >k+I. Then k>m+n-1/2, which again contradicts k <m+n-1 Then, successively delete the row having a single basic variable and repeat the argument for the reduced array, establishing the theorem
Proof: All bases are triangular • variable variables. Let k be the number of basic variables. Then there are at least 2n basic variables in the supplies section, and at least 2m basic variables in the demands section, thus k >2n , k >2m , so k >m+n. But since there are only m+n-1 independent equations, there is a contradiction. Proof: All bases are triangular • from the original system leaves an equation in exactly one basic variable. – equation. Let k’ be the new number of basic variables. Again make the contrary assumption to get k’ >2(n-1) , k >2m. There was at least one basic entry in the equation excluded, so k >k’+1. Then k >m+n-1/2, which again contradicts k <m+n-1. • basic variable and repeat the argument for the reduced array, establishing the theorem. Lemma: Some row has exactly one basic – Assume each row has at least two basic Lemma: Exclusion of any redundant equation Drop some equation as redundant, say, the last demand Then, successively delete the row having a single
Network optimization The transportation problem is the simplest network optimization problem. More complex problems include transshipment nodes, arc capacities, and nonlinear objective functions Network optimization is a well-developed computer science field offering specialized algorithms and approximation techniques for myriad practical problems. Shortest paths maximum flow, traveling salesman problem, minimal delay routing problems are further examples
Network optimization • network optimization problem. More complex problems include transshipment nodes, arc capacities, and nonlinear objective functions. Network optimization is a well-developed computer science field offering specialized algorithms and approximation techniques for myriad practical problems. Shortest paths, maximum flow, traveling salesman problem, minimal delay routing problems are further examples. The transportation problem is the simplest
