Minimizacion Simplex

1
Lic. Araujo Cajamarca, Raul
Programacio n Lineal-Me todo simplex-Minimizacio n
1. Resolver el siguiente problema mediante el método gráfico y el método simplex
primal.
Función objetivo:
Min. 1 2 z  3x  2.5x
Sujeto a:
1 2 2x  4x  40 (Inecuación 01)
1 2 3x  2x  50 (Inecuación 02)
1 2 x , x  0
SOLUCIÓN POR EL MÉTODO GRÁFICO
Primer paso: Convertir las inecuaciones en ecuaciones.1 2 2x  4x  40 (Ecuación 01)
1 2 3x  2x  50 (Ecuación 02)
Segundo paso: Graficar ecuaciones e identificar área de factibilidad.
2
Lic. Araujo Cajamarca, Raul
Tercer paso: Identificar los vértices del área de factibilidad.
Los puntos son: B (20,0), C (15,2.5) y D (0,25)
Cuarto paso: Determinar el valor mínimo.
Vértices 1 x 2 x z
B 20 0 60.00
C 15 2.5 51.25
D 0 25 62.50
El valormínimo se alcanza para el punto C ( x1 15 y 2 x  25), z  51.25
SOLUCIÓN POR EL MÉTODO SIMPLEX
Primer paso: Convertir las inecuaciones en ecuaciones (agregar las variables de exceso
necesarias)
Tipo de
desigualdad
Tipo de variable
que aparece
 -Exceso + Artificial
= +Artificial
 +Holgura
3
Lic. Araujo Cajamarca, Raul
Función objetivo:
Min. z  3x1  2.5x2
Sujeto a:
1 2 2x  4x  401 2 3x  2x  50
1 2 x , x  0
Función objetivo:
Min. 1 2 1 2 1 2 z  3x  2.5x 0s 0s Mr Mr
Sujeto a:
1 2 1 1 2x  4x  s  r  40
1 2 2 2 3x  2x  s  r  50
1 2 x , x  0
1 2 s , s  0
1 2 r , r  0
i r =Variables artificiales
i s =Variables de exceso
M =Coeficiente de las variables artificiales, infinitamente grande
Si la función objetivo fuese Maximización, entonces los Mtendrían el signo menos (-M) en la
función objetivo.
Segundo paso: Determinar las variables básicas y las no básicas.
BASICAS NO BÁSICAS
1 r 1 x
2 r 2 x
1 s
2 s
Tercer paso: Elaborar la tabla inicial del Simplex.
Tablero Simplex
j c 3 2.5 0 0 M M i b i 
B c B x 1 x 2 x 1 s 2 s 1 r 2 r
M 1 r 2 4 -1 0 1 0 40
M 2 r 3 2 0 -1 0 1 50
j z
5M 6M -M -M M M 90M
j j c  z 3-5M 2.5-6M M M 0 0Cuarto paso: Elección de la columna pivote (variable que entra).
El coeficiente ( 0 j j c  z  ) de z más pequeño (NEGATIVOS) = Columna 2 x
4
Lic. Araujo Cajamarca, Raul
Si estuviésemos en el caso de maximización, se elige el más grande (POSITIVO) 0 j j c  z 
Quinto paso: Elección de la fila pivote (variable que sale).
 =Razón = Solución / Coeficiente columna pivote
Razón Menor = sólo  0 , Fila perteneciente a 1 r
j c 3 2.5 0 0 M M i b i 
B c B x 1 x 2 x 1 s 2 s 1 r 2 r
M 1 r 2 4 -1 0 1 0 40 10
M 2 r 3 2 0 -1 0 1 50 25
j z
5M 6M -M -M M M 90M
j j c  z 3-5M 2.5-6M M M 0 0
Intersección de fila pivote y columna pivote = Elemento pivote
Sexto paso: Elaborar la nueva tabla del simplex.
a) Nueva fila pivote = Fila Pivote / Elemento Pivote
2 4 -1 0 1 0 40
÷ ÷ ÷ ÷ ÷ ÷ ÷4 4 4 4 4 4 4
= = = = = = =
1/2 1 -1/4 0 1/4 0 10
b) Nueva filas = Fila Anterior – Coeficiente de la Columna Pivote x Nueva Fila Pivote
Fila 2 r
3 2 0 -1 0 1 50
- - - - - - -
2 2 2 2 2 2 2
x x x x x x x
1/2 1 -1/4 0 1/4 0 10
= = = = = = =
2 0 1/2 -1 -1/2 1 30
5
Lic. Araujo Cajamarca, Raul
Nuevo tablero simplex:
j c 3 2.5 0 0 M M i b i 
B c B x 1 x 2 x 1 s 2 s 1 r 2 r
2.5 2 x 1/21 -1/4 0 1/4 0 10 20
M 2 r 2 0 1/2 -1 -1/2 1 30 15
j z
8 5
4
M 
2.5
4 5
8
M 
-M
5 4
8
 M
M 25+30M
j j c  z
7 8
4
 M
0
5 4
8
 M
M
12 5
8
M 
0
Séptimo paso: Elaborar la nueva tabla del simplex.
c) Nueva fila pivote = Fila Pivote / Elemento Pivote
2 0 1/2 -1 -1/2 1 30
÷ ÷ ÷ ÷ ÷ ÷ ÷
2 2 2 2 2 2 2
= = = = = = =
1 0 1/4 -1/2 -1/4 1/2 15
d) Nueva filas = FilaAnterior – Coeficiente de la Columna Pivote x Nueva Fila Pivote
Fila 2 x
1/2 1 -1/4 0 1/4 0 10
- - - - - - -
1/2 1/2 1/2 1/2 1/2 1/2 1/2
x x x x x x x
1 0 1/4 -1/2 -1/4 1/2 15
= = = = = = =
0 1 -3/8 1/4 3/8 -1/4 5/2
6
Lic. Araujo Cajamarca, Raul
Nuevo tablero simplex:
j c 3 2.5 0 0 M M i b i 
B c B x 1 x 2 x 1 s 2 s 1 r 2 r
2.5 2 x 0 1 -3/8 1/4 3/8 -1/4 5/2
3 1 x 1 0 1/4 -1/2...