Universidad Militar Nueva Granada

Facultad de estudios a distancia

Programas de Ingenierı́a
Investigación de operaciones

Taller
Segundo Corte
Información importante: Estimado estudiante, es importante que lea cuidadosamente las siguientes ins-
trucciones para la entrega de cada ejercicio:
La entrega se debe hacer en un único documento en PDF, con el enunciado del problema para
cada ejercicio, con un proceso claro y debidamente justificado. En caso de realizarlo a mano alzada,
asegurarse de: escanear muy bien el documento, evite tomarle foto y organice de forma secuencial
cada uno de los puntos.

La forma de evaluar este trabajo será mediante la siguiente rúbrica de evaluación, en cada ejercicio
se especifica el número de puntos que se otorgarán. En los problemas del numeral 3 se debe tener
en cuenta que se calificará como un proceso. Es decir, si el problema primal esta mal planteado,
el problema dual y el método simplex tendrán puntuación de 0. De igual manera, si el primal esta
bien pero el dual está mal planteado. El número de puntos para el método simplex será 0.

El porcentaje relacionado será evaluado respecto al avance alcanzado en su proceso versus el mı́nimo
de pasos entregados. Es decir, sı́ el ejercicio se podı́a realizar en 3 iteraciones y usted entrega 10
iteraciones pero se obtiene el mismo resultado que en una iteración, su porcentaje será del 33,33 %.
En los ejercicios 1.a),3) y 1.b),3), usar otro método diferente a las ecuaciones de sensibilidad le
otorgarán una puntuación de 0 unidades.

La nota final se obtendrá sobre el total de puntos que corresponden a 50.

RÚBRICA DE EVALUACIÓN

ASPECTO PUNTOS
#
A EVALUAR OBTENIDOS
1 Presentación 2 PUNTOS 1.5 PUNTOS 1 PUNTO 0.5 PUNTOS
La presentación del La escritura del La escritura del La escritura del
trabajo cumple con proceso algebraico proceso algebraico proceso algebraico
todas las indicacio- de cada uno de los es poco com- es incomprensible,
nes dadas. ejercicios es claro prensible, es fácil no es posible seguir
pero las gráficas perderse en el el proceso que
elaboradas son po- hilo del ejercicio. pudiese obtener
co comprensibles. Sin embargo, las la respuesta fi-
gráficas elaboradas nal. Además, las
son de muy buena gráficas elaboradas
calidad. carecen de estética
y tampoco son
entendibles.
2 Planteamiento 3 PUNTOS 2 PUNTOS 1 PUNTO 0 PUNTOS
de ecuaciones El planteamien- Se planteó una Se plantearon dos Se plantearon tres o
to de todas las ecuación de sensi- ecuaciones de sen- más ecuaciones de
ecuaciones de bilidad de manera sibilidad de manera sensibilidad de for-
sensibilidad son incorrecta. incorrecta. ma incorrecta.
correctas.

