1
Linear Programming

1.1. Introduction

Linear programming can be defined as a mathematical technique for solving management problems. For example, suppose that a manager faced with various options wishes to determine the optimal way to use the resources of a company to achieve a specific objective, such as maximizing the utility or minimizing the cost. The company's problems can usually be modeled as a linear program (LP) consisting of a certain number of resources [HIL 90]. For instance, the labor, raw materials and capital are all resources available in limited quantities that must be distributed optimally over various manufacturing processes. The approach to solving this type of problem is divided into two key steps:

• - model the problem with linear equations or inequalities that allow us to properly identify and structure the constraints satisfied by the variables of the model. The contribution of each variable to the company's overarching objective must also be defined as a function that will be optimized;
• - find the mathematical optimum using specific linear programming techniques. We will study three methods for solving the various types of linear programming problems. The first is based on graphical solving and is therefore limited to two or three variables. The second method is more algebraic; it motivates the third method presented in this chapter, which is known as the simplex method (or algorithm).

1.2. Definitions

DEFINITION 1.1.- An LP is in canonical form if it is expressed as follows:

An LP is in standard form if it is expressed as follows:

Every linear problem can be expressed in canonical form: min cTx = - max cTx.

THEOREM 1.1.- Every LP in standard form can be expressed in canonical form and vice versa.

Terminology

• - The function cT x is the objective function, cost function or loss function.
• - The components of the vector x are called decision variables.
• - If the vector x satisfies all constraints, then x is an admissible solution.
• - The set of all admissible solutions is the admissible set or admissible region.
• - An admissible solution x* that maximizes the loss function (i.e. cTx* = cTx for every admissible x) is called an optimal admissible solution or optimal solution.

EXAMPLE 1.1.- A factory manufactures two products P1 and P2 while consuming certain resources: equipment, labor and raw materials. The needs are listed in the following table. Each resource is available in limited quantities.

The two products P1 and P2 yield effective profits of 6 dhs and 4 dhs per unit. The goal is to determine which (possibly non-integer) quantities of the products P1 and P2 the factory should produce to maximize the total profit from selling these two products, subject to the availability of the resources.

Let x1 and x2 be the quantities of the products P1 and P2, respectively.

The LP may be expressed as follows: maximize z(x1, x2) = 6x1 + 4x2 subject to:

• - availability of resources:

• - positivity of variables: x1, x2 = 0

1.3. Geometry of the linear program

1.3.1. Polyhedra

DEFINITION 1.2.- A polyhedron is a set that can be described as

where A is an m × n matrix and b is a vector in Rm. Note that the admissible set of an LP is a polyhedron.

DEFINITION 1.3.- A polyhedron P is said to be bounded if there exists a constant c such that ||x|| = c for every x ? P.

Figure 1.1. Bounded polyhedron (left) and unbounded polyhedron (right). For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip

DEFINITION 1.4.- Let a be a non-zero vector of Rn, and let b be a scalar.

• - The set {x ? Rn|aTx = b} is said to be a hyperplane.
• - The set {x ? Rn|aTx = b} is said to be a half-space.

Note that a hyperplane is the boundary of the corresponding half-space and the vector a is perpendicular to the hyperplane that it defines [TEG 12].

1.3.2. Extreme points and vertices

Let P be a polyhedron and x* ? P. The point x* is an extreme point if and only if x* is a vertex and x* is a basic admissible solution.

DEFINITION 1.5.- Let P be a polyhedron. A vector x ? P is an extreme point of P if it cannot be expressed as a convex combination of two other points of P.

DEFINITION 1.6.- Let P be a polyhedron. A vector x ? P is a vertex of P if there exists c such that

for every y in P not equal to x.

THEOREM 1.2.- In linear programming, if the admissible domain is neither empty nor the whole of Rn, it is a convex polytope with finitely many vertices that can either be bounded or unbounded. If an extreme point exists, it is attained at one of the vertices of the polytope. A point in the interior of the domain is never an extreme point if f ? 0. If the polytope is bounded, f attains both a minimum and a maximum on it.

This theorem gives us a graphical solving method.

1.4. Graphical solving of a linear program

The graphical method works by plotting lines and searching for a solution as follows:

• - identify the admissible domain;
• - identify the contours;
• - contours perpendicular to the vector c, and therefore mutually parallel;
• - each value of z is associated with a contour;
• - the value of z increases in the direction of c.

EXAMPLE 1.2.- Consider, again, the example from earlier. Its mathematical model is defined by the following linear program:

The intersection of the half-planes determined by the lines corresponding to each constraint represents the set of solutions that satisfy the constraints (shaded area). The direction of the cost function is given by

This gives us the optimal solution by sliding the line with this direction upwards, while keeping it parallel, until its intersection with the y-axis is maximal. Graphical solutions are of course only applicable with programs of, at most, three variables (see Figure 1.2).

Figure 1.2. Graphical solution. For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip

EXAMPLE 1.3.- Consider the linear program:

The graphical solution is shown in Figure 1.3. We have z* = -2, with and

Figure 1.3. Graphical solution with isoprofit lines. For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip

1.5. Simplex algorithm

If a linear programming problem in standard form has an optimal solution, then a basic admissible solution that is optimal exists. The simplex algorithm is an algorithm for solving linear optimization problems. Introduced by George Dantzig in 1947, it was probably the earliest algorithm for minimizing functions on sets defined by inequalities. The algorithm moves from one basic admissible solution to the next while reducing the cost.

The idea of the method is as follows:

• - Let x0 be a basic admissible solution.
• - For k = 0, . . . , find an adjacent basic admissible solution xk+1 such that .
• - Until no adjacent basic admissible solution improves the objective.

This gives a local minimum, which is in fact a global minimum in linear programming.

1.5.1. Basic solutions and basic feasible solutions

Consider a system of m linear equations Ax = b with n variables (m = n).

DEFINITION 1.7.- A basic solution of the system of equations Ax = b is obtained by setting n - m variables to zero and solving the system for the remaining p variables. The solution of the system of p equations in m unknowns is assumed to be unique. The n - p variables set to zero are said to be non-basic variables, and the p remaining variables are said to be basic variables. An LP admits, at most, basic solutions. If the basic solution also satisfies the non-negativity constraints, it is said to be a basic feasible solution.

DEFINITION 1.8.- A...