After gathering data for a linear programming model, the next step in the formulation process is to

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

After gathering data for a linear programming model, the next step in the formulation process is to

After gathering data for a linear programming model, the next step in the formulation process is to

After gathering data for a linear programming model, the next step in the formulation process is to


Page 2

After gathering data for a linear programming model, the next step in the formulation process is to

Example LP Problem

 

After gathering data for a linear programming model, the next step in the formulation process is to

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.

1. Define Banana Computer’s personal digital devices production problem.

2. Define the decision variables for this problem.

3. Formulate the problem as a linear programming (LP) model.

4. Sketch the LP model using the graphical method.

5. Determine the optimal solution using the isoprofit line approach.

6. Verify the optimal solution using the corner-point evaluation method.*

7. Determine the optimal solution if the price of the Basic Banana is raised to $430 while the Top Banana’s is lowered to $450.

8. Determine the optimal solution if the Basic Banana's price were $400 while the Top Banana's were $450.

9. Use Excel’s Solver to determine the optimal solutions under all pricing schemes.

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

After gathering data for a linear programming model, the next step in the formulation process is to


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
Price                $400       $550
Cost                  100         150
Profit margin    $300       $400

The LP model is therefore:

Max Z = 300 BB + 400 TB


  st               BB +        TB  ≤ 1000
                   BB                 ≤   700
                                  TB  ≤   600
                   BB                 ≥   300
                                  TB  ≥   200
                   BB, TB ≥ 0

4.  Graphical model showing feasible region

After gathering data for a linear programming model, the next step in the formulation process is to

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
300    600    $330,000
400    600    $360,000      optimal solution
700    300    $330,000
700    200    $290,000

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
300    600    $279,000
400    600    $312,000
700    300    $321,000      revised optimal solution
700    200    $291,000

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
300    600    $270,000
400    600    $300,000     Alternate Optimal Solution #1
700    300    $300,000     Alternate Optimal Solution #2
700    200    $270,000