14. Linear programming

Idea

Assume that we study a process, in which there are some variables, which depend on each other linearly and there are some constraints defined also in a linear form. We would like to maximize (e.g. profits) or minimize (e.g. costs), i.e. a property also given in a linear form. Such problem is called a problem of linear programming.

E.g.: x+2y-z\to \max under conditions x+2y=3, y-z\leq 2, x+2z\geq 3 means that we would like to try to find values of variables x,y,z, such that x+2y-z is as big as possible while those values meet the given conditions.

Polygons, polyhedrons, polytopes, simplexes

If we consider a problem in which there are two variables, the possible solutions can be visualized as points on the plane. Conditions \leq and \geq restrict possible set of solutions (feasible set) to some half-planes (and conditions — to lines). Satisfying all such conditions gives a polytope (generalized polygon), generalized because it can be unbounded.

Now if we draw levels of the function of costs, they would be parallel lines. It is easy to see that the optimal point (if it exists) is always a vertex of our polygon! Or maybe the whole edge consists of such points if an edge is parallel to cost levels lines.

In three dimensions we will see polyhedrons but again, we have to look for the optimal solution in one of the vertices.

Standard form of a problem

To construct a method of solving such problems first we need to define a standard form of a problem. We will say that a problem is in the canonical form if:

  • it is a problem of minimization,
  • every variable has condition \geq 0,
  • all other conditions are equations.

Every problem of linear programming can be transformed to the standard form in the following way:

  • in a problem of maximization we can multiply the objective function by -1 to get a cost function and a minimization problem,
  • every variable x, for which there is no condition \geq 0, has to be changed to sum of two variables x^+-x^- and add conditions x^+\geq 0, x^-\geq 0
  • for each condition of form e.g. a+2b\leq 3 we add new variable x (called a slack variable) and modify this condition to a+2b+x=3 and add condition x\geq 0. Analogously for every condition of form e.g. a+2b\geq 3 add new variable x and modify it to a+2b-x=3 and add condition x\geq 0.

E.g.: x+2y-z\to \max with conditions: x+2y=3, y-z\leq 2, x+2z\geq 3, has the following canonical form: -x^+ +x^- -2y^+ +2y^- +z^+ -z^- \to\min with conditions: y^+ -y^- -z^+ +z^- +a=2, x^+ -x^- +2z^+ -2z^- -b=3 i x^+,x^-,y^+,y^-,z^+,z^-,a,b\geq 0.

Basic and feasible solutions

Therefore the problem of linear programming in the canonical form consists of a linear cost function, few equations and assumption that all variables have to be \geq 0. Therefore our simplex is bounded by hyperplanes of type x\geq 0, so the vertices are the points with coordinates mainly zero, with except for some variables called basic. In other words, to calculate a vertex (called basic solution) we have to choose as many variables as we have independent equations (so called basic variables) and we set other variables to zero and calculated those basic variables.

E.g. in problem x+y+z=2, 2x+y-z=3, x,y,z\geq 0 we have the following basic solutions (vertices):

  • x,y basic, so z=0, so x+y=2, 2x+y=3, and x=1, y=1. (1,1,0).
  • x,z basic, so y=0, so x+z=2, 2x-z=3, and x=\frac{5}{3}, z=-\frac{1}{3}. (\frac{5}{3},0,-\frac{1}{3}).
  • y,z basic, so x=0, so y+z=2, y-z=3, and y=\frac{5}{2}, z=-\frac{1}{2}. (0,\frac{5}{2},-\frac{1}{2}).

Only the first of the above solutions is feasible, since rest of them violate constraints that x,y,z\geq 0.

Simplex method

Actually we already are able to solve a problem of linear programming. We know that we have to look for the optimal value in a vertex. We know how to calculate vertices. So we can calculate all the vertices and check the value of the cost in each of them and the vertex with the lowest value is the solution. But if there are many vertices, checking all of them is tedious. We need to check only few of them and that is what the simplex method is all about.

The idea is as follows. First we find and acceptable basic solution (a vertex). There are some edges in this vertex. Edges can be understood as changing one basic variable to an another. We have to check whether there exists an edge, which has the property that the cost value decreases along it. If so we go along it to the next vertex. We need to know how far we can go (we cannot make any variable negative) — it will determine which variable is dropped from the set of basic variable. It is the first which reaches zero. And iterate this procedure. In the new vertex we again look for an improving edge.

Before we formalize the above idea, one more remark. It may happen that there is no basic solution. Then the problem is contradictory and there is no solution at all. Also there may exist an infinite improving edge. An edge with no restriction. Edge along which cost value decreases but no variable decreases to zero. In this case also there is no optimal solution. Every solution can be improved.

Simplex array

We will use a tool called the simplex array. Consider a problem of linear programming in the standard form, e.g.: 2x+y+3z\to\min under conditions: x+y+3z+2t=5, y+z+t=3, x,y,z,t\geq 0. The simplex array is the matrix of this system of linear equations with additional row at the top representing the linear function which has to be minimized:

    \[\begin{array}{cccc|c}2&1&3&0&0\\ \hline 1&1&3&2&5 \\0&1&1&1&3\end{array}\]

