mediciones

3. El Método Simplex

Procedimiento para un Problema de Maximizar con Restricciones de Menor o Igual

Paso Inicial

Se introducen las variables de holgura para transformar el problema de la forma canónica a la forma estándar. Se seleccionan las variables de holgura como las variables básicas iniciales. Por lo tanto, las variables de decisión son las variables no básicas iniciales (esdecir, iguales a cero).Luego, la función objetivo se expresa como sigue



Prueba de Optimalidad

La solución factible actual es la óptima si y sólo si todos los coeficientes en el renglón
Z son no negativos.. Si se ha encontrado la solución óptima, el proceso se detiene; de otra manera realizar una iteración para obtener la siguiente solución factible.

*Nota: Para un problema de minimizar,la solución factible actual es la óptima si y sólo si todos los coeficientes en el renglón Z son negativos o ceros.

Iteración

Paso 1. Determinar la variable básica entrante.

Seleccione la variable no básica con el valor Z más negativo. Marque la columna de la variable que entrará a la base. Esta columna es llamada la columna pivote.

*Nota: Para un problema de minimizar, se seleccionala variable no básica con el valor
Z más positivo.

Paso 2. Determinar la variable básica saliente.

Seleccione la variable básica aplicando la prueba del mínimo cociente.

Prueba del mínimo cociente
1. Divida los coeficientes del lado derecho (LD) entre los coeficientes de la columna pivote que sean positivos (mayores que cero).
2. Identifique el renglón que tiene el cociente máspequeño. Este es el renglón pivote.
3. La variable básica en ese renglón es la variable que saldrá de la base.

El elemento que se encuentra en la intersección de la columna y el renglón pivote es llamado el elemento pivote.

Paso 3. Pivotear para obtener la siguiente solución factible.

Usando operaciones elementales sobre los renglones (operaciones de Gauss-Jordan), el elemento pivote setransforma en uno y se hacen ceros los elementos arriba y abajo del elemento pivote. Regresar a la prueba de optimalidad.

Como Determinar el Tipo de Solución

Solución Única. Si en la tabla óptima sólo las variables básicas tienen el valor Z igual a cero. Es decir, si el número de ceros en el renglón Z es igual al número de variables básicas.

Solución Múltiple o Alternativa. Si en la tabla óptimaalguna variable no básica tiene el valor Z igual a cero. Es decir, si el número de ceros en el renglón Z es mayor que el número de variables básicas. En la práctica, los óptimos alternativos son útiles porque permiten escoger entre muchas soluciones sin que se deteriore el valor objetivo.

Solución Ilimitada o no Acotada. Si en alguna iteración la columna pivote tiene solamente valores nopositivos (ceros y negativos). En este caso, el valor de Z tenderá a infinito y al menos una de las variables también tenderá a infinito. La solución no acotada apunta hacia la posibilidad de que el modelo esté mal construido.

Solución no factible. Todos los problemas que tienen únicamente restricciones de menor o igual tienen región de soluciones factible, por lo que en estos casos no se presentansoluciones no factibles. Una solución no factible se puede presentar cuando el problema tiene restricciones de igualdad o de mayor o igual.

Solución Degenerada. Si una variable básica es igual a cero. Esta condición indica que el modelo tiene al menos una restricción redundante. Desafortunadamente, no hay técnicas fiables para identificar las restricciones redundantes a partir de la tabla.Cuando se presenta una solución degenerada en una tabla no óptima, puede ocasionar que el método simplex se “cicle” y no converja hacia la solución óptima. Aunque esto rara vez sucede en la práctica.

Como corregir un problema con solución ilimitada

Verifique los datos, es decir, que los coeficientes del modelo sean los correctos.
Verifique la dirección de la optimización.
Haga las...