{VERSION 2 3 "IBM INTEL NT" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 256 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Helvetica" 1 12 0 0 255 1 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "M aple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Courier" 1 18 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "Lucidabright" 1 19 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 3" -1 258 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 4" -1 259 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 5" -1 260 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 6" -1 261 1 {CSTYLE "" -1 -1 "Lu cida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 7" -1 262 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 8 " -1 263 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 9" -1 264 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 10" -1 265 1 {CSTYLE "" -1 -1 "Charter " 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 11" -1 266 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 1 2" -1 267 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 13" -1 268 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 14" -1 269 1 {CSTYLE "" -1 -1 "L ucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 15" -1 270 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 16" -1 271 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 17" -1 272 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 18" -1 273 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 19" -1 274 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 20" -1 275 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 21" -1 276 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 22" -1 277 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 23" -1 278 1 {CSTYLE " " -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 24" -1 279 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 25" -1 280 1 {CSTYLE "" -1 -1 "Luci datypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 26" -1 281 1 {CSTYLE "" -1 -1 "Lucidatypewr iter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 27" -1 282 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 28" -1 283 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 4 284 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 284 "" 0 "top" {TEXT -1 26 "The revised simplex m ethod" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 714 "We want to redo the sim plex method using matrix multiplication. The main reason for doing th is (aside from the fact that matrices are nice) is to be able to do se nsitivity analysis in a computationally efficient manner. Our current method involves keeping a record of the pivots that we performed in g etting to an optimal corner point solution, and then modifying either \+ a constraint restriction or a price coefficient in the original set of equations, performing the same sequence of pivots, and solving the re sulting inequalities we got by looking at the final set of equations \+ to get the ranges. We will see that using matrices greatly reduces \+ the amount of arithmetic. So lets look at a typical problem." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "Ma ximize " }{XPPEDIT 18 0 " 2*x + y" ",&*&\"\"#\"\"\"%\"xGF%F%%\"yGF%" } {TEXT -1 13 " subject to " }{XPPEDIT 18 0 "x+y<=10" "1,&%\"xG\"\"\"% \"yGF%\"#5" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "3*x+y <=15" "1,&*&\"\" $\"\"\"%\"xGF&F&%\"yGF&\"#:" }{TEXT -1 1 "." }{MPLTEXT 1 0 1 " " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, new definition for norm" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for trace" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "First, construct the matrix of the initial tableau. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 95 "T := matrix(3,6,[1,-2,- 1,0,0,0,\n 0,1,1,1,0,10,\n 0,3,1,0,1,1 5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"TG-%'MATRIXG6#7%7(\"\"\"! \"#!\"\"\"\"!F-F-7(F-F*F*F*F-\"#57(F-\"\"$F*F-F*\"#:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 215 "We choose the third column as the pivot column and the must choose (because of the ratios) the second row as the piv ot row. So now construct the elementary gauss matrix to perform the n ecessary row operations on T." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "id := diag(1,1,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#idG-%'M ATRIXG6#7%7%\"\"\"\"\"!F+7%F+F*F+7%F+F+F*" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 24 "multipliers := [1,1,-1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,multipliersG7%\"\"\"F&!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "e1 := augment( col(id,1),multipliers,col(id,3)); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#e1G-%'MATRIXG6#7%7%\"\"\"F*\"\" !7%F+F*F+7%F+!\"\"F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "To get th e tableau after one iteration, multiply e1 by T." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "T1 := evalm(e1&*T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T1G-%'MATRIXG6#7%7(\"\"\"!\"\"\"\"!F*F,\"#57(F,F*F*F *F,F-7(F,\"\"#F,F+F*\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 162 "The re is still a negative coefficient in the top row. Choose the second \+ column and (by necessity) the third row as the pivot row and column. \+ The multipliers are" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "mult ipliers := [1/2,-1/2,1/2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,multi pliersG7%#\"\"\"\"\"##!\"\"F(F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "and the gaussian matrix is" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "e2 := augment(col(id,1..2),multipliers);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#e2G-%'MATRIXG6#7%7%\"\"\"\"\"!#F*\"\"#7%F+F*#!\"\"F- 7%F+F+F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "and the new (and fina l) tableau is" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "T2 := eval m(e2&*T1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T2G-%'MATRIXG6#7%7(\" \"\"\"\"!F+#F*\"\"#F,#\"#DF-7(F+F+F*#\"\"$F-#!\"\"F-#\"#:F-7(F+F*F+F3F ,#\"\"&F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 191 "The product e2*e1 c ontains a complete record of the pivots that were made in the simplex \+ algorithm. Note it actually appears in the final tableau-- it is the \+ 1st, 4th, and 5th columns of T2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "e21 := evalm(e2&*e1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$e21G-%'MATRIXG6#7%7%\"\"\"#F*\"\"#F+7%\"\"!#\"\"$F,#!\"\"F,7% F.F1F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 160 "To do sensitivity anal ysis on the first resouce, all we need to do is multiply e21 by the co lumn [0,10+theta,15] and solve the resulting inequalities for theta." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "sense1 :=evalm(e21&*( [0 ,10+theta,15]) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'sense1G-%'VEC TORG6#7%,&#\"#D\"\"#\"\"\"%&thetaG#F-F,,&#\"#:F,F-F.#\"\"$F,,&#\"\"&F, F-F.#!\"\"F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "solve(\{sen se1[3]>=0,sense1[2]>=0\},theta);" }}{PARA 0 "" 0 "" {TEXT -1 465 "So, \+ the right hand side of the first resource can vary between 5 and 15 b efore the basic variables change in the optimal solution. Notice th at to perform this sensitivity analysis, we only need to multiply e21 \+ times the right most column of the original tableau, modified by addin g theta to the 2nd entry. This provides a computational advantage ove r the previous method of performing sensitivity analysis, which involv ed stepping through the iterations again." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$1%&thetaG\"\"&1!\"&F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "Sensitivity analysis on the second resource is done in th e same way and is shown below." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "sense2 :=evalm(e21&*( \+ [0,10,15+theta]) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'sense2G-%'V ECTORG6#7%,&#\"#D\"\"#\"\"\"%&thetaG#F-F,,&#\"#:F,F-F.#!\"\"F,,&#\"\"& F,F-F.F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "solve(\{sense1[ 3]>=0,sense1[2]>=0\},theta);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$1%&t hetaG\"\"&1!\"&F%" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 189 "Now, sensi tivity analysis on the price coefficients is a tiny bit more involved. In order to see what to do, let's add epsilon to the first price coefficient in T and multiply by e21." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "T[1,2]:= -(2+epsilon);" }}{PARA 11 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"TG6$\"\"\"\"\"#,&!\"#F'%(e psilonG!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "price1_sens itivity := evalm(e21&*T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%3price1 _sensitivityG-%'MATRIXG6#7%7(\"\"\",$%(epsilonG!\"\"\"\"!#F*\"\"#F/#\" #DF07(F.F.F*#\"\"$F0#F-F0#\"#:F07(F.F*F.F6F/#\"\"&F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 323 "The only thing that happens is that an epsilo n appears in the first row second column of the tableau. In order to \+ bring x back into solution, we must multiply the bottom row by epsilon and add it to the top row. This row operation can be performed by mu ltiplying on the right by an elementary upper triangular matrix e3." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "e3 := augment(col(id,1..2) ,[epsilon,0,1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#e3G-%'MATRIXG6# 7%7%\"\"\"\"\"!%(epsilonG7%F+F*F+7%F+F+F*" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 37 "p1s := evalm(e3&*price1_sensitivity);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%$p1sG-%'MATRIXG6#7%7(\"\"\"\"\"!F+,&#F*\"\"#F* %(epsilonG#!\"\"F.,&F-F*F/F-,&#\"#DF.F*F/#\"\"&F.7(F+F+F*#\"\"$F.F0#\" #:F.7(F+F*F+F0F-F6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 182 "Now we se e what to do. The shadow prices want to stay nonnegative , else we c ould increase profit by changing basic variables. So there are two in equalities to solve for epsilon." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "solve(\{p1s[1,4]>=0,p1s[1,5]>=0\},epsilon);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$1%(epsilonG\"\"\"1!\"\"F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "This says that the coefficient of x can \+ range all the way from 1 to 3 before the basic variables must change t o maintain optimality." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 256 7 "Problem " }{TEXT -1 111 ": Carry out the sensitivity analysis on the second p rice coefficient (the coefficient of y in the objective). " }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }