{VERSION 2 3 "HP RISC UNIX" "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 "Hyperlink" -1 17 "" 0 1 0 128 128 1 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 "Hea ding 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 "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 "R3 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 "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 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 }} {SECT 0 {SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 " Duality" }}{EXCHG {PARA 0 "" 0 "top" {TEXT -1 64 " Problem: Set up and solve the primal prob lem and its dual. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 44 "First, we'll do it with the simplex package." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "with(simplex);" }}}{EXCHG {PARA 0 "> " 0 "primal problem" {MPLTEXT 1 0 143 "primalprob := 10*x1 -4*x2+7*x3, [3*x1 -x2 + 2*x3 <=25,\n x1 -2*x2 + 3*x3 <=25,\n5*x1 +x2 \+ + 2*x3 <=40,\n x1 +x2 + x3 <=90,\n2*x1 -x2 + x3 <=20] ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "infolevel[simplex]:= 3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "soln :=maximize(primalprob,NONNEGAT IVE);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "Three iterations are mad e to optimize in the primal problem." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "subs(soln,[primalprob]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 201 "So the maximum value is 600/7 when [x1,x2,x3] is [25/7,0 ,50/7]. Note that the shadow prices of the slack variables [s1,s2, s3,s4,s5] = [23/7, 1/7, 0,0,0] can be read off of the objective equat ion. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "To solve the dual, first check out the help page on dual." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "?dual" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "That's e asy enough. simplex will create the dual problem, which we can then f eed to minimize." }}}{EXCHG {PARA 0 "> " 0 "dual problem (setting up w ith simplex)" {MPLTEXT 1 0 32 " dualprob :=dual(primalprob,y) ;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "dualsoln :=minimize(dualprob ,NONNEGATIVE);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "It took 2 itera tions in phase 1 and 1 more iteration in phase 2 to optimize," }} {PARA 0 "" 0 "" {TEXT -1 54 "so in this case the number of iterations \+ was the same." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "subs(duals oln,[dualprob]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "So the minimu m value is 600/7 when [y1,y2,y3,y4,y5] = [23/7,1/7,0,0,0]. " }}{PARA 0 "" 0 "" {TEXT -1 132 "Can we read off an optimal corner point for th e primal problem from the objective of the dual problem in the final s et of equations?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 39 "Lets solve both problems again using " }{TEXT -1 0 "" }{TEXT -1 0 "" }{HYPERLNK 17 "matmax " 1 "revised2.mws" "top" }{TEXT -1 128 " from the previous worksheet. You will need to execute the cells containing the definitions of gauss, getpiv, and matmax the re." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "So lution: initialize the tableau." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 244 "T := matrix(6,10,[1,-10,4,-7,0,0,0,0,0,0,\n \+ 0, 3,-1,2,1,0,0,0,0,25,\n 0,1,-2,3,0,1,0,0,0,25,\n \+ 0,5,1,2,0,0,1,0,0,40,\n 0,1,1,1,0,0,0,1, 0,90,\n 0,2,-1,1,0,0,0,0,1,20]);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 24 "Now say the word matmax." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " matmax(T,[1,5,6,7,8,9]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "So there are three iterations to solve the primal pr oblem." }}{PARA 0 "" 0 "" {TEXT -1 43 "Read the solution off of the fi nal tableau." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Now construct the tableau for the dual problem." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "evalm(T); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "First, grab out the matrix A of constraint coefficient s " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "A := submatrix(T,2..6 ,2..4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Next write down the ve ctor of objective coefficients " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "c := [10,-4,7]; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "b := [25,25,40,90,20];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " dA := transpose(A);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " i3 \+ := diag(1,1,1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "i3[2,2]: =-1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "dA := evalm(i3&*dA) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "dT :=augment([0,0,0],d A,[-1,0,0],[0,0,-1],[1,0,0],[0,1,0],[0,0,1],[10,4,7]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "zrow := [1 ,op( b), 0,0, M,0, M,0] ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " dT := stack(zrow,dT) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "e1 := gauss( col(dT,9) ,2 ); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " dT2 := evalm(e1& *dT);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "e2 := gauss(col(dT 2,11),4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "dT3 := evalm(e 2&*dT2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "matmax(subs(M=1 000,evalm(dT3)),[1,9,10,11]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 " So the dual problem optimizes in only 2 iterations using matmax." }}} {EXCHG {PARA 0 "" 0 "" {HYPERLNK 17 "Table of Contents" 1 "ma416s97.mw s" "top" }{HYPERLNK 17 "" 1 " Assign7sln.mws" "top" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "0 0 0" 8 }{VIEWOPTS 1 1 0 1 1 1803 }