Simplex revisado

M´todo Simplex Revisado e
Daniel Severin
A continuaci´n, vamos a resolver el ejercicio 7 de la pr´ctica 4. El enuno a ciado dice: Resolver el siguiente problema mediante el m´todo simplex revisado.e m´x z = −2x2 + x3 a s/a x1 − 2x2 + x3 ≥ −4 x1 + x2 + x3 ≤ 9 2x1 − x2 − x3 ≤ 5 x 1 , x2 , x3 ≥ 0 Preliminares. Lo primero que debemos hacer es convertir el problema a su forma standard. En nuestrocaso, m´x z = −2x2 + x3 a s/a −x1 + 2x2 − x3 + x4 = 4 x1 + x2 + x3 + x5 = 9 2x1 − x2 − x3 + x6 = 5 x 1 , x2 , x3 ≥ 0 Matricialmente, m´x z = c.x a s/a A.x = b x≥0

1

donde,       4 −1 2 −11 0 0  ,b =  9 ,x =   1 1 1 0 1 0 A=   5 2 −1 −1 0 0 1   x1 x2 x3 x4 x5 x6        

y c = (0, −2, 1, 0, 0, 0). Estos vectores/matrices van a permanecer constantes a lo largo delejercicio. No obstante, cuando introduzcamos B, N , xB , xN , cB y cN , estos ultimos van a variar seg´n la base establecida en cada iteraci´n. ´ u o B´ squeda primer soluci´n factible. El problema esorigen factible, u o as´ que no tenemos necesidad de utilizar el m´todo de las dos fases. Simı e plemente, podemos comenzar con la base B = (a4 , a5 , a6 ). Obviamente, N = (a1 , a2 , a3 ). Esto indicaque,         1 0 0 x1 −1 2 −1 x4 1 1  , xB =  x 5  , xN =  x 2  , B =  0 1 0  = B −1 , N =  1 x3 0 0 1 x6 2 −1 −1 cB = (0, 0, 0) y cN = (0, −2, 1). Test de optimalidad. Recordemos laforma general del diccionario, xB = B −1 .b − B −1 .N.xN . z = cB .B −1 .b + (cN − cB .B −1 .N ).xN Debemos investigar los coeficientes de la funci´n objetivo (i.e. cN −cB .B −1 .N ). o Llamemos w alvector que resulta del producto cB .B −1 . Utilizando la primer soluci´n factible hallada, cB resulta ser el vector nulo, as´ que tambi´n o ı e w = (0, 0, 0). Lo siguiente es evaluar los coeficientes dela funci´n objetivo (correspondieno tes a las variables no b´sicas) hasta encontrar uno que sea estrictamente a positivo: c1 − w.a1 = 0, c2 − w.a2 = −2, c3 − w.a3 = 1, por lo tanto entra x3 a la...