Simplex algorithm: simplex

6.52.1 Simplex algorithm: simplex_reduce

The simple case

The simplest linear programming problem is to find the maximum of an objective function

z(x₁,…,x_n) = c₁x₁+ ⋯ + c_nx_n

under the constraints (where b_i≥ 0, i=1,…,m):

a₁₁x₁	+	a₁₂x₂	+	⋯	+	a_1nx_n	≤	b₁	(7)
⋮								⋮	(8)
a_m1x₁	+	a_m2x₂	+	⋯	+	a_mnx_n	≤	b_m	(9)
									(10)

and

x_i≥ 0 i=1,…,n.

This can be abbreviated

max(c· x), Ax ≤ b, x ≥ 0, b≥ 0

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

The simplex method

Xcas can do the simplex method for you, but it can still help to get a rough idea of how it works. You can google “simplex method” for more details.

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

a₁₁x₁

a₁₂x₂

⋯

a_1nx_n

s₁

⋯

b₁

⋮

a_m1x₁

a_m2x₂

⋯

a_mnx_n

⋯

s_m

b_m

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 beginning solution. The objective function

z	= c₁x₁+⋯ + c_nx_n
	= c₁x₁+⋯ + c_nx_n+0s₁+⋯ + 0s_m

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

⎛
⎜
⎝

A	I_m	b
−c	0	0

⎞
⎟
⎠

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.

simplex_reduce

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:

⎛
⎜
⎝

A	I_m	b
−c	0	0

⎞
⎟
⎠

which you can get with:

B := augment(A,idn(m));

C := border(B,b)

d:=append(-c,0$(m+1))

D:=augment(C,[d])

and then call simplex_reduce(D).

Example.
Find

max(X+2Y) where

⎧
⎪
⎨
⎪
⎩

(X,Y)	≥	0
−3X +2Y	≤	3
X +Y	≤	4

Input:

simplex_reduce([[-3,2],[1,1]],[3,4],[1,2])

Output:

⎡
⎣

1,3,0,0

⎤
⎦

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

−

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

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, find:

min(2x+y−z+4) where

⎧
⎪
⎪
⎨
⎪
⎪
⎩

x	≤	1
y	≥	2
x+3y−z	=	2
2x−y+z	≤	8
−x+y	≤	5

(11)

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) where:

⎧
⎪
⎨
⎪
⎩

X	≥	0
Y	≥	0
2(1−X)−(Y+2)+ 5−X+3Y	≤	8
−(1−X) +(Y+2)	≤	5

or to find the minimum of:

(−X−2Y+3) where

⎧
⎪
⎨
⎪
⎩

X	≥	0
Y	≥	0
−3X+2Y	≤	3
X +Y	≤	4

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 a starting 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:

⎛
⎜
⎝

A	I_m	b
0	1	0

⎞
⎟
⎠

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

−x	−	y			+	t	=	1
		y	−	z	+	t	=	3

you would start by finding a solution of

−x

−

s₁

−

s₂

as mentioned above.
Input:

simplex_reduce([[-1,-1,0,1,1,0,1],[0,1,-1,1,0,1,3],[0,0,0,0,1,1,0]])

Output:

⎡
⎣

0,1,0,2,0,0

⎤
⎦

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

−

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

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).
Input:

simplex_reduce([[-1/2,0,-1/2,1,2],[1/2,1,-1/2,0,1],[2,3,-1,1,0]])

Output:

−5,

⎡
⎣

0,1,0,2

⎤
⎦

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

−

−5

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

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).