LOS PASOS DEL METODO SIMPLEX SON LOS SIGUIENTES

FORMATO ESTANDAR

Otra de las condiciones del modelo estándar del problema es que todas las restricciones sean ecuaciones de igualdad (también llamadas restricciones de igualdad), por lo que hay que convertir las restricciones de desigualdad o inecuaciones en dichas identidades matemáticas.

La condición de no negatividad de las variables (x1,..., xn ≥ 0) es la única excepción y se mantiene tal cual.

• Restricción de tipo "≤"

Para normalizar una restricción con una desigualdad del tipo "≤", hay que añadir una nueva variable, llamada variable de holgura xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y sumando en la ecuación correspondiente (que ahora sí será una identidad matemática o ecuación de igualdad).

a11·x1 + a12·x2 ≤ b1   a11·x1 + a12·x2 + 1·xs = b1

• Restricción de tipo "≥"

En caso de una desigualdad del tipo "≥", también hay que añadir una nueva variable llamada variable de exceso xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y restando en la ecuación correspondiente.

Surge ahora un problema con la condición de no negatividad con esta nueva variable del problema. Las inecuaciones que contengan una desigualdad de tipo "≥" quedarían:

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

Al realizar la primera iteración con el método Simplex, las variables básicas no estarán en la base y tomarán valor cero. En este caso la nueva variable xs, tras hacer cero a x1 y x2, tomará el valor -b1 y no cumpliría la condición de no negatividad. Es necesario añadir otra nueva variable xr, llamada variable artificial, que también aparecerá con coeficiente cero en la función objetivo y sumando en la restricción correspondiente. Quedando entonces de la siguiente manera:

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

• Restricción de tipo "="

Al contrario de lo que cabría pensar, para las restricciones de tipo "=" (aunque ya son identidades) también es necesario agregar variables artificiales xr. Como en el caso anterior, su coeficiente será cero en la función objetivo y aparecerá sumando en la restricción correspondiente.

a11·x1 + a12·x2 = b1   a11·x1 + a12·x2 + 1·xr = b1

En el último caso se hace patente que las variables artificiales suponen una violación de las leyes del álgebra, por lo que será necesario asegurar que dichas variables artificiales tengan un valor 0 en la solución final. De esto se encarga el método de las Dos Fases y por ello siempre que aparezcan este tipo de variables habrá que realizarlo.

En la siguiente tabla se resume según la desigualdad el tipo de variable que aparece en la ecuación normalizada, así como su signo:

1- Utilizando la forma estándar, determinar una solución básica factible inicial igualando a las n-m variables igual a cero (el origen).

2- Seleccionar la variable de entrada de las variables no básicas que al incrementar su valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la solución actual es la óptima; si no, ir al siguiente paso.

3- Seleccionar la variable de salida de las variables básicas actuales.

4- Determinar la nueva solución al hacer la variable de entrada básica y la variable de salida no básica, ir al paso 2 (actualizar)