hum-013*. «W;kqu - ’25:».- ”W5“ .—.. “5- ' O } i ' I Q 1 O I l I A“ o '-'O O ‘0 c I u ..— H» *o v' ‘ ' , a- m - -..--.-—-“-. “V I... ——~-f.o|.'~"" ' ‘ ‘ ' 0....“ ~: “1"7'2‘.. an.» O '0" ‘ 3'? ' ' to. r . -h.‘"—‘ - 'W I . .0-QOOO*O ' .O ‘. 3.. ADV-‘4..- . 0 "Fl '9' W...” O ‘ ‘ _v- " - 0- 1 . fa.“ W'- c.‘~”0.l1'4. 9"» In. “ 00.0...rw . W‘ 1;) ‘3 '-“-‘-'- ‘-"‘.".’.’.r. J | O l.l | I H |-' O O. . . .' J' i J I ,0 5 _$ .4 9‘: “g I c." O _uo‘..... m-tt uI-w-- I 0 O , . o". h-f-auu- ‘7'. “—. 5'03}: M \u-‘O-‘v 0‘00 0- ”So. u . . o I V ' '- ~ . n 'I .. r . o... . "J—-'. g.- ' ,v-0 5.: vi) ‘.1 o o... f'(;' O! o ”Jul-mm Vl'bo’ub-Mor¢-t J" 5 4 .' a - O o d‘ ‘. Ilia ' Ar;- .. ) . . . . . O .: O . ‘ .- .o - _ . a ‘ . ‘ .ad 1 0 I. . . '. ' ' _ s _ __ _.- _ V ‘ - ° _ - '7' ‘1 (~15. I " ‘ ~ ° 4' ‘ 4 °.‘_ .. -- i - -' ' '. '-~‘ ‘« ~ ‘ ..'.“.. ‘ -'-".~" g.-ux“"~‘:‘:4:: 9: u " ‘ .' ' ' ‘ -5‘ ' ' ’ " ' ..’ s ' " v " '. .. J) v'fi‘w'fi.' fi-I . A‘AJ- ‘~. 0.. .‘U' ' ‘ . _ ._ v. . I ‘I L; ,1 J._ > " I A. . . _n. I _ '.. 9 o ):H' ‘._ _ . I.. ~ , }.‘ . 0‘ I‘I ' ‘0': ' . . . .I f. . ..‘ I O ' .-. 1 '-“"~."" :. -o-.~- ‘ ' A .0‘0' 0 0 - '- ‘ " ' ' A. .9‘ — o - g ' 0‘ '- . no 0-! ‘ a. - |.-‘ “h x ' " w °-- ‘ -~. .' ‘ . ' . ‘ ‘ ‘~ ”y." . “1"! -’I ~ .“ -’.‘;..-.: mm 0. . . -.- .‘~— ‘ . . ,I...L . . _ ‘t .o' 1 I ._ ';:- our \“_¢- ‘. :3 .c‘ ”-3.: .‘ mr‘. .. [J .5 “ ‘. I' ' .l I O ' 3.. '5 o ~“"tI;'a ‘- ‘ . ‘ ' ' ‘ .1 '.- ‘¢1._._‘ f ‘0 - 'm°".— . :4: J -‘l l.'. . o .0 o . Y , . - J" . _l p----- ‘ ‘. .1 - ‘ I' I .0 ~ . k..$ ‘, ' n-.l «gm ‘ . “v I ‘ ' _ . . . ' pg - "' 4-. "' ' - O--.“ n- - ‘. . .‘ -" ' . .. ' . . ‘ - ' r' __« - 2,.) :“fi‘ 4.. I. 5 ‘ v . 0- - .‘ I 1. . A . a . . no 0 _ I . | 0' ' __ o . ' D" O - '_ ‘ . . o .- O .2. . ‘ v" ' ' ' - O . ' .‘. I' . o u .' ' . . f o .‘I ' . ‘ . U. v (Q‘- .‘ U A ¥ - I . q . . ‘ 9 ' _ 9 ’ . ‘ I _ O . . - . I- u . - . ..‘ s ' I O — . - \ ~' ‘ ‘ 4.- . - | a. l. — ‘ J . u . - Z. '.. ‘ q . r. - ' ‘ ‘ . .‘ .v' ' -.*- . . I ‘ '_jv ....'|'I‘-“' |"|"... ‘ ‘ .‘J ‘r ~"..:I _ . -_l.0| .._; .: Oq’h 1-5.?- m o — ‘ ~ _ o ,- '0“ 0- 4“ .. ‘ '4:- _ - g. -' . .v-U- " - 0.. , '.A 0 ‘ ' _ - - '4. ' .9. . .- o " ‘ ’9 I'l ' ,,_ __ I... VI :3. . ”—" o . » - -'-—‘ '0‘ _ . o ., “x" “" ..I t- .I D: --J.- . 4 '.n ‘1!- .., . ‘1 .g. .._ *6. o»... ' ‘ Io - ' _ Jor. t . .11... y -“ ' 0" ' I ? ‘ _ ' .. O .‘.. :4. H.- ." p'. ' « ‘~‘ q-.1‘.:. DEVELOPMENT OF REFINED MATHEMATICAL PROGRAMMING METHODS FOR INDUSTRIAL ENGINEERING PROBLEMS By Robert W. Metzger AN ABSTRACT Submitted to the College of Engineering Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Mechanical Engineering 1957 Approved ABSTRACT Metzger, Robert W. , M. S. , Michigan State University, March 1957. DEVELOPMENT OF REFINED MATHEMATICAL PROGRAMMING METHODS FOR INDUSTRIAL ENGINEERING PROBLEMS. Major Professor: W. P. Smith. Mathematical programming is presented in a broader concept than linear programming and as one facet of the broader field of Operations Research. The methods of mathematical programming namely; the modified dis- tribution method, Vogel's approximation method and the simplex method are presented in an easy to understand step by step manner, and further illus— trated via typical though simple problems. Situations of degeneracy, unequal supply and demand, and other miscellaneous restrictions are included in the discussion of the distribution methods. Degeneracy and types of algebraic relationships are included in the discussion of the simplex method. Two larger problems, a production planning and a manufacturing problem are presented and solved. The problems are formulated and solved in a logical step by step manner to further illustrate the application of mathematical programming in solving industrial problems. The production planning problem is the first of its kind to be presented in its entirety. Mathematical notation is simplified and minimized. No attempt is made to prove the methods and their various theorems but liberal references are provided for the student who wishes to pursue the subject. The thesis is summarized by discussing the advantages, prerequisites and limitations of mathematical programming as well as typical problem areas. In the conclusions several possible areas for further research are presented and discussed. J‘ll‘r iii ll I'll!" DEVELOPMENT OF REFINED MATHEMATICAL PROGRAMMING METHODS FOR INDUSTRIAL ENGINEERING PROBLEMS By Robert W. Metzger A THESIS Submitted to the College of Engineering Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Mechanical Engineering 1957 Rise I. II. III. IV. VI. TABLE OF CONTENTS Introduction .......................... Mathematical Programming Methods .............. Modified Distribution Method ................. A Problem ......................... Unequal Supply and Demand .............. . . Degeneracy ........................ Alternate Solutions .................... Summary ......................... Vogel's Approximation Method ................ The Simplex Method ..................... A Problem ......................... Degeneracy ......................... Types of Relationships ................... Geometric Interpretation ................. Summary ....... . ................. A Production Planning Problem ................. The Problem .................. . . ..... Data.... .......... Formulation ........................ . Optimum Solution .................... . . Analysis of the Optimum Solution ............... Summary ................. . ........ . A Manufacturing Problem .................... The Problem ......................... Problem Formulation .............. . ...... Solution... ......... . ......... Summary . ............ . ............. .Summary... ............ ....... . Conclusions ........................... Appendix ............................. Bibliography ............ . . ........... . . 10 21 23 27 27 29 31 33 43 44 50 54 55 55 57 61 62 62 65 65 65 69 71 73 78 80 81 II. III. IV. VI. VII. VIII. VIIIa. IX. XI. XII. XIII. XIV. XV. XVII. XVIII. XIX. XXI. . Distribution Matrix (Route Table) LIST OF TABLES Distribution Matrix (Route and Cost Tables Combined) Mileage Chart ...... Shipping Costs Per Unit (Cij's) ................ . Distribution Matrix . . . Northwest Corner Initial Solution . 00000000000000 Initial Solution R1 and Kj Values Established ......... Changes in Initial Assignments ................ Changes in Initial Assignments . . . . . Distribution Problem -- Unequal Supply and Demand . Distribution Problem -- Balanced Supply and Demand Distribution Matrix —- A Degenerate Problem ....... . Degenerate Distribution Problem -- An Initial Solution . . . Degenerate Distribution Problem -- Degeneracy Resolved Problem Equations in Matrix Form Initial or Trivial Solution . Initial Solution Objective Function Included Initial Simplex Tableau O O O O O Q 0000000000000 Initial Simplex Tableau Key Row and Column Indicated Main Row of New Tableau . Simplex Tableaus I and II Initial Simplex Matrix - - Optimum Solution ii Page 10 11 12 13 14 16 18 19 21 22 24 25 26 35 36 36 37 38 39 4O 68 Page XXII. 1957 Data for Production Plan Straight Time Production Capacity ............................. 90 XXIII. 1957 Data for Production Plan Overtime Production Capacity . 91 XXIV. Unit Costs for Production and Storage ............. 92 XXV. Distribution Matrix -- Production Planning Problem ..... 94 XXVI. Distribution Matrix -- Optimum Production Plan ....... 95 XXVII. Simplex Solution to Manufacturing Problem .......... 96 XXVIII. Equally Optimum Alternate Solution .............. 97 iii Figure 1. Figure 2. Figure Figure Figure Figure Figur e Figure Figure 3. 4. 5. LIS T OF FIGURES Problem Equations Graph ............... Problem Equations Graph Profit Function Included . . Optimum Solution . 4. . ........ . . ........ Straight Time Production Data -- Sample Calculations Overtime Production Data -- Sample Calculations Unit Cost Calculations ........... I ..... Storage and Inventory Charges -- Sample Calculations ...................... Final Optimum Solution ................ Final Solution -- Cost Summary ............ iv MATHEMATICAL PROGRAMMING APPLIED TO INDUSTRIAL ENGINEERING PROBLEMS I. INTRODUCTION Mathematics has always been a useful tool to industrial engineers. Yet, until recently the full capabilities of certain mathematical techniques in solving industrial engineering problems have not been realized. This thesis presents a new and powerful tool called mathematical programming which offers a new perspective in solving many industrial problems. Mathematical programming is one facet of the larger field of operations research. Operations research refers to the application of the scientific methods of the physical sciences to analyzing and solving complex business problems. Operations research, as such, had its beginning during World War II when scientists were employed by the British armed forces to apply their scientific knowledge to problems of strategy and tactics. In many respects it is unfortunate that the work of an early operations researcher, Thomas A. Edison, fell into obscurity. Mr. Edison, while chairman of the Naval Consulting Board during World War I, became involved in various tactical problems.1 It is interesting to note how many of his developments had to be rediscovered to reach their full usefulness in World War 11. Operations research was more effective in World War II primarily due to organization. The Naval Consulting Board was a group of civilian advisors reporting to a civilian, the Secretary of the Navy. Whereas operations research groups in World War II usually worked for and reported to an operational command. Therein lies the chief reason for the wider use and general acceptance of operations research results by command personnel during World War 11. During the post war period, operations research personnel, usually called operations analysts, entered industry to apply their military proven methods 1Scott. Lloyd N. Naval Consulting Board of £13 United States, Government Printing Office, Washington. 1920. See also Wm. F. Whitmore, ‘Edison and Operations Research, [ournal _01 £3 Operations Research Society 31 America. Vol. 1, No. 2, February, 1953. P. 83- 5. to solving industrial problems. Unfortunately many of the results derived by the early operations research groups were little more than results that could have been achievedlby the application of good common sense. This factor plus the often highly sophisticated and complicated notation and writing of operations analysts caused management to summarily dismiss operations research as just a new name for the same thing industry has been doing by committee for years. This explains the generally slow acceptance of operations research in American industry. Operations research actually differs from anything industry has done in the past, chiefly in method and approach to a problem. Operations research requires an exacting statement of the problem. All the variables and factors with their proper interrelationships must be included. The tools of operations research include some very advanced mathematical techniques which make precise formulation a prime requisite. When this becomes an established habit, then the new viewpoint of operations research is possible in attacking industrial problems. This thesis will be limited to that portion of operations research called mathematical or linear programming. The term mathematical programming will be used throughout the thesis since it implies a broader concept than linear programming. Mathematical programming has been defined from time to time as follows: ". . a method for picking a best choice when choices exist. . . . a formal method of calculating the best solution to a problem or situation where many solutions or management decisions are 2possible, depending on certain limiting conditions. " ". . . a number of new procedures which make it possible for management to solve a wide variety of important company problems much faster, more easily, and more accurately than ever before. " ". . . is used to find the optimum relationship between a number of interdependent variables where the inter- relationships are algebraically linear. "4 2Ferguson, Robert O. , Linear Programmirg, American Machinst Special Report No. 389. McGraw- Hill Company, 1955. 3Henderson, A. and Schlaifer, R. Mathematical Programming: Better Information for Better Decision Making, Harvard Business Review. V. 32, No. 3. May-June, 1954. Pp. 73-100. 4601—2153. M. , and Koenigsberg, E. Operations Research: Scientific Approach to Management, Chemical Week. McGraw-Hill Company, May 21, 1955. ". . . the theory by which activities -- independently variable and subject to certain restrictions -- related to each other in linear fashion . . . are arranged to obtain maximum results. "5 ". . . methods of solving a general class of optimization problems dealing with the interaction of many variables subject to certain restraining conditions. "6 In essence then mathematical programming consists of several methods used to find the optimum combination of variables interrelated in linear expressions. In general the number of variables exceeds the number of significant expressions. This thesis will consider the two primary methods of mathematical programming, namely the Distribution and Simplex methods. The Distribution methods will be considered first, since these are the easiest to understand and use. These methods are applicable to problems of product distribution and to transport problems. Hence the name distribution methods. It is important‘to note though, that these methods can be successfully applied to other types of problems. However, in these cases the problem can be abstracted into a type of distribution problem. The Distribution methods are, in reality, three methods. They are: 1. Basic Distribution Method or "Stepping Stone" method. 2. Modified Distribution Method. 3. Vogel's Approximation Method. One of the earliest approaches to solving distribution problems using formal mathematical methods appeared in 1941.,7 During World War 11 significant improvements in the solution methods occurred. In 1951 5 Ibis, 6Arnoff. E. L. The Application of Linear Programming to Production Engineering and Scheduling, ASME Paper No. 54- A-223 presented at the Annual Meeting, November 28-December 3, 1954. 7Hitchcock, Frank L. The Distribution of a Product from Several Sources to Numerous Localities. Journal p_f Mathematics a_nd Physics, Vol. 20, 1941; Pp. 224-230. considerable advance was given to operations research and mathematical programming by the Cowles Commission8 and particularly to the solution 10 The Basic Distribution Method is properly credited to G. B. Dantzig. However, of distribution problems by G. B. Dantzig9 and T. C. Koopmans. the methods were still difficult for a non-mathematician to understand. The "stepping stone" method devised by W. W. Cooper and A. Charnes 11 essentially presented Dantzig's method. However, the terminology was such that the "stepping stone" method could be very easily understood by the average person. The solution methods were somewhat improved in 1954 12 and fulrgther refined to the Modified Distribution Method which appeared in 1955. The Modified Distribution Method, while it is based upon the "stepping stone" method, so improved the computation procedure that it has supplanted the "stepping stone" method. Therefore, the "stepping stone" method will not be discussed here. Vogel's Approximation Method 14 permits a much better initial solution than can usually be had by any other means. Vogel's Approximation Method with the modified distribution method permits more rapid hand computation of problems heretofore only practical to solve with electronic computors. 8I 80 - 27o Demand 90 70 50 60 270 The changes are then shown in Table VIIIa. Note that the initial assignments have been crossed out and the new assignments made. Note also that the rim conditions (supply and demand figures) are still met. Making this change essentially involved adding and subtracting the same quantity from each of two rows and two columns, thereby leaving the rim conditions unchanged. This improved solution may be checked to determine the amount of improvement attained. This improved solution shows a savings of $390. 00 over the initial Initial N. W. Corner Solution Square No. Units Cost/ Unit RlKl 90 $27. 00 R1K2 60 23. 00 RZKZ 10 45. 00 R2K3 30 40. 00 R3K3 20 35. 00 R3K4 60 57. 00 First Improved Solution m No. Units Cost/ Unit RlKl 80 $27. 00 R1K2 70 23. 00 R2K1 10 10. 00 R2K3 30 40. 00 R3K3 20 35. 00 R3K4 60 57. 00 Total Cost $2, 430. 00 1, 380. 00 450. 00 1., 200. 00 700. 00 3, 420. 00 $9, 580. 00 Total Cost $2,160.00 1,610.00 100.00 1,200.00 700.00 3,420.00 $9,190.00 20 N. W. Corner Solution. . Note that this amount is exactly equal to the number of units moved times the water square evaluation for square R1K2. RK 1 2 Water square evaluation Number of units moved -39 10 Net savings by improvement $390. 00 21 Hence the water square evaluation can be used to predict the amount of improvement step by step. These are essentially the steps required in the Modified Distribution Method. This iterative process is continued until all water square evaluations are positive or zero, at which time the optimum solution is at hand. The problem discussed here had balanced rim conditions and was not degenerate. These two situations will be considered now. Unequal Supply and Demand.- When supply exceeds demand or vice versa, it is desirable to allow the mathematics to determine which source retains some of its supply or which customer must be short on his order. To do this arbitrarily might defeat the solution to the problem. This condition is easily accomplished if we consider the same problem as above with the supply at Janesville increased to 55 units. The problem then appears as in Table IX. The northwest corner solution indicates that 15 units will always remain in the St. Louis warehouse. Table IX. Distribution Problem Unequal Supply and Demand To From Chicago Cleveland Dayton Minneapolis Supply -27 - 23 - 31 — 69 Flint 150 - 10 -45 -40 -32 55 Janesville -30 -54 -35 -57 ‘ 80 St. Louis ® 285 Demand 90 '70 50 60 2'70 1...... a}... .. a. , .1... a e. x . ,. _, ,. _....t.£.., Lu»... ..... . . g a. . \ 5|.ll 1’ ll? '51 '11! 22 It would be better if the problem were set up to allow the mathematics to determine which warehouse retains a portion of its supply. This can be accomplished by inserting a dummy customer with a demand of 15 units. This will balance the rim conditions. Table X. Distribution Problem Balanced Supply and Demand To From Chicago Cleveland Dayton Minneapolis Dummy Supply - 27 - 23 ~31 - 69 0 150 Flint - 10 ~45 -40 - 32 0 55 Janesville -30 -54 - 35 -57 0 80 St. Louis @ ® 285 Damand 90 70 50 60 15 285 4 L...» fr; .mMnand‘..-q _.?........_u.u...__..,.“.m.b .59....” V1 .1 _. . ~ . a .1 Luv»! _., .x— 23 The cost factors for the dummy customer are zero, since the dummy customer represents a fictitious demand for units that will in reality remain in a warehouse. In certain situations it may be desirable to insert inventory costs for the various warehouses in the dummy column rather than zeros. The problem will then minimize distribution and inventory costs. Now that the problem is set up the modified distribution method may be used to obtain the optimum answer. Much the same approach is used when demand exceeds supply. Here a dummy warehouse (row) is established and the problem developed in much i! i. the same manner as discussed above. Occasionally it may be impossible to ship from a warehouse to a certain customer. When this situation arises then the cost of shipment between the two is considered as -M. The symbol -M being defined as so large that it dominates all else in the problem. Hence that shipment is mathematically factored out of the problem. This added technique permits a wide range of management restrictions to be considered in a problem. Degeneracy. This occurs in mathematical programming problems when the problem begins to cycle (i. e. , return to the same solution), or when an infinite number of steps are required to obtain an answer or when the solution method begins to collapse before an optimum answer is obtained. Obviously, all of these conditions can occur when errors are present in the work. However they can also occur due to the nature of the problem. In distribution problems degeneracy is most apparent when the rim conditions are similar. Consider the previous problem with slight modification in rim conditions as shown in Table XI. - .143. .. . runs...» _.- r... .2 q LJMVfimm . ... 5.. . a, .- . a... .040; ‘ _.V . .. .2 TABLE XI. DISTRIBUTION MATRIX A DEGENERATE PROBLEM 24 owm om ov or om vamp—0Q own ow 3:04 Jw rm: mm: «an- cm: 3. 2:38.: am: ovi n13: oHi cm: “5; mo. Hm: mm- rm: 332m £032.52 :9er 3395—0 omaoEU EOE OH. EoEonm mamaocomom < OSHA—m2 COSSQTSWHQ .HN mfinmrfi «adagifi. than. w.“ m3. 44:...2m V1 Err. . I). “a. ! nwt. W -1! The initial northwest corner solution would then be as follows: Table XII. Degenerate “Distribution Problem An Initial Solution 25 To From Chicago Cleveland Dayton Minneapolis Supply - 27 - 23 -31 - 69 Flint 160 - 10 - 45 -40 - 32 Janesville ® 40 - 30 - 54 - 35 - 57 St. Louis 80 280 Demand 90 70 40 80 280 The degeneracy would be evident when attempting to establish Bi and K. J values. If R1 = 0 is assumed then K1 and K2 can be determined. Here it is impossible to proceed further. west corner solution is missing. Actually the problem matrix (Table XII) can be partitioned into three parts as it now stands. Note that the stair step pattern of the north- The degeneracy can be resolved by inserting zero stones (0) wherever needed. This has no effect upon the real problem but does afford a useful gunmick to permit solution of the problem. 26 _: I! . - ...-..——,..-- __._ TABLE XIII. DEGENERATE DISTRIBUTION PROBLEM DEGENERACY RESOLVED omm cm ov 2. cm use—bun— cmm cm Q 6 3:04 Jm r m 1 mm .. «em. u on u 3. @ ® 0:33: 3 mm .. on"? 9.1 GH 1 om: 6 Sim mo 1 Hm 1 mm 1 pm .. . a L . 333 333552 grann— vafl o> 20 030sz EOE OB EoEOnm OOSOOEHEQ manposomom OoZOmom homeosomom A L .Ex Bree H 27 Now the remaining Ri and Kj values may be computed. Actually there is considerable lattitude as to the placement of the zero stones. However only the correct number of stones may be used. It can be seen from the previous problems that m + n - 1 represents the number of stones or assignments. If less than 111 + n - 1 stones exist then the problem is degenerate.16 This applies similarly for any step in the solution method. When more than m + n - 1 stones exist usually it implies that an error has been made. Alternate Solutions. The modified distribution method permits very rapid evaluation of alternate solutions by way of the water square evaluations. a _.A-e—si :6 The economics of alternate courses of action can be quickly evaluated for both equally optimum or less-than-optimum solutions. The water square evaluations predict the per unit increase or decrease in costs for any change in the solution. Obviously then when one or more zero water square evaluations exist in a final solution then many equally optimum alternate solutions exist for the problem. If for some reason management says that a particular solution cannot be carried out, then an alternate solution can be developed. The difference in costs resulting from such a decision is readily available and management has then a concrete cost value for that decision. This presents some very interesting and most useful information for management. Summary. The modified distribution method presents a very simple and useful means to solving distribution type problems. It is significant to note that, while costs were used throughout the discussion, wherever the word cost appeared the word profit could be inserted. Obviously the rational executive wishes to maximize profits. Hence profits would be expressed as positive numbers. This handling of costs as negative and profit as positive numbers involves exactly the same mathematics to minimize costs or maximize profits. 16See Dantzig. G. B. Application of the Simplex Method to a Transportation Problem in Activity Analysis of Production and Allocation, p. 360. 28 Distance and time are two other factors that can conceivably be used in distribution type problems. It is entirely possible to have problems with both cost and profit elements. Here the mathematics is unchanged and the optimum solution will both maximize profits and minimize costs. The steps of the modified distribution method can be summarized as follows: 1. Set up the problem distribution matrix. 2. Balance the rim conditions (supply and demand). 3. Establish initial solution. a. N. W. corner solution. b. Inspection solution. Note: The number of stones = m + n - 1 4. Establish R and K values. R1 = 0 ' R + K = Cost or profit at an intersecting stone square. a. Resolve degeneracy as may be necessary with zero stones (0). 5. Evaluate each water square. R + K - (Cost or profit of water square) a. If above is positive (+) then no further improvement is possible. ~ b. If above is negative (-) then there is further improvement possible. 6. Select the water square with the greatest negative value. a. Establish a closed path (as a rook moves in chess) from this water square via stone squares back to the same water square. There will be one and only one such path. b. Establish alternate plus (+) and minus (-) signs on this path starting with a plus (+) in the particular water square. This should still permit balanced rim conditions to exist. 7. 8. 9. 10. 29 Determine the amount to be placed in the selected water square as the smallest stone at a negative place on the closed path. Place that smallest stone in the selected water square. Make the desired changes by adding or subtracting that selected amount from every stone in the path. Re-establish R and K values as may be necessary. Repeat steps 5 through 10 until all water square values are plus (+) or zero (0). Interpretation of the water square evaluations: 1. A positive number indicates the per unit increase in cost or reduction in profit that would result when a stone for one unit is placed in the water square and the necessary adjust- ments are made in the program so as not to violate the rim conditions. A negative number indicates the per unit decrease in cost or increase in profit that would result when a stone for one unit is placed in the water square and the necessary adjust- ments are made in the program so as not to violate the rim conditions. When one or more water square values are zero and the remaining water square values are all positive numbers (greater than zero) there exists one or more equally optimum alternate solutions to the problem. Mathematically speaking if two equally optimum alternate solutions exist then an infinite number of equally optimum alternate solutions exist for the problem. Vogel's Approximation Method 17 Vogel's approximation method is a technique for developing an initial solution to distribution problems. In most cases this method will develop a much better solution than could be developed by inspection. The work required to successfully solve distribution type problems is materially reduced when a better initial solution is obtained. 17 , , Credited to Mr. W. R. Vogel. This material will be included in Mathematical Programming fgr Industrial 529 Systems Engineers by N. V. Reinfeld and W. R. Vogel (in preparation). 30 Vogel's approximation method can be applied when the distribution matrix is established and the rim conditions balanced. The steps of the method are: 1. For each row and column determine the difference between the two most algebraically maximum cost or profit elements. 2. Select that row or column with the greatest difference and assign as many units as possible to the square associated with the most algebraically maximum element (lowest cost or highest profit square). 3. Cross out that row or column that has been completely utilized or satisfied. 4. Redetermine the differences as in step 1, neglecting the row(s) or column(s) crossed out. 5. Repeat steps 2 through 4 until all assignments have been made. 6. Check the assignments and improve the solution with the modified distribution method. Several supplementary steps may be required when the same difference occurs in two rows or columns or in a row and column. These steps are: 7. When the same difference occurs in a row and a column and the cost (or profit) element at the junction is the lowest (or highest) then assign as much as possible in that square. If the junction is not the lowest cost or highest profit then assign in either the row or column wherever the lowest cost or highest profit prevails. 8. When the same difference is obtained for two or more rows or columns then assign wherever the lowest cost or highest profit element prevails. It is possible to recognize and resolve degeneracy when applying Vogel's approximation method. 9. If, when an assignment is made both a row and column are fulfilled simultaneously the problem is degenerate. Resolve degeneracy by placing a zero stone (0) in a remaining square in either the row or column. Experience with Vogel's approximation method indicates that the optimum answer is usually obtained immediately in smaller distribution type 31 problems. In larger problems it is safe to estimate at least seventy-five per cent of the work is eliminated by using this method to obtain an initial solution. It is felt by the author that Vogel's approximation method is superior to the method offered by Mr. H. s. Houthakker.18 Mr. Houthakker's method is limited to a class of problems possessing a unique cost pattern. Vogel's approximation method can be applied equally well to any type distribution problem. The Simplex Method The origin of the Simplex Method is properly credited to G. B. Dantzig.19 Various extensions have been made notably by Beale, Charnes, Cooper, Lemke, Orden and Wolfe which have made the simplex method rather mechanical and reasonably simple to understand and use. The simplex method is a method of algebraic manipulations used to solve systems of linear equations where one solution of an infinite number of solutions is desired. The method is much like Gauss' scheme (Doolittle's method) for solving systems of linear equations. Several other methods . notably the relaxation method exist for solving systems of linear equations but these are beyond the scope of this discussion. This section will present the Simplex Method much like that offered by Charnes and Cooper 20 except that the terminology employed here will be less rigorous. The proof of the method and its various theorems will not be presented here for three reasons: First, the proofs are well developed in numerous publications, notably in the work by Dantzig and Charnes and Cooper; secondly, an understanding of the theorems and their proofs is unnecessary to effectively use the Simplex Method; third, the author lacks the high degree of mathematical maturity required to successfully accomplish such a venture without virtually copying from other authors. is Houthakker, H. C. "On the Numerical Solution of the Transportation Problem", journal gt: t_h£ Ogrations Research Society pf America, Volume 3, Number 2. May, 1955. Pages 210- 214. 19Koopmans, et al. Chapter XXI. pages 339-347. Op. cit. 20Chames, Cooper, Henderson. Op. cit. 32 The Simplex Method can best be illustrated via a typical manufacturing problem. The general mathematical statement of the problem will be developed then a specific problem will be solved. If we let j = (1, 2, --- n) the commodities to be produced i = (1, 2, ~—- m) the machine tools or manufacturing processes xij = number of units of the j'th commodity produced on the i'th manufacturing process tij = time required to manufacture one unit of the j'th commodity on the i'th manufacturing process i = total available time on the i'th manufacturing process Pij = the profit derived from the sale of one unit of the j'th commodity that was produced by the i'th manufacturing process and an assumption is made that all that is produced can be sold, then the rational executive would want to manufacture the commodities so as to realize the greatest possible profit. Mathematically this would be stated: to determine the xij's so as to maximize p11 x11+p12 x12 +. . . . +pij xij+° . . . +pmnxmn subject to the following: t11 x11 +t12 x12 . . . . +t1jx1j+ . t1n x1n T1 t21X21 + t22 x22° ' + ’2. 23 + t2n x2n T2 h r-l t +t . .+ . . . m1 xm1 + m2 xm2 +° ' mj Xmj tmn Xmn m 33 This set of relationships could also be expressed: .x..=’T. n m 2 t. ij 1j 1 I—tb—l i J In essence the above says to determine how much of each commodity to manufacture so that the maximum profit can be realized and at the same time not exceed the available time on the various manufacturing processes. The Simplex Method can accomplish this. . A Problem. Consider a specific problem much like the above general case. A manufacturer wishes to determine how to produce two products (A and B) so as to realize the maximum total profit from the sale of the products. Both products are made in two processes (I and II). It takes 7 hours in process I and 4 hours in process II to manufacture 100 units of product A. It requires 6 hours in process I and 2 hours in process II to manufacture 100 units of product B Process 1 can handle 84 hours of work and precess II can take 32 hours of work in the schedule period. If the profit is $11. 00 per 100 units for product A and $4. 00 per 100 units for product B then how much of product A and B should be manufactured to realize the maximum profit. It is assumed that whatever is produced may be sold and that setup time on the two processes is negligible. While this is a relatively simple problem it will serve to illustrate the simplex method. In terms of the previous symbolism the problem can be expressed thusly, j‘ = 1, 2 the commodities to be produced 1 = Product A, 2 = Product B i = 1, 2 the manufacturing processes 1 = Process 1, 2 = Process 11 x1 = number of units (x100) commodity A produced number of units (x100) of commodity B produced 34 ti. = time to manufacture one unit (x100) of the j'th commodity J on the i'th process Ti = total available time on the i 'th process pj = the profit derived from the sale of one unit (x100) of the j'th commodity The problem is then to determine the value of x1 and x2 so as to maximize 11x +4): 1 2 subject to the following: 7x +6xzé84 1 4x1+2x2 In order to simplify the notation, since this is a two variable problem, £32 let x1 = x x2 = y then the problem is to maximize 11 x + 4 y ' (2. 1) subject to 7x+6y584 (2.2) 4x+2y£32 (2.3) It can be seen that expression (2. 1) represents the profit or objective function. Expressions (2. 2 and 2. 3) represent the manufacturing time for each of the two processes. The first step is to make equations of the above inequalities. This is accomplished with the addition of slack variables. A slack variable can be of 35 any size (as long as it is positive) and merely causes equality to exist. This is accomplished as follows: 84 (2.4) 32 (2. 5) 7x+6y+W 1 4x+2y+W2 In the real physical problem the slack variables W1 and W2 would represent idle equipment time on process I and II respectively. If no profit or loss were associated with these slack variables then the profit function (2. 1) can be amended to: 11x+4y+0°W1+0'W2=max (2.6) It is possible to consider the burden costs for idle equipment if that is desired. For simplicity here no costs will be associated with idle equipment time. Note that the problem as it now stands involves four variables in two equations. Mathematically this means that an infinite number of solutions exist. The second step is to organize the equations in matrix form to begin the first simplex tableau. Table XIV illustrates the equations in matrix form. Table XIV. Problem Equations in Matrix Form x y W1 W2 84 7 6 1 0 32 4 2 0 1 The simplex method requires an initial solution as did the distribution methods. Here the initial solution is the trivial or worst possible solution. 36 In this case the initial solution would be to produce nothing, having wholly idle time on the equipment, and realize no profit. This is shown in Table XV. Table XV. Initial or Trivial Solutionk x y W1 W2 w1 84 7 6 1 0 W2 32 4 2 0 1 Now it is necessary to evaluate this solution to serve as a guide for further improvement. To accomplish this the Objective (profit) function must be included. The objective function is written in a row above the position of the variables. At this point it would be well to name some of the parts of the matrix for easier reference. This is shown in Table XVI. Table XVI. Initial Solution Objective Function Included 11 4 0 0 Objective row x y W1 wo. Variable row 0 W1 84 7 6 1 0 0 W2 32 4 2 0 1 Bod of the Identity of ma ix the matrix A new row called the index row can now be developed along the bottom of the matrix. The numbers in this row are developed by the formula: Index number = 2 (number in the column X the corresponding number in the objective column) - number in the objective row at the head of the column. 37 This is used to develop index numbers in the constant column and the body and identity of the matrix. The index number in the constant column would be: Index number [84 - 0 + 32 . 0] - 0 (Constant col. ) = 0 The index number for the first column of the body of the matrix is: (7. 0+2- 0)-11 Index number = - 1 1 The completed index row is shown in Table XVII. This illustrates the first simplex tableau with all the various parts named. Table XVII. Initial Simplex Tableau Objective row 11 4 0 0 .a‘ Variable row 1: y W1 W2 -—+ The problem 0 W1 84 7 6 1 0 equations ) 0 W2 32 4 2 0 1 1 ‘- 1. 1 L // V W Index row 0 -11 -4 0 0 5"" Objective column Variable column Body Identity Constant column It will be noted that the index row in this problem is the negative of the objective row. This holds true only when all the slack variables have zeros in the objective column. 38 The initial solution is then: x =0 y =0 W1=84 W2=16 Total Profit = 0 The index numbers point to possible improvement in the solution. In essence $11. 00 profit (represented by the -11) is being lost by not producing any x and $4. 00 profit is being lost by not producing any y. Since x shows the highest profit potential (the largest negative number) it is selected to improve the solution. The column in which x appears may then be called the key column. Obviously to bring x into the solution (have it appear in the variable column) either W1 or W2 must be removed from the solution. The variable that is to be removed from the solution is determined by dividing the numbers in the constant column by the corresponding positive non- zero numbers in the key column. The row with the smallest quotient becomes the key row and the variable in that row is removed from the solution. This can be verified by standard algebraic methods as the change that will permit the largest x that still satisfies the system of relationships. The number at the intersection of the key column and key row is called the key number. This is illustrated in Table XVIII. Table XVIII. Initial Simplex Tableau Key Row and Column Indicated ~11400 0 W1 84 7 6 1 0 ‘ Key row ( 0 W2 32 . 2 o 1 2V 0 -11 4 0 0 icy Number Key Column 39 Now the improved solution can be developed. This entails developing a new tableau or mathematically it is changing the basis of the matrix. The key row is divided by the key number and appears in the same position as the main row of the new tableau. The variable (x) and its objective number (11) of the key column replaces the variable (W2) and its objective number (0) of the key row. The remaining variables in‘the variable column and their objective numbers remain unchanged. Table XIX. Main Row of New Tableau 11 4 0 0 x y w1 W2 Tableau I 0 W1 84 p 6 1 0 Q W2 32 4 2 0 1) Key row Tableau II 11 x 8 1 1/2 0 1/4 Main row For the sake of brevity the variable and objective rows are not rewritten in succeeding tableaus. The remaining numbers of the new tableau in the constant column, body, identity and index row, are determined by the formula: New no. = Old no. - Corres. No. x Corres. No. (i key row of key column Key number 40 The number in row one in the constant column would be determined as follows: New number = 84 - 16 x 7 2 = 84 - 56 = 28 Applying the same formula would develop the second tableau as shown in Table XX. Table XX. Simplex Tableaus I and II Optimum Solution 11 4 0 0 x y W1 W2 Tableaul 0 W1 84 ,7 6 1 0 0 w2 32 4 2 0 1 0 -11 -4 0 0 0 W1 28 0 5/2 1 -7/4 .11 x 8 1 1/2 0 1/4 Tableau II 88 0 .3/2 0 11/4 The solution presented in tableau II is the optimum solution because all the numbers in the index row are either positive or zero. If any negative numbers still existed in the index row the entire process would be repeated, and a further improved solution would be obtained. I 41 The optimum answer to the problem is x =8 y =0 W1=28 W2=0 Maximum Profit = $88. 00 In terms of the initial problem statement the answer is: Product A - produce 800 units Product B - produce 0 units Process I — will have 28 hours unutilized time Process 11 - will be 100% utilized Profit = $88. 00 This optimum answer is easily verified. Any other solution will yield a lower profit. It is of interest to note that an economic significance can be attached to the index row numbers in the final tableau. Any numbers under the body of the matrix (3/2 for y in this case) represents the reduction in the objective function per unit of that variable introduced into the solution. In the case of the above problem the total profit would be reduced by $1. 50 per "y" introduced into the solution. To introduce one "y" would mean removing some "x" (in this case . 5x) hence the reduced profit. This answer would be: x =7.5 y =1 W1=27.5 W2=0 Profit = 7. 5 (11)+1 (4) = $86. 50 which can be easily verified with the initial equations. 42 Any numbers in the index row under the identity (11/4 for W2 in this case) can be considered to represent opportunity profit. This means that an increase of one "W1" in the initial problem (i. e. , relaxing the restriction on the second process by one hour) would permit an increase of 11/4 or $2. 75 in the profit function. This can serve as a guide for equipment expansion or replacement. It is necessary to have some means of checking the work since errors can easily occur. One method of checking involves checking the numbers in the index row. The same method used to establish the index row in the first tableau can be used to check the index row of succeeding tableaus. This check, however, is of limited value since it cannot detect an error in a row where the objective number is zero. A better checking device is to employ a check column. The numbers in the check column are established in the first tableau as equal to the sum of the numbers in the respective row. This includes the numbers in the constant column and everything to the right. In succeeding tableaus the check column is handled as a part of the problem matrix, just like the index row, and will always represent the sum of the numbers in the respective rows. If the check column does not tally then an error has occurred and can easily be found and corrected. The check column, while it does add another column to the matrix array, is by far the easiest and best method for checking the accuracy of the work. Of course as Charnes and Cooper21 mention, the all important check though it may seem trite is in assessing the resulting solution(s) in terms of its meaningfulness and practicability as a course of action to the problem at hand. It is well to note several useful short cuts in developing a new tableau. These are: 1. A "+1" appears at the intersection of a row and column containing the same variable. All other numbers of that column are zero including the number in the index row. \ 21Chames, Cooper, Henderson. Ibid, page 18. 43 2. If there is a zero in the key row of the previous tableau or main row of the new tableau all figures in the column in which the zero appears are unchanged and thus repeated in the new tableau. 3. If there is a zero in the key column, that row containing the zero is unchanged and thus repeated in the new tableau. These short cuts can be easily verified by the previous formula for developing the numbers of the new tableau. This will tend to substantially reduce the hand calculation time. Degeneracy. It is possible to have degeneracy in much the same manner as in distribution problems. However, the resolution of degeneracy is a little more involved in the simplex method. Degeneracy can be recognized when determining the key row. Degeneracy exists when two or more rows yield the same smallest quotient. In this case a choice must be made. If the wrong choice is made the problem may begin to cycle and hence never reach an optimum. The degeneracy is resolved as follows:22 1. Divide each element in the "tied" rows by its number in the key column. 2. Compare the quotients obtained term by term from left to right only in the identity of the matrix array. 3. At the first place where the quotients are unequal the tie is broken. 4. Select that row with the algebraically smaller ratio. This is a perfectly general procedure and will resolve degeneracy very effectively. 22Charnes, Cooper, Henderson. Ibid, pages 20-25. This is the basis for the above discussion and includes a very comprehensive appraisal of degeneracy. 44 Several sources have indicated a rule of thumb method for resolving ' degeneracy much like the north west corner rule used in distribution problems. It says to select the uppermost row if two rows are tied or to select the left column if two columns are tied. This may work; however, it yields exactly the opposite choice in the first tableau of Charnes and Cooper's nut mix problem.23 This author solved the nut mix problem with this opposite choice and obtained the same answer in the same number of steps. However, the validity of the northwest rule to resolve degeneracy in the simplex method is most certainly open to serious question. Types of Relationships. In mathematical programming problems the less-than-or-equal-to (5) relationship is not the only type that will be encountered. It is possible to have some approximately-equal-to ("=’) and greater-than-or-equal-to (é) relationships. Each of these must be handled differently. Consider the relationship: 5x + 3y 5 50 Add a slack variable and it becomes an equation: 5x + By + W = 50 This is in suitable form to be put into the simplex matrix. Consider 5x + 3y "=’ 50 In this situation a slack variable is both added and subtracted to form the equation 5x+3y-W1+W2=50 23Charnes, Cooper, Henderson. Lid, page 10. 45 The slack variables are included in the objective function preceded by a "-1". This will tend to minimize the slack variables and make 5x + 3y—->50 In this case the "W1” would appear in the body of the matrix and the "W2" in the identity. Consider 5x 4- 33:2 50 which would be the same as -5x -3y-..é-50 This seems suitable except that all the numbers in the constant column must be positive in order to yield meaningful solutions. If a slack variable were subtracted fromjthe first expression an equation would result as follows: 5x + 3y - W = 50 This cannot be placed into the simplex matrix as yet. The simplex matrix array requires that the identity be square (i. e. , same number of rows as columns) and further, that it be a positive unit diagonal (i. e. , positive 1's appearing in a diagonal from upper left to lower right). As the expression stands now there is no variable that can be placed in the identity. Here an artificial variable can be employed. 5x+3y- W+U= 50 A factor -M is attached to "U" in the objective function, since equality existed before "U" was added, and since "U" has no economic significance in the real problem. This "-M" factor, defined as so large that it dominates all else in the problem, automatically assures that "U" will have no value in the optimum solution. This means that the variable "U" is in essence a computational gimmick that permits this type of relationship to be included in H H H H the simplex method. The variables x , y , and "W" would appear in the body of the matrix. The variable "U" would appear in the identity. 46 Geometric Interpretation. It is possible to attach a geometric inter- pretation to the mathematical programming problem and the simplex method. In the previous problem the relationships were 7x + 6yé. 84 (2. 4) 4x + 2yé-32 (2.5) These linear relationships can be plotted as shown in the graph (Figure l). 4X+2Y= 32 7X+6Y=84 2 4 6 8 l0 l2 l4 I6 I8 20 . X . FIG.| PROBLEM EQUATIONS GRAPH 47 The line AEC represents possible solutions to the equation, _ 7x + 6y = 84 Thearea AECO represents the area of possible solutions to the inequality, 7x + 6y £84 The line DEB represents possible solutions to the equation, 4x + 2y = 32 The area DEBO represents the area of possible solutions to the inequality, 4x + 2y £32 Point E is the simultaneous solution to the set of equations, 7x + By = 84 4x + 2y = 32 The area CEBO represents the area of possible solutions to the system of inequalities, 7x + Byé 84 4x + 2yé 32 and consequently is the area of possible solutions to the problem. The profit function must be included in order to find that solution which yields the maximum profit. The profit function 1 1x + 4y can be represented by a line with a -E slope. 4 48 PROFIT FUNCTION l IX 4- 4Y 7X+6Y=84 4 6 8 I0 I2 l4 l6 l8 X Fig. 2 Problem Equations Graph Profit Function Included The distance the line moves from the origin, represented by ray P, is equivalent to an increase in the value of the profit function. The maximum profit is obtained when the profit function moves to the farthest extreme point of the possible solutions space (area CEBO in this problem). 49 \a PROFIT FUNCTION ‘ I IX + 4Y= MAX. 2468\l0l2l4l6l8 X Fig. 3. Optimum Solution Figure 3 will verify the previously derived solution. The value of the profit function can be obtained by scaling the ray P and computing the total profit. This graphical method can. quickly provide the answer to similar two variable problems. However the accuracy of this graphical approach depends upon the accuracy of the graph construction. 50 The important point in the geometric interpretation is that it holds true regardless of the number of variables. In essence the linear programming problem in "n" variables can be thought of as forming a convex polyhedral cone in an ”n" dimension space. The functional can be thought of as repre- senting a hyperplane in this "n" dimension space. The simplex method then proceeds to move the functional from an extreme point to an adjacent extreme point until an optimum has been obtained (i. e. , the functional is moved as far from the origin as possible and still intersects the convex polyhedral cone).24 In mathematical programming problems the optimum always lies on a boundary and never within the solutions space. Summary The simplex method can be summarized in ten steps: 1. Develop the equations, including slack and artificial variables as may be required. 2. Form the matrix, and establish the check column. a. The numbers in the constant column (except in the index row) must be positive. b. The identity of the matrix must be square and must be a positive unit diagonal. c. The check column is the algebraic sum of all numbers in the row, including the constant column. 3. Put the coefficients of corresponding variables of the objective equation above the proper columns. 4. Develop index row values. a. Multiply numbers of each column by corresponding numbers in the objective column and total; from this sum subtract the number in the objective row at a top of the column. The value so found is placed in the index row. 24Charnes, Cooper, Henderson. 31:}, part 11, pages 41- 62. 51 . Select key column. a. The most negative index number locates the key column. In case of a tie, select either column. . Select key row. a. Divide the numbers of constant column by the corresponding positive non- zero numbers of the key column. Select that row with the smallest quotient. In case of a tie, see discussion on degeneracy below. . Select key number. a. At intersection of key row and key column. . Develop new tableau. a. Main row of the new tableau is in the same position as the key row of the previous tableau. The main row is developed by dividing the numbers of the key row by the key number. The key column of the previous tableau appears in the new tableau with a "+1" at the junction of the main row, all other numbers in that column are "0". b. The variable and its objective number from the key column replaces the variable and its objective number from the key row and becomes the objective and variable for the main row of the new tableau. c. The remaining variables and their objective numbers associated with other rows and columns remain unchanged and occupy the same position in the new tableau. d. The remaining numbers in the identity, body, constant column, check column, and index row are determined by the following formula: New Number = Old Number - Corresponding No. x Corres. No. of Key Row of Key Col. Key number 52 . Check the accuracy of the new tableau by examination of the check column. (1) If an error appears, use step 4 to check numbers of index row. This will isolate the error by column and row. f. Short cuts. (1) These short cuts can easily be verified by the equation in 8d preceding. A +1 appears at the intersection of the row and column containing the same variable. All other numbers of that column are zero including the number in the index row. (2) If there is a "0" in the key row of the previous tableau or main row of new tableau, all figures in the column in which the "0" appears are unchanged and thus repeated in the new tableau. (3) If there is a "0" in the key column, that row containing the "0" is unchanged and thus repeated in the new tableau. 9. If all the new index row numbers are "0" or positive, the best solution has been reached. If negative numbers occur, a new tableau is formed by repeating steps 5 through 9. 10. The best solution is reached when the index row contains no negative numbers in the body and identity of the matrix. The interpretation is as follows: a. The number in the index row of the constant column gives the value of the objective equation for that solution. . The other numbers of the constant column are the values of the corresponding variables. The numbers in the index row, below the body of the tableau, represent the amount of reduction in the objective equation if one unit of that variable is introduced into the solution with the corresponding changes in the other variables. 53 d. The numbers in the index row, below the identity of the tableau, represent the ”opportunity profit" or the increase which would occur in the objective function if one more unit of that variable were available (i. e. , if the restriction were relaxed by one more unit). e. Equally optimal alternate solutions are evidenced by a zero in the index row under a variable not in the solution. In reality the simplex method is not as difficult as it is time consuming and tedious. Actually the effort in applying mathematical programming must be directed to defining and refining the problem statement, setup of the simplex matrix and finally interpreting the final results and passing them on to manage- ment for action. Applying the simplex method is in essence a means to an end. The simplex method is another addition to the industrial engineer's tool kit -- a very powerful addition. 11. Degeneracy occurs when a tie occurs in selecting the key row (step 6 above). Degeneracy may be resolved as follows: a. Divide each number in the "tied” rows by the number in the key column. b. Compare the quotients obtained, column by column from left to right in the identity of the matrix array. c. At the first column where the quotients are unequal the tie is broken. d. Select as the key row that row with the algebraically smaller quotient. III. A PRODUCTION PLANNING PROBLEM At present the function of production planning in industry is a some- what inexact activity that strives by various means to develop a broad overall producing plan for an organization. This is management's grand strategy planning. In developing such a plan an incomplete picture of the cost relation- ships usually exists and in many cases it is difficult to obtain a factual comparison between two or more production plans. The production planning usually begins with what data is available and works toward a manufacturing plan. This involves consideration of various tangible and intangible factors and their effects upon the manufacturing plan and vice versa. The application of mathematical programming can greatly assist the production planning activity. With mathematical programming the lowest cost producing plan can be determined. 25 This lowest cost plan can then be tempered as necessary by the several intangible factors such as employee relations, community relations and other management policies. The resulting production plan should certainly be the best plan possible. This section will develop, solve and analyze a typical production planning problem. 2'SThe author is indebted to Mr. N. V. Renfield of Executive Services, Cleveland, Ohio who suggested this general approach to the production planning problem. A similar approach may be found in: Harrison, Jr. , Joseph 0. Linear Programming and Operations Research. J. F. McCloskey and F. N. Trefethen (eds) Operations Research for Management. P. 231-33, Johns Hopkins Press, Baltimore, 1954, and Bowman, Edward H. Production Scheduling by the Transportation Method of Linear Programming, Journal of the Operations Research Society of America, V. 4, No. 1, February, 1956. Pages 100-103. 54 55 The Problem An organization, producing a variety of home workshop machines, desires a manufacturing plan to be prepared for a combination disk and belt sanding machine. The sales forecast and all pertinent cost and capacity data are available. The planning is best accomplished by working with man-hour data because this is the most reliable measure of producing capacity. The problem is complicated to some extent because the manufacturing plans are already prepared for all products except this sanding machine. This means that a portion of the total factory capacity is already taken up in producing these other products. Therefore, the available capacity shows a considerable fluctuation during the year. The problem is then to develop the best, not necessarily lowest cost, producing plan to meet the sales forecast for the sanding machine. Data The following data is representative of data required to develop a manufacturing plan: 1. Forecasted sales in units: January 12, 500 July 25, 000 February 7, 500 August 27, 500 March 17, 500 September 32, 500 April 22, 500 October 30, 000 May 17, 500 November 22, 500 June 20, 000 December 15, 000 Total - 250, 000 units 26 6This forecast is by no means to be construed as representative of the actual demand for this type of product. This is merely an illustrative problem. 2. 3. 10. 11. 12. 13. 56 The factory capacity already planned for the other products is as follows: January 46, 000 man-hours July 48, 000 man- hours February 53, 000 August 41, 000 March 38, 000 September 30, 000 April 44, 000 October 48, 000 May 44, 000 November 48, 000 June 42, 000 December 49, 000 The factory normally works two shifts of 40 hours per week, 52 weeks per year. The two shifts are of equal size. . In a normal two shift working day the total plant capacity is 3520 man- hours. . Each, unit of the sanding machine requires 1. 5 man-hours of direct labor. This includes necessary plant efficiency allowances. The average direct labor costs are: First Shift $1. 70 per hour Second Shift $1. 75 per hour The average factory burden is determined as 200% of the direct labor costs. ' Each unit requires $10. 00 in direct materials. Overtime is paid at time and one-half for work in excess of 8. 0 hours in one day and 40. 0 hours in one week. Overtime is paid at double time for Sundays and holidays and for work in excess of 8. 0 hours on a Saturday. Storage facilities are sufficient and cost $0. 20 per square foot per month. Each finished unit occupies 1. 3 square feet of floor space but they can be stacked four units high. Inventory charges are 20 per cent per annum on the inventory investment. Inventory charges are usually figured monthly. Finished stock inventory at the end of the producing year must not exceed 500 units. Production and distribution are such that the total units produced in January are available for sale in January. The lead time from manufacturing to the consumer is zero. 57 This is the type of data that should be available to the production planners. The initial step of the problem is then to organize the data in some form that is adaptable to analysis. This is accomplished for the straight time producing capacity for the calendar year 1957 as illustrated in Figure 4, pagefliin the Appendix, and summarized in Table XXII, page fl in the Appendix. Table XXII indicates a shortage in straight time producing capacity of 10, 296 units or 15, 444 man-hours. Since sufficient straight time producing capacity does not exist it will be necessary to consider overtime production capacities. Management must specify the desired maximum overtime con- sistent with their policies. For this problem maximum time and one-half overtime is considered as eight hours per Saturday and two hours per week day. Maximum double time overtime includes eight hours per Sunday. This is accomplished as shown in Figure 5, page _8_5_ in the Appendix, and summa- rized in Table XXIII, pageiLin the Appendix. The cost information is then calculated in terms of cost per unit for direct material, direct labor, factory burden, storage (floor space), and inventory costs as shown in Figures 6 and 7, pages_8_6_ and ii in the Appendix. The storage and inventory costs are summarized in Table XXIV, page_9_z_ in the Appendix. Inventory and storage costs are calculated monthly and added to the inventory investment. This, in effect, causes a cumulative or compound inventory charge. Formulation Prior to considering the specific problem at hand the general statement of the production planning problem will be developed and discussed. If we let: Pi = number of units of producing capacity in the i'th month Qj = number of units of forecasted sales for the j'th month x. = number of units produced in the i'th month and sold in 13 the j'th month 1. cost per unit to produce in the i'th month and inventory J for sales demand in the j'th month 9’ ll 58 i (1, 2, 3,---12) j (1: 2: 3.1---12) then the production planning problem can be formulated in two sets of relation- ships. The first set (restrictions) says that what is produced in the i'th month and sold in that month and succeeding months is less-than-or equal to the production capacity for the i'th month. Mathematically this is: 12 Z xi.-EPi j=i J (3.1) The second set of relationships (equations) considers the sales demand. What is sold in the j'th month must naturally be produced in that month or preceding months (since back orders are excluded from consideration). Mathematically this can be stated as follows: 3 Z xii ‘ Q1 i=1 (3. 2) The objective function is to minimize the producing and storage costs and can be stated thus: 12 Z (a.. x. .) = minimum 1.] 11 pa II II 1 1 (3. 3) La The total producing capacity is then: .12 Z 13i = Ptotal i=1 (3. 3) and the total sales forecast is then: 12 Z Qj : Qtotal j=1 (3. 4) where: Ptotai E Qtotai 59 The total producing capacity (Ptotal) is always greater than the sales demand (Qtota1)' This may always be obtained by considering overtime producing capacity and/ or subcontracting. The latter can conceivably present an unlimited potential capacity. The summation limits of (3. 1) and (3. 2) factor out the possibility of back orders, i. e. , February's production cannot be used to fulfill the January sales demand. Back orders may be considered if management can provide factual cost information. However, this general statement of the problem will not allow back orders. Since the problem at hand must include overtime production of at least 10, 296 units (see Table XXII, page 99 in Appendix) this should be factored into the statement of the problem. For the sake of simplicity, subcontracting will not be considered at this time. In order to include this overtime consideration in the problem formulation the symbols must be expanded as follows: i' = number of units produced at straight time in the i'th month J and sold in the j'th month xi. = number of units produced at time and one-half overtime J in the i'th month and sold in the j'th month xi'. = number of units produced at double time in the i'th J month and sold in the j'th month i' = cost per unit to produce at straight time in the i'th 3 month and inventory for sales demand in the j'th month ai. = cost per unit to produce at time and one-half overtime in J the i'th month and inventory for sales demand in the j'th month a". = cost per unit to produce at double time in the i'th 1‘] month and inventory for sales demand in the j'th month "U II number of units of producing capacity in the i'th month = number of units of forecasted sales for the j'th month (1, 2, 3, --- 12) Ll. I) i =(1,2,3,---12) 60 The new form of the first set of restrictions involving producing capacities can now be expanded to include the overtime consideration as follows: 12 .. + .'. + 3'. . Z (x1J le le ) 5 P1 j:i (3. 5) The second set of relationships (equations) expressing the sales demand can also be expanded thus: 3' l " _ Z(Xi' + xij+ xij ) - Q. J J i=1 (3. 6) and the expanded form of the objective function is now: ' g H II = - - Z (aij xi]. + aij xij + ij xij ) minimum (3. 7) This objective function (3. 7) can be simplified by deducting direct material, straight time (direct) labor and factory burden costs, since these are common to all units produced. The problem objective is then simplified to minimize the labor overtime premium, storage and inventory costs which are the basic variables in this problem. The general production planning problem is thus represented by a mathematical model containing 12 linear equations and 12 linear inequalities involving 234 variables. At this point the problem would seem insurmountable since the simplex setup would result in a 24 by 258 matrix array (24 equations or rows plus 234 variables or columns plus a 24 x 24 identity). The production planning problem lends itself to solution with the distribution methods. The factory capacities month by month can be con- sidered as sources of supply while the sales forecast can be considered as demand. With this analogy it is possible to visualize a distribution matrix 61 with monthly factory capacities for the rows and the monthly sales forecast as the columns or vice versa. The distribution matrix form for this production planning problem appears as Table XXV, page 94 in Appendix. The production planning problem is now represented in a 13 by 36 distribution matrix array. This organization certainly makes the problem appear more easily solvable and yet every relationship of the general statement of the problem (3. 5, 3. 6, 3. 7) remains intact in the problem. The producing capacity (3. 5) is represented as the columns and the sales demand (3. 6) is represented as the rows. The simplified form of the cost factors (ai., aij , an. representing overtime premium, storage and inventory costs) appears as the cost factors in the respective i'th columns and j'th rows. The quantities ' II xij' xij: xij are to be determined subject to the rim conditions. Note that the rim conditions have been balanced with the dummy row (row 13) which represents fictious demand for the product. In the real physical situation this represents unutilized producing capacity. Note also that the cost factors for about half of the matrix are -M. Since back orders are not considered practical in this problem the -M cost (defined as so large that it dominates all else in the problem) accomplishes this restriction. If management allowed back orders then a suitable cost factor could be used. However, such a cost would be difficult if not impossible to obtain. Optimum Solution The production planning problem can now be solved by any of the distribution methods. Vogel's Approximation Method (VAM) and subsequent improvement with the Modified Distribution Method yielded the answer in several steps?7 by hand. The problem can also be solved with any of the 27This problem required the VAM plus six steps with the MODI method for solution. This required 10 hours. However, it is felt by the author that the solution could be accomplished in fewer steps and a shorter time period. This was verified by resolving the problem requiring the VAM + two steps with the MODI method. This was accomplished in approximately 3 hours. 62 digital computors. However, the cost of machine computation over hand computation for a problem of this size might be difficult to justify. The final optimum solution matrix is shown in Table XXVI, page 95 in the Appendix and is also summarized in Figures 8 and 9, pages 88 and 89 in the Appendix. This solution certainly appears to be a practicable one. Analysis of the Optimum Solution It is now possible to analyze the optimum (minimum cost) solution in light of the various intangible considerations and management policies. Two points about the problem should be borne in mind. First, this problem assumes a zero lead time from manufacturing to consumer sales. While this is seldom if ever the real case a suitable lead time can easily be included in the problem formulation. Second, the inventory charges are cumulative and calculated monthly for a full month's storage in inventory. In an actual situation this may vary somewhat and could conceivably reduce the inventory charges. It can be seen from the final optimum solution (pagefl in the Appendix). that a FIFO (first-in-first-out) inventory system is in effect. This is partly due to the compound inventory charges that were used. In general a FIFO inventory system will be more economical than a LIFO (last-in-first-out) system when inventory charges are compounded. Summary Now for probably the first time management has a truly complete analysis of a production plan. Alternatives brought about by any intangible factors can easily be analyzed in light of the effect upon costs. However, it is necessary here to present a word or two of caution. This type of solution does not and cannot include costs associated with labor fluctuations and turnover and other such non-linear items (costs that do not vary directly with the production quantities). Nor can it include costs associated with less than full budgeted utilization of equipment and facilities. Then too, the production plan is only as good as the sales forecast. This means that no matter how well a production plan is developed it is poor if based upon an ill conceived sales forecast. 63 In a real situation the greatest difficulty is not in obtaining the numerical solution but in obtaining meaningful costs, capacities, and requirements. If desired, alternative production plans can be based upon some established upper and lower limits of the sales forecast. Comparison of these alternative plans for the upper limit, the mean, and the lower limit of the sales forecast will provide management with a guide as to the flexibility of the production plan with a variable sales forecast. This additional information can be very useful in such situations. The problem can be expanded to include planning for the desired inventories period by period. Here the problem matrix takes on more rows as the various inventories are included. In many situations this would be the more desired formulation of the problem. The production planning may be accomplished on a continuous basis, either monthly or quarterly, for the next twelve-month period. This type of continuous planning means that a twelve-month plan is always available. While this requires more work it means that more and better information is available to management. A once-per-year planning cannot include changes in sales demand from the original forecast. Continuous planning can successfully accomplish such changes. Less risk of sub-optimization (optimizing one year's plan at a sacrifice in the next year's plan) would result in continuous planning. The 13 x 36 distribution matrix array of the production planning problem can be used as a standard form by most manufacturers. The problem setup can be reduced to a routine and the solution can be accomplished either with a computor or properly trained clerks. The production planning problem may be expanded to include several products. It is necessary, in considering such a problem, to express the production and sales in some common unit such as man- hours or equivalent 64 units or in terms of one hour's production as suggested by Mr. Bowman. 28 While this would increase the size (number of columns) of the distribution matrix it still remains a solvable problem. This application illustrates how time periods can be successfully incorporated within the framework of a linear programming problem. A useful extension of this can result in better analysis of product distribution to various warehousing locations. In situations where factory output and/or customer demand fluctuate through several periods a better product distribution can result when considering several periods rather than just one at a time. 281313, pg. 101-2, IV. A MANUFACTURING PROBLEM In most manufacturing situations a number of courses of action are possible. Usually the multi-facet nature of the problem defies solution by inspection or intuition. Such a manufacturing problem will be considered here. The Problem A manufacturer receives orders for two products (A and B). The customers require 200 units of product A and 300 units of product B. Both products are manufactured in two operations. The first operation is performed in Process I and it requires two hours and four hours per unit to produce products A and B respectively. The second operation can be performed in either Process 11 or III. It requires four hours per unit of product A and seven hours per unit of product B produced in Process II. It requires ten hours per unit of product A and twelve hours per unit of product B manufactured in Process HI. There are 1700 hours on Process 1, 1000 hours on Process H and 3000 hours on Process III available in the schedule period. An additional 500 hours is available on Process II in overtime. The labor and burden costs are $3. 00, $3. 00 and $2. 00 per hour on Processes I, II andI’II respectively. The overtime on Process II increases the costs to $4. 50 per hour. If no penalty is assumed for idle machine time then the problem is to determine how to manufacture the products so the overall costs are a minimum. Problem Formulation If we let x1 = number of units of product A manufactured in Process I and at straight time in Process II number of units of product A manufactured in Process I and x 2 at overtime in Process II M II number of units of product A manufactured in Process I and Process III 65 x4 = number of units of product B manufactured in Process I and at straight time in Process 11. x5 = number of units of product B manufactured in Process I and at overtime in Process II x = number of units of product B manufactured in Process I and Process III the formulation is then (Process 1) 2x1 + 2x2 + 2x3 + 4x4 + 4x5 + 4x6 ‘5 1700 (4. 1) (Process II Straight Time) 4x1 + 7x 4 £ 1000 (4. 2) (Process II Overtime) 4x2 + 7x5 ‘5 500 (4. 3) (Process 111) 103.23 + 12x6 €3000 (4. 4) (Product A) x1 + x2 + x3 = 200 (4. 5) (Product B) x4 + x5 + x6 = 300 (4. 6) Multiplying the time by the cost per hour will yield the following objective (cost) relationship: -36x = Minimum (4. 7) -43. 5x 6 —24x -26x -33x “18" 2 3 4 1 5 The problem is thus stated in four inequalities (4. 1_- 4. 4) and two equations (4. 5 and 4. 6) and the objective (cost) function (4. 7) is to be minimized. The four inequalities represent process time on the three 66 processes. The two equations (4. 6 and 4. 7) insure that the required amount of each product is made. The objective function represents the cost (in dollars) to produce the two products by the various processes. 67 The relationships must be prepared for solution by the simplex method. This is accomplished by adding slack (w) and artificial (U) variables as follows: ‘ 2x1 +2x2 +2x3 +4x4+4x5+ 4x6+W1 = 1700 (4.8) 4x1 + 7x4 + W2 = 1000 (4. 9) 4x2 + 7x5 + W3 = 500 (4. 10) 10x3 +12x6 + W4 = 3000 (4. 11) x1 + x2 + x3 +U1 = 200 (4.12) x4 + x5 + x6+U2 = 300 (4.13) The objective function now becomes: -18x1 ~24x2 -26x3 --33x4 -43. 5x5 -36x6 + 0. W1 + 0.W2 + 0. W3 + 0.W4 - -MU1 -MU2 = Minimum (4. 14) The slack variables (W1 - W4) were added to make equations of the inequalities. These can be thought of as representing idle process time. The slack variables have zero weight in the objective function because no penalty is assumed for idle process time. The artificial variables (U1 and U2) are included to form a square identity or basis for the simplex method. The -M cost factor (defined as so large that it dominates all else in the problem) is attached to the artificial variables to assure that they will be zero, since equality exists without them. The problem is now ready for the simplex method. The initial simplex tableau is shown in Table XXI. 68 ".8: o o o o o o 8.65.: 8+ 8+ 3+ 2+ .225. 2- 2- z- 2- 2- 2- com. 3..” H H H H can an .2. Ham H H H H 8m H: 2.. 88 H «H oH 88 H.3 o «Hm H H. H. 25 «.3 o «SH H H. H. 83 a; o mHS H H. H. H. a a a 8: H3 o «D HD 35 m3 m3 3 wx mx wx mx ax an 3.8.6 Hz- 2- o o a o 8- as? mm- mm. 3. 2. 5532 $3.5m HmHHEH don 638. 69 All the relationships are included. The initial or trivial solution, the index row, and check column are shown. Solution This problem was solved in five iterations, the details of which are shown in Table XXVII ( page 96 in the Appendix, fold out for reference). The optimum solution, in this case lowest cost solution in terms of the formulation, is as follows: x1=200 W =100 1 X2: 0 W2: 0 x3= 0 w3=350 X4=_2_0_Q W4: 0 7 x5=_1_§_9_ U1 = 0 7 x6=250 U2 = 0 Minimum Cost = $14, 475. 00 These answers can be seen in Tableau V, Table XXVII and can be easily verified by substitution in the original equations (4. 8 through 4. 14). ProcessI 2x +2x +2x +4x +4x +4x +W =1700 (4.8) 1 2 3 4 5 6 1 2(200) + 2(0) + 2(0) + 4(200) + 4(150) + 100 = 1700 7 7 1700 = 1700 Process II 4x1 + 7x4 + W2 = 1000 (4. 9) Straight Time 4(200) + 7(200) + 0 = 1000 7 1000 = 1000 70 Process II 4x2 + 7x5 + W:3 = 500 (4. 10) Overtime 4(0) + 7(150) + 350 = 500 7 500 = 500 Process III 10x3 + 12x6 + W4 = 3000 (4. 11) 10(0) + 12(250) + 0 = 3000 3000 =3000 x1 + x2 + x3 = 200 (4. 12) 200 + 0 + 0 = 200 200 = 200 x4+x5+x6 = 300 (4.13) 2_0(_) + 1_5_0 + 250 = 300 7 7 300 = 300 (4. 14) ~18x1 -24x2 -26x3 -33x4 --43. 5x5 -36x6 -MU1 -MU2 = Minimum .-18(200) -24(0) -26(0) -33(200) -43. 5(15_O) 7 7 -36(250) -M° O -M° 0 Minimum 14475 = Minimum Analysis of the index row will provide some useful information about alternate solutions (refer to Tableau V, Table XXVII, page _96in the Appendix). The index number for the second column is zero. This indicates that "x2 This could be introduced into the solution without increasing the total cost. would provide an equally optimum alternate solution. solution is shown in Table XXVIII, page 97 in the Appendix. The equally optimum It is obtained by introducing "x2" in place of "x5" from Tableau V, Table XXVII. H 71 The alternate solution is: x1= 162.5 W1= 100 x2 = 37.5 W2 = 0 x3 = 0 W = 350 3 x4 = 50 w4 = 0 x5 = 0 U1 = 0 x6 = 250 U2 = 0 Minimum Cost = $14, 475. 00 This can be easily verified by the initial problem equations. The index row also provides useful information about less-than-optimum alternate solutions. The cost function would be increased by $8. 25 per unit of "x3" introduced into the solution. Opportunity profit is shown by the index numbers under the identity of the matrix. These numbers can be interpreted as. follows: The cost function would be reduced by $1. 50 per each additional hour (W2) on Process II at straight time. The cost function would be reduced by $0. 625 per additional hour (W4) on Process III. In other words, cost would be reduced if the restraints were relaxed (available time increased). Summary The problem discussed here is a typical example of many manufacturing problems. The simplex method was employed here for illustrative purposes. In an actual plant situation a suitable approximation method would probably be used. This would not necessarily result in the very lowest cost solution but it would tend to reduce the combined computation and production cost. As with any computational method the economics of the problem and the method must be considered. If such a problem were encountered once per quarter the simplex method would seem justified. If once per week a suitable 72 approximation method can be employed. If the problem comes up several times per day then either an approximation method or a high speed computor can be used to obtain the necessary answers. In many cases the solution is not as significant as the side results obtained in the index row. These side results, for probably the first time, provide management with factual comparisons between processes and products. Then too, the requirement of an exacting statement of the problem often uncovers other problems which heretofore were unsolved. In many cases merely the attempt to apply mathematical programming will bring many otherwise hidden problems to light. V. SUMMARY The material presented in this thesis is designed for the engineer. Liberal references through the text and in the bibliography will provide adequate material for the student interested in research and development in this field. While a wealth of material has been published to date, a really adequate primer in mathematical programming as yet does not exist, although several are in preparation. The mathematical programming type problems can best be summarized in terms of what must exist in the problem to apply the mathematical pro- gramming methods. There must be: 1. A number of choices or ways of taking action. 2. An efficiency (or cost) differential between the possible choices. 3. A set of restrictions or upper limits, i. e. , that which cannot be exceeded. 4. A set of requirements or lower limits, i. e. , that which must be accomplished (often implicit in the problem statement). 5. An objective or policy statement, i. e. , the goal to aim at; maximum profit, minimum costs, etc. 6. An interrelationship of the variables in significant expressions. 7. A common unit of measure. The preceding are necessary though not necessarily sufficient prereq- uisites for the mathematical programming problem. Some of the industrial applications of mathematical programming are: 1. Production allocation and scheduling. 2. Distribution and shipping. 74 3. Market research -- locating outlets, warehouses, etc. 4. Salary and job evaluation. 5. Blending -- oils, gasolines, alloys, etc. 6. Product mix problems. 7. Materials handling (non-automated). 8. Production planning. The mathematical programming approach to solving the above problems is much superior to many of the present intuitive methods employed today. It is interesting however to discover that often the intuitive solution by an experienced person will be very close to the optimum solution obtained by mathematical programming. This however does not discount the value of the mathematical formulation and solution, since any individual with only nominal experience can always obtain the very best answer with mathematical programming whereas years of experience are usually required to develop any valid intuitive method. Mathematical programming was limited initially to static analysis. As developments progressed the production planning problem was presented as the first example of dynamic analysis (incorporating more than one period of time) with mathematical programming. The planning problem presented in this thesis is the first such problem shown in its entirety. It is possible now to solve certain dynamic problems with mathematical programming. In fact, a problem such as production planning can be made more dynamic by analysis and solution periodically, perhaps monthly or quarterly. This approach can accommodate changes or variations in product demand and available capacity (inputs to the problem) as time progresses. While this presents more work it provides management with more and better answers to an ever changing problem. Much the same type of dynamic analysis can be applied to problems of product distribution. This applies particularly well when the demand varies 75 from period to period. In fact, the danger of sub-optimization (optimizing one problem or a part of a problem at a disproportionate sacrifice in another problem or another part of the same problem) can only be minimized by dynamic analysis in problems of this type. Usually the most difficult task in mathematical programming is obtaining the necessary factual information. Often the digging for the required infor- mation will uncover previously hidden problems which when exposed can be easily solved. It is not inconceivable that the gains derived in solving these previously hidden problems may far outweigh the gains from mathematical programming. In fact, the problem to be solved may be reduced to where the solution is obvious thereby making mathematical programming unnecessary for solution. This however does not discount the value of mathematical pro- gramming since it involves more of a philosophy of problem approach rather than merely the solution methods discussed in the thesis. In the final analysis anything that forces a critical look at what is being done is of value to an organization. Mathematical programming is not a panacea for. solving all industrial problems in that it has some very serious limitations. The biggest limitation is that the relationships of the variables must be linear. Some work has been done to circumvent this restriction 29however only limited progress has been made to date. Non-linear elements such as setup times in a manufacturing problem cannot be included in a mathematical programming model. To date (a problem like this may be handled by arbitrarily setting aside a portion of the available equipment time for setup and solving the problem using run time only. The setup time required by the solution is then checked against the time allotted previously for setup. Any discrepancies are corrected by reallocating setup time and resolving the problem. This technique, while it yields a usable Y_’ 29 See Saline, L. E. Quadratic Programming of lnterdependent Activities for Optimum Performance, A. S. M. E. Paper No. 54-A-58, November, 1954. 21‘ pp. 76 answer, is very questionable from the standpoint - is the answer truly optimum. The danger of sub-optimization exists in this type of problem approach. However until non-linear elements can be treated more scientifically this is about the only approach that can be made to such problems. Mathematical programming requires the variables to be related in meaningful expressions. This is often difficult though not impossible to obtain. However, much difficulty will usually be encountered in establishing the objective function. This is usually difficult for management to pin point. The objective may be maximum equipment utilization, minimum cost, maximum profit, maximum number of pieces, etc. Each of these objectives may yield a different solution to the same model. The problem used toillustrate the simplex method (page 33) is just such a model where different solutions may be obtained for maximum profit, maximum equipment utilization and maximum number of pieces produced. If management cannot clearly envision and state the objective then mathematical programming is stopped before it has even begun. It is well to point out here that digital computors may be used for solving mathematical programming problems. The IBM type 701 computor can solve distribution problems up tomx n = 3000, and simplex problems up to 50 x 100 in size. The newer IBM 704 and 705 will handle even larger problems, primarily due to larger memory capacity. In general computors will be employed either when the problem is very large and an appropriate approximation is not available or of suitable accuracy, or where the problem must be solved on a repetitive basis and the answer is required rather quickly to be of use. In some cases a computor may be used as a periodic check when an approximation method is regularly used. This thesis contains recommended improvements primarily in the terminology of mathematical programming. The presentation here has been 77 in non-mathematical terms. Throughout the thesis the mathematics is minimized though not completely ignored. The thesis presents the methods for the first time reduced to an easy to understand step by step procedure. This will permit more emphasis to be properly placed on problem formulation and the interpretation of the answers rather than on the methods employed. Actually the methods of mathematical programming are little more than a means of cranking out an answer. The effort then must be channeled to the remaining work in defining and solving a problem. The thesis was limited to discussing industrial applications of mathe- matical programming. However, many problems other than industrial can be solved provided they have the above mentioned prerequisites. VI. CONC LUSIONS Mathematical programming is presented here in an easy to understand, step by step method. This thesis records for the first time in one writing all the methods of mathematical programming in simplified terminology. Mathematical programming applied to production planning as discussed in this thesis offers a new approach of scientific analysis to problems of this type. The production planning problem exemplifies mathematical program- ming as a tool for dynamic analysis of distribution type problems. Heretofore the general production planning problem has been presented as an example of dynamic analysis. This thesis presents a typical problem fully developed in order to completely illustrate the phases of work required for such an analysis. This analysis can be even more dynamic if solved for example every month for the succeeding twelve month period. This would accommodate variations in capacity, forecast, and sales and would provide better answers for manage- ment. This problem also presents mathematical programming in its proper perspective: As a tool of analysis that in many situations yields an initial solution that may have to be modified in light of other intangible and/ or non- linear considerations. However, this does not discount the value of mathe- matical programming since, in addition to the optimum solution, much very useful information regarding alternate choices of action is revealed. In the case of production planning, mathematical programming is used to minimize the tangible cost factors such as labor premium, inventory and storage costs. However, intangible costs associated with labor turnover and low equipment utilization cannot be included within the framework of mathematical program- ming analysis. Mathematical programming applied to the manufacturing problem pre— sents a scientific approach to optimizing work allocation. While the problem discussed here considered unlimited sales potential (usually an impractical assumption) and no loss or penalty associated with idle equipment time, these factors can be modified by a forecasted sales potential and idle equipment charges (unabsorbed burden) and included in the analysis. The real signifi- cance of this problem lies in the fact that for the first time costs are obtained 78 79 that reflect the interaction of the various jobs competing for the available machines. At the same time profit opportunities are presented that reflect the interrelationship of the equipment efficiencies in light of the products manufactured. Research is continually being conducted in this field but this thesis points toward several possible research studies. Pure and applied research is re- quired to expand the applications of mathematical programming and to develop means of better coping with the problem of non-linear elements. Develop- ments in both these directions should improve and expand the usefulness of mathematical programming in industry. Research could be undertaken to determine a mathematical basis for Vogel's approximation method. This method was intuitively developed but it seems that some logical mathematical basis exists. Once this is obtained it may be possible to apply it toward obtaining a better initial solution in the simplex method. This type of research can greatly expand the use of mathe- matical programming and has the potential to materially reduce computation time and cost. This thesis can be considered as a primer in mathematical programming and can serve as initial training for an individual interested in this field. The references in the. text and bibliography are provided for those interested in further development in both mathematical programming and operations research. APPENDIX BIBLIOGRAPHY Arnoff, E. L. The Application of Linear Programming to Production Engineering and Scheduling. American Society of Mechanical Engineers, New York, Paper No. 54-A-223, December, 1954. 7 pp. Barankin, E. W. The Schedulig Problem a_s _an Algebraig Generalization p_f Ordinagy Linear Programming. Industrial Logistics Research Project, University of California, Los Angeles, Discussion Paper No. 19. 16 pp. Bowman, Edward H. Production Scheduling by the Transportation Method of Linear Programming. Journal 31' t_h_e_ Operations Research Society 91: America. 4:1 pp. 100-103, 1956. Brisley, M. D. J. Assessing Engineering Problems by Operational Research Methods. Engineer. 199: 803-805, 1955. Charnes, A. , W. W. Cooper and A. Henderson. Ag Introduction t_o Linear Progamming. New York: John Wiley 8: Sons, Inc. , 1953. Chatto, K. A. An Application of Operations Research Methods to the Selection of a Processing Plan in a Meat Packing Plant. Unpublished M. S. I. E. Thesis, Purdue University, June, 1955. Cooper, W. W. and A. Charnes. Transportation Scheduling by Linear Programming. Proceedings _o_f the Conference g Operations Research In Marketing at Case Institute o_f Technology, January, 1953. Dantzig. G. B. Application of the Simplex Method to a Transportation Problem. Koopmans, T. C. , Editor. Activity Analysis g_f Production and Allocation, New York: John Wiley and Sons, Inc. , 1951. Dorfman, Robert. Application of Linear Programming t_o t_h_e Theory o_f 3133 Firm. Berkeley, California: University of California Press, 1951. Eisemann, Kurt. Linear Programming. Quarterly of Applied Mathematics. 13:3 October, 1955. Ferguson, Robert 0. Linear Programming. American Machinist, Special Report 389, 1955. ‘ Goland, M. and E. Koenigsberg. Operations Research Scientific Approach to Management. Chemical Weekly. May 21, 1955. Harrison, Jr. , Joseph 0. Linear Programming and Operations Research. Operations Research for Management. Baltimore: John Hopkins Press, 1954. Harvard University Graduate School of Business Administration. Operations Research Challenge t_o Modern Management, August, 1954. Henderson, A. and R. Schlaifer. Mathematical Programming: Better Information for Better Decision Making. Harvard Business Review, May-June, 1954. Herrmann, C. C., and J. F. Magee. Operations Research for Management. Harvard Business Review, July-August, 1953, pp. 100-112. Hitchcock, Frank L. The Distribution of a Product from Several Sources to Numerous Localities. Journal o_f Mathematics and Physics. 20: 224- 230, 1941. Hoffman, A. J. Linear Programming.» Applied Mechanics Review. 9:5 (May 1956), pp. 185-187. Houthakker, H. C. On the Numerical Solution of the Transportation Problem. Journal of the Operations Research Society _o__f America. 4:1 (February T—_):_956_ pp. 100- 103. Koopmans, T. C. Activity Analys_i_s of Production and Allocation, New York. John Wiley and Sons, Inc., 1951. pp. 404. Kruse, B. Using Computors to Match Production and Seasonal Trends. American Business. 25: 12-13, October, 1955. Magee, J. F. Application of Operations Research to Marketing and Related Management Problems. Jou_r__nal _o__f Marketing. 18. 361- 369, April, 1954. Discussion byR. L. Ackoff. 20: 47- 48, July, 1955. Manne, Alan S. Scheduling_ of Petroleum Refinery Operations, Cambridge, Massachusetts: Harvard University Press, 1956. 181 pp. McAllister, G. Eric. Statistical Decision Theory. Industrial Logistics Research Project, University of California, Los Angeles, Technical Report No. 10. 1953. McCloskey, J. F. et al. _perations Research f_o_r Management. Baltimore: John Hopkins Press, 1954. (Vol. II, 1956f Saline, L. E. Quadratic Programming of Interdependent Activities for Optimum Performance. American Society of Mechanical Engineers, New York, Paper No. 54-A-58, November, 1954. 21 pp. Salveson, M. E. A Mathematical Theory of Production Planning and Scheduling. Journal 3f Industrial Engineering. 4:1 (February 1953), pp. 3-6. Salveson, M. E. and R. C. Canning. Electronic Production Control. Industrial Logistics Research Project, University of California, Los Angeles, Research Report No. 17. On a Quantitative Method in Production Planning and Scheduling. Econometrica. 20:4 (October 1952), pp. 554-590. ___The Assembly- Line Balancing Problem. American Society of Mechanical Engineers, New York, Transactions 77:6 (August 1955), pp. 939-948. Schultz, A. Operations Research Related to Production Engineering. American Society of Mechanical Engineers, New York, Paper No. 54-A-221, December, 1954. Scott, Lloyd N. Naval Consulting Board _o_f_ the United States. Government Printing Office, Washington, 1920. Slade, J. J. Some Observations on Formal Models for Programming. American Society of Mechanical Engineers, New York, Paper No. 54-A—241, December, 1954. Symonds, G. H. Linear Pro rammin : The Solution 21; Refinery Problems. New York: Esso Standard rOil Company, 1955, '74 pp. ' Wald, Abraham. Statistical Decisions Functions. New York: John Wiley and Sons, Inc., 1950. 179 pp. Whitmore, William F. Edison and Operations Research. Journal o_f th_e Operations Research Society 9_f America. 1:2 (February 1953 ), pp. 83-85. Month January, 1957 Regular Working Days 22 Total Plant Capacity 77, 440 Man-hours 3520 Man-hours/day x 22 days Capacity not available 46, 000 Man-hours Capacity available 31, 440 Man- hours 31, 440 Man-hours = 20, 960 Units 1. 5 Man- hours/ Unit Required Capacity (Sales Forecast) 12, 500 Units 18, 750 Man-hours Difference between available and required capacity + 12, 690 Man-hours + 8, 460 Units (Surplus over required capacity) Number of employes 31, 440 Man-hours 1 = 179 employes 22(8) Hours/man Figure .4. Straight Time Production Data Sample Calculations 84 Month January, 1 95 7 Reglar Work DaLs 22 Overtime Work Days Saturdays - 4 Sundays - 4 Number of employes 179 Units at time and one-half overtime 22 days at 2 hours/day = 44 hours 4 Saturdays at 8 hours/day = 32 hours Total 76 hours 179 men at 76 hours = 13, 604 Man-hours 13, 604 man-hours = 9, 069 Units 1. 5 man- hours/ unit Units at double time overtime 4 Sundays at 8 hours/day '= 32 hours 179 men at 32 hours = 5, 728 man—hours 5, 728 man-hours = 3’ 819 units 1. 5 man- hours/ unit Figure 5. Overtime Production Data Sample Calculations 85 *Note: 86 Stratght Time Production Costs Direct Material $10. 00 Direct Labor 2. 588 1. 5 man- hours/unit x $1. 725/man- hour Manufacturing burden 5. 176 (200% direct labor) Total unit cost $17. 764 Time and one-half overtime Production Costs Direct Material $10. 00 Direct labor (including overtime) 3. 882 1. 5 man-hourslunit x 1. 5 ($1. 725/man-hour) Manufacturing burden* 5. 176 Total unit cost $19. 058 Double time overtime Production Costs Direct material $10. 00 Direct labor . 5. 176 1. 5 man-hours/unit x 2 ($1. 725) Manufacturing burden* 5. 176 Total unit cost $20. 352 Figure 6. Unit Cost Calculations Manufacturing burden rate would actually be lower at other than straight time. For simplicity the same number of dollars of burden is used. This reflects the lower rate. Unit Cost $17. 764 One Month's Storage Inventory Charges .20/year( 1 year ) $17.764 mont 8 Floor space Costs 1. 3 square foot ($. 20/ sq. ft. /month) 4 (units .296 . 065 Total unit cost (including one month store) $18. 125 Total inventory and floorspace charges . 361 Figure 7. Storage and Inventory - Charges Sample Calculations Note: Inventory charges for the second month are based upon the unit cost of $18. 125. Subsequent inventory charges are based upon the unit cost including applicable storage charges. 87 January Produce 20, 960 units Sell 12, 500 in January Sell 7, 500 in February Sell 960 in March February Produce 11, 600 units Sell 11, 600 in March March Produce 23, 946 units Sell 4, 940 in March Sell 19, 006 in April April Produce 19, 946 units Sell 3, 494 in April Sell 16, 452 in May May Produce 22, 293 units Sell 1, 048 in May Sell 20, 000 in June Sell 1, 245 in July June Produce 18, 933 units Sell 18, 933 in July July Produce 19,627 units Sell 4, 822 in July Sell 14, 805 in August August Produce 24, 293 units Sell 12, 695 in August Sell 11, 598 in September September Produce 26, 933 units Sell 20, 902 in September Sell 6, 031 in October October Produce 21, 973 units Sell 21, 872 in October Sell 101 in November *Produce 2, 097 Sell 2, 097 in October November Produce 14, 933 units Sell 14, 933 in November *Produce 7, 466 Sell 7, 466 in November December Produce 14, 267 units Sell 14, 267 in December *Produce 733 Sell 733 in December Figure 8. Final Optimum Solution *At overtime. 89 PRODUCTION PLAN COST SUMMARY Manufacturing Costs Direct material costs $2, 500, 000. 00 250, 000 units @ $10. 00 Direct labor costs 250, 000 units @ 1. 5 man-hours/unit 646, 875. 00 @ $1. 725/hour Manufacturing burden @ 200% direct labor 1, 293, 750. 00 Total manufacturing costs Additional Costs Overtime premiums $ 13, 323. 02 Inventory charges 38, 632. 29 Floor space charges 8, 478. 34 Total additional costs Total costs and charges Average unit cost = $18. 005 $4,440,625.00 $ 60, 433. 65 $4,501,058.65 Figure 9. Final Solution Cost Summary 90 25 .3. 5m .2- 25 .55 _52. .53 :33. 25.3- «NH 52. - H5H.H .. 25 .2 25 .mm 25.3 25.3 25 .2. 25.2. 5 H. cm .8580qu 25.5 - 5H 25.2. - 25.2- 25 .mm 55.2.. 55.3 25 .mm 25 .2. 25.8 H. 5 on 358962 55; - 3H 35.5 - 2.5.2- 25 .5 25 .5 25.5 25 .mm 25 .2. 25.5 H. H. mm .8880 25.5 + 25 25.5 - 25.5 - 25 .mm 55.2. 55.5 25.2. 25 .5 25.2. 5 H. on 528555 25.HH+ :5 25.5 - 55.5 .. 25.5 55.5 25.55 25.5 25.5 25.2. H. 5 mm 552.... 25.55 5H 2.5.5 - 25 .5 - 25 .5” 25 .5 2.8.2 2.5.2.. 25 .5 25.2. 5 H. mm .22. 2.35.. 2H 25; - 25 .H - 25 .3 25 .5 25.2 25 .5 25 .5 25.2. m 5 om. 2.2. 525+ 25 25.5 + 5H .s + 25 .5 2.5.5 25.5 2.5.2.. 25 .5 2.5.? H. H. mm 222 «5.3+ 2H 55.5 - 25.5 - 25 .3 25.5 2.5.2 58.3 25 .558 .2. H. H. Hm Fa... 25 .5H+ H.HN 55.5 + 55 .5 + 25 .2 53.5 255 .2“ 58.5 25 .5 H55 .2. 5 5 Ha . :2qu 252+ 5H 2: .H. + 5H .5 + 25 .2. 55.: 25.: 25 .2 25 .5 25 .E H. H. 5 28532 25.5 + EH 25.5 + 55 .~H+ 25 .NH H55 .2 25 .5 2.5.5 25 .2. 2.5.: . H. H. .8 28:2. I .2: .HmEm 8:5 .8: :22 325 «E H52, 3:5 .3: 52 .2: :22 .2: 522 .25 Hum 939 .E=U .02 35250 .30230 032234. gown—«O 355:5 .5533. oHnaHHa>< H02 .30 H33. WBHU o 9 o :3 o 1:: c: p 20. 420 2 656 21. 876 4. 112 23. 331 5. 567 fighth Month Storage Inventory cost . 340 . 365 . 389 Floor space cost A . 065 . 065 . 065 20. 825 3. 061 22. 306 4. 542 23. 785 6. 021 Ninth Month Storage Inventory cost . 347 . 372 . 396 Floor space cost . 065 _._Q§_5_ . 065 21. 237 3. 473 22. 743 4. 979 24. 246 6. 482 Tenth Month Storege Inventory cost . 354 . 379 . 404 Floor space cost . 065 . 065 . 065 21. 656 3. 892 23. 187 5. 423 24. 715 6. 951 Eleven Month Storage Inventory cost . 361 . 386 . 412 Floor space cost . 065 . 065 , _LOQ 22. 082 4. 318 23. 638 5. 874 25. 192 7. 428 1"? AN FUR 5:1.««‘\E“;I'_)IT\3(§ N“:"«.(‘I~HT\VE FOR 1.57 Li ». 4 V a. halfflql‘fl‘ . » -Mu‘me- 4..«—-__....-q,..._\-.~ . I 323‘. » ‘ - ~ —-p_.-.v.1..__ . .4.; .. ,A7.:,.. r 3 5 I 1 _..,.._‘._~—._ 1.-....Mn I r—r 4. ' ._ ,. "FY51 ' . -1«4‘-\ "Iv-u...“ -,., .~« .I. | . , . . . .- -47.»... r... . - “nun... -- ' '--- ,n-u // -: » .‘.-' I >.--..... -..~—.—......M\--\_ :-..-..- ~ ' 1 .-..-_ .11...-1-‘.:L...; . \ t 1 9 IFWuwu—no.w-mu.§nu. . . - m... .-. -o.-—-—-.—| — . _ a _ 1' ' I v t ’ . . 7 .. - .mdz-r '5)? '.'m7aq-r—uvtkavb;~ v ' 1' , . _~ r v. . ... .- v I :‘ ,. . an”! In" :‘1uW. 'Lm. . of" ”1'1" v 7 enunuuah ”mun“. ~.-vv<.u» 2 i ..'. I f 9.1 2 I .. u,- I z r ..... a, .. V "P- .— ‘\ I *f-yo a '1 I , _4_, A“ I l V -. I I I \ I 3,];- an; I L (:5 . A ) 1 ._ T” - .. ( I g L.‘ I L - . . 1 ._ .7. p, . I H , . 1—1 2 ; Sputum L- l/ .. 2 Straight 2 straight 1-1/ 2 2 Sualght 1° 1,"? 2 Straight 1-1/‘2 2 Straight 1.1/2 2 Demand W arizr‘ , t '1 ru-mme ’E'izm» (Wartime. Overtime Time Overtime Overtime Time Overd me Overtime Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime Forecast syn—u...” mkp”- ... 5...--. i I — --, ,v~.-. _aYn-—“.. July fmly July Aug. Aug. Sept. Sept, OcL Oct. Oct, NOV. Nov.' NOV. Sept. Dec. Dec. Dec. E'mz'r: 5 June. ? ' M '/ 1 ”M «M -M -M -M ~M -_.1 -M -M 'M -M «M -M -M -M 14. .1--. i i n fiv-vo—>K-Av—n—w~ -- . m 4‘ I l ; ‘. I I l. 4 4.4““ r... "L. . .A- . , .1. A!J1.wv-_.~l~ov'fl< . .. .. : 1 .-..,T "m”...rJ-.- ”.7... MMMIA , I j J ) . . a “i l t L -. “4, t -«-(~--.. W+ .' m s.“ y , I «-7 _.J . —}.. | A. .7 “1,. , 1-. .. r' If 4‘64 2 ~:s_';73; E«4 .7- t T '— 8,461 3,562 11,592 4,416 26,933 13,077 6,746 21,973 9,308 3,818 14,933 3‘3 7 LOWEST COST PRODUCING PLAN FOR SANDING MACHINE FOR 1957 Jan. Jan. Jan. Feb. Feb. Feb. Mar. Mar. Mar. Apr. Apr. Apr, May May May June June June July July July Aug. Aug. Aug. Sept. Sept. Sept. Oct. Oct. Oct. Nov, Nov. Nov. Dec. Dec. Dec. Straight 1' 1/ 2 2 Straight 1- 1/2 2 Straight 1' 1/2 2 Straight 1' 1/2 2 Straight 1- 1/ 2 2 Straight 1- 1/ 2 _3 2 Straight 1- 1/ 2 2 Straight 1- 1/ 2 2 Straight 1- 1/ 2 2 Straight 1- 1 / 2 2 Straight 1- 1/ 2 2 Straight 1. 1/2 2 Demand Time Overtime Overtime Time Overtime Overtime Time Over time Overtime Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime , Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime Time Overtime Overtime Forec ast ‘. I 0 61.294 62. 588 -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M 'M 'M “M “M 'M 'M ‘M "M 'M 'M 'M 'M 'M 'M 12 500 I JAN. ~ ’ o ‘ 12, 500 ., 361 61.677 2. 992 0 1.294 62.588 -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M * -M -M -M -M 7.500 FEB. 7, 500 .728 62.066 3. 423 6.861 1.677 62. 992 0 61.294 14.588 -M -M -M -M -M -M -M -M -M " -M l -M -M -M -M -M -M -M -M -M -MJ -M l -M -M -M _M _M [ .M . 4 _. _. . , 17,500 ‘1 MAR. 960 - 11, 600 4, 940 " 1.101 2, 462 63.841 6. 728 2. 066 3. 423 -.361 61.677 62.992 0 -1.294 62.588 -M -M -M -M -M -M -M -M -M --M -M -M -M -M -M -M -M -M -M “M 'M -M -M -M 22 500 APR 1 9, 006 3,494 i I 61. 480 2.864 ~4. 249 -1. 101 2. 462 .3, 841 P. 728 ~2. 066 63, 423 6, 361 -1, 6'17 62, 992 0 61.294 -2.588 -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M 17 500 MAY . g . 16,452 1,048 I 1. 866 3. 278 64. 682 61,48c -2. 864 I 64. 249 61.101 62.462 63. 841 6. 728 62, 066 68.423 6.361 61.677 I2.992 0 1.294 -2.588 -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M _M _M ,M 20 000 JUNE 20, 000 2.258 63.689 65.121 61.866 68.278 64.682 61.480 62.864 -4.249 61,101 62. 462 I3.841 -.728 2.066 I3.428 —,361 61.677 -2.992 0 61.294 2.588 -M -M -M -M -M -M -M -M -M -M -M -M -M -M -M 25 000 JULY ' . . . I 1.245 18,933 4,822 2.656 4.112 5.567 2.258 -3.689 5.121 -1.866 68.273 64,682 61.480 62.864 64.249 61.101 ~2.462 63.841 .728 I2.066 —3.423 I.361 -1.677 I2.992 0 4.294 _2 588 -M -M -M -M -M -M -M -M -M -14 -M ' -M 27 500 AUG. - I t_‘. . 4 .._—_—I. o n . 14, 805 12, 695' I , -4061 .4542 6,021 62.656 4.112 -5.567 62.258 68.689 -5.121 1.866 8.278 “4.682 -1480 -2854 .4249 .1401 .2462 63.841 -.728 .1066 .3423 _.361 -1.677 62.992 0 1.294 -2,588 -M -M -M -M -M -M ‘M 'M 'M ' 32 500 I SEPT. 11, 593' 20,902 3.473 *4-979 433432 3-061 “4542 '6-021 '2-656 '4-112 ['5-567 r2258 3.689 -5.121 61.866 63.273 64.682 -1.480 62.864 64.249 61.101 2.462 63.841 6. 728 -2.066 -3.423 -.861 1.677 62.992 0 61.294 2.588 -M -M -M -M -M 'M 30 000 ' OCT. ' *6 — ’ g 6,031 21.872 2,097 3,892 -5423 66.951 3.473 64.979 66.482 ~3.061 -4.542 66.021 t2.656 64.112 65.567 -2,25 .3,689 65.121 -1.866 63.278 -4.682 61.480 62,864 4,249 -1,101 -2.462 68.841 -. 728 2.066 3.423 6.361 -1,677 -2.992 0 -1.294 -2.588 -M -M -M 22 500 Nov. . - , —- - - _ , . . - ~ 101 14.933 7.466 64.318 —5.87 7.428 63.892 65.428 66.951 -3.473 -4.979 66.482 -3.061 64.542 66.021 62.656 64.112 -5.567 -2,258 -3.689 « 65.121 -1.866 63,273 -4,682 61.480 ~2,864 .4249 -1,101 -246 3,841 -,728 -2,066 -3.423 ~ -.361 -1.677 -2.992 . 0 1-294 '2-583 DEC. ‘ j '--—' 14’ 267 733 15,000 7 0 0 0 0 ° ° ° ° ° 0 ° 0 0 o 0 0 0 0 0 0 0 0 0 o 0 0 0 0 0 0 0 o o o 0 0 DUMMY -- w m — -- ' , 4 ,4 , , 147,673 9. 069 3. 819 5. 170 2. 304 . _11. €99 5, 706 8, 781 3, 797 9.728 :4. 096 9, 493 4, 746 8, 461 3, 562 11, 592 4, 416 12, 077 6, 746 7, 211 3, 818 2, 986 5. 143 3. 253 2123153: I—" ' __ L— 3 253 397,673 20. 960 9.069 3. 819 11, 600 5.170 2, 304 23. 946 1 1. 699 5. 706 19. 946 8. 781 3, 797 22, 293 9, 728 4. 096 18, 933 9, 493. 4, 746 19,627 8, 461 3,562 24, 293 11, 592 4, 416 26, 933 12, 077 6, 746 21, 973 9, 308 3, 818 14, 933 7, 466, 2,986 . 14. 267 5’ 376 ' TABLE XXVII SIMPLEX SOLUTION TO PRODUCT ALLOCATlON PROBLE M -/‘/53'.2 J14” 4. 4 mafia mzwflwfim WM44/JOJWL4MW wa/aouwaa/Mflm a 44 o 4.7,. 14 77.14 74.4w owaoa/Oooa 0M200/0/7/7M Owl/000000 14,/54%4000/000 %%0/0077770 fiMWO/OOOOO 2 4.. a 4.224 44 a“ 4w m WflOOOOO/O ova/4.000.0/00 «a w,%4w3/44%%1 0 4 0 .4 4 ._. V Date Due Au 23 '5 ROOM USE UNLY Dec6’57 Demco-293 I I l I I III I III I l ElHlHllllllill 47