Principles of Optimization
Principles of Optimization Math 364
Popular in Course
Popular in Mathematics (M)
This 4 page Class Notes was uploaded by Ashley Ernser II on Thursday September 17, 2015. The Class Notes belongs to Math 364 at Washington State University taught by B. Krishnamoorthy in Fall. Since its upload, it has received 90 views. For similar materials see /class/205963/math-364-washington-state-university in Mathematics (M) at Washington State University.
Reviews for Principles of Optimization
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: 09/17/15
Principles of Optimization Simplex Method in Matrix Form and Sensitivity Analysis 1 Matrix Form of Simplex Method Consider the following maxLP given in matrixform max 2 ch st Ax b l x 2 0 The necessary slack and surplus arti cial variables have already been added and hence we have all constraints in the form Here A is an m X 71 matrix ie in rows and 71 columns I is an mvector c and x are nvectors Thus the 71 variables represented as 95 includes the slacksurplusarti cial variables Suppose we know which of the 71 variables are basic in the optimal tableau Since there are m constraints there will be in basic variables and n 7 m nonbasic variables Grouping all the basic variables together and all the x B where 953 denotes the m bas1c var1ables and xN nonbasic variables together we split the vector as into the nonbasic variables Subsequently we also group the columns of A corresponding to the variables 9513 into the m X in matrix B and the remaining nonbasic columns into the m X n 7 in matrix N The cost vector is similarly divided as CT cg cN Thus the starting tableau for the simplex method can be written as follows 2 Notice here that 0 is the mvector of all zeros Applying the simplex method the optimal tableau looks something like this We know that the basic variables form the canonical columns in the optimal tableau thus giving the identity matrix I as shown The important task of course is to gure out what each of the s are Recall that the steps of the simplex method are equivalent to those of the GaussJordan method we are performing elementary row operations in both cases Hence we can think of obtaining the optimal tableau by multiplying the initial tableau by a suitable matrix on the left which is the transformation matrix representing all the ero s Lets call this transformation matrix as T notice that it will be an m 1 X m 1 matrix If you concentrate on the columns of 2 and 9513 you can see that multiplying by T actually converts this part of the tableau to the identity matrix 1 icg 7 1 0 Tl0 B lo I 4 Hence we must have that 1 7CT 7 l CTB 1 We BB an all lt5gt You should check that the inverse of T is indeed as given here The multiplication looks similar to the multipli cation of 2 X 2 matrices except that the elements themselves are matrices or vectors Knowing T we can write the optimal tableau as follows 1 ch l l icg 7c 0 0 B 1 OBNb 6 l 0 7c ch lN ch lb 0 I B lN B lb Thus the optimal objective function value is given by 2 ch lb and the optimal solution is given by 9513 Bill xN 0 Math364 Matrix form of simplex method 7 October 26 2005 2 We will use the Farmer Jones example to illustrate the various cases of sensitivity analysis that we want to study To make the example interesting the objective function coefficient of acres of wheat 95 will be set at 25 as opposed to the original value of 100 7 think about the price per bushel of wheat being set at 1 in place of 4 The LP is max 2 30951 25952 total revenue st 951 952 S 7 total acres 4951 10952 S 40 labor hrs x1 2 3 min corn Notice that the mincorn constraint has been divided by 10 throughout The starting tableau and the optimal tableau for the above LP are given below The variables that are basic in the optimal tableau are 957 53 32 951 Table 1 Starting tableau 2 x1 x2 31 32 63 a3 rhs 1 730 725 0 0 0 M 0 0 1 1 1 0 0 0 7 0 4 10 0 1 0 0 40 0 1 0 0 0 71 1 3 Table 2 optimal tableau 2 x1 x2 31 32 63 a3 rhs 1 0 5 30 0 0 M 210 0 0 1 1 0 1 71 4 0 0 6 74 1 0 0 12 0 1 1 1 0 0 0 7 with the optimal solution given by 951 7 32 12 63 4 and 2 210 Hence cg 0 0 30 and the matrix B and its inverse are as given below 001 1071 B014B 17410 101 100 Check the inverse of B We can actually read of B 1 from the optimal tableau Note that the element in the rightbottom position of T is 3 1 Hence if some of the columns in the initial tableau actually had the identity matrix I in the rows 1 to m then the same columns will have B 1 in the optimal tableau For example if the nonbasic part of A were actually identity iiei N I then in the optimal tableau we will have under the columns of xN B lN B II B li At the same time the slack and arti cial variables indeed form the identity matrix in the initial tableau which is in canonical form 7 see the columns of 31 32 13 in the initial tableau Table 1 Hence B 1 can be read OH from the columns of 31 32 and 13 from the optimal tableau check to make sure that this indeed is true 2 Sensitivity Analysis Now we are ready to consider the various cases of sensitivity analysis The optimal tableau will remain optimal as long as 1 7c ch lN 2 0 for a maxLP all entries in the zrow should be nonnegative for optimality and 2 3 11 2 0 in order to maintain feasibility We will use these two conditions to check whether the current basis still remains optimal after one or more of the parameters is are changed Math364 Matrix form of simplex method 7 October 26 2005 3 21 Changing 03 When 3 is nonbasic Here xj is one of the variables in xN We denote the column of N corresponding to xj by 11quot Consider changing Cj to Cj A From Equation 6 we can see that the only entry in the optimal tableau that possibly changes is the xjentry in row0 As seen from the optimal tableau for the Farmer Jones problem 952 is a nonbasic variable Consider changing the objective function coefficient of 952 from 25 to 25 A you could consider the yield per acre of wheat changing from 25 to 25 A Our goal is to nd the range of values of A for which the current basis still remains optimal The new entry for 952 in row0 of the optimal tableau is 1 0 71 1 1 52725Ach 1a27257A0 0 30 74 1 0 10 7257A30 0 0 10 57A 1 0 0 0 0 We need 52 2 0 for the current basis to remain optimal condition Hence the range of values of A for which the current basis remains optimal is A S 5 Notice that the optimal solution and the optimal objective function value do not change when A is in this range Also recall that the optimal solution was to farm corn in all the 7 acres available 951 7 x2 0 in the optimal solution With A S 5 the revenue per acre of wheat is S 30 which is the value for corn At the same time each acre of wheat requires more hours of labor 10 than an acre of corn There is no minimum level of wheat production required either Hence it makes sense not to farm any wheat If the revenue per acre of wheat becomes higher than that of corn gt 30 one should farm some acres of wheat in order to make the maximum revenue This value 5 is called the reduced cost of the nonbasic variable 952 The reduced cost of a nonbasic in the optimal tableau variable of a maxLP is de ned as the maximum amount by which its objective function coefficient can increase while the current basis still remains optimal Hence if the objective function coefficient of wheat changes to 32 ie A 7 the current basis is no longer optimal 7 in fact it is suboptimal in the sense that the value of 952 can be increased from 0 to some positive value and the value of 2 can be increased In this case in order to nd the new optimal tableau one will have to perform one more simplex pivot with 952 as the entering variable 22 Changing 03 When 3 is basic Here xj is one of the variables in 9513 Consider changing the objective function coefficient of 951 from 30 to 30 A CB also changes here 7 CB 0 0 30 Since CB changes all the entries in row0 corresponding to xN ie all the nonbasic variables could possibly change The new entries in row0 under xN are given by 1 0 71 1 1 0 cN7cNcBB 1N725 0 M0 0 30A 74 1 0 10 0 0 0 0 0 0 1 725 0 M30A 30A 05A 30A M Using the condition 1 again the current basis remains optimal if all entries in EN 2 0 iiei if 5 A 2 0 and 30 A 2 0 Hence the range of values of A for which the current basis remains optimal is A 2 75 For this range the revenue per acre of corn will be at least as big as the value for wheat 25 and hence one will not grow any wheat If A 78 for example then each acre of wheat will yield a higher revenue than an acre of corn 25 and 22 respectively The current basis becomes suboptimal in this case In order to nd the new optimal solution one will have to pivot 95 into the basis perform one more simplex pivot Math364 Matrix form of simplex method 7 October 26 2005 4 23 Changing the righthandside 0f the ith constraint Consider changing I to I A From Equation 6 we can see that the entries in the rhs last column will change For example consider changing the rhs of acres constraint to 7 A 1 re the rst constraint here This change models the situation where Farmer Jones has some extra land to farm The new rhs vector can be 7 A 7 A written asg 40 40 0 Hence 3 3 1 0 71 A 4 A 4A 19463413 74 1 0 0 12 74A 1274A 23 7 1 0 0 0 7 A 7A Using the condition 2 in order for the current basis to still remains optimal we need all elements of 9213 2 0 In other words 4A 2 01274A 2 0 7A 20 Which giveA 2 74 A 31243 A 2 77 or 74 S A S 3 The current basis remains optimal as long as A is in this range Notice that when A gt 3 Jones will have more than 10 acres to farm but could only use 10 due to the limit on the labor hours why Thus the optimal solution will change when A 4 for example Similarly when A 745 the minimum level of corn cannot be satis ed as Jones will have only 25 acres and hence the current basis will no longer be optimal For 74 S A S 3 the new optimal objective function is given by using the expression for B lb from Equation 2 c7523 346 0 0 30 12 7 4A 210 30A 7 A Hence the shadow price of the acres constraint is 30 Recall that the shadow price of a constraint is de ned as the improvement increase for a maxLP in the objective function value for a unit increase the rhs value of the rhs 24 Changing the column both 03 and 13 When 3 is nonbasic The general method outlined above can also be used to calculate the new optimal tableau and optimal basis when more than one parameter is changed For example consider changing the objective function coefficient of 952 which is nonbasic from 25 to 35 and at the same time changing the its coefficient in the labor hours77 constraint from 10 to 8 ie the number of labor hours required for an acre of wheat is now 8 Using the formulae given in Equation 6 the new entries in the column of 952 are given by 1 73530 0 0 0 7 0 5 7c ch laQ 7 1 B lag 1 0 71 1 4 74 1 0 8 1 1 0 0 Notice that we used the result for ch l 30 0 0 which we already saw in section 21 Since the modi ed entry in the row0 under 952 is no longer nonnegative it is 75 the current basis is no longer optimal Intuitively it required less number of labor hours and generates more revenue to farm an acre of wheat after these changes In order to nd the new optimal tableau the column of 952 in the original optimal tableau should be replaced with the one derived above and one more simplex pivot should be performed The new optimal solution thus obtained is 63 1 x2 4 x1 3 with 2 225
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'