PDF Linear Programming Models PDF

Activities/Assessments 1. Identify five applications of management science in various areas of a firm and illustrate its applications e.g. accounting, production. 2. Based on what you learned, what do you mean by Management Science? 3. Illustrate and explain each of the Management Sci...

Activities/Assessments 1. Identify five applications of management science in various areas of a firm and illustrate its applications e.g. accounting, production. 2. Based on what you learned, what do you mean by Management Science? 3. Illustrate and explain each of the Management Science Process. 4. Enumerate and explain each of the Management Science Techniques. 5. Illustrate and explain the relevance of management science in decision support system CHAPTER 2: LINEAR PROGRAMMING: MODEL FORMULATION, AND GRAPHICAL SOLUTION Overview Many major decisions faced by a manager of a business focus on the best way to achieve the objectives of the firm, subject to the restrictions placed on the manager by the operating environment. These restrictions can take the form of limited resources, such as time, labor, energy, material, or money; or they can be in the form of restrictive guidelines, such as a recipe for making cereal or engineering specifications. One of the most frequent objectives of business firms is to gain the most profit possible or, in other words, to maximize profit. When a manager attempts to solve a general type of problem by seeking an objective that is subject to restrictions, the management science technique called linear programming is frequently used. Learning Outcomes At the end of this chapter, students must be able to: 1. Understand and Analyze components and characteristics of the minimization and maximization model 2. Illustrate and discuss the graphical solutions of linear programming models COURSE MATERIALS Model Formulation A linear programming model consists of certain common components and characteristics. The model components include decision variables, an objective function, and model constraints, which consist of decision variables and parameters. Decision variables are mathematical symbols that represent levels of activity by the firm. The objective function is a linear mathematical relationship that describes the objective of the firm in terms of the decision variables. The objective function always consists of either maximizing or minimizing some value 9 The model constraints are also linear relationships of the decision variables; they represent the restrictions placed on the firm by the operating environment. The restrictions can be in the form of limited resources or restrictive guidelines. The actual numeric values in the objective function and the constraints, such as the 40 hours of available labor, are parameters. A Maximization Model Example Beaver Creek Pottery Company is a small crafts operation run by a Native American tribal council. The company employs skilled artisans to produce clay bowls and mugs with authentic Native American designs and colors. The two primary resources used by the company are special pottery clay and skilled labor. Given these limited resources, the company desires to know how many bowls and mugs to produce each day in order to maximize profit. This is generally referred to as a product mix problem type. Figure 2.1 Beaver Creek Pottery Company The two products have the following resource requirements for production and profit per item 10 produced (i.e., the model parameters): There are 40 hours of labor and 120 pounds of clay available each day for production. We will formulate this problem as a linear programming model by defining each component of the model separately and then combining the components into a single model. The steps in this formulation process are summarized as follows: Decision Variables The decision confronting management in this problem is how many bowls and mugs to produce. The two decision variables represent the number of bowls and mugs to be produced on a daily basis. The quantities to be produced can be represented symbolically as x1 = number of bowls to produce x2 = number of mugs to produce The Objective Function The objective of the company is to maximize total profit. The company’s profit is the sum of the individual profits gained from each bowl and mug. Profit derived from bowls is determined by multiplying the unit profit of each bowl, $40, by the number of bowls produced,. Likewise, profit derived from mugs is derived from the unit profit of a mug, $50, multiplied by the number of mugs produced, Model Constraints In this problem, two resources are used for production—labor and clay—both of which are limited. Production of bowls and mugs requires both labor and clay. For each bowl produced, 1 hour of labor is required. Therefore, the labor used for the production of bowls is 1x1 hours. Similarly, each mug requires 2 hours of labor; thus, the labor used to produce mugs every day is 11 2x2 hours. The total labor used by the company is the sum of the individual amounts of labor used for each product: 1x1 + 2x2 However, the amount of labor represented by the complete labor constraint is 1x1 + 2x2 ≤ 40 hr. The ―less than or equal to‖ (≤) inequality is employed instead of an equality (=) the 40 hours of labor is a maximum limitation that can be used, not an amount that must be used. This constraint allows the company some flexibility; the company is not restricted to using exactly 40 hours but can use whatever amount is necessary to maximize profit, up to and including 40 hours. This means that it is possible to have idle, or excess, capacity (i.e., some of the 40 hours may not be used). 3x2 The constraint for clay is formulated in the same way as the labor constraint. Because each bowl requires 4 pounds of clay, the amount of clay used daily for the production of bowls is pounds; and because each mug requires 3 pounds of clay, the amount of clay used daily for mugs is 4x1. Given that the amount of clay available for production each day is 120 pounds, the material constraint can be formulated as 4x1 + 3x2 ≤ 120 lb. A final restriction is that the number of bowls and mugs produced must be either zero or a positive value because it is impossible to produce negative items. The complete linear programming model for this problem can now be summarized as follows: The solution of this model will result in numeric values for x1 and x2, that will maximize total profit, Z As one possible solution, consider x1 = 5 bowls and x2 = 10 mugs, 1(5) + 2(10) ≤ 40 25 ≤ 40 4(5) + 3(10) ≤ 120 50 ≤120 Because neither of the constraints is violated by this hypothetical solution, we say the solution is feasible (i.e., possible). Substituting these solution values in the objective function gives Z = 40(5) + 50(10) = $700. However, for the time being, we do not have any way of knowing whether $700 is the maximum profit., Z = $40(10) + 50(20) = 400 + 1,000 12  = $1,400 Although this is certainly a better solution in terms of profit, it is infeasible (i.e., not possible) because it violates the resource constraint for labor: 1(10) + 2(20) 50 ≤/ 40 The solution to this problem must maximize profit without violating the constraints. The solu-tion that achieves this objective is x1 = 24 bowls and x2 = 8 mugs, with a corresponding profit of $1,360. The determination of this solution is shown using the graphical solution approach in thefollowing section. Graphical Solution of a Maximization Model The product mix model will be used to demonstrate the graphical interpretation of a linear programming problem. Recall that the problem describes Beaver Creek Pottery Company’s attempt to decide how many bowls and mugs to produce daily, given limited amounts of labor and clay. The complete linear programming model was formulated as Below is a set of coordinates for the decision variables x1 and x2 on which the graph of our model will be drawn. Note that only the positive quadrant is drawn (i.e., the quadrant where x1 and x2 will always be positive) because of the nonnegativity constraints, x1 ≥ 0 and x2 ≥ 0 Figure 2.2 Coordinates for graphical analysis 13 The first step in drawing the graph of the model is to plot the constraints on the graph. This is done by treating both constraints as equations (or straight lines) and plotting each line on the graph. Let’s consider the labor constraint line first: x1 + 2x2 = 40 A simple procedure for plotting this line is to determine two points that are on the line and then draw a straight line through the points. One point can be found by letting x1 = 0 and solving for x2: (0) + 2x2 = 40 x2 = 20 Thus, one point is at the coordinates x1 = 0, and x2 = 20. A second point can be found by letting x2 = 0 and solving for x1: x1 + 2(0) = 40 x1 = 40 Now we have a second point, x1 = 40, x2 = 0. The line on the graph representing this equation is drawn by connecting these two points. However, this is only the graph of the constraint line and does not reflect the entire constraint, which also includes the values that are less than or equal to (≤) this line. The area representing the entire constraint is shown below. Figure 2.3 Graph of the labor constraint line 14 Figure 2.4 The labor constraint area To test the correctness of the constraint area, we check any two points—one inside the constraint area and one outside. For example, check point A in Figure 2.4, which is at the intersection of x1 = 10 and x2 = 10. Substituting these values into the following labor constraint, 10 + 2(10) ≤ 40 30 ≤ 40 hr. shows that point A is indeed within the constraint area, as these values for x1 and x2, yield a quantity that does not exceed the limit of 40 hours. Next, we check point B at x1 = 40 and x2 = 30: 15  40 + 2(30) ≤ 40 100 ≠ 40 hr. Point B is obviously outside the constraint area because the values for x1 and x2 yield a quantity (100) that exceeds the limit of 40 hours. We draw the line for the clay constraint the same way as the one for the labor constraint— by finding two points on the constraint line and connecting them with a straight line. First, let x1 = 0 and solve for x2: 4(0) + 3x2 = 120 x1 = 30 This operation yields a second point, x1 = 30, x2 = 0. Plotting these points on the graph and connecting them with a line gives the constraint line and area for clay, as shown below: Figure 2.5 The constraint area for clay Combining the two individual graphs for both labor and clay produces a graph of the model constraints, as shown in below. The shaded area is the area that is common to both model constraints. Therefore, this is the only area on the graph that contains points (i.e., values for x1 and x2) that will satisfy both constraints simultaneously. For example, consider the points R, S, and T. Point R satisfies both constraints; thus, we say it is a feasible solution point. Point S satisfies the clay constraint (4x1 + 3x2 ≤ 120) but exceeds the labor constraint; thus, it is infeasible. Point T satisfies neither constraint; thus, it is also infeasible. The shaded area is referred to as the feasible solution area because all the points in this area satisfy both constraints. Some point within this feasible solution area will result in maximum profit for Beaver Creek Pottery Company. The next step in the graphical solution approach is to locate this point. 16 Figure 2.6 Graph of both model constraints Figure 2.7 The feasible solution area constraints The Optimal Solution Point The second step in the graphical solution method is to locate the point in the feasible solution area that will result in the greatest total profit. To begin the solution analysis, we first plot the objective function line for an arbitrarily selected level of profit. For example, if we say profit, Z, is $800, the objective function is $800 = 40xG1 + 50x2 A portion of trhe objective function line for a profit of $1,200 is outside the feasible solution area, but part of the line remains within the feasible area. Therefore, this profit line indicates that there are feasible solution points that give a profit greater than $800. Now let us increase 17 profit again, to $1,600. This profit line, also shown in Figure 2.9, is completely outside the feasible solution area. The fact that no points on this line are feasible indicates that a profit of $1,600 is not possible. Figure 2.8 Objective function line for Z = $800 Figure 2.9 Alternative objective function lines for profit, Z, of $800, $1,200, and $1,600 We can see from Figure 2.9 that profit increases as the objective function line moves away from the origin (i.e., the point x1 = 0, and x2 = 0). Given this characteristic, the maximum profit will be attained at the point where the objective function line is farthest from the origin and is still touching a point in the feasible solution area. This point is shown as point B. Point B is referred to as the optimal (i.e., best) solution. The Solution Values The third step in the graphical solution approach is to solve for the values of x1 and x2 once the optimal solution point has been found. The graphical coordinates corresponding to point B are x1 = 24 and x2 = 8. This is the optimal solution for the decision Figure 2.10 Identification of optimal solution point 18 Figure 2.11 Optimal solution coordinates variables in the problem. However, unless an absolutely accurate graph is drawn, it is frequently difficult to determine the correct solution directly from the graph. A more exact approach is to determine the solution values mathematically once the optimal point on the graph has been determined. The mathematical approach for determining the solution is described in the following pages. First, however, we will consider a few characteristics of the solution. These corners (points A, B, and C) are protrusions, or extremes, in the feasible solution area; they are called extreme points. It has been proven mathematically that the optimal solution in a linear programming model will always occur at an extreme point. Slack Variables Once the optimal solution was found at point B simultaneous equations were solved to determine the values of x1 and x2. Recall that the solution occurs at an extreme point where constraint equation lines intersect with each other or with the axis. Thus, the model constraints are considered as equations (=) rather than (≥) or (≤) inequalities. 19 There is a standard procedure for transforming ≤ inequality constraints into equations. This transformation is achieved by adding a new variable, called a slack variable, to each constraint. In the clay constraint, 5 bowls and 10 mugs require only 50 pounds of clay. This leaves 70 pounds of clay unused. Thus, x2 represents the amount of unused clay. In general, slack variables represent the amount of unused resources. The ultimate instance of unused resources occurs at the origin, where x1 = 0 and x2 = 0. Substituting these values into the equations yields. x1 + 2x2 + s1 = 40 0 + 2(0) + s2 = 40 s1 = 40 hr. labor and 4x1 + 3x2 + s2 = 120 4(0) + 3(0) + s2 = 120 s2 = 120 lb. of clay The complete linear programming model can be written in what is referred to as standard form with slack variables as follows: The solution values, including the slack at each solution point, are summarized as follows: Figure 2.12 shows the graphical solution of this example, with slack variables included at each solution point 20 Summary of the Graphical Solution Steps The steps for solving a graphical linear programming model are summarized here: 1. Plot the model constraints as equations on the graph; then, considering the inequalities of the constraints, indicate the feasible solution area. 2. Plot the objective function; then, move this line out from the origin to locate the optimal solution point. 3. Solve simultaneous equations at the solution point to find the optimal solution values. Or 2. Solve simultaneous equations at each corner point to find the solution values at each point. 3. Substitute these values into the objective function to find the set of values that results in the maximum Z value. Graphical Solutions of Linear Programming Models The graphical method is realistically limited to models with only two decision variables,which can be represented on a graph of two dimensions. Models with three decision variablescan be graphed in three dimensions,but the process is quite cumbersome,and models of four ormore decision variables cannot be graphed at all. Irregular Types of Liner Programming Models For some linear programming models, the general rules do not always apply. There are several special types of atypical linear programming problems. Although these special cases do not occur frequently, they will be described so that you can recognize them 21 when they arise. These special types include problems with more than one optimal solution, infeasible problems, and problems with unbounded solutions. 1. Multiple Optimal Solutions  Multiple optimal solutions provide greater flexibility to the decision maker 2. An Infeasible Problem  has no feasible solution area; every possible solution point violates one or more constraints. 3. An Unbounded Problem  In this type of problem, the objective function can increase indefinitely without reaching a maximum value Characteristics of Linear Programming Problems 1. A linear programming problem requires a choice between alternative courses of action or a decision. The decision is represented in the model by decision variables. 2. The problem encompasses an objective that the decision maker wants to achieve. The two most frequently encountered objectives for a business are maximizing profit and minimizing cost. 3. In a linear programming problem, restrictions exist, making unlimited achievement of the objective function impossible. Example of which are limited resources, such as labor or material. Properties of Linear Programming Models In addition to encompassing only linear relationships, a linear programming model also has several other implicit properties:  The term linear not only means that the functions in the models are graphed as a straight line; it also means that the relationships exhibit proportionality which means the slope of a constraint or objective function line is constant.  The terms in the objective function or constraints are additive.  The values of decision variables are continuous or divisible.  All model parameters are assumed to be known with certainty. Activities/Assesments 1. Identify five situations in business for each minimization and maximization linear programming techniques and discuss how these two could be useful to such situations. 2. Discuss the components and characteristics of maximization and minimization model. 3. Enumerate and explain the Graphical Solution Steps. 22