First we have to find any feasible basic solution. In our example we see, that if we take x,y as basic variables and set z=t=0, we will get a feasible solution. Therefore, we need to transform the simplex array to the form describing this vertex, which means that in columns of basic variables I would like to have 1 in one row and 0 in the other rows. So:

    \[\underrightarrow{w_0-w_2, w_1-w_2} \begin{array}{cccc|c}2&0&2&-1&-3\\ \hline 1&0&2&1&2 \\0&1&1&1&3\end{array}\underrightarrow{w_0-2w_1}\begin{array}{cccc|c}0&0&-2&-3&-7\\ \hline 1&0&2&1&2 \\0&1&1&1&3\end{array}\]

Notice, that in the free coefficients column we get values of the basic variables, so we are in vertex (2,3,0,0). The value in the right top corner is the value of the cost function we would like to minimize multiplied by -1. So its value in this vertex is 7.

Now we would like to go along an improving edge. What does it mean? It means transforming the array in such a way that we will have 1 and zeros in another column and the function we would like to minimize decreases (value in the right top corner increases). One can see that this is possible if we choose a column in which there is a negative number in the top row. In other words columns of non-basic variables represent edges and numbers in this column in the top row represent their type. Improving edges have negative numbers, aggravating edges have positive numbers there. Zero means that the function which we are minimizing does not change along the edge. In our case we have two improving edges, and we have to go along one of them. Let us choose the third column. So we will have a new basic variable, namely z. Now we need to find out which variable, x or y will cease to be basic. In other words, in which row I should have one in the third column? It is determined by the fact that no variable can have negative value, in other words in the column of free coefficients we cannot have any negative number. Or yet in other words it is determined by the length of this edge. How to check it? Notice, that it depends on the value in the free column divided by the value in the column we have chosen. In our case: \frac{2}{2}=1 and \frac{3}{1}=3, respectively. We have to chose lower but positive number out of those. So we have to choose the first row. If we had chosen the second, in the first we would have negative number on the right. Additional remark is the following: if no quotient were positive or defined, our edge would be infinite, and no optimal solution would exist. Therefore, one will change its place in the first row, x will be dropped from the set of basic variables and we will end with basic variables: y,z:

    \[\underrightarrow{w_1\cdot \frac{1}{2}} \begin{array}{cccc|c}0&0&-2&-3&-7\\ \hline \frac{1}{2}&0&1&\frac{1}{2}&1 \\0&1&1&1&3\end{array}\underrightarrow{w_0+2w_1, w_2-w_1}\begin{array}{cccc|c}1&0&0&-2&-5\\ \hline \frac{1}{2}&0&1&\frac{1}{2}&1 \\-\frac{1}{2}&1&0&\frac{1}{2}&2\end{array}.\]

We are in the vertex (0,2,1,0) and the value of the function we are minimizing is 5. We have two vertices here: one aggravating (the first column) and one improving (the fourth column). We have to go along the second one (new basic variable: t). Restrictions: \frac{1}{\frac{1}{2}}=2 and \frac{2}{\frac{1}{2}}=4, both positive, the first one is lower, so again we have to choose the first row (variable z will cease to be basic):

    \[\underrightarrow{w_1\cdot 2} \begin{array}{cccc|c}1&0&0&-2&-5\\ \hline 1&0&2&1&2 \\-\frac{1}{2}&1&0&\frac{1}{2}&2\end{array}\underrightarrow{w_0+2w_1, w_2-\frac{1}{2}w_1}\begin{array}{cccc|c}3&0&4&0&-1\\ \hline 1&0&2&1&2 \\-1&1&-1&0&1\end{array}.\]

So we are in vertex (0,1,0,2). There are two edges here, both of them are aggravating. Therefore, we are in the optimal vertex with function value 1. So this is the solution of our problem: x=0,y=1,z=0,t=2.

Finding the first basic solution

It may happen that we do not see immediately any feasible basic solution which can be used to start the simplex method. E.g. assume that we do not know (even though it is possible to notice it in this case), which basic variables we should choose in the following problems: 2x+y\to \min, x+y+z=4, x-2y=1, x,y,z\geq 0. But we can do the following trick. We add a new variable to the second equation (then we will immediately see a basic solution): x+y+z=4, x-2y+m=1, x,y,z,m\geq 0 (if needed we can also add further variables to other equations). Next we modify the costs function to force the simplex method to substitute zero to the variable m. Let M be a very big number and let our new costs function be: 2x+y+Mn\to\min. Now during minimization our algorithm will have to decrease m down to zero.

Let us check:

    \[\begin{array}{cccc|c} 2&1&0&M&0\\ \hline 1&1&1&0&4\\ 1&-2&0&1&1\end{array}\underrightarrow{w_0-Mw_2} \begin{array}{cccc|c} 2-M&1+2M&0&0&-M\\ \hline 1&1&1&0&4\\ 1&-2&0&1&1\end{array}\]

describes vertex (0,0,4,1) and has one (very) improving edge related to variable x. The restrictions are 4 i 1, so we have to choose the second row and so variable m will cease to be basic. So:

    \[\underrightarrow{w_0-(2-M)w_2, w_1-w_2}\begin{array}{cccc|c} 0&4&0&M-2&-2\\ \hline 0&3&1&-1&3\\ 1&-2&0&1&1\end{array}\]

which describes vertex (1,0,3,0), which has only aggregating edges, so it is an optimal vertex. In the original problem it is vertex (1,0,3), with costs value 2.