Industrial

Solo disponible en BuenasTareas
  • Páginas : 8 (1869 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de septiembre de 2010
Leer documento completo
Vista previa del texto
PROCEDIMIENTO SIMPLEX REVISADO
Este método requiere una menor cantidad de cálculos, ya que realiza cálculos únicamente en los vectores de aquellas variables no-básicas y registra en memoria lo relativo a las variables básicas, B −1 , c B B −1 , x B y c B x B (así como todos los valores iniciales cj, aij y b i). Pasos: ♦ Determinar las variables básicas y formar B. ♦ Obtener B −1 . ♦ Obtener z j− c j = wa j − c j . Donde W = c B B −1 Si z j − c j ≤ 0 para un problema de minimización o z j − c j ≥ 0 para un problema de maximización la solución es óptima y es el fin del proceso. Si esto no se cumple continúe el proceso. ♦ Determinar la variable que entra en solución (sea esta x k ) usando WA-C para toda variable no-básica ( wi a j − c j ). ♦ Se analiza
xBi (para toda i) para determinar quela variable sale de solución, ykj

sea ésta x f . Ahora actualice la columna a k para que ésta aporte la columna de la matriz identidad que aportaba la variable saliente x f . ♦ Regresar al principio del proceso, realizar los cálculos necesarios para sacar de la base a x f y meter a la misma x k (actualice la columna a k para que esta aporte la columna de la matriz identidad que aportaba lavariable saliente x f ). Procedimiento: Si Z = c B X B donde X B = B −1 A , entonces Z = c B B −1 A equivale a z j = c B B −1 a j y si W = c B B −1 entonces ahora WA − C = Z − C equivale a wi a j − c j = z j − c j .

Base de la inversa W B-1

Lado derecho CBXB XB

Tablas en el proceso
W

CB X B

B

−1

x B1 xB2 M x Bm

xk z k − ck y 1k y2k

M y mk

Ejemplo:
Max Z = 5 x1 + 3 x 2Sujeto a: 3 x1 + 5 x 2 ≤ 15

5 x1 + 2 x 2 ≤ 10 x1 , x 2 ≥ 0
Así:
x1 3 A= 5 x2 5 2 x3 1 0 x4 0 1 

C = [5

3

0

0

]

15 b=  10

Analizando para todas las variables no-básicas: x1 x2

z j − c j = WA − C = [0

3 ] 0 5

5 − 5 2 

[

3 = −5 ][

3

]

por lo que entra en solución x1 . Tabla 1

y1
0 0 1 0 0 1
0 15

10

x3 x4

−5 3

5

←Sale x 4

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 4 ) se tiene:

0 1 0

1 −3 5 15

10 9 2

x3 x1

Analizando para todas las variables no-básicas:
x2 x4  5 0 z j − c j = WA − C = [ 0 1 ]  − 3 [ 0 = ]−1[ 1 2 1

]

por lo que entra en solución x 2 . Tabla 2

y2 0 1 0 1 −3 515 10 9 2 x3 x1 −2 19 5 25 ← Sale x 3

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 3 ) se tiene:

5 19 5 19 − 2 19

16 19 − 3 19 5 19

235 19 45 19 20 19

Analizando para todas las variables no-básicas: x3 x4

0 1 [ ] 16 19 , ] 0 = [5 19 16 19  ] − 0 1 0  Como todos los valores sonmayores que cero la solución óptima se ha alcanzado. z j − c j = WA − C = [5 19
Solución óptima:

Z = 325 19 x1 = 20 19 x 2 = 45 19

Ejemplo:
Método de la M Min Z = 3 x1 + 2 x 2 Sujeto a: 3 x1 + x 2 ≥ 3

4 x1 + 3 x 2 ≥ 6 x1 + x 2 ≤ 3 x1 , x 2 ≥ 0
3 x1 + x 2 − x 3 + x6 =3

4 x1 + 3 x 2 − x4 + x7 = 6 x1 + x 2 + x5 =3 x 6 y x 7 son variables artificiales
Así:

x1 3 A = 4  1 

x2 13 1

x3

x4

x5 0 0 1

x6 1 0 0

x7 0 1  0 
C = [3 2 0 0 0 M M]

-1 0 0 -1 0 0

3 b = 6    3  

Analizando para todas las variables no-básicas:

x1 C B B −1 a j − c j = z j − c j = WA − C = [M C B B −1 a j − c j = z j − c j = WA − C = [7 M M 4M 3 ] 0 4  1  −M

x2 1 3 1

x3

x4

C B B −1 a j − c j = z j − c j = WA − C = [7 M − 3 4M − 2 − M
Entra ensolución x1 por tener el valor más positivo. Tabla 1

[ − M ]− 3 2 0 0]
− M]

- 1 0 0 - 1 − [3 2 0 0  0 0 

]

M 1

M 0 0 0

0 0

1 0

0 1

9M 3 6 3

x6 x7 x5

y1 7M − 3 3

← Sale x 6

4 1

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 6 ) se tiene:

− 4 3M +1 13...
tracking img