TRABAJO Nº 01-INVOPE

UNIVERSIDAD NACIONAL DE TRUJILLO

Facultad de IngenieríaFacultad de IngenieríaEscuela Profesional de IngenieríaEscuela Profesional de Ingeniería

de Sistemasde Sistemas

ASIGNATURAASIGNATURA :: Investigación de Operaciones. IIInvestigación de Operaciones. II

PROFESORPROFESOR :: Ing. Marco Baca.Ing. Marco Baca.

TRABAJOTRABAJO :: “Programación entera, binaria y “Programación entera, binaria y

continua” continua”

ALUMNOSALUMNOS ::

Carasas Moreno, Vanessa.Carasas Moreno, Vanessa.

Jacobo Garcia Segundo LuisinJacobo Garcia Segundo Luisin

Luís Ruiz, Fredy.Luís Ruiz, Fredy.

Luján Aguilar, Yuliana.Luján Aguilar, Yuliana.

CICLOCICLO : : VIIVII

Trujillo- PerúTrujillo- Perú20102010

PROGRAMACIÓN CONTINUA, ENTERA Y BINARIA

Problema Nº1

Euing Gas elabora dos tipos de gasolina (gasolina 1 y gasolina 2) a partir de dos tipos de petróleo

(petróleo 1 y petróleo 2). Cada galón de gasolina 1 debe contener por los menos 50% de petróleo

1, y cada galón de gasolina 2 debe contener por lo menos 60% de petróleo 1. Cada galón de

gasolina 1 se puede vender en 12 centavos, y casa galón de gasolina 2 se puede vender en 14

centavos. Dispone ahora de 500 galones de petróleo 1 y 1000 galones de petróleo 2. Se pueden

comprar a lo máximo de 1500 galones de petróleo 1 a los precios siguientes: primeros 500

galones, 25 centavos por galón; siguientes 500 galones, 20 centavos por galón; siguientes 500

galones, 15 centavos por galón. Plantee un PE con que el maximice las utilidades de Euing

(ingresos – costos de compra).

Incógnitas

N: Cantidad de petróleo 1 comprado

Xij: Cantidad usada de petróleo i para producir gasolina j (i, j = 1, 2)

Límites

Restricción 1: Euing puede comprar cuando mucho N + 500 galones de petróleo 1

X11 + X12 <= N + 500

Restricción 2: Euing puede utilizar cuando mucho 1000 galones de petróleo 2

X21 + X22 <= 1000

Restricción 3: El petróleo mezclado para producir la gasolina 1 debe contener por lo menos

50% del petróleo 1

X11/(X11 + X21) >= 0.5 ó 0.5*X11 – 0.5*X21 >= 0

Restricción 4: El petróleo mezclado para producir la gasolina 2 debe contener por lo menos

60% del petróleo 1

X12/(X12 + X22) >= 0.6 ó 0.4*X12 – 0.6*X22 >= 0

Objetivo

Ingreso Total = 12*(X11 + X21) + 14*(X12 + X22)

Costo de compra de petróleo = C(N)

25*N (0 <= N <= 500)

C(N) = 20*N + 2500 (500 < N <= 1000)

15*N + 7500 (1000 < N <= 1500)

Por lo tanto, la función objetivo de Euing es maximizar:

Max = 12*X11 + 12*X21 + 14*X12 + 14*X22 – C(N)

Puesto que C(N) es una función lineal por segmentos, la función objetivo no es una función

lineal de N por lo que esta optimización no es un PL. No obstante, al aplicar el siguiente

método es posible transformar este problema en un PE. Luego de recordar que los puntos

de quiebre para C(N) son 0, 500, 1000 y 1500 se produce como se indica:

Paso 1:

Reemplazamos C(N) por lo siguiente:

C(N) = Z1*C (0) + Z2*C (500) + Z3*C (1000) +Z4*C (1500)

Quedando la nueva función objetivo:

Max = 12*X11 + 12*X21 + 14*X12 + 14*X22 – Z2*(12500) – Z3*(22500) – Z4*(30000)

Paso 2:

Sumamos las siguientes restricciones:

N = 0*Z1 + 500*Z2 + 1000*Z3 + 1500*Z4

Z1 <= Y1;

Z2 <= Y1 + Y2;

Z3 <= Y2 + Y3;

Z4 <= Y3;

Z1 + Z2 + Z3 + Z4 = 1;

Y1 + Y2 + Y3 = 1;

Y1, Y2 y Y3, Binarios y Zi >= 0 (i=1,2,3,4)

Solución Lingo

Modelo:

Max = 12*X11 + 12*X21 + 14*X12 + 14*X22 – Z2*(12500) – Z3*(22500) – Z4*(30000);

X11 + X12 <= N + 500;

X21 + X22 <= 1000;

0.5*X11 – 0.5*X21 >= 0;

0.4*X12 – 0.6*X22 >= 0;

N = 0*Z1 + 500*Z2 + 1000*Z3 + 1500*Z4;

Z1 <= Y1;

Z2 <= Y1 + Y2;

Z3 <= Y2 + Y3;

Z4 <= Y3;

Z1 + Z2 + Z3 + Z4 = 1;

Y1 + Y2 + Y3 = 1;

@BIN -> Permite que el LINGO tome la variable como binaria.

Problema Nº 2