1
3 Planteamiento 3 PUNTOS 2 PUNTOS 1 PUNTO 0 PUNTOS
de intervalos El planteamien- Se planteó un inter- Se plantearon dos Se plantearon tres
to de todos las valo de sensibilidad intervalos de sensi- o más intervalos de
intervalos de de manera incorrec- bilidad de manera sensibilidad de for-
sensibilidad son ta. incorrecta. ma incorrecta.
correctos.
4 Análisis de 3 PUNTOS 2 PUNTOS 1 PUNTO 0 PUNTOS
sensibilidad El análisis de sensi- El análisis de sen- El análisis de sen- El análisis de sen-
bilidad en todas las sibilidad es correc- sibilidad es correc- sibilidad es correc-
variables es correc- to entre el 75 % y to entre el 50 % y to entre el 25 % y
to. el 80 % de las varia- el 60 % de las varia- el 40 % de las varia-
bles. bles. bles.
5 Función objetivo 2 PUNTOS 0 PUNTOS
del dual La función objetivo del problema dual La función objetivo del problema dual
esta bien planteada no esta bien planteada
6 Restricciones de 1.5 PUNTOS 1 PUNTOS 0.5 PUNTOS 0 PUNTOS
del dual Las tres restriccio- Solamente dos res- Solamente una de Ninguna restricción
nes del dual que- tricciones del dual las restricciones del del dual quedó bien
daron bien plantea- quedaron bien plan- dual quedó bien planteada.
das. teadas. planteada.
7 Condiciones 1.5 PUNTOS 1 PUNTOS 0.5 PUNTOS 0 PUNTOS
variables del dual Las tres condiciones Solamente dos con- Solamente una de Ninguna condición
del dual quedaron diciones del dual las rcondiciones del del dual quedó bien
bien planteadas. quedaron bien plan- dual quedó bien planteada.
teadas. planteada.
8 Planteamiento 3 PUNTOS 2 PUNTOS 1 PUNTO 0 PUNTOS
primal El modelamien- La función objetivo El problema tiene El problema tiene
to del problema esta mal propuesta, dos errores de plan- tres o más erro-
primal es comple- pero las restriccio- teamiento. Restric- res de planteamien-
tamente correcto. nes son correctas. ciones y función ob- to. Restricciones y
jetivo. función objetivo.
9 Planteamiento 3 PUNTOS 2 PUNTOS 1 PUNTO 0 PUNTOS
del dual El modelamiento La función objetivo El problema tiene En el planteamien-
del problema dual esta mal propuesta, dos errores de plan- to del primal hay
es completamente pero las restriccio- teamiento. Restric- un error o más.
correcto. nes son correctas. ciones y función ob- Esto implica que
jetivo. el modelamien-
to del dual será
incorrecto.
10 Simplex 4 PUNTOS 3.5 PUNTOS 2 PUNTOS 1 PUNTOS
y respuesta El 100 % de las ta- El 100 % de las ta- Entre el 74 % y Entre el 49 % y
blas o sistemas de blas o sistemas de 50 % de las ta- 25 % de las ta-
ecuaciones propues- ecuaciones propues- blas o sistemas de blas o sistemas de
tos son correctos, y tos son correctos, y ecuaciones propues- ecuaciones propues-
la respuesta final es la respuesta final es tos son correctos. tos son correctos..
correcta. incorrecta.

EJERCICIOS

1. Resolver los ejercicios ejercicios 1a y 1b usando la siguiente información.

Modelo de renovación urbana

Un pequeño municipio ubicado en la zona metropolitana de una gran ciudad en los Estados Unidos
enfrenta un problema de recorte de su presupuesto por parte del distrito federal. Por tal razón,
busca aumentar su base tributaria y propone la demolición de un área de viviendas en un sector
cercano a la gran ciudad a la cual pertenece, buscando edificar nuevas viviendas. Este proyecto se
debe realizar en dos fases: en la primera, se realizará la adquisición de las viviendas y su posterior
demolición; en la segunda, se realizará la construcción del nuevo proyecto. Las restricciones de este
proyecto son:

2
 El número de casas que máximo se pueden demoler son 600, y cada una ocupa un lote de
250 m2 y el costo de demolición de cada casa es de 20000 USD.
Se van a ofertar 4 tipos de casas. A continuación se indica el área horizontal total, el número
de pisos de la edificación y el área total construida de cada tipo:
• Tipo I: terreno total de 180 m2 , 2 pisos y un área total construida de 220 m2 .
• Tipo II: terreno total de 280 m2 , 3 pisos y un área total construida de 600 m2 .
• Tipo III: terreno total de 400 m2 , 3 pisos y un área total construida de 800 m2 .
• Tipo IV : terreno total de 500 m2 , 3 pisos y un área total construida de 1200 m2 .
Se debe destinar un 15 % del espacio disponible para la construcción de zonas comunes, vı́as e
instalación de servicios.
El total de casas de tipo III y tipo IV , deben ocupar por lo menos el 25 % del total de
construcciones nuevas. Las casas tipo I, deben ocupar por lo menos el 20 % y las de tipo II
deben ser por lo menos el 10 %.
El impuesto anual que se recaudará para las viviendas de tipo I, II, III y IV serán 15,100,
24,100, 32,100 y 39,100 USD, respectivamente.
El costo de construcción por unidad de cada unidad familiar será 500,000, 700,000, 1,300,000
y 1,600,000, respectivamente. Y, lo máximo que se logró conseguir como financiación fueron
150,000,000 USD.

