Constructing and Solving Linear Models

Which ones are suitable problems for linear programming? Look for these characteristics:

• A linear programming problem is an optimization problem. That means the question should ask for you to find a maximum or minimum, or the conditions when a maximum or a minimum occurs. Look for words like most, least, maximum, minimum, maximize, minimize, etc. in the problem.
• The problem must have a linear objective function. Your objective should be a linear combination of the variables. This means that you should be able to write the expression you are trying to optimize in the form ax + by.

  (Note that although we restrict ourselves to two-variable situations, linear programming can be used to solve situations with many variables. The catch is that you have to use different techniques to solve them; you can't solve a situation with more than two variables graphically.)

• A linear programming problem will also have some constraints that define a feasible region. You may not be able to tell whether the problem defines a valid feasible region until you start working on the problem; the region may be open-ended or there may be inconsistent constraints. If a situation like this occurs, it doesn't mean you've made the wrong decision about using linear programming; it just means that the situation as described has no solution. But before concluding that, double check the problem description. Have you understood all the constraints correctly? Are there any constraints implied but not stated explicitly (as non-negativity constraints often are, for instance)?

Now let's consider the problems posed.

1. Yes, linear programming might give you a solution to this. It is an optimization problem -- you are trying to minimize cost. It is linear -- the objective is a linear combination of two volumes of paint. And there are some constraints that look like they might define a feasible region. We can go ahead and formulate this into a linear model.

   You might be thinking that you could work this out more simply another way. You'd probably be right. This is a pretty simple problem and could be tackled in a number of ways. However for the point of the exercise, go ahead and do it using linear programming.

2. No, this is not a linear programming problem. Although we have two variables and some constraints, it is not an optimization problem. You don't need linear programming for this, just a bit of algebra. (You might like to demonstrate this to yourself by going ahead and solving it anyway.)
3. Yes, this is a linear programming problem. It is an optimization (we're looking for the most profit) with a linear objective (a linear combination of the number of cartons made to give the total profit) and constraints that appear to define a feasible region.
4. Yes, this is a linear programming problem. It is an optimization problem (maximize weight loss) with a linear objective (a linear combination of the number of minutes spent walking and swimming) within a set of constraints.
5. Yes, this is a linear programming problem. It is an optimization problem (minimize cost) with a linear objective (a linear combination of the mass of each of the two metals) within a set of constraints.
6. No, this is not a linear programming problem. Although it is an optimization problem (maximize area) within a set of constraints, the objective is not a linear since the area is the product of the two side lengths, not a linear combination of them.

Back to the questions