16.1.1  Simplex algorithm

The simple case.

Linear programming problem in its simplest form is to find the maximum of an objective function

subject to constraints (where b_i≥ 0, i=1,…,m):

and

This can be abbreviated as

where the vector inequalities mean term-by-term inequalities. The constraints determine a simplex in ℝⁿ and the standard approach to solving this problem is called the simplex method.

The simplex method.

Xcas can apply the simplex method for you, but it can still help to get a rough idea of how it works. (You can search the Internet for “simplex method” to get more details.)

The constraint inequalities (1) can be turned into equalities by adding an auxiliary (surplus) variable for each inequality. The constraints are equivalent to:

for some s₁,…,s_m≥ 0. The straightforward solution to this system of equations, namely x_i=0 for i=1,…,n and s_j=b_j for j=1,…,m, will be the initial solution. The objective function

will be zero at this solution. If one of the coefficients of the objective function is positive, you can find a larger value of x_i that will also be a solution of the equations (by making one of the s_j smaller) and will give a larger value of z.

The mechanics of this process involves writing the given information in a matrix. The matrix of the system of equalities including the surplus variables is (A I_mb); the simplex method begins with this matrix above a row beginning with −c followed by zeros. The last element of the last row is the value of the objective function at the current solution. The resulting matrix (the simplex tableau) looks like

The simplex method involves doing a specific series of row operations that effectively determine a new solution to the constraints that increase the values of the current values of the variables x_i and so increase the value of the objective function. The method ends when there are no negative values left in the bottom row.

The simplex_reduce command performs the simplex method on a linear programming problem of the form, for b≥ 0, Ax ≤ b with x≥ 0.

• simplex_reduce takes three arguments:
  • A, b and c from the problem.
• simplex_reduce(A,b,c) returns a sequence consisting of:
  • The maximum value of the objective function.
  • The solution of x (augmented since the algorithm works by adding auxiliary variables).
  • The reduced matrix.

Alternatively, you could combine the arguments A,b,c into the matrix that begins the algorithm:

which you can construct with the following command lines:

The above matrix is obtained as D and passed to simplex_reduce.

Example

Maximize X+2Y subject to

This means that the maximum of X+2Y under these conditions is 7, it is obtained for X=1,Y=3 because [1,3,0,0] is the augmented solution and the reduced matrix is:

Notice that the (non-zero) values of the solution have columns of the m× m identity matrix above them.

Reducing a more complicated case to the simple case.

With the former call of simplex_reduce, you have to:

• rewrite constraints to the form x_k ≥ 0,
• remove variables without constraints,
• add variables such that all the constraints have positive components.

For example, minimize 2x+y−z+4 subject to

Let x=1−X, y=Y+2, z=5−X+3Y. The problem is equivalent to finding the minimum of −2X+Y−(5−X+3Y)+8 under conditions

or to find the minimum of (−X−2Y+3) subject to

i.e. to find the maximum of −(−X−2Y+3)=X+2Y−3 under the same conditions, hence it is the same problem as to find the maximum of X+2Y seen before. You found that the previous problem had a maximum of 7, hence the result here is 7−3=4.

The general case.

A linear programming problem may not in general be directly reduced like above to the simple case. The reason is that a starting solution must be found before applying the simplex algorithm.

The standard form of a linear programming problem is similar to the simplest case above, but with Ax=b (instead of Ax≤ b) for b ≥ 0 under the conditions x≥ 0. In this case, there is no straightforward solution. So the first problem is to find an x with x≥ 0 and Ax=b.

Finding an initial solution.

Let m be the number of rows of A. Add artificial variables s₁,…,s_m and maximize −∑s_i under the conditions Ax=b, x ≥ 0, s ≥ 0 starting with initial value 0 for x variables and y=b. If a solution exists and is 0, then the s_i must all be 0 and so x will be solution of Ax=b, x≥ 0.

You can solve this with simplex_reduce by calling it with a single matrix argument:

For example, to find the minimum of 2x+3y−z+t with x,y,z,t≥ 0 and:

you would start by finding a solution of

as mentioned above.

Since the solution (x,y,z,t,s₁,s₂)=(0,1,0,2,0,0) has s₁=s₂=0, a non-negative solution of the equalities in x,y,z and t is (x,y,z,t)=(0,1,0,2).

Finding a solution of the LP problem.

Now you can make a second call to simplex_reduce with the reduced matrix (less the columns corresponding to the variables s₁ and s₂) and the usual c. In this case, finding the requested minimum means finding the maximum of −2x−3y+z−t, so c=(−2,−3,1,−1).

This maximum is −5, so the requested minimum is −(−5)=5 at (0,1,0,2) (x=0, y=1, z=0 and t=2).