home *** CD-ROM | disk | FTP | other *** search
/ Education Sampler 1992 [NeXTSTEP] / Education_1992_Sampler.iso / Mathematics / Notebooks / OperationsResearch / 533notebook.ma next >
Text File  |  1992-07-27  |  19KB  |  483 lines
  1. (*^
  2.  
  3. ::[paletteColors = 128; currentKernel; 
  4.     fontset = title, nohscroll, center, bold,  24, "Times"; ;
  5.     fontset = subtitle, nohscroll, center, bold,  18, "Times"; ;
  6.     fontset = subsubtitle, nohscroll, center, bold,  14, "Times"; ;
  7.     fontset = section, nohscroll, grayBox, bold,  18, "Times"; ;
  8.     fontset = subsection, nohscroll, blackBox, bold,  14, "Times"; ;
  9.     fontset = subsubsection, nohscroll, whiteBox, bold,  12, "Times"; ;
  10.     fontset = text, nohscroll,  12;
  11.     fontset = smalltext, nohscroll,  10, "Times"; ;
  12.     fontset = input, nowordwrap, bold,  12, "Courier"; ;
  13.     fontset = output, nowordwrap,  12, "Courier"; ;
  14.     fontset = message, nowordwrap, R21845, G21845, B21845,  12, "Courier"; ;
  15.     fontset = print, nowordwrap,  12, "Courier"; ;
  16.     fontset = info, nowordwrap,  12, "Courier"; ;
  17.     fontset = postscript, nowordwrap,  12, "Courier"; ;
  18.     fontset = name, nowordwrap, nohscroll, italic, R21845, G21845, B21845,  11, "Times"; ;
  19.     fontset = header,  10, "Times"; ;
  20.     fontset = Left Header, nohscroll, cellOutline,  12;
  21.     fontset = footer, center,  12;
  22.     fontset = Left Footer, cellOutline, blackBox,  12;
  23.     fontset = help, nohscroll,  14, "Times"; ;
  24.     fontset = clipboard,  12;
  25.     fontset = completions, nowordwrap,  16, "Courier"; ;
  26.     fontset = special1, nowordwrap,  12;
  27.     fontset = special2, nowordwrap, center,  12;
  28.     fontset = special3, nowordwrap, right,  12;
  29.     fontset = special4, nowordwrap,  12;
  30.     fontset = special5, nowordwrap,  12;]
  31. :[font = subtitle; inactive; startGroup; ]
  32. A Tutorial For Solving
  33. :[font = title; inactive; ]
  34. Problems in Operations Research
  35. :[font = text; inactive; center; endGroup; ]
  36. by
  37. Krishnapradad V. Kamisetty
  38. CIM Systems Research Center
  39. Arizona State University, Tempe, AZ 85287-5106
  40. -- Now at Intel, Phoenix --
  41. :[font = section; inactive; startGroup; ]
  42. The Assignment Model
  43. :[font = subsection; inactive; ]
  44. Introduction
  45. :[font = text; inactive; ]
  46. This problem consists of allocating some resources to some operating patterns in such a way that the costs of the assignments are minimized, each resource is assigned exactly once. Hungarian algorithm is used to solve the problem.
  47.  
  48. This tutorial assumes that the given problem will be in a square matrix form and that the values given in the matrix are COSTS.  If the original problem is given in terms of  profits, the user will have to multiply the profit numbers by -1 and then use the tutorial.
  49. :[font = subsection; inactive; ]
  50. Example1
  51. :[font = text; inactive; ]
  52. This section steps you through an example problem.  The following subsections are arranged logically so that you can perceive the operations performed to arrive at an optimum solution. Please note that there may typically be many more alternate optimum solutions.
  53. :[font = subsubsection; inactive; ]
  54. Loading the Function Definitions
  55. :[font = input; ]
  56. <<hungarian.m
  57. :[font = subsubsection; inactive; ]
  58. Initialization
  59. :[font = input; startGroup; ]
  60. initialization
  61. :[font = print; inactive; endGroup; ]
  62. INITIALIZATION DONE
  63. :[font = subsubsection; inactive; ]
  64. Data Input Process
  65. :[font = input; startGroup; ]
  66. inputphase
  67. :[font = print; inactive; endGroup; ]
  68. 2   10  9
  69.  
  70. 15  4   14
  71.  
  72. 13  14  16
  73. :[font = subsubsection; inactive; ]
  74. Row Reduction by the minimum of the row elements
  75. :[font = input; startGroup; ]
  76. rowreduction
  77. :[font = print; inactive; endGroup; ]
  78. 0   8   7
  79.  
  80. 11  0   10
  81.  
  82. 0   1   3
  83. :[font = subsubsection; inactive; ]
  84. Column Reduction by the minimum of the column elements
  85. :[font = input; startGroup; ]
  86. columnreduction
  87. :[font = print; inactive; endGroup; ]
  88. 0   8   4
  89.  
  90. 11  0   7
  91.  
  92. 0   1   0
  93. :[font = subsubsection; inactive; ]
  94. Checking for all the zeroes that the matrix has at this point
  95. :[font = input; startGroup; ]
  96. zerocheck
  97. :[font = print; inactive; endGroup; ]
  98. 11
  99. 22
  100. 31
  101. 33
  102. :[font = subsubsection; inactive; ]
  103. What kind of solution do we have now?
  104. :[font = input; startGroup; ]
  105. whatdoithink
  106. :[font = print; inactive; endGroup; ]
  107. POSSIBLE OPTIMUM goto OPTIMAL function
  108. :[font = subsubsection; inactive; ]
  109. Check for Optimum solution and find the SOLUTION
  110. :[font = input; startGroup; ]
  111. optimal
  112. :[font = print; inactive; endGroup; ]
  113. OPTIMAL
  114. 11
  115. 22
  116. 33
  117. :[font = subsection; inactive; ]
  118. Example2
  119. :[font = subsubsection; inactive; ]
  120. Loading the Function Definitions
  121. :[font = input; ]
  122. <<hungarian.m
  123. :[font = subsubsection; inactive; ]
  124. Initialization
  125. :[font = input; startGroup; ]
  126. initialization
  127. :[font = print; inactive; endGroup; ]
  128. INITIALIZATION DONE
  129. :[font = subsubsection; inactive; ]
  130. Data Input Process
  131. :[font = input; startGroup; ]
  132. inputphase
  133. :[font = print; inactive; endGroup; ]
  134. 2   10  9   7
  135.  
  136. 15  4   14  8
  137.  
  138. 13  14  16  11
  139.  
  140. 4   15  13  19
  141. :[font = subsubsection; inactive; ]
  142. Row Reduction by the minimum of the row elements
  143. :[font = input; startGroup; ]
  144. rowreduction
  145. :[font = print; inactive; endGroup; ]
  146. 0   8   7   5
  147.  
  148. 11  0   10  4
  149.  
  150. 2   3   5   0
  151.  
  152. 0   11  9   15
  153. :[font = subsubsection; inactive; ]
  154. Column Reduction by the minimum of the column elements
  155. :[font = input; startGroup; ]
  156. columnreduction
  157. :[font = print; inactive; endGroup; ]
  158. 0   8   2   5
  159.  
  160. 11  0   5   4
  161.  
  162. 2   3   0   0
  163.  
  164. 0   11  4   15
  165. :[font = subsubsection; inactive; ]
  166. Checking for all the zeroes that the matrix has at this point
  167. :[font = input; startGroup; ]
  168. zerocheck
  169. :[font = print; inactive; endGroup; ]
  170. 11
  171. 22
  172. 33
  173. 34
  174. 41
  175. :[font = subsubsection; inactive; ]
  176. What kind of solution do we have now?
  177. :[font = input; startGroup; ]
  178. whatdoithink
  179. :[font = print; inactive; endGroup; ]
  180. POSSIBLE OPTIMUM goto OPTIMAL function
  181. :[font = subsubsection; inactive; ]
  182. Check for Optimum solution and find the optimal solution
  183. :[font = input; startGroup; ]
  184. optimal
  185. :[font = print; inactive; endGroup; ]
  186. NONOPTIMAL still go to Nonoptimal
  187. :[font = subsubsection; inactive; ]
  188. Modify the matrix by the HUNGARIAN way 
  189. :[font = input; startGroup; ]
  190. nonoptimal
  191. :[font = output; output; inactive; endGroup; ]
  192. TableForm[{{0, 6, 0, 3}, {13, 0, 5, 4}, {4, 3, 0, 0}, 
  193.    {0, 9, 2, 13}}]
  194. ;[o]
  195. 0   6   0   3
  196.  
  197. 13  0   5   4
  198.  
  199. 4   3   0   0
  200.  
  201. 0   9   2   13
  202. :[font = subsubsection; inactive; ]
  203. Check for the zeroes again in the new matrix
  204. :[font = input; startGroup; ]
  205. zerocheck
  206. :[font = print; inactive; endGroup; ]
  207. 11
  208. 13
  209. 22
  210. 33
  211. 34
  212. 41
  213. :[font = subsubsection; inactive; ]
  214. Check for the optimum solution again
  215. :[font = input; startGroup; ]
  216. optimal
  217. :[font = print; inactive; endGroup; ]
  218. OPTIMAL
  219. 13
  220. 22
  221. 34
  222. 41
  223. :[font = subsection; inactive; ]
  224. Tutorial for solving a given problem
  225. :[font = subsubsection; inactive; ]
  226. Introduction
  227. :[font = text; inactive; ]
  228. This tutorial allows you to solve any assignment problem you have, of any order. You will have to start the program by first clicking the INITIALIZATION cell. This clears out all the previous results stored.  Then you should click the DATA INPUT cell.  First, you will be asked to give the order of the matrix. i.e. 3,4,5 etc.
  229.  
  230. Then, click the ROW REDUCTION, COLUMN REDUCTION, ZEROCHECK, WHATDOITHINK  cells in that order. Depending on the message given by the last function, you will want to go either to OPTIMAL or NONOPTIMAL cell. If you are directed to OPTIMAL and OPTIMAL says "optimal", you will get the final solution and you are done. But, if you get the message "Non optimal still...go to NONOPTIMAL", then click NONOPTIMAL, ZEROCHECK, OPTIMAL in that order. Repeat the 3 function process until you are done. The Tutorial has appropriate messages at every point and so, please rest assured that you WILL get the solution even if you do not clearly comprehend what was just said in these two paragraphs. 
  231.  
  232. Whenever the tutorial says click the command etc., you are expected to place the cursor anywhere in that command line and press "Enter" ...not "Return" .  Good Luck!
  233. :[font = subsubsection; inactive; ]
  234. STEP1 : LOAD THE DEFINITIONS
  235. :[font = text; inactive; ]
  236. This is an essential step before solving any problem using this tutorial. This step loads the necessary function definitions stored elsewhere.
  237. :[font = input; ]
  238. <<hungarian.m
  239. :[font = subsubsection; inactive; ]
  240. STEP2 : INITIALIZATION 
  241. :[font = text; inactive; ]
  242. This step lets you clear out all the previous definitions and results and start afresh. This will have to be performed every time you would like to solve a new problem or if you would like to re-solve the problem that has been just solved.
  243. :[font = input; ]
  244. initialization
  245. :[font = subsubsection; inactive; ]
  246. STEP3 : DATA INPUT
  247. :[font = text; inactive; ]
  248. This step when performed, opens a dialog box for you to input the order of the matrix and the cost elements of the matrix.  You will have to press "Return" and not "Enter" after each input. The cost elements should be entered row by row. i.e. If you have matrix of order 2, then you will enter the elements in the following order:
  249.  
  250. row 1 & Column 1
  251. row 1 & Column 2
  252. row 2 & Column 1
  253. row 2 & Column 2
  254.  
  255. If you make a mistake in inputting the numbers, go back to INITIALIZATION and perform that and the following steps once again. You don't have to LOAD the definitions again, though.
  256. :[font = input; ]
  257. inputphase
  258. :[font = subsubsection; inactive; ]
  259. STEP4 : ROW REDUCTION
  260. :[font = text; inactive; ]
  261. This step finds the minimum element in each row and subtracts that number from each element of the respective row.These are nothing but valid matrix row operations which point at a possible minimum cost optimum solution.
  262. :[font = input; ]
  263. rowreduction
  264. :[font = subsubsection; inactive; ]
  265. STEP5 : COLUMN REDUCTION
  266. :[font = text; inactive; ]
  267. This step finds the minimum element in each column and subtracts that number from each element of the respective column.These are nothing but valid matrix column operations which point at a possible minimum cost optimum solution.
  268. :[font = input; ]
  269. columnreduction
  270. :[font = subsubsection; inactive; ]
  271. STEP6 : CHECKING FOR ZEROES
  272. :[font = text; inactive; ]
  273. This step when performed, enumerates all the zeroes in the matrix resulting from the row and column operations in steps 4 and 5. The rest of the tutorial involves manipulating zeroes to see if we have an optimum solution or to tell us what to do if we still have a nonoptimum solution.
  274. :[font = input; ]
  275. zerocheck
  276. :[font = subsubsection; inactive; ]
  277. STEP7 : WHERE DO WE GO NEXT?
  278. :[font = text; inactive; ]
  279. This step is designed to aid you to know where to go next.  When performed, you will get a message. If you get, "Possible Optimum go to OPTIMAL function" then click the input command in STEP8. If you get, "Non Optimal yet..go to NONOPTIMAL function", then click the input command in STEP9.  You will be directed further by those steps till you arrive at a final OPTIMAL solution.
  280. :[font = input; ]
  281. whatdoithink
  282. :[font = subsubsection; inactive; ]
  283. STEP8 : CHECKING FOR OPTIMUM SOLUTION
  284. :[font = text; inactive; ]
  285. This step checks for an optimum solution and if it finds one comes back and tells you
  286. "OPTIMAL" followed by the solution in terms of the row and column numbers. If it tells you "nonoptimal still...go to NONOPTIMAL", then you should click the command in STEP9.
  287. :[font = input; ]
  288. optimal
  289. :[font = subsubsection; inactive; ]
  290. STEP9 : MODIFICATION OF THE MATRIX
  291. :[font = text; inactive; ]
  292. This step modifies the matrix from the STEP5 according to the HUNGARIAN Algorithm. At the end of the process, you will see the resulting matrix. You will have to click the command in STEP6 again followed by STEP7.  Just follow the directions from there on in an iterative fashion until you arrive at an optimum solution.
  293. :[font = input; ]
  294. nonoptimal
  295. :[font = subsubsection; inactive; ]
  296. FINAL STEP 
  297. :[font = text; inactive; ]
  298. At this point, you will have an OPTIMUM solution in your hands.  If you want to save the calculations for yourself, then choose "SAVE AS" in the "WINDOW" menu and give the file a new name of your choice.
  299.  
  300. If you just want to quit without saving anything, then just choose "QUIT" in the main menu OR close the window by clicking on X and clicking NO in the dialog box that appears.
  301.  
  302. Thank you for using this tutorial!
  303. :[font = subsection; inactive; endGroup; ]
  304. Implementation Aspects
  305. :[font = subsubsection; inactive; ]
  306. Initialization Function
  307. :[font = input; ]
  308.  
  309. initialization := Block[{},
  310.                         k=.;v=.;g=.;h=.;i=1;j=1;
  311.                         Clear[cost,min,rred,cmin,cred,check,check1];
  312.                         
  313.                         Print[INITIALIZATION," ",DONE]
  314.                        ]
  315. :[font = subsubsection; inactive; ]
  316. Input Data Function
  317. :[font = input; ]
  318. inputphase := Block[{},
  319.                        n=Input["What is the square matrix order?"];
  320.                        Do[cost[xx,yy]=Input["Enter row by row,one
  321.                                               element at a time"],
  322.                                               {xx,n},{yy,n}
  323.                         ];
  324.                        costmatrix = Table[cost[y,z], {y,n},{z,n}];
  325.                        Print[TableForm[costmatrix]]
  326.                    ]
  327. :[font = subsubsection; inactive; ]
  328. Row Reduction Function
  329. :[font = input; ]
  330. rowreduction := Block[{},
  331.                         Clear[min,rred];
  332.                         Do[min[k] = Min[costmatrix[[k]]],{k,1,n}];
  333.                         Do[ rred[k] = costmatrix[[k]] - min[k],{k,1,n}];
  334.                         rowreducedmatrix = Table[rred[k],{k,n}];
  335.                         Print[TableForm[rowreducedmatrix]] 
  336.                      ]
  337. :[font = subsubsection; inactive; ]
  338. Column Reduction Function
  339. :[font = input; ]
  340. columnreduction := Block[{},
  341.                           Clear[cmin,cred];
  342.                           p = Transpose[rowreducedmatrix]; 
  343.                           Do[cmin[k] = Min[p[[k]]],{k,1,n}];
  344.                           Do[cred[k] = p[[k]] - cmin[k],{k,1,n}];
  345.                           q = Table[cred[k],{k,n}];
  346.                           colreducedmatrix=Transpose[q];
  347.                           Print[TableForm[colreducedmatrix]]
  348.                        ]
  349. :[font = subsubsection; inactive; ]
  350. Zero Check Function
  351. :[font = input; ]
  352. zerocheck := Block[{},
  353.                       Clear[check,check1];v=.;k=.;g=.;h=.;i=1;j=1;
  354.                       Do[
  355.                          If[ colreducedmatrix[ [k,v] ] == 0, check[i]=k;
  356.                              check1[j]=v;Print[k,v];i++;j++ 
  357.                            ],{k,n},{v,n}
  358.                         ];
  359.                       zerorows=Table[check[g],{g,1,i-1}];
  360.                       zerocols=Table[check1[h],{h,i-1}];
  361.                    ]
  362. :[font = input; ]
  363.  
  364. :[font = subsubsection; inactive; ]
  365. What Do I Think Function?
  366. :[font = input; ]
  367. whatdoithink := 
  368.                If[Length[zerorows]>=n,
  369.                   Print[POSSIBLE," ",OPTIMUM," ",goto," ",OPTIMAL," ",
  370.                   function],
  371.                   Print[NOT," ",OPTIMUM," ",YET," ",goto," ",
  372.                   NONOPTIMAL," ",function]
  373.                  ] 
  374. :[font = subsubsection; inactive; ]
  375. Assignment Function
  376. :[font = input; ]
  377. assignment := Block[{l1,l2,s,x={},y={}},
  378.                      If[iter != 0,
  379.                           t=Append[t,e[[iter]]];
  380.                           u=Append[u,f[[iter]]];
  381.                           l1=Length[e];
  382.                           x={};y={};x=e;y=f;
  383.                           Do[If[First[x] == Last[t], 
  384.                             e=Drop[e,{1,1}];x=RotateLeft[x];
  385.                             f=Drop[f,{1,1}];y=RotateLeft[y],
  386.                             x=RotateLeft[x];y=RotateLeft[y];
  387.                             e=RotateLeft[e];f=RotateLeft[f] ],{s,l1}
  388.                             ];
  389.                           x={};y={};x=e;y=f;l2=Length[e];
  390.                           Do[If[First[y] == Last[u],
  391.                                f=Drop[f,{1,1}];y=RotateLeft[y];
  392.                                e=Drop[e,{1,1}];x=RotateLeft[x],
  393.                                y=RotateLeft[y];x=RotateLeft[x];
  394.                                f=RotateLeft[f];e=RotateLeft[e] ],{s,l2}
  395.                             ]
  396.                       ]; (* end of outermost IF *)
  397.                       If[Length[e] == 0,iter=0,iter=1] 
  398.                     ] (* end of BLOCK *)  
  399. :[font = subsubsection; inactive; ]
  400. Optimal Check Function
  401. :[font = input; ]
  402. optimal := Block[{soln,l,r},
  403.                    l=Length[zerorows];objective=0;
  404.                    For[i=1,i<=l,i++,
  405.                         t={};u={};tu={};
  406.                         e={};f={};e=zerorows;f=zerocols;iter=i;
  407.                         Do[assignment,{soln,n}];
  408.                         tu=Intersection[t,u];
  409.                         If[Length[tu] == n, Print[OPTIMAL];
  410.                                          Do[Print[t[[r]],u[[r]]];
  411.                         objective += costmatrix[[t[[r]],u[[r]]]],{r,n}];
  412.                         Print[OBJECTIVE," ",COST," ",IS," ",objective];
  413.                                          Break[] 
  414.                           ]
  415.                       ];
  416.                     If[i==l+1,Print[NONOPTIMAL," ",still," ",go," ",
  417.                                 to," ",Nonoptimal]]
  418.                   ]
  419.                                          
  420. :[font = subsubsection; inactive; ]
  421. Non Optimal Modification Function
  422. :[font = input; ]
  423. nonoptimal := 
  424. Block[ {z,rows={},cols={},uncovered={},common={},iteru,iterc,q2={}},
  425.           z=n;q2=colreducedmatrix;timen=1;timen++;
  426.           While[z != 0,
  427.              For[row=1,row <= n,row++,
  428.                If[FreeQ[rows,row],
  429.                  If[Count[q2[[row]],0] ==z, rows=Append[rows,row];
  430.                                         q2[[row]]=q2[[row]]+1
  431.                                              ] (*endif*)
  432.                   ] (*end outer If *)
  433.                 ]; (* end of For loop *)
  434.                                                 
  435.                  q2=Transpose[q2];
  436.                  For[col=1,col<=n,col++,
  437.                    If[FreeQ[cols,col],
  438.                     If[Count[q2[[col]],0] ==z, cols=Append[cols,col];
  439.                                            q2[[col]]=q2[[col]]+1
  440.                                             ](*endif*)
  441.                      ] (*end outer If *)
  442.                     ]; (*end of FOR loop *)
  443.                   q2=Transpose[q2];
  444.               z-- ]; (*end of WHILE loop *) 
  445.       For[row=1,row<=n,row++,
  446.          For[col=1,col<=n,col++,
  447.              If[FreeQ[rows,row] && FreeQ[cols,col],
  448.                 uncovered=Append[uncovered,colreducedmatrix[[row,col]]]
  449.                ];
  450.              If[MemberQ[rows,row] && MemberQ[cols,col],
  451.                 common=Append[common,colreducedmatrix[[row,col]]]
  452.                ]
  453.             ] (* end of inner For loop *)
  454.          ]; (* end of outer For loop *)
  455. minuncov=Min[uncovered];iteru=1;iterc=1;
  456. For[row=1,row<=n,row++,
  457.  For[col=1,col<=n,col++,
  458.    If[FreeQ[rows,row] && FreeQ[cols,col] && iteru<=Length[uncovered],
  459.         colreducedmatrix[[row,col]] = uncovered[[iteru]]-minuncov;
  460.         iteru++
  461.      ];
  462.    If[MemberQ[rows,row] && MemberQ[cols,col] && iterc <= Length[common],
  463.         colreducedmatrix[[row,col]] = common[[iterc]]+minuncov;
  464.         iterc++
  465.      ]
  466.     ] (* end of inner for loop *)
  467.    ];  (* end of outer for loop *)  
  468.  TableForm[colreducedmatrix]
  469.  
  470.  ] (*end of Block *)          
  471. :[font = subsubsection; inactive; ]
  472. Command for Saving the function definitions in a FILE.m (Change the filename)
  473. :[font = input; ]
  474. Save["hungarian.m",initialization,inputphase,rowreduction,
  475.         columnreduction,zerocheck,whatdoithink,assignment,
  476.         optimal,nonoptimal]
  477. :[font = subsubsection; inactive; ]
  478.  Command for CLEARING the function definitions 
  479. :[font = input; ]
  480. Clear[initialization,inputphase,rowreduction,
  481.         columnreduction,zerocheck,whatdoithink,assignment,
  482.         optimal,nonoptimal]
  483. ^*)