Mtodo de las dos fases - Diana Fases.pdfAs haciendo operaciones de fila y columna tenemos: bnb 0 X x 1 x 2 x 3 x 4 x 5 x 6 Sol X 0 0-10 6 X 0 1 03 2 4 x 1 01 2 x 5 01 2/5 -1/5 x 6 0-5 3 1 x 3 01 2 b b ...

  • Published on
    23-Feb-2018

  • View
    215

  • Download
    3

Transcript

Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 1 Mtodo de las dos fases Max X0 = 3x1+ 5x2 Sujeta a 4 x1 + x2 4 - x1 + 2x2 2 x2 3 x1, x2 0 1. Se obtiene el problema aumentado con variables artificiales. Max X0 = 3x1 + 5x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 Sujeta a: 4 x1 + x2 - x3 + x6 = 4 - x1 + 2 x2 - x4 + x7 = 2 x2 + x5 = 3 xi 0 i=1, 2, 3,..,7 2. Se obtiene la funcin artificial despejando las variables artificiales y sumndolas. x6 = 4 - 4 x1 - x2 + x3 x7 = 2 + x1 - 2 x2 + x4 _______________________________________________________________ X0' = 6 - 3 x1 - 3 x2 + x3 + x4 X0' + 3 x1 + 3 x2 - x3 - x4 = 6 y adems X0 - 3 x1 - 5 x2 + 0 x3 + 0x4 + 0x5 + 0x6 + 0x7 = 0 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 2 3. Se forma la tabla Simplex aumentada nb nb nb nb b b b Base X0 x1 x2 x3 x4 x5 x6 x7 Sol X0' 0 3 3 -1 -1 0 0 0 6 X0 1 -3 -5 0 0 0 0 0 0 x6 0 4 1 -1 0 0 1 0 4 x7 0 -1 2 0 -1 0 0 1 2 x5 0 0 1 0 0 1 0 0 3 4. Se minimiza la funcin artificial x0' hasta cero. nb b nb nb b b nb Base X0 x1 x2 x3 x4 x5 x6 x7 Sol X0' 0 9/2 0 1 1/2 0 0 -3 3 X0 1 -1/2 0 0 -5/2 0 0 5/2 5 x6 0 9/2 0 -1 1/2 0 1 -1/2 3 x2 0 -1/2 1 0 -1/2 0 0 1/2 1 x5 0 1/2 0 0 1/2 1 0 -1/2 2 b b nb nb b nb nb Base X0 x1 x2 x3 x4 x5 x6 x7 Sol X0' 0 0 0 0 0 0 -1 -5/2 0 X0 1 0 0 -11/9 -17/9 0 -11/9 17/9 26/3 x1 0 1 0 -2/9 1/9 0 2/9 -1/9 2/3 x2 0 0 1 -1/9 -4/9 0 1/9 4/9 4/3 x5 0 0 0 1/9 4/9 1 -1/9 -4/9 5/3 5. Como ya est minimizada la funcin artificial se eliminan las variables artificiales y el rengln de la funcin artificial. Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 3 2a fase b b nb nb b Base X0 x1 x2 x3 x4 x5 Sol X0 1 0 0 -11/9 -17/9 0 26/3 x1 0 1 0 -2/9 1/9 0 2/3 x2 0 0 1 -1/9 -4/9 0 4/3 x5 0 0 0 1/9 4/9 1 5/3 b b nb b nb Base X0 x1 x2 x3 x4 x5 Sol X0 1 0 0 -3/4 0 17/4 43/3 x1 0 1 0 -1/4 0 -1/4 1/4 x2 0 0 1 0 0 1 3 x4 0 0 0 1/4 1 9/4 15/4 b b b nb nb Base X0 x1 x2 x3 x4 x5 Sol X0 1 0 0 0 3 11 27 x1 0 1 0 0 1 2 4 x2 0 0 1 0 0 1 3 x3 0 0 0 1 4 9 15 Solucin x1 = 4 x4 = 0 x2 = 3 x5 = 0 X0 = 27 x3 =15 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 4 Representacin grfica del problema sta es la solucin grfica al problema. Obsrvese que en la fase I se generaron los puntos extremos A, B, C, y en la fase II partiendo de C se generaron D y E. 321AB CD E12 3 4 5 6-1-21234 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 5 Interpretacin de Resultados del Mtodo de las dos fases Al final de la fase I, cuando el criterio de mejorabilidad se ha satisfecho, pueden ocurrir las tres posibilidades siguientes: 1. X'0 = 0 y no hay VA en la base En este caso se ha encontrado una SBFI para el PO y debe procederse con ella hacia la fase II. 2. X0' = 0 y hay VA en la base, que sin duda sern ceros. En este caso, las VA deben intercambiarse por VR no bsicas, requirindose slo que el coeficiente de reemplazo entre la VA de salida y la VR de entrada sea diferente de cero. Si el intercambio es total, se ha generado una SBFI degenerada, para el PO y debe iniciarse con ella la fase II. Si el intercambio es parcial, las restricciones asociadas a las VA no desalojadas son redundantes analticamente, se deben eliminar de la tabla final de la fase I e ir a la fase II con las restricciones restantes. 3. X0 ' > 0 y evidentemente hay una VA bsica a nivel positivo. En este caso el problema original posee solucin inconsistente, entonces deben intercambiarse todas las VA bsicas por VR no bsicas, requirindose que el coeficiente de reemplazo sea diferente de cero. Si todas las VA bsicas se logran sacar de la base ptima, entonces la solucin ptima del PO es infactible. Si de lo contrario, una o ms VA permanecen en la base ptima, entonces la solucin del PO es inexistente. Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 6 Ejemplo de SBFI degenerada Min X0 = 2x1+ x2 Sujeta a x1 + 2x2 2 x2 2 3x1 + x2 6 x1, x2 0 Estandarizando el problema se tiene: x1 + 2x2 + x3 = 2 x2 + x4 = 2 3x1 + x2 - x5 + x6 = 6 De donde despejando x6 se obtiene la funcin artificial: f.a. = x6 = 6 - 3x1 - x2 + x5 y la tabla Simplex es: nb nb b b nb b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 3 1 0 0 -1 0 6 X0 1 -2 -1 0 0 0 0 0 x3 0 1 2 1 0 0 0 2 x4 0 0 1 0 1 0 0 2 x6 0 3 1 0 0 -1 1 6 De aqu observamos que la variable de entrada es x1 por ser la ms positiva, y la variable de salida es x3, de donde: Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 7 b nb nb b nb b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 -5 -3 0 -1 0 0 X0 1 0 3 2 0 0 0 4 x1 0 1 2 1 0 0 0 2 x4 0 0 1 0 1 0 0 2 x6 0 0 -5 -3 0 -1 1 0 Como se observa en la tabla anterior ya se minimiz hasta cero la funcin artificial y en el rengln cero ya no hay variables de entrada. Sin embargo todava existe una v.a. (x6) dentro de la base y se debe intentar sacarla. Esto se puede hacer metiendo a la base x2 y como el pivote es diferente de cero, esta operacin s sera posible. Por esta razn decimos que la SBFI es degenerada: Dividiendo toda la fila de x6 entre 5 tenemos: b nb nb b nb b Base X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 -5 -3 0 -1 0 0 X0 1 0 3 2 0 0 0 4 x1 0 1 2 1 0 0 0 2 x4 0 0 1 0 1 0 0 2 x6 0 0 1 3/5 0 1/5 -1/5 0 y transformando la matriz con operaciones de fila y columna: b b nb b nb nb Base X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 0 0 0 0 -1 0 X0 1 0 0 -1/5 0 -3/5 -3/5 4 x1 0 1 0 -1/5 0 -2/5 2/5 2 x4 0 0 0 -3/5 1 -1/5 1/5 2 x2 0 0 1 3/5 0 1/5 -1/5 0 Con esta matriz terminamos la primera fase y podemos entonces eliminar toda la fila de la funcin artificial y las columnas de las variables artificiales, quedando: Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 8 Como se puede observar esta es la matriz ptima de la segunda fase, es decir, en el rengln cero ya no hay variables no bsicas positivas, luego, la solucin ptima es: b b nb b nb Base X0 x1 x2 x3 x4 x5 Sol X0 1 0 0 -1/5 0 -3/5 4 x1 0 1 0 -1/5 0 -2/5 2 x4 0 0 0 -3/5 1 -1/5 2 x2 0 0 1 3/5 0 1/5 0 Solucin x1 = 2 x4 = 2 x2 = 0 x5 = 0 X0 = 4 x3 = 0 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 9 Ejemplo de redundancia analtica Max X0 = 2 x1 + x2 Sujeta a x1 + 2 x2 = 2 2 x1 - x2 = 4 3 x1 + x2 = 6 x2 2 x1, x2 0 Cuya estandarizacin es: X0 - 2 x1 - x2 = 0 x1 + 2 x2 + x4 = 2 2 x1 - x2 + x5 = 4 3 x1 + x2 + x6 = 6 x2 + x3 = 2 De aqu, despejando las VA x4, x5 y x6 y sumndolas para obtener la funcin artificial se tiene: x4 = 2 - x1 - 2 x2 x5 = 4 - 2 x1 + x2 x6 = 6 - 3 x1 - x2 ____________________________ f.a. = X0' = 12 - 6 x1 - 2 x2 x0' + 6 x1 + 2 x2 = 12 De donde la matriz inicial es: nb nb b b b b Base X0 x1 x2 x3 x4 x5 x6 Sol X0 0 6 2 0 0 0 0 12 X0 1 -2 -1 0 0 0 0 0 x4 0 1 2 0 1 0 0 2 x5 0 2 -1 0 0 1 0 4 x6 0 3 1 0 0 0 1 6 x3 0 0 1 1 0 0 0 2 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 10 b nb b nb b b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 -10 0 -6 0 0 0 X0 1 0 3 0 2 0 0 4 x1 0 1 2 0 1 0 0 2 x5 0 0 -5 0 -2 1 0 0 x6 0 0 -5 0 -2 1 0 0 x3 0 0 1 1 0 0 0 2 Revisando el rengln cero, resulta que ya se minimiz la funcin artificial hasta cero pues las variables no bsicas ya no son positivas. Sin embargo, las variables x5 y x6, las cuales son artificiales, todava estn en la base y se debe tratar de expulsarlas. Entonces, se busca entre las variables nb una candidata para reemplazarlas. As observamos que x2 puede entrar por x5. La nica condicin para el reemplazo es que el nmero que ser el pivote debe ser diferente de cero (en este caso es -5). As haciendo operaciones de fila y columna tenemos: b nb b nb b b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 -10 0 -6 0 0 0 X0 1 0 3 0 2 0 0 4 x1 0 1 2 0 1 0 0 2 x5 0 0 1 0 2/5 -1/5 0 0 x6 0 0 -5 0 -3 0 1 0 x3 0 0 1 1 0 0 0 2 b b b nb nb b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 0 0 -2 -2 0 0 X0 1 0 0 0 4/5 3/5 0 4 x1 0 1 0 0 1/5 2/5 0 2 x2 0 0 1 0 2/5 -1/5 0 0 x6 0 0 0 0 -1 -1 1 0 x3 0 0 0 1 -2/5 1/5 0 2 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 11 Como x6 no puede intercambiarse por ninguna variable real, entonces la tercera restriccin es redundante y la podemos eliminar de la tabla. As mismo se eliminan la fila de la funcin artificial y las columnas de las variables artificiales para continuar hacia la 2a. fase. b b b nb nb b X0 x1 x2 x3 x4 x5 x6 Sol X0 0 0 0 0 -2 -2 0 0 X0 1 0 0 0 4/5 3/5 0 4 x1 0 1 0 0 1/5 2/5 0 2 x2 0 0 1 0 2/5 -1/5 0 0 x6 0 0 0 0 -1 -1 1 0 x3 0 0 0 1 -2/5 1/5 0 2 de donde la matriz resultante es: b b b X0 x1 x2 x3 Sol X0 1 0 0 0 4 x1 0 1 0 0 2 x2 0 0 1 0 0 x3 0 0 0 1 2 Revisando sta ltima matriz, se observa que ya se tiene la condicin de optimalidad en el rengln cero y por tanto la solucin ya es la ptima: Solucin x1 = 2 x2 = 0 X0 = 4 x3 = 3 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 12 Ejemplo de solucin infactible Min X0= -2 x1 - 3 x2 Sujeta a x1 + x2 2 (1) 2 x1 + 4 x2 12 (2) x1, x2 0 El problema ya transformado es: X0 + 2 x1 + 3 x2 + 0x3 + 0x4 + 0x5 = 0 x1 + x2 + x3 = 2 2 x1 + 4 x2 - x4 + x5 = 12 Despejando de la restriccin (2) a x5 para formar la funcin artificial tenemos: X'0 = x5 = 12 - 2 x1- 4 x2 + x4 X0' + 2 x1+ 4 x2- x4 = 12 As, la tabla inicial para el problema es: nb nb b nb b Base X0 x1 x2 x3 x4 x5 Sol X0 0 2 4 0 -1 0 12 X0 1 2 3 0 0 0 0 x3 0 1 1 1 0 0 2 x5 0 2 4 0 -1 1 12 Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 13 nb b nb nb b Base X0 x1 x2 x3 x4 x5 Sol X0 0 -2 0 -4 -1 0 4 X0 1 -1 0 -3 0 0 -6 x2 0 1 1 1 0 0 2 x5 0 -2 0 -4 -1 1 4 El rengln X0' indica que se tiene solucin ptima pero X0' = 4 y adems la variable artificial x5 est en la base con valor positivo de 4 PO tiene solucin inconsistente. Se debe tratar de intercambiar x5 (por ser artificial) por x1, x3 x4 que son no bsicas. Como tal intercambio sera factible puesto que el coeficiente de entrada es 0 para las tres, se diagnostica solucin infactible. Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 14 Ejemplo de solucin inexistente Max X0 = 3x1 + 2x2 Sujeta a 2 x1 + 3 x2 = 6 6 x1 + 9 x2 = 36 x1, x20 Estandarizando el problema: X0 - 3x1 - 2x2 = 0 2x1 + 3x2 + x3 = 6 6x1 + 9x2 + x4 = 36 Despejando x3 y x4 y sumndolas para formar la funcin artificial: x3 = 6 - 2x1 - 3x2 x4 = 36 - 6x1 - 9x2 ___________________________ X0' = 42 - 8x1-12 x2 X0' + 8 x1+12 x2 = 42 As, la matriz inicial es: nb nb b b Base X0 x1 x2 x3 x4 Sol X0 0 8 12 0 0 42 X0 1 -3 -2 0 0 0 x3 0 2 3 1 0 6 x4 0 6 9 0 1 36 Dividiendo la fila x3 entre 3 para formar el pivote: Investigacin de Operaciones ____________________________________________________________________________________ Diana Cobos 15 nb nb b b Base X0 x1 x2 x3 x4 Sol X0 0 8 12 0 0 42 X0 1 -3 -2 0 0 0 x3 0 2/3 1 1/3 0 2 x4 0 6 9 0 1 36 nb b nb b Base X0 x1 x2 x3 x4 Sol X0 0 0 0 -4 0 18 X0 0 -5/3 0 2/3 0 4 x2 0 2/3 1 1/3 0 2 x4 0 0 0 -3 1 18 La solucin actual es ptima, porque en el rengln 0 ya se cumplieron las condiciones de optimalidad, sin embargo, X0=18 y x4, que es V.A., es bsica. Lo que procede entonces es tratar de expulsar a x4 de la base y meter a ella una variable real no bsica. La variable que se pudiera meter en lugar de x4 es x1 pero el coeficiente de reemplazo es cero, luego entonces la solucin es inconsistente inexistente.

Recommended

View more >