Obj 8

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Obj 8 as PDF for free.

More details

  • Words: 505
  • Pages: 1
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.

Related Documents

Obj 8
November 2019 34
Obj
November 2019 36
Obj
April 2020 33
Obj Datastream.pdf
October 2019 39
Obj Datastream.pdf
October 2019 28
Obj 6
November 2019 36