Método simplex. Teoria

Uso del Método Simplex

1. MÉTODO SIMPLEX
•Procedimiento general para resolver problemas de programación
lineal.
•DesarrolladoporGeorgeDantzigen1947.
•Es un procedimiento algebraico aunque sus conceptos
fundamentalessongeométricos.
•Está basado en un algoritmo o series de pasos donde se evalúan
loscriteriosdeOptimalidadyFactibilidad
•Sepuedenusarcon2omásvariablesdedecisión.

2. FunciónObjetivo:
MaxZ=5X
1+4X
2
Restricciones
:
MÉTODO SIMPLEX
Restricciones
:
1. 6X
1+4X
2<=24
2. X
1+ 2X
2<= 6
3. -X
1+ X
2<= 1
4. X
2<= 2
5. X
1,X
2>= 0

3. Pasos:
1. Transformar la función Z y las restricciones a igualdades e
introducir las variables de holgura o de exceso de acuerdo al
casodelarestricción,estasvariablestambiéndenominadasno
básicas
se
determinan
en
función
del
número
de
restricciones
MÉTODO SIMPLEX
básicas
se
determinan
en
función
del
número
de
restricciones
presentesenelmodelo:
•Enel casode lasrestriccionessi son<= se conviertenen=
pero se introducen variables de holgura o variables básicas
consignopositivo
•Enelcasodelasrestriccionessison>= seconviertenen=

4. Pasos:
•pero se introducen variables de exceso o variables básicas
consignonegativo
Ennuestroejemplobaseestepasoquedadelasiguienteforma
Z
-
5
X
-
4
X
+
0
X
+
0
X
+
0
X
+
0
X
=
0
MÉTODO SIMPLEX
Z
-
5
X
1
-
4
X
2
+
0
X
3
+
0
X
4
+
0
X
5
+
0
X
6
=
0
6X
1+4X
2+X
3+0X
4+0X
5+0X
6=24
X
1+2X
2+0X
3+X
4+0X
5+0X
6=6
-X
1+X
2+0X
3+0X
4+X
5+0X
6=1
0X
1+X
2+0X
3+0X
4+0X
5+X
6=2
X
1,X
2,X
3,X
4,X
5,X
6>=0

5. Pasos:
2. ConstruirlatablaoriginaldepartidadelMétodoSimplex
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z 1 -5 -4 0 0 0 0 0 Z X
3
0 6 4 1 0 0 0 24 X
3

Variablesnobásicas(ceros)(X
1yX
2)
Variablesbásicas(X
3,X
4,X
5,X
6)
X
4
0 1 2 0 1 0 0 6 X
4

X
5
0 -1 1 0 0 1 0 1 X
5

X
6
0 0 1 0 0 0 0 2 X
6

6. Pasos:
3. Identificar que Variable sale y cual entra utilizando los
criteriosdeoptimalidadydefactibilidadrespectivamente
•Criterio de Optimalidad:Si el problema es de
Maximización
la
variable
no
básica
que
entra
es
la
que
MÉTODO SIMPLEX
Maximización
la
variable
no
básica
que
entra
es
la
que
tiene el coeficiente más negativo en el renglón Z, si el
problema es Minimización la variable no básica que
entra es la que tiene el coeficiente más positivo en el
renglónZ.Enelcasodequehubieseempatesserompen
enformaarbitraria.Sellegaalóptimoenlaiteraciónen

7. Pasos:
•la que todos los coeficientes de las variables no básicas
son positivas (si el problema es Maximización) o son
positivas(sielproblemaesMinimización).
Criterio
de
Factibilidad
:
Independientemente
si
el
MÉTODO SIMPLEX
•
Criterio
de
Factibilidad
:
Independientemente
si
el
problemaesdemaximizaciónyminimización,lavariable
de salida es la variable básica asociada con la mínima
razón no negativa (con denominador estrictamente
positivo).Losempatesserompenenformaarbitraria.

8. Pasos:
Ennuestroejemplobaseestepasoquedadelasiguienteforma
MÉTODO SIMPLEX
Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

Renglón

Z

1

-
5

-
4

0

0

0

0

0

Z

Z

1

-
5

-
4

0

0

0

0

0

Z

X
3

0

6

4

1

0

0

0

24

X
3

X
4
0
1 2 0 1 0 0 6 X
4

X
5

0

-
1

1

0

0

1

0

1

X
5

X
6
0
0 1 0 0 0 0 2 X
6

9. Pasos:
PortantosedividelaSoluciónentrecadacoeficientedelaColumna
X
1porserlavariablequeentraenestemomentoportanto
MÉTODO SIMPLEX
Básicas

Solución

X
1

Nueva Solución

X
3

24

6

4
624
=

6
X
4
6 1
6
16
=

X
5

1

-
1

1
1
1
-=
-

X
6
2 0
¥=
02

