PROGRAMACION LINEAL TAREA 1. MÉTODOS SIMPLEX PRIMAL Y SIMPLEX DUAL
JULIANNY PALLARES AMAYA
CODIGO DEL CURSO: xxxxxxxx
TUTOR xxxxxxxxxxxxxx
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA (UNAD) MARZO DE 2019.
INTRODUCCIÓN
Mediante la programación podemos resolver problemas de la vida diaria de manera eficaz, entregándole órdenes básicas para el desarrollo de una operación a una función lineal simple y básica, de esta manera se asegura que el sistema funcione. La programación permite modificar variables dentro de una función para que entregue resultados de optimización de manera inmediata y nos permite sistematizar procesos para hacerlos más eficientes y evitar errores de carácter humano. Un método usado para la programación y la resolución de problemas básicos que simplifican procesos básicos de la vida diaria, el método simplex primal permite tomar decisiones para conocer la estrategia óptima que en este caso nos permitirá conocer los valores óptimos de producción con las decisiones tomadas para la mejor venta En el siguiente trabajo desarrollaremos ejercicios propuestos para esta actividad usando el método simplex primal y el método simplex dual para varios casos identificar diferencias y facilidades en el momento de la resolución de los ejercicios.
EJERCICIO 1. Una empresa de jugos naturales produce tres tipos de bebidas que se venden en los supermercados de cadena y que cuyas compradoras potenciales son las madres para poner en las loncheras de sus hijos (Jugo 1 de pera, Jugo 2 de manzana y Jugo 3 tropical). El jugo 1 está compuesto por 20 mililitros el componente A, 30 mililitros el componente B y 20 mililitros el componente C. El jugo 2 está compuesto por 30 mililitros el componente A, 20 mililitros el componente B y 20 mililitros vez el componente C y finalmente el jugo 3 está compuesto por 20 mililitros el componente A, 10 mililitros el componente B y 20 mililitros el componente C. Se deben gastar como minino 1500 mililitros del componente A, máximo 1700 mililitros del B y máximo 1300 mililitros del C por producción al día. La utilidad de los jugos 1, 2 y 3, es respectivamente de 600, 400 y 500 pesos. El componente A, hace relación al agua usada, el B al saborizante que incluye concentración de azúcar y el C al conservante. Formule el problema expuesto en la situación 1 y resuélvalo por el método simplex por los algoritmos simplex algebraico y simplex de las dos fases. Responda: a. ¿Qué cantidad de cada uno de los jugos debe fabricarse, según el método algebraico del simplex primal? b. ¿Qué cantidad de cada uno de los jugos debe fabricarse, según el método de las dos fases del simplex primal? c. ¿Cuál es la utilidad del problema? d. ¿Las respuestas de producción según las condiciones varían de acuerdo a cada método usado? DESARROLLO FORMULACIÓN DEL PROBLEMA Sea x_1: Jugo 1 x_2: Jugo 2 x_3: Jugo 3
FUNCIÓN OBJETIVO Max Z=600x_1+400x_2+500x_3
RESTRICCIONES 20x_1+30x_2+20x_3≥1500 30x_1+20x_2+10x_3≤1700 20x_1+20x_2+20x_3≤1300 x_1, x_2, x_3≥0
Agregando las variables de holgura y de exceso se obtiene 20x_1+30x_2+20x_3-s_1=1500 30x_1+20x_2+10x_3+s_2=1700 20x_1+20x_2+20x_3+s_3=1300 Donde x_1, x_2,x_3,s_1,s_2,s_3≥0 Luego la función objetivo queda determinada de la siguiente manera
Max Z=600x_1+400x_2+500x_3-0s_1+0s_2+0s_3 METODO SIMPLEX ALGEBRAICO Ya que se tienen m=3 restricciones y n=6 incógnitas y como n≥m se obtendrá una solución básica si se hace (n-m)=6-3=3 variables iguales a cero: Ya que al observar en la función objetivo que la variable que genera mayor utilidad es la variable x_1 tomaremos las siguientes variables iguales a cero: x_2=0, x_3=0, s_1=0 Remplazando en la primera restricción se obtiene 20x_1+30*0+20*0-0=1500 x_1=1500/20=75 x_2=0, x_3=0, s_2=0 Remplazando en la segunda restricción 30x_1+20*0+10*0+0=1700 x_1=1700/30=56.7 x_2=0, x_3=0, s_3=0
Remplazando en la tercera restricción 20x_1+20*0+20*0+0=1300 x_1=1300/20=65
30x_1+20x_2+10x_3+s_2=1700 30x_1=1700-20x_2-10x_3-s_2 x_1=(1700-20x_2-10x_3-s_2)/30 Sustituyendo en la función objetivo se obtiene
Max Z=600((1700-20x_2-10x_3-s_2)/30)+400x_2+500x_3-0s_1+0s_2+0s_3
Simplificando Max Z=20(1700-20x_2-10x_3-s_2) +400x_2+500x_3-0s_1+0s_2+0s_3 Max Z=34000-400x_2-200x_3-20s_2+400x_2+500x_3-0s_1+0s_2+0s_3 Se obtiene Max Z=34000+300x_3+-0s_1-20s_2+0s_3
Remplazando x_1 en la primera restricción, se obtiene 20((1700-20x_2-10x_3-s_2)/30) +30x_2+20x_3-s_1=1500 2/3*(1700-20x_2-10x_3-s_2) +30x_2+20x_3-s_1=1500 3400/3-40/3 x_2-20/3 x_3-2/3 s_2+30x_2+20x_3-s_1=1500 ((90-40)/3) x_2+ ((60-20)/3) x_3-s_1-2/3 s_2=(4500-3400)/3 50/3 x_2+40/3 x_3-3/3 s_1-2/3 s_2=1100/3 50x_2+40x_3-3s_1-2s_2=1100
Remplazado x_1 en la tercera restricción 20((1700-20x_2-10x_3-s_2)/30)+20x_2+20x_3+s_3=1300 2/3(1700-20x_2-10x_3-s_2)+20x_2+20x_3+s_3=1300
3400/3-40/3 x_2-20/3 x_3-2/3 s_2+20x_2+20x_3+s_3=1300 ((60-40)/3 ) x_2+((60-20)/3) x_3-2/3 s_2+s_3=(3900-3400)/3 20x_2+40x_3-2s_2+3s_3=500
Equivalente. FUNCIÓN OBJETIVO Max Z=34000+300x_3+-0s_1-20s_2+0s_3 RESTRICCIONES 50x_2+40x_3-3s_1-2s_2=1100 30x_1+20x_2+10x_3+s_2=1700 20x_2+40x_3-2s_2+3s_3=500
x_2=0, s_1=0 y s_2=0 Remplazando en la primera restricción se tiene
50*0+40x_3-3*0-2*0=1100 x_3=1100/40=27.5
x_2=0, x_1=0, s_2=0 30*0+20*0+10x_3+0=1700 x_3=1700/10=170 x_2=0, s_2=0, s_3=0 20*0+40x_3-2*0+3*0=500 x_3=500/40=12.5
Tercera restricción limita. 20x_2+40x_3-2s_2+3s_3=500 40x_3=500-20x_2+2s_2-3s_3
x_3= (500-20x_2+2s_2-3s_3)/40 Sustituyendo en la función objetivo se tiene Max Z=34000+300((500-20x_2+2s_2-3s_3)/40) +-0s_1-20s_2+0s_3 Max Z=34000+30/4 (500-20x_2+2s_2-3s_3) +-0s_1-20s_2+0s_3 Max Z=34000+3750-150x_2+15s_2-45/2 s_3-0s_1-20s_2+0s_3 Max Z=34000+3750-150x_2+15s_2-45/2 s_3-0s_1-20s_2+0s_3 Max Z=37750-150x_2-5s_2-45/2 s_3-0s_1
Remplazando en la primera restricción 50x_2+40((500-20x_2+2s_2-3s_3)/40)-3s_1-2s_2=1100 50x_2+500-20x_2+2s_2-3s_3-3s_1-2s_2=1100 30x_2-3s_3-3s_1=1100-500 30x_2-3s_3-3s_1=600 Remplazando en la segunda restricción 30x_1+20x_2+10((500-20x_2+2s_2-3s_3)/40)+s_2=1700 30x_1+20x_2+1/4(500-20x_2+2s_2-3s_3)+s_2=1700 30x_1+20x_2+500/4-20/4 x_2+2/4 s_2-3/4 s_3+s_2=1700 120/4 x_1+((80-20)/4) x_2+2/4 s_2-3/4 s_3+4/4 s_2=(6800-500)/4 120x_1+60x_2+2s_2-3s_3+4s_2=6300
Obtenemos el siguiente sistema FUNCIÓN OBJETIVO Max Z=37750-150x_2-5s_2-45/2 s_3-0s_1 RESTRICCIONES 30x_2-3s_3-3s_1=600 120x_1+60x_2+6s_2-3s_3=6300 20x_2+40x_3-2s_2+3s_3=500
En donde obtenemos un sistema equivalente al inicial y ya que se tienen m=3 ecuaciones y n=6 variables, de nuevo podemos volver cero 3 variables de estas, en donde observando la función objetivo se debe aumentar el valor de x_2, por ello tomamos: s_3=0, s_1=0 En la primera restricción 30x_2-3*0-3*0=600 x_2=600/30=20 x_1=0, s_2=0, s_3 En la segunda restricción 120*0+60x_2+6*0-3*0=6300 x_2=6300/60=105 x_3=0, s_2=0, s_3=0 En la tercera restricción 20x_2+40*0-2*0+3*0=500 x_2=500/20=25 Entonces la primera restricción es la que más limita la variable x_2, por lo tanto despejamos que la primera restricción la variable x_2 de la siguiente manera 30x_2-3s_3-3s_1=600 30x_2=600+3s_3+3s_1 x_2=(600+3s_3+3s_1)/30 Remplazando en la función objetivo se tiene Max Z=37750-150((600+3s_3+3s_1)/30)-5s_2-45/2 s_3-0s_1 Max Z=37750-5(600+3s_3+3s_1)-5s_2-45/2 s_3-0s_1 Max Z=37750-3000-15s_3-15s_1-5s_2-45/2 s_3-0s_1 Max Z=34750-75/2 s_3-15s_1-5s_2
Remplazando x_2 en la segunda restricción se tiene 120x_1+60((600+3s_3+3s_1)/30)+6s_2-3s_3=6300 120x_1+2(600+3s_3+3s_1)+6s_2-3s_3=6300
120x_1+1200+6s_3+6s_1+6s_2-3s_3=6300 120x_1+3s_3+6s_1+6s_2=6300-1200 120x_1+3s_3+6s_1+6s_2=5100
Remplazando x_2 en la tercera restricción se tiene 20((600+3s_3+3s_1)/30)+40x_3-2s_2+3s_3=500 2/3(600+3s_3+3s_1)+40x_3-2s_2+3s_3=500 400+2s_3+2s_1+40x_3-2s_2+3s_3=500 5s_3+2s_1+40x_3-2s_2=500-400 40x_3+5s_3+2s_1-2s_2=100
Por lo tanto, obtenemos el siguiente sistema
FUNCIÓN OBJETIVO Max Z=34750-75/2 s_3-15s_1-5s_2 RESTRICCIONES 30x_2-3s_3-3s_1=600 120x_1+3s_3+6s_1+6s_2=5100 40x_3+5s_3+2s_1-2s_2=500-400 Y por último, se le da el valor de cero a las variables s_1,s_2,s_3 entonces se tiene: Max Z=34750-75/2*0-15*0-5*0=34750
30x_2-3*0-3*0=600 x_2=600/30=20
120x_1+3*0+6*0+6*0=5100 x_1=5100/120=42.5
40x_3+5*0+2*0-2*0=100 x_3=100/40=2.5
En resumen, se obtuvo: Max Z=34750 Con
x_1=42.5 x_2=20 x_3=2.5 METODO SIMPLEX DOS FACES
FUNCIÓN OBJETIVO Max r=R_1 RESTRICCIONES 20x_1+30x_2+20x_3-t_1+R_1=1500 30x_1+20x_2+10x_3+s_2=1700 20x_1+20x_2+20x_3+s_3=1300 x_1,x_2,x_3,s_1,s_2,s_3≥0 FASE 1 C_j
0
0
0
0
-1
0
0
0
C_s
VB
X_1
X_2
X_3
t_1
R_1
S_2
S_3
LD
-1
R_1
20
30
20
-1
1
0
0
1500
50
0
S_2
30
20
10
0
0
1
0
1700
85
0
S_3
20
20
20
0
0
0
1
1300
65
r_j
20
30
20
0
1
0
0
1500
r
-20
-30
-20
1
0
0
0
-1500
C_j-r_j
Theta
C_j C_s
VB
0
0
0
0
-1
X_1
X_2
X_3
t_1
R_1
0
0
0
S_2 S_3 LD
0
X_2 0,6667
1
0,666667
-0,0333 0,03333
0
0
50
0
S_2 16,667
0
-3,333333 0,66667 -0,6667
1
0
700
0
S_3 6,6667
0
6,666667
0
1
300
0
0
0
0
0
C_j-r_j
r
0
0,66667 -0,6667 0
1
Es decir existe alguna solución posible para el problema ya que todos los C_jr_j≥0 para todas la j, entonces se tiene que 𝑥1∗ 50 𝑥𝑏∗ = ( 𝑠2 ) = ( 700 ) 𝑦 𝑟 ∗ = 0 𝑠3∗ 300
FASE 2 Para este caso el sistema no tiene alguna variable artificial, entonces para no tener demasiadas columnas en la tabla se suprimen todas las columnas de las variables artificiales, es decir Estandarizando la Fase 2 se tiene FUNCIÓN OBJETIVO Max W=600x_1+400x_2+500x_3+0*s_2+0*s_3
RESTRICCIONES 0,66x_1+x_2+0,66x_3=50 16,66x_1-3.33x_3-t_1+s_2=700 6,66x_1+6,66x_3+s_3=300 x_1,x_2,x_3,t_1,s_2,s_3≥0
Theta
Entonces la tabla de la fase dos queda determinada de la siguiente manera C_j
600
400
500
0
0
0
0
X_3
t_1
S_2
S_3
LD
Theta
0
0
50
75
0,66667
1
0
700
42
45
C_s
VB
X_1
X_2
400
X_2
0,6667
1
0
S_2
16,667
0
0,666667 -0,0333 3,333333
0
C_j-
S_3
6,6667
0
6,666667 0,66667
0
1
300
w_j
266,67
400
266,6667 -13,333
0
0
20000
r
-
0
0
0
20000
-
-13,333
w_j
333,33
233,3333
C_j
600
400
500
0
0
0
0
C_s
VB
X_1
X_2
X_3
t_1
S_2
S_3
LD
400
X_2
0
1
0,8
-0,06
-0,04
0
22
600
X_1
1
0
-0,2
0,04
0,06
0
42
0
S_3
0
0
8
0,4
-0,4
1
20
C_j-
r
0
0
-300
0
20
0
34000
600
400
500
0
0
0
0
Theta
w_j
C_j C_s
VB
X_1
X_2
X_3
t_1
S_2
S_3
LD
Theta
400
X_2
0
1
0,8
-0,06
-0,04
0
22
27,5
600
X_1
1
0
-0,2
0,04
0,06
0
42
-210
0
S_3
0
0
8
0,4
-0,4
1
20
2,5
w_j
600
400
200
0
20
0
34000
w
0
0
-300
0
20
0
34000
C_jw_j
C_j
600
400
500
0
0
0
0
C_s
VB
X_1
X_2
X_3
t_1
S_2
S_3
LD
400
X_2
0
1
0
-0,1
0
-0,1
20
600
X_1
1
0
0
0,05
0,05
0,025
42,5
500
X_3
0
0
1
0,05
-0,05
0,125
2,5
C_j-
w
0
0
0
15
5
37,5
34750
Theta
w_j
Por lo tanto, se tiene la siguiente solución Z=34750 x_2=20 x_1=42,5 x_3=2,5 CONCLUSIÓN a. En conclusión, por el método simplex a dos fases se sugiere que se deben producir 42.5 jugos 1 de Pera, 20 jugos 2 de manzana y 2.5 jugos 3 tropical con una utilidad de 34750. b. En conclusión, por el método algebraico del simplex primal se sugiere que se deben producir 42.5 jugos 1 de Pera, 20 jugos 2 de manzana y 2.5 jugos 3 tropical con una utilidad de 34750 c. Por el método simplex a dos fases se sugiere que se deben producir 42.5 jugos 1 de Pera, 20 jugos 2 de manzana y 2.5 jugos 3 tropical con una utilidad de 34750. d. La utilidad del problema es de Z=34750 e. No, en este caso las respuestas coincidieron.
EJERCICIO 2.
De acuerdo a las siguientes condiciones de un problema productivo, donde se han tomado los datos de utilidades y restricciones, según ciertas condiciones y necesidades, determine:
Cantidad de cada uno de las variables a fabricarse, según el método simplex algebraico. Cantidad de cada uno de las variables a fabricarse, según el método de las dos fases del simplex primal. Utilidad del problema. Compare los resultados obtenidos por cada uno de los métodos propuestos y justifíquelos.
FUNCIÓN OBJETIVO Maximizar Z = 6x_1+7x_2+5x_3+3x_4
SUJETO A LAS RESTRICCIONES: 3x_1+3x_2+2x_3+x_4≤ 75 3x_1+ 2x_2+3x_3+2x_4≤ 100 2x_1+2x_2+4x_3+3x_4≥ 30 2x_1+2x_2+x_3+2x_4≤ 68 x_1,x_2,x_3,x_4≥ 0
MÉTODO SIMPLEX ALGEBRAICO
Maximizar Z -6x_1 - 7x_2 -5x_3 -3x_4=0 3x_1+3x_2+2x_3+x_4≤75 3x_1+2x_2+3x_3+2x_4≤100 2x_1+2x_2+4x_3+3x_4≥30 2x_1+2x_2+1x_3+2x_4≤68
x_1,x_2,x_3,x_4≥ 0 Agregando las variables de holgura Maximizar Z -6x_1 - 7x_2 -5x_3 -3x_4=0 3x_1+3x_2+2x_3+x_4+y_1=75 3x_1+2x_2+3x_3+2x_4+y_2=100 2x_1+2x_2+4x_3+3x_4-y_3=30 2x_1+2x_2+x_3+2x_4+y_4=68 x_1,x_2,x_3,x_4≥ 0 Vamos a tomar la -7x_2, 3x_1+3x_2+2x_3+x_4+y_1=75 3x_1+2x_2+3x_3+2x_4+y_2=100 2x_1+2x_2+4x_3+3x_4-y_3=30 2x_1+2x_2+1x_3+2x_4-y_4=68 Al cambiar las variables 3(0)+3x_2+2(0)+ (0)+ (0)=75 3(0)+2x_2+3(0)+2(0)+ (0)=100 2(0)+2x_2+4(0)+3(0)-(0)=30 2(0)+2x_2+1(0)+2(0)+ (0)=68 Obteniendo los valores correspondientes de las variables x_2 3x_2=75 x_2=75/3=25
2x_2=100 x_2=100/2=50
2x_2=30 x_2=30/2=15
2x_2=68 x_2=68/2=34 Despejar de la ecuación 3, la variable x_2 2x_1+2x_2+4x_3+3x_4-y_3=30 2x_2=30-(2x_1+4x_3+3x_4-y_3) x_2= (30-(2x_1+4x_3+3x_4+y_3))/2 x_2=15-x_1-2x_3-3/2 x_4+1/2 y_3 Esta ecuación se sustituye dentro de las ecuaciones iniciales a excepción de la ecuación 3. Maximizar Z -6x_1 - 7(15-x_1-2x_3+3/2 x_4-1/2 y_3) -5x_3 -3x_4=0 3x_1+3(15-x_1-2x_3+3/2 x_4-1/2 y_3)+2x_3+x_4+y_1=75 3x_1+2(15-x_1-2x_3+3/2 x_4-1/2 y_3)+3x_3+2x_4+y_2=100 2x_1+2x_2+4x_3+3x_4-y_3=30 2x_1+2(15-x_1-2x_3+3/2 x_4-1/2 y_3)+x_3+2x_4+y_4=68 Expandiendo y Multiplicando las ecuaciones por 2, ahora nuestro sistema de ecuaciones es: Maximizar 2z-210+2x_1+18x_3+15x_4-7y_3=0 -8x_3-7x_4+2y_1+3 y_3=60 2x_1-2x_3-2x_4+2y_2+2y_3=140 2x_1+2x_2+4x_3+3x_4-y_3=30 -6x_3-2x_4+2y_3+2y_4=76 Con lo cual vamos a tomar la variable -7y_3. En cada restricción vamos a cambiar las variables por cero a excepción de la variable y_3, es decir si las ecuaciones en su respectivo orden son:
-8x_3-7x_4+2y_1+3y_3=60 2x_1-2x_3-2x_4+2y_2+2y_3=140 2x_1+2x_2+4x_3+3x_4-y_3=30 -6x_3-2x_4+2y_3+2y_4=76
Al cambiar las variables -8(0)-7(0)+2(0)+3 y3=60 2(0)-2(0)-2(0)+2(0)+2y3=140 2(0)+2(0)+4(0)+3(0)-y3=30 -6(0)-2(0)+2y3+2(0)=76 Obteniendo los valores correspondientes de las variables y_3 3 y_3=60 y_3=60/3=20
2y_3=140 y_3=140/2=70
-y_3=30 y_3=30/-1=-30
2y_3=76 y_3=76/2=38 Tomando la ecuación cuyo valor positivo es mínimo, es decir la ecuación 1 entonces vamos a despejar de la ecuación 1, la variable y_3 -8x_3-7x_4+2y_1+3y_3=60 Multiplicando por 2 toda la ecuación 3 y_3=60+8x_3+7x_4-2y_1 y3=1/3 (60+8x_3+7x_4-2y_1 ) Esta ecuación se sustituye dentro de las ecuaciones iniciales a excepción de la ecuación 1. Maximizar 2z-210+2x_1+18x_3+15x_4-7(1/3 (60+8x_3+7x_4-2y_1 ))=0 -8x_3-7x_4+2y_1+3 y_3=60 2x_1-2x_3-2x_4+2y_2+2(1/3 (60+8x_3+7x_4-2y_1 ))=140 2x_1+2x_2+4x_3+3x_4-1/3 (60+8x_3+7x_4-2y_1 )=30
-6x_3-2x_4+2(1/3 (60+8x_3+7x_4-2y_1 ))+2y_4=76 Expandiendo y multiplicando por 3 6z-1050+6x_1-2x_3-4x_4+14y_1=0 -8x3-7x_4+2y_1+3 y_3=60 6x_1+10x_3+8x_4-4y_1+6y_2=300 6x_1+6x_2+4x_3+2x_4+2y_1=150 -2x_3+8x_4-4y_1+6y_4=108 Tomando la variable de la función objetivo mas grande pero negativo, es decir -4x_4 en cada restricción vamos a cambiar las variables por cero a excepción de la variable x_4, es decir si las ecuaciones en su respectivo orden son: -8x_3-7x_4+2y_1+3 y_3=60 6x_1+10x_3+8x_4-4y_1+6y_2=300 6x_1+6x_2+4x_3+2x_4+2y_1=150 -2x_3+8x_4-4y_1+6y_4=108 Al cambiar las variables -8(0)-7x4+2(0)+3 (0)=60 6(0)+10(0)+8x4-4(0)+6(0)=300 6(0)+6(0)+4(0)+2x4+2(0)=150 -2(0)+8x4-4(0)+6(0)=108 Obteniendo los valores correspondientes de las variables x_4 -7x_4=60 x_4=60/-7.
8x_4=300 x_4=300/8=37,5.
2x_4=150 x_4=150/2=75
8x_4=108 x_4=108/8=13,5 Tomando la ecuación cuyo valor positivo es mínimo, es decir la ecuación 4 entonces vamos a despejar de la ecuación 4, la variable x4 -2x_3+8x_4-4y_1+6y_4=108 8x_4=108+2x_3+4y_1-6y_4 x_4=1/8 (108+2x_3+4y_1-6y_4 ) Esta ecuación se sustituye dentro de las ecuaciones iniciales a excepción de la ecuación 2. 6z-1050+6x_1-2x_3-4(1/8 (108+2x_3+4y_1-6y_4 ))+14y_1=0 -8x_3-7(1/8 (108+2x_3+4y_1-6y_4 ))+2y_1+3 y_3=60 6x_1+10x_3+8(1/8 (108+2x_3+4y_1-6y_4 ))-4y_1+6y_2=300 6x_1+6x_2+4x_3+2(1/8 (108+2x_3+4y_1-6y_4 ))+2y_1=150 -2x_3+8x_4-4y_1+6y_4=108 Expandiendo y Multiplicando 24z -4416+24x_1-12x_3+48y_1+12y_4=0 -39x_3-6y_1+12y_3+21y_4 =618 24x_1+48x_3+24y_2-24y_4=768 24x_1+24x_2+18x_3+12y_1-6y_4=492 -2x_3+8x_4-4y_1+6y_4=108 Tomamos la variable de la función objetivo con valor más grande pero negativo, con lo cual vamos a tomar la variable -12x_3. En cada restricción vamos a cambiar las variables por cero a excepción de la variable x_3, es decir -39x_3-6y_1+12y_3+21y_4=618 24x_1+48x_3+24y_2-24y_4=768 24x_1+24x_2+18x_3+12y_1-6y_4=492 -2x_3+8x_4-4y_1+6y_4=108 Al cambiar las variables -39x_3-6(0)+12(0)+21(0)=618
24(0)+48x_3+24(0)-24(0)=768 24(0)+24(0)+18x_3+12(0)-6(0)=492 -2x_3+8(0)-4(0)+6(0)=108 Obteniendo los valores correspondientes de las variables x_3 -39x_3=618 x_3=618/(-39)
48x_3=768 x_3=768/48=16
18x_3=492 x_3=492/18=27.3
-2x_3=108 x_3=108/-2 Tomando la ecuación cuyo valor positivo es mínimo, es decir la ecuación 2 entonces vamos a despejar de la ecuación 2 la variable x3
24x_1+48x_3+24y_2-24y_4=768 48x_3=768-24x_1-24y_2+24y_4 x_3=1/48 (768-24x_1-24y_2+24y_4 )
24z -4416+24x_1-12(1/48 (768-24x_1-24y_2+24y_4 ))+48y_1+12y_4=0 -39x_3-6y_1+12(1/48 (768-24x_1-24y_2+24y_4 ))+21y_4=618 24x_1+48x_3+24y_2-24y_4=768 24x_1+24x_2+18(1/48 (768-24x_1-24y_2+24y_4 ))+12y_1-6y_4=492 -2(1/48 (768-24x_1-24y_2+24y_4 ))+8x_4-4y_1+6y_4=108
Expandiendo por 2
48 z -9216+60x_1+96y_1+12y_2+12y_4=0 39x_1-12y_1+39y_2+24y_3+3y_4=2484 24x_1+48x_3+24y_2-24y_4=768 30x_1+48x_2+24y_1-18y_2+6y_4=408 2x_1+16x_4-8y_1+2y_2+10 y_4=280
Como todas las variables en la función objetivo no tiene ninguna constante negativa el proceso acaba y haciendo las variables x_1=y_1=y_2=y_3= y_4=0 las cuales están presentes en la función objetivo
39x_1-12y_1+39y_2+24y_3+3y_4=2484 24x_1+48x_3+24y_2-24y_4=768 30x_1+48x_2+24y_1-18y_2+6y_4=408 2x_1+16x_4-8y_1+2y_2+10 y_4=280
Cambiando las variables 39(0)-12(0)+39(0)+24(0)+3(0)=2484 24(0)+48x3+24(0)-24(0)=768 30(0)+48x2+24(0)-18(0)+6(0)=408 2(0)+16x4-8(0)+2(0)+10(0)=280 Es decir inconsistente 48x_3=768 x_3=768/48=16
48x_2=408 x_2=408/48=8.5
16x_4=280 x_4=280/16=17.5
CONCLUSIÓN
Z=192 x_1=0 x_2=8.5 x_3=16 x_4=17.5
MÉTODO SIMPLEX DOS FASES Maximizar Z -6x_1 - 7x_2 -5x_3 -3x_4=0 3x_1+3x_2+2x_3+x_4≤75 3x_1+2x_2+3x_3+2x_4≤100 2x_1+2x_2+4x_3+3x_4≥30 2x_1+2x_2+1x_3+2x_4≤68 x_1,x_2,x_3,x_4≥ 0 Agregando las variables de holgura Maximizar Z -6x_1 - 7x_2 -5x_3 -3x_4=0 3x_1+3x_2+2x_3+x_4+y_1=75 3x_1+2x_2+3x_3+2x_4+y_2=100 2x_1+2x_2+4x_3+3x_4-y_3+y_4=30 2x_1+2x_2+x_3+2x_4+y_5=68 x_1,x_2,x_3,x_4≥ 0
Organizando las ecuaciones en una tabla entonces x1
x2
x3
x4
y1
y2
y3
y4
y5
z
R
y1
3,00
3,00
2,00
1,00 1,00 0,00
0,00 0,00 0,00 0,00
y2
3,00
2,00
3,00
2,00 0,00 1,00
0,00 0,00 0,00 0,00 100,00
y3
2,00
2,00
4,00
3,00 0,00 0,00 -1,00 1,00 0,00 0,00
30,00
y4
2,00
2,00
1,00
2,00 0,00 0,00
0,00 0,00 1,00 0,00
68,00
-6,00 -7,00 -5,00 -3,00 0,00 0,00
0,00 0,00 0,00 1,00
0,00
z
75,00
Tomando de la última fila el valor más mínimo, para fijar la columna pivote, por otro lado, haciendo los cocientes de las columnas R con los valores de la columna pivote, y tomando la fila cuyo valor al realizar el cociente es el menor número positivo. x1
x2
x3
x4
y1
y2
y3
y4
y5
z
R
cocientes
y1 3,00 3,00 2,00
1,00 1,00 0,00
0,00 0,00 0,00 0,00
75,00
25,00
y2 3,00 2,00 3,00
2,00 0,00 1,00
0,00 0,00 0,00 0,00 100,00
50,00
y3 2,00 2,00 4,00
3,00 0,00 0,00 -1,00 1,00 0,00 0,00
30,00
15,00
y4 2,00 2,00 1,00
2,00 0,00 0,00
0,00 0,00 1,00 0,00
68,00
34,00
- -3,00 0,00 0,00
0,00 0,00 0,00 1,00
0,00
z
-
-
6,00 7,00 5,00
La variable que entra es x_2 y la variable que sale es y_3, ahora bien realizando las operaciones siguientes entre filas de la tabla 1 𝑓 → 𝑓3 , 2 3
3 𝑓1 − 𝑓3 → 𝑓1 , 2
𝑓2 − 𝑓3 → 𝑓2 ,
𝑓4 − 𝑓3 → 𝑓4 ,
7 𝑓5 + 𝑓3 → 𝑓5 2
Donde el cuadrado designa la variable entrante y saliente x1
x2
x3
x4
y1
y2
y3
y4
y5
z
R
y1 0,00 0,00 -4,00 -3,50 1,00 0,00
1,50 -1,50 0,00 0,00
30,00
y2 1,00 0,00 -1,00 -1,00 0,00 1,00
1,00 -1,00 0,00 0,00
70,00
x2 1,00 1,00
2,00
1,50 0,00 0,00 -0,50
y4 0,00 0,00 -3,00 -1,00 0,00 0,00 z
1,00 0,00
9,00
0,50 0,00 0,00
15,00
1,00 -1,00 1,00 0,00
38,00
7,50 0,00 0,00 -3,50
3,50 0,00 1,00 105,00
Tomando el valor mínimo de la última fila, para fijar la columna pivote, por otro lado, haciendo los cocientes de las columnas R con los valores de la columna pivote, y tomando la fila cuyo valor al realizar el cociente es el menor número positivo. x1 y1
x2
0,00 0,00
x3
x4 -
4,00 y2
x2
1,00 0,00
1,00 1,00
y1
y2
- 1,00 0,00
y3
y4
1,50
3,50
-
y5
z
- 0,00 0,00
R
theta
30,00
20,00
70,00
70,00
0,50 0,00 0,00
15,00
-30,00
- 1,00 0,00
38,00
38,00
1,50
- 0,00 1,00
1,00
1,00
2,00
1,50 0,00 0,00
1,00
- 0,00 0,00 1,00
0,50
y4
z
0,00 0,00
1,00 0,00
-
- 0,00 0,00
3,00
1,00
9,00
7,50 0,00 0,00
1,00
1,00 -
3,50 0,00 1,00 105,00
3,50
La variable que entra es y3 y la variable que sale es y1, ahora bien realizando las operaciones siguientes entre filas de la tabla 1 𝑓 → 𝑓1 , 1.5 1 𝑓4 −
𝑓2 −
1 𝑓 → 𝑓2 , 1.5 1
1 𝑓 → 𝑓4 , 1.5 1
𝑓5 +
𝑓3 +
0.5 𝑓 → 𝑓3 , 1.5 1
3.5 𝑓 → 𝑓5 1.5 1
x1
x2
x3
x4
y1
y3 0,00 0,00 -2,67 -2,33
y2
y3
y4
y5
z
0,67 0,00 1,00 -1,00 0,00 0,00
R 20,00
y2 1,00 0,00
1,67
1,33 -0,67 1,00 0,00
0,00 0,00 0,00
50,00
x2 1,00 1,00
0,67
0,33
0,33 0,00 0,00
0,00 0,00 0,00
25,00
1,33 -0,67 0,00 0,00
0,00 1,00 0,00
18,00
y4 0,00 0,00 -0,33 z
1,00 0,00 -0,33 -0,67
2,33 0,00 0,00
0,00 0,00 1,00 175,00
Tomando el valor mínimo de la última fila, para fijar la columna pivote, por otro lado haciendo los cocientes de las columna R con los valores de la columna pivote, y tomando la fila cuyo valor al realizar el cociente es el menor número positivo. x1
x2
x3
x4
y1
y3 0,00 0,00 -2,67 -2,33
y2
y3
y4
y5
z
0,67 0,00 1,00 -1,00 0,00 0,00
R 20,00
theta -8,57
y2 1,00 0,00
1,67
1,33 -0,67 1,00 0,00
0,00 0,00 0,00
50,00 37,50
x2 1,00 1,00
0,67
0,33
0,33 0,00 0,00
0,00 0,00 0,00
25,00 75,00
1,33 -0,67 0,00 0,00
0,00 1,00 0,00
18,00 13,50
y4 0,00 0,00 -0,33 z
1,00 0,00 -0,33 -0,67
2,33 0,00 0,00
0,00 0,00 1,00 175,00
La variable que entra es x4 y la variable que sale es y4, ahora bien, realizando las operaciones siguientes entre filas de la tabla 1 𝑓 → 𝑓4 , 1.33 4 𝑓3 −
𝑓2 +
2.33 𝑓 → 𝑓2 , 1.33 4
0.33 𝑓 → 𝑓3 , 1.33 4
𝑓5 +
𝑓2 − 𝑓4 → 𝑓2 ,
0.67 𝑓 → 𝑓5 1.33 4
x1
x2
x3
x4
y1
y2
y3
y4
y5
y3 0,00 0,00 -3,25 0,00 -0,50 0,00 1,00 -1,00
z
R
1,75 0,00
51,50
y2 1,00 0,00
2,00 0,00
0,00 1,00 0,00
0,00 -1,00 0,00
32,00
x2 1,00 1,00
0,75 0,00
0,50 0,00 0,00
0,00 -0,25 0,00
20,50
0,00
0,75 0,00
13,50
0,00
0,50 1,00 184,00
x4 0,00 0,00 -0,25 1,00 -0,50 0,00 0,00 z
1,00 0,00 -0,50 0,00
2,00 0,00 0,00
Tomando el valor mínimo de la última fila, para fijar la columna pivote, por otro lado, haciendo los cocientes de las columnas R con los valores de la columna pivote, y tomando la fila cuyo valor al realizar el cociente es el mentó numero positivo. x1
x2
y3 0,00 0,00
x3
x4 - 0,00
3,25
y1
y2
y3
y4
- 0,00 1,00 0,50
y5
z
- 1,75 0,00
R
cocientes
51,50
-15,85
32,00
16,00
20,50
27,33
13,50
-54,00
1,00
y2 1,00 0,00 2,00 0,00 0,00 1,00 0,00 0,00
- 0,00 1,00
x2 1,00 1,00 0,75 0,00 0,50 0,00 0,00 0,00
- 0,00 0,25
x4 0,00 0,00
- 1,00 0,25
z
1,00 0,00
- 0,00 0,00 0,00 0,75 0,00 0,50
- 0,00 2,00 0,00 0,00 0,00 0,50 1,00 184,00 0,50
La variable que entra es x3 y la variable que sale es y2, ahora bien realizando las operaciones siguientes entre filas de la tabla 1 𝑓 → 𝑓2 , 2 2 𝑓4 +
𝑓1 +
3.25 𝑓 → 𝑓1 , 2 2
0.25 𝑓 → 𝑓4 , 2 2
𝑓5 +
𝑓3 −
0.75 𝑓 → 𝑓3 2 2
0.5 𝑓 → 𝑓5 2 2
x1
x2
x3
x4
y1
y2
y3
y4
y3 1,63 0,00 0,00 0,00 -0,50
1,63 1,00 -1,00
x3 0,50 0,00 1,00 0,00
0,00
0,50 0,00
x2 0,63 1,00 0,00 0,00
0,50 -0,38 0,00
x4 0,13 0,00 0,00 1,00 -0,50 z
1,25 0,00 0,00 0,00
2,00
y5
z
R
0,13 0,00 103,50
0,00 -0,50 0,00
16,00
0,00
0,13 0,00
8,50
0,13 0,00
0,00
0,63 0,00
17,50
0,25 0,00
0,00
0,25 1,00 192,00
Debido a que en la última fila no hay más numero negativos entonces el proceso termina y por tanto la solución al problema está dada por x_1=0,x_2=8.5,x_3=16,x_4=17.5 CONCLUSIÓN Z=192 x_1=0 x_2=8.5 x_3=16 x_4=17.5
EJERCICIO 3: Raúl García es el heredero de un taller de carpintería que le ha dejado su padre como parte de tradición familiar. Raúl es un comerciante de vehículos importados que nunca se interesó por el negocio con el que su padre le creó y le pagó sus estudios universitarios. Ahora con la muerte de su padre Raúl debe hacerse cargo del negocio, el cual heredará algún día a uno de sus hijos. Cuando Raúl visita el taller para hacerse cargo, encuentra que el producto que mayor atención merece por ser el de mayor venta es el de escritorios tipo deko que su padre diseñó y que se fabrican según especificaciones de los clientes, tipo 1 para hogar, tipo 2 para oficinas y tipo 3 para colegios. Cada escritorio pasa por 3 procesos básicos el corte de la madera, el ensamblado y la pintura del producto terminado que se miden en horas de trabajo. Raúl seguirá la política de contratación de personal de su padre, los turnos rotativos, por lo cual el tiempo de trabajo es variable entre una y otra semana, las horas mínimas a contratar por semana se muestran en la tabla 1. A partir de los datos siguientes que se consignan en la tabla 1, formule el problema de programación lineal y resuélvalo a partir del método simplex primal de las dos fases para ayudar a Rubén a minimizar los costos del proceso. Tipo de
Corte
Ensamble
Pintura
escritorio
Costos por producto semanales
1
2
3
2
US 17
2
2
2
3
US 17
3
3
1
1
US 23
Horas
33
31
35
Sea x_1≔Cantidad de escritorios del Tipo 1 x_2≔Cantidad de escritotios del Tipo 2 x_3≔Cantidad de escritorios del Tipo 3 FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3
RESTRICCIÓN 2x_1+2x_2+3x_3≥33 3x_1+2x_2+x_3≥31 2x_1+3x_2+x_3≥35 x_1,x_2,x_3≥0 Agregando las variables de holgura y de exceso se tiene
FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3+0*s_1+0*s_2+0*s_3 RESTRICCIÓN 2x_1+2x_2+3x_3+s_1=33 3x_1+2x_2+x_3+s_2=31 2x_1+3x_2+x_3+s_3=35 x_1,x_2,x_3,s_1,s_2,s_3≥0
MÉTODO SIMPLEX A DOS FASES Se tiene el siguiente sistema Sea x_1≔Cantidad de escritorios del Tipo 1 x_2≔Cantidad de escritotios del Tipo 2 x_3≔Cantidad de escritorios del Tipo 3 FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3+0*s_1+0*s_2+0*s_3 Y esto es lo mismo que Max Z=-17x_1-17x_2-23x_3+0*s_1+0*s_2+0*s_3
RESTRICCIÓN 2x_1+2x_2+3x_3-s_1+s_2=33 3x_1+2x_2+x_3-s_3+s_4=31 2x_1+3x_2+x_3-s_5+s_6=35 x_1,x_2,x_3,s_1,s_2,s_3,s_4,s_5,s_6≥0 FASE 1 Construyendo la tabla simplex se obtiene C_j
0
0
0
VB
X_1
X_2
X_3
-1 s_2
2
2
3
-1
1
0
0
0
0
33
-1 s_4
3
2
1
0
0
-1
1
0
0
31
-1 s_6
2
3
1
0
0
0
0
-1
1
35
r_j
-7
-7
-5
1
-1
1
-1
1
-1
-99
r
-7
-7
-5
1
0
1
0
1
0
-99
C_s
C_j-r_j
0 s_1
-1 s_2
0 s_3
-1 s_4
0
-1
s_5
0
s_6
LD
Theta
Seleccionando el menor valor de los C_j-r_j la cual nos indica la columna pivote, luego determinado el valor de theta del cual se selecciona el menor valor más positivo, indicándonos este la fila pivote y culla intersección con la columna pivote es el pivote de la tabla. C_j C_s
0
0
0
0
VB X_1 X_2 X_3 s_1
-1
0
-1
s_2 s_3 s_4
0
-1
0
s_5 s_6 LD
Theta
-1 s_2
2
2
3
-1
1
0
0
0
0
33
-1 s_4
3
2
1
0
0
-1
1
0
0
31 10,3333333
-1 s_6
2
3
1
0
0
0
0
-1
1
35
-7
-7
-5
1
0
1
0
1
0
-99
C_j-r_j r
16,5
17,5
Volviendo 1 en pivote y ceros los valores de la columna pivote se obtiene C_j
0 VB
C_s
0
X_1 X_2
-1 s_2 0 X_1 -1 s_6 C_j-r_j r
0
0
X_3
-1
0
s_1 s_2 s_3
-1 s_4
0
0,66667
2,333333
-1
1
1
0,66667
0,33333
0
0
-0,33333
0
1,66667
0,33333
0
0
0
-2,33333
-2,66667
1
0 -1,33333333
0
-1
s_5
0,66667 -0,66667
0
s_6 LD 0
0
12,3333
0,33333
0
0
10,3333
0,666667 -0,66667
-1
1
14,3333
2,33333
1
0 -26,6667
Repitiendo el proceso, volvemos a determinar el pivote, la columna pivote y la fila pivote: C_j
0
C_s
0
V
X_ X_2
B
1
-1 s_
0
2
0 X_3
0,66666
2,33333
667
333
0
-1
s_
s_
1
2
-1
1
0 s_3
-1 s_4
0,66666
-
667
0,66666
0
-1
s_
s_
5
6 0
0
0 LD
Theta
12,3333
5,285
333
71429
10,3333
31
667 0 X_
1
1
0,66666
0,33333
667
333
0
0
-
0,33333
0,33333
333
0
0
333
333 -1 s_
0
6
1,66666
0,33333
667
333
0
0
0,66666
-
667
0,66666
-1
1
14,3333 333
667 r_j
C_jr_j
r
0
0
-
-
2,33333
1
-
1,33333
2,66666
1,33333
333
333
667
333
-
-
2,33333 333
1
-1
0
1
-1
26,6666 667
-
2,33333
2,66666
1,33333
333
667
333
1
0
26,6666 667
43
Theta
Volviendo 1 el nuevo pivote y ceros la columna pivote se obtiene. C_j C_s
0 V
X
B
_1
0 X
0
_3
0 X_2
0 X
0 s_1
-1 s_2
0 s_3
s_4
_3
0,2857
1
1429
-
0,4
0,2857
-
0,4285
29
1429
0,2857
714 0 X
1
_1
-1 s_
0,5714
0
2857
0
6
1,5714
0
2857
0
j
C_j- r r_j
0
-
0,1428
-
-
0,4285
5714
0,1
0,4285
7143
43
7143
0,1428
-
0,5714
5714
0,1
2857
s
_
_
5
6
0
0
0
0
0 LD
Th eta
5,2857
18,
1429
5
8,5714
15
2857
1
0,5714
12,571 4286
2857
0,1
-
0,5714
1,5714
0,1428
43
0,5714
2857
2857
571 0
s
- -1
-
-
0
0 -1
1429
43 r_
-1
1 -1
12,571
2857
4286
-
1,1
-
1,5714
1,5714
0,1428
43
0,5714
2857
2857
571
2857
-
1
0
12,571 4286
8
Repitiendo el proceso para determinar de nuevo el pivote y la columna pivote se obtiene C_j C_s
0 V
X
B
_1
0 X
0
_3
0 X_2
0 X
0 s_1
-1 s_2
0 s_3
s_4
_3
0,2857
1
1429
-
0,4
0,2857
-
0,4285
29
1429
0,2857
714 0 X
1
_1
-1 s_
0,5714
0
2857
0
6
1,5714
0
2857
0
j
C_j- r r_j
0
-
0,1428
-
-
0,4285
5714
0,1
0,4285
7143
43
7143
0,1428
-
0,5714
5714
0,1
2857
s
_
_
5
6
0
0
0
0
0 LD
Th eta
5,2857
18,
1429
5
8,5714
15
2857
1
0,5714
12,571 4286
2857
0,1
-
0,5714
1,5714
0,1428
43
0,5714
2857
2857
571 0
s
- -1
-
-
0
0 -1
1429
43 r_
-1
1 -1
12,571
2857
4286
-
1,1
-
1,5714
1,5714
0,1428
43
0,5714
2857
2857
571
2857
-
1
0
12,571 4286
8
Volviendo 1 el pivote y cero los otros valores de la columna pivote se obtiene C_j
0
0
0
V
X
X
X
B
_1
_2
_3
0 X
0
0
1
C_s
_3
0 s_1
-1 s_2
s_3
- 0,45 0,45454
0
-1 s_4
1
0
0 0,09090
_1
0 X
0
1
-
0,1
-
818
0,18181
82
0,18
5
818
r
0
0
0,63636
0,3
-
909 0,09
0,63636
364
64
0,36
1
364
-
0,36363
-
-
0,63
909 0,09
636
0,36363
0,6
64
636
4
1
0
0
0
1
0 L
The
D
ta
3
2
-
4
4
1 C_j-
s_6
-
0 0,09090
_2
s_5
-1
0,18181
55 0 X
0
0
1
8
0
r_j
Ya que todos los valores de C_j-r_j son todos positivos, ssignifica que existe una solución posible al sistema, entonces se pasa a la fase 2. FASE 2 Colocando los datos de la función objetivo en nuestra tabla simplex: C_j
-17
-17
-23
0
0
0
s_3
s_5
LD Theta
0,182
C_s
VB
-23
X_3 0
0
1
-0,4545455
0,18181818
3
-17
X_1 1
0
0
0,09090909 -0,636 0,36363636
4
-17
X_2 0
1
0
0,09090909 0,364
-0,63636364 8
0
0
0
0
C_j-r_j r
X_1 X_2 X_3 s_1
0
0
0
0
Determinando 𝐶𝑗 − 𝑟𝑗 se obtiene C_j
-17
-17
-23
0
0
0
s_3
s_5
LD
0,182
C_s
VB
-23
X_3 0
0
1
-0,4545455
0,18181818
3
-17
X_1 1
0
0
0,09090909 -0,636 0,36363636
4
-17
X_2 0
1
0
0,09090909 0,364
-0,63636364 8
r
-17
-17
-23
7,36363636 0,455
0,45454545
-273
0
0
0
7,36363636 0,455
0,45454545
-273
C_j-r_j r
X_1 X_2 X_3 s_1
0
Theta
Ya que todos los valores de C_j-r_j son positivos, ya se obtiene la solución del problema: Max Z=-273 Es decir Min Z=273 x_1=4 x_2=8 x_3=3 CONCLUSIÓN: Según el método simplex primal a dos fases, Raúl debe producir 4 escritorios del Tipo 1, 8 cantidades del Tipo 2 y 3 cantidades del Tipo 3 para obtener un costo mínimo de 273.
EJERCICIO 4. FUNCIÓN OBJETIVO Minimizar Z = 720x_1+ 215x_2+120x_3+70x_4 SUJETO A LAS RESTRICCIONES: 30x_1 + 5x_2 + 3x_3+ 7x_4≥ 510 17x_1+ 7x_2+ 3x_3+ 5x_4 ≥ 320 11x_1+ 5x_2 + 4x_3 + 2x_4≥ 280 7x_1+ 6x_2+ 5x_3+ 1x_4≥ 170 x_1,x_2,x_3,x_4≥ 0 PRIMERA FASE Minimizar Z = 720x_1+ 215x_2+120x_3+70x_4 SUJETO A LAS RESTRICCIONES: 30x_1 + 5x_2 + 3x_3+ 7x_4-y_1+z_1= 510 17x_1+ 7x_2+ 3x_3+ 5x_4-y_2+z_2=320 11x_1+ 5x_2 + 4x_3 + 2x_4-y_3+z_3= 280 7x_1+ 6x_2+ 5x_3+ 1x_4-y_4+z_4=170 x_1,x_2,x_3,x_4≥ 0 PRIMERA FASE Minimizar r = z_1+z_2+z_3+z_4 Sujeto a las restricciones: 30x_1 + 5x_2 + 3x_3+ 7x_4-y_1+z_1= 510 17x_1+ 7x_2+ 3x_3+ 5x_4-y_2+z_2=320 11x_1+ 5x_2 + 4x_3 + 2x_4-y_3+z_3= 280 7x_1+ 6x_2+ 5x_3+ 1x_4-y_4+z_4=170 x_1,x_2,x_3,x_4≥ 0
x1 x2 x3 x4 y1 y2 y3 y4 z1 z2 z3 z4 LD 0
0
0
0
0
0
0
0
-1
-1
-1
z1 30
5
3
7
-1
0
0
0
1
0
0
0 510
z2 17
7
3
5
0
-1
0
0
0
1
0
0 320
z3 11
5
4
2
0
0
-1
0
0
0
1
0 280
7
6
5
1
0
0
0
-1
0
0
0
1 170
r
z4
-1
0
Formando la tabla Sumando las filas 1, 2, 3,4 y 5 en la primera fila. FASE 1 x1 x2
x3
x4
y1
y2
y3
y4
z1
z2
z3
z4
LD
r
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
z1
30
5
3
7
-1
0
0
0
1
0
0
0
510
z2
17
7
3
5
0
-1
0
0
0
1
0
0
320
z3
11
5
4
2
0
0
-1
0
0
0
1
0
280
z4
7
6
5
1
0
0
0
-1
0
0
0
1
170
x
x2
x3 x4
y1
1 r
-
-23
6
-
-15
1
y
y
y
2
3
4
1
1
1
z1
0
z
z
z
2
3
4
0
0
0
15
3
1
0
z
1
2
7
z
1
3
1
theta
128
5 x
LD
0 5
3
7
-1
0
0
0
1
0
0
0 510
17
7
3
5
0
-
0
0
0
1
0
0 320
18,823
1 5
4
2
0
0
5294 1
0
0
0
1
0 280
25,454 5455
z
7
6
5
1
0
0
0
x
x2 x3
x4
y1
1
x
0
0
0
1 170
24,285
1
4
r
-
0
1
1
-
-
0,1666
-
12,166
8,
6667
1,1666
667
5
0,1666
0,
0,2333
-
6667
1
3333
0,0333
y
y
y
2
3
4
1
1
1
7143 z1
2,1666
z
z
z
2
3
4
0
0
0
6667
LD
theta
175
667 0
0
0
0,0333
0
0
0
17
102
1
0
0
31
7,44
0
1
0
93
29,368
3333
333 x
0
2
4,1666
1,
1,0333
0,5666
-
6667
3
3333
6667
1
0
0
0,5666 667
z
0
3
3,1666
2,
-
0,3666
6667
9
0,5666
6667
0
-
0
-
1
0,3666
667 z
0
4
667
4,8333
4,
-
0,2333
3333
3
0,6333
3333
0
0
-
-
1
0,2333
333
x x x3
x4
y1
r 0 0
y y4
z1
z2
3 -
3,18
0,48
4,
4
8
0
0
1
51
10,551 7241
333
y2
1 2
4211
-1,92 1
z z4
LD
theta
3 1
0,51
2,92 0
0
2
70
-
17,9
84,4
5918
8
37
15,7
328,
6
3333
4 x 1 0
0,
0,19
-
1
04
2
0,05
8
6
0,04 0
0
0,05 6
-0,04 0
0
33
x 0 1
0,
0,24
0,13
2
31
8
6
-0,24 0
0
2 z 0 0
1,
-
-
3
91
1,35
0,06
2
2
4
x 0 0
2,
-
-
3
79
1,83
0,42
2
2
4
x3
x4
y1
x x
0,76
0
1
0,24 0
0,09
-
7421
0,22
2
6361
0
1
0,22
-
3495 7
6
38
0,06
-0,76 1
0
4
1,16 0
-1
0,42
-1,16 0
1
4
0
y2 y
y4
z1
0,03 1
2
0
3
z2 z
z4
LD
0,68
6361
5616
4813
59,1
95
4813
03
05
75
4040
3
1
theta
1
8710
8710
31
98
6
- 0
-
15,5
901,
0,02
0,01
0143
6666
0057
7192
27
67
-
5,75
51,5
3 - 0
0,11
-
0,36 0
0,36
1747
0,18
9627
0,11
9312
3846
9627
85
3381
51
1747
32
15
-
59,1
86,3
1
9
-
0,22
-
-
0,68
-
0,09
6361
0,03 1
4813
0,22
4383
0,68
4040
5983
7421
03
75
6361
95
4813
11
26
0,35
5,38
-
4384
0,03 1
2 x 0 0
6819
4383
5 z 0 0
4
-
7191
09
5,38
1,68
0057
06
15,0
0,96 0
0,04
3381
1799
1,22
0,04
2722
4
-
0,01
0,18
36,3
3
0,02 0
0,45
69,4
48
6 x 0 1
23,8 4615
8 x 1 0
7,44
0,13
3 0
0
16
1 2 r 0 0
-
-
8
-
-
0,65
0,15
6160
1862
5
5
0,41 0
-
0,15
5472
0,35
1862
0,41
8166
6819
15,0
78
8166
46
5472
19
48
4
2
- 0
8
x x x x4
y1
y2
y y4
1 2 3
- 0,034 1
3
3 - 1,226 0,965 0 1,684
-
3610
6160
361
5
8138
3
5
5
- 0
- 15,50 901,6
- 0,020 0 0,017 0,048
8137 59,14 0401
4957 0,048
0573
1919
7106 0,020
0,017
1432
6666
7106
1
8
0573
192
7
7
7220
- 0 0,111
3810 0,369 6275
5
- 0,226
-
- 0,684
0,097
-
3610 0,034 1 3
1605
384
- 0,415 0
0,656 0,151 8625
- 0,369 0
7478 0,183
9
4212 x 0 0 1
theta
0,684
6
3
LD
3839
x 0 1 0 0,452 0,183
z 0 0 0
z z4
4212 0,226
x 1 0 0 0,223
2
z2
3
r 0 0 0 0,097
1
z1
3811
5
361
- 0,151
4727
0,358
8
1662
6275
0,111
3123
8461
1
7479
2
5
- 0,034 1
8137 0,226
- 59,14 86,35
3839
0,684
0401
9832
5
8138
1
6
- 0 0,358 5,386
-
8624 0,415 6
- 5,759 51,53
4728
1661 9
8194 15,04 8
x x2
x x4
1
3
r 0
6,128 0
2,871
0,897
2051
7948
4359
3
7
x 1 1
y1
y2
y y z1
z2
z z LD
3 4
- 0
3 4
- 1 0 2,230
0,102
3,230 0 1
5641
7692
23,84
3
6154
- 0 0
14,61
7692
0,153
-
0,153
8461
8462
theta
-
0,076 0 0
0,076
0,076
9230
9230
0,076
5384
5
9231
8
8
9231
6
- 0 1
-
3,307 0
-
51,53
-
1
8461
15,58
5
1395
23,84
10,68
2,230
6153
9655
7692
8
2
0,769 0 0
23,84
-31
y 0
8,948 0
4,051
1,641
4
7179
2820
0256
3,307
1,641
6923
5
5
4
6923
0256
1
- 0
-
-
2,230
0,897
- 1 0
6,128
2,871
0,897
7692 1
2051
7949
4359
3
x 0
3,205 1
0,794
0,435
- 0 0
3
1282
8717
8974
0,769
0,435
2307
6153
1
9
4
2308
8974
7
8
z 0 3
x
x2
x
1
x4
y1
3
0
0
0
0
x
1
0,0574
0
0,2528
7126
4359
-
y3
y
2
r
1
y
- 0
7356
0
z1
z
0
4
y 2
0
- 0
-
0,1379
0,2068
31
966
- 0
-
z
4
2
4
LD
0
0
0
1 1
1 1
0
- 0
0,0344
0
0,0459 0
- 0
13,793
0,0459
8276
7701
0,0344
77 y
z3
190
0,3103 0 4483
- 1
1034
828 - 1
- 0
1,4827
0,3103
586
448
- 0
2,7471
1,2873
0,4022
0,4482
264
563
989
759
0,4022
-
9885 1
1,4827
-
86,896
5862 1
5517
0,4482 0
10,689
7586
6552
x
0
1,0919
1
5402
3
-
0,1264 0
0,1954
3678
023
- 0
- 0
0,3448
0,1264
276
368
0,3448 0 2759
32,068 9655
FASE 2 x1
x2
x3
x4
y1
y
y3
y
2 z
x
-
-215
-
72
12
0
0
1
0,05747
0
126
4
LD
theta
4
-70
0
0
0
0
0
0,25287
-
0
0,03448
0
13,7931
54,5454
356
0,04597
034
545
86,8965
-420
276
7 y
0
4
y
0
2
x 3
0
-
-
0,31034
0,13793
0,20689
483
1
66
-
0
-
2,74712
1,28735
0,40229
0,44827
64
63
89
59
-
0,12643
0,19540
678
402
23
517
86 -
1
1
1,48275
-
1,09195
0
0
1
0
-
0,34482 76
0
10,6896
-
552
8,30357 14
0
32,0689
-
655
164,117 65
z
x1
x2
x3 x4
-720
-83,965517
0
y1
y2 y3
-93,448276 15,1724138
-41,37931
0 3848,27586
0 0,03448276
0 13,7931034
x1
1 0,05747126
0 0,25287356
y4
0
-0,137931
0
-0,2068966 0,31034483
0
-1,4827586
1 86,8965517
y2
0
-2,7471264
0
-1,2873563
-0,4022989
1
-0,4482759
0 10,6896552
x3
0 1,09195402
1
-0,1954023 0,12643678
0
-0,3448276
0 32,0689655
x
x2
x
1 z
0
-
2
0 88,62068
-
0
theta
4 -
0 13779,31 03
4
4
-
0 0,034482
56 0,045977
76
34
45
-
1 86,89655
-420
1,482758
17
-
0 0,252873
0
- 0,310344 0,206896
0
83
6
2
LD
7
0,137931
0
y
16,55172
26
y
y3
97 17,93103
1
4
y
42,58620
1 0,057471
0
y1
3
x
y
x4
-0,045977
0
y4 LD
-
0
2,747126
0 1,091954
3
02
6 -
1
1,287356 0,402298
4 x
-
3 1
9
- 0,126436 0,195402 3
0 13,79310 54,54545
78
0
-
0 10,68965
-
0,448275
52 8,303571
9
4
-
0 32,06896
-
0,344827
55 164,1176
6
5
x1
x2
x3
x4
z
-350,45
y1
-62,727273
0
0
-1,8181818
0
-28,636364
0 8945,45455
x1
3,95455 0,22727273
0
1
-0,1818182
0 0,13636364
0 54,5454545
y4
0,81818
-0,0909091
0
0 0,27272727
0
-1,4545455
1 98,1818182
y2
5,09091
-2,4545455
0
0
-0,6363636
1
-0,2727273
0 80,9090909
x3
0,77273 1,13636364
1
0 0,09090909
0
-0,3181818
0 42,7272727
y3
y2 y3
y4
LD
x1
x2
-350,45
-62,727273
0
0
-1,8181818
0
-28,636364
0 8945,45455
x1 3,95455 0,22727273
0
1
-0,1818182
0 0,13636364
0 54,5454545
y4 0,81818
-0,0909091
0
0 0,27272727
0
-1,4545455
1 98,1818182
y2 5,09091
-2,4545455
0
0
-0,6363636
1
-0,2727273
0 80,9090909
x3 0,77273 1,13636364
1
0 0,09090909
0
-0,3181818
0 42,7272727
z
x3 x4 y1
y2
Entonces
x_1=0 x_2=0 x_3=42.7272727 x_4=54.5454545 Z=8945.4545 CONCLUSIÓN:
Min Z=8945.4545 x_1=0 x_2=0 x_3=42.7272727 x_4=54.5454545
y4 LD
theta
EJERCICIO 5. Para desarrollar el ejercicio se requiere consultar la siguiente referencia: Resuelva el ejercicio 1 de maximización por el método simplex dual, recuerde que en éste método la solución comienza siendo infectable y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. Resuelva por cualquier método, recomendado simplex algebraico: Cantidad de cada uno de las variables a fabricarse, según el método de las dos fases del simplex dual.
FORMULACIÓN DEL PROBLEMA Sea x_1=: Jugo 1 de Pera x_2=: Jugo 2 de manzana x_3=: Jugo 3 tropical FUNCIÓN OBJETIVO Max Z=600x_1+400x_2+500x_3
RESTRICCIONES
20x_1+30x_2+20x_3≥1500 30x_1+20x_2+10x_3≤1700 20x_1+20x_2+20x_3≤1300 x_1,x_2,x_3≥0
Estandarizando se obtiene FUNCIÓN OBJETIVO Max Z=600x_1+400x_2+500x_3+0t_1+0s_2+0s_3 RESTRICCIONES
20x_1+30x_2+20x_3-t_1=1500 30x_1+20x_2+10x_3+s_2=1700 20x_1+20x_2+20x_3+s_3=1300 x_1,x_2,x_(3,) t_1,s_2,s_3≥0
Multiplicando por (-1) la primera restricción para tener una matriz identidad de tamaño 3x3 en la variables básica. Así entonces queda: FUNCIÓN OBJETIVO Max Z=600x_1+400x_2+500x_3+0t_1+0s_2+0s_3
RESTRICCIONES
-20x_1-30x_2-20x_3+t_1=-1500 30x_1+20x_2+10x_3+s_2=1700 20x_1+20x_2+20x_3+s_3=1300 x_1,x_2,x_(3,) t_1,s_2,s_3≥0
La tabla simplex queda determinada de la siguiente manera:
Z
600
VB
X_1
400 X_2
500 X_3
0 t_1
0 s_2
0 s_3
0 LD
t_1
-20
-30
-20
1
0
0
-1500
s_2
30
20
10
0
1
0
1700
s_3
20
20
20
0
0
1
1300
Tomando el menor valor de LD el cual nos indica la fila pivote y de esta se toma el menor valor en este caso -30
Z VB
600 X_1
400 X_2
500 X_3
0 t_1
0 s_2
0 s_3
0 LD
t_1
-20
-30
-20
1
0
0
-1500
s_2
30
20
10
0
1
0
1700
s_3
20
20
20
0
0
1
1300
Lo que significa que sale la variable 𝑡1 de la base y entra la variable 𝑥2 Pivoteando se obtiene
Z
333,333333
VB
X_1
X_2
0,66666667
1
s_2
16,6666667
0 -3,33333333
s_3
6,66666667
0
0 X_2
233,333333
13,3333333
X_3
t_1
0 s_2
0,66666667 -0,03333333
6,66666667
0 s_3
-20000 LD
0
0
50
0,66666667
1
0
700
0,66666667
0
1
300
De nuevo se seleccionan las filas y columna pivote, ya que no existe valores en LD negativos entonces se toma cualquier valor de tal manera que simplifiquemos los valores de 𝑥1 y 𝑥3
Z
333,333333
VB
X_1
X_2
0,66666667
1
s_2
16,6666667
0 -3,33333333
s_3
6,66666667
0
Z VB
0 X_2
233,333333 X_3
13,3333333 t_1
0 s_2
0,66666667 -0,03333333
6,66666667
0 s_3
-20000 LD
0
0
50
0,66666667
1
0
700
0,66666667
0
1
300
Es decir sale de la base 𝑠2 y entra la variable 𝑥3 1500 X_1
0 X_2
0 X_3
60 t_1
70 s_2
0 s_3
29000 LD
X_2
4
1
0
0,1
0,2
0
190
X_3
-5
0
1
-0,2
-0,3
0
-210
s_3
40
0
0
2
2
1
1700
De nuevo se selecciona la fila y columna pivote
Z
1500 X_1
VB
0 X_2
0 X_3
60 t_1
70 s_2
0 s_3
29000 LD
X_2
4
1
0
0,1
0,2
0
190
X_3
-5
0
1
-0,2
-0,3
0
-210
s_3
40
0
0
2
2
1
1700
Es decir sale de la base la variable 𝑠3 y entra la variable 𝑥1 Pivoteando se obtiene
Z VB
0 X_1
0 X_2
0 X_3
-15 t_1
-5 s_2
-37,5 s_3
-34750 LD
X_2
0
1
0
-0,1
0
-0,1
20
X_3
0
0
1
0,05
-0,05
0,125
2,5
X_1
1
0
0
0,05
0,05
0,025
42,5
Como se ha restaurado la factibilidad y se cumple el criterio de optimalizad, la base actual es óptima y su solución es óptima es: x_2=20 x_3=2,5 x_1=42,5 MaxZ=34750 CONCLUSIÓN Por el método simplex dual se sugiere que se deben producir 42.5 jugos 1 de Pera, 20 jugos 2 de manzana y 2.5 jugos 3 tropical con una utilidad de 34750.
EJERCICIO 6. Resuelva el ejercicio 3 de minimización por el método simplex dual, recuerde que en éste método la solución comienza siendo infactible y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. Resuelva por cualquier método, recomendado simplex algebraico FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3 RESTRICCIÓN
2x_1+2x_2+3x_3≥33 3x_1+2x_2+x_3≥31 2x_1+3x_2+x_3≥35 x_1,x_2,x_3≥0
Agregando las variables de holgura y de exceso se tiene FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3+0*t_1+0*t_2+0*t_3 RESTRICCIÓN
2x_1+2x_2+3x_3-t_1=33 3x_1+2x_2+x_3-t_2=31 2x_1+3x_2+x_3-t_3=35 x_1,x_2,x_3,t_1,t_2,t_3≥0
Multiplicando por (-1) las restricciones para tener una matriz identidad de tamaño 3x3 en la variables básica. Así entonces queda: FUNCIÓN OBJETIVO Min Z=17x_1+17x_2+23x_3+0*t_1+0*t_2+0*t_3 RESTRICCIÓN
-2x_1-2x_2-3x_3+t_1=-33 -3x_1-2x_2-x_3+t_2=-31 -2x_1-3x_2-x_3+t_3=-35 x_1,x_2,x_3,t_1,t_2,t_3≥0
La tabla simplex queda determinada de la siguiente manera:
Z VB
17 X_1
17 X_2
23 X_3
0 t_1
0 t_2
0 t_3
0 LD
t_1
2
2
3
-1
1
0
-33
t_2
3
2
1
0
0
-1
-31
t_3
2
3
1
0
0
0
-35
Se selecciona el menor valor de LD el cual nos indica la fila pivote y de esta fila se selecciona el menor valor en este caso −3 Z VB
17 X_1
17 X_2
23 X_3
0 t_1
0 t_2
0 t_3
0 LD
t_1
-2
-2
-3
1
0
0
-33
t_2
-3
-2
-1
0
1
0
-31
t_3
-2
-3
-1
0
0
1
-35
Lo que significa que la variable que sale de la base es 𝑡3 y la variable que entra es 𝑥_2 Pivoteando se obtiene: Z
5,66666667
0
17,3333333
X_2 X_3
0
0
VB
X_1
t_1
-0,66666667
0 -2,33333333
1
0 -0,66666667 -9,66666667
t_2
-1,66666667
0 -0,33333333
0
1 -0,66666667 -7,66666667
x_2
0,66666667
1
0
0 -0,33333333
0,33333333
t_1 t_2
5,66666667 -198,333333 t_3
LD
11,6666667
Se determina de nuevo la fila y la columna pivote Z C_s
5,66666667
VB
X_1
0
17,3333333
X_2 X_3
0 t_1
0 t_2
5,66666667 -198,333333 t_3
LD
0 t_1
-0,66666667
0 -2,33333333
1
0 -0,66666667 -9,66666667
0 t_2
-1,66666667
0 -0,33333333
0
1 -0,66666667 -7,66666667
0 x_2
0,66666667
1
0
0 -0,33333333
0,33333333
11,6666667
Es decir la variable que sale de la base es 𝑡1 y la que entra es 𝑥3 Z VB
0,71428571 X_1
0 X_2
0 X_3
7,42857143 t_1
0 t_2
0,71428571 -270,142857 t_3
x_3
0,28571429
0
1 -0,42857143
0
t_2
-1,57142857
0
0 -0,14285714
1 -0,57142857 -6,28571429
x_2
0,57142857
1
0
0 -0,42857143
0,14285714
0,28571429
LD 4,14285714
10,2857143
De nuevo se selecciona la fila y columna pivote Z VB
0,71428571 X_1
0 X_2
0 X_3
7,42857143 t_1
0 t_2
0,71428571 -270,142857 t_3
X_3
0,28571429
0
1 -0,42857143
0
t_2
-1,57142857
0
0 -0,14285714
1 -0,57142857 -6,28571429
x_2
0,57142857
1
0
0 -0,42857143
0,14285714
0,28571429
LD 4,14285714
10,2857143
Es decir sale de la base la variable 𝑡2 y entra la variable 𝑥1 Pivoteando se obtiene: Z VB
0 X_1
0 X_2
0 X_3
7,36363636 t_1
x_3
0
0
1 -0,45454545
X_1
1
0
x_2
0
1
0,45454545 t_2
0,45454545 t_3
-273 LD
0,18181818
0,18181818
3
0
0,09090909 -0,63636364
0,36363636
4
0
0,09090909
0,36363636 -0,63636364
8
Como se ha restaurado la factibilidad y se cumple el criterio de optimalidad, la base actual es óptima y su solución es óptima es: 𝑥3 = 3 𝑥1 = 4 𝑥2 = 8 min 𝑍 = 273 CONCLUSIÓN: Según el método simplex dual, Raúl debe producir 4 escritorios del Tipo 1, 8 cantidades del Tipo 2 y 3 cantidades del Tipo 3 para obtener un costo mínimo de 273.
EJERCICIO 7 Como actividad grupal ingresen al Entorno Práctico, en este espacio se presentan videos para el uso del Complemento Solver de Excel y tutoriales prácticos para desarrollar las actividades propuestas, recuerden anexar mediante capturas de pantalla a su trabajo colaborativo definitivo, el ingreso y tabla de resultados para los ejercicios planteados. En este mismo espacio pueden revisar cuidadosamente la guía para el uso de recursos educativos, el uso del complemento Solver les ayudará a dar solución a los ejercicios planteados en esta tarea. a. Solución de Ejercicio 1 por Solver: FUNCIÓN OBJETIVO 𝑀𝑎𝑥 𝑍 = 600𝑥1 + 400𝑥2 + 500𝑥3 RESTRICCIONES
20𝑥1 + 30𝑥2 + 20𝑥3 ≥ 1500
30𝑥1 + 20𝑥2 + 10𝑥3 ≤ 1700
20𝑥1 + 20𝑥2 + 20𝑥3 ≤ 1300
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Resultado 𝒙𝟏
𝒙𝟐
𝒙𝟑
𝟒𝟐, 𝟓
20
2,5
b. Solución del Ejercicio 3 por Solver FUNCIÓN OBJETIVO 𝑀𝑖𝑛 𝑍 = 17𝑥1 + 17𝑥2 + 23𝑥3 RESTRICCIÓN
𝒙𝟏
2𝑥1 + 2𝑥2 + 3𝑥3 ≥ 33
3𝑥1 + 2𝑥2 + 𝑥3 ≥ 31
2𝑥1 + 3𝑥2 + 𝑥3 ≥ 35
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
𝒙𝟐 4
Z
𝒙𝟑 8 273
3