LINEAR PROGRAMMING

THE ROLE OF MATHEMATICAL MODELS IN OPERATIONS DECISION MAKING

Advances in business and engineering research and computer technology have expanded managers use of mathematical models. A model represents the essential features of an object, system, or problem without unimportant details. The models in this supplement have the important aspects represented in mathematical form using variables, parameters, and functions. Analyzing and manipulating the model gives in-sight into how the real system behaves under various conditions. From this we deter-mine the best system design or action to take. Mathematical models are cheaper, faster, and safer than constructing and manipulating real systems. Suppose we want to find the mixture of recycled scrap paper to use when producing a type of paperboard that minimizes cost. A company could try several different combinations, check the quality, and calculate the cost. Since all possible combinations are not tried, the optimum combination will probably not be found. Alternatively, using a mathematical model, we evaluate all possible combinations to find the one that satisfies product specifications at the lowest price. Mathematical modelling is quicker and less expensive than using the trial-and-error approach. Facility location, vehicle routing and scheduling, personnel, machine and job scheduling, product mixes, and inventory management problems are formulated as constrained optimization models. Constrained optimization models are mathematical models that find the best solution with respect to some evaluation criterion from a set of alternative solutions. These solutions are defined by a set of mathematical constraintsmathematical inequalities or equalities. This type of model is called a linear programming model or a linear program because the objective function is linear and functions in all the constraints are linear.

CONSTRAINED OPTIMIZATION MODELS

1. Decision variables are physical quantities controlled by the decision maker and represented by mathematical symbols. For example, the decision variable xj can represent the number of pounds of product j that a company will produce during some month. Decision variables take on any of a set of possible values. 2. Objective function defines the criterion for evaluating the solution. It is a mathematical function of the decision variables that converts a solution into a numerical evaluation of that solution. For example, the objective function may measure the profit or cost that occurs as a function of the amounts of various products produced. The objective function also specifies a direction of optimization, either to maximize or minimize. An optimal solution for the model is the best solution as measured by that criterion.
3. Constraints are a set of functional equalities or inequalities that represent physical,

economic, technological, legal, ethical, or other restrictions on what numerical values can be assigned to the decision variables. For example, constraints might ensure that no more input is used than is available.
1

LINEAR PROGRAMMING
ADVANTAGES AND DISADVANTAGES OF USING OPTIMIZATION MODELS
The main benefit of optimization models is the ability to evaluate possible solutions in a quick, safe, and inexpensive way without actually constructing and experimenting with them. Other benefits are as follows. 1. Structures the thought process. Constructing an optimization model of a problem forces a decision maker to think through the problem in a concise, organized fashion. The decision maker determines what factors he or she controls; that is, what the decision variables are. The decision maker specifies how the solution will be evaluated (the objective function). Finally, the decision maker describes the decision environment (the constraints). Modelling acts as a way of organizing and clarifying the problem. 2. Increases objectivity. Mathematical models are more objective since all assumptions and criteria are clearly specified. Although models reflect the experiences and biases of those who construct them, these biases can be identified by outside observers. By using a model as a point of reference, the parties can focus their discussion and disagreements on its assumptions and components. Once the model is agreed on, people tend to live by the results. 3. Makes complex problems more tractable. Many problems in managing an organization are large and complex and deal with subtle, but significant, interrelationships among organizational units. For example, in determining the optimal amounts of various products to ship from geographically dispersed warehouses to geographically dispersed customers and the routes that should be taken, the human mind cannot make the billions of simultaneous trade-offs that are necessary. In these cases, the decision maker often uses simple rules of thumb, which can result in less than optimal solutions. Optimization models make it easier to solve complex organization-wide problems. 4. Make problems amenable to mathematical and computer solution. By rep-resenting a real problem as a mathematical model, we use mathematical solution and analysis techniques and computers in a way that is not otherwise possible. 5. Facilitates what if analysis. Mathematical models make it relatively easy to find the optimal solution for a specific model and scenario. They also make what if analysis easy. With what if analysis, we recognize that the prices, demands, and product availabilities assumed in constructing the model are simply estimates and may differ in practice. Therefore, we want to know how the optimal solution changes as the value of these parameters vary from the original estimates. That is, we want to know how sensitive the optimal solution is to the assumptions of the model. What if analysis is also called sensitivity or parametric analysis. Although mathematical modelling has many advantages, there are also disadvantages. The actual formulation or construction of the model is the most crucial step in mathematical modelling. Since the problems tend to be very complex, it is possible to mismodel the real problem. Important decision variables or relationships may be omitted or the model may be
2

