Metodo Simplex

Método Simplex
- Construcción de la primera tabla: En la primera columna de la tabla aparecerá lo que llamaremos base, en la segunda el coeficiente que tiene en la función objetivo cada variable que aparece en la base (llamaremos a esta columna Cb), en la tercera el término independiente de cada restricción (P0), y a partir de ésta columna aparecerán cada una de las variables de la funciónobjetivo (Pi). Para tener una visión más clara de la tabla, incluiremos una fila en la que pondremos cada uno de los nombres de las columnas. Sobre ésta tabla que tenemos incluiremos dos nuevas filas: una que será la que liderará la tabla donde aparecerán las constantes de los coeficientes de la función objetivo, y otra que será la última fila, donde tomará valor la función objetivo. Nuestra tablafinal tendrá tantas filas como restricciones.
 
Tabla
 
 
 
C1
C2
...
Cn
Base
Cb
P0
P1
P2
...
Pn
Pi1
Ci1
bi1
a11
a12
...
a1n
Pi2
Ci2
bi2
a21
a22
...
a2n
...
...
...
...
...
...
...
Pim
Cim
bim
am1
am2
...
amn
Z
 
Z0
Z1-C1
Z2-C2
...
Zn-Cn
 
Los valores de la fila Z se obtienen de la siguiente forma: El valor Z0 será el de sustituir Cim en la funciónobjetivo (y cero si no aparece en la base). El resto de columnas se obtiene restando a este valor el del coeficiente que aparece en la primera fila de la tabla.
Se observará al realizar el método Simplex, que en esta primera tabla, en la base estarán las variables de holgura.
- Condición de parada: Comprobaremos si debemos de dar una nueva iteración o no, que lo sabremos si en la fila Z aparecealgún valor negativo. Si no aparece ninguno, es que hemos llegado a la solución óptima del problema.
- Elección de la variable que entra: Si no se ha dado la condición de parada, debemos seleccionar una variable para que entre en la base en la siguiente tabla. Para ello nos fijamos en los valores estrictamente negativos de la fila Z, y el menor de ellos será el que nos de la variable entrante.- Elección de la variable que sale: Una vez obtenida la variable entrante, obtendremos la variable que sale, sin más que seleccionar aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que sólo se hará cuando Pj sea mayor de 0). La intersección entre la columna entrante y la fila saliente nos determinará el elemento pivote.
- Actualización de la tabla:Las filas correspondientes a la función objetivo y a los títulos permanecerán inalterados en la nueva tabla. El resto deberá calcularse de dos formas diferentes:
Si es la fila pivote cada nuevo elemento se calculará:

Nuevo Elemento Fila Pivote = Elemento Fila Pivote actual / Pivote.
Para el resto de elementos de filas se calculará:

Nuevo Elemento Fila = Elemento Fila Pivote actual -(Elemento Columna Pivote en la fila actual * Nuevo Elemento Fila).


Método de las Dos Fases
Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el método Simplex normal.
FASE 1
Enesta primera fase, se realiza todo de igual manera que en el método Simplex normal, excepto la construcción de la primera tabla, la condición de parada y la preparación de la tabla que pasará a la fase 2.
- Construcción de la primera tabla: Se hace de la misma forma que la tabla inicial del método Simplex, pero con algunas diferencias. La fila de la función objetivo cambia para la primera fase, yaque cambia la función objetivo, por lo tanto aparecerán todos los términos a cero excepto aquellos que sean variables artificiales, que tendrán valor "-1" debido a que se está minimizando la suma de dichas variables (recuerde que minimizar F es igual que maximizar F·(-1)).
La otra diferencia para la primera tabla radica en la forma de calcular la fila Z. Ahora tendremos que hacer el cálculo de...