{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 } {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 "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 "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 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 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart; with(lina lg):" }}{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 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "D efine a procedure to determine the entering variable." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 948 "enterin g := proc(A,cc,BVs,Binv,m) local i,NBVs,cB,cN,y,N,cNhat,t,cmin; \+ NBVs:=\{seq(i,i=1..n)\}; \+ \+ for i from 1 to n do if member(i,BVs) then NBVs:=NBVs minus \{i\} fi \+ od; NBVs:=sort(convert(NBVs, list)); cB:=subvect or(cc,1,BVs); cN:=subvector(cc,1,NBVs); \+ y:=multiply(cB,Binv); N:=submatrix(A,1..m ,NBVs); cNhat: =evalm(cN-multiply(y,N)); \+ t:=0; cmin:=0; \+ for i from 1 to n-m do if cNhat[i] " 0 "" {MPLTEXT 1 0 430 "leavingrow := proc(AtHAT,bh at,m) local i,k,xt,rit; \+ k:=0; xt:=infinity; \+ for i from 1 to m do if AtHAT[i]>0 then rit:=bhat[i]/AtHAT[i]; \+ if rit " 0 "" {MPLTEXT 1 0 486 "update := proc(Binv,AtHAT,m,k) local i,j,W; \+ W:=matrix(m,m); \+ for j fr om 1 to m do W[k,j]:=Binv[k,j]/AtHAT[k] od; \+ for i from 1 to m do if i<>k then for j from \+ 1 to m do W[i,j]:=Binv[i,j]-AtHAT[i]*W[k,j] od fi \+ od; evalm(W) e nd:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Choose A, b, c, and initial list of basic variables." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "A := matrix([[1,1,1,1,0,0],[-1,2,-2,0,1,0],[2,1,0,0,0,1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'matrixG6#7%7(\"\"\"F*F*F*\"\"!F+7(! \"\"\"\"#!\"#F+F*F+7(F.F*F+F+F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "b := vector([4,6,5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG-%'vectorG6#7%\"\"%\"\"'\"\"&" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 30 "c0 := vector([-1,-2,1,0,0,0]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#c0G-%'vectorG6#7(!\"\"!\"#\"\"\"\"\"!F,F," }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "BVs:=[4,5,6];" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%$BVsG7%\"\"%\"\"&\"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 108 "Determine dimension s. Convert c to a 1xn matrix (to enable the subvector function). Com pute original Binv." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "m:=vectdim(b): n:=vectdim(c0): c:=mat rix(1,n,c0):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "B:=submatrix(A,1..m ,BVs): Binv:=inverse(B):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "unbou nded:=false: DONE:=false:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 55 "Compute bhat and zhat. Note that we mus t have bhat>=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 962 "bhat:=multiply(Binv,b); \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "cB:=subvector(c,1,BVs): \+ zhat:=evalf(dotprod(cB,bhat));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% %bhatG-%'vectorG6#7%\"\"%\"\"'\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%%zhatG\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "Test optimality and determine t. If t=0 then the cu rrent BFS is optimal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "t:=entering(A,c,BVs,Binv,m);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"tG\"\"#" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "Determine entering row \+ location k. If k=0 then z is unbounded. Note s=BVs(k). " }}{PARA 0 "" 0 "" {TEXT -1 78 "Determine new list of basic variables. Update Bi nv. Compute bhat and zhat. " }}{PARA 0 "" 0 "" {TEXT -1 73 "Test opt imality and determine t. If t=0 then the current BFS is optimal." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "AtHAT:=multiply(Binv,col(A,t)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "k:=leavingrow(AtHAT,bhat,m):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "if k=0 then unbounded:=true fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "if not unbounded then BVs:=subsop(k=t,BVs) fi;" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 68 "if not unbounded then W:=update(Binv,AtHAT,m,k): Bi nv:=evalm(W): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 987 "if not unboun ded then bhat:=multiply(Binv,b) fi; \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "if not unbounded then zhat:=evalf(d otprod(subvector(c,1,BVs),bhat)) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "if not unbounded then t:=entering(A,c,BVs,Binv,m) fi: " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "if t=0 then DONE:=true fi;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$BVsG7%\"\"%\"\"#\"\"'" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%%bhatG-%'vectorG6#7%\"\"\"\"\"$\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%zhatG$!\"'\"\"!" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "Now copy the last cell \+ and repeat as needed. " }}{PARA 0 "" 0 "" {TEXT -1 104 "If DONE, then an optimal solution has been reached. If unbounded, then there is no optimal solution. " }}{PARA 0 "" 0 "" {TEXT -1 57 "If zhat does not \+ improve, then the problem is degenerate." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "AtHAT:=multiply(Binv ,col(A,t)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "k:=leavingrow(AtHAT, bhat,m):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "if k=0 then unbounded:= true fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "if not unbounded then B Vs:=subsop(k=t,BVs) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "if not u nbounded then W:=update(Binv,AtHAT,m,k): Binv:=evalm(W): fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 987 "if not unbounded then bhat:=multiply(Bin v,b) fi; \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "if not unbounded then zhat:=evalf(dotprod(subvector(c,1,BVs),bha t)) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "if not unbounded then t: =entering(A,c,BVs,Binv,m) fi: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "if t=0 then DONE:=true fi;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$B VsG7%\"\"\"\"\"#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%bhatG-%'ve ctorG6#7%#\"\"#\"\"$#\"#5F+#\"\"\"F+" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%%zhatG$!+LLLLt!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%DONEG%%tr ueG" }}}}{MARK "21 12" 0 }{VIEWOPTS 1 1 0 1 1 1803 }