Constructing and Solving Linear Models

For the solution applets shown, drag the white dot to change the scale to see the whole feasible region.

1. A painter can use either Ludux or Bautman paint for a job that involves painting 44 square metres of wall. Allowing for two coats, the Ludux will cover 6 square metres per litre and the Bautman will cover 7.5 square metres per litre. The paint can be bought in bulk for $7 per litre (Ludux) and $8.50 per litre (Bautman). How much of each paint should the painter buy to minimize cost, and how much will it cost?

There is only one constraint apart from the implied non-negativity constraints. The amount of paint must be enough to cover at least 44 square metres. Thus, using x to represent the number of litres of Ludux and y to represent the number of litres of Bautman,

The objective is to minimize cost, given by

The applet shows the problem set up. It is a minimization problem, so the objective approaches the feasible region from below. Note that even though the feasible region is unbounded above, the problem has a solution because it is a minimization problem and because of the non-negativity constraints. The solution is to buy 5.9 litres of Bautman at a cost of $50.20.

Also note that the objective line is nearly parallel to the constraint line. This suggests that there is not much difference between either extreme. In fact if you slide the red dot down the objective line you find a cost of $50.40 for buying Ludux. (This is actually out a bit because of rounding errors in the applet). In a real world problem you would probably conclude that this was not enough difference to worry about, and you would buy whichever was most convenient.

Of course the simplest way to do this problem is to work out what it would cost to use each of the paints and choose the cheaper. You wouldn't normally use linear programming to solve something with only one constraint.

2. How many bags of flour should a bakery order so as to be able to bake 200 loaves and 300 rolls a day for the next week, if it takes 500g of flour for each loaf and 150g for each roll and a bag of flour contains 20kg?

As noted earlier, this is not a linear programming problem.

3. Nubbles, a small snack food company, has to decide how many of each of two types of health bar to manufacture. They make $35 profit on a carton of nutty bars, and $16 profit on a carton of open sesame bars. The factory uses a 2-stage process to make open sesame bars, and it takes two minutes for a carton of bars to be processed by each stage. This means the maximum production of open sesame bars is 15 cartons an hour. Nutty bars, however, use a 3-stage process with each stage again taking two minutes. This means the maximum production but nutty is 10 cartons per hour. The same equipment is used for both bars, so the number of cartons of each type is restricted by the constraint 2 x the number of open sesame cartons + 3 x the number of nutty may not exceed 30 per hour. In addition, management has a policy that the number of cartons of nutty bars should be no more than three times the number of open sesame bars. Assuming that all bars made will be sold, what combination of bars gives the most profit?

The objective is to maximize profit. If we use x to represent the number of cartons of nutty bars per hour and y to represent the number of cartons of open sesame bars per hour, we can represent the profit function as

The first constraint is that we can have no more than 15 cartons of nutty bars an hour.

Next, the limit on the number of cartons of open sesame bars per hour:

Third the total production constraint:

(Actually, the third constraint also takes care of both of the first two. If you click constraint 3 in the applet, you'll see that clicking constraints 1 and 2 don't reduce the feasible region any further, so they could be safely left out. They are redundant constraints.)

Finally, the constraint that the number of nutty bars is no more than three times the number of open sesame bars. Initially we would write this as x ≤ 3y, then rearrange it as

Does the applet look like what you constructed? If not, make sure you understand the construction of the problem, then go back to the question now and have another go before reading on.

It is a maximization problem, so we move the objective line down from above. The applet gives the solution as a profit of $402.80 per hour when 10 cartons of nutty bars and 3.3 of open sesame bars are made per hour.

4. In order to try to lose some weight I have decided to either walk or swim. I'm going to spend at least 20 minutes a day on exercise, but I'm not a good enough swimmer to swim for more than 45 minutes. If I shed 2g of fat for each minute I spend swimming but only 1g of fat for each minute I spend walking, how long should I walk and swim to lose the most weight?

The objective is to maximize weight loss. If we use x to represent the number of minutes walking and y to represent the number minutes swimming, we can represent the weight loss in grams of fat as

The first constraint is that the total minutes of exercise must be at least 20:

The next constraint is that we can have no more than 45 minutes swimming:

But now we have a problem. Because it is a maximization problem we need to start above the feasible region, but because there is no upper bound on walking, the objective function has no maximum, and the problem has no solution. (You'll need to adjust the scale of the applet to see this.)

Actually, it should be clear that the problem lies with the way the problem is stated. It's not feasible for there to be no upper limit to the number of minutes spent walking each day. There are only 1,440 minutes in a day, there must be an upper limit ... and you'd assume that I might need some time for other activities, too, like work, sleep, meals, etc. The best way to answer a question like this is to say that "the problem, as stated, has no solution."

5. A firm that manufactures metal components for the maritime industry has a commission to cast a component that can be made of either of two metals, angstide or beranium, or any combination of them. There is 17kg of angstide available at a cost of $43.50 per kilogram, while only 15.5kg of beranium is available at a cost of $32 per kilogram. The component must have a finished weight of at least 18kg. The foundry can handle volumes up to 100 decilitres. 1kg of angstide occupies 3.5 decilitres and 1kg of beranium occupies 6 decilitres. What amounts of the two metals should be used to minimize cost? What is the minimum cost?

The objective is to minimize cost. If we use x to represent the number of kilograms of angstide and y to represent the number kilograms of beranium, we can represent the cost function as

The first constraint is that we can have no more than 17kg of angstide available.

Next, the limit on the beranium is 15.5kg:

Third the total mass must be at least 18kg:

Finally, the limit on the volume the foundry can handle:

It is a minimization problem so we start with the objective below the feasible region.

The applet shows the solution at 3.3kg of angstide and 14.7kg of beranium giving a total cost of $614.

6. A neighbour of mine keeps a sheep in her yard. If she wants to make a rectangular pen using her fence as one side and some or all of a 20 metre roll of wire mesh to make the other three sides, what length sides should she use to give the maximum area for the pen. The fence is only 18m long, and her yard only extends 6m away from the fence.

As noted earlier, this is not a linear programming problem.

Back to questions