INVOP2 Programación Entera

EJERCICIOS DE PROGRAMACION ENTERA Y BINARIA

1. Una joven pareja Carlos y Sara quieren dividir las principales tareas del hogar (ir de compras, cocinar, lavar platos y lavar ropa) entre los dos, de manera que cada uno tenga dos obligaciones y que el tiempo total para hacer estas tareas sea el mínimo. La eficiencia en cada una de las tareas difiere entre ellos; la siguiente tabla proporciona el tiempo que cada uno necesita para cada tarea:

	Horas necesarias por semana
	Compras (A)	Cocinar (B)	Lavar platos (C)	Lavar ropa (D)
Carlos (1)	4.5	7.8	3.6	2.9
Sara (2)	4.9	7.2	4.3	3.1

Formule un modelo de programación entera binaria y resolver por software.

Variables

Xij: Se realiza o no la actividad “i” por la persona “j” (i = A,B,C,D) (j = 1,2)

FO

Min Z = 4.5*XA1 + 4.9*XA2 + 7.8*XB1 + 7.2*XB2 + 3.6*XC1 + 4.3*XC2 + 2.9*XD1 + 3.1*XD2;

XA1 + XB1 + XC1 + XD1 = 2;

XA2 + XB2 + XC2 + XD2 = 2;

XA1 + XA2 = 1;

XB1 + XB2 = 1;

XC1 + XC2 = 1;

XD1 + XD2 = 1;

Xij>=0, enteros, binarios

@BIN(XA1);@BIN(XA2);@BIN(XB1);@BIN(XB2);@BIN(XC1);@BIN(XC2);@BIN(XD1);@BIN(XD2);

2. Graña tiene seis proyectos a realizar en el próximo semestre, así que ya debe estar preparando al personal para el inicio de las obras, los datos económicos de cada proyecto es:

Proyectos	Camino	Supermercado	Casas	Departamentos	Parques	Puentes
Beneficio (miles de $)	50	60	70	80	90	50

Según las condiciones de la empresa se tiene que cumplir las siguientes condiciones:

· El Camino se hace para que se pueda hacer el Supermercado. Si el supermercado no se hace el camino podría hacerse para beneficiar a las casas aledañas.

· De los proyectos Camino y Departamentos se debe elegir uno a lo más.

· El proyecto Casas podría hacerse si es que se hace el proyecto Departamentos y/o el proyecto Parques.

· De los seis proyectos se debe elegir cuatro proyectos.

· El proyecto Departamentos se puede hacer si es que se hace el proyecto Casa y no el proyecto Puentes.

Elabore un modelo PLB para ayudar a Graña a elegir sus proyectos.

Variables

i: Se realiza o no “i” proyecto (i=CA,SU,CS,DE,PA,PU)

FO

Max Z = 50*CA + 60*SU + 70*CS + 80*DE + 90*PA + 50*PU;

SU – CA <= 0;

CA + DE <= 1;

CS – DE– PA <= 0;

CA + SU + CS + DE + PA + PU = 4;

3*DE – 2*CS + PU <= 1;

@BIN(CA);@BIN(SU);@BIN(CS);@BIN(DE);@BIN(PA);@BIN(PU);

3. Un centro comercial tiene 10000 m2 de espacio para alquilar y se quiere determinar la cantidad de tiendas por tipo de negocio que tendrían que instalarse. En la tabla se dan los números mínimo y máximo de tiendas por cada tipo de negocio (junto con la superficie en m2 que éstas ocupan).

Tipo de Tienda	Superf (m2)	Mín	Máx
Joyería	500	1	3
Zapatería	600	1	3
Electrodomésticos	1500	1	3
Librería	700	0	3
Telefonía	900	1	3

La ganancia anual de cada tipo de negocio dependerá del número de tiendas por tipo instaladas en el centro comercial. Esta dependencia se da en la tabla siguiente:

	Ganancia por número de tiendas (millares de $)
Tipo	1	2	3
Joyería	9	8	7
Zapatería	10	9	5
Electrodomésticos	27	21	20
Librería	16	9	7
Telefonía	17	13	10

