Obj 8

OBJETIVO # 8. RESOLVER PROBLEMAS DE P.L. CON SOLUCIONES DEGENERADAS O CON VARIABLES ACOTADAS, EMPLEANDO TECNICAS AVANZADAS. La degeneración se genera cuando una variable básica es cero y se da cuando hay empate al determinar la variable que sale. En general se conocen dos métodos para resolver el problema de la degeneración: Método de Perturbación de Charnes y el Método Simplex Generalizado. MÉTODO DE CHARNES. Se emplea el algoritmo del simplex Al momento de escribir la tabla inicial del simplex se escriben primero las VB (de holgura) y luego las de decisión. Cuando al seleccionar la variable saliente se genera un empate, se va a la 1º columna y se dividen los coeficientes (vector b) de las variables con empate entre la columna de la VE (columna pivote). Si el empate persiste, se pasa a la siguiente columna, y así sucesivamente. SOLUCIONES PERTURBADAS En cada iteración se pueden detectar las soluciones perturbadas de la siguiente manera VB = xnb (ε ) = bi + ∑ xij ε j . Por ejemplo para hallar x3 (VB) sería: valor de x3 (b1) + los

valores de los coeficientes x1, x2, … xn en la tabla por ε elevado a la 1,2,…n Al obtener todos los valores de las VB se halla Z(ε) sustityendo en las variables de decisión los valores obtenidos anteriormente. Si por ejemplo, estamos en la primera iteración, Z(ε) = 0, ya que las variables de decisión aun no han entrado a la base.

VARIABLES ACOTADAS Se dice que una variable está acotada cuando se encuentra entre 2 valores o cotas, cota inferior (ci) y cota superior (cs). Para resolver un problema con variables acotadas se emplea el siguiente algoritmo: 1) Todas las variables acotadas deben tener cota inferior a 0. En caso que alguna no cumpla con esta condición se hace lo siguiente: a. Se hace cambio de variable: xn = x’n + ci b. Se sustituye la variable en la función objetivo y en las restricciones 2) Se emplea el algoritmo del simplex pero con las siguientes variaciones: a. Para seleccionar la variable saliente, el mínimo se obtiene de t1, t2 y uv, siendo t1 = mínimo entre las divisiones positivas, en caso de no haber términos positivos es ∞; t2 = mínimo entre las divisiones negativas, en caso de no haber términos negativos es ∞ y uv = cota superior de la variable entrante. b. Si el mínimo es igual al valor de t1, entonces se aplica simplex normal c. Si el mínimo es igual al valor de u v, entonces no hay VE ni VS, se sustituye la VE en su cota superior a través de la siguiente fórmula: xn = cs – x’n. Es decir, en la tabla la fila de la VE cambia de signo, luego se multiplica c/elemento de la fila por la cota superior y se suma a b. d. Si el mínimo es igual al valor de t1, entonces se aplica simplex normal y en la siguiente iteración se sustituye la VE en su cota superior.