• Author / Uploaded
• milysanti

• Categories
• Métodos matemáticos y cuantitativos (economía)
• Optimización Matemática
• Matemáticas De La Computación
• La investigación de operaciones
• Áreas de informática

Citation preview

MÉTODO DE LAS DOS FASES Los problemas de programación Lineal (PL) pueden resolverse por el método Simplex en formato matricial que llamaremos Ta b l o i d e . El Método de las Dos fases es el mismo método Simplex que aplicamos en los problemas de Maximización, solo que con algunas variantes que iremos explicando en el desarrollo de un ejemplo cuya optimización se obtendrá por Minimización.

Max X0 = 3x1+ 5x2 Sujeto a

4 x1 + x2 - x1 + 2x2 x2 x1, x2



4 2 3



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 función artificial despejando las variables artificiales y sumándolas.

x6 = 4 - 4 x1 - x2 + x3 x7 = 2 + x1 - 2 x2 + x4 X 0 ' = 6 - 3 x1 - 3 x2 + x3 + x4 

y además

X 0 ' + 3 x1 + 3 x2 - x3 - x4 =6 X0 - 3 x1 - 5 x2 + 0 x3 + 0x4 + 0x5 + 0x6 + 0x7 = 0

3. Se forma la tabla Simplex aumentada Base X0' X0 x6 x7 x5

X0 0 1 0 0 0

nb x1 3 -3 4 -1 0

nb x2 3 -5 1 2 1

nb x3 -1 0 -1 0 0

nb x4 -1 0 0 -1 0

b x5 0 0 0 0 1

b x6 0 0 1 0 0

b x7 0 0 0 1 0

Sol 6 0 4 2 3

4. Se minimiza la función artificial x0' hasta cero. Base X0' X0 x6 x2 x5

Base X0' X0 x1 x2 x5

X0 0 1 0 0 0

nb x1 9/2 -1/2 9/2 -1/2 1/2

b x2 0 0 0 1 0

nb x3 1 0 -1 0 0

nb x4 1/2 -5/2 1/2 -1/2 1/2

b x5 0 0 0 0 1

b x6 0 0 1 0 0

nb x7 -3 5/2 -1/2 1/2 -1/2

Sol 3 5 3 1 2

X0 0 1 0 0 0

b x1 0 0 1 0 0

b x2 0 0 0 1 0

nb x3 0 -11/9 -2/9 -1/9 1/9

nb x4 0 -17/9 1/9 -4/9 4/9

b x5 0 0 0 0 1

nb x6 -1 -11/9 2/9 1/9 -1/9

nb x7 -5/2 17/9 -1/9 4/9 -4/9

Sol 0 26/3 2/3 4/3 5/3

5. Como ya está minimizada la función artificial se eliminan las variables artificiales y el renglón de la función artificial.

a

2 fase Base X0 x1 x2 x5

Base X0 x1 x2 x4

Base X0 x1 x2 x3

X0 1 0 0 0

b x1 0 1 0 0

b x2 0 0 1 0

nb x3 -11/9 -2/9 -1/9 1/9

nb x4 -17/9 1/9 -4/9 4/9

b x5 0 0 0 1

Sol 26/3 2/3 4/3 5/3

X0 1 0 0 0

b x1 0 1 0 0

b x2 0 0 1 0

nb x3 -3/4 -1/4 0 1/4

b x4 0 0 0 1

nb x5 17/4 -1/4 1 9/4

Sol 43/3 1/4 3 15/4

X0 1 0 0 0

b x1 0 1 0 0

b x2 0 0 1 0

b x3 0 0 0 1

nb x4 3 1 0 4

nb x5 11 2 1 9

Sol 27 4 3 15

Solución

x1 = 4 x2 = 3 x3 =15

x4 = 0 x5 = 0



X0 = 27

Representación gráfica del problema

2

4

3

E

D

3 2

C

1 B

A -2

-1

1

2

3

4

5

6

1

Ésta es la solución gráfica al problema. Obsérvese 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.

Interpretación de Resultados del Método 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 serán ceros. En este caso, las VA deben intercambiarse por VR no básicas, requiriéndose sólo 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 analíticamente, 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 básica a nivel positivo. En este caso el problema original posee solución inconsistente, entonces deben intercambiarse todas las VA básicas por VR no básicas, requiriéndose que el coeficiente de reemplazo sea diferente de cero. Si todas las VA básicas se logran sacar de la base óptima, entonces la solución óptima del PO es infactible. Si de lo contrario, una o más VA permanecen en la base óptima, entonces la solución del PO es inexistente.

