Let’s begin our study of LP with an example of an important class of problems known as the product mix problem. This exercise follows Prof. Norman Pendegraft’s original, published in his article Lego of My Simplex on ORMS Today 24:1, p. 8, February 1997.
Example Problem: Lego Tables and Chairs
S. Claus & Company, the renowned North Pole enterprise, manufactures tables and chairs from Lego blocks for worldwide distribution. A table can be assembled from two large blocks (yellow) and two small blocks (blue). A chair requires one large block and two small blocks, as illustrated below: The marginal contributions to profit for tables and chairs are $16 and $10, respectively. Assume that demand for Claus’s Lego products is virtually unlimited and that all other production resources are plentiful and available. For the upcoming production run, Claus has six large blocks and eight small blocks in components inventory, as shown below:
Determine the product mix (i.e., the number of tables and chairs to be produced) for the upcoming production run such that total contribution to profit is maximized. (Claus is actually a nonprofit enterprise. All proceeds are donated to charitable causes.)
Before modeling this problem, you may wish to try solving it on your own. It should not be too hard since this is, after all, a toy problem. To solve the problem with LP, let’s follow the steps discussed previously. Note that Step 0 (recognizing the problem) has already been done by virtue of the problem statement. In the real world, the analyst should prepare (or obtain) a written problem statement analogous to the one above prior to embarking on problem modeling.
1. Define the Problem
LP problem definition requires the specification of two basic elements: an objective and a set of constraints. Objective: maximize total contribution to profit Comments: The assumption that demand is “virtually unlimited” means there is no demand constraint for this problem. In general, market demand imposes a constraint on production: produce no more than can be sold. By the same token, all other resources necessary for production are assumed to be plentiful and therefore yield no constraints for this model.
2. Define the Decision Variables
Put yourself in the position of the production manager: What decision is required from the manager so that production can begin? Clearly, the production staff must be told how many units to assemble of each product. Once they know that, production can begin. Thus, Let x = number of tables to be assembled (in the upcoming production run) In mathematics, variables represent unknown quantities. Initially, we don’t know how many tables and chairs should be assembled. But by using variables, we can model and solve the problem. The solution to the problem consists of the values that will be determined by LP for each of the decision variables. LP will be able to find the optimal solution if we are successful in formulating a correct model, which is the next step.
3. Collect the Necessary Data The problem statement for this example included the data: the parameters. In the real world, the analyst must obtain the data. 4. Formulate a Model
LP model formulation basically consists of expressing the objective and each constraint algebraically in terms of the decision variables: 4A. Objective Function
The stated objective is to maximize total contribution to profit. Claus generates its profit from two products: tables and chairs. Thus, the total profit contribution must equal the sum of profits derived from tables plus the profits obtained from chairs. That is to say, we know that the objective function must have two terms, and that they are summed. Consider first the contribution to profit due to tables. Each table contributes $16 to profit. Claus will produce x tables, where x is still to be determined. Consequently, the contribution to profit due to x tables is 16x , in dollars. Analogously, the profit contribution due to chairs is 10y. Finally, the total profit contribution is the sum of these two terms. Therefore, the objective function is:
Max 16x + 10y It is common practice to express the objective as a formal equation. Creating a new variable Z to stand for total profit contribution, we have:
Max Z = 6x + 10y Either expression is accepted as valid in LP formulations. Note that Z is not a decision variable, which are independent variables, but a dependent variable added to the model for convenience. Dependent variables depend on other (independent) variables for their values — in this case, Z = ƒ ( x , y ). Independent variables have their values assigned independently by the decision maker (or by LP).
Note: Since Z is a dependent variable, it is not usually defined formally, as was the case with the decision variables.
continued
