Linear Programming - Applications

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+19n≤420.

The numbers of the two products produced are each at least zero. So, we can write $m\ge0$m≥0 and $n\ge0$n≥0 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+t≤540           (maximum number of bookings)
$c+t\ge300$c+t≥300          (minimum bookings in order to open)
$t>c$t>c
$t\le2c$t≤2c
$t\ge0$t≥0, $c\ge0$c≥0

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

Question 2

Question 3