 New Zealand
Level 8 - NCEA Level 3

Linear Programming - Applications

Lesson

Some big ideas in optimisation were developed during and soon after the second world war. The new field came to be known as Linear Programming.

Significant contributors to it were Leonid Kantorovich in 1939 and George Dantzig in 1946 and 1947. Initially, the Linear Programming formulation had mainly military applications but it is now recognised as a tool with many commercial uses to do with finding the best ways to allocate available resources.

In this chapter, we consider some simple examples.

Example 1

Suppose a manufacturer can make two kinds of product and there is a strong demand for both types. The profit that can be made on the first type is $\$50$$50 per unit and on the second type, it is \40$$40 for each unit. Clearly, the total profit $P$P depends on the numbers of the two types of product that are produced and the unit profit on each product. We express this algebraically as

$P=50m+40n$P=50m+40n

where $m$m and $n$n are the respective numbers of the two products.

In other circumstances, this profit function might be a cost function or a revenue function or a time function or a function giving some other useful quantity as its output. In general, it is called the objective function.

To maximise the objective function in the case we are considering, it might seem that the correct course of action is to produce as many as possible of the more profitable product and none of the other type. But, usually, there will be constraints of various kinds that restrict what can actually be done and which make some combination of the two products a better option.

For example, suppose the work is done in $7$7-hour shifts. It takes $27$27 minutes to produce each unit of the more profitable product, and it takes $19$19 minutes to make each unit of the other type. At the end of the shift, there are to be no partially completed units.

A simple calculation shows that it would be possible to complete, at most, $15$15 of the more profitable product but there would be $15$15 minutes left unused in the shift. Perhaps it would be better to produce just $14$14 of this type, leaving $42$42 minutes remaining in the shift which could be used for making $2$2 units of the second type.

Thus, referring to the objective function, we could have $m=15$m=15 and $n=0$n=0, so that

$P=50\times15+40\times0=750$P=50×15+40×0=750

or, we could have $m=14$m=14 and $n=2$n=2, so that

$P=50\times14+40\times2=780.$P=50×14+40×2=780.

Clearly, the second option is better.

The constraints in the process are expressed as inequalities. The constraints need to involve the same variables as occur in the objective function. In the example above, the time constraints would be expressed

$27m+19n\le420$27m+19n420.

The numbers of the two products produced are each at least zero. So, we can write $m\ge0$m0 and $n\ge0$n0 as two further constraints.

Other constraints will arise due to limited supplies of raw materials, labour, transport or other factors.

As a result, only a certain set of values for the variables $m$m and $n$n is possible. On a graph, this set appears as an area bounded by lines. This region of possible values is a convex polygonal shape, usually called the feasible region. Any point whose coordinates $(m,n)$(m,n) lie outside the feasible region is said to be infeasible.

We might calculate the value of the objective function for the points $(m,n)$(m,n) in the feasible region, looking for the optimal solution. This would take a very long time were it not for the fact that

the optimal solution is always at a vertex of the feasible region.

Thus, the problem reduces to that of finding the intersections of the lines forming the boundary of the feasible region and then testing those points by substitution into the objective function.

Example 2

A hotel and conference centre at a holiday destination can cater for a maximum of $540$540 tourists and conference attendees per month but does not open for business in any month in which the number of bookings is less than $300$300. The number of tourist bookings is always greater than the number of conference attendees but never more than twice as many.

The profit made per tourist per month is $\$16$$16 while the profit made per conference attendee per month is \19$$19. What mix of conference attendees and tourists should the centre aim for to maximise the profit and what is the maximum profit?

The steps to be carried out in the optimisation process are:
• Define the variables.
• Construct the objective function.
• Write the constraints in the form of a system of linear inequalities.
• Draw the graphs.
• Find the vertices of the feasible region.
• Test for the optimum vertex, and write a conclusion.

Let $c$c be the number of conference attendees and $t$t be the number of tourists. If $P$P is the total profit, then the objective function can be written $P=19c+16t$P=19c+16t.

The constraints are:

$c+t\le540$c+t540           (maximum number of bookings)
$c+t\ge300$c+t300          (minimum bookings in order to open)
$t>c$t>c
$t\le2c$t2c
$t\ge0$t0, $c\ge0$c0

The graph of these inequalities looks as follows: To find the vertices of the feasible region we consider the intersecting boundary lines in pairs.

