Deterministic Optimiz ISYE 6669
Popular in Course
Popular in Industrial Engineering
This 0 page Class Notes was uploaded by Maryse Thiel on Monday November 2, 2015. The Class Notes belongs to ISYE 6669 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/234214/isye-6669-georgia-institute-of-technology-main-campus in Industrial Engineering at Georgia Institute of Technology - Main Campus.
Reviews for Deterministic Optimiz
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
13 The Simplex Algorithm The linear programming examples discussed in the introduction describe situations where one is required to minimize or maximize a linear function of several variables subject to linear equality or inequality constraints on the variables Many of the methods that have been developed for solving such problems are based on geometric concepts So we begin our discussion of solution techniques with a geometric description of linear programming problems in two and three variables Consider the problem maximize 3x1 2x2 31 subject to x1 x2 S 6 x1 x2 S 2 3x1 x2 S 12 x1x2 Z 0 The region of the x1 x2 plane described by these constraint inequalities is shown shaded in the gure 31 This shaded region is called the feasible region for problem 31 It is the set of values of the variables that satisfy the constraints The feasible region for a linear programming problem is always a polyhedron In Fig 31 we have also plotted the equation of the objective function z 3x1 2x2 for several values of z As z increases the line described by this equation moves across 3x12x2 16 3x12x2 10 3x12x2 5 3x1x2 12 Figure 31 the feasible region in a direction normal to the line From this it is clear that the maximum value z can attain 0n the feasible region occurs at a point where two of the lines describing the feasible region intersect We call such a point a vertex of the constraint polyhedron In general at least one solution of a linear programming problem if solutions exists occurs at a vertex of the constraint polyhedron If this polyhedron is unbounded a solution may not exist The problem 31 can be stated in matrix notation as Maximize cx Subjectto Ax S b x Z 0 For the purpose of describing the simplex algorithm for solving such problems it is convenient to convert the inequality constraints AxS b to equality constraints We do this by adding slack variables to the model which in the case of problem 3 l converts it to maximize 3x1 2x2 32 subject to x1 x2 x3 6 x1 x2 x4 2 3x1 x2 x5 12 x1x2x3x4x5 Z 0 When 3 l is written in this form we see that each of the lines in Fig 31 is represented by one of the equations x10x2 0x3 0x4 0x5 0 With this in mind we rephrase our statement that a solution occurs at a vertex of the feasible region to say a solution occurs at a feasible point where two of the variables in 32 are zero At each feasible point in Fig 31 where two ofthe variables in 32 are zero the remaining three variables are positive So we can also characterize a solution of 32 as one of the feasible points where three of the variables in 32 are positive and the remaining ones are zero In general for a linear programming problem stated in the form minimize cx 33 subjectto Axbx20 where A is an m X 71 matrix an optimal solution occurs at a point where nm of the variables are zero Thus in a problem like 33 involving m equality constraints and n variables we can confine our search for an optimal solution to feasible points where nm of the variables have the value zero This fact will aid us in our search for an optimal solution But as we will see later this search will be complicated by the fact that the remaining m variables need not all be positive For example if we were to add the constraint 3x12x2 S 15 34 to the model 3 l and change the objective slightly to maximize 4x1 2x2 35 we would have to add a new slack variable and the constraints 3x12x2 x6 15 x6 2 0 to the model 32 However adding the constraint 34 to the model 31 does not change the feasible region at all since 34 is implied by the solution of 3 1 And the optimal solution of the modi ed problem occurs at the same vertex But now this vertex is the intersection of three lines namely x1 0c3 0 and x6 0 The remaining three variables are positive So here we have an example of a linear programming problem involving four linear equality constraints but only three positive variables in the optimal solution This means that in general the number of equality constraints in the model 33 is only an upper bound on the number of positive variables in some solution of 33 Our twodimensional example showing a case of 33 where the optimal solution has fewer than m positive variables was contrived by adding a redundant constraint to the problem 31 A vertex of a twodimensional polyhedron can always be described by the intersection of two lines Thus if there are no unnecessary constraints in such a problem the number of positive variables in an optimal solution will equal the number of linear equality constraints However in higher dimensions there are examples where the number of positive variables in an optimal solution is smaller than the number of equality constraints even when all the constraints are essential for describing the feasible region For example consider the threedimensional problem 5 m1n1mlze x1 x2 2x3 36 subject to x1 x3 S 3 4 x2 x3S34 x1x2 x3Sl x1x2x3 Z 0 The feasible region for this problem is shown in the following figure After adding slack x2x334 Figure 32 x1x2x3 34 variables to the model we obtain a case of 33 with three equality constraints However the optimal solution of this problem has x3 l and all other variables equal to zero Moreover each of the constraints are essential in de ning the feasible region In particular if the constraint x1 x2 x3 S l is dropped the optimal solution changes to x1x2 34 x3 0 The above examples demonstrate that for the linear programming problem 33 When an optimal solution exists there is always one having at most m positive variables We will now give a more precise description of optimal solutions of 33 A point x satisfying the constraints in 33 is said to be afeasible point for 33 Let B be a m X m nonsingular submatrix of A Such a matrix is said to be a basis matrix or simply a basis for 33 For any basis matrix B we will denote the components of x corresponding to columns in B by xB The columns in A that are not in B will be denoted by AN and the corresponding components of x will be denoted by xN Similarly the components of c corresponding to xB will be denoted by CB and those corresponding to xN will be denoted by cNThe components of x3 are called basic variables and those of xN are called nonbasic variables In general upper case letters will refer to sets and lower case numbers to elements Thus A j will refer to the 1 column of A If BxB b and xN 0 x is said to be a basic solution of 33 IffuIther x3 20 x is said to be a basicfeasible solution of 33 If x3 gt 0 x is said to be a nondegenerate basic feasible solution of 33 Finally if x3 20 but has at least one zero component x is said to be a degenerate basic feasible solution We have just seen two examples of linear programming problems whose optimal solutions are degenerate basic feasible solutions It turns out that among the solutions of a linear programming problem there is always one which is a basic feasible solution This is the essence of the following theorem Theorem31 If problem 33 has a feasible solution it has a basic feasible solution Moreover if 33 has an optimal solution it has a basic feasible solution which is optimal The impottance of this result is that it allows us to restrict our search for an optimal solution of a linear programming problem to the set of basic feasible solutions Clearly 33 has only a finite number of basic feasible solutions since there are at most 391 ways of selecting a basis matrix from the columns of A Thus in principle we could find an optimal solution of 33 by examining all of its basic feasible solutions But this would be inefficient Especially if we had no way of checking whether or not a given basic feasible solution is optimal In this na39139ve approach we could start with an optimal solution and not know it until we had compared it with all others The simplex algorithm is a much more efficient way of finding an optimal solution One of its most important features is a method of testing a given basic feasible solution for optimality Before we describe the simplex we explain this optimality test Let x be any feasible solution for 33 and let B be any basis matrix We will denote the vector Bilb by b The equation Ax b can be written as BxB ANxN b Solving for x13 gives xB B 1b B 1ANxN b BilAjxj IEN Substituting this in OK gives 2 ox chB chN cBB 1bcN cBB lANxN This expresses z in terms of the nonbasic variables Let I CBBT1 We can then write this equation as z7rbjEZNcj m4jxj 37 The following theorem gives a simple optimality test for a basic feasible solution Theorem 32 Let x denote a basic feasible solution for 33 corresponding to the basis matrix B and define I 03371 If m4 S C for each nonbasic variable xj 38 x is optimal for 33 Proof By definition x Bilb and x 0 Therefore 1 cx chB chN 033 b 7rb Equation 37 shows that cx Z Irb cxi for any feasible solution X This proves the optimality of x This theorem gives a sufficient condition for a basic feasible solution of 33 to be optimal It is by no means a necessary condition If x is a degenerate basic feasible solution it may be associated with several basis matrices Some of them may not satisfy the optimality test 38 Example Consider the following problem which is the modification of 3 I discussed above minimize 4x1 2x2 39 subject to x1 x2 x3 6 x1 x2 x4 2 3x1 x2 x5 12 3x13x2 x615 x1xzx3x4x5x6 Z 0 The reader should observe that we have added the constraint 3x1 2x2 S 15 to the problem 31 This does not decrease the feasible region shown in Fig 31 but introduces a degenerate vertex at x1 x2 3 3 The basis 1 1 BA1A2A4A5 3 has cB 4 2 0 0 Qt ID ID I OOHO OHOO The equation AB 63 has solution 72 071393 0 71 2 74 2 Thus 71113 2 gt 0 03 So the optimality condition 38 is not satis ed However the equation Bx B b has the solution x1 3 x2 3 x4 2 x5 0 This agrees with the optimal solution of 31 found by our analysis of Fig 31 Thus B is an optimal basis matrix for 39 It turns out that there are other basis matrices associated with the basic feasible solution x1 3 x2 3 x3 0 x4 2 x5 x6 0 One such matrix is 1 1 0 0 1 1 1 0 BA1A2A4A6 3 1 0 0 3 2 0 1 This basis also has 63 4 4 0 0 But in this case the equation 728 63 has solution 71 1 72 0 73 1 74 0 This solution satisfies conditions 38 and this proves the optimality of x Linear programming problems have the interesting property that among their optimal solutions there is at least one which is a basic solution and for this solution there is a basis matrix which satis es the optimality test 38 We summarize this result in the following theorem Theorem 33 If 33 has an optimal solution it has an optimal basic feasible solution with basis matrix B such that the vector 7139 CEB 1 satis es 7124 S cj for each column A j in A The proof of this theorem follows from the convergence proof of the simplex algorithm which we are about to describe Let B be a basis matrix corresponding to a basic feasible solution of 33 Compute 7139 CEB 1 and B Bilb the values of the basic variables Find a nonbasic column AAv satisfying RAJ gtcJv If no such column exists stop B satisfies the optimality test 38 so the current basic feasible solution is optimal The current value ofthe objective function is z 035 cBBilb Irb IfB is not an optimal basis we must replace it by a new feasible basis which gives a smaller value to the objective function Compute d BTIAX and observe that for any value of 6 BE 6d6AS b 310 Let x denote the vector with xJv 6 and whose components corresponding to the columns in B are given by B 6d and whose remaining components are zero 310 can then be written as Ax b Moreover cxcBB 6dcs6cBBcs m456 311 Thus if 6 Z 0 and 5 6d 2 0 x is feasible for 33 and cx Zirb If all components of the vector d are S 0 then 5 6d 2 0 for all values of 6 20 In this case it follows from 3 l 1 that the objective cx can be made arbitrarily small by taking 6 sufficiently large In this case we say problem 33 is unbounded If d has at least one positive component we choose 6 as large as possible subject to the condition B 6d 2 0 That is we take 5 6 min 7 01 gt 0 51 Assume this minimum is attained at 139 r Then equation 310 expresses b as a nonnegative combination of the column AAv and the columns of B excluding the one in position r Let B denote the matrix obtained from B by replacing the column in position r with A Assume for the moment that E is nonsingular Equation 310 shows that the equation Ex bhas a nonnegative solution fcl which satis es c xg CB 5 19acJv 7139AJ19 S chB with strict inequality holding if 19 gt 0 Thus E is a basis matrix whose corresponding basic solution is feasible and has an objective value which is at least as good as the one corresponding to B The process by which we went from B to E constitutes one iteration of the simplex algorithm To complete the description of this iteration we must show that E is nonsingular Let E denote the matrix obtained from the identity matrix by replacing column r with d Then clearly E BE The element in the diagonal position rrof E is d gt 0 This means that E is nonsingular In fact it is easy to see that if 0 d1 0 0 1 d2 0 0 3 E d anddr 0then 0 0 dm 1 0 d1d 0 1 d2d E l 0 E z 312 ld 39 39 0 0 dmd 1 It follows that 3 1 E lB l Thus in going from one iteration of the simplex algorithm there is a simple procedure for updating the inverse of the basis matrix We will elaborate on this when we discuss implementation issues in Section 14 The following table gives a formal description of the simplex algorithm The Primal Simplex Algorithm Step 1 Let B be a feasible basis Compute b Bilb and I 63371 Step 2 Let E C 7139Aj j1n prossible nd an index s such that EAv lt 0 If no such s exists stop The current basis is optimal Step 3 Compute d BilIX If d S 0 stop The problem is unbounded If d has some positive components perform the following minimum ratio test 639 min 01 gt 0 139 MM Step 4 Let r denote a value of 139 where the minimum in Step 3 is attained Replace column r in B with column A and return to Step 1 Table 31 Termination In our discussion of degenerate basic feasible solutions we alluded to the fact that they contribute to the dif culty of solving large linear programming models In turns out that the simplex algorithm as we have stated it may not terminate if the linear programming model has one or more degenerate basic feasible solutions However this is not a major concern In practice the algorithm seems to always terminate after a finite number of steps Of far greater concern is the fact that in the presence of degeneracy the algorithm may perform many iterations without advancing from a given basic feasible solution This phenomenon is known as stalling Since a linear programming model has only finitely many basic feasible solutions and the simplex algorithm only visits basic feasible solutions if the algorithm does not terminate it eventually encounters a given basis for the second time From that point on it repeats a cycle starting at that basis indefinitely This phenomenon is known as cycling As we have said cycling is rare in practice Nevertheless techniques have been devised for dealing with cycling and stalling We will describe some techniques for avoiding cycling when we come to implementation issues for the simplex algorithm in Section 511 We will discuss antistalling techniques in Chapter 6 For the time being we content ourselves with the following observation Theorem 34 If problem 33 has no degenerate basic feasible solutions the simplex algorithm applied to it terminates with an optimal solution or with an indication that the problem is unbounded Proof If the problem has no degenerate basic feasible solutions the vectors 5 computed in Step 1 all have strictly positive components Thus the values of 639 computed in Step 3 are strictly positive It therefore follows from 311 that there is a strict improvement in the objective function Thus no basis can repeat so the algorithm does not cycle Thus the algorithm terminates in Step 2 with an optimal solution or it terminates in Step 3 with an indication that the problem is unbounded Dantzig has given imperial evidence that the simplex algorithm requires on average between m and 2m iterations to solve 33 If the algorithm requires more than m iterates not all the variables entering the basis can remain basic throughout the process So in general during the course of the simplex algorithm some variables go in and out of the basis It is an interesting fact that if a variable leaves the basis on some iteration it will not reenter on the very next iteration To see this assume without loss of generality that B consists of the first m columns of A Let It 01313quot1 and assume that 7545 gt c for some sgt m and that A enters the basis Let A denote the column that leaves the basis matrix Let 3 denote the new basis matrix and let I c l denote the new dual variable We must show that 72A g c Actually we will prove the stronger result 784 lt 0 Let d 13quotle denote the update of the entering column Then A d1A1d2A2 dmAm This equation implies that CirMr 7Ms EdiMi 65 drcr gdici il i r 0 drcr cBB 1AJ cx 71lx drcr Since cx 7124 lt 0 we have 61724 lt drcr And since 61 gt 0 this implies that 7714 lt c as claimed The Simplex Tableau The version of the simplex algorithm we have described is known as the revised simplex algorithm Given a basis B it requires one to solve the equations BxBb 7EBCB and to find the smallest ofthe numbers 0 m4 j l n This determines the column that wants to enter the basis Given the entering column call it AX we must compute d B IAJv and perform a ratio test to determine the column that leaves the basis For calculations on small problems it is sometimes more convenient to carry out these calculations on a matrix containing the LP data A b and c This matrix is called a simplex tableau The rst tableau is given by z x RHS l c 0 0 A b and is interpreted to read zcx and Axb 313 Given a feasible basis B the rst step of the simplex algorithm essentially asks us to write the basic variables in terms of the nonbasic ones 2 is always treated as a basic variable From the equations BxB 2 ijj b zchB Z cjxj jEN jEN we have x3 B 1b IZ Bilijj and z7rb Hz 0 71ljxj JEN jEN where I 03371 This says that when we solve the m l equations 313 for the m l variables 2 x B we compute all the quantities required by one step of the simplex algorithm It is convenient to solve these equations directly as they appear in the simplex tableau For example consider problem 32 Its rst tableau is 2 x1 x2 x3 x4 x5 RHS l 3 2 0 0 0 0 T1 0 Q l l 0 0 6 0 l l 0 l 0 2 0 3 l 0 0 l 12 Suppose we start the simplex algorithm with x1 4 x3 2c4 6 in the basis The basic variables 2 and x4 each appears in only one equation We can eliminate x1 from all but the second equation by successively multiplying row 2 by 3 l 3 and adding the result to rows 1 3 and 4 respectively This operation is known as pivoting on the circled l in tableau 1 This gives the tableau l 0 l 3 0 0 18 0 l l l 0 0 6 0 0 2 l l 0 8 0 0 2 0 l 6 We can eliminate x3 from all but the last equation in this tableau by pivoting on the circles element This gives the tableau 10 100112 T011300134 2 004301136 00 10 132 This tableau expresses the basic variables in terms of the nonbasic ones In particular it shows that z12x2 x5 Thus in order to increase 2 we must increase x2 If we increase x 2 while holding x5 at 0 the equations in T2 state that L x1 4 3x2 x3 2 xz x4 6 gxz In vector notation this can be written as x3 B lb 434in2 I dxz The maximum amount we can increase x2 by without driving a basic variable negative is given by di gt 0 di Notice that these ratios can be computed directly from the RHS column and the x2 column in T2 The smallest ratio occurs for 139 3 so the third variable in the basis matrix must be replaced by A2 From the positions of the identity columns in T2 we see that currentlyB 141144 A3 Thus the new basis is given by B A1 A4 A2 The equations in T2 can be solved for the new basic variables in terms of the nonbasic ones by pivoting on the circled element in T2 Note that the pivot element is at the intersection of the incoming column and the row that wins the ratio test This is how the pivot element is chosen in the general case The pivoting operation on T2 gives the tableau 100150515 010 5053 T3 000 2112 001150 53 This tableau is optimal since there are no negative entries left in the first row The values of the basic variables can be read directly from the tableau x13 x23x42 Example Equation 311 shows that when the column A enters the basis the objective function cx decreases by the amount 65X This suggests that in Step 2 of the simplex algorithm 3 should be chosen to make EX is as small as possible This is Dantzig s rule for selecting the variable to enter the basis In Dantzig s Book p 160 Dantzig reports based on empirical evidence that when this rule is used for problems having m S 50 constraints the simplex algorithm usually terminates in fewer than 3m 2 iterations The example we are about to give has m 5 constraints and the simplex algorithm using Dantzig s rule requires 2m iterations for its solution In the next Section we will discuss a procedure for selecting the entering variable that on average performs better than the Dantzig rule The worst case behavior of the simplex algorithm will be discussed in Section Consider the problem min cx Ax b x Z 0 where c 4 4 4 5 22 0 l 0 5 0 7 2 4 and b COD NO onoo Hgooo mooom ooooH oooHo COD 00 OD OOO Hoooo oohom Hoooo mume Suppose we start the simplex algorithm with the basis 4 2 0 BlA5gtA6gtA7gtA8gtA9 0 0 2 OOOOH OOOHO OOHOO Ot OOO It is easy to check that the corresponding basic variables are Bflb 32133 45T Thus Bl is afeasible basis We have cBl 22 0 1 0 12 and the vector In 0101211 satis es IrlBl cBl The objective value corresponding to El is 210131 lb772 To nd an improved basis we compute min cj inlAj 1 j e N c4 1A4 718 This shows that x4 wants to enter the basis The vector d Bf1A4 is given by d1212004T The ratio test gives 19 32 al2 1312 Thus A6 leaves the basis The new basis is 24 0 0 0 0 0 0 1 0 0 BzA5A4A7A8A9 0 0 0 1 0 0 4 0 0 1 2 1 0 0 0 and the corresponding values of the basic variables are x5 131 19d132 1312122324 x4 61312 x7 13 19d3 3 x8 E4 6d4 4 x9 55 19d5 5 1312423 We combine these values in the vector 1 232413123 4 23 The cost coefficients associated with these variables are 032 22 75 1 0 12 and the new objective value is Z2 52124 lt 77292424Zl The solution ofthe equation sz ch is y 32 1 0 12 7 A brief calculation gives Ec yA 35 6 45 0 015 0 0 0 7 25 Following Dantzig s rule we allow x2 to enter the basis Let dBglAz00210T The ratio test in Step 3 gives 19 53 d3 32 Thus x7 leaves the basis and the new basis matrix is 24 0 0 0 0 0 0 2 0 0 B3A5A4A2A8A9 0 0 1 1 0 0 4 0 0 1 2 1 0 0 0 The corresponding basic variables are x5 I 1 6d12324 x4 42 6512 1312x2 632 x8 E4 6d4 4 3252x9 55 6d5 23 The corresponding cost coefficients are CB3 22 5 40l2 The new objective value is 23 033x33 10 lt 22 Continuing in this way the simplex algorithm generates the following sequence of basis matrices
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'