Chapter 6Linear Programming: The Simplex Method

1 Chapter 6 Linear programming : TheSimplex MethodWe will now consider LP (Linear programming ) problems that involvemore than 2 decision variables. We will learn an algorithm called thesimplex Method which will allow us to solve these kind of Problem in Standard FormWe start with defining the standard form of a linear programmingproblem which will make further discussion linear programming problem is said to be astandard max-imization problem in standard formif its mathematicalmodel is of the following form:MaximizeP=c1x1+c2x2+..+cnxnsubject toa11x1+a12x2+..+a1nxn b1 am1x1+am2x2+..+amnxn bmx1, x2, .. , xn 0wherex1, x2, .. , xnaredecisionvariables,c1, .. , cn,a11, .. , amnare any real numbers, andb1, .. , bm 0 arenonnegative real :Any linear programming problem (in the form we definedearlier) can be converted intothe standard maximization problemin standard 6.

2 Linear programming : The Simplex MethodInitial System and Slack VariablesRoughly speaking, the idea of the Simplex Method is to represent anLP problem as a system of linear equations, and then a certain solu-tion (possessing some properties we will define later) of the obtainedsystem would be an optimal solution of the initial LP problem (if anyexists). The Simplex Method defines an efficient algorithm of findingthis specific solution of the system of linear , we need to start with converting given LP problem into asystem of linear equations. First, we convert problem constraints intoequations with the help ofslack the following maximization problem in the standard form:MaximizeP= 5x1+ 4x2(1)subject to4x1+ 2x2 322x1+ 3x2 24x1, x2 0 The variabless1ands2are calledslack variablesbecause each makesup the difference (takes up the slack) between the left and right sidesof an each problem constraint of the originalproblem we introduce a single slack 6.

3 Linear programming : The Simplex MethodTherefore, we get4x1+ 2x2+s1=32(2)2x1+ 3x2+s2=24x1, x2, s1, s2 0 Note that each solution of (2) corresponds to a point in the feasibleregion of (1). Also note that theslack variables should be non-negativeas well. If slack variable is negative, then the right-hand sideof corresponding problem constrain should be larger than the left-hand, , this constraint would be , we also add the objective function to (2) treatingPas yet 5x1+ 4x2= Therefore, we get4x1+ 2x2+s1= 322x1+ 3x2+s2= 24 5x1 4x2+P= 0x1, x2, s1, s2 0 The above system is called theinitial system. Again, every solutionof the initial system (taking into account nonnegative constrains) cor-responds to some point in the feasible region of the original LP (andvice versa!)

4 , and in addition the initial system incorporates informa-tion about the objective function of the original LP. Therefore,oneof the solution of the initial system should be an optimalsolution of the original LP(if any exists). Clearly, theinitialsystem has infinitely many solutions, so the key question iswhich one of these solutions is an optimal solution of theLP?3Ch 6. Linear programming : The Simplex MethodBasic Solutions and Basic Feasible SolutionsWe now define two important types of solutions of the initial systemsthat we should focus our attention on in order to identify the optimalsolution of the (Basic Solution)Given an LP withndecision variables andmconstraints, abasicsolutionof the corresponding initial system is a solution of theinitial systems (not taking into account nonnegative constraints)in whichnof the variablesx1.

5 , xn, s1, .. , smare equal to :the list of variablesx1, .. , xn, s1, .. , sm,nof whichshould be zero, does not (Basic Feasible Solution)If a basic solution of the initial system corresponds to a certainpoint in the feasible region of the original LP, then it is called abasic feasible feasible region of (1) looks like 11357911131517 11357911131517x1x2(8,0)(6,4)(0,8)(0,0)(1 2,0)(0,16)4Ch 6. Linear programming : The Simplex MethodIn 2-dimensional case (2 decision variables), the set of basic solutionsis the of pairwise intersections of boundary lines of all problem con-straints. In turn, the set of basic feasible solutions is the set of thecorner points. Indeed,5Ch 6. Linear programming : The Simplex MethodTheorem 1 (Fundamental Theorem of Linear Pro-gramming: Another Version)If the optimal value of the objective function in a linear program-ming problem exists, then that value must occur at one or moreof the basic feasible solutions of the initial , by checking all basic solutions for feasibility and optimality we can solve anyLP.