Por lo tanto, si hay 2 tiendas de Electrodomésticos en el centro comercial, cada una genera ganancias por $21000 al año. Cada negocio paga 5% de su ganancia como alquiler. 

Formule un problema de programación entera cuya solución indicará cómo maximizar el ingreso por alquileres en el centro comercial.

Variables

ij: Número “j” de tiendas “i” a instalar (i=J,Z,E,L,T)(j=0,1,2,3)

FO

Max=0.05*(9*J1+16*J2+21*J3+10*Z1+18*Z2+15*Z3+27*E1+42*E2+60*E3+16*L1+18*L2+21*L3+17*T1+26*T2+30*T3);

J1+J2+J3=1;

Z1+Z2+Z3=1;

E1+E2+E3=1;

L0+L1+L2+L3=1;

T1+T2+T3=1;

500*J1+1000*J2+1500*J3+600*Z1+1200*Z2+1800*Z3+1500*E1+3000*E2+4500*E3+700*L1+1400*L2+2100*L3+900*T1+1800*T2+2700*T3<=10000;

@BIN(J1);@BIN(J2);@BIN(J3);@BIN(Z1);@BIN(Z2);@BIN(Z3);@BIN(E1);@BIN(E2);@BIN(E3);@BIN(L0);@BIN(L1);@BIN(L2);@BIN(L3);@BIN(T1);@BIN(T2);@BIN(T3);

4. Una empresa ha diseñado 3 nuevos productos y dispone de dos plantas que los pueden producir. Sin embargo, para evitar una diversificación excesiva de la línea de productos de la empresa, la administración ha dispuesto en primer lugar que deben producirse como máximo dos de estos tres nuevos productos posibles. Y, en segundo lugar, que solo una de las plantas debe asignarse para la fabricación de los nuevos productos.

Se considera que el costo unitario de fabricación de cada producto sería el mismo en las dos plantas, pero por diferencia de instalaciones, el número de horas de producción por unidad de cada producto puede diferir entre ellas. Estos datos se dan en la tabla adjunta junto con la información del departamento de mercadotecnia del número de unidades de cada producto que se pueden vender a la semana si se producen. El objetivo es seleccionar los productos, la planta y las tasas de producción de los nuevos productos de manera que se maximice la ganancia total. Considerar que las tasas de producción pueden adoptar valores decimales

	Tiempo de producción utilizado por cada unidad producida (horas)			Horas disponibles por semana
	Producto 1	Producto 2	Producto 3
Planta 1 Planta 2	3 4	5 6	2 2	30 40
Ganancia unitaria	5	7	3	(miles de $) (unid/sem)
Ventas potenciales	7	5	9

  

Modelo:

!Xi = Unidades a elaborar del producto i (i=1,2,3);

!Yi = Se elabora o no el producto i (i=1,2,3)

!Z = Variable binaria auxiliar para escoger solo una entre dos restricciones;

MAX = 5*X1 + 7*X2 + 3*X3;

X1 <=7*Y1;

X2 <= 5*Y2;

X3 <= 9*Y3;

Y1 + Y2 + Y3 <= 2; 

3*X1 + 5*X2 + 2*X3 <= 30 + 10000*Z;

4*X1 + 6*X2 + 2*X3 <= 40 + 10000*(1 - Z);

@BIN(Y1);@BIN(Y2);@BIN(Y3);@BIN(Z);

@GIN(X1);@GIN(X2);@GIN(X3);

5. Una siderúrgica produce unas planchas de metal a partir de aleaciones, cada una de las cuales tienen un porcentaje de agentes contaminantes A, B y C. Los porcentajes máximos aceptables para cada contaminante es de 2.3% de A, 1.7% de B y 3.1 % de C.

El costo y las propiedades de cada aleación aparecen en la siguiente tabla: 

	Aleación 1	Aleación 2	Aleación 3
Costo por tonelada($)	190	200	185
% de A	2.2%	2.5%	2.4%
% de B	1.8%	1.5%	1.9%
% de C	3.2%	4.1%	2.9%

Si fuese aceptable con que se cumplan con dos de las restricciones de los agentes contaminantes. Determinar cómo minimizar los costos para una tonelada de producción.

