12.3-6Considere el ejemplo de PE de dos variables de la seccin 12.5, ilustrado en la figura 12.

3
a) Use una representacin binaria de variables para reformular este modelo como un
problema de PEB.
Maximizar=x+2y+5z+10w
Sujeto a: x+2y+10z+20w<=20
x+2y<=2
yij binaria

b) Utilice la computadora para resolver este problema de PEB. Despus use la solucin
ptima para identificar una solucin ptima para el modelo original de PE.

12.3-7La compaa area Fly-Right construye jets pequeos que vende a corporaciones para uso
ejecutivo. Para cumplir con sus necesidades, en ocasiones los clientes ordenan aviones con diseo
especial. Cuando es as, se incurre en un costo de preparacin para iniciar la produccin de las
aeronaves.
Fly-Right acaba de recibir pedidos de tres clientes con fechas de entrega cercanas. Debido a que
las instalaciones de produccin estn comprometidas para cumplir contratos anteriores, no
podrn aceptar los tres pedidos. En consecuencia, debe decidirse el nmero de aviones que
producirn (si lo hacen) para cada uno de los tres clientes.
Los datos relevantes se presentan en la siguiente tabla. El primer rengln contiene los costos fijos
para iniciar la produccin de aviones de cada cliente. Con la produccin en marcha, el ingreso neto
marginal (precio de compra menos costo marginal de produccin) de cada avin se presenta en el
segundo rengln. El tercero contiene los porcentajes de capacidad de produccin disponibles para
cada avin. El ltimo rengln indica el nmero mximo de aviones pedidos por cada cliente (pero
aceptaran menos).

Fly-Right desea determinar cuntos aviones debe producir para cada cliente (si lo hace) de modo
que se maximice su ganancia total (ingresos netos menos costos fijos).
a) Formule un modelo con variables enteras y variables binarias para este problema.
Donde xi es el nmero de productos producidos
Yi= 1 si el producto es producido
0 en otro caso
Maximizar Z = 2x1+3x2+0.8x3-3y1-2y2
0.2x1+0.4x2+0.2x3<=1
x1<=My1
x2<=My2
x1<=3
x2<=2
x3<=5
x1, x2, x3>= 0 Enteras
y1, y2 binarias

b) Use la computadora para resolver este modelo.

12.4-1Reconsidere en problema 12.3-7 de Fly-Right. Un anlisis ms detallado de los factores de

costo e ingreso indica que l ganancia potencial de producir los aviones de cada cliente no se puede
expresar solo en trminos del costo fijo y un ingreso neto marginal por avin producido. Ms bien
las ganancias se dan en la siguiente tabla.

a) Formule un modelo de PEB para este problema que incluya restricciones para las
alternativas mutuamente excluyentes.
Maximizar Z=-y11+2y12+4y13+y21+5y22+y31+3y32+5y33+6y34+7y35
y11+y12+y13<=1
y21+y22<=1
y31+y32+y33+y34+y35<=1
y11+2y12+3y13+2y21+4y22+1y31+2y32+3y33+4y34+5y35<=5
yij binarias

b) Use la computadora para resolver el modelo formulado en el inciso a. Despus use esta
solucin ptima para identificar el nmero ptimo de aviones que se deben fabricar para
cada cliente.

c) Repita el inciso b para el modelo formulario en el inciso c.

12.4-2Reconsidere el problema de Wyndor Glass Co. Presentado en la seccin 3.1. La gerencia ha

decidido que solo debe fabricarse uno de los dos nuevos productos y la eleccin debe hacerse
para maximizar la ganancia. Introduzca variables binarias auxiliares para formular un modelo de
PEM para esta nueva versin del problema.

12.4-3Reconsidere el problema 3.1-11, donde la administracin de Omega estudia la

posibilidad de dedicar el exceso de capacidad a uno o ms de tres productos. Ahora agregue la
restriccin de la gerencia de que no deben introducirse ms de dos de los tres nuevos
productos.
a) Introduzca variables binarias auxiliares para formular un modelo de PEM para esta nueva
versin del problema.
Se introducen variables binarias y1, y2, y3 para representar productos de niveles.
Maximizar Z=50x1+20x2+25x3
Sa.
9x1+3x2+5x3<=500
5x1+4x2<=350
3x1+2x3<=150
x3 <=20
x1 <=M*y1
x2 <=M*y2
x3 <=M*y3
y1+y2+y3<=2
x1, x2, x3>=0
y1, y2, 23 binarios