Gandhi Cloth Company fabrica tres tipos de prendas de vestir: camisetas, shorts y pantalones. La

elaboración de cada tipo de prenda requiere que Gandhi tenga disponible el tipo de maquinaria

apropiada. La maquinaria necesaria para manufacturar cada tipo de prenda se tiene que rentar a

las tarifas siguientes: maquinaria para camisetas, $ 200 por semana; maquinaria para shorts, $ 150

por semana; maquinaria para pantalones, $ 100 por semana. La hechura de cada tipo de prenda

también requiere las cantidades de tela y mano de obra que se indican en la tabla 2. Están

disponibles cada semana 150 horas de mano de obra y 160 yardas cuadradas de tela. El costo

unitario variable y el precio unitario para cada tipo de prenda, se proporcionan en la tabla 3.

Formule un PL cuya solución maximice la utilidad semanal de Gandhi.

Tabla 2. Recursos Necesarios para Gandhi

Tipo dePrenda

Mano de Obra(Hr)

Tela(yardas cuadradas)

Camisetas 3 4Shorts 2 3

Pantalones 6 4

Tabla 3. Ingresos e información del Costo para Gandhi

Tipo dePrenda

Precio de Venta($)

Costo Variable($)

Camisetas 12 6Shorts 8 4

Pantalones 15 8

Incógnitas

Xi: Número de prendas de cada tipo (Variable Entera)

Donde:

X1: Número de camisetas

X2: Número de shorts

X3: Número de pantalones

Yi: Variable binaria que indica si habido fabricación de alguna prenda

Y1 = 1 Si se fabrican camisetas

0 Si no sucede así

Y2 = 1 Si se fabrican short

0 Si no sucede así

Y3 = 1 Si se fabrican pantalones

0 Si no sucede así

Límites

Restricción de mano de obra

3*X1 + 2*X2 + 6*X3 <= 150

Restricción de la Tela

4*X1 + 3*X2 + 4*X3 <=160

Restricción de Y1, Y2 y Y3 (impedir Yi = 0)

X1 <= M1*Y1

X2 <= M2*Y2

X3 <= M3*Y3

Donde M1, M2, y M3 son tres números positivos grandes, para este caso:

M1 = 40, M2 = 53, M3 = 25 son loas valores máximos.

Objetivo

Costo de Renta de maquinaria = 200*Y1 + 150*Y2 + 100*Y3

Ingresos = 12*X1 + 8*X2 + 15*X3

Utilidades de la semana = (12*X1 + 8*X2 + 15*X3) – (6*X1 + 4*X2 + 8*X3) – (200*Y1 +

150*Y2 + 100*Y3)

Max = 6*X1 + 4*X2 +7*X3 – 200*Y1 – 150*Y2 – 100*Y3

Solución Lingo

Problema Nº3

Hay seis ciudades (ciudades de 1 a 6) en el condado de Kilroy. El condado debe decidir donde

construir la estación de bomberos. Asimismo, el condado quiere construir la cantidad mínima de

estaciones de bomberos necesarias para tener la certeza de que por lo menos una está dentro de

15 minutos (tiempo de manejo) de cada ciudad. Los tiempos (en minutos) necesarios para ir en

automóvil de una ciudad a otra del condado se indican en la tabla siguiente. Plantee una PE

mediante el cual Kilroy sepa cuántas estaciones de bomberos debe construir y donde ubicarlas.

Tabla 1. Tiempo necesario para viajar de ciudad a ciudad en el condado Kilroy

DesdeA

Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad 6Ciudad 1 0 10 20 30 30 20Ciudad 2 10 0 25 35 20 10Ciudad 3 20 25 0 15 30 20Ciudad 4 30 35 15 0 15 25Ciudad 5 30 20 30 15 0 14Ciudad 6 20 10 20 25 14 0

Incógnitas

Kilroy debe determinar, para cada ciudad, si construye una estación de bomberos allí.

Definimos las variables binarias: X1, X2, X3, X4, X5 y X6, mediante:

Xi = 1 si se construye una estación de bomberos en la ciudad i

0 si no sucede así

Límites

El condado debe tener la certeza de que hay una estación de bomberos a 15 minutos de

cada ciudad. En la Tabla 2 se indica a cuales ciudades se puede llegar en 15 minutos o en

menos. Para asegurar que por lo menos una estación de bomberos está a 15 minutos de la

ciudad 1, se suma la restricción:

X1 + X2 >= 1 (Restricción de la ciudad 1)

Esta restricción ayuda a que sea imposible X1 = 0 y X2 = 0. Lo mismo para todas las

ciudades completando las siguientes cinco restricciones:

X1 + X2 + X6 >= 1 (Restricción de la ciudad 2)

X3 + X4 >= 1 (Restricción de la ciudad 3)




Tabla 2. Ciudades a 15 minutos de una ciudad particular

Ciudad A 15 minutos1 1,22 1,2,63 3,44 3,4,55 4,5,66 2,5,6

Objetivo

La cantidad total de estaciones de bomberos que se construyen, está dada por (X1 + X2 +

X3 + X4 + X5 + X6), y la función objetivo de Kilroy se tiene que minimizar:

Min = X1 + X2 + X3 + X4 + X5 + X6

Solución Lingo

TRABAJO Nº 01-INVOPE

Documents

Transcript of TRABAJO Nº 01-INVOPE