Modelo:

!Xi = Fracción de tonelada a utilizar de la aleación i (i=1,2,3);

!Yj = Variable auxiliar para aceptar o no la restricción j (j=1,2,3)

MIN  =  190*X1 + 200*X2 + 185*X3;

0.022*X1 + 0.025*X2  + 0.024*X3 <= 0.023 + 1000*Y1;

0.018*X1 + 0.015*X2  + 0.019*X3 <= 0.017 + 1000*Y2;

0.032*X1 + 0.041*X2  + 0.029*X3 <= 0.031 + 1000*Y3;

X1+X2+X3 = 1;

Y1+Y2+Y3 <= 1;

@BIN(Y1);@BIN(Y2);@BIN(Y3);

6. Alpha Airline no desea programar más de un vuelo desde Chicago a cada una de las siguientes ciudades: Columbus, Denver, Los Ángeles y Nueva York. Las horas de partida disponibles son 8, 10, y 12 de la mañana. Alpha paga alquiler por los aviones, al costo de $5,000 hasta las 10 a.m. inclusive, y de $3,000 después de las 10 a.m., y está en condiciones de alquilar dos aviones como máximo en cada hora de partida. Además, si un vuelo parte de Nueva York a una hora determinada, será necesario que parta también un vuelo hacia Los Ángeles a la misma hora. La aportación esperada en las ganancias por cada vuelo, antes de considerar los costos del alquiler, se presenta en la siguiente tabla. Formule y resuelva un modelo para un programa que permita maximizar las ganancias.

INGRESO POR CADA VUELO (miles de $ )
Horario	8am	10am	12m
Ciudad
Columbus	10	6	6
Denver	9	10	9
Los Ángeles	14	11	10
Nueva York	18	15	10

!VARIABLES:

Xij: Se programa o no el vuelo con destino a i en el turno j

(i=C,D,A,N) (j=1,2,3)

FUNCION OBJETIVO;

MAX = (10-5)*XC1+(9-5)*XD1+(14-5)*XA1+(18-5)*XN1+

       (6-5)*XC2+(10-5)*XD2+(11-5)*XA2+(15-5)*XN2+

       (6-3)*XC3+(9-3)*XD3+(10-3)*XA3+(10-3)*XN3;

!No más de un vuelo a cada destino;

XC1+XC2+XC3<=1;

XD1+XD2+XD3<=1;

XA1+XA2+XA3<=1;

XN1+XN2+XN3<=1;

!2 aviones como máximo a cada hora de partida;

XC1+XD1+XA1+XN1<=2;

XC2+XD2+XA2+XN2<=2;

XC3+XD3+XA3+XN3<=2;

!Si hay vuelo a NY también a LA en el mismo horario;

XN1<=XA1;

XN2<=XA2;

XN3<=XA3;

@BIN(XC1);@BIN(XC2);

@BIN(XD1);@BIN(XD2);

@BIN(XA1);@BIN(XA2);

@BIN(XN1);@BIN(XN2);

7. Un modelo que una compañía de servicio eléctrico requiere para sus operaciones diarias consiste en una guía para decidir qué generadores debe poner en marcha en cada ocasión. El servicio en cuestión cuenta con tres generadores con las característi­cas que aparecen en la tabla siguiente. El día está dividido en dos periodos y en el primero de ellos se necesitan 2900 megavatios. En el segundo periodo se requieren 3900 megavatios. Un generador puesto en marcha en el primer periodo puede usarse en el segundo sin incurrir en un costo adicional de puesta en marcha. Todos los generadores principales (por ejemplo, A, B y C) se apagan al final de cada día. Formule y resuelva este modelo como una PLEM.

GENERADOR	COSTO FIJO DE ARRANQUE ($)	COSTO POR PERIODO POR MEGAVATIO USADO ($)	CAPACIDAD MÁXIMA EN CADA PERIODO (MW)
A	3000	5	2100
B	2000	4	1800
C	1000	7	3000

!VARIABLES

Xij: MW utilizados por el generador i en el período j

Yi: Se utiliza o no el generador i

FUNCION OBJETIVO;

