Metodo Simplex

En el año 1947 el doctor George Dantzig presentó el algoritmo que desarrolló y que denominó SIMPLEX. A partir de este logro se pudieron resolver problemas que por más de un siglo permanecieron en calidad de estudio e investigación con modelos formulados pero no resueltos. El desarrollo paralelo de la computación digital, hizo posible su rápido desarrollo y aplicación empresarial a todo tipo de problemas.

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.

 PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

La forma estándar del modelo de problema consta de una función objetivo sujeta a determinadas restricciones:

Función objetivo: c1•x1 + c2•x2 + ... + cn•xn

Sujeto a: a11•x1 + a12•x2 + ... + a1n•xn = b1

a21•x1 + a22•x2 + ... + a2n•xn = b2

...

am1•x1 + am2•x2 + ... + amn•xn = bm

x1,..., xn ≥ 0

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.

 TIPO DE OPTIMIZACIÓN.

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.

 CAMBIO DE SIGNO DE LOS TÉRMINOS INDEPENDIENTES

También se ha dicho que los términos independientes (bi) de cada ecuación deben ser no negativos para poder emplear el método Simplex. A tal fin, si alguna de las restricciones presenta un término independiente menor que 0 habrá que multiplicar por "-1" ambos lados de la inecuación (teniendo en cuenta que esta operación también afecta al tipo de restricción).

 Ventajas: Con ésta simple modificación de signos en las restricciones correspondientes se posibilita la aplicación del método Simplex al problema modelado.

 Inconvenientes: Puede resultar que en las restricciones

...