Descripcion Del Metodo Simplex

Método Simplex

Ejemplo

Método Simplex
1. Transformar un sistema de desigualdades en otro de ecuaciones con variables de holgura: 0,02x1+0,04x2≤4800 0,02x1+0,04x2+1x3=4800 0,04x1+0,02x2≤6000 0,04x1+0,02x2+1x4=6000 (ecuaciones) 0,04x1+0,04x2≤6400 0,04x1+0,04x2+1x5=6400 Función objetivo a maximizar: z=6x1+4x2 z=6x1+4x2+0x3+0x4+0x5 2. Construir la tabla con los datos: 6 4 0 BASES CK P0 x1 x2x3 x3 0 4800 0,02 0,04 1 0 6000 0,04 0,02 0 ←x4 x5 0 6400 0,04 0,04 0 0 -4 0 -6↑ ↑ Zj-Cj →

0 x4 0 1 0 0

0 x5 0 0 1 0

Base: nº de variables, igual al nº de ecuaciones. CK: Coeficientes de las variables de la base en la función objetivo P0: Columna de términos independientes de las ecuaciones. Inicialmente, x3=4800, x4=6000, x5=6400, x1 y x2, no están en la base, valen 0. x1, x2, x3, ...,xn: Coeficientes de estas variables en cada una de las ecuaciones. En la fila superior se pone el valor de esas variables en la función objetivo. Valores de la última fila, por columnas: P0: Multiplicar la columna CK*P0 (multiplica los elementos de cada fila y sumar los productos: 0*488+0*6000+0*6400=0. Resto de valores: Sumar los productos de cada fila de los elementos CK*xk, y restarle elcoeficiente de la función objetivo (nº encima de la xk). Ejemplo: x1=0*0,02+0*0,04+0*0,04-6=-6, Los valores de las variables que están en la base son 0 (x3, ...) • El nº negativo de mayor valor absoluto de la fila Zj-Cj determina la columna de la variable entrante, en la base, (se marca con ↑ ) • Para determinar la variable que sale de la base, hacer el cociente entre los términos de P0 y los de lavariable entrante, en su misma fila, usando como divisores únicamente los valores positivos. x3: 4800/0,02=240000; x4: 6000/0,04=150000; x5: 6400/0,04=160000; la variable que obtiene el menor valor sale de la base (se marca con ←).

1

Método Simplex

Ejemplo

3. Iniciar segundo cuerpo de la tabla: (Cambia variable saliente por entrante) 6 x1 0,02 (0,04) 0,04 -6↑ ↑ 0 (1) 0 0 4 x2 0,04 0,02 0,04-4 *III 0,03 0,5 IV * 0,02 -1 ↑ 0 x3 1 0 0 0 1 0 0 0 0 x4 0 1 0 0 *V –0,5 25 VI * -1 150 0 x5 0 0 1 0 0 0 1 0

BASES CK x3 0 0 ←x4 x5 0 Zj-Cj → x3 0 x1 6 0 ←x5 Zj-Cj →

P0 4800 6000 6400 0 *I 1800 150000 *II 400 900000

La intersección de la columna entrante con la fila de la saliente, da la ubicación del pivote (0,04), transformarlo en 1, dividiendo la fila desde P0 en adelante por elvalor del pivote. Las variables que estaban en la base, y siguen estando, no modifican su columna. En la columna del pivote, el resto de los elementos son 0. En la columna CK, en la fila de la variable entrante, se pone el coeficiente que tiene dicha variable en la función objetivo (6). Los espacios * se completan con determinantes 2x2, tomando como diagonal principal (mantiene el signo del producto)la que contiene al pivote (1). 4800 0,02 (I) =4800-(0,02*150000)=4800-3000=1800. 150000 (1) 15000 (1) (II) =6400-(150000*0,04)=6400-6000=400. 6400 0,04 0,02 0,04 (III) =0,04-(0,02*0,5)=0,04-0,01=0,03. (1) 0,5 (1) 0,5 (IV) =0,04-(0,04*0,5)=0,04-0,02=0,02. 0,04 0,04 0,02 0 (V) =0-(0,02*25)= -0,5. (1) 25 (1) 25 (VI) =0-(0,04*25)= -1. 0,04 0 Para la fila Zj-CJ, Efectuar los productos de CK y loselementos de P0, x1, x2, ..., sumando los productos de la misma columna y restando el coeficiente de la variable en la función objetivo: P0 : (0*1800)+(6*150000)+(0*400)-0= 900000. X1: (0*0)+(6*1)+(0*0)-6= 0. X2: (0*0,3)+(6*0,5)+(0*0,2)-4= -1. X3: (0*1)+(6*0)+(0*0)-0= 0. X4: (0*0,5)+(6*25)+(0*(-1))-0= 150. X5: (0*0)+(6*0)+(0*1)-0= 0. Para saber la variable que sale de la base, se dividen loscoeficientes de P0, por los de la columna de la variable entrante (x2, valor -1 en la fila Zj-Cj). x3: 1800/0,03=60000; x1: 150000/0,5=300000; x5: 400/0,02=20000 (←). ← 2

Método Simplex

Ejemplo

4. Construir el tercer cuerpo de la tabla: (Cambia variable saliente por entrante) 6 x1 0,02 0,04 0,04 -6↑ ↑ 0 1 0 0 0 1 0 0 4 x2 0,04 0,02 0,04 -4 0,03 0,5 (0,02) -1 ↑ 0 0 (1) 0 0 x3 1 0 0 0 1 0 0 0 1 0...