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 ℝn, and let b be a scalar.
– The set {x ∈ ℝn|aTx = b} is said to be a hyperplane.
– The set {x ∈ ℝn|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 ℝn, 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
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:
[1.2]
The graphical solution is shown in Figure 1.3. We have z* = −2, with
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 basic solution is said to be degenerate if at least one basic variable is zero. This type of solution is obtained when the number of lines passing through an extreme point is greater than the number of decision variables. A basic feasible solution whose m basic variables are positive is said to be a non-degenerate basic feasible solution.
REMARK.– Each basic feasible solution corresponds to an extreme point. However, there can be more than one basic feasible solution for the same extreme point. This occurs when the basic feasible solution is degenerate.
REMARK.– The number of basic solutions quickly becomes very large, even in modestly sized models. For example, a model in standard form with 12 constraints and 25 variables can have up to