Instructional Materials for BUMA 20103: Management Science PDF

Republic of the Philippines POLYTECHNIC UNIVERSITY OF THE PHILIPPINES Office of the Vice President for Academic Affairs College of Business Administration INSTRUCTIONAL MATERIALS FOR BUMA 20103: MANAGEMENT SCIENCE...

Republic of the Philippines POLYTECHNIC UNIVERSITY OF THE PHILIPPINES Office of the Vice President for Academic Affairs College of Business Administration INSTRUCTIONAL MATERIALS FOR BUMA 20103: MANAGEMENT SCIENCE COMPILED BY: Dr. Leopoldo Francisco Bragas Dr. Roy Angelo Pobre Prof. Jennifer Munsayac Prof. Perry David Solosa Prof. Michelle Lasundin PUP A. Mabini Campus, Anonas Street, Sta. Mesa, Manila 1016 Direct Line: 335-1730 | Trunk Line: 335-1787 or 335-1777 local 000 Website: www.pup.edu.ph | Email: [email protected] THE COUNTRY’S 1st POLYTECHNICU  INTRODUCTION This instructional material provides learning on the course Management Science. This course pertains to the application of mathematical models and computing technology to help decision makers solve problems. This also includes the technological advances used by businesses and organizations for solving problems. The topics in this course include:  Introduction to Management Science  Linear Programming: Model Formulation  and Graphical Solution  Linear Programming : Computer Solution and Sensitivity Analysis  Linear Programming: Modeling Examples  Integer Programming  Transportation, Transshipment & Assigned Problems  Network Flow Models  Project Management  Multicriteria Decision Making  Nonlinear Programming  Probability and Statistics  Decision Analysis  Queuing Analysis  Simulation Management science is a recognized and established discipline in business. The applications of management science techniques are widespread, and they have been frequently credited with increasing the efficiency and productivity of business firms. The students are expected to read and understand the topics, answer all the activities and assessments at the end of each lesson, and accomplish the Midterm and Final Examination attached at the latter part of this instructional material. i  TABLE OF CONTENTS INTRODUCTION........................................................................................................................ i COURSE OUTCOMES.............................................................................................................. v CHAPTER 1: MANAGEMENT SCIENCE............................................................................ 1 Management Science Definition and Process......................................................................... 1 Model Building: Break-even Analysis...................................................................................... 4 Management Science Modeling Techniques.......................................................................... 6 Business Usage of Management Science Techniques........................................................... 7 Management Science Models in Decision Support Systems.................................................. 8 Activities/Assessments........................................................................................................... 9 CHAPTER 2: LINEAR PROGRAMMING: MODEL FORMULATION, AND GRAPHICAL SOLUTION 9 Model Formulation.................................................................................................................. 9 Graphical Solution of a Maximization Model..........................................................................13 Graphical Solutions of Linear Programming Models..............................................................21 Irregular Types of Liner Programming Models.......................................................................21 Characteristics of Linear Programming Problems..................................................................22 Activities/Assesments............................................................................................................22 CHAPTER 3: LINEAR PROGRAMMING: COMPUTER SOLUTION AND SENSITIVITY ANALYSIS 23 Computer Solution.................................................................................................................23 Sensitivity Analysis................................................................................................................29 Activities/Assesments............................................................................................................42 CHAPTER 4: LINEAR PROGRAMMING: MODELING EXAMPLES..................................43 A Product Mix Example.........................................................................................................43 A Marketing Example............................................................................................................49 Activities/Assesments............................................................................................................54 CHAPTER 5: INTEGER PROGRAMMING........................................................................55 Integer Programming Models................................................................................................55 Computer Solution of Integer Programming Problems with Excel and QM for Windows........59 Activities/Assesments............................................................................................................66 CHAPTER 6: TRANSPORTATION, TRANSSHIPMENT, AND ASSIGNMENT PROBLEMS...67 ii  The Transportation Model......................................................................................................67 The Transshipment Model.....................................................................................................76 The Assignment Model..........................................................................................................80 Activities/Assesments............................................................................................................83 CHAPTER 7: NETWORK FLOW MODELS.......................................................................85 Network Components............................................................................................................85 The Shortest Route Solution Approach..................................................................................87 The Minimal Spanning Tree Problem....................................................................................95 The Maximal Flow Problem...................................................................................................96 Activities/Assesments..........................................................................................................102 CHAPTER 8: PROJECT MANAGEMENT.......................................................................104 The Elements of Project Management.................................................................................104 CPM/PERT..........................................................................................................................111 Project Crashing and Time–Cost Trade-Off.........................................................................130 Formulating the CPM/PERT Network as a Linear Programming Model...............................134 Activities/Assesments..........................................................................................................142 CHAPTER 9: MULTI CRITERIA DECISION MAKING......................................................143 Goal Programming..............................................................................................................143 Graphical Interpretation of Goal Programming.....................................................................148 Computer Solution of Goal Programming Problems with QM for Windows and Excel..........151 Scoring Model with Excel Solution.......................................................................................166 Activities/Assesments..........................................................................................................167 CHAPTER 10: NONLINEAR PROGRAMMING..................................................................167 Nonlinear Profit Analysis.....................................................................................................168 Solution of Nonlinear Programming Problems with Excel....................................................174 Activities/Assesments..........................................................................................................184 CHAPTER 11: PROBABILITY AND STATISTICS............................................................185 Types of Probability.............................................................................................................185 Fundamentals of Probability................................................................................................186 Statistical Independence and Dependence..........................................................................190 Expected Value...................................................................................................................197 The Normal Distribution.......................................................................................................199 Activities/Assesments..........................................................................................................210 CHAPTER 12: DECISION ANALYSIS...............................................................................210 Components of Decision Making.........................................................................................211 iii  Decision Making Without Probabilities.................................................................................212 Activities/Assesments..........................................................................................................242 CHAPTER 13: QUEUING ANALYSIS...............................................................................242 Elements of Waiting Line Analysis.......................................................................................243 The Single-Server Waiting Line System..............................................................................243 The Single-Server Model.....................................................................................................245 Finite Queue Length............................................................................................................256 Finite Calling Population......................................................................................................259 The Multiple-Server Waiting Line.........................................................................................262 Activities/Assesments..........................................................................................................267 CHAPTER 14: SIMULATION.............................................................................................268 The Monte Carlo Process....................................................................................................268 Computer Simulation with Excel Spreadsheets...................................................................274 Simulation of a Queuing System..........................................................................................279 Continuous Probability Distributions....................................................................................282 Statistical Analysis of Simulation Results.............................................................................288 Verification of the Simulation Model.....................................................................................297 Activities/Assesments..........................................................................................................298 APPENDICES.........................................................................................................................299 GRADING SYSTEM...............................................................................................................301 REFERENCES.......................................................................................................................302 MIDTERM EXAMINATION.....................................................................................................303 FINAL EXAMINATION..........................................................................................................304 iv  COURSE OUTCOMES At the end of the semester, the students will be able to:  Illustrate and discuss the Management Science Process  Understand and Apply the Management Science Modeling and Computing Techniques  Evaluate the implication of the results of applied management science models to business efficiency and profitability  Create mathematical modeling and computing techniques to solve various business problems v CHAPTER 1: MANAGEMENT SCIENCE Overview Management science can be defined as the application of a scientific techniques in solving various kinds of phenomena or problems which cannot be easily understood by way of simple approaches. Its application is widespread to include problems in the military and even for such complex problems that need to be simplified through modelling technique to make it easily understood so as to institute much reliable solution through the use of some mathematical equations. Thus solutions are credible and reliable hence it relies on data using mathematical formulas. The applications of management science techniques are widespread, and they have been frequently credited with increasing the efficiency and productivity of business firms. Management science (also referred to as operations research, quantitative methods, quantitative analysis, and decision sciences) is part of the fundamental curriculum of most programs in business. Learning Outcomes At the end of this chapter, students must be able to: 1. Define management science 2. Illustrate and discuss the process of management science 3. Appreciate the importance of break-even analysis 4. Differentiate management science modelling techniques 5. Apply the different management science techniques 6. Appreciate and discuss the business usage of management science 7. Illustrate and explain the relevance of management science in decision support system COURSE MATERIALS Management Science Definition and Process Management science encompasses a logical, systematic approach to problem solving, which closely parallels what is known as the scientific method for attacking problems. It follows a generally recognized and ordered series of steps: (1) observation (2) definition of the problem (3) model construction (4) model solution (5) implementation of solution results. 1 Observation The first step in the management science process is the identification of a problem that exists in the system (organization). The person who normally identifies a problem is the manager because managers work in places where problems might occur. Figure 1.1 The management science process However, problems can often be identified by a management scientist, a person skilled in the techniques of management science and trained to identify problems, who has been hired specifically to solve problems using management science techniques. Definition of the Problem Once it has been determined that a problem exists, the problem must be clearly and concisely defined. Because the existence of a problem implies that the objectives of the firm are not being met in some way, the goals (or objectives) of the organization must also be clearly defined. A stated objective helps to focus attention on what the problem actually is. Model Construction A management science model is an abstract representation of an existing problem situation. It can be in the form of a graph or chart, but most frequently a management science model consists of a set of mathematical relationships. These mathematical relationships are made up of numbers and symbols. As an example, consider a business firm that sells a product. The product costs $5 to produce and sells for $20. A model that computes the total profit that will accrue from the items sold is Z = $20x - 5x x represents the number of units of the product that are sold, and Z represents the total profit that results from the sale of the product. The symbols x and Z are variables. The term variable is used because no set numeric value has been specified for these items. Z is a dependent variable because its value is dependent on the number of units sold; x is an independent variable because the number of units sold is not dependent on anything else (in this equation). The numbers $20 and $5 in the equation are referred to as parameters. Parameters are constant values that are generally coefficients of the variables (symbols) in an equation. 2 Parameters usually remain constant during the process of solving a specific problem. The parameter values are derived from data (i.e., pieces of information) from the problem environment. The equation as a whole is known as a functional relationship (also called function and relationship). The term is derived from the fact that profit, Z, is a function of the number of units sold, x, and the equation relates profit to units sold. Let us assume that the product is made from steel and that the business firm has 100 pounds of steel available. If it takes 4 pounds of steel to make each unit of the product, we can develop an additional mathematical relationship to represent steel usage: 4x = 100 lb. of steel This equation indicates that for every unit produced, 4 of the available 100 pounds of steel will be used. Now our model consists of two relationships: Z = $20x - 5x 4x = 100 The profit equation in this new model is an objective function, and the resource equation is a constraint. In other words, the objective of the firm is to achieve as much profit, Z, as possible, but the firm is constrained from achieving an infinite profit by the limited amount of steel available. To signify this distinction between the two relationships in this model, we will add the following notations: maximize Z = $20x - 5x subject to 4x = 100 This model now represents the manager’s problem of determining the number of units to produce. You will recall that we defined the number of units to be produced as x. Thus, when we determine the value of x, it represents a potential (or recommended) decision for the manager. Therefore, x is also known as a decision variable. The next step in the management science process is to solve the model to determine the value of the decision variable. Model Solution A management science solution technique usually applies to a specific type of model. Thus, the model type and solution method are both part of the management science technique. We are able to say that a model is solved because the model represents a problem. When we refer to model solution, we also mean problem solution. Note, however, that the value of the decision variable does not constitute an actual decision; rather, it is information that serves as a recommendation or guideline, helping the manager make a decision. Some management science techniques do not generate an answer or a recommended decision. Instead, they provide descriptive results: results that describe the system being modeled. 3 For example, suppose the business firm in our example desires to know the average number of units sold each month during a year. The monthly data (i.e., sales) for the past year are as follows: Monthly sales average 40 units (480 ÷ 12). This result is not a decision; it is information that describes what is happening in the system. The results of the management science techniques in this text are examples of the two types shown in this section: (1) solutions/decisions and (2) descriptive results. Implementation The final step in the management science process for problem solving described in Figure 1.1 is implementation. Implementation is the actual use of the model once it has been developed or the solution to the problem the model was developed to solve. Frequently the person responsible for putting the model or solution to use is not the same person who developed the model, and thus the user may not fully understand how the model works or exactly what it is supposed to do. Individuals are also sometimes hesitant to change the normal way they do things or to try new things. If the management science model and solution are not implemented, then the effort and resources used in their development have been wasted. Model Building: Break-even Analysis Break-Even Analysis In this section we will continue to explore the process of building and solving management science models, using break-even analysis, also called profit analysis. Break-even analysis is a modeling technique to determine the number of units to sell or produce that will result in zero profit. The break-even point gives a manager a point of reference in determining how many units will be needed to ensure a profit. Components of Break-Even Analysis The three components of break-even analysis are volume, cost, and profit. Volume is the level of sales or production by a company. It can be expressed as the number of units (i.e., quantity) produced and sold, Two type of costs are typically incurred in the production of a product: fixed costs and variable costs. Fixed costs are generally independent of the volume of units produced and sold. That is, fixed costs remain constant, regardless of how many units of product are produced within a given range. Fixed costs can include such items as rent on plant 4 and equipment, taxes, staff and management salaries, insurance, advertising, depreciation, heat and light, and plant maintenance. Taken together, these items result in total fixed costs. Variable costs are determined on a per-unit basis. Thus, total variable costs depend on the number of units produced. Variable costs include such items as raw materials and resources, direct labor, packaging, material handling, and freight. Total variable costs are a function of the volume and the variable cost per unit. This relationship can be expressed mathematically as Total variable cost = vcv where cv = variable cost per unit and v = volume (number of units) sold The total cost of an operation is computed by summing total fixed cost and total variable cost, as follows: total cost = total fixed cost + total variable cost TC = cf + vcv Where cf = fixed cost The third component in our break-even model is profit. Profit is the difference between total revenue and total cost. Total revenue is the volume multiplied by the price per unit, total revenue = vp where p = price per unit Now that we have developed relationships for total revenue and total cost, profit (Z) can be computed as follows: The break-even volume can be determined using the following formula: Sensitivity Analysis This relationship enables us to see how the level of profit (and loss) is directly affected by changes in volume. However, when we developed this model, we assumed that our parameters, fixed and variable costs and price, were constant. In reality such parameters are frequently uncertain and can rarely be assumed to be constant, and changes in any of the parameters can affect the model solution. The study of changes on a management science model is called sensitivity analysis—that is, seeing how sensitive the model is to changes. Sensitivity analysis can be performed on all management science models in one form or another. In fact, sometimes companies develop models for the primary purpose of 5 experimentation to see how the model will react to different changes the company is contemplating or that management might expect to occur in the future. Management Science Modeling Techniques Two of the five steps of the management science process - model construction and solution are the two steps that use the management science techniques. The techniques presented in this text can be loosely classified into four categories The term programming used to identify this technique does not refer to computer programming but rather to a predetermined set of mathematical steps used to solve a problem. This particular class of techniques holds a predominant position in this text because it includes some of the more frequently used and popular techniques in management science. In general, linear programming models help managers determine solutions (i.e., make decisions) for problems that will achieve some objective in which there are restrictions, such as limited resources or a recipe or perhaps production guidelines. Manufacturing companies develop linear programming models to help decide how many units of different products they should produce to maximize their profit (or minimize their cost), given scarce resources such as capital, labor, and facilities. Probabilistic Techniques Probabilistic techniques are distinguished from mathematical programming techniques in that the results are probabilistic. Mathematical programming techniques assume that all parameters in the models are known with certainty. Therefore, the solution results are assumed to be known with certainty, with no probability that other solutions might exist. A technique that assumes certainty in its solution is referred to as deterministic. In contrast, the results from a probabilistic technique do contain uncertainty, with some possibility that alternative solutions might exist. An example of a probabilistic technique is decision analysis, decision analysis, it is shown how to select among several different decision alternatives, given uncertain (i.e., probabilistic) future 6 conditions. For example, a developer may want to decide whether to build a shopping mall, build an office complex, build condominiums, or not build anything at all, given future economic conditions that might be good, fair, or poor, each with a probability of occurrence. Network Techniques Networks consist of models that are represented as diagrams rather than as strictly mathematical relationships. As such, these models offer a pictorial representation of the system under analysis. These models represent either probabilistic or deterministic systems. a network is drawn that shows the relationships of all the tasks and activities for a project, such as building a house or developing a new computer system. This type of network can help a manager plan the best way to accomplish each of the tasks in the project so that it will take the shortest amount of time possible. Other Techniques The analytical hierarchy process (AHP) easily classified. It is a mathematical technique for helping the decision maker choose between several alternative decisions, given more than one objective; however, it is not a form of linear programming, as is goal programming. Simulation, probably the single most unique topic in the text. It has the capability to solve probabilistic and deterministic problems and is often the technique of last resort when no other management science technique will work. In simulation, a mathematical model is constructed (typically using a computer) that replicates a real-world system under analysis, and then that simulation model is used to solve problems in the ―simulated‖ real-world system. In general, historical sales and demand data are used to build a mathematical function or formula that can be used to estimate product demand in the future. Business Usage of Management Science Techniques Not all management science techniques are equally useful or equally used by business firms and other organizations. Some techniques are used quite frequently by business practitioners and managers; others are used less often. The most frequently used techniques are linear and integer programming, simulation, network analysis (including critical path method/project evaluation and review technique [CPM/PERT]), inventory control, decision analysis, and queuing theory, as well as probability and statistics. An attempt has been made in this text to provide a comprehensive treatment of all the topics generally considered within the field of management science, regardless of how frequently they are used. Although some topics may have limited direct applicability, their study can reveal informative and unique means of approaching a problem and can often enhance one’s understanding of the decision-making process. The variety and breadth of management science applications and of the potential for applying management science, not only in business and industry but also in government, health care, and service organizations, are extensive. Areas of application include project planning, capital budgeting, production planning, inventory analysis, scheduling, marketing planning, quality control, plant location, maintenance policy, personnel management, and product demand forecasting, among others. 7 Management Science Models in Decision Support Systems Historically, management science models have been applied to the solution of specific types of problems; for example, a waiting line model is used to analyze a specific waiting line system at a store or bank. A decision support system (DSS) is a computer-based system that helps decision makers address complex problems that cut across different parts of an organization and operations. A DSS is normally interactive, combining various databases and different management science models and solution techniques with a user interface that enables the decision maker to ask questions and receive answers. In its simplest form any computer-based software program that helps a decision maker make a decision can be referred to as a DSS. Alternatively, enterprise-wide DSSs can encompass many different types of models and large data warehouses, and they can serve many decision makers in an organization. They can provide decision makers with interrelated information and analyses about almost anything in a company. A DSS can be primarily a data-oriented system, or it can be a model-oriented system. A new type of DSS, called an online analytical processing system, or OLAP, focuses on the use of analytical techniques such as management science models and statistics for decision making. A desktop DSS for a single user can be a spreadsheet program such as Excel to develop specific solutions to individual problems. On the other end of the DSS spectrum, an enterprise resource planning (ERP) system is software that can connect the components and functions of an entire company. It can transform data, such as individual daily sales, directly into information that supports immediate decisions in other parts of the company, such as ordering, manufacturing, inventory, and distribution. A large-scale DSS such as an ERP system in a company might include a forecasting model to analyze sales data and help determine future product demand; an inventory model to determine how much inventory to keep on hand; a linear programming model to determine how much material to order and product to produce, and when to produce it; a transportation model to determine the most cost-effective method of distributing a product to customers; and a network flow model to determine the best delivery routes. All these different management science models and the data necessary to support them can be linked in a single enterprise wide DSS that can provide many decisions to many different decision makers. 8 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 CHAPTER 3: LINEAR PROGRAMMING: COMPUTER SOLUTION AND SENSITIVITY ANALYSIS Overview The application of linear proramming methods in business operation is a tough activity, because of its approach which is too mathematical. Since this is so essential, more so that there is too much competition now in every corner of the business everyone need to devise measures by which to make their decision highly efficient to generate greater profitability. Each and every manager must learn quantititive methods in decision making to make them effective in crafting business decisions especially in regards to profitability. Linear programming technique is one of the best mathematical methods that can aid the manager come up with good decisions. However, the rigor involved in using this method requires adoption of a much easier and reliable way of generating solutions for problems involving maximization and minimization conditions. Thus computer solutions for this method is highly sought to make computations much easier and reliable. In this chapter, we will show how linear programming problems can be solved using several personal computer software packages. We will also describe how to use a computer solution result to experiment with a linear programming model to see what effect parameter changes have on the optimal solution, referred to as sensitivity analysis. Learning Outcomes At the end of this lesson. Students must be able to: 1. Apply computer solutions such as Excel Spreadsheet and QM for windows 2. Apply analysis of parameter changes and their effects on model solution COURSE MATERIALS Computer Solution When linear programming was first developed in the 1940s, virtually the only way to solve a problem was by using a lengthy manual mathematical solution procedure called the simplex method. As computer technology evolved, the computer was used more and more to solve linear programming models. The mathematical steps of the simplex method were simply programmed in prewritten software packages designed for the solution of linear programming problems. The ability to solve linear programming problems quickly and cheaply on the computer, regardless of the size of the problem, popularized linear programming and expanded its use by businesses. As a result of the easy and low-cost availability of personal computers and linear programming software, the simplex method has become less of a focus in the teaching of linear programming. In the next few sections, we demonstrate how to solve linear programming problems by using Excel spreadsheets and QM for Windows, a typical general-purpose quantitative methods software package. 23 Excel Spreadsheets Excel can be used to solve linear programming problems, although the data input requirements can be more time-consuming and tedious than with a software package like QM for Windows that is specifically designed for the purpose. A spreadsheet requires that column and row headings for the specific model be set up and that constraint and objective function formulas be input in their entirety, as opposed to just the model parameters, as with QM for Windows. However, this is also an advantage of spreadsheets, in that it enables the problem to be set up in an attractive format for reporting and presentation purposes. In addition, once a spreadsheet is set up for one problem, it can often be used as a template for others. The values for bowls and mugs and for profit are contained in cells B10, B11, and B12, respectively. These cells are currently empty or zero because the model has not yet been solved. The objective function for profit, =C4*B10+D4*B11, is embedded in cell B12 shown in bar. This formula is essentially the same as Z = 40x1 + 50x2, where B10 and B11 represent x1 and Exhibit 3.1 x2, and B12 equals Z. The objective function coefficients, 40 and 50, are in cells C4 and D4. Similar formulas for the constraints for labor and clay are embedded in cells E6 and E7. For example, in cell E6 we input the formula =C6*B10+D6*B11. The < = signs in cells F6 and F7 are for cosmetic purposes only; they have no real effect. To solve this problem, first click on the ―Data‖ tab on the toolbar at the top of the screen and then click on ―Solver‖ on the far right side of the Data toolbar. The window Solver Parameters will appear, as shown in Exhibit 3.2. Initially all the windows on this screen are blank, and we must input the objective function cell, the cells representing the decision variables, and the cells that make up the model constraints. When inputting the Solver parameters as shown in Exhibit 3.2, we first ―Set Objective:‖ which is B12 for our example. (Excel automatically inserts the $ sign next to cell addresses; you should not type it in.) Next we indicate that we want to maximize the objective by clicking on ―Max.‖ We achieve our objective by changing cells B10 and B11, which represent our model decision variables. The designation ―B10:B11‖ means all the cells between B10 and B11, inclusive. We next input our model constraints by clicking on ―Add,‖ which will access the screen shown in Exhibit 3.3. 24 Exhibit 3.3 shows our labor constraint. Cell E6 contains the constraint formula for labor whereas cell G6 contains the labor hours available (i.e., 40). We continue to add constraints until the model is complete. Note that we could have input our constraints by adding a single constraint formula, E6:E7 < = G6:G7, which means that the constraints in cells E6 and E7 are less than or equal to the values in cells G6 and G7, respectively. It is also not necessary to input the nonnegativity constraints for our decision variables, B10:B11 > = 0. This can be done in the Solver Parameters screen (Exhibit 3.2). Click on ―OK‖ on the Add Constraint window after all constraints have been added. This will return us to the Solver Parameters screen. There are two more necessary steps before proceeding to solve the problem. On the Solver Parameters screen, check where it says, ―Make Unconstrained Variables Non-Negative,‖ and where it says ―Select a Solving Method,‖ select ―Simplex LP.‖ This will ensure that Solver uses the simplex procedure to solve the model and not some other numeric method (which Excel has available). Exhibit 3.2 Exhibit 3.3 Once the complete model is input, click on ―Solve‖ at the bottom of the Solver Parameters screen (Exhibit 3.2). First, a screen will appear, titled Solver Results, which will provide you with the opportunity to select the reports you want and then when you click on ―OK,‖ the solution screen shown in Exhibit 3.4 will appear. 25 If there had been any extra, or slack, left over for labor or clay, it would have appeared in column H on our spreadsheet, under the heading ―Left Over.‖ In this case, there are no slack resources left over. When you click on ―OK‖ from the Solver screen, the intermediate Solver Results screen provides an opportunity for you to select several reports, including the answer report, shown in Exhibit 3.5. This report provides a summary of the solution results. QM for Windows Before demonstrating how to use QM for Windows, we must first make a few comments about the proper form that constraints must be in before a linear programming model can be solved with QM for Windows. The constraints formulated in the linear programming models presented in Chapter 2 and in this chapter have followed a consistent form. All the variables in the constraint have appeared to the left of the inequality, and all numerical values have been on the right-hand side of the inequality. For example, in the pottery company model, the constraint for labor is x1 + 2x2