|
The Problem
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.
|
