Universidad Nacional de Ingeniería Sede: UNI-Norte Investigación de Operaciones I

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Ejemplo. Resolver el siguiente problema de P.L. Max z  4 x1  3x2 s. a:

x1  x2  40 2 x1  x2  60 x1 , x2  0

Para resolver por el método simplex revisado, primero debemos eliminar las desigualdades en las restricciones. Eso se logra introduciendo variables de holguras. En la primer restricción sumamos una variable x3 para establecer la igualdad. Lo mismo hacemos con la segunda, le sumamos una variable x4.

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Ejemplo. Modelo ampliado Max

max Z  CX s.a : AX  b X 0

Z  4 x1  3 x2  0 x3  0 x4 s.a : x1  x2  x3  40 2 x1  x2  x4  60 x1 , x2  0

Las variables de holguras que hemos introducidos en las restricciones, serán parte de la función objetivo pero tendrán coeficiente cero, ya que no deben alterar los resultados del modelo.

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal 1 1 1 0   A    2 1 0 1

c  4,3,0,0

 40  b     60 

 x1     x2  X   x3   x   4

La matriz A está conformada por los coeficientes de las ecuaciones de restricción. Esta matriz a su vez se subdivide en la submatriz B y la submatriz N. De igual manera la Matriz X se subdividirá en la submatriz XB (variables básicas) y XN (submatriz de variables no básicas). La matriz de costo se subdividirá en la submatriz de costos básica y no básicas. b: matriz del lado derecho. X: matriz de variables C : matriz de costos A : matriz de coeficientes

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Primera solución factible: comenzamos con la base B =(a3, a4), obviamente N(a1, a2) . Esto indica que:

1 0   B 1 B   0 1 CN  4,3

 1 1  N    2 1

 x3  X B     x4 

CB  0,0

XN

 x1      x2 

La primera solución factible se obtiene tomando como matriz base las variables de holgura introducidas al modelo.

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Iteración 0: Debemos obtener la primer solución factible.

cB  (0,0)  40  b     60 

X N  X   X  B  x3  XB     x4 

1 0 B   0 1   1

 x1  XN     x2 

 x3  1 0 40 40 XB  B b             x4  0 1 60 60 1

Z  CB X B

40  (0,0)     0 60

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Test de optimalidad Debemos investigar los coeficientes de la función objetivo. C N  CB B 1 N llamaremos w  CB B 1 Entonces:

1 w  (0,0) 0 

c N  wN c1  wa1  4  0  4 c2  wa2  3  0  3

Entra X1 a la base

0   (0,0)  1

Evaluamos los coeficientes de la función objetivo correspondiente a las variables no básicas, hasta encontrar una que sea estrictamente positiva. Nota: no es necesario calcular los coeficientes C j  wa j  j  Nobase Solamente debemos calcular hasta encontrar un coeficiente no negativo.

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Test de factibilidad Ahora tenemos que hallar la variable saliente, que más restricción pone cuando X1 comienza a crecer. Partimos de la ecuación. X B  B 1b  B 1 NX N  b  NX N  b  a1 x1

esta ecuación se reduce dado de B-1 = I. X1 dejará de ser cero pero X2 =0. En resumen: c N  wN  40   1 11    60    2 1  0  x3  40  x1      x4  60  2 x1 (sale x 4 )

Sale X4 de la base

 40  1    60    2  x1    

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Actualización: Para poder pasar a la próxima iteración (la cual comienza con el test de optimalidad) debemos actualizar la base de datos y con ella, los vectores/matrices B,N, XN, CB y CN. Todos ellos se hallan mediante un reordenamiento de sus componentes (donde estaba antes la columna/valor correspondiente a la variable entrante, ahora estará la de la variable saliente y viceversa). Iteración 1: Es decir B =(a3, a1), obviamente N(a4, a2), XB=(x3,x1), XN=(x4,x2), CB=(0,4), CN=(0,3). 1 B   0

1 1   B 1   2 0

1/ 2   1 / 2 

 x3   1 X B  B 1b    x    1  0

 1 / 2   40   10    60    30   1/ 2      

 10  Z  C B X B  (0,4)    30    120  

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Test optimalidad: Nuevamente volvemos a evaluar los coeficientes de la función objetivo correspondientes a los nuevas variables básicas. En primer lugar. 1 w  cB B 1  (0,4) 0 

c N  wN c4  wa4  0  0  0 c2  wa2  3  0  3

1/ 2    (0,2)  1/ 2 

Evaluamos los coeficientes de la función objetivo correspondiente a las variables no básicas, hasta encontrar una que sea estrictamente positiva.

Entra x2

Test factibilidad: Ahora tenemos que hallar restricciones pone cuando x2 comienza a crecer

la variable que más

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal X B  B 1b  B 1 NX N 1 X B   0

 1 / 2   40   1    1 / 2   60   0

1/ 2   1  1 / 2   0

1 1   x2 2 1

cN  wN x3  10  3 / 2 x2 (sale x 3 ) x1  30  1 / 2 x2

Para la siguiente iteración sale x3 y entra x2

Iteración 2: CB=(3,4), CN=(0,0), XB=(x2,x1), XN=(x4,x3), 1 1   2  1 1    B    B   1 2  1 1      x2   2 X B  B 1b    x    1   1

 1  40   20           1   60   20  

Julio Rito Vargas Avilés

Investigación de Operaciones

Método Simplex Revisado Programación Lineal Iteración 2:  20  Z  C B X B  (3,4)    20    60  80  140  

Solución factible (4,3,0,0) Esta es la solución óptima.

Z=140

Cuando sabemos que hemos terminado? Cuando no hay coeficientes estrictamente positivos en las variables no básicas.