• Author / Uploaded
• Jesus Urrieta

Citation preview

Objetivo Nro. 02 Obtener la solución de un problema de Programación Lineal Utilizando el método Simplex en forma Tabular

Realizado por: Edenny Flores C.I: 17.228.208 Francisco Toth C.I.: 7426034

El Problema Dado el siguiente problema de programacion lineal resolverlo usando el metodo simplex de forma tabular: Maximizar:

z = 2x1 – 4x2 + 5x3 - 6x4 Sujeto a:

x1 + 4x2 - 2x3 + 8x4 ≤ 2 (1) -x1 + 2x2 + 3x3 + 4x4 ≤ 1 (2) x1, x2 , x3 , x4 ≥ 0 (3)

● Desigualdad del tipo ≤ sumamos una variable

de holgura en cada restricción

● Igualamos la función objetivo a cero

Maximizar z-2x1 +4x2 - 5x3 + 6x4 - 0x5 - 0x6 = 0 sujeto a: x1 + 4x2 - 2x3 + 8x4 + x5 = 2 - x1 + 2x2 + 3x3 + 4x4 + x6 = 1 x1, x2 ≥ 0

Ahora construimos la tabla con los coeficientes tanto de la función objetivo, y las restricciones: Maximizar z-2x1 +4x2 - 5x3 + 6x4 - 0x5 - 0x6 = 0 sujeto a: x1 + 4x2 - 2x3 + 8x4 + x5 = 2 - x1 + 2x2 + 3x3 + 4x4 + x6 = 1 x1, x2 ≥ 0 VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

-2

4

-5

6

0

0

0

x5

0

1

4

-2

8

1

0

2

x6

0

-1

2

3

4

0

1

1

VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

-2

4

-5

6

0

0

0

x5

0

1

4

-2

8

1

0

2

x6

0

-1

2

3

4

0

1

1

Buscamos la columna pivote, para esto observamos las variables de decisión (x1, x2, x3 y x4) en la primera fila o la fila de la función objetivo, y vemos que coeficiente de estas es el mas negativo, en este caso (-5 correspondiente a x3) Para buscar el renglón pivote, dividimos los factores correspondientes a la columna de SOL entre el que le corresponde de la columna pivote “solo para las restricciones y escogemos el menor valor positivo, es decir: 2/-2=-1 y 1/3= 1/3, por lo tanto el elemento pivote es el

elemento que se encuentra en la intersección de la columna pivote y el renglón pivote en este caso es : 3

Iteración 01 Debemos hacer el elemento pivote ”1” , para esto debemos dividir entre 3 todo el renglon donde se encuentra el elemento pivote, ósea:

1/3 f3 (1/3 por fila 3)

Debemos hacer cero el resto de los coeficientes en la columna pivote, para esto hacemos las siguientes operaciones: f2+2/3f3 y f1 +5/3f3 VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

-2

4

-5

6

0

0

0

x5

0

1

4

-2

8

1

0

2

x6

0

-1/3

2/3

1

4/3

0

1/3

1/3

Las operaciones serian:

1/3 f3: 0/3= 0; -1/3=-1/3; 2/3= 2/3; 3/3=1; 4/3= 4/3; 0/3 = 0; 1/3= 1/3 y 1/3 =1/3 f2+2/3f3 f2

0

1

4

-2

8

1

0

2

2/3f3

0

-2/3

4/3

2

8/3

0

2/3

2/3

F2+2/3f3

0

1/3

16/3

0

32/3

1

2/3

8/3

Y la siguiente operación es f1+5/3 f3 f1

1

-2

4

-5

6

0

0

0

5/3f3

0

-5/3

10/3

5

20/3

0

5/3

5/3

f1+5/3f3

1

-11/3

22/3

0

38/3

0

5/3

5/3

Nueva tabla: sale la variable de holgura X6 y entra la variable X3 en la columna de VB

 

VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

-11/3

22/3

0

38/3

0

5/3

5/3

x5

0

1/3

16/3

0

32/3

1

2/3

8/3

x3

0

-1/3

2/3

1

4/3

0

1/3

1/3

Ahora debemos hacer 1/3, 1 y el resto de coeficientes (-11/3 y – 1/3 en la columna pivote cero), para esto hacemos las siguientes operaciones : 2da Iteracion:

3f2 f3+f2 f1+11f2 VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

-11/3

22/3

0

38/3

0

5/3

5/3

x5

0

1/3

16/3

0

32/3

1

2/3

8/3

x3

0

-1/3

2/3

1

4/3

0

1/3

1/3

Las operaciones serian: 3f2 3f2

0

1

16

0

32

1

2

8

0

Y la siguiente operación es f3+f2 f2

0

1/3

16/3

0

32/3

1

2/3

8/3

f3

0

-1/3

2/3

1

4/3

0

1/3

1/3

F3+f2

0

0

6

1

12

1

1

3

Y la otra operación es f1+11f2 f1

1

-11/3

22/3

0

38/3

0

5/3

5/3

11f2

0

11/3

176/3

0

352/3

11

22/3

88/3

f1+11f2

1

0

66

0

130

11

9

31

Nueva tabla: sale la variable de holgura X5 y entra la variable X3 en la columna de VB VB

z

X1

X2

X3

X4

X5

X6

SOL

Z

1

0

66

0

130

11

9

31

x1

0

1

16

0

32

1

2

8

x3

0

0

6

1

12

1

1

3

Ahora vemos si terminamos, para esto observamos los coeficientes de las variables de decisión en la función objetivo y vemos que todos son positivos por lo tanto tenemos una solución optima donde:

Z= 31 X1=8 X3=3