Investigacin de operaciones:Viernes, 05 de Agosto de 2011

Smplex - Mtodo de -las dos fases. Investigacin de Operaciones Tarea n2:Mtodo de las 2 Fases.

Alumno: Gorki Andrs Gonzlez Canales.EJERCICIO 1Minimizar S. a

Desarrollo. Primero, pasar la funcin objetivo de minimizar a maximizar. Ello se logra, multiplicando la funcin objetivo por menos uno (-1), lo cual deja a la funcin objetivo as

A continuacin, se procede a dejar en forma de igualdad las restricciones del problema y a modificar la funcin objetivo, segn corresponda.

Ahora, se procede a eliminar el trmino M de la funcin objetivo o ecuacin cero (0) Para ello, se realiza la siguiente operacin: Ello genera una nueva Ahora, a la la cual logra que el trmino sea cero.

se le aplicar la siguiente operacin: que ya no cuenta con el trmino logrando as, eliminar todos los trminos M en la funcin objetivo o

Ello genera una nueva Ahora, a la ecuacin cero.

se le multiplica por

Entonces, nuestro sistema queda as

Ahora, se est en condiciones de aplicar Smplex.Iteracin Variable Bsica Nmero de Ecuacin Coeficientes Lado Derecho Cociente Mnimo?

Z

0 1 2

Z -1 0 0

-7

-4 1 3

1 -1 0

0 1 0

1 0 -1

0 0 1

-9 3 6

0

34

11,5

MIN

1

Solucin Bsica Factible Inicial. Z -9

0

0

0

3

0

6

Variable bsica entrante:

Variable bsica saliente:

(1)*(1/3) = N(1) (2)-(N(1)*4) = N(2) (0)+(N(1)*7) = N(0)

Z 0 0 -1

1 0 0

1/3 5/3 -5/3

-1/3 4/3 -4/3

1/3 -4/3 7/3

0 -1 1

0 1 0

LD 1 2 -2

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

1Solucin Bsica Factible.

0 1 2

Z -1 0 0

Lado Derecho

Cociente

Mnimo?

0 1 0

-5/3 -4/3 1/3 -1/3

7/3 1/3 -4/3

1 0 -1

0 0 1

-2 1 2

5/3

4/3

3 1,2

MIN

Z -2

1

0

0

0

0

2

Variable bsica entrante:

Variable bsica saliente: Z 0 0 -1 LD 6/5 3/5 0

(2)*(3/5) = N(2) (1)-[N(2)*(1/3)] = N(1) (0)+[N(2)*(5/3)] = N(0)

0 1 0

1 0 0

4/5 -3/5 0

-4/5 3/5 1

-3/5 1/5 0

3/5 -1/5 1

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z -1 0 0 0 1 0 0 0 1 0 1 0 1 -3/5 3/5 1/5 -1/5 4/5 -4/5 -3/5 3/5

Lado Derecho

Cociente

Mnimo?

Z

0 1 2

2

03/5 6/5

Regln cero, no hay ms coeficientes negativos. Fin de iteracin.1 Solucin Bsica Factible. Z

0

3/5

6/5

0

0

0

0

Ahora, se quitan las columnas de las variables artificialesIteracin Variable Bsica Nmero de Ecuacin

y

.Lado Derecho

Coeficientes

1

Z

0 1 2

Z -1 0 0

0 1 0

0 0 1

0 -3/5 4/5

0 1/5 -3/5

0 0,6 6/5

Si el valor de la Z ptima es cero, se puede continuar, de lo contrario el problema no tiene solucin y no se contina.

2

Se reemplaza los coeficientes del regln cero por los coeficientes de la funcin objetivo, pero maximizada. Las restricciones quedan tal cual.Iteracin Variable Bsica Nmero de Ecuacin Coeficientes

-

Z

0 1 2

Z -1 0 0

Lado Derecho

1 1 0

2 0 1

0 -3/5 4/5

0 1/5 -3/5

0 3/5 6/5

Ahora, se deben de hacer cero las variables de decisin

y

, y las restricciones quedan igual.2

(0)-(1) =

N(0)

Z -1

0

2

3/5

-1/5

LD -3/5

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

-

Z

0 1 2

Z -1 0 0

Lado Derecho

0 1 0

2 0 1

3/5 -3/5 4/5

-1/5 1/5 -3/5

-3/5 3/5 6/5

N(0)-[(2)*2] = N(0)*

Z -1

0

0

-1

1

LD -3

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

-

Z

0 1 2

Z -1 0 0

Lado Derecho

0 1 0

0 0 1

-1 -3/5 4/5

1 1/5 -3/5

-3 3/5 6/5

Ahora, se hace Smplex, con el fin de dejar los coeficientes positivos en el regln cero o ecuacin cero.Iteracin Variable Bsica Nmero de Ecuacin Coeficientes Lado Derecho Cociente Mnimo?

0

Z

0 1 2

Z -1 0 0

0 1 0

0 0 1

-1 -3/5

4/5

1 1/5 -3/5

-3 3/5 6/5

1,5

MIN

Variable bsica entrante:

Variable bsica saliente: Z 0 0 -1 LD 3/2 3/2 -3/2

(2)*(1/0,8) = N(2) (1)+[N(2)*0,6)] = N(1) (0)+N(2) = N(0)

0 1 0

5/4 3/ 4 5/4

1 0 0

-3/4 -1/4 1/4

2

El paso de hacer cero las variables de decisin, slo se hace cuando la funcin objetivo inicial es minimizar. Si es maximizar, este paso no se realiza.

3

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z -1 0 0 0 1 0 5/4 3/ 4 5/4 0 0 1 1/4 -1/4 -3/4

Lado Derecho

Cociente

Mnimo?

Z

0 1 2

