Numerical Methods with Programming

Section 35.1 Introduction to linear programming

Suppose we want to maximize the function \(f(\mathbf x) = x_1+2x_2-5x_3\) subject to constraints \(0\le x_1\le x_2\le x_3\le 10\) and \(2x_3 - x_1\ge 3\text{.}\) This is a linear programming (LP) problem, since each constraint is a linear inequality and the objective function is linear.

There are various standard forms to which linear programming problems can be transformed by manipulations such as the following:

• An equality constraint can be expressed as the combination of \(\le \) and \(\ge\) constraints.
• Any \(\ge \) constraint becomes \(\le \) after multiplication by \(-1\text{.}\)
• Maximization of \(f\) is equivalent to minimization of \(-f\text{.}\)

Using the transformations described above, any LP can be expressed as:

where the inequality between vectors \(A\mathbf x \le \mathbf b\) is understood as a system of linear inequalities: each component on the left is less than or equal to the corresponding component on the right. Compare this to how \(A\mathbf x = \mathbf b\) means a system of linear equations.

Sometimes the nature of the problem requires the variables \(x_k\) to be nonnegative, which leads to

Or, one may have linear equations instead of inequalities:

One can convert between these three “standard” forms as follows.

From (35.1.1) to (35.1.2): replace each variable \(x_k\) with the difference \(x_k = x_k' - x_k''\text{,}\) and require \(x_k', x_k''\) to be nonnegative. Since every real number is the difference of two nonnegative numbers, this does not change the essence of the problem. In terms of \(A, b\text{,}\) this transformation keeps \(\mathbf b\) the same but doubles the size of \(A\) by appending \(-A\) to the right. The vector \(\mathbf c\) is similarly doubled.

From (35.1.2) to (35.1.1): add linear inequalities of the form \(-x_k \le 0\text{.}\) This means appending \(-I\) to the bottom of matrix \(A\text{,}\) with zeros added to the bottom of vector \(\mathbf b\text{.}\)

From (35.1.2) to (35.1.3): introduce slack variables \(z_k = b_k - (A\mathbf x)_k\text{.}\) Then replace all linear inequalities \(A\mathbf x\le \mathbf b\) with nonnegativity constraints \(\mathbf z\ge 0\text{.}\) What remains is the definition of slack variables, which is a system of linear equations.

From (35.1.3) to (35.1.2): rewrite each linear equation as two linear inequalities. That is, a system of linear equations \(A\mathbf x = \mathbf b\) is equivalent to having two systems of linear inequalities: \(A\mathbf x \le \mathbf b\) and \(A\mathbf x \ge \mathbf b\text{.}\) The latter system is rewritten as \((-A)\mathbf x \le -\mathbf b\) and appended to the former.

In Matlab, the problem (35.1.1) is solved with

x = linprog(c, A, b)

which returns the optimal \(\mathbf x\text{.}\) One can get the optimal value of objective function with c'*x.

linprog([-1; -1], [1 2; 3 1], [4; 5])

Example 35.1.1 illustrates basic use of linprog. This command allows more parameters which express equality constraints and additional lower and upper bounds on the variables: see help linprog.

Octave-specific remark. The current version of Octave has a similar function glpk instead of linprog. The main difference is that glpk(c, A, b) solves (35.1.3) instead of (35.1.1). However, the fourth argument of glpk can be used to set lower bounds to \(-\infty\) instead of \(0\text{,}\) the fifth argument (for upper bounds) can be left empty [], and the sixth argument is a string indicating the form of constraints, with letters 'U' for \(\le\text{.}\) So, Example 35.1.1 with Octave would be

glpk([-1; -1], [1 2; 3 1], [4; 5], [-Inf; -Inf], [], 'UU')

See help glpk for more.

As an additional example, let us solve the problem at the beginning of this section. The objective function \(f(\mathbf x) = x_1+2x_2-5x_3\) was to be maximized, so we minimize \(-f\) which means c = [-1; -2; 5]. The constraints \(0\le x_1\le x_2\le x_3\le 10\) become \(-x_1\le 0\text{,}\) \(x_1-x_2\le 0\text{,}\) \(x_2-x_3\le 0\text{,}\) and \(x_3\le 10\text{.}\) Finally, \(2x_3 - x_1\ge 3\) becomes \(x_1 - 2x_3 \le -3\text{.}\) We arrive at a system of five linear constraints, summarized in A, b below:

c = [-1; -2; 5];
A = [-1 0 0; 1 -1 0; 0 1 -1; 0 0 1; 1 0 -2];
b = [0; 0; 0; 10; -3];
x = linprog(c, A, b);
fprintf('Found x = (%g, %g, %g) with c*x = %g \n', x, c'*x) ;

Note that A*x is the vector [0; -1.5; 0; 1.5; -3] where three of components are equal to the components of b and the others are strictly less. The equality means that the corresponding constraints, such as \(-x_1 \le 0\text{,}\) are active at the optimal point: the point pushes against them. The constraints \(x_1\le x_2\) and \(x_3\le 10\) are inactive at this point: they hold as strict inequalities. The solution would stay the same if the inactive constraints were removed.

The following terms may appear in error messages or warnings issued by linprog or its analogues in other software.

• A feasible point is a vector \(x\) that satisfies the constraints. The set of all such points is the feasible set.
• A problem is infeasible if there are no feasible points. (Example: \(x_1\ge 2\text{,}\) \(x_2\ge 2\text{,}\) \(x_1+x_2\le 3\text{.}\)) Such a problem has no solution.
• A problem is unbounded if the objective function takes arbitrarily small values on the feasible set (in case of minimization) or arbitrarily large values (in case of maximization). Such a problem has no solution.
• If the feasible set is nonempty and bounded, the problem surely has a solution. But it is possible to have an unbounded feasible set on which the objective function is bounded: recall Example 35.1.1.

Applied LP problems tend to have many variables and constraints, and a lot of work went into developing refining its solution methods such as the simplex method (walking along the edges of the feasible set) and interior point methods (moving through the interior of the feasible set toward its boundary).