LINEAR PROGRAMMING
inappropriate for the situation. The optimal solution to the wrong problem is of no value. A second disadvantage is, not understanding the role of modelling in the decision-making process. The optimal solution for a model is not necessarily the optimal solution for the real problem. Mathematical models are tools to help us make good decisions. However, they are not the only factor that should go into the final decision. Sometimes the model only evaluates solutions with regard to quantitative criteria. In these cases qualitative factors must also be considered when making the final decision. The bottom line for evaluating a model is whether or not it helps a decision maker identify and implement better solutions. The model should increase the decision makers confidence in the decision and the willingness to implement it.

ASSUMPTIONS OF LINEAR PROGRAMMING MODELS

1. Proportionality. With linear programs, we assume that the contribution of individual variables in the objective function and constraints is proportional to their value. That is, if we double the value of a variable, we double the contribution of that variable to the objective function and each constraint in which the variable appears. The contribution per unit of the variable is constant. For example, suppose the variable xj is the number of units of product j produced and cj is the cost per unit to produce product j. If doubling the amount of product j produced doubles its cost, per unit cost is constant and the proportionality assumption is satisfied. 2. Additivity. Additivity means that the total value of the objective function and each constraint function is obtained by adding up the individual contributions from each variable. 3. Divisibility. The decision variables are allowed to take on any real numerical values within some range specified by the constraints. That is, the variables are not restricted to integer values. When fractional values do not make a sensible solution, such as the number of flights an airline should have each day between two cities, the problem should be formulated and solved as an integer program. 4. Certainty. We assume that the parameter values in the model are known with certainty or are at least treated that way. The optimal solution obtained is optimal for the specific problem formulated. If the parameter values are wrong, then the resulting solution is of little value. In practice, the assumptions of proportionality and Additivity need the greatest care and are most likely to be violated by the modeller. With experience, we recognize when integer solutions are needed and the variables must be modelled explicitly.

FORMULATING LINEAR PROGRAMS

This section presents simple examples of real managerial problems that can be formulated as linear programs. Each example has a name describing the type of problem. In real life, problems are seldom as pure and clean as these examples. Do not try to memorize and match the problems illustrated here with real problems you may en-counter. In practice, problems may contain a mixture of features from several of the categories illustrated here.
3

LINEAR PROGRAMMING
You should focus on why and how various physical relationships are best represented in model form. Model formulation is the most important and the most difficult aspect of solving a real problem. Solving a model that does not accurately represent the real problem is useless. There is no simple way to formulate optimization problems, but the following suggestions may help.

Steps in Problem Formulation

1. Identify and define the decision variables for the problem. Define the variables completely and precisely. All units of measure need to be stated explicitly, including time units if appropriate. For example, if the variables represent quantities of a product produced, these should be defined in terms of tons per hour, units per day, barrels per month, or some other appropriate units. 2. Define the objective function. Determine the criterion for evaluating alternative solutions. The objective function will normally be the sum of terms made up of a variable multiplied by some appropriate coefficient (parameter). For example, the coefficients might be profit per unit of production, distance travel per unit transported, or cost per person hired. 3. Identify and express mathematically all of the relevant constraints. It is often easier to express each constraint in words before putting it into mathematical form. The written constraint is decomposed into its fundamental components. Then substitute the appropriate numerical coefficients and variable names for the written terms. A common mistake is using variables that have not been defined in the problem, which is not valid. This mistake is frequently caused by not defining the original variables precisely. The formulation process is iterative, and sometimes additional variables must be defined or existing variables redefined. For example, if one of the variables is the total production of the company and five other variables represent the production at the companys five plants, then there must be a constant that forces total production to equal the sum of the production at the plants. Feed Mix or Diet Problem Example International Wool Company Feed Mix Problem International Wool Company operates a large farm on which sheep are raised. The farm manager determined that for the sheep to grow in the desired fashion, they need at least minimum amounts of four nutrients (the nutrients are nontoxic so the sheep can consume more than the minimum without harm). The manager is considering three different grains to feed the sheep. Table B-2 lists the number of units of each nutrient in each pound of grain, the minimum daily requirements of each nutrient for each sheep, and the cost of each grain. The manager believes that as long as a sheep receives the minimum daily amount of each nutrient, it will be healthy and produce a standard amount of wool. The manager wants to raise the sheep at minimum cost.