10. Pasos:
En función de este cálculo se desecha los valores negativos y los
indeterminadospornocumplirelcriteriodefactibilidad,portanto
quedaX
3con 3 yX
4con 6 para aplicar dicho criterio, por tanto se
tomaX
3con3porserelvalormáspequeño.
MÉTODO SIMPLEX
Columna Pivote (X
1) Variable que entra (X
1) Fila Pivote (X
3) Variable que sale (X
3) Elemento
Pivote: 6
Básica Z
X
1
X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z 1
-5 -4 0 0 0 0 0 Z
X
3

0

6

4

1

0

0

0

24

X
3

X
4
0
1 2 0 1 0 0 6 X
4

X
5

0

-
1

1

0

0

1

0

1

X
5

X
6
0
0 1 0 0 0 0 2 X
6

11. Pasos:
Iteración#1:
Aplicando el Método de Gauss – Jordan para obtener la nueva
soluciónbásica
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z

1

0

-
2/3

5/6

0

0

0

20

Z

X
1

0

1

2/3

1/6

0

0

0

4

X
1

X
4

0 0 4/3 -1/6 1 0 0 2
X
4

X
5

0 0 5/3 1/6 0 1 0 5
X
5

X
6

0 0 1 0 0 0 0 2
X
6

12. Pasos:
Iteración#1:
NuevaFilaPivote (NFP)X
1=FilaPivoteX
3/ElementoPivote
MÉTODO SIMPLEX
Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

X
1

0
/6

6
/6

4
/6

1
/6

0
/6

0
/6

0
/6

24
/
6


Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

X
1

0

1

2/3

1
/6

0

0

0

4

13. Pasos:
NuevaZ=ZAnterior+(NFPX
1*(-)CoeficientedelaColumnaPivote
X
1)
MÉTODO SIMPLEX Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

Z
anterior

1

-
5

-
4

0

0

0

0

0

anterior

NFP
X
1

0
*5

1*5

(2/3) *5

(
1
/6)*5

0
*5

0
*5

0
*5

4
*5


Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
Z
anterior

1

-
5

-
4

0

0

0

0

0


+

NFP
X
1

0

5

10/3

5/6

0

0

0

20

Nueva Z

1 0 -2/3 5/6 0 0 0 20

14. Pasos:
Nueva X
4=X
4Anterior + (NFPX
1* (-)Coeficiente de la Columna
PivoteX
1)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
4
anterior

0 1 2 0 1 0 0 6
NFP X
1
0*-1 1*-1 (2/3) *-1 (1/6)*-1 0*-1

0*-1

0*-1

4*-1

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
4
anterior

0 1 2 0 1 0 0 6
+
NFP X
1
0 -1 -2/3 -1/6 0

0

0

-4
Nueva
X
4

0 0 4/3 -1/6 1 0 0 2

15. Pasos:
Nueva X
5=X
5Anterior + (NFPX
1* (-)Coeficiente de la Columna
PivoteX
1)
MÉTODO SIMPLEX
Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

X
5
anterior

0

-
1

1

0

0

1

0

1

NFP
X
1

0
*1

1*1

(2/3) *1

(
1
/6)*1

0
*1

0
*1

0
*1

4
*1


Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución


X
5
anterior

0

-
1

1

0

0

1

0

1


+
NFP
X
1

0

1

2/3

1/6

0

0

0

4

N
ueva X
5

0

0

5
/3

1/6

0

1

0

5

16. Pasos:
Nueva X
6=X
6Anterior + (NFPX
1* (-)Coeficiente de la Columna
PivoteX
1)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
6
anterior

0 0 1 0 0 0 0 2
NFP X
1
0*0 1*0 (2/3) *0 (1/6)*0 0*0

0*0

0*0

4*0

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
6
anterior

0 0 1 0 0 0 0 2
+
NFP X
1
0 0

0

0

0

0

0

0

Nueva
X
6

0 0 1 0 0 0 0 2

17. Pasos:
Iteración#2:Aplicandoloscriteriosdeoptimalidadyfactibilidad
MÉTODO SIMPLEX
Básica

Z

X
1

X
2

X
3

X
4

X
5

X
6

Solución

Renglón

Z

1

0

-
2/3

5/6

0

0

0

20

Z

X

0

1

2/3

1/6

0

0

0

4

X

X
1

0

1

2/3

1/6

0

0

0

4

X
1

X
4

0

0

4/3

-
1/6

1

0

0

2

X
4

X
5

0

0

5/3

1/6

0

1

0

5

X
5

X
6
0 0
1 0 0 0 0 2 X
6

18. Pasos:
PortantosedividelaSoluciónentrecadacoeficientedelaColumna
X
2porserlavariablequeentraenestemomentoportanto
MÉTODO SIMPLEX
Básicas

Solución

X
2

Nueva Solución

X
1
4 2/3
6
2
12
32
1
4
= =

3
X
4
2 4/3
5,1
4
6
3
4
1
2
= =

X
5
5 5/3
3
5
15
3
5
1
5
= =

X
6
2 1
2
12
=

19. Pasos:
En función de este cálculo queda X
4con 1,5 por ser el valor más
pequeño.
MÉTODO SIMPLEX
Básica Z X
1