-3/2 3/2 3/2

1

Ya no hay ms coeficientes negativos en regln cero. Fin de iteracin. La solucin bsica factible FINAL para este problema es: Z 3/2 3/2 0 3/2 0 0 0

EJERCICIO 2Resolver el siguiente problema usando el Mtodo de Dos Fases. Maximizar S. a

Desarrollo. Primero, se transforman las restricciones de desigualdad a igualdad, y se modifica la funcin objetivo, segn corresponda. (0) (1) (2) (3) A continuacin, se debe de eliminar las variables artificiales funcin objetivo. (0)-[M*(2)] => (0)*-[(3)*M] => (0)** => y , para luego eliminar el trmino M de la

=> Nueva ecuacin (0)* => Nueva ecuacin (0)** => Nueva FUNCIN OBJETIVO.

Ahora, se pasa a Smplex.

4

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

0

0 1 2 3

Z 1 0 0 0

Lado Derecho

Cociente

Mnimo?

-4 1 2

-4 2 3 1

0 1 0 0

0 0 1 0

1 0 0 -1

0 0 0 0

-20 12 12 8

12 6

2

4

MIN

Solucin Bsica Factible Inicial. Z -20

0

0

12

12

0

8

Variable bsica entrante:

Variable bsica saliente: Z 0 0 0 1 LD 4 4 8 -4

Ec(3)*1/2 Ec(2)-[NEC(3)*2] Ec(1)-NEC(3) Ec(0)+[NEC(3)*4]

NEC(3) NEC(2) NEC(1) NEC(0)

1 0 0 0

1/2 2 3/2 -2

0 0 1 0

0 1 0 0

-1/2 1 1/2 -1

0 0 0 0

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

1Solucin Bsica Factible.

0 1 2 3

Z 1 0 0 0

Lado Derecho

Cociente

Mnimo?

0 0 0 1

-2 3/2

0 1 0 0

0 0 1 0

-1 1 -1/2

0 0 0 0

-4 8 4 4

5

21/2

28

MIN

Z -4

4

0

8

4

0

0

Variable bsica entrante:

Variable bsica saliente: Z 0 1 0 0 LD 2 0 5 3

Ec(2)*(1/2) Ec(0)+[NEC(2)*2] Ec(1)-[NEC(2)*(3/2)] EC(3)-[NEC(2)*(1/2)]

NEC(2) NEC(0) NEC(1) NEC(3)

0 0 0 1

1 0 0 0

0 0 1 0

0,5 1 -0,75 -0,25

0,5 0 -0,25 -0,75

0 0 0 0

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

2

0 1 2 3

Z 1 0 0 0

Lado Derecho

0 0 0 1

0 0 1 0

0 1 0 0

1 0 -3/4 -1/4 1/2 1/2 -1/4 -3/4

0 0 0 0

0 5 2 3

Regln cero, no hay ms coeficientes negativos. Fin de iteracin. Solucin Bsica Factible. Z 0

3

2

5 5

0

0

0

Ahora, se eliminan las columnas de las variables artificialesIteracin Variable Bsica Nmero de Ecuacin

y

.Lado Derecho

Coeficientes

Z

-

0 1 2 3

Z 1 0 0 0

0 0 0 1

0 0 1 0

0 1 0 0

0 -1/4 1/2 -3/4

0 5 2 3

Ahora, se reemplazan los coeficientes del regln cero, por los coeficientes de la funcin objetivo original.Iteracin Variable Bsica Nmero de Ecuacin Coeficientes Lado Derecho

Z

Z

Ahora, se utiliza smplex.Iteracin Variable Bsica Nmero de Ecuacin

0 1 2 3

10 0 0

-30 0 1

-20 1 0

01 0 0

0-1/4 1/2 -3/4

05 2 3

Coeficientes

Z

0Variable bsica entrante:

0 1 2 3

Z 1 0 0 0

Lado Derecho

Cociente

Mnimo?

-3 0 0

1

-2 0 1 0

0 1 0 0

0 -1/4 1/2 -3/4

0 5 2 3

3

MIN

Variable bsica saliente: Z 1LD

Ec(0)+[Ec(3)*3]

NEC(0)

0

-2

0

-9/4

9

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

1Variable bsica entrante:

0 1 2 3

Z 1 0 0 0

Lado Derecho

Cociente

Mnimo?

0 0 0 1

-2 0

10

0 1 0 0

-9/4 -1/4 1/2 -3/4

9 5 2 3

2

MIN

Variable bsica saliente:

Ec(0)+[Ec(2)*2]

NEC(0)

Z 1

0

0

0

-5/4

LD 13

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

2

0 1 2 3

Z 1 0 0 0

Lado Derecho

Cociente

Mnimo?

0 0 0 1

0 0 1 0

0 1 0 0

-5/4 -1/4

1/2-3/4

13 5 2 3

4

MIN

6

Variable bsica entrante:

Variable bsica saliente: Z 0 1 0 0 LD 4 18 6 6

Ec(2)*2 Ec(0)+[NEC(2*(5/4)] Ec(1)+[NEC(2)*(1/4)] Ec(3)+[NEC(2)+(3/4)]

NEC(2) NEC(0) NEC(1) NEC(3)

0 0 0 1

2 5/2 1/2 3/2

0 0 1 0

1 0 0 0

Iteracin

Variable Bsica

Nmero de Ecuacin

Coeficientes

Z

3

0 1 2 3

Z 1 0 0 0

Lado Derecho

0 0 0 1

5/2 1/2 2 3/2

0 1 0 0

0 0 1 0

18 6 4 6

Ya no hay ms coeficientes negativos en regln cero. Fin de iteracin. La solucin bsica factible FINAL para este problema es: Z 18 6 0 6 0 4 0

7