Engineering Optimization

12Linear Programming

12.1 Introduction

Linear programming (LP) is a technique for the special case of a linear OF and linear constraints. In a 2‐DV case, both OF and constraints have the linear form of . While this may seem to be a trivial and restrictive model, it actually represents broad categories of applications in scheduling, blending, allocation, and logistics. LP applications are the mainstay of business optimization, and the applications go well beyond the 2‐DV realm, with 100–1000 DVs not uncommon.

This text has a focus on nonlinear optimization. Although linear applications constitute an important category of optimization applications and linear programming (LP) is a mainstay for many, this chapter only provides an introduction. The reader should have an understanding of the application category and LP technique, but this book does not provide details to make one an expert in its implementation.

A few examples will introduce the linear aspects of the application.

Example 1

An optimization application that leads to an LP structure, and which may be familiar to the reader, is planning meals. The objective is to minimize the cost of food items purchased for the week of meals while preparing meals that meet minimum daily requirements of nutrition elements. Here, only two constraints, Vitamin A and salt, are explicitly indicated; but the many S.T. relations would include ...