X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z 1 0
-2/3 5/6 0 0 0 20 Z
X
1

0

1

2/3

1/6

0

0

0

4

X
1

ColumnaPivote(X
2)Variablequeentra(X
2)FilaPivote(X
4)Variable
quesale(X
4)ElementoPivote:4/3
X
1

0

1

2/3

1/6

0

0

0

4

X
1

X
4

0
0
4/3
-1/6
1
0
0
2 X
4

X
5
0 0
5/3 1/6 0 1 0 5 X
5

X
6
0 0
1 0 0 0 0 2 X
6

20. Pasos:
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z
1 0 0 3/4 1/2 0 0 21
Z
X
1

0 1 0 1/4 -1/2 0 0 3
X
1

X
2

0

0

1

-
1/8

3/4

0

0

3/2

X
2

X
2

0

0

1

-
1/8

3/4

0

0

3/2

X
2

X
5

0 0 0 3/8 -5/4 1 0 5/2
X
5

X
6

0 0 0 1/8 -3/4 0 0 1/2
X
6

21. Pasos:
NuevaFilaPivote (NFP)X
2=FilaPivoteX
4/ElementoPivote
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

X
2

10

10

34

6
1
-

11

10

10

12

3
4
1

3
4
1

3
4
3

3
4
6

3
4
1

3
4
1

3
4
1

3
4
1


Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

X
2
0 0 1 -1/8 3/4

0

0

3/2

22. Pasos:
NuevaZ=ZAnterior+(NFPX
2*(-)CoeficientedelaColumnaPivote
X
2)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6

Solución
Z
anterior

1 0 -2/3 5/6 0 0 0 20
NFP X
2

0* 2/3 0* 2/3 1* 2/3 -1/8* 2/3 3/4* 2/3 0* 2/3 0* 2/3 3/2* 2/3

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
Z
anterior

1

0

-
2/3

5/6

0

0

0

20


+
NFP X
2
0 0 2/3 -1/12 1/2

0

0

1
Nueva Z

1 0 0 3/4 1/2 0 0 21

23. Pasos:
Nueva X
1=X
1Anterior + ((NFPX
2* (-)Coeficiente de la Columna
PivoteX
2)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

X
1
anterior

0 1 2/3 1/6 0

0

0

4
NFP X
2

0* -2/3 0* -2/3 1* -2/3 -1/8* -2/3 3/4* -2/3 0* -2/3 0* -2/3 3/2* -2/3

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
1
anterior

0 1 2/3 1/6 0

0

0

4
+
NFP X
2
0 0 -2/3 1/12 -1/2

0

0

-1
Nueva
X
1

0 1 0 1/4 -1/2 0 0 3

24. Pasos:
Nueva X
5=X
5Anterior + (NFPX
2* (-)Coeficiente de la Columna
PivoteX
2)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6

Solución
X
5
anterior

0 0 5/3 1/6 0 1 0 1
NFP
X

0*
-
5
/3

0*
-
5
/3

1
*
-
5
/3

-
1/8
*
-
5
/3

3/4
*
-
5
/3

0*
-
5
/3

0*
-
5
/3

3/
2*
-
5
/3
NFP
X
2

0*
-
5
/3

0*
-
5
/3

1
*
-
5
/3

-
1/8
*
-
5
/3

3/4
*
-
5
/3

0*
-
5
/3

0*
-
5
/3

3/
2*
-
5
/3

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
5
anterior

0 0 5/3 1/6 0 1 0 5
+
NFP X
2
0 0 -5/3 5/24 -5/4

0

0

-5/2
Nueva
X
5

0 0 0 3/8 -5/4 1 0 5/2

25. Pasos:
Nueva X
6=X
6Anterior + (NFPX
2* (-)Coeficiente de la Columna
PivoteX
2)
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
6
anterior

0 0 1 0 0 0 0 2
NFP X
2

0* -1 0* -1 1* -1 -1/8* -1 3/4* -1 0* -1 0* -1 3/2* -1

Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución
X
6
anterior

0 0 1 0 0 0 0 2
+
NFP X
2
0 0

-1

1/8

-3/4

0

0

-3/2

Nueva
X
6

0 0 0 1/8 -3/4 0 0 1/2

26. Pasos:
Como no hay más valores negativos o en otras palabras hay
solamente valores positivos en la fila de Z se detiene el algoritmo
simplexquedandoZcon21,X
1con3yX
2con1,5.
MÉTODO SIMPLEX
Básica Z X
1
X
2
X
3
X
4
X
5
X
6
Solución

Renglón

Z
1
0
0
3/4
1/2
0
0
21
Z
X
1

0
1
0
1/4
-1/2
0
0
3
X
1

X
2

0
0
1
-1/8
3/4

0

0

3/2
X
2

X
5

0 0 0 3/8 -5/4 1 0 5/2
X
5

X
6

0 0 0 1/8 -3/4 0 0 1/2
X
6