24.03 Constraints and objective functions (Extended)

As we saw in the previous lesson, many real-world problems involve constraints on a set of resources. These constraints give us a set of possible combinations for the resources, which we call the feasible region.

Any one of these combinations may be viable, but we often consider things like cost of production, or profit to inform us of which exact combination(s) are most suitable to either reduce the cost, or to maximise the profit.

An objective function is a function of the constraint variables, and typically indicates a cost or profit. For instance, let $x$x and $y$y indicate the amount of flour and sugar in kilograms respectively. If flour costs $\$1.05$$1.05 per kg, and sugar costs $\$1.65$$1.65 per kg, then the cost, $z$z, of the ingredients is:

$z=1.05x+1.65y$z=1.05x+1.65y

Linear programming problems involve maximising or minimising an objective function over the feasible region. This section investigates only identifying the objective function.

Worked example

Example 1

Define the constraints and objective function for the following problem:

A recycling company that has two types of waste bins available for purchase. The Bin-it bin costs $\$100$$100 each, the Fill-it-up bin costs twice as much, and the total available for purchases is $\$1400$$1400.

The Bin-it bins take up $6$6 m² of factory yard space and can hold $8$8 m³ of recyclable waste. The more expensive bins take up $8$8 m² of space but can hold $12$12 m³ of waste. The yard is fairly small, confined to $72$72 m² of useable area.

Think: We are given three types of information:

1. the cost of each type of waste bin.
2. the factory yard space of each type of waste bin.
3. the volume of waste of each type of waste bin.

Note that each scenario has the 'type of waste bins' in common. Therefore, we first want to identify these constraint variables.

So let $x$x be the number of Bin-it bins, and $y$y be the number of Fill-it-up bins.

Then using the available budget, and space, we want to identify a set of inequalities that describe the constraints. From there we want to construct an objective function, one that gives the total waste storage (in cubic metres) in terms of $x$x and $y$y.

It is often helpful to group the given information into relevant categories:

Type of waste bin	Variable	Cost $(\$)$($)	Yard space ( m2 )	Volume of waste ( m3 )
Bin-It	$x$x	$100$100	$6$6	$8$8
Fill-it-up	$y$y	$200$200	$8$8	$12$12
Totals		$\le$≤ $1400$1400	$\le$≤ $72$72	$?$?

 

Do: We can now form our inequalities.

To buy $x$x Bin-it bins, the cost would be $\$100x$$100x, and to buy $y$y Fill-it-up bins the cost would be $\$200y$$200y. The total cost of $x$x Bin-it bins and $y$y Fill-it-up bins would be the sum $100x+200y$100x+200y, and this must not exceed our limit of $\$1400$$1400.

So the first constraint is given by $100x+200y\le1400$100x+200y≤1400.

Secondly, yard space is limited. Buying $x$x Bin-it bins will take up $6x$6x m² of yard space and $y$y Fill-it-up bins will take up $8y$8y m² of yard space with a maximum space of $72$72 m^2.

Another constraint is given by $6x+8y\le72$6x+8y≤72.

Finally, the quantities $x$x and $y$y cannot be negative numbers. We can write these constraints as $x\ge0$x≥0 and $y\ge0$y≥0. These last constraints are not contained in the problem explicitly, but they should be included when considering realistic solutions.

So in summary the constraints are listed in the table:

$100x+200y\le1400$100x+200y≤1400	(1)
$6x+8y\le72$6x+8y≤72	(2)
$x\ge0$x≥0	(3)
$y\ge0$y≥0	(4)

The problem also asks for an objective function, one that describes the total waste storage. If we call the total storage $S$S, then since $x$x Bin-it bins store $8x$8x m³, and $y$y Fill-it-up bins store $12y$12y m³, then we can write:

$S=8x+12y$S=8x+12y

Reflect: It would be ideal to find the values of $x$x and $y$y that maximise the value of the storage space $S$S, but still satisfies the constraints. This is called a linear programming problem, and will be touched on in the following chapter.

 

Practice questions

Question 1

Question 2

Question 3