Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

General linear programs

In the general linear-programming problem, we wish to optimize a linear function subject to a set of linear inequalities. Given a set of real numbers a₁, a₂, ..., a_n and a set of variables x₁, x₂, ..., x_n, a linear function f on those variables is defined by

If b is a real number and f is a linear function, then the equation

f(x₁, x₂, ..., x_n) = b

is a linear equality and the inequalities

f(x₁, x₂, ..., x_n) ≤ b

and

f(x₁, x₂, ..., x_n) ≥ b

are linear inequalities. We use the term linear constraints to denote either linear equalities or linear equalities. In linear programming, we do not allow strict inequalities. Formally a linear-programming problem is the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints. If we are to minimize, then we call the linear program a minimization linear program, and if we are to maximize, then we call the linear program a maximization linear program.

This remainder of this chapter will cover the formulation and solution of linear programs. Although there are several polynomial-time algorithms for linear programming, we shall not study them in this chapter. Instead, we shall study the simplex algorithm, which is the oldest linear-programming algorithm. The simplex algorithm does not run in polynomial time in the worst case, but it is fairly efficient and widely used in practice.