LINEAR PROGRAMMING
Table B-2 1 20 10 50 6 41 Grain 2 30 10 30 2.5 36 3 70 0 0 10 96 Minimum Daily Requirement (units) 110 18 90 14

Nutrient A Nutrient B Nutrient C Nutrient D Cost (/lb)

Solution The quantities that the manager controls are the amounts of each grain to feed each sheep daily. We define xj = number of pounds of grain j (= 1, 2, 3) to feed each sheep daily Note that the units of measure are completely specified. In addition, the variables are expressed on a per sheep basis. If we minimize the cost per sheep, we minimize the cost for any group of sheep. The daily feed cost per sheep will be (cost per lb of grain j) x (lb. of grain j fed to each sheep daily) That is, the objective function is to Minimize z = 41x1 + 36x2 + 96x3 Why cant the manager simply make all the variables equal to zero? This keeps costs at zero, but the manager would have a flock of dead sheep, because there are minimum nutrient constraints that must be satisfied. The values of the variables must be chosen so that the number of units of nutrient A consumed daily by each sheep is equal to or greater than 110. Expressing this in terms of the variables yields 20x1 + 30x2 + 70x3 110 The constraints for the other nutrients are: 10x1 + 10x2 18 50x1 + 30x2 90 6x1 + 2.5x2 + 10x3 110 and finally all xjs 0 The optimal solution to this problem (obtained using a computer software package) is x1 = 0.595, x2 = 2.008, x3 = 0.541, and z = 148.6 cents. It is common practice to take a model initially used for one application and apply it to other situations. The feed mix problem is a good example of a case where one might use the same basic structure of a model in different applications. For example, a golf course manager can use the model to select the best mix of fertilizers to provide the grass with the desired amounts of active chemicals (nitrogen, phosphorus, potash). The managers problem is structurally the same as that faced by the manager of International Wool. The basic feed mix problem makes several subtle assumptions that do not apply for humans. First, issues of taste have been ignored. Earlier, we assumed that the sheep will eat whatever grain mixture we feed them. Humans have varying tastes to consider. Some foods may not taste good together. Second, not all humans are of similar size or have the same appetite. Third, the basic feed mix is a static model: the optimal feed mix today is the same as that of tomorrow and the next 500 days unless some parameters change. We do not want to feed people the same meal day after day.
5

LINEAR PROGRAMMING
THE GEOMETRY OF LINEAR PROGRAMS
The characteristic that makes linear programs easy to solve is their simple geometric structure. Lets define some terminology. A solution for a linear program is any set of numerical values for the variables. These values need not be the best values and do not even have to satisfy the constraints or make sense. For example, in the Healthy Pet Food problem, M = 25 and Y = 800 is a solution, but it does not satisfy the constraints, nor does it make physical sense. A feasible solution is a solution that satisfies all of the constraints. The feasible set or feasible region is the set of all feasible solutions. Finally, an optimal solution is the feasible solution that produces the best objective function value possible. Figure B-1 shows the relationships among these types of solutions. Lets use the Healthy Pet Food example to show the geometry of linear pro-grams and to show how two-variable problems can be solved graphically. The linear programming formulation for the Healthy Pet Food problem is: Maximize z = 0.65M = 0.45Y Subject to 2M + 3Y 400,000 3M + 1.5Y 300,000 M 90,000 and M, Y 0 Where M is the number of packages of Meaties made and sold per month and Y is the number of packages of Yummies made and sold per month. Suppose we construct a coordinate system with M measured on the horizontal axis and Y measured on the vertical axis, as shown in Figure B-2. Each point in the M, Y plane corresponds to a product mix or production plan. The coordinate values for each point represent conceivable, though not necessarily physically possible, values for the variables. Further-more, every possible product mix is represented by a point in the M, Y plane. The best solution is the point that makes the objective function as large as possible yet satisfies all the constraints. Figure B-1: Relationship among solutions

LINEAR PROGRAMMING
Figure B-2.: Graphical representation of the Healthy Pet Food problem