Como la alcadı́a busca recaudar la mayor cantidad de impuestos anualmente, el planteamiento del
problema de programación lineal quedarı́a:
Máx Z = 15,100x1 + 24,100x2 + 32,100x3 + 39,100x4

sujeto a las restricciones:

Área disponible: 180x1 + 280x2 + 400x3 + 500x4 − 212,5x5 + s1 = 0

Costos de construcción (millones): 500x1 + 700x2 + 1,300x3 + 1,600x4 − 20x5 + s2 = 150,000
Cantidad de casa a demoler: x5 + s3 = 600
Restricción de casas tipo I: −0,8x1 + 0,2x2 + 0,2x3 + 0,2x4 + s4 = 0
Restricción de casas tipo II: 0,1x1 − 0,9x2 + 0,1x3 + 0,1x4 + s5 = 0
Restricción de casas tipo III y IV: 0,25x1 + 0,25x2 − 0,75x3 − 0,75x4 + s6 = 0

Donde x1 , x2 , x3 y x4 respresentan el número de viviendas de tipo I, II, III y IV que se van a

construir, respectivamente. Y, x5 serı́an el número de viviendas que se van a demoler. Al resolver
el problema de programación lineal, se llega al siguiente tablero del método simplex

TABLA 1

Bás. x1 x2 x3 x4 x5 s1 s2 s3 s4 s5 s6 Cons.
Fila Z 0 0 0 2000 0 0 30 600 3000 0 10000 4860000
Fila x3 0 0 1 1,093 0 0 0 0,006 -0,062 0 -0,815 50
Fila x2 0 1 0 0,204 0 0 0,001 0,014 0,864 0 1,407 110
Fila s1 0 0 0 -7,407 0 1 -0,358 205,34 -28,395 0 -94,815 69500
Fila x5 0 0 0 0 1 0 0 1 0 0 0 600
Fila x1 1 0 0 0,074 0 0 0 0,005 -1,049 0 0,148 40
Fila s5 0 0 0 0,167 0 0 0,001 0,011 0,889 1 1,333 90

a) Análisis de sensibilidad para la variación de los recursos.

1) Escriba las ecuaciones de sensibilidad para cada una de las variables solución respecto a la
variación de los recursos (D2 , D3 , D4 , D6 ) usando la información de la tabla 1. (Aspecto
#2)
2) Determine el valor mı́nimo y el valor máximo de cada una de las variables del numeral
anterior para que la solución siga siendo factible y óptima suponiendo que no hay variación
en los otros recursos. (Aspecto #3)
3) Debido al exito del proyecto, el gobierno logra adquirir 1000 viviendas nuevas para demo-
lición y una nueva inversión de 750,000,000 USD. Con esta nueva inversión monetaria y el
nuevo espacio disponible para la construcción indique el nuevo número de casas de cada
tipo que se puede construir y el área vacı́a que quedo libre (resultado de la variable s1 )
, USANDO LAS ECUACIONES DE SENSIBILIDAD DEL NUMERAL 1.a.1). (Aspecto
#4)

3
 b) Análisis de sensibilidad para la variación de los costos:
1) Escriba las ecuaciones de sensibilidad para cada una de las variables no básicas respecto a
la variación de los impuestos (d1 , d2 , d3 , d4 ) usando la información de la tabla 1. (Aspecto
#2)
2) Determine el valor mı́nimo y el valor máximo en el cual puede cambiar los impuestos de
cada tipo de cada para que la solución siga siendo factible y óptima suponiendo que no
hay variación en los otros impuestos. (Aspecto #3)
3) Antes de publicar los precios de los impuestos, un consejero de la alcaldia le recomienda que
en las casa de tipo I aumente el impuesto en 1000 dolares, en las casas de tipo II aumente
en 1500 dolares, reduzca en 3500 las casas de tipo III y en 1000 las casas de tipo IV .
El mandatario, al revisar en su modelo de programación lineal observa que esta variación
implicarı́a que ahora no se construyan casas de tipo III sino de tipo IV. ¿Cuántas casas
de tipo I, II y IV se construirán ahora? ¿Esto beneficia al recaudo de impuestos o no?.
Para justificar las dos respuestas, USE LAS ECUACIONES DE SENSIBILIDAD DEL
NUMERAL 1.B.1) y realize una iteración del método simplex sobre el nuevo tablero..
(Aspecto #4)

2. Reescribir cada uno de los siguientes problemas en su forma dual general, tenga en cuenta las reglas
de la Tabla de Tucker. (NO SOLUCIONAR EL PROBLEMA NI EL DUAL) (Para cada
ejercicio se evaluan los aspectos #5, #6 y #7)

a) Máximizar Z = 3x1 − 2x2 − 3x3 b) Minimizar Z = 6x1 + x2 − 3x3