b) Use la computadora para resolver el modelo

Interpretacin:
Del producto 1 (x1) se producirn 45 semanalmente, del producto 2 (x2) se producirn 31
semanalmente, del producto 3 (x3) no se producir nada. El costo por unidad del producto 1
es de 50, del producto 2 es de 20 y del producto 3 es de 25; por lo que nuestro total queda
como 50*45+20*31+0*25=2870.

12.4-4Considere el siguiente problema de programacin entera no lineal.

Maximizar Z= 4X12-x13+10x22-x24,
Sujeta a
X1+X2<=3 y X1>=0, X2>=0.
X1 y X2 son enteros.
Este problema se puede reformular de dos maneras como un problema de PEB equivalente
(con una funcin objetivo lineal) y seis variables binarias (y1j y y2j para j=1,2,3), segn la
interpretacin que se d a las variables binarias.
a) Formule un modelo de PEB para este problema donde las variables binarias tienen la
siguiente interpretacin.
Yij= 1 si xi=j

0 de otra manera.

Maximizar Z= 3y11+8y12+9y13+9y21+24y22+9y23
y11+y12+y13<=1
y11+y23<=1
y12+y23<=1
y12+y22<=1
y21+y22+y23<=1
y13+y21<=1
y13+y22<=1
y13+y21<=1
yij binarios

b) Utilice la computadora para resolver el modelo formulado en el inciso a, y despus

identifique una solucin ptima para (x1, x2) para el problema original.

c) Formule un modelo de PEB para este problema donde las variables binarias tienen la
siguiente interpretacin.
Yij= 1 si xi>=j
0 de otra manera.

Maximizar Z= 3y11+5y12+2y13+9y21+15y22-15y23
y12<=y21
y13<=y12
y22<=y21
y23<=y22
y11+y23<=1
y12+y22<=1

y13+y21<=1
yij binarios

d) Use la computadora para resolver el modelos formulado en el inciso c, y despus

identifique una solucin ptima para( x1, x2) para el problema original.

12.4-5Considere el siguiente problema de programacin no lineal discreta.

Maximizas Z=2x1-x12+3x2-3x22,
Sujeta a
X1+x2<=0.75
Y cada variable est restringida a los valores
a) Reformule este problema como un problema de programacin lineal entera binaria pura.

Maximizar
Z=(3/4)y11+(5/9)y12+(7/16)y13+(9/25)y14+(3/4)y21+(2/3)y22+(9/
16)y23+(12/25)y24
y11+y12+y13+y14<=1
y21+y22+y23+y24<=1
y11+y21<=1
y11+y22<=1
y12+y21<=1

yij binarias

b) Use la computadora para resolver el modelo formulado en el inciso a y despus

identifique una solucin ptima para (x1, x2) para el problema original.

12.4-6Considere el siguiente tipo especial de problema de la ruta ms corta en el que los

nodos estn en una columna y las nicas trayectorias posibles se mueven siempre hacia
adelante, una columna a la vez. Los nmeros colocados junto a las ligaduras son distancias y el
objetivo es encontrar la ruta ms corta del origen al destino.

Este problema tambin se puede formular como un modelo PEB que abarca tanto alternativas
mutuamente excluyentes como decisiones contingentes.
a) Formule este modelo. Identifique las restricciones de las alternativas mutuamente
excluyentes y las decisiones contingentes.
Minimizar Z=3x12+6x13+6x24+5x25+4x34+3x35+3x46+2x56
x12+x13=1
x24+x25+x34+x35=1
x46+x56=1
x24+x25<=x12
x34+x35<=x13
x46<=x24+x34
x56<=x25+x35

xij binarias

b) Use la computadora para resolver este problema.

Interpretacin:
El camino ms corto entre el Origen y Destino est dado por la siguiente ruta
Origen A(x12) D(x25) Destino(x56) con costo de 10
12.4-7Considere la red del proyecto para un sistema PERT del problema 11.2-3. Formule un
modelo de PEB para el problema de encontrar una ruta crtica(es decir, la trayectoria ms
larga) para esta rede de proyecto.
Maximizar
Z=5*x12+3*x13+4*x24+2*x25+3*x35+1*x46+3*x47+6*x57+2*x58+5*x69+4*x79
+7*x89
Sujeto a

xij binarias

