Up to now, we have concentrated on the role of descriptive analytics and pre- dictive analytics in managerial decisions. In every area of business, managers want to make the best possible decisions. For example, marketing analysts want to choose the best advertising to attract the most customers; finance manag- ers want to set the best prices to maximize profit; operations managers need to determine the best inventory and production policies. In your own life, you might want to find the best route for vacation travel (thank you, Google maps) or deter- mine the best players for a fantasy sports team. While many decisions involve only a limited number of alternatives and can be addressed using statistical analysis, simple spreadsheet models, or simula- tion, others have a very large or even an infinite number of possibilities. We intro- duced optimization—the fundamental tool in prescriptive analytics—in Chapter 1. Optimization is the process of selecting values of decision variables that mini- ‘mize or maximize some quantity of interest and is the most important tool for prescriptive analytics. Optimization models have been used extensively in operations and supply chains, finance, marketing, and other disciplines for more than 50 years to help managers allocate resources more efficiently and make lower-cost or more-profitable Cae decisions. Optimization is a very broad and complex topic; in this chapter, we focus U NN- ‘on formulating and solving many practical optimization models in business. Tisgik =e BF Optimization Models There are three basic types of optimization models: linear, integer, and nonlinear Alinear optimization model (often called a linear program, or LP model) has two basic proper- ties. First, the objective function and all constraints are linear functions of the decision variables. This means that each function is simply a sum of terms, each of which is some constant multiplied by a decision variable, such as Sx + 4y. Linear optimization models are easy to solve using highly efficient solution algorithms. The second property of a linear optimization model is that all variables are continuous, meaning that they may assume any real value (typically, nonnegative, that is, greater than or equal to zero). Of course, this assumption may not be realistic fora practical business problem (you cannot produce half a refrigerator). However, because this assumption simplifies the solution method and analysis, we often apply it in many situations where the solution would not be seriously affected. For example, in deciding on the optimal number of cases of diapers to produce y next month, we could use a linear model, since rounding a value like 5,621.63 would have . litle impact on the results. However, in @ production-planning decision involving low- volume, high-cost items such as airplanes, an optimal value of 10.42 would make litle sense, and a difference of one unit (rounded up or down) could hav: and production planning consequences. In an integer linear optimization model (also called an i meth oe ee pga of integer problem is one in which variables can be only 0 or 1; these are used to model Significant economiclogical yes-or-no decisions. Integer linear optimization models are generally more difficult to solve than pure linear optimization models, but have many important applications in areas such as scheduling and supply chains. Finally, there are many situations in which the relationship among variables in a ‘model is not linear. Whenever either the objective function or a constraint is not linear, we have a nonlinear optimization model (also called a nonlinear program, or NLP model), In a nonlinear optimization model, the objective function and/or constraint functions are nonlinear functions of the decision variables; that is, terms cannot be written as a constant multiplied by a variable. Some examples of nonlinear terms are 3x’, 4/y, and 6xy. Building nonlinear optimization models requires more creativity and analytical expertise than linear or integer models; they also require different solution techniques. We will address inte- er and nonlinear models in the next chapter. Nonlinear models may also include integer restrictions; these are among the most difficult types of optimization models to solve. In this chapter, we will focus exclusively on linear optimization, Linear optimization models are the most ubiquitous of optimization models used in ‘organizations today. Applications abound in operations, finance, marketing, engineering, and many other disciplines. Table 13.1 summarizes some common types of generic linear optimization models. This list represents but a very small sample of the many practical {types of linear optimization models that are used in practice throughout business. We will see examples of many of these later in this chapter. > Table 13.1 Generic Examples of Linear Optimization Models Type of Model Decisions Objective Typical Constraints Product mix ‘Quantities of product to Maximize contribution Resource limitations (for produce and sell to profit example, production tine, labor, material); minimum sales requirements; maximum sales potential Process selection Quantities of product to make Minimize cost. Demand requirements; resource using alternative processes limitations Blending Quantity of materials to mix Minimize cost Specifications on acceptable to produce one unt of output mixture Portfolio selection Proportions to invest in ditfer-. Maximize future Limit on available funds; sector cent financial instruments retum or minimize risk requirements or restrictions; exposure proportional relationships on investment mix Tansportation ‘Amount to ship between Minimize total Limited availability at sources; sources of supply and transportation cost _required demands met at destinations pestnatots Mtipetiod Minimize total produc- Limited production rates; production Quantities of product to pro- ; ; Manning Soares Sh ofseveral time tion and inventory material balance equations periods; amount of inventory costs to hold between periods Wiperiod financi vein hort: Maximize cash on hand Cash balance equations ee pmnounie to a required cash obligations Budget imitation; production limitations; demand requirements Pr it term instruments ft “ctlon/marketing Allocation of advertising Maximize prof expenditures; production quantitieshe Developing Linear Optimization Models Any optimization model has the following elements: 1. Decision variables 2. An objective to maximize or minimize 3. Constraints Decision variables in an optimization model are the unknown values that the model seeks to determine. Depending on the application, decision variables might be the quantities of different products to produce, the amount of money spent on R&D projects, the amount to ship from a warehouse to a customer, the amount of shelf space to devote to a product, and so on. The quantity we seek to minimize or maximize is called the objective func- tion; for example, we might wish to maximize profit or revenue, or minimize cost or some measure of risk. Constraints are limitations, requirements, or other restrictions that are imposed on any solution, either from practical or technological considerations or by man- agement policy. The presence of constraints along with a large number of variables usu- ally makes identifying an optimal solution considerably more difficult and necessitates the use of powerful software tools. The essence of building an optimization model is to first identify these model components, and then translate the objective function and constraints into mathematical expressions. Managers can generally describe the decisions they have to make, the performance measures they use to evaluate the success of their decisions, and the limitations and requirements they face or must ensure rather easily in plain language. The task of the analyst is to take this information and extract the key elements that form the basis for developing a model. Developing any optimization model consists of three basic steps: 1, Identify the decision variables, the objective, and all appropriate constraints. 2, Write the objective and constraints as mathematical expressions to create a mathematical model of the problem. 3, Implement the mathematical model on a spreadsheet.‘We will begin with a simple scenario to illustrate the development and spreadsheet implementation of a linear optimization model. Sklenka Ski Company (SSC) is a small ‘manufacturer of two types of popular all-terrain snow skis, the Jordanelle and the Deercrest models. The manufacturing process consists of two principal departments: fabrication and finishing. The fabrication department has 12 skilled workers, each of whom works seven hours per day. The finishing department has three workers, who also work a seven-hour shift Each pair of Jordanelle skis requires 3.5 labor-hours in the fabricating department and 1 labor-hour in finishing. The Deercrest model requires 4 labor-hours in fabricating and 1.5 labor-hours in finishing. The company operates five days per week. SSC makes a net profit of $50 on the Jordanelle model and $65 on the Deercrest model. In anticipation of the next ski-sale season, SSC must plan its production of these two models. Because of the popularity of its products and limited production capacity, its products are in high demand, and SSC can sell all it can produce each season. The company anticipates selling at least twice as many Deercrest models as Jordanelle models. The company wants to determine how many of each ‘model should be produced on a daily basis to maximize net profit. Identifying Decision Variables, the Objective, and Constraints ‘The first thing to do is to read the problem statement carefully and identify the decision variables, objective, and constraints in plain language before attempting to develop a math- ematical model or a spreadsheet. Sklenka Ski Company: Identifying Model Components Step 1. identify the decision variables. SSC makes we diferent models of ss. The decisions are stated ler: now many ofeach model sk retction. inthis example, we ae tat both the ‘should be produced each day? Thus, we may fabrication and finishing departments have limited sefine numbos of workers, who work onl even hours each day, tists the amour of production femme eee time avalabie in each department. Therefore we Overcrest = Number of pairs of Deercrest have the folowing constraints: skis produced /day Fabrication: Total labor-hours used in fabrication cannot exces he amount abor-hours avaible. Finishing: Teta aber nous uses rihing cannot exceed the amount of bor hours aval describe limited resources that are available, Fequirements that must be met, or other Itis very important to clearly specify the dimensions of the variables, for example, “pairs of skis produced/day” rather than simply “Jordanelle skis.” In addition, the company anticipates selling at least twice as many Deercrest models as Jordanelle models. Thus, we need a constraint that states. Step 2. Identity the objective function. The problem states that SSC wishes to maximize net profit, ‘and we are given the net profit figures for each type of ski. In some problems, the objective is not explicitly stated, and we must use logic and business experience to identify the appropriate objective. Step 3. Identify the constraints. To identify constraints, look for clues in the problem statement that Number of paits of Deercrest skis must be at least twice the number of parts of Jordanelle skis, Finally, we must ensure that negative values of the decision variables cannot occur. Nonnegativity constraints are assumed in nearly all optimization models.Chapter 13. Linear Optimization 499 Developing a Mathematical Model The challenging part of developing optimization models is translating the descrip- tions of the objective and constraints into mathematical expressions. We usually Tep- resent decision variables by descriptive names (such as Jordanelle and Deercrest). abbreviations, or subscripted letters such as X; and X2. For mathematical formulations involving many variables, subscripted letters are often more convenient; however, in spreadsheet models, we recommend using descriptive names to make the models and solutions easier to understand. In Example 13.2, we show the importance of specifying the dimension of the decision variables. This is extremely helpful to ensure the accur racy of the model. Stace Sklenka Ski Company: Modeling the Objective Function The decision variables are the number of pairs of each type of ski to produce each day. Because SSC makes a net profit of $50 on the Jordanelle model and $85 on the Deercrest model, then, for example, if we produce 10 pairs of Jordanelle skis and 20 pairs of Deercrest skis during one day, we would make a profit of ($50/pair of Jordanelle skis) (10 pairs of Jordanelle + ($66/pair of Jordanelle skis) (20 pairs of Deercrest skis) = $500 + $1,300 = $1,800. Because we don’t know how many pairs of skis to produce, we write ‘each term of the objective function by multiplying the unit profit by the decision variables we have defined: Maximize Total Profit = $50 Jordanelle + $65 Deercrest Note how the dimensions verify that the expression is correct: (S/pair of skis) (number of pairs of skis) os Constraints are generally expressed mathematically as algebraic inequalities or equa- tions with all variables on the lft side and constant terms onthe right (his facilitates solv- inthe model on a spreadsheet, a we will discuss later). To model the constraints, we use an nilar approach. First, consider the fabrication and finishing constraints. We expressed these constraints as Fabrication: Total labor-hours used in fabrication cannot exceed the amount of labor hours available. Finishing: Total labor-hours used in finishing cannot exceed the amount of labor hours available. First, note that the phrase “cannot exceed” translates mathematically as “=.” In other con- straints, we might find the phrase “at least,” which would translate as “=" or “must contain exactly.” which would specify an “=” relationship. All constraints in optimization models must be one of these three forms. Second, note that “cannot exceed” divides each constraint into two parts—the left- hand side (“total labor-hours used”) and the right-hand side (“amount of labor-hours avail- able”). The left-hand side of each of these expressions is called a constraint funetion. ‘A constraint function is a function of the decision variables in the problem. The right- hand sides are numerical values (although occasionally they may be constraint functions as well) All that remains is to translate both the constraint functions and the right-hand sides into mathematical expressions.500 Chapter 13. Linear Optimization The amount of labor available in fabrication is (12 workers) X (T hours/day) = 84 hours/day, whereas in finishing we have (3 workers) x (7 hours/day) = 21 hours/day. Because ‘8ach pair of Jordanelle skis requires 3.5 labor-hours and each pair of Deercrest skis requires 4 labor-hours in the fabricating department, the total labor used in fabrication is 3.5 Jordanelle + 4 Deercrest. Note that the dimensions of these terms are (hours/pair of skis)(number of pairs Of skis produced per day) = hours. Similarly, for the finishing department, the total labor used is 1 Jordanelie + 1.5 Deercrest. Therefore, the appropriate constraints are: Fabrication: 3.5 Jordanelle + 4 Deercrest = 84 Finishing: 1 Jordanelle + 1.5 Deercrest = 21 For the market mixture constraint “Number of pairs of Deorcrest skis must be at least twice the number of pairs of Jordanelle skis,” we have Deercrest = 2 Jordanelle ‘Sklenka Ski Company: Modeling the Constraints It is customary to write all the variables on the left-hand, side of the constraint. Thus, an alternative expression for this constraint is Deercrest ~ 2 Jordanelle = 0 The difference between the number of Deercrest skis and twice the number of Jordanelle skis can be thought of as the excess number of Deercrest skis produced over the ‘minimum market mixture requirement. Finally, nonnegativity constraints are written as Deorcrest = 0 Jordanelle = 0 The complete mathematical model for the SSC problem is Maximize Total Profit 50 Jordanelle + 65 Deercrest 3.5 Jordanelle + 4 Deercrest = 84 1 Jordanelle + 1.5 Deercrest = 21 Deererest ~ 2 Jordanelle = 0 Deererest = 0 Jordanelle = 0 More About Constraints The most challenging aspect of model formulation is identifying constraints, Understand ing the different types of constraints can help in proper identification and modeling, Con- straints generally fall into one of the following categories: © Simple Bounds. Simple bounds constrain the value of a single variable. You can recognize simplé Bounds in problem statements such as no more than $10,000 may be invested in stock ABC, or we must produce at least 350 units of product Y to meet customer commitments this month, @ Limitations. Li itations usually involve the allocation of scarce resources. Prob- {em statements such as the amount of material used in production cannot exceed the amount available in inventory, minutes used in assembly cannot exceed the available labor hours, or the amount shipped from the Austin plant in July cannot exceed the plant’s capacity are typical of these types of constraints.Requirements. Requireme, ; f per e ¢nts involve the specification of minimum levels of formance. Such statement e Financial obligations mea set cash must be available in February t0 meet Orders, oF the marheg sus tion must be sufficient to meet promised custom a tacted marketing plan should ensure that at least 400 customers are cot ‘ed each month are some examples, Proportional Relationships. Proportional relationships are often found in prob- lems involving mixtures or blends of materials or strategies. Examples include the amount invested in aggressive growth stocks eannot be more than twice the mount invested in equity-income funds, or a mixture of fertilizer must contain exactly 30% nitrogen, Balance Constrains, Balance constraints essentially sate that input = output and ensure that the flow of material or money is accounted for at locations or between time periods, Examples include production in June plus any available inventory must equal June's demand plus inventory held to July, the total amount Shipped to a distribution center from all plants must equal the amount shipped from the distribution center to all customers, or the total amount of money invested or saved in March must equal the amount of money available at the end of February. ove Ses Modeling Constraints \Weilustrate each of these types of constraints in the folowing examples. 1, Simple bound: We must produce at least 350 units of product Y to meet customer commitments this month 2. Limitation: The amount of money spent on research and development projects cannot exceed the assigned bud- get of $300,000. - Requirement: Contractual requirements specify that a total of at least 500 units of product must be shipped from factories in Austin and Atlanta. ~ Proportional relationship: A mixture of fertilizer must Contain exactly 30% nitrogen. : + Balance oe avaiable inventory and production in June must satisfy the demand of 150 units or be held over to July, To model any constraint, first identify the phrase that Soresponds to either =, =, or = and substitute these into the constraint. Thus, for these examples, we would ‘te the following: 1. Amount of = 950 product Y = ean * Amount spent on research and developmen! a + Number of units of product shipped from Atlanta = 500 in ‘Amount of nitrogen in mixture/total amount i Mixture = 0.30 5. Inventory and production in current month = demand and inventory held over to the next month ‘Then it simply becomes an exercise to translate the words into mathematical expressions using the decision variables in the problem. For instance: 1. Define Product_y to be the number of units of product Y produced. Then the constraint is Product_Y = 350 2. Define REDExpenses to be the amount of money spent ‘on research and development projects. Then the con- straint is R&DExpenses = $300,000 3. Define X; = amount shipped from Austin and Xp = amount shipped from Atlanta. Then the constraint is X, + Xp = 500 4, Suppose that two ingredients contain 20% and 33% nitrogen, respectively; then the fraction of nitrogen in a ‘mixture of x pounds of the first ingredient and y pounds of the second ingredient is expressed by °2% = 9397, Ifthe fraction of nitrogen in the mixture must be 0,30, then we would have °2% = 92 _ 9.3, Note that this ‘constraint is actually nonlinear. However, we can con- vert it to a linear form using simple algebra. This can be rewritten as 0.20x + 0.33y = 0.3 + y) and simplified as -0.1x + 0.03y = 0. 5. Define | June = inventory available in June, | July = inven tory held over to July, and P_June = production in June. Then the constaintis Lune + P_lune = 160 + | JulyConstraints in linear optimization models are generally some combination of con- straints from these categories. Problem data or verbal clues in a problem statement often help you identify the appropriate constraint. In some situations, all constraints may not be ‘explicitly stated, but are required for the model to represent the real problem accurately. An ‘example of an implicit constraint is nonnegativity of the decision variables, Implementing Linear Optimization Models on Spreadsheets ‘We will learn how to solve optimization models using an Excel tool called Solver. To facilitate the use of Solver, we suggest the following spreadsheet engineering guidelines for designing spreadsheet models for optimization problems: Put the objective function coefficients, constraint coefficients, and right-hand values ina logical format in the spreadsheet. For example, you might assign the decision variables to columns and the constraints to rows, much like the math- ematical formulation of the model, and input the model parameters in a matrix. If you have many more variables than constraints, it might make sense to use rows for the variables and columns for the constraints. Define a set of cells (either rows or columns) for the values of the decision vari- ables. In some models, it may be necessary to define a matrix to represent the decision variables. The names of the decision variables should be listed directly above the decision variable cells. Use shading or other formatting to distinguish these cells. Define separate cells for the objective function and each constraint function (the lefi-hand side of a constraint). Use descriptive labels directly above these cells. A Spreadsheet Model for Sklenka Skis Figure 13.1 shows a spreadsheet model for the SSC to make is given in cells B14 and C14, Also in the Mode! example. (Excel file Sklenka Skis already has the optimal section are calculations for the constraint functions, solution. Typically, you would start wth all decision variables equal to zero as shown in Figure 19.1). Weuse the *5 Yordanelle + 4 Deercrest (hours used in fabrication, principles of spreadsheet The engineering that we discussed ote in Chapter 2 to implement the model. The Data portion of 1 Jordanelle + 1.5 Deercrest (hours used in finishing, the spreadsheet provides the objective function coefficients, cellD16) Constraint coetficients, and right-hand sides of the model. | Such data should be kept separate from the actual model so eres ercecwte (mevkit mbsure, coll D1} that if any data are changed, the model will automatically be and the abjective function, 50 Jordanelle + 65 Deercrest Updated. In the Model section, the number of each product (cell D2) ‘To help you understand the correspondence between the mathematical model and the spreadsheet model more clearly, we will write the model in terms of formulas used in the spreadsheet cells, Maximize Profit = D22 = B9*B14 + CO*CI4 subject to the constraints DIS = BO*BI4 + C6*C14 < D6 (fabrication) D6 = B7*B14 + C7*C14 = D7 (finishing) D19 = Cl4 ~ 2*B14 = 0 (market mixture) Bl4 = 0,Cl4 = 0 (nonnegativity) La cara “3Chapter 13 Linear Optimization Rear aN asin cr optimization model 1, Explain the steps in developing a line 2. List the different categories of constraints that one might find in a linear optimization model. 3. What guidelines should you follow when implementing linear optimization models on spreadsheet oh Solving Linear Optimization Models To solve an optimization problem, we seek values of the decision variables that maximize or minimize the objective function and also satisfy all constraints. Any solution that satis- fies all constraints of a problem is called a feasible solution. Finding an optimal solution among the infinite number of possible feasible solutions to a’given problem is not an easy task. A simple approach is to try to manipulate the decision variables in the spreadsheet model to find the best solution possible; however, for many problems, it might be very dif ficult to find a feasible solution, let alone an optimal solution. You might try to find the best solution you can for the Sklenka Ski problem by using the spreadsheet model. With a litle experimentation and perhaps a bit of luck, you might be able to zero in on the optimal solu- tion or something close to it. However, to guarantee finding an optimal solution, some type of systematic mathematical solution procedure is necessary. Fortunately, such a procedure is provided by the Excel Solver tool, which we discuss next. { Solver is an add-in packaged with Excel that was developed by Frontline Systems, Inc.¢www.solver.com), and can be used to solve many different types of optimization problems. Solver can be found in the Analysis group under the Data tab in Excel. When Solver is invoked, the Solver Parameters dialog appears. You use this dialog to define the objective, decision variables, and constraints from your spreadsheet model within Solver. g Solver for the SSC Problem Figure 13.2 shows the completed Solver Parameters dialog for the SSC example. Define the objective function cell in, ‘the spreadsheet (022) in the Set Objective field. Either enter the cell reference or click within the field and then in the cell in the spreadsheet. Click the appropriate radio button for Max or Min. Decision variables (cells B14 and C14) are entered in the field called By Changing Variable Cells; click within this field and highlight the range corresponding to the decision variables in your spreadsheet. To enter a constraint, click the Add button. A new dialog, Add Constraint, appears (see Figure 13.3). In the leftfield, Cel! Reference, enter the cell that contains the constraint function (left-hand side of the constraint) For example, the constraint function for the fabrication constraint is in cell D15. Make sure that you select the correct type of constraint ( =, =, or =) in the drop-down ‘box in the middle of the dialog. The other options are discussed in the next chapter. In the right field, called Constraint, enter the numerical value of the right-hand side Of the constraint or the cell reference corresponding to it For the fabrication constraint, this is cell D6. Figure 13.3 shows the completed dialog for the fabrication constraint. To add other constraints, click the Add button. You may also define a group of constraints that all have the same algebraic form (all <, all =, or all =) and enter them together. For example, the department resource limitation Constraints are expressed within the spreadsheet model as 015 = 06 016 < D7 Because both constraints are = types, we could define them as a group by entering the range D15:D16 in the Call Reference field and D6:07 in the Constraint field to simplify the input process. When all constraints are added,Chapter 13. Linear Optimization 507 ‘Sinatra rb a hai Manor of abe Number of Fabrication Nonber of Fabrication _ Hours 84 — (3.5 x 5.25 + 4 x 105) = 23.625 Hours Used jours Unused * aval Available slack variables are always nonnegative, s0 for = 2 ‘constraints, slack represents the difference between the left-hand side of the constraint function and the right-hand side of the requirement. The slack on a binding constraint will always be zero. Graphical Interpretation of Linear Optimization with Two Variables We can easily illustrate optimization problems with two decision variables graphically “This can help you to better understand the properties of linear optimization models and the interpretation of the Solver output. Recall that a feasible solution is a set of values forthe decision variables that satisfy all ofthe constraints. Linear programs generally ave an infi- nite number of feasible solutions. We fist characterize the set of feasible solutions, often called the feasible region. We use the SSC model to illustrate this graphical approach: Maximize Total Profit = 50 Jordanelle + 65 Deererest 3.5 Jordanelle + 4 Deercrest = 84 1 Jordanelle + 1.5 Deercrest = 21 Deercrest ~ 2 Jordanelle = 0 Deercrest = 0 Jordanelle = 0 For a problem with only two decision variables, xj and x2, we eam draw the feasible mnal coordinate system. Let us begin by considering the simplest ‘model, namely, that the decision variables must be non- x1 = O corresponds to region on a two-dimensiot constraints in a linear optimization negative, These constrains are x, = O and x) = 0. The constra Figure 13.5 Iver Answer Report ™510 Chapter 13. Linear Optimization ‘Fishing Constraint Hf] aJordaneiies1 5 Deererest=21 9 10 M1 a2 19 a4 45 46 47 UR 19 20 22 22 2 26 25 4 Figure 13.8 Graph of the Finishing Constraint Identit The feasible region is the set of points that satisty all constraints simultaneously. From Figure 13.9, we see that the feasible region must be below the fabrication constraint line, below the finishing constraint line, to the left of the market mix constraint line, and, of course, within the first quadrant defined by the nonnegativity, constraints. This is shown by the triangular region in Figure 13.10. Notice that every point that satisfies the finishing constraint also satisfies the fabrication constraint. In this case, we say that the fabrication constraint is a redundant constraint because it does not impact the feasible region at all. Because our objective is to maximize profit, we seek ‘comer point that has the largest value of the objective function total profit = 50 Jordanelle + 65 Deercrest. ‘Note that if we set the objective function to any numerical value, we define a straight line. For example, if we set 50 Jordanelle + 65 Deercrest = 600, then any point on this line will have a total profit of $600. Figure 13.11 shows the dashed-jine graphs of the objective function for profit values of $600, $800, and $1,000. Notice that as the profit increases, the graph of the objective function moves in an upward direction. However, for a profit of $1,000, no points Bead serdanete ing the Feasible Region and Optimal Solution ‘on the line also pass through the feasible region. From the figure, then, we can conclude that the maximum profit must bbe somewhere between $800 and $1,000, We also see that as the profit increases, the last, ‘point in the feasible region that the profit lines will cross. is the comer point on the right side of the triangle, identified by the circle in Figure 13.11. This must be the optimal solution. This point is the intersection of the finishing and market mix constraint lines. We can find this ‘point mathematically by solving these constraint lines. simultaneously: 1 Jordanelle + 1.5 Deercrest = 21 Deercrest ~ 2 Jordanalle = 0 From the second equation, we have Deercrest = 2 Jordanelle; ‘substituting this into the first equation, we obtain 1 Jordanelle + 1.5(2 Jordanelle) = 21 4 Jordanelle = 21 Jordanelie = 5.25 ‘Then Deercrest = 25.25) = 10.5. This is exactly the solution that Solver provided.30 11 12 23 14 45 6 17 18 19 20 21 22 23 24 25 Jordanede 4 Figure 13.11 Identifying the Optimal Solution Compare the graphical interpretation of the solution to the SSC problem with the Solver Answer Report in Figure 13.5. Notice that Solver reported that both the finishing constraint and market mix constraint are binding. Graphically, this means that these con- straints intersect at the optimal solution. The fabrication constraint, however, is not bind- ing and has a positive value of slack because it does not intersect at the optimal solution. Slack can be interpreted as a measure of the distance from the optimal corner point to the nonbinding constraint. oO olelay Tap MaU eu 4. What is a feasible solution? 2. Explain how to use Solver to solve a linear optimization model on a spreadsheet. 3. What information is provided in the Solver Answer Report? 4. Explain how to graphically visualize linear optimization models with two variables.Chapter 13. Linear Optimization 513 J How Solver Works Solver uses a twathematical algorithm called the simplex method. which was developed in 1947 by the late Dr. George Dantzig. The simplex method characterizes feasible solutions algebraically by solving systems of linear equations. It moves systematically from one ‘comer point to another to improve the objective function until an optimal solution is found (or until the problem is deemed infeasible or unbounded), Because of the linearity of the constraints and objective function, the simplex method is guaranteed to find an optimal solution if one exists and usually does so quickly and efficiently. To gain some intuition into the logic of Solver, consider the following example. PECUEREROE Crebo Manufacturing Crebo Manufacturing produces four types of structural support fitings—plugs, rails, rivets, and clips—which are machined on two CNC machining centers. The machining centers have a capacity of 280,000 minutes per year. The and clips, respectively, to produce. The problem is to maximize gross margin = 0.3X; + 1.3X. + 0.75% + 1.2% ‘subject to the constraint that limits the machining capacity and nonnegativity of the variables: ‘gross margin per unit and machining requirements are provided in the table below. How many of each product should be made to maximize gross profit margin? To formulate this as a linear optimization model, define 1, Mo, Xs. and Xq 10 be the number of plugs, rails, rivets, 1%, + 2.5 Xp + 1.5 Xp + 2X = 280,000 Xi Xa Xs Xe = 0 Product lugs Gross margin/unit 0.90 Minutes/unit ‘To solve this problem, your first thought might be to choose the variable with the high- cest marginal profit. Because Xz has the highest marginal profit, you might try producing as tany rails as possible. Since each ral requires 2.5 minutes, the maximum number that can be produced is 280,000 /2.5 = 112,000, for a total profit of $1.3( 112,000) = $145,600. However, notice that each rail uses a lot more machining time than the other products. The best solution isn't necessarily the one with the highest marginal profit, but the one that pro- vides the highest total profit. Therefore, more profit might be reatized by producing a pro- portionately larger quantity ofa different product having a smaller marginal profit. This is the key insight. What the simplex method essentially does is evaluate the impact of constraints jn terms of their contribution to the objective function for each variable. For the simple ease Of only one constraint, the optimal (maximum) solution is found by simply choosing the ‘variable with the highest ratio of the objective coefficient to the con aint coetticient Solving the Crebo Manufacturing Model {nthe Crebo Manufacturing Model, compute the ratio of the gross margin/unit to the minutes per unit of machining capacity used, as shown in row 6 in Figure 13.12 (Excel fie Grebo Manufacturing Mode), These ratios can be interpreted as the marginal proit per unit of resource consumed. The highest ratio occurs for clips. If we produce the maximum number of clips, 280,000/2 = 140,000, the total profit is $1,20(140,000) = $168,000. The mathematics ats complicated with more constraints and requires ‘multiple iterations to systematically improve the solution.enapuer 19 Liear ponrnene a Solver Outcomes and Solution Messages Solving a linear optimization model can result in four possible outcomes: 1. a.unique optimal solution 2, alternative (multiple) optimal solutions 3. an unbounded solution 4, infeasibility Unique Optimal Solution When a model has a unique optimal solution, it means that there is exactly one solution that will result in the maximum (or minimum) objective. The solution to the SSC model is unique; there are no solutions other than producing 5.25 pairs of Jordanelle skis and 1055 pairs of Deercrest skis that result in the maximum profit of $945. We could see this graphically in Figure 13.11 because there is a unique corner point that lies on the objective function line at the optimal value of profit. Alternative (Multiple) Optimal Solutions If a model has alternative optimal solutions, the objective is maximized (or minimized) by more than one combination of decision variables, all of which have the same objective function value. Solver does not tell you when alternative solutions exist and reports only ‘one of the many possible alternative optimal solutions. However, you can use the Sensitiv- ity Report information to identify the existence of alternative optimal solutions. When any of the Allowable Increase or Allowable Decrease values for changing cells are zero, then alternative optimal solutions exist, although Solver does not provide an easy way to find them. th Alternative Optimal Solutions igh Rene A Model 0 ilustrate a model with alternative optimal solutions, uppose we change the objective function in the SSC nodel to Max 50 Jordanelle + 75 Deercrest. A sol btained using Solver is shown in Figure 13.13, producing 10 Jordanelle skis and 14 pairs of Deercrest skis and constraint ine. Thus, as the profit increases, you can see that the profit line must stop along the top boundary of the feasible region defined by the finishing constraint. Both comer points that are circled are optimal solutions, as is any point connecting them. Therefore, when altemative esulting in a profit of $1,050. However, notice that the optimal solutions exist, there actually are an infinite number riginal optimal solution also has the same objective of them; however, identifying them other than graphically inction value: profit = $60(6.25) + $75(10.6) = $1,060. requires some advanced analysis. This may be seen graphically in Figure 13.14. The ew objective function lines are parallel to the finishing ee Unbounded Solution 'A solution is unbounded if the value of the objective can be increased or decreased Figure 13.28 General Appliance Corpora- tion Solver Mode! Chapter 13 Linear Optimization 529 (oe) ‘The SUMPRODUCT function can be used for any two arrays as Tong as the dimensions are the same. Here, the function multiplies pairwise the cost coefficients in the range B6:E7 by the amounts shipped in the range B13:E14 and then adds the terms. In the model, we also use the SUM function in cells F13 and F14 to sum the amount shipped from each plant, and also in cells B15 to E15 to sum the total amount shipped to each distribution center. Multiperiod Production Planning Models Many linear optimization problems involve making decisions over a future time horizon. (One example is planning production. The basic decision is how much to produce in each time period to meet anticipated demand over each period. Although it might seem obvi- ous to simply produce to the anticipated level of sales, it may be advantageous to produce ‘more than needed in earlier time petiods when production costs may be lower and store the excess production as inventory for use in later time periods, thereby letting lower produc- tion costs offset the costs of holding the inventory. So the best decision is often not obvious. K&L Designs KL Designs is a home-based company that makes hand- painted jewelry boxes for teenage girls. Forecasts of sales for the next year are 150 in the autumn, 400 in the winter, ‘and 50 in the spring. Plain jewelry boxes are purchased ‘rom a supplier for $20. The cost of capital is estimated to >be 24% per year (or 6% per quarter}; thus, the holding cost per item is 0.06($20) = $1.20 per quarter. The company hires art students part-time to craft designs during the autumn, and they earn $5.50 per hour. Because of the high ‘demand for part-time help during the winter holiday season, labor rates are higher in the winter, and workers earn $7.00 pper hour. In the spring, labor is more difficutt to keep, and ‘the owner must pay $6.25 per hour to retain qualified help. Each jewelry box takes two hours to complete. How should production be planned over the three quarters to minimize the combined production and inventory-holding costs? ‘The principal decision variables are the number of jewelry boxes to produce during each of the three quarters. However, since we have the option of carying inventory to Other time periods, we must also define decision variables for the number of units to holdin inventory at the end of ‘each quarter. The decision variables are (Continued)