SIMPLEX METHOD

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

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.

Model of the problem is prepared 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 a maximize or a minimize the function.
2. All restrictions must be equal.
3. All variables are non-negatives.
4. The independent terms are non-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 to maximize objective.

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

Inconveniences/ Disadvantages :  In the event of the function having all its 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(special condition).

Change in signs of 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.

Special Condition

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 "≥"  :

a11·x1 + a12·x2 ≥ b1 -----> a11·x1 + a12·x2 - 1·xs = b1

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 x1and 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:

a11·x1 + a12·x2 ≥ b1 -----> a11·x1 + a12·x2 - 1·xs + 1 ·xr = b1

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 be 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

Also, to solve the equations with the “≥” inequality, we can use another method apart from “Two Phase Method”. This method is known as “Big-M” Method. This will be explained later.