$t=2c$t=2c and $c+t=540$c+t=540 gives $c=180$c=180 and $t=360$t=360.

$t=2c$t=2c and $c+t=300$c+t=300 gives $c=100$c=100 and $t=200$t=200.

$t=c$t=c and $c+t=540$c+t=540 gives $c=t=270$c=t=270.

$t=c$t=c and $c+t=300$c+t=300 gives $c=t=150$c=t=150.

We now substitute each vertex point into the objective function $P=19c+16t$P=19c+16t to find the maximum value for $P$P.

 $19\times180+16\times360$19×180+16×360 $=$= $9180$9180 $19\times100+16\times200$19×100+16×200 $=$= $5100$5100 $19\times270+16\times270$19×270+16×270 $=$= $9450$9450 $19\times150+16\times150$19×150+16×150 $=$= $5250$5250

The profit is maximised when there are $270$270 conference attendees and $270$270 tourists. The profit is then $\$9470$$9470. Worked Examples Question 1 A television manufacturer makes rear-projection and plasma televisions. The profit per unit is \75$$75 for the rear-projection televisions and $\$150$$150 for the plasma televisions. 1. Let xx be the number of rear-projection televisions sold in a month and yy be the number of plasma televisions sold in a month. Write the objective function that models the total monthly profit zz. 2. The manufacturer is bound by the following constraints: 1. Equipment in the factory allows for making a maximum of 150150 rear-projection televisions in one month. 2. Equipment in the factory allows for making a maximum of 300300 plasma televisions in one month. 3. The cost to manufacture per unit is \400$$400 for the rear-projection televisions, and $\$300$$300 for the plasma televisions. Total monthly costs cannot exceed \120000$$120000.

Express the three constraints as inequalities:

1. $\editable{}\le\editable{}$
2. $\editable{}\le\editable{}$
3. $\editable{}\le\editable{}$
3. Graph the region defined by the inequalities $x\le150$x150, $y\le300$y300 and $400x+300y\le120000$400x+300y120000 in the first quadrant:

4. The region of possible solutions that you graphed in part (c) has been sketched more clearly below:

Evaluate the objective function for total monthly profit at each of the corners of the region. Give your answer to the nearest dollar.

Points Total Monthly Profit (dollars)
$\left(0,0\right)$(0,0) $\editable{}$
$\left(0,300\right)$(0,300) $\editable{}$
$\left(75,300\right)$(75,300) $\editable{}$
$\left(150,200\right)$(150,200) $\editable{}$
$\left(150,0\right)$(150,0) $\editable{}$
5. Use the region of possible solutions graphed above to help you determine the maximum monthly profit and the coordinates of the point it occurs on:

The maximum monthly profit is $\editable{}$ dollars at the point $\left(\editable{},\editable{}\right)$(,).

Question 2

Oliver is opening a new cross-state shipping company. He has the option to buy semi-trailer trucks or box trucks. To help in his decision, Oliver analyzed the following data:

• The annual maintenance cost should not exceed $\$562500$$562500. • The total payload had to be at least 300300 tons. • Only 3030 semi-trailer trucks are available. Semi-Trailer Truck Box Truck Annual maintenance cost \12500$$12500 $\$11250$$11250 Payload 2020 tons 33 tons 1. The average profit made by a semi-trailer truck is \12000$$12000 per year and the average profit made by a box trucks is $\$1300013000 per year. Find how many of each type of truck Oliver has to buy in order to maximize his annual profit.

The maximum annual profit is $\editable{}$ dollars, if Oliver buys $\editable{}$ semi-trailer trucks and $\editable{}$ box trucks.

Question 3

Food and clothing are shipped to survivors of a hurricane. Each box of food will feed $4$4 people, while each box of clothing will help $6$6 people. Each $1.0$1.0 m3 box of food weighs $5$5 kg and each $0.6$0.6 m3 box of clothes weighs $8$8 kg. The planes transporting food and clothing are bound by the following constraints:

• The total weight per plane cannot exceed $2000$2000 kg, and the total volume must be less than $300$300 m3.
1. How many boxes of food and how many boxes of clothing should be sent with each plane shipment to maximize the number of people that are helped?

$\editable{}$ boxes of food and $\editable{}$ boxes of clothing should be sent to help $\editable{}$ people.

Outcomes

M8-4

Use curve fitting, log modelling, and linear programming techniques

91574

Apply linear programming methods in solving problems