An Introduction to Optimization, 4th Edition

CHAPTER 15

INTRODUCTION TO LINEAR PROGRAMMING

15.1 Brief History of Linear Programming

The goal of linear programming is to determine the values of decision variables that maximize or minimize a linear objective function, where the decision variables are subject to linear constraints. A linear programming problem is a special case of a general constrained optimization problem. In the general setting, the goal is to find a point that minimizes the objective function and at the same time satisfies the constraints. We refer to any point that satisfies the constraints as a feasible point. In a linear programming problem, the objective function is linear, and the set of feasible points is determined by a set of linear equations and/or inequalities.

In this part we study methods for solving linear programming problems. Linear programming methods provide a way of choosing the best feasible point among the many possible feasible points. In general, the number of feasible points is infinitely large. However, as we shall see, the solution to a linear programming problem can be found by searching through a particular finite number of feasible points, known as basic feasible solutions. Therefore, in principle, we can solve a linear programming problem simply by comparing the finite number of basic feasible solutions and finding one that minimizes or maximizes the objective function—we refer to this approach as the brute-force approach. For most practical decision problems, even this finite ...