5. The Fundamental Assumptions of Linear Programming
Now that you have seen how some simple problems can be formulated
and solved as linear programs, it is useful to reconsider the
question of when a problem can be realistically represented as
a linear programming problem. A problem can be realistically represented
as a linear program if the following assumptions hold:
- The constraints and objective function are linear.
- This requires that the value of the objective function and
the response of each resource expressed by the constraints is
proportional to the level of each activity expressed in
- Linearity also requires that the effects of the value of
each variable on the values of the objective function and the
constraints are additive. In other words, there can be
no interactions between the effects of different activities; i.e.,
the level of activity X1 should not affect
the costs or benefits associated with the level of activity X2.
- Divisibility -- the values of decision variables
can be fractions. Sometimes these values only make sense if they
are integers; then we need an extension of linear programming
called integer programming.
- Certainty -- the model assumes that the responses
to the values of the variables are exactly equal to the responses
represented by the coefficients.
- Data -- formulating a linear program to solve a problem
assumes that data are available to specify the problem.