{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 "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 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 "2 D 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 "Maple O utput" 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 "newpage" -1 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 1 0 -1 0 } {PSTYLE "vfill" -1 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 258 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 259 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 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 "R 3 Font 4" -1 261 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 262 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 263 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 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 8 " -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 9" -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 10" -1 267 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 268 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 269 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 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 14" -1 271 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 272 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 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 17" -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 "R3 Font 18" -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 19" -1 276 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 277 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 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 22" -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 23" -1 280 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 281 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 282 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 283 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 284 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 285 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 }} {SECT 0 {SECT 0 {PARA 3 "" 0 "" {TEXT -1 26 "The revised simplex metho d" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 714 "We want to redo the simplex \+ method using matrix multiplication. The main reason for doing this (a side from the fact that matrices are nice) is to be able to do sensiti vity analysis in a computationally efficient manner. Our current meth od involves keeping a record of the pivots that we performed in gettin g to an optimal corner point solution, and then modifying either a con straint restriction or a price coefficient in the original set of equa tions, performing the same sequence of pivots, and solving the resulti ng inequalities we got by looking at the final set of equations to ge t the ranges. We will see that using matrices greatly reduces the a mount of arithmetic. So lets look at a typical problem." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "Maximize " }{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." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 189 "Now, sensitivity 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'%(epsilonG!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "price1_sensitivity := evalm(e21&*T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%3price1_sensitivityG-%'MATRIXG6#7%7(\"\"\",$%(epsilon G!\"\"\"\"!#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 h appens is that an epsilon appears in the first row second column of t he 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 operati on can be performed by multiplying on the right by an elementary upper triangular matrix e3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "e 3 := 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&*pr ice1_sensitivity);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$p1sG-%'MATRIX G6#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 see what to do. The shadow prices want to stay nonnegative , else we could increase profit by changing basic variables. So there are two inequalities 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 c oefficient of x can range all the way from 1 to 3 before the basic var iables must change to maintain optimality." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 256 7 "Problem" }{TEXT -1 111 ": Carry out the sensitivity anal ysis on the second price coefficient (the coefficient of y in the obje ctive). " }}}{PARA 3 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "sense2 :=eva lm(e21&*( [0,10,15+theta]) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%' sense2G-%'VECTORG6#7%,&#\"#D\"\"#\"\"\"%&thetaG#F-F,,&#\"#:F,F-F.#!\" \"F,,&#\"\"&F,F-F.F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "sol ve(\{sense1[3]>=0,sense1[2]>=0\},theta);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$1%&thetaG\"\"&1!\"&F%" }}}}}{EXCHG {PARA 0 "" 0 "" {HYPERLNK 17 "Table of contents" 1 "ma416s97.mws" "" }{TEXT -1 0 "" }}}}{MARK "1 0 0" 4 }{VIEWOPTS 1 1 0 1 1 1803 }