MIN = 5*(XA1+XA2)+4*(XB1+XB2)+7*(XC1+XC2)+3000*YA+2000*YB+1000*YC;

!RESTRICCIONES;

XA1+XB1+XC1>=2900;

XA2+XB2+XC2>=3900;

XA1<=2100*YA;

XB1<=1800*YB;

XC1<=3000*YC;

XA2<=2100*YA;

XB2<=1800*YB;

XC2<=3000*YC;

@BIN(YA);@BIN(YB);@BIN(YC);

8. Una pipa que entrega petróleo tiene 5 compartimientos que transportan hasta 2700, 2800, 1100, 1800 y 3400 galones de combustible (súper, regular y sin plomo) a un cliente. La demanda, penalización por galones no entregados y el faltante máximo admisible se proporcionan en la tabla siguiente:

Tipo de gasolina	Demanda (galones)	Costo por galones no entregados	Faltante máximo admisible
(A) Súper	2900	10	500
(B) Regular	4000	8	500
(C) Sin plomo	4900	6	500

Cada compartimiento puede llevar sólo un tipo de gasolina. Formule un PE cuya solución le indique cómo cargar la pipa de una manera en que se minimicen los costos por los faltantes.

!VARIABLES

Xij: Galones de combustible tipo i en el compartimiento j

Yij: Va o no combustible tipo i en el compartimiento j

Nei: Galones no entregados de combustible tipo i

(i= A-Súper, B-Regular, C-Sin plomo) (j= 1, 2, 3, 4, 5)

FUNCION OBJETIVO;

Min  = 10*NeA + 8*NeB + 6*NeC;

!RESTRICCIONES;

XA1 + XA2 + XA3 + XA4 + XA5 + NeA = 2900;

XB1 + XB2 + XB3 + XB4 + XB5 + NeB = 4000;

XC1 + XC2 + XC3 + XC4 + XC5 + NeC = 4900;

NeA <= 500;

NeB <= 500;

NeC <= 500;

XA1 <= 2700*YA1;

XA2 <= 2800*YA2;

XA3 <= 1100*YA3;

XA4 <= 1800*YA4;

XA5 <= 3400*YA5;

XB1 <= 2700*YB1;

XB2 <= 2800*YB2;

XB3 <= 1100*YB3;

XB4 <= 1800*YB4;

XB5 <= 3400*YB5;

XC1 <= 2700*YC1;

XC2 <= 2800*YC2;

XC3 <= 1100*YC3;

XC4 <= 1800*YC4;

XC5 <= 3400*YC5;

YA1 + YB1 + YC1 = 1;

YA2 + YB2 + YC2 = 1;

YA3 + YB3 + YC3 = 1;

YA4 + YB4 + YC4 = 1;

YA5 + YB5 + YC5 = 1;

@BIN(YA1); @BIN(YB1); @BIN(YC1);

@BIN(YA2); @BIN(YB2); @BIN(YC2);

@BIN(YA3); @BIN(YB3); @BIN(YC3);

@BIN(YA4); @BIN(YB4); @BIN(YC4);

@BIN(YA5); @BIN(YB5); @BIN(YC5);

PROBLEMA (Planificación de la producción)

Cierta línea de producción fabrica dos productos. Los datos perti­nentes aparecen en la primera tabla adjunta. El tiempo total disponible (para la producción y la puesta en marcha) cada semana es de 80 horas. La firma no tiene inventario de producto alguno al principio de la semana 1, y no se permite que lo tenga al final de la semana 4. El costo de conser­var una unidad de inventario de una semana a la siguiente es de $4 para cada producto. Una uni­dad de demanda no satisfecha cuesta $10 por el producto A y $15 por el producto B. Los datos so­bre la demanda aparecen en la segunda tabla adjunta. La línea se cierra para realizar operaciones de limpieza cada fin de semana. Por tanto, si un producto es fabricado en la semana presente, tendrá que pagarse el costo correspondiente al tiempo de arranque del equipo en la siguiente semana, si es que se decide fabricar éste. Sólo un tipo de producto puede fabricar­se durante la semana. No puede haber producción durante el tiempo en el cual se pone en marcha la línea. Formule y resuelva este modelo de planeación de 4 semanas. El objetivo es maximizar las ganancias en el periodo de 4 semanas.

