E.
P: Ingeniería de Sistemas e Informática
CURSO: Investigación de Operaciones I
TEMA: Ejercicios de Método Simplex
DOCENTE: Godofredo Poccori Umeres
INTEGRANTES:
Oscar Álvarez Chevarria
Lizbeth Dávalos Bautista
Juvenal Jherson Soto Mamani
Joseph Andre Zuñiga Ccahuana
Ilde Brando Taipe Velasquez
Ejercicio 6
Considere el problema de programación lineal solo
con enteros, encuentre la solución óptima con el
método simplex y compruebe con solver su
respuesta.
Resolver:
Max Z=4X1 + 3X2
Sujeto a:
2X1 + X2 <= 2
3X1 + 4X2 <= 6
Con:
X1, X2 >=0
Paso 1 Convirtiendo las desigualdades en igualdades
Z-4X1-3X2 = 0
2X1+X2+S1=2
3X1+4X2+S2=6
Paso 2 Construir la tabla simplex
Z X1 X2 S1 S2 R
1 -4 -3 0 0 0
0 2 1 1 0 2
0 3 4 0 1 6
Paso 3 Identificar la columna pivot en la tabla simplex
Z X1 X2 S1 S2 R
1 -4 -3 0 0 0
0 2 1 1 0 2
0 3 4 0 1 6
Paso 4 Identificar la fila pivot dividiendo la columna pivote entre las constantes R
Z X1 X2 S1 S2 R
1 -4 -3 0 0 0 R/X1
0 2 1 1 0 2 2/2=1
0 3 4 0 1 6 6/3=2
Paso 5 Identificar el elemento pivot
Z X1 X2 S1 S2 R
1 -4 -3 0 0 0
0 1 1 1 0 2
0 3 4 0 1 6
Paso 6 Convertir el elemento pivot en unidad
Z X1 X2 S1 S2 R
1 -4 -3 0 0 0
0 1 1/2 1/2 0 1 2*1/2
0 3 4 0 1 6
Paso 7 Convertir todos los elementos que están por encima y por debajo del elemento pivot a cero
4*f2+f1
-3*F2+F3
Z X1 X2 S1 S2 R
f1 1 0 -1 2 0 4
f2 0 1 1/2 1/2 0 1
f3 0 0 5/2 -3/4 1 6
Paso 8 Volvemos al paso 3(Identificar la columna pivot en tabla simplex)
Z X1 X2 S1 S2 R
f1 1 0 -1 2 0 4
f2 0 1 1/2 1/2 0 1
f3 0 0 5/2 -3/4 1 3
Paso 9 Identificar la fila pivot
Z X1 X2 S1 S2 R
f1 1 0 -1 2 0 4 R/X2
f2 0 1 1/2 1/2 0 1 1/ (1/2) =2
f3 0 0 5/2 -3/4 1 3 3/ (5/2) =6/5
Convertir el elemento pivot a
Paso 10 unidad
Z X1 X2 S1 S2 R
f1 1 0 -1 2 0 4
f2 0 1 1/2 1/2 0 1
f3 0 0 1 -3/10 2/5 6/5 5/2*2/5=1
Paso 11 Convertir todos los elementos que están por encima y por debajo del elemento pivot a cero
f3+f1
(-1/2) *f3+f2
Z X1 X2 S1 S2 R
f1 1 0 0 17/10 0 26/5
f2 0 1 0 13/20 -1/5 2/5
f3 0 0 1 -3/10 2/5 6/5
Paso 12 Mi nueva matriz es:
Z X1 X2 S1 S2 R
1 0 0 1 2 2
0 1 0 3/10 1/5 2/5
0 0 1 1/5 2/5 6/5
Z= 26/5 5,2 5
X1 = 2/5 0,40 0
X2 = 6/5 1,2 1
Resolver:
Max Z=4X1 + 3X2 x1= 0,4
x2= 1,2
Sujeto a:
2X1 + X2 <= 2 Z= 5,2
3X1 + 4X2 <= 6
Con: Restricciones:
X1, X2 >=0 R1= 2 <= 2
R2= 6 <= 6
Resolver:
Max Z=1X1 + 1X2
Sujeto a:
7X1 + 9X2 <=63
9X1 + 5X2 <=45
3X1 + 1X2 <=12
Con:
X1, X2 >=0
X2 entero
Paso 1 Convirtiendo las desigualdades en igualdades
Z-X1-X2=0
7X1+9X2+S1=63
9X1+5X2+S2=45
3X1+X2+S3=12
Paso 2 Construir la tabla simplex
Z X1 X2 S1 S2 S3 R
1 -1 -1 0 0 0 0
0 7 9 1 0 0 63
0 9 5 0 1 0 45
0 3 1 0 0 1 12
Paso 3 Identificar la columna pivot en la tabla simplex
Z X1 X2 S1 S2 S3 R
1 -1 -1 0 0 0 0
0 7 9 1 0 0 63
0 9 5 0 1 0 45
0 3 1 0 0 1 12
Paso 4 Identificar la fila pivot dividiendo la columna pivote entre las constantes R
Z X1 X2 S1 S2 S3 R
1 -1 -1 0 0 0 0 R/X2
menor
0 7 9 1 0 0 63 63/9=7
0 9 5 0 1 0 45 45/5=9
0 3 1 0 0 1 12 12/1=12
Paso 5 Identificar el elemento pivot
Z X1 X2 S1 S2 S3 R
1 -1 -1 0 0 0 0
0 7 9 1 0 0 63
0 9 5 0 1 0 45
0 3 1 0 0 1 12
Paso 6 Convertir el elemento pivot en unidad
Z X1 X2 S1 S2 S3 R
f1 1 -1 -1 0 0 0 0
f2 0 7/9 1 1/9 0 0 7 9*1/9 =1
f3 0 9 5 0 1 0 45
f4 0 3 1 0 0 1 12
Paso 7 Convertir todos los elementos que están por encima y por debajo del elemento pivot a cero
f2+f1
(-5) *f2+f3
(-1) *f2+f4
Z X1 X2 S1 S2 S3 R
f1 1 -2/9 0 1/9 0 0 7
f2 0 7/9 1 1/9 0 0 7
f3 0 46/9 0 -5/9 1 0 10
f4 0 20/9 0 -1/9 0 1 5
Paso 8 Volvemos al paso 3(Identificar la columna pivot en tabla simplex)
Z X1 X2 S1 S2 S3 R
f1 1 -2/9 0 1/9 0 0 7
f2 0 7/9 1 1/9 0 0 7
f3 0 46/9 0 -5/9 1 0 10
f4 0 20/9 0 -1/9 0 1 5
Paso 9 Identificar la fila pivot
Z X1 X2 S1 S2 S3 R
f1 1 -2/9 0 1/9 0 0 7 R/X2
f2 0 7/9 1 1/9 0 0 7 7/ (7/9) = 9
f3 0 46/9 0 -5/9 1 0 10 10/ (46/9) =45/23
f4 0 20/9 0 -1/9 0 1 5 5/ (20/9) =9/4
Convertir el elemento pivot a
Paso 10 unidad
Z X1 X2 S1 S2 S3 R
f1 1 -2/9 0 1/9 0 0 7
f2 0 7/9 1 1/9 0 0 7
f3 0 1 0 -5/46 9/46 0 45/23 46/9*9/46 =1
f4 0 20/9 0 -1/9 0 1 5
Paso 11 Convertir todos los elementos que están por encima y por debajo del elemento pivot a cero
2/9*f3+f1
(-7/9) *f3+f2
(-20/9) *f3+f4
Z X1 X2 S1 S2 S3 R
f1 1 0 0 2/23 1/23 0 171/23
f2 0 0 1 9/46 -7/46 0 126/23
f3 0 1 0 -5/46 9/46 0 45/23
f4 0 0 0 3/23 -10/23 1 15/23
Paso 12 Mi nueva matriz es:
Z X1 X2 S1 S2 S3 R
1 0 0 2/23 1/23 0 171/23
0 0 1 9/46 -7/46 0 126/23
0 1 0 -5/46 9/46 0 45/23
0 0 0 3/23 -10/23 1 15/23
Z= 171/23 7,43478261
X1= 45/23 1,95652174
X2= 126/23 5,47826087 X2 entero = 5
Resolver:
Max Z=1X1 + 1X2 X1= 1,95652174
X2= 5,47826087
Sujeto a:
7X1 + 9X2 <=63 Z= 7,43478261
9X1 + 5X2 <=45
3X1 + 1X2 <=12 Restricciones:
Con: R1= 63 <= 63
X1, X2 >=0 R2= 45 <= 45
X2 entero R3= 11,3478261 <= 12
Una fábrica de zapatos de cuero produce dos líneas: modelos de lujo y modelos
regulares. Cada tipo modelo requiere un pie cuadrado de cuero. Un modelo regular
necesita 1 hora de mano de obra, mientras que un modelo de lujo requiere 2 horas
de mano de obra. Cada semana se dispone de 40 pies cuadrados de cuero y de 60
horas de mano de obra. Cada zapato regular genera una utilidad de 30 mil y cada
modelo de lujo representa una utilidad de 40 mil.
Para plantear el modelo se emplearán las variables:
x1: número de zapatos de lujo producidos a la semana
x2: número de zapatos regulares producidos a la semana
Max z = 40x1
+ 30x2
x1 + x2 ≤ 40 2x1 + x2 ≤ 60 x1,
x2 ≥ 0
covertirmos
Z-30000x1 - 40000x2=0 X1+X2+S1=40
2X1+X2+S2=60
1) la tabla simplex
Z X1 X2 S1 S2 R
1 -30000 -40000 0 0 0
0 1 1 1 0 40
0 2 1 0 1 60
2) la columna pivot y la fila pivot
Z X1 X2 S1 S2 R
1 -30000 -40000 0 0 0
0 1 1 1 0 40
0 2 1 0 1 60
3) convertir el pivot en la unidad
Z X1 X2 S1 S2 R
1 -30000 -40000 0 0 0
0 1 1 1 0 40
0 2 1 0 1 60
Z X1 X2 S1 S2 R
1 -30000 -40000 0 0 0
0 1 1 1 0 40
0 2 1 0 1 60
4) Convertir por encima y abajo del pivot a cero
Z X1 X2 S1 S2 R
1 -70000 0 -40000 0 1600000
0 1 1 1 0 40
0 1 0 -1 1 20
5)Identificamos la nueva fila y columna pivot
Z X1 X2 S1 S2 R
1 -70000 0 -40000 0 1600000
0 1 1 1 0 40 40/1=40
0 1 0 -1 1 20 20/1=20
6)Identificamos el elemento pivot
Z X1 X2 S1 S2 R
1 -70000 0 -40000 0 1600000 *1/1
0 1 1 1 0 40
0 1 0 -1 1 20
7)convertimos el elemento pivot
Z X1 X2 S1 S2 R
1 -70000 0 -40000 0 1600000
0 1 1 1 0 40
0 1 0 -1 1 20
8)Convertir en ceros los elementos que se encuentran por encima y por debajo del pivot
Z X1 X2 S1 S2 R
1 -70000 0 -40000 0 160000 70000*f3+f1
0
0 1 1 1 0 40 -1*f3+f2
0 1 0 -1 1 20
Z X1 X2 S1 S2 R
1 0 0 30000 70000 3000000
0 0 1 0 -1 20
0 1 0 -1 1 20
9) Final de la tabla simplex
Z X1 X2 S1 S2 R
1 0 0 30000 70000 3000000
0 0 1 0 -1 20
0 1 0 -1 1 20
x1= 20
x2= 20
z= 3000000
