{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 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 128 0 0 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 "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 "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 Fo nt 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 "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 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 1 1" -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 12" -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 "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 14" -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 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 "R 3 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 "R3 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 "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 23" -1 278 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 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 "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 26" -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 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 "" 3 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 "" {TEXT -1 22 "Assignment problems. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "If you have n people to do n jo bs and it costs " }{XPPEDIT 18 0 "c[ij" "&%\"cG6#%#ijG" }{TEXT -1 464 " dollars for the ith person to do the jth job, then you have an assig nment problem. It can be treated as a transportation problem where t he supply and demand equations all have right hand sides 1. A basi c feasible solution will have exactly n assignments of value 1, and th e other n-1 basic variables will be assigned value 0. This will cause a lot of 'wasted iterations' when we apply the transportation simplex algorithm, but that's ok. They're cheap. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 246 "I have expanded the defi nitions of the words fastransport, checkopt, and get cycle so as to \+ print out more intermediate information to enable you to see the work \+ going into getting the entering variable, the cycle, and the leaving v ariable. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " restart;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "with(simplex):" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 40 " The northwest corner rule is unchanged." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 481 " nwcrule := proc(c,s,d )\n \+ local bv,x, i,j,rw,cl,n,m,fin;\n n := rowdim(c):\n m := coldim(c): \n x := matrix(n,m,[0$n*m]);\n bv := NULL: rw := 1:\n for cl from \+ 1 to m do\n while rw < n+1 and sum(x[i,cl],i=1..rw-1 ) < d[cl] do\n x[rw,cl] := min(d[cl]-sum(x[i,cl],i=1..rw-1),\n s [rw]-sum(x[rw,j],j=1..cl-1));\n bv := bv,[rw,cl];\n rw := rw+1; \+ \n od;\n if rw > n or s[rw]-sum(x[rw,j],j=1..cl) > 0 then rw \+ := rw-1 fi\n od; \n [evalm(x),\{bv\}]; \n end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 284 "getuv finds the shadow prices that accom pany the current basis. These enable you to choose the entering var iable. Note that as we discussed in class, the u[i] and v[j]'s are \+ not unique and so you can set any one of them to zero and then determi ne the others. We can set v[1]=0." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 313 "getuv := proc(c,x,bv,`u`,`v`)\n local eqs, i, j,t,t1 ,rw;\n eqs := \{\}:\nfor i from 1 to rowdim(x) do\n for j from 1 to co ldim(x) do\n if member([i,j],bv) then \n eqs := eqs union \{c[i,j]=u[ i]+v[j]\} fi;\n od od;\n v[1]:=0;\n assign(solve( eqs ,\n\{seq(u[i], i= 1..rowdim(x)), seq(v[j],j=2..coldim(x))\})); \nend: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Checkopt returns true if the c urrent solution is optimal, else returns the entering variable. " }} }{EXCHG {PARA 0 "> " 0 "checkopt" {MPLTEXT 1 0 516 "checkopt := proc(c ,x,bv,u,v,prt)\n local i,j ,t,t1,inc,shad ;\n t := 0;\nshad := matrix (rowdim(c),coldim(c),[seq(0,i=1..rowdim(c)*coldim(c))]);\ninc := true: for i from 1 to rowdim(c) do\n for j from 1 to coldim(c) do\n t1 \+ := subs(M=infinity,c[i,j]-u[i]-v[j]);\n if member ([i,j],bv) then sha d[i,j]:=`b`\n else shad[i,j]:= t1 fi;\n if not member([i,j],bv) \n then if t1 < t then\n t := t1; inc := [i,j] fi fi;\n od od;\n i f nargs() = 5 then print(`reduced costs`);\n print(evalm(shad)); fi ;\n RETURN(inc); end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "getcyc le takes the current basis and entering variable and returns the" }} {PARA 0 "" 0 "" {TEXT -1 35 "cycle in bv union ev containing ev." }}} {EXCHG {PARA 0 "> " 0 "getcycle " {MPLTEXT 1 0 598 "getcycle := proc(b v,ev)\n local paths, lev, fin, newpaths, i,j, p, v;\npaths := table() \+ ; \npaths[1] := [ev]; \nlev := 0; fin := false; \nwhile not fin do\n \+ newpaths := table(); i := 0;\n for j from 1 to nops(\{indices(p aths)\}) do\n for v in bv minus \{op(paths[j])\} do\n if \+ v[lev mod 2 +1] = paths[j][-1][lev mod 2 +1] \n then i := i+1;\n newpaths[i] := [op(paths[j]),v]; \n \+ if v[lev+1 mod 2 +1] = ev[lev+1 mod 2 +1] then\n \nRETURN(newpaths[i]) fi; \n fi;\n od od;\n paths := op(newpaths);\n \+ lev := lev+1;\n od;\n end:" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 24 "We need a cost function." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 " cost := proc(c,x,bv) convert([seq(c[op(bv[i])]*x[op( bv[i])],i=1..nops(bv))],`+`); end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 " Finally, putting this all together in the word fasttransport 2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 911 "fasttransport2 := pr oc(c,s,d,prt)\n local sol, x,bv,iter, fin, u, v, ev, st,cy,cyc, t, r, \+ i, r1, t1, lv;\nsol := nwcrule(c,s,d ) ;\n x := sol[1];\n bv := sol[2 ];\nfin := false;\niter := 0;\nwhile not fin do\nif nargs()=4 then pri nt(evalm(x)); print(cost(c,x,bv)) fi;\nu := 'u': v := 'v': \ngetuv(c,x ,bv,u,v);\nev := checkopt(c,x,bv,u,v);\nif ev=true then RETURN([bv,op( x),cost(c,x,bv)]) fi;\niter := iter+1; print(`iteration `,iter);\ncy : = getcycle(bv,ev);\ncyc := matrix(nops(s),nops(d),[seq(0,i=1..nops(s)* nops(d))]);\nfor st in bv do cyc[op(st)]:=1 od:\nfor st in cy do cyc[o p(st)]:=`y` od;\ncyc[op(ev)]:=`e`;\n print( evalm(cyc));\n t := infin ity; r := 0,0; for i from 1 to nops(cy)/2 do\n r1 := op(cy[2*i ]);\n t1 := subs(M=infinity, x[r1]);\n if t1 < t then t := t1; r := r1; f i\n od ; lv := [r];\n for i from 1 to nops(cy) do\n x[op(cy[i])] : = x[op(cy[i])]+(-1)^(i+1)*t od;\n bv := \{ev\} union (bv minus \{lv\} ); \nod; end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 " Now let's look \+ at the assignment problem from class." }{MPLTEXT 1 0 3 " " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "c := matrix(3,3,[5,6,1,3,2,2 ,5,2,5 ]); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "d := [1,1,1] : s := [1,1,1]: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "t := ti me():sol := fasttransport2(c,s,d,p); ftime := time()-t;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 " We need to check this against the stand ard setup a transportation problem." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 526 "slowtransport := proc(c,s,d)\n local m, n, x, eqs, \+ i, j, obj,soln;\n m := rowdim(c): n := coldim(c):\n x := matrix(m,n) ;\n eqs := NULL;\n for i from 1 to m do\n eqs := eqs,sum(x[i,j],j= 1..n)<= s[i],\n sum(x[i,j],j=1..n)>= s[i] od;\n i := 'i':\n \+ for j from 1 to n do\n eqs := eqs,sum(x[i,j],i=1..m)<=d[j],\n sum (x[i,j],i=1..m)>=d[j] od;\n eqs := \{eqs\};\n j := 'j':\n obj := \+ sum(sum(c[i,j]*x[i,j],j=1..n),i=1..m);\n soln:=minimize(obj,eqs,NONN EGATIVE);\n assign(soln);\n [subs(soln,obj),evalm(x)]; \n \+ end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "t := time():sln := \+ slowtransport(subs(M=10^3 ,op(c)),s,d);\ntime()-t;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 223 "Well, so much for the streamlinedness of the fas t transportation algorithm. Slow is faster than fast in this implemen tation. We could try a larger problem to see what happens. Make a \+ random 10 by 10 assignment problem." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "c := map(abs,randmatrix(10,10)); \ns := [1$10];\nd := s;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "t := time():sln := fa sttransport2(subs(M=10^3 ,op(c)),s,d);\ntime()-t; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "t : = time():sln := slowtransport(subs(M=10^3 ,op(c)),s,d);\ntime()-t;" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 " " }}}}{MARK "0 0 0" 19 }{VIEWOPTS 1 1 0 1 1 1803 }