DATOS SOBRE LOS PRODUCTOS
	PRODUCTO
	A	B
Tiempo de arranque	5 horas	10 horas
Tiempo de producción por unidad	0.5 horas	0.75 horas
Costo de arranque	$200	$400
Costo de producción por unidad	$10	$15
Precio de venta	$20	$30

DATOS SOBRE LA DEMANDA
PRODUCTO	SEMANA
	1	2	3	4
A	80	100	75	80
B	15	20	50	30

Solución:

!VARIABLES:

Xijk: Unidades elaboradas del producto i en la semana j para cubrir la demanda de la semana k

Yij: Se fabrica o no el producto i en la semana j

FUNCION OBJETIVO;

MAX = 20*(XA11+XA12+XA13+XA14+XA22+XA23+XA24+XA33+XA34+XA44)+

       30*(XB11+XB12+XB13+XB14+XB22+XB23+XB24+XB33+XB34+XB44)-

       (200*(YA1+YA2+YA3+YA4)+400*(YB1+YB2+YB3+YB4))-

       (10*(XA11+XA22+XA33+XA44)+14*(XA12+XA23+XA34)+18*(XA13+XA24)+22*(XA14))-

       (15*(XB11+XB22+XB33+XB44)+19*(XB12+XB23+XB34)+23*(XB13+XB24)+27*(XB14))-

       (10*((80-XA11)+(100-XA12-XA22)+(75-XA13-XA23-XA33)+(80-XA14-XA24-XA34-XA44)))-

       (15*((15-XB11)+(20-XB12-XB22)+(50-XB13-XB23-XB33)+(30-XB14-XB24-XB34-XB44)));

!RESTRICCIONES DE DEMANDA;

XA11<=80;

XB11<=15;

XA12+XA22<=100;

XB12+XB22<=20;

XA13+XA23+XA33<=75;

XB13+XB23+XB33<=50;

XA14+XA24+XA34+XA44<=80;

XB14+XB24+XB34+XB44<=300;

!UN SOLO TIPO DE PRODUCTO DURANTE LA SEMANA;

YA1+YB1=1;

YA2+YB2=1;

YA3+YB3=1;

YA4+YB4=1;

!RESTRICCIONES DE TIEMPO DISPONIBLE;

5*YA1+10*YB1+0.5*(XA11+XA12+XA13+XA14)+0.75*(XB11+XB12+XB13+XB14)<=80;

5*YA2+10*YB2+0.5*(XA22+XA23+XA24)+0.75*(XB22+XB23+XB24)<=80;

5*YA3+10*YB3+0.5*(XA33+XA34)+0.75*(XB33+XB34)<=80;

5*YA4+10*YB4+0.5*(XA44)+0.75*(XB44)<=80;

!PERMITIR CANTIDADES SOLO CUANDO SE PROGRAMA PRODUCCION;

XA11+XA12+XA13+XA14<=(80+100+75+80)*YA1;

XA22+XA23+XA24<=(100+75+80)*YA2;

XA33+XA34<=(75+80)*YA3;

XA44<=(80)*YA4;

XB11+XB12+XB13+XB14<=(15+20+50+30)*YB1;

XB22+XB23+XB24<=(20+50+30)*YB2;

XB33+XB34<=(50+30)*YB3;

XB44<=(30)*YB4;

@GIN(XA11);@GIN(XA12);@GIN(XA13);@GIN(XA14);

@GIN(XA22);@GIN(XA23);@GIN(XA24);

@GIN(XA33);@GIN(XA34);

@GIN(XA44);

@GIN(XB11);@GIN(XB12);@GIN(XB13);@GIN(XB14);

@GIN(XB22);@GIN(XB23);@GIN(XB24);

@GIN(XB33);@GIN(XB34);

@GIN(XB44);

@BIN(YA1);@BIN(YA2);@BIN(YA3);@BIN(YA4);

@BIN(YB1);@BIN(YB2);@BIN(YB3);@BIN(YB4);