TEORIA DEL METODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función

objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho
valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el
caso, para el que se satisfacen todas las restricciones).

Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en

buscar otro punto que mejore el valor anterior. Como se verá en el método Gráfico, dichos
puntos son los vértices del polígono (o poliedro o polícoro, si el número de variables es mayor
de 2) que constituye la región determinada por las restricciones a las que se encuentra sujeto el
problema (llamada región factible). La búsqueda se realiza mediante desplazamientos por las
aristas del polígono, desde el vértice actual hasta uno adyacente que mejore el valor de la
función objetivo. Siempre que exista región factible, como su número de vértices y de aristas es
finito, será posible encontrar la solución.

El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor

máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor
de Z aumenta.

Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del
problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes
sean mayores o iguales a 0. Por tanto, habrá que estandarizar las restricciones para que cumplan
estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste
proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan
cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método
de las Dos Fases.

El modelo debe cumplir las siguientes condiciones:

1. El objetivo consistirá en maximizar o minimizar el valor de la función objetivo (por

ejemplo, incrementar ganancias o reducir pérdidas, respectivamente).

2. Todas las restricciones deben ser ecuaciones de igualdad (identidades matemáticas).

3. Todas las variables (xi) deben tener valor positivo o nulo (condición de no negatividad).

4. Los términos independientes (bi) de cada ecuación deben ser no negativos.

Hay que adaptar el problema modelado a la forma estándar para poder aplicar el algoritmo del
Simplex.

TIPO DE OPTIMIZACION

Como se ha comentado, el objetivo del método consistirá en optimizar el valor de la función

objetivo. Sin embargo, se presentan dos opciones: obtener el valor óptimo mayor (maximizar) u
obtener el valor óptimo menor (minimizar).

Además, existen diferencias en el algoritmo entre el objetivo de maximización y el de

minimización en cuanto al criterio de condición de parada para finalizar las iteraciones y a las
condiciones de entrada y salida de la base. Así:

 Objetivo de maximización

Condición de parada: cuando en la fila Z no aparece ningún valor negativo.

Condición de entrada a la base: el menor valor negativo en la fila Z (o el de mayor valor absoluto
entre los negativos) indica la variable Pj que entra a la base.

Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se
determina mediante el menor cociente P0/Pj de los estrictamente positivos.

 Objetivo de minimización

Condición de parada: cuando en la fila Z no aparece ningún valor positivo.

Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable Pj que entra
a la base.

Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se
determina mediante el menor cociente P0/Pj de los estrictamente negativos.

No obstante, es posible normalizar el objetivo del problema con el fin de aplicar siempre los
mismos criterios en lo referente a la condición de parada del algoritmo y a las condiciones de
entrada y salida de las variables de la base. De esta forma, si el objetivo es minimizar la solución,
se puede cambiar el problema a otro equivalente de maximización simplemente multiplicando
la función objetivo por "-1". Es decir, el problema de minimizar Z es equivalente al problema de
maximizar (-1)·Z. Una vez obtenida la solución será necesario multiplicarla también por (-1).

Ventajas: No hay que preocuparse por nuevos criterios de parada, condición de entrada y salida
de la base ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todos los coeficientes de sus variables básicas
positivos, y además las restricciones sean del tipo de desigualdad "≤", al hacer el cambio dichos
coeficientes quedan negativos cumpliéndose la condición de parada en la primera iteración (en
la fila del valor de la función objetivo todos los valores son positivos o cero). Obteniéndose en
este caso por defecto un valor óptimo para la función igual a 0.

Solución: Realmente no existe este problema dado que para que la solución sea superior a 0 es
necesario que alguna restricción tenga impuesta la condición "≥" (y se trataría de un modelo
para el método de las Dos Fases). En el caso planteado, la solución real debe ser cero.

NORMALIZACION DE LAS RESTRICCIONES

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:

Tipo de desigualdad Tipo de variable que aparece

≥ - exceso + artificial

= + artificial

≤ + holgura

IDENTIFICANDO CASOS ANOMALOS Y TIPOS DE SOLUCIONES

Solución óptima: cuando se cumple la condición de parada y no hay variables artificiales en la

base con valor positivo (los valores se indican en la columna P0), se ha conseguido la
optimización. El valor Z0 actual es la solución óptima del problema, cumpliéndose para las
variables que se encuentran en la base. Si se trata de un problema de minimización, el valor
óptimo obtenido se multiplicará por "-1".
Infinitas soluciones: cumplida la condición de parada, si alguna variable de decisión no básica
tiene un valor 0 en la fila Z, significa que existe otra solución que aporta el mismo valor óptimo
para la función objetivo. Es este caso el problema admite infinitas soluciones, estando todas
ellas comprendidas dentro del segmento (o porción del plano, región del espacio, etc.
dependiendo del número de variables del problema) definido por A·X1 + B·X2 = Z0. Mediante
una nueva iteración y haciendo que la variable de decisión que tiene el 0 en la fila Z entre en la
base se obtendrá otra solución diferente para el mismo valor óptimo.

Solución ilimitada (no acotada): si toda la columna de la variable que entra a la base tiene todos
sus elementos negativos o nulos se trata de problema no acotado, es decir, que tiene solución
ilimitada. No hay valor óptimo concreto para la función objetivo, sino que a medida que se
aumenta el valor de las variables también se incrementa el valor Z sin violar ninguna restricción.

No existe solución: cuando ningún punto satisface todas las restricciones del problema se
produce la infactibilidad no existiendo ninguna solución posible para él. En este caso, una vez
terminadas todas las iteraciones del algoritmo, existen en la base variables artificiales cuyo valor
es superior a cero.

Empate de variable entrante: cuando se produce un empate en la condición de decisión de la

variable entrante se puede optar por cualquiera de ellas sin que esto afecte a la solución final.
Por contra si influye en el número de iteraciones necesarias para obtener dicha solución. Se
aconseja optar a favor de las variables básicas ya que ellas son las que formarán parte de la
solución óptima.

Empate de variable saliente: se puede nuevamente optar por cualquiera de ellas. Sin embargo,
a fin de no alargar el problema y evitar la entrada en un bucle infinito (caso degenerado), se
discrimina a favor de las variables de decisión haciendo que permanezcan en la base. En el caso
de estar en la primera fase del método de las Dos Fases, se optará por sacar de la base las
variables artificiales.

Curiosidad en la Fase 1: al finalizar la fase 1, si el problema original tiene solución, todas las
variables artificiales en la fila indicadora deben tener el valor "1".

¿El elemento pivote puede ser nulo?: No, el elemento pivote siempre será estrictamente
positivo ya que únicamente se realizan los cocientes entre valores no negativos y mayores que
cero (ante un problema de maximización).