3. Collect the necessary parametric data Many, if not most, of the elements needed to model the system of interest are not under the control of the decision maker. For instance, in manufacturing systems, products must comply with detailed specifications, production processes follow fixed operating procedures, and financial aspects are strictly budgeted. These requirements are normally quantified by the people involved in those activities, such as engineering and accounting & finance. The analyst must collect this information. Any piece of information in the form of a constant quantity is called a parameter. A parameter is simply a numerical constant that specifies particular system attributes. Sometimes system requirements vary depending on certain other factors, in which case they are known as uncontrollable variables. 4. Formulate a model In LP, model formulation means expressing the objective and each of the constraints algebraically in terms of the decision variables and parameters. This is usually straightforward if the problem and the decision variables have been defined correctly. Difficulties in model formulation are typically a sign that something was amiss when defining the problem or the decision variables. Make sure steps 1 and 2 are complete and correct (coherent) before attempting to formulate a model. There may be several possible ways to model the same problem. Which way is best depends on what information the analyst wants to obtain from the analysis. It is advisable to begin with a relatively simple model at the outset and subsequently refine it if additional information is desired. 5. Solve the model Model solution in LP is computationally intensive and normally conducted by means of computer software. In this module, we will examine the graphical solution method to illustrate the basic concepts of LP. But the graphical method, although theoretically sound, is very limited in power and therefore practically useless for real-world applications. We will make use of Excel's Solver Add-In to illustrate a practical solution method. There are many software options available, however, all of which provide the same basic information regarding LP solutions. 6. Verify and Validate the model Model verification means ensuring that the model is computationally correct, that it calculates what it is supposed to. A model containing errors (of both omission and commission) is useless. Model validation means ensuring that the model is representationally correct, that it accurately reproduces the behavior of the real-world system being modeled. Verification deals with the internal consistency of the model while validation addresses its external (representational) correctness. In LP, verifying and validating a model can range from a simple inspection of the output to detailed comparisons of model results to the system's operational statistics. Here's a quick reference on the subject: Model V & V. 7. Analyze model output The computer provides the solution to the LP problem along with a sensitivity analysis. However, in LP the term solution means the optimal quantities the model assigns to the decision variables. The term value means the result obtained for the objective function with that optimal solution. The term optimal means the best possible value that complies with all problem constraints, one that maximizes or minimizes the value of the objective function. Sensitivity analysis consists of additional information provided by the model. This includes the opportunity costs (called shadow prices or dual prices) for all resources, the ranges in which these dual prices hold, and the range where the model solution remains valid if the objective function parameters (called objective function coefficients) were to change. Keep in mind that a model is an idealized representation of a real-world system and therefore the model solution is also an idealized result. In order to make effective use of model results, the next step must be performed. 8. Interpret model results Every model is a simplification of the actual system being analyzed. Thus model solutions must be interpreted in the light of real-world considerations that may deviate from the simplifying assumptions built into the model. One way of dealing with this is to work interactively with the model to assess the impact of different possible conditions on model results. A great deal can be learned about system behavior by experimenting with the model, without affecting the actual system. The insight thus gained can be extremely useful for managers in the implementation phase of the project as well as in control of operations. 9. Recommend a course of action Presentation of the findings concludes the LP modeling analysis. Terms Constraint — a restriction that must be observed (complied with) Controllable variable — another name for decision variable Decision variable — a quantity that is under the control of and chosen by the decision maker (or determined by a decision model such as LP) Dual price — a term somewhat synonymous with shadow price (there is a slight difference in how they are computed and interpreted, but they both represent the economic value of an additional unit of a resource; see Dual vs. Shadow Price) Important problem — a situation of significance that calls for a carefully reasoned solution Model validation — ensuring that the model adequately represents the object system Model verification — ensuring that the model is computationally correct Negative problem — situation that exists when a system is underperforming Objective — the system state or performance level intended to be attained Objective function — an algebraic equation that states the end one seeks to achieve Opportunity cost — loss of potential gain from other alternatives incurred by choosing one course of action Optimal — the best possible alternative that satisfies a set of constraints Optimal solution — a solution that yields the best possible value (either maximum or minimum) for a given objective function and set of constraints Parameter — a numerical constant defining some system attribute Performance gap — the difference between actual system performance and established standards Positive problem — a situation or set of circumstances that offers advantageous prospects Problem — a matter, situation or state of affairs requiring a solution Sensitivity analysis — a procedure that determines the effect on the model solution and the value of the objective function for small changes in model parameters; a technique that throws light on the degree of stability of a given solution when the model is slightly altered Shadow price — the opportunity cost (economic value forgone) of not having one additional unit of a particular resource; the maximum premium one would be willing to pay for an additional unit of some resource Solution — a set of values for the decision variables that is feasible (complies with all constraints) Symptom — a sign indicating the existence of some condition in a system Uncontrollable variable — a nonconstant quantity that defines some system attribute Urgent problem — a situation demanding prompt attention Value — the numerical quantity generated by the objective function for a given solution Page 2Example LP Problem
BANANA COMPUTER Banana Computer produces two models of personal digital devices (PDD): the Basic Banana and the deluxe version, the Top Banana. Both models use a critical component, the wireless communication chip (WCC), which is currently in short supply. Each PDD uses one WCC. Banana’s suppliers can guarantee delivery of only 1,000 WCCs per week. All other components and resources required for production of the PDDs are abundant and readily available. Banana’s marketing department has forecast product demand for the upcoming week, in units, as follows: Basic Banana Top Banana Maximum Demand 700 600 Minimum Demand 300 200 Banana’s accounting department has determined the direct costs for each product as $100 for the Basic Banana and $150 for the Top Banana. Current marketing strategy calls for sales pricing of $400 for the Basic Banana and $550 for the Top Banana. Naturally, Banana wishes to maximize the marginal contribution to profit of its total production. Company policy calls for meeting minimum demand forecasts while not exceeding expected maximum demand.
Try to solve the problem on your own first. Answers are provided on the next page. * The corner-point evaluation method calculates the value of the objective function at each corner point of the feasible region. For each corner point, plug its coordinates into the objective function and choose the highest overall Z. <<MP <<LP <<PREV NEXT>>
Page 3
Answers to Example Problem
1. Objective: Max profit (marginal contribution to profit) Constraints: WCC availability (1) Sales forecast: max demand (2), min demand (2) 2. Let BB = units of Basic Banana PDDs to be produced in the upcoming week TB = units of Top Banana PDDs to be produced in the upcoming week 3. Since the objective is to maximize marginal contribution to profit, we must first obtain the profit contribution margins of each product. Profit margins are defined as sales price – direct costs (or equivalently, unit revenue – unit cost): BB TB
4. Graphical model showing feasible region
5. The isoprofit line has a slope of -300/400 = -3/4. Since this is greater (less negatively inclined) than the WCC constraint line’s slope of -1 but less than the zero slope of the maximum demand constraint for the Top Banana, the optimal point is (400, 600), indicating that the optimal solution is BB = 400 units and TB = 600 units, yielding a value of $360,000 as the maximum profit. 6. Candidate corner point solutions — north & east points of feasible region BB TP Profit
7. Revised pricing solution: The revised isoprofit line now has a slope of -330/300 = -1.1, which is steeper than the WCC constraint line. This implies that the optimal solution is now (700, 300) with maximum profit = $321,000. BB TP Profit
8. Hypothetical pricing solution: The slope of the resulting isoprofit line is equal to the slope of the WCC constraint line. This means that when sliding the isoprofit line to the northeast, it would last touch (intersect) the feasible region not at a single corner point but throughout the line segment between the points (400, 600) and (700, 300). Consequently, there would be multiple optimal solutions to the problem: the two corner points just mentioned as well as any point lying on the line segment. The coordinates of these latter points are linear combinations of the coordinates of the two corner points at the ends of the line segment. BB TP Profit |