6 In our example, this is quite easy because there are 6 basic solutions and just4 of them are feasible. However, in a lot of real-world LP problems the numberof variables and the number of constraints are much higher. For example, if aproblem hasn= 30 decision variables andm= 35 problem constraints, thenumber of possible basic solution becomes approximately3 1018. It will takeabout15 yearsfor an average modern personal computer to check all thesesolutions for feasibility and Simplex Method describes a smart way to find much smaller subset ofbasic solutions which would be sufficient to check in order to identify the optimalsolution. Staring from some basic feasible solution calledinitial basic feasiblesolution, the Simplex Method moves along the edges of the polyhedron (verticesof which are basic feasible solutions) inthe direction of increase of theobjective functionuntil it reaches the optimal 6.

7 Linear programming : The Simplex MethodSimplex TableauThe Simplex Method utilizes matrix representation of the initial systemwhile performing search for the optimal solution. This matrix repre-sentation is calledsimplex tableauand it is actually the augmentedmatrix of the initial systems with some additional s write down the augmented matrix of the initial system corre-sponding to the LP (1). 42100322301024 5 40010 At each step of the Simplex Method a particular basic feasible solutionis considered. Information about this solutions is also represented inthe Simplex tableau. Recall that we defined a basic feasible solution asa solution withnvariables being zero. In this context, we haveDefinition (Basic and Nonbasic Variables)The variables of a basic solution that are assumed to be zero arecallednonbasicvariables.

8 All the remaining variables are at each step, we need define the list of basic and nonbasic that ifnnonbasic variables are assigned the value 0, the corre-sponding values of the nonbasicm+ 1 variables can be determined bysolving the corresponding system of linear :How do we decide which variables are basic and whichare not? In particular, how can we decide what variables would bebasic and what would be nonbasic on the very first step of the simplexmethod (how do we choose the initial basic feasible solution)?7Ch 6. Linear programming : The Simplex MethodTherefore, for our example we have 42100322301024 5 40010 Pivot OperationSo far, we set up asimplex tableauand identified theinitial basicfeasible solutionby determining basic and nonbasic variables.

9 Thisis the first step of the Simplex each further step the Simplex methodsswaps one of the non-basic variables for one of the basic variables(so it moves toanother vertex of the polyhedron) in the way such that the value of theobjective function is improved(becomes higher). If improve-ment of the objective function is not possible, then we got an 6. Linear programming : The Simplex MethodSince we do not choose ourselves which variables are basic but ratherdetermine them by reading the Simplex tableau, in order for such swapto happen the Simplex tableau should be changed. This is done with thehelp ofpivot operations. However, before doing this transformationwe need to decide ourselves which nonbasic variable should becomebasic and vice (Entering and Exiting Variables)Anonbasicvariable that is chosen to become abasicvariableat a particular step of the Simplex Method is that is chosen to become anonbasicvariable at aparticular step of the Simplex Method is calledexiting back to our example 42100322301024 5 40010 Let s first select theenteringvariable:9Ch 6.

10 Linear programming : The Simplex MethodDefinition (Pivot Column)The column corresponding to theenteringvariable is called thepivot , let s select theexitingvariable:10Ch 6. Linear programming : The Simplex MethodDefinition (Pivot Row and Pivot Element)The row corresponding to theexitingvariable is called element at the intersection of thepivot columnand thepivotrowis called thepivot , we have 42100322301024 5 40010 11Ch 6. Linear programming : The Simplex MethodNow, when we know which variable is entering and which is exiting weneed to perform row operations on the tableau so that thepivot ele-ment is transformed into 1 and all other elements in thecolumn into 0 s. This procedure for transforming a nonbasic vari-able into a basic variable is called apivot operation, orpivoting,and is summarized a pivot operation has the following effects:1.