PHPSimplex

Optimizing resources with Linear Programming

Tweet

Simplex method theory

 

Simplex method is an iterative procedure that allows to improve the solution at each step. This procedure is finished when isn't possible to improve the solution.

Starting from a random vertex value of the objective function, Simplex method tries to find repeatedly another vertex value that improves the one you have before. The search is done through the side of the polygon (or the edges of the polyhedron, if the number of variables is higher). As the number of vertices (and edges) is finite, it will always be able to find the result. (See Graphical method)

Simplex method is based on the following property: if objective function, F, doesn't take the max value in the A vertex, then there is an edge starting at A, along which the value of the function grows.

You should take care about Simplex method only works with "≤" type inequality and independent coefficients higher or equal to zero, and you will have to standardize the restrictions for the algorithm. Case after this procedure "≥" o "=" type restrictions appear (or not modified) you should try other ways, being Two-Phase Simplex method the best choice.

 

Preparing the model to adapt it to the Simplex method

This is the standard way of the model:

Objective function:	c1·x1 + c2·x2 + ... + cn·xn
Subject to:	a11·x1 + a12·x2 + ... + a1n·xn = b1 a21·x1 + a22·x2 + ... + a2n·xn = b2 ... am1·x1 + am2·x2 + ... + amn·xn = bm x1,..., xn ≥ 0

To do this you must follow these rules:

1. The objective must be maximize or minimize the function.
2. All restrictions must be equal.
3. All variables are not negatives.
4. The independent terms are not negatives.

Changing the optimization type.

If we want to minimize our model, we can keep it, but we must consider the new criteria for the halt condition (stop iterations when all coefficients in the value objective function row are less or equal to zero), and the leaving condition row. In order to not change criteria, we can convert the minimize objective function F to maximize objective F·(-1).

Advantages: We will not have to worry about halting criteria, or exit condition of rows, since they keep on.

Inconveniences: In the event of the function have all his basic variables positive, and further the restrictions are inequality "≤", they become negative when doing the change and plus signs remain in the row of the value of the objective function, then Simplex method obeys the halting condition, and that optimal value would be obtained is 0, by default.

Solution: In fact this kind of problem does not exist, since so that the solution is greater than 0, any restriction should have the condition "≥", and then we would go into a model for the Two-Phase Simplex method.

 

Converting the independent term sign (constants to the right of restrictions)

We will have to arrange our model so that the independent terms of restrictions will be greater or equal to 0, if not, Simplex method cannot be used. The only thing that would be necessary to do is multiply by "-1" the restrictions where independent terms be less than 0.

Advantages: With this simple modification of signs in restriction we can use Simplex method.

Inconveniences: It can work out in restrictions where we have to modify the signs of constants, the signs of inequalities be ("=", "≤"), becoming ("=","≥") what in any event we will have to develop the Two-Phase Simplex method. This inconvenience is not controllable, although it would be able to benefit us only if terms of inequality exist ("≤","≥"), and terms "≥" coincide with restrictions where the independent term is negative.

 

Normalization restrictions.

If an inequality of the type "≥", appears in our model, will we have to add a new variable, called surplus variable si, with restriction si ≥ 0. The new variable appears with coefficient equal to zero in the objective function, and subtracting in inequalities.

A problem appears to us, let's see how to solve inequalities that contains an inequality type "≥" :

As all our models based on that all his variables are greater or equal than zero, when we do the first iteration in the Simplex's model, the basic variables will not be in the base and they will take value zero, and all others will maintain their values. In this case our variable xs, after doing zero to x1 and x2, will take the value - b1. The condition of not negativeness will not come true, so it will be necessary to add a new variable, xr, that will appear in the objective function with zero coefficient, and adding in the inequality of correspondent restriction. Would be left of the following way:

This type of variables are called artificial variables, and they will appear when there are inequalities with inequality ("=","≥"). This will take us compulsorily to accomplish the Two-Phase Simplex method, that will explain later on.

Itself mode, if inequality has "≤" type, we will have to add a new variable, called slack variable si, with restriction si "≥" 0. The new variable appears with zero coefficient in the objective function, and adding up in the inequalities.

To sum up we can let this board, according to the inequality that appears, and with the value that the new variables must be with.

Type of inequality	Type of variable
≥	- surplus + artificial
=	+ artificial
≤	+ slack

 

Starting the Simplex method

Once we have standardized our model, it can happen to go into the Simplex method or Two-Phase Simplex method. See yourself in the figure as we must perform on for reach the solution of our problem.

 

 

We will explain each method step by step, concretizing the aspects that are necessary to take into account.

Simplex method

- First Board Construction: In the board's first column will appear that we will call base, in the second one, the coefficient that each variable that appears at base has in the objective function (we will call this column Cb), in third column, the independent term of every restriction (P0), and from this column will appear each variable of the objective function (Pi). In order to have a more obvious vision of the board, we will include a row that we will put each one of the names of columns in. On this board we have, we will include two new rows: One that will lead the board, where the constants of the coefficients of the objective function will appear, and another one that will be the last row, where the objective function will take value. Our final board will have such rows as restrictions.

 

Tableau
			C1	C2	...	Cn
Base	Cb	P0	P1	P2	...	Pn
P1	Cb1	b1	a11	a12	...	a1n
P2	Cb2	b2	a21	a22	...	a2n
...	...	...	...	...	...	...
Pm	Cbm	bm	am1	am2	...	amn
Z		Z0	Z1-C1	Z2-C2	...	Zn-Cn

