Investigación de operaciones I - Primer parcial
Julio ReolonApuntes17 de Octubre de 2018
1.493 Palabras (6 Páginas)331 Visitas
Universidad de Montevideo – Facultad de Ingeniería
Investigación de operaciones I - Primer parcial
Solución 25/4/13
Ejercicio 1
La siguiente tabla resume los hechos importantes sobre dos productos, A y B, y los recursos Q, R y S, requeridos para producirlos.
Recurso | Recursos utilizados por unidad de producto | Cantidad de recursos disponibles | |
Producto A | Producto B | ||
Q | 2 | 1 | 2 |
R | 1 | 2 | 2 |
S | 3 | 3 | 4 |
Ganancia/Unidad | 3 | 2 |
Todas las suposiciones de programación lineal se cumplen.
- Formule un modelo de programación lineal
- Resuelva este modelo en una gráfica y halle la solución óptima.
- Resuelva el problema usándola forma tabular del método simplex, paso a paso.
Respuesta Ejercicio 1:
- Variables de decisión: A = lotes del producto A; y B = lotes del producto B.
Función objetivo: Maximizar ganancia Z = 3A + 2B
Restricciones:
2A + B <= 2
A + 2B <= 2
3A + 3B <= 4
A y B >= 0
- Solución: A = B = 2/3; Z =10/3
[pic 1]
- Forma ampliada:
Función objetivo: Maximizar ganancia Z = 3A + 2B
Restricciones:
2A + B + H1 = 2
A + 2B + H2 = 2
3A + 3B +H3 = 4
A, B, H1, H2, H3 >= 0
VB | EC | Z | A | B | H1 | H2 | H3 | LD |
Z | (0) | 1 | -3 | -2 | 0 | 0 | 0 | 0 |
H1 | (1) | 0 | 2 | 1 | 1 | 0 | 0 | 2 |
H2 | (2) | 0 | 1 | 2 | 0 | 1 | 0 | 2 |
H3 | (3) | 0 | 3 | 3 | 0 | 0 | 1 | 4 |
Entra A y sale H1 | ||||||||
Z | (0) | 1 | 0 | -1/2 | 3/2 | 0 | 0 | 3 |
A | (1) | 0 | 1 | ½ | ½ | 0 | 0 | 1 |
H2 | (2) | 0 | 0 | 3/2 | -1/2 | 1 | 0 | 1 |
H3 | (3) | 0 | 0 | 3/2 | -3/2 | 0 | 1 | 1 |
Entra B y sale H2 | ||||||||
Z | (0) | 1 | 0 | 0 | 4/3 | 1/3 | 0 | 10/3 |
A | (1) | 0 | 1 | 0 | 2/3 | -1/3 | 0 | 2/3 |
B | (2) | 0 | 0 | 1 | -1/3 | 2/3 | 0 | 2/3 |
H3 | (3) | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
Solución: A = B = 2/3 y H1 = H2 = H3 = 0 con Z =10/3
Ejercicio 2
Dado el siguiente problema:
Maximizar: Z = -3X1 + X2 - 2X3 - X4
sujeto a: 2X 1 + X2 + 2X3 >= 4
-3X1 + X2 - 2X3 <= 6
X2 - 4X3 - X4 = - 1
X1 + X2 = - X3
X1 , X2, X3 y X4 >= 0
- Plantee la forma estándar para aplicar el algoritmo simplex.
- Plantee la tabla inicial e indique la variable entrante y la saliente en la primera iteración.
- Plantee el problema dual.
Respuesta Ejercicio 2:
- Forma estándar aumentada:
Maximizar: Z = -3X1 + X2 - 2X3 - X4 – MX6 – MX8 – MX9
sujeto a: 2X 1 + X2 + 2X3 - X5 + X6 = 4
-3X1 + X2 - 2X3 + X7 = 6
- X2 + 4X3 + X4 + X8 = 1
X1 + X2 + X3 +X9 = 0
Xi >= 0 para i = 1, 2, …, 9
| |||||||||||||
Variables básicas | Ecuación | Z | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | lado derecho | |
Z | 0 | 1 | 3 | -1 | 2 | 1 | 0 | M | 0 | M | M | 0 | |
X6 | 1 | 0 | 2 | 1 | 2 | 0 | -1 | 1 | 0 | 0 | 0 | 4 | |
X7 | 2 | 0 | -3 | 1 | -2 | 0 | 0 | 0 | 1 | 0 | 0 | 6 | |
X8 | 3 | 0 | 0 | -1 | 4 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | |
X9 | 4 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
Tabla inicial: Haciendo operaciones en el renglón 0, para llevar al formato estándar. | |||||||||||||
Variables básicas | Ecuación | Z | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | lado derecho | Cociente |
Z | 0 | 1 | 3 -3M | -1 -M | 2 -7M | 1-M | M | 0 | 0 | 0 | 0 | -5M | |
X6 | 1 | 0 | 2 | 1 | 2 | 0 | -1 | 1 | 0 | 0 | 0 | 4 | 2 |
X7 | 2 | 0 | -3 | 1 | -2 | 0 | 0 | 0 | 1 | 0 | 0 | 6 | Neg |
X8 | 3 | 0 | 0 | -1 | 4 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | ¼ |
X9 | 4 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
En primera instancia, debería entrar X3 por tener el coeficiente más negativo (2-7M) y debería salir X9, pero esta variable básica ya tiene valor 0, por lo tanto no puede disminuir, porque se haría negativa. Hay que buscar otra variable entrante. Con X1 y X2 pasa exactamente lo mismo: no pueden ingresar a la base sin que X9 se haga negativa. Sólo nos queda X4 como candidata a entrar a la base (la única variable no básica que queda con coeficiente negativo en el renglón 0); y por la regla del cociente, la variable que sale es X8.
...