The chess set problem: description

To illustrate the model development and solving process we shall take a very small example.

A joinery makes two different sizes of boxwood chess sets. The smaller size requires 3 hours of machining on a lathe and the larger only requires 2 hours, because it is less intricate. There are four lathes with skilled operators who each work a 40 hour week. The smaller chess set requires 1 kg of boxwood and the larger set requires 3 kg. However boxwood is scarce and only 200 kg per week can be obtained.

When sold, each of the large chess sets yields a profit of $20, and one of the small chess set has a profit of $5. The problem is to decide how many sets of each kind should be made each week to maximize profit.

A first formulation

Within limits, the joinery can vary the number of large and small chess sets produced: there are thus two decision variables (or simply variables) in our model, one decision variable per product. We shall give these variables abbreviated names:

The number of large and small chess sets we should produce to achieve the maximum contribution to profit is determined by the optimization process. In other words, we look to the optimizer to tell us the best values of small, and large.

The values which small and large can take will always be constrained by some physical or technological limits: they may be constrained to be equal to, less than or greater than some constant. In our case we note that the joinery has a maximum of 160 hours of machine time available per week. Three hours are needed to produce each small chess set and two hours are needed to produce each large set. So the number of hours of machine time actually used each week is 3·small+ 2·large. One constraint is thus:

which restricts the allowable combinations of small and large chess sets to those that do not exceed the lathe-hours available.

In addition, only 200 kg of boxwood is available each week. Since small sets use 1 kg for every set made, against 3 kg needed to make a large set, a second constraint is:

where the left hand side of the inequality is the amount of boxwood we are planning to use and the right hand side is the amount available.

The joinery cannot produce a negative number of chess sets, so two further non-negativity constraints are:

In a similar way, we can write down an expression for the total profit. Recall that for each of the large chess sets we make and sell we get a profit of $20, and one of the small chess set gives us a profit of $5. The total profit is the sum of the individual profits from making and selling the small small sets and the large large sets, i.e.

Profit is the objective function, a linear function which is to be optimized, that is, maximized. In this case it involves all of the decision variables but sometimes it involves just a subset of the decision variables. In maximization problems the objective function usually represents profit, turnover, output, sales, market share, employment levels or other `good things'. In minimization problems the objective function describes things like total costs, disruption to services due to breakdowns, or other less desirable process outcomes.

The collection of variables, constraints and objective function that we have defined are our model. It has the form of a Linear Programming problem: all constraints are linear equations or inequalities, the objective function also is a linear expression, and the variables may take any non-negative real value.