Z row's values are obtained this way: Z0 value will be the result of substituting Cim in the objective function (zero else appears in the base). The left columns are obtained subtracting to this value the one belonging to the coefficient that appears in the board's front row.

It will be observed when realizing Simplex method, that slack variables will be in the base, in this first table.

- Halt Condition: Will check if we must do a new iteration or not to do, that it will be know if in Z row appears any negative value. If this is not the case, it means we have reached the problem's optimal solution.

- Choosing incoming variable: If halt condition has not come true, we must choose one variable to enter the base in the next board. For it we look for strictly negative values of the Z row, and the minor will be which give us the incoming variable.

- Choosing the variable that slips out: Once we have obtained the incoming variable, the coming out variable will be reached, having nothing else to do that select that row whose quotient P0/Pj be the lowest among strictly positives (considering that only will be done when Pj be greater than 0). The intersection among incoming column and the coming out row will determine us the pivot element.

- Updating the board: The correspondent rows to the objective function and titles will remain unaltered in the new board. Left rows will be calculated with two ways:

• If we are trying with pivot row, each element will result from:

   

  New Pivot Row Element = Actually Pivot Row Element / Pivot.

   

• The left elements of rows will be reached so:

   

  New Row Element = Actually Pivot Row Element - (Pivot Column Element from actually Row * New Row Element).
  

Two-Phase Simplex method

This method differs from Simplex method that first it is necessary to accomplish an auxiliary problem that has to minimize the sum of artificial variables. Once this first problem is resolved and reorganizing the final board, we start with the second phase, that consists in making a normal Simplex.

1st Phase

At this first phase, all can be done like in Simplex method, except the first board's construction, halt condition and preparing the board that will be used in the second phase.

- First Board Construction: We proceed in same way as Simplex method, but with some differences. Objective Function row is different in the first phase, because the objective function changes, due to it will appear every term with zero value, but them which are artificial variables, which have "-1" value because we are minimizing the sum of this variables (remember that minimize F is the same that maximize F·(-1)).

The other difference for this first board consists in the way of calculating the row Z. It will have to be calculated the following way: The Cb·Pj products will be added for all rows and to this sum we must subtract the value that appears (according to the column that we are doing) in the objective function row.

 

Tableau
		C0	C1	C2	...	Cn-k	...	Cn
Base	Cb	P0	P1	P2	...	Pn-k	...	Pn
P1	Cb1	b1	a11	a12	...	a1n-k	...	a1n
P2	Cb2	b2	a21	a22	...	a2n-k	...	a2n
...	...	...	...	...	...	...	...	...
Pm	Cbm	bm	am1	am2	...	amn-k	...	amn
Z		Z0	Z1	Z2	...	Zn-k	...	Zn

Being Zj = Σ(Cb·Pj) - Cj with Cj = 0 for all decision, slacks and surplus variables and Cj = -1 for artificial variables.

 

- Halt condition: The halt condition is the same that in Simplex method. The difference reside in that can occur two cases when halt condition is reached: the function takes zero value, it means that the original problem has solution, or function takes a different value, suggesting that our model does not have solution.

- Erasing artificial variables columns: If we have reached the conclusion that the original problem has solution, we must prepare our board for the second phase. The artificial variables columns will be erased, modify the objective function row instead original, and calculate Z row at same way that in the 1st phase's first board.

 

Noticing anomalous cases and solutions

Obtaining the solution: When the halt condition is reached, you can see the values of the basic variables which are in the base and the optimal value that the function takes, looking at P0 column. At case you're minimizing, this optimal value must be multiplied by "-1".

Infinite solutions: Once the halt condition is obeyed, if you notice that any variable that doesn't appear in the base, has a 0 value at row Z, it means there are other solutions that give you the same optimal value for the objective function. This is a problem which admits infinite solutions, all them among the segment (or plane portion, or space region, etc. depending on the number of variables) that defines Ax+By=Z0. You could do more iterations using as incoming variable any of the variables in the Z row which have zero value, and you would have other solutions.

Unbounded solution: When you are searching the outgoing variable whether you notice that every variable in the incoming variable column have all their elements negative or void, it's a problem which has an unbounded solution. So there is no optimal concrete value. If the values of the variables grow, the objective function value also grows without violates any restriction.

Solution does not exist: In case that there seems to be no solution, we will have to solve it using Two-Phase Simplex method, so at the end of the 1st phase we will know if we are in such situation.

Tie of incoming variable: You can choose anyone of them, unless it affect the final solution, the inconvenience that it presents is that according to this choose you will have to do more or less iterations. Is counseled to choose to favor of the basic variables, since are those that will stay on the base at the end of the method.

Tie of coming out variable: Again you can choose anyone of them, although it can occur degenerated case and entering into loop cycles. In order to avoid them as far as possible, we will have prejudice in favor of basic variables doing that they remain in the base. At the case to be in the first phase (of the Two-Phase Simplex method), we will choose in case of tie to take out the artificial variables.

Curiosity in the 1st Phase: When the first phase finalizes, if the original problem has solution all the artificial variables in the Z row must have value "1".

Can the pivot be 0?: It can not be 0, because, quotients must be greater than 0.

Copyright ©2006-2024 PHPSimplex. All rights reserved.

X