sujeto a: sujeto a:

4x1 − 5x2 > 6 4x1 − 5x2 + x3 = 8

−2x1 + x2 − 4x3 = 9 −x1 − 2x2 + 3x3 6 5
x1 + 4x2 + 2x3 6 5 8x1 + 4x2 − 2x3 6 7

Con x1 , x2 > 0 y x3 libre. Con x2 6 0, x3 > 0 y x1 libre.

3. Para cada uno de los siguientes ejercicios: 1. plantear el problema primal, 2. plantear su dual, 3.
solucionar el dual usando el método simplex y 4. presentar la respuesta del primal como los precios
sombra del dual. (Para cada ejercicio se evaluan los aspectos #8, #9 y #10). Tenga en cuenta que
si resuelve el primal y no el dual, el punto no se contará como válido.
a) A una compañı́a se le ha concedido el permiso para realizar vuelos privados entre las ciudades
de Bogotá, Girardot y Tunja. La nueva lı́nea desea implementar su servicio mediante tres tipos
diferentes de aeronaves: aviones de turbohélice (ATH) , aviones ligéros (AL) y helicópteros (H).
Se tiene un presupuesto inicial de 28 mil millones de pesos para adquirir las aeronaves a una
compañı́a que brinda la siguiente información de cada una de sus productos.

Tipo de Precio Mantenimiento Tripulación Capacidad

Aparato (miles de mill.) (miles pesos/dı́a) Piloto Copiloto Azafata (pasaj./mes)
ATH 3 120 2 − 2 4000
AL 1 60 1 1 1 300
H 0,5 30 1 − − 100
Como máximo es posible contratar 18 pilotos y 16 azafatas. Mientras que mı́nimo, se deben
contratar 3 copilotos. De acuerdo a la estimación del mercado, en la ruta Bogotá-Tunja se
esperan 8000 pasajeros por mes (SOLO ATH) y Bogotá-Girardot se estiman 500 pasajeros por
mes (AL o H). De acuerdo a las leyes establecidas, la empresa debe contar con un mı́nimo de
15 aeronaves para su operación. Determinar una solución óptima que minimice el costo del
mantenimiento.
b) Una refinerı́a ubicada en el nororiente de Colombia y que se encarga de la producción de
dos tipos de combustible: diesel y corriente, y surte al 75 % del paı́s, usa dos aditivos A y
B para su elaboración. Buscando cumplir con las normas establecidas por el ministerio de
minas y energı́a, la gasolina corriente puede tener una concentración máxima del aditivo B
correspondiente al 60 %, mientras que para la producción de diesel se busca que como mı́nimo,
el 40 % de la concentración contenga el aditivo A.
Esta refinerı́a adquiere el crudo desde dos fuentes ubicadas en Meta y Arauca, respectivamente.
De la primera fuente, el crudo es extraido y viene con una concentración correspondiente
al 20 % de aditivo A y 70 % de aditivo B. Mientras, desde Arauca el crudo llega con unas
concentraciones de 50 % y 35 %, de cada aditivo A y B, respectivamente. El costo por barril
de crudo desde Meta, se estima en USD25/gl, mientra que desde Arauca ese costo es mayor

4
por USD5/gl. Determine el número de galones que se deben adquirir desde cada una de las
refinerı́as para minimizar el costo, teniendo en cuenta que se debe indicar el número de galones
que se va a usar para cada tipo de combustible, proveniente desde cada una de las ciudades (es
decir, el problema tiene 4 variables) y, teniendo presente que semanalmente se debe atender
una demanda de 77000 galones de diesel y 57000 galones de corriente,