IUTAJS Valencia 2013-2

Investigación de Operaciones

Simplex Elemental

Método Simplex – Proceso iterativo (repetitivo) que mejora la solución de un Problema de PL hasta llegar a la solución

óptima [es recorrer cada posible solución de la región solución del Método Gráfico] – El Método Simplex puede ser utilizado con cualquier cantidad de Variables de Decisión. – El Método Simplex Elemental solo puede ser utilizado para casos con restricciones con relaciones del

tipo " ≤ " o " < " – El Método Simplex se ayuda de la técnica Gauss-Jordan de solución de sistemas ecuaciones, cuya

adaptación se conoce como Tabla Simplex (Tableau [tabló] Simplex). Para poder utilizar el Método Simplex Elemental, cada restricción debe ser transformada en igualdad,

para ello, a cada restricción se debe sumar una variable de holgura: " +S ", identificando con un subíndice la restricción a la que corresponde; así por ejemplo " +S1 ", indica que pertenece a la restricción 1

– Para poder utilizar la Tabla Simplex, la FO debe ser igualada a cero Formato de Tabla Simplex

Variables de Decisión Variables de Holgura Lado Derecho

Razón x y S1 S2 FO Variables Solución

– El lado derecho corresponde al lado derecho de la igualdad de la FO y de las restricciones – La tabla se reproducirá tantas veces sea necesaria, hasta llegar a la solución óptima

Variables de Decisión Variables de Holgura Lado Derecho

Razón x y S1 S2 MaxB –6 –8 0 0 0 Variables Solución

S1 30 20 1 0 300 300/20 S2 5 10 0 1 110 110/10

x y S1 S2 MaxB –2 0 0 8/10 88 Variables Solución

S1 20 0 1 –2 80 80/20 y 1/2 1 0 1/10 11 11/1/2

x y S1 S2 MaxB 0 0 1/10 6/10 96 Variables Solución

x 1 1/20 -1/10 4 y 0 1 -1/40 1/20 9

IUTAJS Valencia 2013-2

Investigación de Operaciones

Simplex Elemental

Llenado de la Tabla Simlex: –La primera fila corresponde a las variables utilizadas en el Problema de PL modificado. –La segunda fila es la de la FO, se colocan los coeficientes correspondientes a cada variable (de

decisión y de holgura) que aparezca en la FO cuando se iguala a cero. –Las filas restantes de la Tabla, corresponden a una fila por cada restricción que haya en el Modelo de

PL, y se colocan los coeficientes que aparecen en dicha fila correspondiente a cada variable. –En la columna de la FO, van aquellas variables que conforman la solución básica del Modelo de PL.

Inicialmente se colocan las Variables de Holgura. Desarrollo del Método Simplex para casos de Maximización 1– Elección de la Variable de Decisión u Holgura a entrar como Variable Solución:

en la fila de la FO, se elige el mayor valor con signo negativo, ej.: –5 , –-1 → –5. La columna correspondiente es la "columna pivote".

2– Elección de la Variable Solución a ser sustituida por la Variable que entra: se utiliza el criterio de la "Razón".

Criterio de la Razón: consiste en tomar el valor del lado derecho de cada restricción y dividirlo entre el valor en la fila correspondiente a la "columna pivote". La Variable Solución a salir es aquella que tenga la "menor razón". No se consideran casos negativos.

La fila de la variable a salir es la "fila pivote". 3– El cruce entre la "columna pivote" y la "fila pivote" genera el "elemento pivote", que es la base para

la aplicación de la técnica Gauss-Jordan para solucionar la Tabla Simplex. 4– En la Tabla Simplex, se sustituye la variable que sale por la variable que entra. 5– Técnica Gauss-Jordan para la Tabla Simplex: el "elemento pivote" hay que convertirlo en "1",

mediante la multiplicación o división por otro número; por ej.: si es "3", habrá que dividir entre "3" [lo que es igual a decir que se multiplica por "1/3". Esta multiplicación (o división) hay que hacerla con todos los valores de la fila. Luego de obtener el nuevo elemento pivote: "1" , en la columna pivote hay que hacer cero todos los demás valores que se encuentren por arriba o por debajo de este nuevo elemento pivote. Para ello, se hacen operaciones entre las filas de la Tabla Simplex como se hacen con una matriz.

6– Repetir el proceso hasta que todos los valores en la fila de la FO sean positivos, que es cuando se alcanza la solución del problema.

Una vez alcanzada la solución, los valores que aparezcan en la columna "Lado Derecho", serán los valores buscados (solución) para la FO y para las Variables de Decisión que queden como variables solución, del Modelo de PL. Desarrollo del Método Simplex para casos de Minimización Es de manera similar que para el caso de Maximización, salvo los siguientes cambios: – en el paso 1, se elige el mayor valor con signo positivo, ej.: +8 , +1 → +8 – en el paso 6, se repite el proceso hasta que todos los valores en la fila de la FO sean negativos.