THE GRAPHICAL SOLUTION APPROACH We begin the solution process by finding the feasible set. The geometric representation of a linear equality is the set of points that lie on and to one side of the line obtained by replacing the inequality sign with an equality sign. The constraint M 0 restricts us to the points on or to the right of the vertical axis (the line M = 0). The constraint Y 0 restricts us to the points on or above the horizontal axis. Next, we draw the constraint 2M + 3Y 400,000. To find the points that satisfy this inequality, we construct the line 2M + 3Y 400,000 by finding two points that lie on the line and then constructing a line through these points. The easiest points to find on the line are the ones that lie on the two axes. First, set M = 0 and solve for Y. This yields the point (M = 0, Y = 133,333.22). We then set Y = 0 and solve for M. This yields the point (M = 200,000 and Y = 0). This line is plotted on Figure B-2. We now determine on which side of the line the points satisfy the constraint. If one point satisfies the constraint, then all points on the same side of the line satisfy the constraint. If one point does not satisfy the constraint, then no point on that side of the line satisfies the constraint, but all the points on the opposite side of the line do satisfy the constraint. It makes sense to select a simple point with which to work, such as (M 0, Y 0). This point satisfies the constraint 2M + 3Y 400,000. Therefore, all points to the lower left do also. The points to the upper right of the line represent product mixes that require more than 400,000 pounds of cereal each month and can be eliminated from consideration. We do the same thing for the meat constraint: 3M + 1.5Y 300,000. We find two points on the line 3M + 1.5Y 300,000. We first set M = 0 and solve for Y, and then set Y = 0 and solve for M, yielding the points (M = 0, Y = 200,000) and (M = 100,000, Y = 0). Checking a point on one side of the line shows that the points on or to the lower left of the line are the ones that satisfy the constraint. The final constraint, M 90,000, is satisfied by the points that lie on or to the left of the
7

LINEAR PROGRAMMING
vertical line M 90,000. The feasible set is the set of points in the five-sided shaded area in Figure B-2. The feasible set for a linear program will always have a shape like the one in this problem, with edges that are straight lines and corners where the edges meet. The corners of the feasible set are called extreme points. Note that each extreme point is formed by the intersection of two or more constraints. USING LINEAR PROGRAMMING MODELS FOR DECISION MAKING The formulations earlier in the supplement give the impression that using linear programming is a simple process. In practice, using linear programming and other optimization models is not so straightforward, nor is it static. Specifically, our goal in using models is to obtain usable solutions that are better than those we would have obtained without the models, to use the models to revise and update our decisions in a timely fashion, and to increase our confidence in our decisions. Lets look at the Healthy Pet Food problem to see how we might use his model in practice and to see what benefits we can gain. 2 Healthy Pet Food Demand Function Solved Problem Chip Green is the head groundskeeper at Birdie Valley Golf Club. For the mix of grass for the golf course, Chip has decided that the best fertilizer would be a 10-8-12 mixture. (Fertilizer is defined by three valuesa, b and cwhere a is the percentage of nitrogen, b is the percentage of phosphorus, and c is the percentage of potash in the fertilizer. The remaining material is inert matter.) Chip can buy a 10-8-12 mix of fertilizer for $21.75 per 100 pounds, but there are other fertilizers on the market at a variety of prices. The chemical content and prices are given below. Chip would like to determine whether or not he could buy several fertilizers and mix them together to obtain a 10-8-12 mixture at a lower cost than $21.75 per 100 pounds. Recognizing that it might be impossible to obtain an exact 10-8-12 mix from the fertilizers, Chip is willing to accept chemical percentages of at least the target amounts, but no more than 0.5% above them (so the nitrogen level should be between 10% and 10.5%). Formulate Chips problem as a linear program. Fertilizer %Ni %Ph %Po Cost/100 lb 1 10-8-12 $21.75 2 8-11-15 $23.50 3 12-7-12 $22.00 4 10-10-10 $19.50 5 15-10-6 $18.50 Solution: Chip is interested in the mix of fertilizers to use, so we can define the variables xj = lb of fertilizer j in each lb of mixture. The objective is to minimize the cost per pound of fertilizer: Minimize z = 0.2175 x1 + 0.2350 x2 + 0.2200 x3 + 0.1950 x4 + 0.1850 x5 The main constraints are those that ensure the desired percentage of nitrogen, phosphorus, & potash.

