AYUDA_07_OPE1_2S_2014

INVESTIGACION DE OPERACIONES 1
AYUDANTIA Nº7
PROGRAMACION LINEAL ENTERA
Profesor: Felicindo H. Cortes

Ayudante: Sr. Diego MugueñoCortes.

Fecha: Martes 28/10/2014

NOMBRE COMPLETO:
PROBLEMA N°1
(20 puntos)
Considerando el siguiente PPL y tabla simplex relajada:
MaxZ= 20 X1 + 16 X2
Sujeto a:
5 X1 + 2 X2 ≤ 30
2 X1 + 3 X2 ≤ 25
X1; X2 ≥ 0, Entero

Cnb
Cb
Vb
20
X1
16
X2
(Zs-Cs)

0
X3
3/11
-2/11
28/110
X4
-2/11
5/11
40/11

Sol.
Xb
40/11
65/11
1840/11

Dado el problema lineal y el tableu simplex final, resolver solución óptima entera:a) Usando método gráfico. (6 puntos)
b) Usando Simplex Branch & Bound. (10 puntos)
c) Comente la solución entera encontrada. (4puntos)
Solución: Z = 160, X1= 4, X2 =5
PROBLEMA N°2
(20 puntos)
Sea el siguiente problema de programación lineal y la tabla solución simplexrelajada que se adjunta:
Minimizar Z = 4 X1 - 1 X2 + 3 X3
Sujeto a:
4 X1 - 3 X2 + 2 X3 ≥ 20
1 X1 + 1 X2 + 3 X3 ≥ 15
3 X1 + 1 X2 + 0 X3≤ 24
2 X1 + 2 X2 + 1 X3 ≤ 30
X1; X2; X3 ≥ 0; Entero

Cb
Vb
-4
X1
-3
X3
0
X6
0
X7
(Zs – Cs)

1

0

0

Sol.

X2
-11/8
5/4
41/8
7/2
3/4

X4-3/8
1/4
9/8
1/2
3/4

X5
1/4
-1/2
-3/4
0
1/2

Xb
15/4
5/2
51/4
20
-45/2

Se pide:
a) Utilice el algoritmo Gomory para encontrar lasolución óptima entera. (15 puntos)
b) Comente (todo) la solución óptima encontrada. (5 puntos)
Respuesta: Z = 24; X1 = 3; X2 =0; X3 =4