X

PHPSimplex
Versión 0.9

Copyright ©2006-2014. Todos los derechos reservados.

Desarrollado por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traducción a inglés por:
Luciano Miguel Tobaria

Traducción a francés por:
Ester Rute Ruiz

PHPSimplex

Optimizando recursos con Programación Lineal



Teoría del método Simplex

Preparando el modelo para adaptarlo al método Simplex
Tipo de optimización
Cambio de signo de los términos independientes
Normalización de las restricciones
Desarrollando el método Simplex
Método Simplex
Método de las Dos Fases
Identificando casos anómalos y soluciones
Método Gráfico
Ejemplo del método Simplex
Ejemplo del método Gráfico
Comparación del método Simplex y el método Gráfico

 

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.

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

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

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 donde tengamos que modificar los signos de las constantes, los tipos de desigualdad fueran "≤" (quedando tras la operación del tipo "≥") siendo necesario desarrollar el método de las Dos Fases. Este inconveniente no es controlable, aunque podría ocurrir el caso contrario y resultar beneficioso si los términos independientes negativos se presentan en todas aquellas restricciones con desigualdad de tipo "≥". Si existe alguna restricción del tipo "=" no supondría ninguna ventaja ni desventaja puesto que siempre sería de necesaria aplicación el método de las Dos Fases.

Normalización 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.

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

Desarrollando el método Simplex

Una vez estandarizado el modelo puede ocurrir que sea necesario aplicar el método Simplex o el método de las Dos Fases. Véase en la figura la forma de actuación para llegar a la solución del problema modelado.

Algoritmo del Simplex

A continuación se explican paso a paso los puntos de cada método, concretando los aspectos a tener en cuenta.

Método Simplex
Método de las Dos Fases

El método de las Dos Fases se utiliza cuando aparecen variables artificiales en la forma canónica o estándar del problema. La primera fase trata de resolver el problema auxiliar Z' de minimizar la suma de las variables artificiales y conseguir que sea cero (con objeto de evitar incongruencias matemáticas). Una vez resuelto este primer problema, y siempre y cuando el resultado sea el esperado, se reorganiza la tabla resultante para utilizarla en la segunda fase sobre el problema original.

En caso contrario el problema no es factible, es decir, no tiene solución y no será necesario continuar con la segunda fase.

FASE 1

Esta primera fase es muy similar al método Simplex, con la excepción de la construcción de la primera tabla, además de la necesidad de estudiar el resultado obtenido para determinar si se desarrolla la segunda fase.

En tal caso, la última tabla de esta fase será, con algunas modificaciones, la utilizada como tabla inicial para la segunda fase.

FASE 2

La segunda fase del método de las Dos Fases se desarrolla exactamente igual que el método Simplex, con la salvedad de que antes de iniciar las iteraciones hay que eliminar las columnas correspondientes a las variables artificiales, y reconstruir la tabla inicial.

A partir de este punto, todas las iteraciones hasta llegar a la solución óptima del problema no presentan ninguna diferencia con el método Simplex.

Identificando casos anómalos y 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).

Copyright ©2006-2014 PHPSimplex. Todos los derechos reservados. Términos y condiciones.
Síguenos en Twitter