Programacion lineal

Tarea N°1
MÉTODO SIMPLEX





1.- Se tiene el siguiente modelo de programación lineal.

Maximizar Z=2X1+X2-3X3+5X4
Sujeto a
X1+2X2-2X3+4X4≤40
2X1-X2+X3+2X4≤8
4X1-2X2+X3-X4≤10

X1,X2,X3,X4≥0

a) Resuelva el problema a través del método simplex
b) Identifique la solución óptima y el valor óptimo obtenido.Desarrollo:

Primero observamos que cumple con todas las condiciones para aplicar el método simplex, que son:
1. F.O. de Maximización
2. Todas los RHS deben ser positivos
3. Todas las variables deben ser no negativas

Forma estándar
Maximizar Z=2X1+X2-3X3+5X4
Sujeto a
X1+2X2-2X3+4X4 +S1 =402X1- X2+ X3+ 2X4 +S2 =8
4X1-2X2+ X3- X4 +S3=10
X1,X2,X3,X4,S1,S2,S3≥0
Forma equivalente
Maximizar Z
S.A.
0 Z-2X1-X2+3X3-5X4 =0
(1) X1+2X2-2X3+4X4 +S1 =40(2) 2X1- X2+ X3+ 2X4 +S2 =8
(3) 4X1-2X2+ X3- X4 +S3=10
X1,X2,X3,X4,S1,S2,S3≥0

Método simplex:

Tableau inicial
V.B. | N° Ec. | Z | Coeficientes | L.D. | Razón |
| | | X1 | X2 | X3 | X4 | S1 | S2 | S3 | | |
Z | 0 | 1 | -2 | -1 | 3 | -5 | 0 | 0 | 0 | 0 | ------ |
S1 | 1 | 0 | 1 | 2 | -2 | 4 | 1 | 0 | 0 | 40| 10 |
S2 | 2 | 0 | 2 | -1 | 1 | 2 | 0 | 1 | 0 | 8 | 4 |
S2 | 3 | 0 | 4 | -2 | 1 | -1 | 0 | 0 | 1 | 10 | ------ |

Variable básica de entrada (con su respectiva columna pivote):
X3
Variable básica de salida (con su respectiva fila pivote):
S2

Confección Nuevo Tableau.

Nueva Fila Pivote:

2 | -1 | 1 | 2 | 0 | 1 | 0 | 8 |
2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
1 | -0,5 | 0,5 | 1 | 0| 0,5 | 0 | 4 |

Nuevas filas:

Fila S1

1 | 2 | -2 | 4 | 1 | 0 | 0 | 40 |
4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
1 | -0,5 | 0,5 | 1 | 0 | 0,5 | 0 | 4 |
-3 | 4 | -4 | 0 | 1 | -2 | 0 | 24 |

Fila S3

4 | -2 | 1 | -1 | 0 | 0 | 1 | 10 |
-1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
1 | -0,5 | 0,5 | 1 | 0 | 0,5 | 0 | 4 |
5 | -2,5 | 1,5 | 0 | 0 | 0,5 | 1 | 14 |
Fila Z

-2 | -1 | 3| -5 | 0 | 0 | 0 | 0 |
-5 | -5 | -5 | -5 | -5 | -5 | -5 | -5 |
1 | -0,5 | 0,5 | 1 | 0 | 0,5 | 0 | 4 |
3 | -3,5 | 5,5 | 0 | 0 | 2,5 | 0 | 20 |

Segundo Tableau:

V.B. | N° Ec. | Z | Coeficientes | L.D. |
| | | X1 | X2 | X3 | X4 | S1 | S2 | S3 | |
Z | 0 | 1 | 3 | -3,5 | 5,5 | 0 | 0 | 2,5 | 0 | 20 |
S1 | 1 | 0 | -3 | 4 | -4 | 0 | 1 | -2 | 0 | 24 |
X4 | 2 | 0 | 1 | -0,5 | 0,5 |1 | 0 | 0,5 | 0 | 4 |
S2 | 3 | 0 | 5 | -2,5 | 1,5 | 0 | 0 | 0,5 | 1 | 14 |

Seguimos iterando, porque hay un coeficiente negativo

V.B. | N° Ec. | Z | Coeficientes | L.D. | Razón |
| | | X1 | X2 | X3 | X4 | S1 | S2 | S3 | | |
Z | 0 | 1 | 3 | -3,5 | 5,5 | 0 | 0 | 2,5 | 0 | 20 | ------ |
S1 | 1 | 0 | -3 | 4 | -4 | 0 | 1 | -2 | 0 | 24 | 6 |
X4 | 2 | 0 | 1 | -0,5 | 0,5 | 1 | 0 |0,5 | 0 | 4 | ------ |
S3 | 3 | 0 | 5 | -2,5 | 1,5 | 0 | 0 | 0,5 | 1 | 14 | ------ |

Variable básica de entrada (con su respectiva columna pivote):
X2
Variable básica de salida (con su respectiva fila pivote):
S1

Confección Nuevo Tableau.

Nueva Fila Pivote:

-3 | 4 | -4 | 0 | 1 | -2 | 0 | 24 |
4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
-3/4 | 1 | -1 | 0 | ¼ | -1/2 | 0 | 6 |

Nuevasfilas:

Fila X4

1 | -0,5 | 0,5 | 1 | 0 | 0,5 | 0 | 4 |
-1/2 | -1/2 | -1/2 | -1/2 | -1/2 | -1/2 | -1/2 | -1/2 |
-3/4 | 1 | -1 | 0 | ¼ | -1/2 | 0 | 6 |
5/8 | 0 | 0 | 1 | 1/8 | 1/4 | 0 | 7 |

Fila S3

5 | -2,5 | 1,5 | 0 | 0 | 0,5 | 1 | 14 |
-5/2 | -5/2 | -5/2 | -5/2 | -5/2 | -5/2 | -5/2 | -5/2 |
-3/4 | 1 | -1 | 0 | ¼ | -1/2 | 0 | 6 |
25/8 | 0 | -1 | 0 | 5/8 | -3/4 | 1 | 29 |...