12.4-8Speedy Delivery proporciona un servicio que entrega paquetes grandes en dos das, en
todo Estados Unidos. Cada maana se cargan los paquetes que llegaron a cada centro de
recoleccin durante la noche en los camiones de reparto para su entrega en el rea. En razn
de que la competencia en este negocio se basa en la rapidez de la entrega, los paquetes se
dividen segn sus destinos geogrficos de manera que se minimice el tiempo promedio
necesario para realizar las entregas.
Esta maana, la despachadora del centro de recoleccin de Blue River Valley, Sharon Lofton,
tiene mucho trabajo. Sus tres choferes llegarn en menos de una hora para el reparto. Hay
nueve paquetes que entregar en lugares muy alejados entre s. Como siempre, Sharon
introduce estos lugares en la computadora para usar Dispatcher, el software especial del

sistema de apoyo. El programa usa las ubicaciones para generar un buen nmero de rutas
posibles para cada camin.
Estas rutas se muestran en la siguiente tabla (donde los nmeros en cada columna indican el
orden de las entregas), junto con los tiempos que se requieren para el recorrido.

Dispatcher es un sistema interactivo que muestra estas rutas para que Sharon las apruebe o
modifique. (Quiz la computadora no sepa que una inundacin ha hecho que una ruta sea no
factible.) Si Sharon aprueba las rutas como posibilidades atractivas con tiempos estimados
razonables, el programa formula y resuelve un modelo de PEB para elegir las tres rutas que
minimizan el tiempo total e incluye cada lugar de entrega slo en una ruta. Esta maana, Sharon
aprueba todas las rutas.

a) Use la computadora para resolver el problema.

12.4-10Reconcidere el problema 12.4-9, La gerencia de Sunny Skies desde ahora

que la decisin de ubicacin de las estaciones de bomberos se base en los costos.
El costo de asignar una estacin de bomberos en un sector es $200000 para el
sector 1; $250000 para el 2; $400000 para el 3; $300000 para el 4, y $500000 para
el 5. El nuevo objetivo de la gerencia es ahora:
Determinar qu sectores deben tener una estacin para minimizar el costo total
de las estaciones asegurando que cada sector tenga al menos una estacin lo
suficientemente cerca para responder a un incendio en no ms de 15 minutos (en
promedio). Observe que al contrario del problema original, el nmero total de
estaciones de bombero no es fijo. Lo que es ms, si un sector sin estacin tiene
ms de una estacin a 15 minutos o menos, ya no es necesario asignar este sector
a solo una de las estaciones.
a) Formule un modelo de PEB pura con cinco variables binarias, para este
problema.
Minimizar Z = 200x1+250x2+400x3+300x4+500x5
x1+x3+x5>=1
x1+x2+x4>=1
x2+x3+x5>=1
x2+x3+x4+x5>=1
x1+x3+x4+x5>=1
Xij binarias

b) Use la computadora para resolver el modelo en a.

12.4-12Una profesora estadounidense pasara un periodo sabtico corto en la

Universidad de Islandia. Ella quiere llevar en el avin todos los artculos necesarios.
Despus de reunir su material profesional se da cuenta que las reglas de la lnea
area sobre el espacio y el peso de las maletas registradas limitaran la ropa que
puede empacar. (Piensa llevar un abrigo caliente y, al llegar, comprar un suter
grueso islands.) La ropa que quiere llevar incluye 3 faldas, 3 pantalones, 4 blusas
y 3 vestidos. La profesora desea maximizar el nmero de atuendos que podr usar
en Islandia (incluso el de viaje). Cada vestido constituye un atuendo. Otras
consisten en una blusa y una falda o un pantaln. Sin embargo, algunos de ellos no
se ven bien juntos y no califican como atuendos.
En la tabla se marcan los atuendos con una x.

En la siguiente tabla se muestra el peso (en gramos) y el volumen (en centmetros

cbicos) de cada artculo.

Formule un modelo de PEB para elegir las piezas de ropa que debe llevar.
(Sugerencia: despus de usar variables de decisin binarias para representar las
piezas individuales, debe introducir variables binarias auxiliares para representar
los atuendos que representan las combinaciones de artculos. Despus utilice las
restricciones y la funcin objetivo para asegurar que estas variables auxiliares
tienen los valores correctos, dados los valores de las variables de decisin.)

Bonilla Alvarez Luis Fernando

Hernandez Gonzalez Marco Antonio