06 método simplex

1. Programación Lineal
Método Simplex

2. IO1 R.Delgadillo 2
Método Simplex
Idea conceptual:
 Desde que las soluciones que
optimizan la F.O. se encuentran en la
frontera de la región Factible y en
particular en los vértices de esta. El
simplex localiza un vértice de la región
y salta para el siguiente vértice
adyacente de forma que mejore el valor
de la F.O.

3. IO1 R.Delgadillo 3
Método Simplex
Ejemplo:
max z = 3x1 + 4x2
s.a. x1 + x2 < 9
x1 + 2 x2 < 16
x1, x2 > 0

4. IO1 R.Delgadillo 4
Método Simplex
9,0

2,7
0,8
16,0
0,9

5. IO1 R.Delgadillo 5
Sistema de ecuaciones lineares
Dado Ax = b , A de dimensión m x n, x de
dimensión n y b de dimensión m
Si la matriz A es inversible ( esto es m=n) =>
Ax = b , tiene como única solución x=Ab
por otro lado, si el rango de la matriz
aumentada (A|b) es mayor que el rango de la
matriz A => Ax = b no tiene solución.
Si el rango de (A|b) es igual al rango de A e
igual k < n, => Ax = b tiene infinitas soluc.

6. IO1 R.Delgadillo 6
Método Simplex (conceptos)
Dado Ax = b, un sistema de ecuaciones
consistente indeterminado (n>m)
Se puede escribir: A= (B,N) , donde
Bmxm inversible y Nmx(n-m). Las columnas
de la matriz B, son vectores de
dimensión m , que constituyen una
base del espacio R, denominase a B
como matriz básica.

m

7. IO1 R.Delgadillo 7
Método simplex
Sea Equivalente
max z = Cx max z = CBxB +CN xN
s.a. s.a.
Ax = b BxB + NxN = b
x > 0 xB > 0, xN > 0
de donde:
xB = B b – B NxN
z = CBB b -(CB B N -CN ) xN

-1 -1
-1 -1

8. IO1 R.Delgadillo 8
Método simplex
En la tabla:
xN xB
xB B N I B b
-z CBB N-CN 0 CBB b
Una solución inicial es:
 xN = 0, xB = B b, z= CBB b

-1
-1
-1
-1
-1
-1
-1

9. IO1 R.Delgadillo 9
Método Simplex (algoritmo)
1. Determine una solución básica factible
2. Verifique si la solución es óptima: vea si los
costos reducidos en el tablero son ceros o
negativos, en ese caso pare, Sol óptima.
3. Determine una nueva solución básica
factible:
-variable que entra a la base xj = coef más
positivo
-variable que sale de la base = min{B b/a.j/
a.j>0}
4. Regresar a paso 2
-1

10. IO1 R.Delgadillo 10
Método Simplex
x1 x2 x3 x4
x3 1 1 1 0 9
x4 1 2* 0 1 16
-z 3 4 0 0 0
x3 1/2* 0 1 -1/2 1
x2 1/2 1 0 1/2 8
-z 1 0 0 -2 -32
VB={x3=9,x4=16}
VNB={x1=x2=0}

11. IO1 R.Delgadillo 11
Método Simplex
x1 x2 x3 x4
x1 1 0 2 -1 2
x2 0 1 -1 1 7
-z 0 0 -2 -1 -34

sol óptima x1=2, x2=7, x3=4, x4=0
z= 34

12. IO1 R.Delgadillo 12
Método Simplex
Ejemplo:
Max z= x1 + 2 x2
s.a.
-2x1 + x2 < 7
x1 - x2 < 2
x1, x2 > 0
En la forma normal
Max z= x1 + 2 x2
s.a.
-2x1 + x2 + x3 = 7
x1 - x2 + x4 = 2
x1, x2, x3, x4 > 0

13. IO1 R.Delgadillo 13
Método Simplex
x1 x2 x3 x4
x3 -2 1* 1 0 7
x4 1 -1 0 1 2
-z 1 2 0 0 0
x2 -2 1 1 0 7
x4 -1 0 1 1 9
-z 5 0 -2 0 -14
B a.j<0, =>
z->oo (óptimo
no-finito)
-1

14. IO1 R.Delgadillo 14
Método Simplex
Ejemplo:
Max z = 15x1 + 30 x2
s.a.
4x1 + x2 + x3 = 36
x1 +2x2 + x4 = 30
x1, x2, x3, x4 > 0

15. IO1 R.Delgadillo 15
Método Simplex
x1 x2 x3 x4
x3 4 1 1 0 36
x4 1 2* 0 1 30
-z 15 30 0 0 0
x3 7/2* 0 1 -1/2 21
x2 1/2 1 0 1/2 15
-z 0 0 0 -15 -450
Obs: Los costos
reducidos asociados
a las VB son 0,y de
las VBN son diferente
de cero
Sol.óptima

16. IO1 R.Delgadillo 16
Método Simplex
x1 x2 x3 x4
x1 1 0 2/7 -1/7 6
x2 0 1 -1/7 4/7 12
-z 0 0 0 -15 -450

Soluciones óptimas alternativas:
x3=21, x2=15, x1=x4=0, Z=450
x1=6, x2=12, x3=x4=0, Z=450
Otra Sol.
óptima

17. IO1 R.Delgadillo 17
Método Simplex
Problema de mínimo:
Primer caso: hacer Min z = Max (-z)
y efectuar el algoritmo para resolver el
problema de mínimo.
Segundo caso: modificar algoritmo
-variable que entra a la base xj = coef
más negativo
- condición de parada es todos los
costos reducidos son ceros o positivos.

18. IO1 R.Delgadillo 18
Ejercicios
Resuelva por la tabla del simplex los
siguientes problemas:
Max 2x1 + 7x2
sujeto a:
3x1 + 4x2 <= 12
x1 + 8x2 <= 8
6x1 + x2 <= 15
x1, x2 >= 0

19. IO1 R.Delgadillo 19
Ejercicio
Min 50 x1 + 100 x2
Sujeto a:
7 x1 + 2 x2 >= 28
2 x1 + 12 x2 >= 24
x1, x2 >= 0