Chapter 2

Linear Programming: Allocation, Covering, and Blending Models

The linear programming model is a very rich context for examining business decisions. A large variety of applications has been reported in the 50 years or so that computers have been available for this type of decision support. Our first task in this chapter is to describe the features of linearity in optimization models. We then begin our survey of linear programming models. Appendix 2 provides a graphical perspective on linear programming. This material may help with an understanding of the linear programming model, but it is not essential for proceeding with spreadsheet-based approaches.

The term linear refers to properties of the objective function and the constraints. A linear function exhibits proportionality, additivity, and divisibility. Proportionality means that the contribution from any given decision variable to the objective grows in proportion to its value. When a decision variable doubles, then its contribution to the objective also doubles. Additivity means that the contribution from one decision is added to (or sometimes subtracted from) the contributions of other decisions. In an additive function, we can separate the contributions that come from each decision variable. Divisibility means that a fractional decision variable is meaningful. When a decision variable involves a fraction, we can still interpret its significance for managerial purposes.