LINEAR PROGRAMMING
Because the variables are defined as the amount of each type of fertilizer in 1 pound of mixture, we need a constraint that ensures that the mixture adds up to exactly 1 pound: x1 + x 2 + x3 + x4 + x 5 = 1 Problem: Volcano Potato Company (VPC) grows potatoes, processes them, and then sells three potato products: fresh potatoes, frozen french fried potatoes, and frozen hash ball potatoes (shredded and then reconstituted balls of potatoes with a soft consistency). During the next two months, VPC expects to harvest 8 million pounds of potatoes. VPC would like to determine how much of each product should be made from the potatoes. Potatoes are graded according to quality on a 0 5 scale. VPC divides its potatoes into three grades: A, B, and C. Grade A potatoes have an average quality rating of 4.5; grade B potatoes have an average quality rating of 2.5, and grade C potatoes have a quality rating below 1 and are not used for any products. From historical data and estimates based on the current growing seasons weather, VPC believes the distribution of potato quality will be: Grade A B C % of Harvest 50 40 10 Fresh potatoes earn a profit of $0.40 per pound after processing costs, but only grade A potatoes can be sold as fresh potatoes. Frozen french fried potatoes earn $0.32 per pound after processing costs, but the potatoes used must have an average quality rating of at least 3.5. Hash balls earn $0.25 per pound after processing costs, but the potatoes used must have an average quality rating of at least 3.0. Assume that these ratings are linear in the sense that the quality rating of a mixture equals the weighted average of the inputs. VPC believes it can sell as much french fried and hash ball potatoes as it can make, but it believes the total demand for its fresh potatoes during the next two months is 2.5 million pounds. Formulate a linear programming model to determine the best use for the potatoes so as to maximize VPCs profit. Problem: Ronald Stimpson is regional sales manager for an industrial products company. His region contains four sales districts. He supervises 10 sales representatives and controls an advertising budget of $800,000 per year. Mr. Stimpson believes that sales in a district are related to the amount of advertising and the number of sales reps assigned to the district. Based on historical data, his estimates of incremental annual sales per dollar of advertising and sales per sales rep for each district are given in the following table. Mr. Stimpson would like to determine how to allocate sales reps and the advertising budget among the four districts to maximize sales. To maintain a reasonable presence in each market, however, each district must be assigned at least one sales rep, and at least $50,000 must be spent on advertising in each market. Formulate a linear programming model to solve his problem. District 1 2 3 4 $ sales/$ advertising 7 12 10 11 $ sales (0000)/sales rep 38 25 36 41 Problem: Great Plains Advertising Company (GPAC) has a $150,000 advertising budget to advertise an automobile firm. GPAC is considering advertising in newspapers and on television. The more GPAC advertises in a particular medium, the less effective additional ads are in reaching new customers. The following table lists the number of new customers reached by each ad. Each newspaper ad costs $1500, and each television ad costs $10,000. At most 30 newspaper ads and 15 television ads can be placed. Also, GPAC would like to use
9

LINEAR PROGRAMMING
at least as many newspaper ads as television ads. Formulate a linear program that will maximize the number of new customers contacted subject to the previous restrictions. (Hint: You need six variables, not two.) No. of Ads 1 10 11 20 21 30 15 6 10 11 15 New Customers/Ad 900 600 300 10,000 5,000 2,000

Newspaper

Television

Problem: Metallica Manufacturing Company has seen the demand for two new types of metal alloys explode in recent months. The alloys, which are made by mixing copper, nickel, and aluminium, do not require an exact formulation of components but must satisfy the following general specifications: Copper costs $2 per pound, nickel $3 per pound, and aluminium $1.50 per pound. Metallica has a limit of 2000 pounds of copper, 3000 pounds of nickel, and 4000 pounds of aluminium available each day. Assume that the company can sell as much of each alloy as it makes at a price of $5 per pound for alloy A and $6 per pound for alloy B. Formulate the companys problem as a linear program to maximize profit. Alloy A Alloy B At least 40% copper No more than 35% copper At least 10% nickel At least 40% nickel No more than 25% nickel No more than 30% aluminium Aluminium content must be exactly twice that of nickel Problem: Wilson Creek Farm has 200 acres of land available for planting. The owner is considering planting three crops: corn, soybeans, and wheat. The production yield, water requirements, and labour requirements for a saleable crop are given here. The owner expects to have only 35,000 gallons of water available per week to use for the crops, and during the growing season he will only have 8000 person-hours of labour available. The expected profit per bushel of each crop is $1.00 for corn, $1.60 for soybeans, and $3.00 for wheat. The owner can use any mix of crops (i.e., he can plant the same crop on all 200 acres or he can plant all three crops in different proportions). Formulate the problem as a linear program to find the profit-maximizing planting strategy. Crop Corn Soybeans Wheat Bushels/Acre Water Required Person-Hours Labour Produced (gal/acre/week) Required/Acre 300 200 80 200 150 125 35 40 30

10