A mathematical technique that solves resource allocation problems
Matt Free owns software development company. On product line involves designing and producing software that detects and removes viruses. The software comes in to formats: Windows and Mac versions. He can sell all of these products that he can produce which is his dilemma. The two formats go through the same production departments. How many of each type should he make maximize his profits?
A close look at Free’s operation tells us he can use a mathematical technique called linear programming to solve his resource allocation dilemma. As we will show, linear programming is applicable to his problem but it cannot be applied to all resource allocation situations. Besides requiring limited resources and the objective of optimization it requires that there be alternative ways of combining resources to produce a number of output mixes. A linear relationship between variables is also necessary which means that a change in one variable will be accompanied by an exactly proportional change in the other. For Free’s business this condition would be met if it took exactly twice the time to produce two diskettes – irrespective of format – as it took to produce one.
Many different types of problems can be solved with linear programming. Selecting transportation routes that minimizes shipping costs, allocating a limited advertising budget among various product brands , making the optimum assignment of personnel among projects and determining how much of each product to make with a limited number of resources are just a few. To give you some idea of how linear programming is useful, let’s return to Free’s situation. Fortunately, his problem is relatively simple, so we can solve it rather quickly. For complex linear programming problems, computer software has been deigned specifically to help develop solutions.
First we need to establish some facts about the business. He has computed the profit margins to be $ 18 for the Windows format and $ 24 for the Mac. He can, therefore, express this objective function a maximum profit = $ 18R + $ 24S , where R S the number of Windows based CDs produced and S is the number of Mac CDs. In addition, he knows how long it takes to produce each format and the monthly production capacity for virus software: 2,400 hours in design and 900 hours in production. The production capacity numbers ct as constraints on his overall capacity. Now Free can establish his constraint equations:
4R + 6S < 2,400
2R + 2S 0 and S> 0. He has graphed his solution as shown. The beige shaded area represents the options that do not exceed the capacity of either department. What does the graph mean? We know that total design capacity is 2,400 hours. So if Matt decides to design only the Windows format, the maximum number he can produce is 600 (2,400 hours ÷ 4 hours of design for each Windows versions). If he decides to produce all Mac versions the maximum he can produce is 400 (2,400 hours ÷ 6 hours of design for Mac). This design constraint is shown in Exhibit as line BC. The other constraint Matt is that of production. The maximum of either format he can produce is 450, because each takes two hours to copy verify, and package.
Free’s optimal resource allocation will be defined at one of the corners of this feasibility region (areas ACFD). Point F provides the maximum profits within the constraints stated. At pointing a, profits would be zero because neither virus software version is being produced. At point C and D profits would be $ 9,600 (400 uits @ $24) and $ 8,100 (450units @ $18), respectively. At point F profits would be $9,900 (150 Windows units @ $18 + 300 Mac units @ $24).