Ejemplo de SBFI degenerada Min

X0 = 2x1+ x2

Sujeta a

x1 3x1

+ 2x2 x2 + x2

  

2 2 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 función artificial: f.a. = x6 = 6 - 3x1 - x2 + x5 y la tabla Simplex es:

X0’ X0 x3 x4 x6

X0 0 1 0 0 0

nb x1 3 -2 1 0 3

nb x2 1 -1 2 1 1

b x3 0 0 1 0 0

b x4 0 0 0 1 0

nb x5 -1 0 0 0 -1

b x6 0 0 0 0 1

Sol 6 0 2 2 6

De aquí observamos que la variable de entrada es x1 por ser la más positiva, y la variable de salida es x3, de donde:

b x1 0 0 1 0 0

X0 0 1 0 0 0

X0’ X0 x1 x4 x6

nb x2 -5 3 2 1 -5

nb x3 -3 2 1 0 -3

b x4 0 0 0 1 0

nb x5 -1 0 0 0 -1

b x6 0 0 0 0 1

Sol 0 4 2 2 0

Como se observa en la tabla anterior ya se minimizó hasta cero la función artificial y en el renglón cero ya no hay variables de entrada. Sin embargo todavía 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 operación sí sería posible. Por esta razón decimos que la SBFI es degenerada: Dividiendo toda la fila de x6 entre 5 tenemos: Base X0’ X0 x1 x4 x6

X0 0 1 0 0 0

b x1 0 0 1 0 0

nb x2 -5 3 2 1 1

nb x3 -3 2 1 0 3/5

b x4 0 0 0 1 0

nb x5 -1 0 0 0 1/5

b x6 0 0 0 0 -1/5

Sol 0 4 2 2 0

nb x6 -1 -3/5 2/5 1/5 -1/5

Sol 0 4 2 2 0

y transformando la matriz con operaciones de fila y columna: Base

X0’ X0 x1 x4 x2

X0 0 1 0 0 0

b x1 0 0 1 0 0

b x2 0 0 0 0 1

nb x3 0 -1/5 -1/5 -3/5 3/5

b x4 0 0 0 1 0

nb x5 0 -3/5 -2/5 -1/5 1/5

Con esta matriz terminamos la primera fase y podemos entonces eliminar toda la fila de la función artificial y las columnas de las variables artificiales, quedando:

Como se puede observar esta es la matriz óptima de la segunda fase, es decir, en el renglón cero ya no hay variables no básicas positivas, luego, la solución óptima es: Base

X0 x1 x4 x2

b x1 0 1 0 0

b x2 0 0 0 1

Solución

x1 = 2

x4 = 2

x2 = 0 x3 = 0

x5 = 0

X0 1 0 0 0

nb x3 -1/5 -1/5 -3/5 3/5

b x4 0 0 1 0



X0 = 4

nb x5 -3/5 -2/5 -1/5 1/5

Sol 4 2 2 0

Ejemplo de redundancia analítica Max X0 = 2 x1 + x2 Sujeta a

x1 + 2 x2 = 2 x1 - x2 = 3 x1 + x2 = x2 

2 4 6 2

x1, x2  0

Cuya estandarización 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 sumándolas para obtener la función 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: Base X0’ X0 x4 x5 x6 x3

X0 0 1 0 0 0 0

nb x1 6 -2 1 2 3 0

nb x2 2 -1 2 -1 1 1

b x3 0 0 0 0 0 1

b x4 0 0 1 0 0 0

b x5 0 0 0 1 0 0

b x6 0 0 0 0 1 0

Sol 12 0 2 4 6 2

X0’ X0 x1 x5 x6 x3

X0 0 1 0 0 0 0

b x1 0 0 1 0 0 0

nb x2 -10 3 2 -5 -5 1

b x3 0 0 0 0 0 1

nb x4 -6 2 1 -2 -2 0

b x5 0 0 0 1 1 0

b x6 0 0 0 0 0 0

Sol 0 4 2 0 0 2

Revisando el renglón cero, resulta que ya se minimizó la función artificial hasta cero pues las variables no básicas ya no son positivas. Sin embargo, las variables x5 y x6, las cuales son artificiales, todavía están 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 condición para el reemplazo es que el número que será el pivote debe ser diferente de cero (en este caso es -5). Así haciendo operaciones de fila y columna tenemos:

X0’ X0 x1 x5 x6 x3

X0’ X0 x1 x2 x6 x3

X0 0 1 0 0 0 0

X0 0 1 0 0 0 0

