This section considers the important
topic of modeling problems with nonlinear objective functions.
When the functions are not concave (when maximizing), it is
necessary to use binary variables as part of the model. In
fact, this is an important application of integer programming.
Consider a 4-machine production system producing three products.
The machines are labeled A through D, and the products are
labeled P, Q and R. The table below gives the time required
in minutes for each unit of product on each of the four machines.
During a one week period, the machines each have 2400 minutes
of capacity.
Production times on machine (minutes)
|
P |
Q |
R |
Machine
A |
20 |
10 |
10 |
Machine
B |
12 |
28 |
16 |
Machine
C |
15 |
6 |
16 |
Machine
D |
10 |
15 |
0 |
The profit for sales of each product is a nonlinear function
of the amount sold. The table below shows profits as a function
of sales for the three products. In each case, up to
100 units can be sold. A number in a cell is the profit per
unit in the specified range.
Profit data for products
Profit/unit,
$ |
P |
Q |
R |
Sales
less than 30 |
60 |
40 |
20 |
Sales
between 30 and 60 |
45 |
60 |
70 |
Sales
between 60 and 100 |
35 |
65 |
20 |
When the unit profit is the same over a range of values, the
resulting function is called a piecewise linear function. The
functions are for the three products are illustrated below.
The profit function for P is said to be a concave function
because it the slope of the function decreases as the amount
sold increases. The function for Q is a convex function because
the slope is increasing as the amount increases. The function
for R is both convex and concave because the slope begins at
20, rises to 70 and then decreases again to 20. We will see
that the shape of the function has much to do with how it is
modeled. |
