{VERSION 3 0 "IBM INTEL NT" "3.0" } {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 Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 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 "Maple 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 "" 0 262 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 262 "" 0 "" {TEXT -1 30 "The Simplex Algorithm: C ycling" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Define functions:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "E_2 := proc(n, i, alpha)\n mulrow (array(identity, 1..n,1..n), i, alpha);\nend:\n" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 73 "Pivot:=proc(A,i,j) linalg[pivot](E_2(rowdim(A) ,i,1/A[i,j]) &* A,i,j) end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&Pivo tGR6%%\"AG%\"iG%\"jG6\"F*F*-&%'linalgG6#%&pivotG6%-%#&*G6$-%$E_2G6%-%' rowdimG6#9$9%*&\"\"\"F=&F:6$F;9&!\"\"F:F;F@F*F*F*" }}}{EXCHG {PARA 0 " " 0 "" {TEXT 267 11 "Example of " }{TEXT -1 0 "" }{TEXT 282 8 " Cyclin g" }{TEXT -1 49 " (Text, p. 127, Example 2): Consider the system" }} {PARA 0 "" 0 "" {TEXT -1 35 " " } {TEXT 260 55 " Max 10 x1 - 57 x2 - 9 x3 - 24 x4 " }}{PARA 0 "" 0 "" {TEXT 295 134 " \+ s.t. (1/2) x1 - (11/2) x2 - (5/2) x3 + 9 x4 + x5 \+ = 0" }}{PARA 0 "" 0 "" {TEXT 296 137 " \+ (1/2) x1 - (3/2) x2 - ( 1/2) x3 + x4 + x6 = 0" }} {PARA 0 "" 0 "" {TEXT 297 153 " \+ x1 \+ + x7 = 1" }}{PARA 0 "" 0 "" {TEXT 298 144 " \+ x1 , x2 , x3 , x4 , x5 , x6 , x 7 >= 0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "A:= matrix (3,7,[1/2,-11/2,-5/2,9,1,0,0,1/2,-3/2,-1/2,1,0,1,0,1,0,0,0,0,0,1]);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'matrixG6#7%7)#\"\"\"\"\"##!# 6F,#!\"&F,\"\"*F+\"\"!F27)F*#!\"$F,#!\"\"F,F+F2F+F27)F+F2F2F2F2F2F+" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "b:=vector(3,[0,0,1]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG-%'vectorG6#7%\"\"!F)\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Ab:=augment(A,b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#AbG-%'matrixG6#7%7*#\"\"\"\"\"##!#6F,#!\" &F,\"\"*F+\"\"!F2F27*F*#!\"$F,#!\"\"F,F+F2F+F2F27*F+F2F2F2F2F2F+F+" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "c:=vector(8,[10,-57,-9,-24, 0,0,0,0]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG-%'vectorG6#7*\"#5 !#d!\"*!#C\"\"!F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Ab c:=stackmatrix(-c,Ab);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$AbcG-%'ma trixG6#7&7*!#5\"#d\"\"*\"#C\"\"!F.F.F.7*#\"\"\"\"\"##!#6F2#!\"&F2F,F1F .F.F.7*F0#!\"$F2#!\"\"F2F1F.F1F.F.7*F1F.F.F.F.F.F1F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 300 11 "Iteration 1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "Pivot(Abc,2,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-% 'matrixG6#7&7*\"\"!!#`!#T\"$/#\"#?F(F(F(7*\"\"\"!#6!\"&\"#=\"\"#F(F(F( 7*F(\"\"%F2!\")!\"\"F.F(F(7*F(\"#6\"\"&!#=!\"#F(F.F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 301 11 "Iteration 2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,3,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'m atrixG6#7&7*\"\"!F(#!#H\"\"#\"#)*#\"#F\"\"%#\"#`F/F(F(7*\"\"\"F(#F3F+! \"%#!\"$F/#\"#6F/F(F(7*F(F3F4!\"##!\"\"F/#F3F/F(F(7*F(F(#F=F+F/#\"\"$F /#!#6F/F3F3" }}}{EXCHG {PARA 263 "" 0 "" {TEXT -1 11 "Iteration 3" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,2,3);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"#H\"\"!F)!#=!#:\"#$*F)F)7*\"\" #F)\"\"\"!\")#!\"$F.#\"#6F.F)F)7*!\"\"F/F)F.#F/F.#!\"&F.F)F)7*F/F)F)F) F)F)F/F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 302 11 "Iteration 4" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,3,4);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"#?\"\"*\"\"!F*#!#@\"\"##\"$T\" F-F*F*7*!\"#\"\"%\"\"\"F*#F3F-#!\"*F-F*F*7*#!\"\"F-F4F*F3#F3F2#!\"&F2F *F*7*F3F*F*F*F*F*F3F3" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 303 11 "Iterati on 5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,2,5);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*!#A\"#$*\"#@\"\"!F+!#C F+F+7*!\"%\"\")\"\"#F+\"\"\"!\"*F+F+7*#F1F0#!\"$F0#!\"\"F0F1F+F1F+F+7* F1F+F+F+F+F+F1F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 304 11 "Iteration 6 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,3,6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*!#5\"#d\"\"*\"#C\"\"!F,F,F,7 *#\"\"\"\"\"##!#6F0#!\"&F0F*F/F,F,F,7*F.#!\"$F0#!\"\"F0F/F,F/F,F,7*F/F ,F,F,F,F,F/F/" }}}{EXCHG {PARA 264 "" 0 "" {TEXT -1 49 "Back to Iterat ion 0. Consider a different pivot:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,2,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'m atrixG6#7&7*!#5\"#d\"\"*\"#C\"\"!F,F,F,7*#\"\"\"\"\"##!#6F0#!\"&F0F*F/ F,F,F,7*F.#!\"$F0#!\"\"F0F/F,F/F,F,7*F/F,F,F,F,F,F/F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,3,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"\"!\"#F!\"\"\"#WF(\"#?F(F(7*F(!\"%!\" #\"\")\"\"\"F*F(F(7*F1!\"$F*\"\"#F(F4F(F(7*F(\"\"$F1F/F(F/F1F1" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,4,3);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"\"!\"#IF(\"#UF(\"#=\"\"\"F,7*F (\"\"#F(\"\"%F,!\"&F.F.7*F,F(F(F(F(F(F,F,7*F(\"\"$F,!\"#F(F4F,F," }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "an " }{TEXT 277 17 "optimal solutio n " }{TEXT -1 7 " with " }{TEXT 278 15 "basic variables" }{TEXT -1 2 " " }{TEXT 276 50 "x1 = 1, x3 = 1, x5 = 2 and optimal value = 1 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "28 0 0" 0 } {VIEWOPTS 1 1 0 1 1 1803 }