b x1 0 0 1 0 0 0 b x1 0 0 1 0 0 0

nb x2 -10 3 2 1 -5 1

b x3 0 0 0 0 0 1

nb x4 -6 2 1 2/5 -3 0

b x5 0 0 0 -1/5 0 0

b x6 0 0 0 0 1 0

Sol 0 4 2 0 0 2

b x2 0 0 0 1 0 0

b x3 0 0 0 0 0 1

nb x4 -2 4/5 1/5 2/5 -1 -2/5

nb x5 -2 3/5 2/5 -1/5 -1 1/5

b x6 0 0 0 0 1 0

Sol 0 4 2 0 0 2

Como x6 no puede intercambiarse por ninguna variable real, entonces la tercera restricción es redundante y la podemos eliminar de la tabla. Así mismo se eliminan la fila de la función artificial y las columnas de las variables artificiales para continuar hacia la 2a. fase.

X0’ X0 x1 x2 x6 x3

X0 0 1 0 0 0 0

b x1 0 0 1 0 0 0

b x2 0 0 0 1 0 0

b x3 0 0 0 0 0 1

nb x4 -2 4/5 1/5 2/5 -1 -2/5

nb x5 -2 3/5 2/5 -1/5 -1 1/5

b x6 0 0 0 0 1 0

Sol 0 4 2 0 0 2

de donde la matriz resultante es:

X0 x1 x2 x3

X0 1 0 0 0

b x1 0 1 0 0

b x2 0 0 1 0

b x3 0 0 0 1

Sol 4 2 0 2

Revisando ésta última matriz, se observa que ya se tiene la condición de optimalidad en el renglón cero y por tanto la solución ya es la óptima:

Solución

x1 = 2 x2 = 0 x3 = 3



X0 = 4

Ejemplo de solución infactible Min X0= -2 x1 - 3 x2 Sujeta a

x1 + x2  2 2 x1 + 4 x2  12

(1) (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 restricción (2) a x5 para formar la función 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:

Base X0’ X0 x3 x5

X0 0 1 0 0

nb x1 2 2 1 2

nb x2 4 3 1 4

b x3 0 0 1 0

nb x4 -1 0 0 -1

b x5 0 0 0 1

Sol 12 0 2 12

Base

X0’ X0 x2 x5

X0 0 1 0 0

nb x1 -2 -1 1 -2

b x2 0 0 1 0

nb x3 -4 -3 1 -4

nb x4 -1 0 0 -1

b x5 0 0 0 1

Sol 4 -6 2 4

El renglón X0' indica que se tiene solución óptima pero X0' = 4 y además la variable artificial x5 está en la base con valor positivo de 4  PO tiene solución inconsistente. Se debe tratar de intercambiar x5 (por ser artificial) por x1, x3 ó x4 que son no básicas. Como tal intercambio sería factible puesto que el coeficiente de entrada es  0 para las tres, se diagnostica solución infactible.

Ejemplo de solución inexistente Max

X0 = 3x1 + 2x2

Sujeta a

2 x1 + 3 x2 = 6 6 x1 + 9 x2 = 36 x1, x2  0

Estandarizando el problema:

X0 - 3x1 - 2x2 = 0 2x1 + 3x2 + x3 = 6 6x1 + 9x2 + x4 = 36 Despejando x3 y x4 y sumándolas para formar la función 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: Base X0’ X0 x3 x4

X0 0 1 0 0

nb x1 8 -3 2 6

nb x2 12 -2 3 9

b x3 0 0 1 0

Dividiendo la fila x3 entre 3 para formar el pivote:

b x4 0 0 0 1

Sol 42 0 6 36

Base X0’ X0 x3 x4

Base X0’ X0 x2 x4

X0 0 1 0 0

nb x1 8 -3 2/3 6

nb x2 12 -2 1 9

b x3 0 0 1/3 0

X0 0 0 0 0

nb x1 0 -5/3 2/3 0

b x2 0 0 1 0

nb x3 -4 2/3 1/3 -3

b x4 0 0 0 1 b x4 0 0 0 1

Sol 42 0 2 36

Sol 18 4 2 18

La solución actual es óptima, porque en el renglón 0 ya se cumplieron las condiciones de optimalidad, sin embargo, X0’=18 y x4, que es V.A., es básica. Lo que procede entonces es tratar de expulsar a x4 de la base y meter a ella una variable real no básica. La variable que se pudiera meter en lugar de x4 es x1 pero el coeficiente de reemplazo es cero, luego entonces la solución es inconsistente inexistente.