Bibliografias

Investigaci´ n Operativa
o

Ejercicios resueltos del examen
de los temas 3 y 4
Sergio Garc´a Mondaray
ı
04621336-S

Escuela Superior de Inform´ tica de Ciudad Real
a
Universidad de Castilla-La Mancha

Ejercicio 1
Enunciado
Resuelva el siguiente problema sin utilizar variables artificiales y usando un m´ todo tabular:
e
Min Z = 6x1 + 3x2
2x1 − 3x2 ≥ 3
x1 + x2 ≥ 4
x1 , x2 ≥ 0Soluci´ n
o
Vamos a emplear el algoritmo Dual del Simplex para resolver el ejercicio. En primer lugar expresamos el problema en forma estandar:
Max Z = −6x1 − 3x2 − 0x3 − 0x4


−2x1 + 3x2 ≤ −3 
 −2x1 + 3x2 + x3 = −3
−x1 − x2 ≤ −4
−x1 − x2 + x4 = −4
⇒


x1 , x2 ≥ 0
x1 , x2 ≥ 0
Iter. 1) Planteamos la primera tabla del Simplex:
CB
0
0
-

XB
x3
x4
Z
Z-Ci

Y1
-2
-1
06

Y2
3
-1
0
3

Y3
1
0
0
0

Y4
0
1
0
0

B
-3
-4
0
-

Iter. 2) Como en B aparecen valores negativos, saldr´ la variable m´ s negativa: x4 . Para ver qu´
a
a
e
variable entra: max{− (−6) , −(−3)} = 6 ⇒ entra x1 .
CB

XB

Y1

Y2

Y3

Y4

B

Op

0
-6
-

x3
x1
Z
Z-Ci

0
1
-6
0

5
1
-6
-3

1
0
0
0

-2
-1
6
0

5
4
-24
-

F1= F1 + 2F2
F2 = −F2
-

Iter. 3) Ahora actuamos como en el Simplex normal: entra la variable x2 , al tener el valor m´ s
a
´
negativo en la ultima fila, y sale x3 :
CB
-3
-6
-

XB
x2
x1
Z
Z-Ci

Y1
0
1
-6
0

Y2
1
0
-3
0

Y3
1/5
-1/5
3/5
3/5

Y4
-2/5
-3/5
24/5
24/5

B
1
3
-21
-

Op
F1 = 1/5F1
F2 = F2 − F1
2

´
Iter. 4) Como todos los valores sonpositivos, tanto de la ultima fila como de la columna B ,
hemos terminado el algoritmo, obteniendo la siguiente soluci´ n optima:
o´
Z = 21; x1 = 3, x2 = 1

1

Ejercicio 3 (Adicionales)

Enunciado
Una f´ brica de coches tiene especial inter´ s en los coches descapotables, pero nunca ha fabricado
a
e
uno y no sabe qu´ beneficio podr´an reportarle. Por tanto quiere compararlos con elcoche que m´ s
e
ı
a
vende. Para la fabricaci´ n de estos coches se necesitan 3 horas en pintar en coche descapotable y 5
o
el normal. Para mirar si todo est´ correcto se necesitan 4 horas en el descapotable y 3 en el normal.
a
El precio en el mercado del descapotable es de 50.000e y 40.000e el coche normal. Adem´ s se
a
sabe que el coste de fabricaci´ n del descapotable es de 15.000e y eldel normal de 2.000e.
o
a) Calcule el beneficio de la empresa.
b) Obtenga el dual y resu´ lvalo.
e
c) Cu´ les son los precios sombra de la pintura y del control de calidad.
a
d) Si a la f´ brica le ofertan 300 horas semanales a un coste de 1000 se aceptar´a la oferta.
a
ı
Soluci´ n
o
En primer lugar vamos a plantear una tabla resumen con los datos del problema:
Horas de pinturaRevisi´ n
o
Coste de fabricaci´ n
o
Beneficio

Normal
5
3
2 mil
40 mil

Descapotable
3
4
15 mil
50 mil

Las variables de decisi´ n de nuestro problema son:
o
x1 = N´ mero de coches normales, x2 = N´ mero de coches descapotables
u
u
Ahora planteemos la funci´ n objetivo y las restricciones:
o
Max Z = 40x1 + 50x2
R0
R1
R2
R3

:
:
:
:

x1 , x2 ≥ 0
5 x 1 + 3 x 2 ≤ Hp
3 x1 + 4 x 2 ≤ Hr
2x1 + 15x2 ≤ P

Siendo Hp el n´ mero de horas disponibles para pintura, Hr el n´ mero de horas disponibles para
u
u
revisi´ n de los veh´culos, y P el presupuesto de la empresa para construir los veh´culos. Podemos
o
ı
ı
ahora resolver el problema en funci´ n de Hp , Hr y P :
o
3

a) Resolvemos el problema por el algoritmo del Simplex:
• En primer lugar planteamos elproblema en forma est´ ndar:
a
Z = 40x1 + 50x2 + 0x3 + 0x4 + 0x5
R0
R1
R2
R3

:
:
:
:

x1 , x2 ≥ 0
5x1 + 3x2 + x3 = Hp
3x1 + 4x2 + x4 = Hr
2x1 + 15x2 + x5 = P

• Ahora creamos la primera tabla del Simplex:
CB
0
0
0
-

XB
x3
x4
x5
Z
Z-Ci

40
y1
5
3
2
0
-40

50
y2
3
4
15
0
-50

0
y3
1
0
0
0
0

0
y4
0
1
0
0
0

0
y5
0
0
1
0
0...