METODO SIMPLEX
Merino Fernando Zambrano David
La empresa Cannon Hill produce muebles: sillas y mesas. Cada mesa toma 4 horas de mano de obra y 2 horas de acabado. Cada silla requiere 3horas de carpintera y 1 hora de terminaciones. Hasta ahora se tienen disponibles 240 horas de tiempo de carpintera y 100 horas de tiempo de acabado. Cada mesa producida da una ganancia de $70 y cada silla una ganancia de $50. Cuntas sillas y mesas debe hacer para maximizar ganancias?
Variables de decisin
x: cantidad de mesas construidas en Cannon Hill y: cantidad de sillas construidas en Cannon Hill
El objetivo es maximizar el ganancia.
P = 70x + 50y
Conjunto de restricciones
4 x + 3 y 240 (restriccin de mano de obra para carpintera) 2 x + y 100 (restriccin de mano de obra para acabado) x 0 , y 0 (restriccin de mano de no-negatividad)
Paso 1: Cada desigualdad () se convierte en un ecuacin introduciendo una variable de holgura. Las variables de holgura representan las horas que sobran para carpintera y acabado sino se utilizan todas 4 x + 3 y 240 2 x + y 100 x0,y0 4x + 3y + 1 + 0s2 = 240 2x + y + 0s1 + 2 = 100 x 0, y 0, 1 0, 2 0
Paso 2: Despejar la funcin objetiva (todas las variables al lado izquierdo). 4x + 3y + 1 + 0s2 = 240 2x + y + 0s1 + 2 = 100
P 70x 50y = 0
x 0, y 0, 1 0, 2 0
4x + 3y + 1 + 0s2 = 240 2x + y + 0s1 + 2 = 100
Paso 3: En las columnas aparecern todas las variables del problema y en las filas, los coeficientes de las Variables que ecuaciones obtenidas.
entran a la Solucin s1 s2 P
P 70x 50y = 0
X
4 2
Y
3 1
S1
1 0 0
S2
0 1 0
Constantes 240 100 0
-70
-50
Paso 1: Determinar cul variable debe entrar a la solucin.
Para escoger la variable de decisin que entra a la solucin ptima, observamos la fila que muestra los coeficientes de la funcin objetiva y escogemos la variable con el coeficiente ms negativo. (Esta es la variable que aporta ms a las Variables que ganancias.) entran a la Constantes X Y S1 S2
Solucin s1 s2 P 4 2 -70 3 1 -50 1 0 0 0 1 0 240 100 0
Paso 2: Determinar cul variable debe salir de la solucin.
Para encontrar la variable de holgura que tiene que salir de la solucin , se divide cada trmino de la ltima columna (valores constante) entre el trmino correspondiente de la columna pivote, siempre que estos ltimos sean mayores que cero
Variables que entran a la Solucin s1 s2 P
X
4 2 -70
Y
3 1 -50
S1
1 0 0
S2
0 1 0
Constantes
240 100 0
Paso 2: Determinar cul variable debe salir de la solucin.
El trmino de la columna pivote que en la divisin anterior d lugar al menor cociente positivo, indica la fila de la variable de holgura que sale de la base, s2. Esta fila se llama fila pivote.
Variables que entran a la Solucin s1 s2 P
X
4 2 -70
Y
3 1 -50
S1
1 0 0
S2
0 1 0
Constantes 240 (240/4=60) 100 (100/2=50) 0
Paso 3: 1ra operacin sobre las fila pivote.
Los nuevos coeficientes de la fila pivote se obtienen dividiendo todos los coeficientes de la fila pivote entre el elemento pivote, 2
Variables que entran a la Solucin s1
X
4
Y
3 1/2 -50
S1
1 0 0
S2
0 1/2 0
Constantes 240 50 0
X
P
1
-70
pivote
Paso 4: Operacin sobre las filas NO pivote.
Usar operaciones sobre las filas para que todos los elementos de la columna pivote sean 0, -4R2 + excepto el pivote. R1 Variables que
entran a la Solucin s1
X
4
Y
3 1/2 -50
S1
1 0 0
S2
0 1/2 0
Constantes 240 50 0
X
P
1
-70
70R2 +
Resultado.
Variables que entran a la Solucin
S1
S2
Constantes
s1
X
0
1
1
1/2
1
0
-2
1/2
40
50
-15
35
3500
Hasta aqu se sabe que 50 mesas van a contribuir $3500 de ganancia. Sobran 40 horas de carpintera , por lo tanto debe haber una solucin mejor. Repetimos el proceso
Paso 1: Determinar cul variable debe entrar a la solucin.
Nuevamente, para escoger la variable de decisin que entra a la solucin, observamos la fila que muestra los coeficientes de la funcin objetiva y escogemos la variable con el coeficiente ms negativo
Variables que entran a la Solucin s1 x P
X
0 1 0
Y
1 1/2 -15
S1
1 0 0
S2
-2 1/2 35
Constantes 40 50 3500
Paso 2: Determinar cul variable debe salir de la solucin.
Para encontrar la variable de holgura que tiene que salir de la base, se divide cada trmino de la ltima columna (valores constantes) entre el trmino correspondiente de la columna pivote, siempre que estos ltimos sean mayores que cero . Sale la variable que da la razn menor Variables que
entran a la Solucin s1
X
0
Y
1
S1
1
S2
-2
Constantes 40 (40/1=40) 50 (50/(1/2))=100
1/2
1/2
Paso 3:
1ra operacin sobre filas: dividir cada elemento de la fila pivoteentre el elemento pivote. En este caso como el pivote es 1, brincamos este paso. pivot
Variables que entran a la Solucin
e
X
0 1 0
S1
1 0 0
S2
-2 1/2 35
Constantes
Y x P
1
1/2 -15
40 50 3500
Paso 4: Operaciones sobre filas para lograr ceros en la columna pivote..
Usar operaciones sobre las filas para que todos los elementos de la columna pivote sean 0, excepto el pivote. - R1/2 +R2 Variables que
entran a la Solucin
X
0 1 0
S1
1 0 0
S2
-2 1/2 35
Constantes
Y x P
1
1/2 -15
40 50 3500
15R1 +
Resultado.
Variables que entran a la Solucin
S1
S2
Constantes
Y X P
0 1 0
1 0 0
1 -1/2 15
-2 3/2 5
40 30 4100
Se deben construir: 30 mesas 40 sillas Ganancia mxima = $4100 No sobran horas de carpintera ni de acabado
Resolver el siguiente problema de programacin lineal: Maximizar Z = 3x1 + 2x2 Sujeto a: restricciones 2x1 + x2 18 2x1 + 3x2 42 3x1 + x2 24 x1 0 , x2 0
Paso 1: Cada desigualdad () se convierte en un ecuacin introduciendo una variable de holgura. Las variables de holgura representan las horas que sobran para carpintera y acabado sino se utilizan todas 2x1 + x2 18 2x1 + 3x2 42 3x1 + x2 24 x1 0 , x2 0 2x1 + x2 + s1+0s2+0s3 = 18 2x1 + 3x2 + 0s1+ s2+0s3 = 42 3x1 + x2 + 0s1+0s2+1s3 = 24
Paso 2: Despejar la funcin objetiva (todas las variables al lado izquierdo).
2x1 + x2 + s1+0s2+0s3 = 18 2x1 + 3x2 + 0s1+ s2+0s3 = 42 3x1 + x2 + 0s1+0s2+1s3 = 24
Z 3x1 2x2 = 0
x 0, y 0, 1 0, 2 0
Paso 3: En las columnas aparecern todas las variables del problema y en las filas, los coeficientes de las ecuaciones obtenidas. Solucin Variable de Variable de Base Constante decisin holgura s X2 S1 S2 S3 X1 S1 2 1 1 0 0 18 S2 2 3 0 1 0 42 S3 3 1 0 0 1 24 Z -3 -2 0 0 0 0
Paso 1: Determinar cul variable debe entrar a la solucin.
Para escoger la variable de decisin que entra a la solucin ptima, observamos la fila que muestra los coeficientes de la funcin objetiva y escogemos la variable con el coeficiente ms negativo. (Esta es la variable que aporta ms a las ganancias.) Variable de Solucin Base Variable de holgura decisin Constantes X2 S1 S2 S3 X1 S1 2 1 1 0 0 18 S2 2 3 0 1 0 42 S3 3 1 0 0 1 24 Z -3 -2 0 0 0 0
Paso 2: Determinar cul variable debe salir de la solucin.
Para encontrar la variable de holgura que tiene que salir de la solucin , se divide cada trmino de la ltima columna (valores constante) entre el trmino correspondiente de la columna pivote, siempre que estos ltimos sean mayores que cero Variable de Solucin Base Variable de holgura decisin Constantes X2 S1 S2 S3 X1 S1 2 1 1 0 0 18 S2 2 3 0 1 0 42 S3 3 1 0 0 1 24 Z -3 -2 0 0 0 0
Paso 2: Determinar cul variable debe salir de la solucin.
El trmino de la columna pivote que en la divisin anterior d lugar al menor cociente positivo, indica la fila de la variable de holgura que sale de la base, s3. Esta fila se llama fila pivote.
Base
Variable de decisin X1 X2
2 2 1 3
Variable de Soluci Operacin holgura n S3 S1 S2
1 0 0 1 0 0 18 42 18/2 = 9 42/2 = 21
S1 S2 S3 Z
3
-3
1
-2
0 0
0
0
1
0
24
0
24/3 = 8
0
Paso 3: 1ra operacin sobre las fila pivote.
Los nuevos coeficientes de la fila pivote se obtienen dividiendo todos los coeficientes de la fila pivote entre el elemento pivote, 2
Base
Variable de decisin x1 x2
2 2 1 3
Variable de holgura S1
1 0
Soluci n
1 3
Operacin
S2
0 1
S3
2 2
S1 S2 X1 Z
1
-3
1/3
-2
0
0
0
0
-1/3
0
8
0
(1/3) X1
pivote
Paso 4: Operacin sobre las filas NO pivote.
Usar operaciones sobre las filas para que todos los elementos de la columna pivote sean 0, excepto el pivote.
Base Variable de decisin x1 x2 0 1/3 0 7/3 1 1/3 0 -1 Variable de holgura S1 1 0 0 0 S2 0 1 0 0 S3 -2/3 -2/3 -1/3 1 Soluci n 2 26 8 24 Operacin
S1 S2 X1 Z
f(S1) 2 f(X1) f(S2) 2 f(X1) f(Z) + 3 f(X1)
Resultado.
Base Variable de decisin x1 x2 0 1/3 0 7/3 1 1/3 0 -1 Variable de holgura S1 1 0 0 0 S2 0 1 0 0 S3 -2/3 -2/3 -1/3 1 Soluci n 2 26 8 24
S1 S2 X1 Z
Hasta aqu se sabe que x1 = 8 Repetimos el proceso
Base
Variable de decisin X1 X2 1/3 7/3 1/3 -1
Variable de holgura S1 1 0 0 0 S2 0 1 0 0 S3 -2/3 -2/3 -1/3 1
Soluci n
Operacin
S1 S2 X1 Z
0 0 1 0
2 26 8 24
2/(1/3) = 6 26/(7/3) = 78/7 8/(1/3) = 24
RESULTADO
Base Variable de decisin X1 0 0 X2 1 0 Variable de holgura S1 3 -7 S2 0 1 S3 -2 4 Soluci n 6 12 Operacin
X2 S2
3X2 f(S2) (7/3) f(X2)
X1
Z
1
0
0
0
-1
3
0
0
1
-1
6
30
f(X1) (1/3) f(X2)
f(Z) + f(X2)
Base
Variable de decisin
X1 x2
Variable de holgura
S1 S2 S3
Soluci n
Operacin
X2
S2
0
0
1
0
3
-7
0
0
-2
4
6
12
No se toma por ser negativo 12/4 = 3
X1
Z
1
0
0
0
-1
3
0
0
1
-1
6
30
6/1 = 6
RESULTADO
Base Variable de decisin X1 X2 S3 X1 Z 0 0 1 0 X2 1 0 0 0 Soluci Variable de holgura n S1 -1/2 -7/4 -3/4 5/4 S2 0 0 0 0 S3 0 1 0 0 12 3 3 33 f(X2) + 2 f(S3) (1/4) S3 f(X1) f(S3) f(Z) + f(S3) Operacin
Como todos los coeficientes de la fila de la funcin objetivo son positivos, hemos llegado a la solucin ptima.
Base
Variable de decisin X1 X2 S3 X1 Z 0 0 1 0 X2 1 0 0 0
Variable de holgura
S1 -1/2 -7/4 -3/4 5/4 S2 0 0 0 0 S3 0 1 0 0
Soluci n
Operacin
12 3 3 33
f(X2) + 2 f(S3) (1/4) S3 f(X1) f(S3) f(Z) + f(S3)
Los solucin ptima viene dada por la columna Solucin, X1 = 3 X2 = 12 Z = 33.
Los ejercicios de maximizar son de utilidades, ganancias, ingresos. Los de minimizar son de costos, perdidas, gastos, distancias.
