Chapters 2 and 3 examined the basic types of structures that appear in formulations of linear programs—allocation, covering, blending, and network models. Not every application of linear programming can be classified as one of those four types, but most applications resemble one or more of them. In this chapter, we look at a type of linear program that has a special application and a special kind of interpretation. This type is associated with Data Envelopment Analysis, or DEA. For classification purposes, the DEA model is essentially an allocation model, but its unique applications make it an important type of model to study in its own right.
As the examples in Chapters 2 and 3 indicated, linear programming is typically used as an ex ante tool in planning, that is, as an aid in choosing among alternative possible courses of action. In DEA, linear programming is used as an ex post tool, to evaluate performance that has already been observed. Compared to other linear programming applications, DEA is a relative newcomer. The first articles on the methodology began appearing in the mid-1970s, and researchers have been elaborating the theory ever since. As recognition of DEA has spread, the technique has been applied in a variety of settings, such as public schools, courts of law, hospitals, oil and gas production, vehicle maintenance, and banking.