Simplex AlgorithmSimplex AlgorithmMath 364: Principles of Optimization, Lecture 8Haijun [email protected] of MathematicsWashington State UniversitySpring 2012Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 1 / 16Simplex AlgorithmStandard FormConvert an LP problem with m constraints into standard form:max (or min) z =nXi=1cixi= cx, s.t. Ax = bwhere c = (c1, . . . , cn) andA =a1,1a1,2· · · a1,na2,1a2,2· · · a2,n............am,1am,2· · · am,n, x =x1x2...xn, b =b1b2...bmNote that some variables xis may be slack and/or excessvariables.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 2 / 16Simplex AlgorithmStandard FormConvert an LP problem with m constraints into standard form:max (or min) z =nXi=1cixi= cx, s.t. Ax = bwhere c = (c1, . . . , cn) andA =a1,1a1,2· · · a1,na2,1a2,2· · · a2,n............am,1am,2· · · am,n, x =x1x2...xn, b =b1b2...bmNote that some variables xis may be slack and/or excessvariables.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 2 / 16Simplex AlgorithmBasic Solutions and Basic Feasible SolutionsBasic SolutionsSelect m columns of A that are linearly independent. Thecorresponding variables are called basic variables.Setting the remaining n − m non-basic variables equal to 0yields unique values for the m basic variables.Basic Feasible Solutions (bfs)Any basic solution satisfying the non-negativity constraintsis called a bfs.Two bfs’ are said to adjacent if their basic variables havem − 1 variables in common.TheoremCorner (extreme) point of the feasible region ⇔ bfs.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 3 / 16Simplex AlgorithmBasic Solutions and Basic Feasible SolutionsBasic SolutionsSelect m columns of A that are linearly independent. Thecorresponding variables are called basic variables.Setting the remaining n − m non-basic variables equal to 0yields unique values for the m basic variables.Basic Feasible Solutions (bfs)Any basic solution satisfying the non-negativity constraintsis called a bfs.Two bfs’ are said to adjacent if their basic variables havem − 1 variables in common.TheoremCorner (extreme) point of the feasible region ⇔ bfs.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 3 / 16Simplex AlgorithmBasic Solutions and Basic Feasible SolutionsBasic SolutionsSelect m columns of A that are linearly independent. Thecorresponding variables are called basic variables.Setting the remaining n − m non-basic variables equal to 0yields unique values for the m basic variables.Basic Feasible Solutions (bfs)Any basic solution satisfying the non-negativity constraintsis called a bfs.Two bfs’ are said to adjacent if their basic variables havem − 1 variables in common.TheoremCorner (extreme) point of the feasible region ⇔ bfs.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 3 / 16Simplex AlgorithmRepresentation of Feasible SolutionsLet S ⊂ Rndenote the feasible region of an LP in standard form.A non-zero vector d ∈ Rnis called a direction ofunboundedness ifx ∈ S, and c ≥ 0 ⇒ x + cd ∈ S.Representation TheoremLet b1, . . . , bkdenote all the bfs’ for an LP with feasible region Sin standard form. Any feasible solution x ∈ S can be written asx = d +kXi=1σibi,where d is the zero vector or a direction of unboundedness, andPki=1σi= 1 and σi≥ 0.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 4 / 16Simplex AlgorithmRepresentation of Feasible SolutionsLet S ⊂ Rndenote the feasible region of an LP in standard form.A non-zero vector d ∈ Rnis called a direction ofunboundedness ifx ∈ S, and c ≥ 0 ⇒ x + cd ∈ S.Representation TheoremLet b1, . . . , bkdenote all the bfs’ for an LP with feasible region Sin standard form. Any feasible solution x ∈ S can be written asx = d +kXi=1σibi,where d is the zero vector or a direction of unboundedness, andPki=1σi= 1 and σi≥ 0.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 4 / 16Simplex Algorithmmax (or min) z =nXi=1cixi= cx, s.t. Ax = bA Consequence of Representation TheoremIf an LP has an optimal solution with finite objective functionvalue, then it has an optimal bfs.Proof. Let x∗be an optimal solution, then x∗= d +Pki=1σibi.1Observe that cd cannot be negative. Why?2If cd > 0, then for any scalar L > 0, x0= Ld +Pki=1σibiisalso feasible, and thus the objective function value cx0canbe arbitrarily large, leading to the contradiction.3Thus cd = 0, and cx∗=Pki=1σicbiis the optimal value.4Suppose that b1is the bfs with the largest objectivefunction value, then we must have cx∗= cb1.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 5 / 16Simplex Algorithmmax (or min) z =nXi=1cixi= cx, s.t. Ax = bA Consequence of Representation TheoremIf an LP has an optimal solution with finite objective functionvalue, then it has an optimal bfs.Proof. Let x∗be an optimal solution, then x∗= d +Pki=1σibi.1Observe that cd cannot be negative. Why?2If cd > 0, then for any scalar L > 0, x0= Ld +Pki=1σibiisalso feasible, and thus the objective function value cx0canbe arbitrarily large, leading to the contradiction.3Thus cd = 0, and cx∗=Pki=1σicbiis the optimal value.4Suppose that b1is the bfs with the largest objectivefunction value, then we must have cx∗= cb1.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 5 / 16Simplex Algorithmmax (or min) z =nXi=1cixi= cx, s.t. Ax = bA Consequence of Representation TheoremIf an LP has an optimal solution with finite objective functionvalue, then it has an optimal bfs.Proof. Let x∗be an optimal solution, then x∗= d +Pki=1σibi.1Observe that cd cannot be negative. Why?2If cd > 0, then for any scalar L > 0, x0= Ld +Pki=1σibiisalso feasible, and thus the objective function value cx0canbe arbitrarily large, leading to the contradiction.3Thus cd = 0, and cx∗=Pki=1σicbiis the optimal value.4Suppose that b1is the bfs with the largest objectivefunction value, then we must have cx∗= cb1.Haijun Li Math 364: Principles of Optimization, Lecture 8 Spring 2012 5 / 16Simplex Algorithmmax (or min) z =nXi=1cixi= cx, s.t. Ax = bA Consequence of Representation TheoremIf an LP has an optimal solution with finite objective functionvalue,