Problemas de programación binaria entera y mixta 2019 PDF

Preview

Summary

Problemas de programación binaria entera y mixtaCaso 1Boxcar_Burger es una nueva cadena de comida rápida, cuyos locales trabajan los 7 días de la semana y están a cargo de un Gerente de local. La empresa planifica su expansión en áreas suburbanas y en el centro de la ciudad. La gerencia desea determ...

Description

INVESTIGACIÓN DE

Problemas de programación binaria entera y mixta Caso 1 Boxcar_Burger es una nueva cadena de comida rápida, cuyos locales trabajan los 7 días de la semana y están a cargo de un Gerente de local. La empresa planifica su expansión en áreas suburbanas y en el centro de la ciudad. La gerencia desea determinar cuántos restaurantes abrir en cada área a fin de aumentar al máximo la ganancia semanal neta. Se establecen las siguientes condiciones: -

No más de 19 gerentes pueden ser asignados. Por lo menos deben abrirse dos restaurantes en el Centro. La inversión total no puede exceder a $2.7 Millones.

BULTO

SUBURBANO

CENTRO

Inversión por la ubicación

200,000

600,000

Ganancia neta diaria ($)

1,200

2,000

Nro Gerentes necesarios

3

1

Caso 2 Una compañía requiere contratar personal de seguridad. Se estima que los guardias trabajarán turnos de 8 horas y que cada día se necesitan seis turnos para cubrir las 24 horas. Las siguientes tablas muestran el número requerido de personal de seguridad por cada 4 horas del día y los horarios de entrada y salida de cada turno: -

Se necesita determinar cuántos guardias deberán trabajar en cada turno con el objeto de minimizar el número de ellos.

PERIODO

PERSONAL REQUERIDO

0 - 4am

4

4am - 8am

7

8am - 12m

15

12m - 4pm

7

4pm - 8pm

12

8pm - 0

19

TURNO

HORARIO

1

Medianoche – 8am

2

4am – Mediodía

INVESTIGACIÓN DE 3

8am – 4pm

4

Mediodía – 8pm

5

4pm – Medianoche

6

8pm – 4am

Si los guardias reciben un sueldo de $100 por hora y un premio de 10% por las horas laboradas entre las 10 pm y 6 am, ¿cómo se modifica el modelo de PLE?

INVESTIGACIÓN DE Caso 3 La compañía Bagwell Chemical elabora dos productos químicos industriales. El primero, XYLINE, se debe producir en sacos de 50 libras; en tanto que el segundo, HEXALL, se vende por libras a granel en seco y, por consiguiente, se puede elaborar en cualquier cantidad. Tanto el XYLINE como el HEXALL se componen de tres ingredientes (A, B y C) según detalla la Tabla. Bagwell vende sacos de 50 libras de XYLINE en $85 y cualquier cantidad de HEXALL a $1.50 cada libra. -

Formule un modelo de PL para Bagwell considerando que no es aceptable producir “fracciones” de saco de XYLINE. ¿Cómo varía la solución óptima si se acepta un resultado no entero para la cantidad de sacos de XYLINE a producir? Comente

INGREDIE NTE

CANTIDAD POR SACO DE 50 LIBRAS DE XYLINE

CANTIDAD POR LIBRA DE HEXALL

DISPONIBILIDAD (Lb)

A

30lb

0.5l b

2,000

B

18lb

0.4l b

800

C

2lb

0.1l b

200

Caso 4 El entrenador de un equipo de natación debe asignar nadadores para la prueba de 200mt postas combinadas, que irán a las olimpiadas juveniles. Como muchos de sus mejores nadadores son rápidos en más de un estilo, no es fácil decidir cuál nadador asignar a cada uno de los cuatro estilos. Los cinco mejores nadadores y sus mejores tiempos -en segundosen cada estilo son los siguientes: ESTILO

CARLOS

MANUEL

DAVID

ANTHONY

BORIS

Espalda

37.7

32.9

33.8

37.0

35.4

Pecho

43.4

33.1

42.2

34.7

41.8

Mariposa

33.3

28.5

38.9

30.4

33.6

Libre

29.2

26.4

29.6

28.5

31.1

Formule un modelo de PL apropiado y resuélvalo, indicando el nadador escogido para cada estilo y el resultado óptimo esperado por el entrenador.

INVESTIGACIÓN DE Caso 5 Se desea realizar la asignación de programadores al desarrollo de programas. Se considera que un programador solo puede desarrollar un solo programa, y un programa debe ser desarrollado solamente por un programador. Se tienen 5 programadores y 4 programas, para tomar la decisión se ha estimado el tiempo de ejecución de acuerdo a la habilidad del programador y a las características del programa. PROGRAMAD OR

PROGRAMAS (HORAS) 1

2

3

4

1

12

11

10

11

2

10

10

11

10

3

11

10

12

14

4

13

9

13

10

5

12

10

14

11

Entre los programadores: 1, 2 y 3 se deben asignar a dos como máximo. Formule el modelo de programación lineal binaria que permita determinar la asignación de programadores para el desarrollo de los programas.

Caso 6 El entrenador Night trata de escoger una alineación inicial para el equipo de básquetbol. El equipo consta de siete jugadores que han sido evaluados (en una escala de 1 = pobre a 3 = excelente) de acuerdo a su manejo de la pelota, sus tiros, sus rebotes y sus habilidades en la defensa. En la siguiente tabla se encuentran las posiciones que cada jugador puede ocupar y sus habilidades. La alineación inicial de 5 jugadores debe satisfacer las siguientes restricciones: -

-

Por lo menos 3 jugadores del equipo inicial deben poder jugar en la defensa (D), por lo menos 2 miembros deben poder jugar al ataque (A) y por lo menos un jugador del equipo inicial debe poder jugar en el centro (C). El nivel medio del manejo de la pelota, de los tiros y del rebote de la alineación inicial debe ser por lo menos igual a 2. Si inicia el jugador 3, entonces el jugador 6 no podrá iniciar. Si el jugador 1 inicia, entonces los jugadores 4 y 5 deben iniciar. Ya sea el jugador 2 o el jugador 3 debe iniciar.

Dadas estas restricciones, el entrenador Night desea maximizar la capacidad defensiva total del equipo inicial. Formule el modelo de PLE que permita determinar qué jugadores deben conformar la alineación inicial del equipo.

INVESTIGACIÓN DE

JUGAD OR

POSICI ÓN

MANEJ O

TIROS

REBOT E

DEFEN SA

1

D

3

3

1

3

2

C

2

1

3

2

3

D-A

2

3

2

2

4

A-C

1

3

3

1

5

D-A

1

3

1

2

6

A-C

3

1

2

3

7

D-A

3

2

2

1

Caso 7 Cada día un camión de despachos debe decidir los bultos que transportará y dejará en su destino final de forma que logre hacer un uso eficiente de su capacidad que es de 500 kilos y maximice las ganancias de su propietario. Tiene la siguiente lista de 10 bultos por transportar en los próximos cuatro días y de ser posible debe transportar todos ellos a lo largo de estos tres días. Evidentemente no es posible transportarlos todos al mismo tiempo. Las ganancias que se señalan en el cuadro son las que recibe el propietario del camión al entregar el bulto el primer día, pero estas ganancias se reducen a la mitad cuando el bulto es entregado el segundo día y a la tercera parte cuando el bulto es entregado el tercer día y cuarto día. Formule el modelo de programación lineal que permita al propietario del camión planificar el trabajo de despacho de los bultos que sea posible trasladar en cada día.

BULTO

1

2

3

4

5

6

7

8

9

10

PESO (Kg)

150

100

300

200

150

120

180

100

200

250

Ganancia ($)

300

330

450

600

450

600

270

420

570

720

!

Caso 8 El quirófano de un centro de salud tiene solamente 15 horas disponibles para operaciones en el día. Deben programarse 8 pacientes que necesitan ser operados de manera urgente. Los pacientes han sido clasificados según la gravedad de su situación clínica. El nivel de gravedad (del 1 menos grave al 5, más grave) así como la duración estimada de la intervención requerida para cada paciente se muestran en la tabla siguiente. Como el tiempo disponible del quirófano no es suficiente para atender a todos, el centro de salud desea saber cuáles pacientes deberán atenderse y cuáles habrá que derivar a otro centro de salud cercano. -

Formule un PLE para ayudar al Centro de salud a tomar la decisión. Supongamos que algunos tratamientos son incompatibles con otros (debido al preparatorio del quirófano, personal especializado, etc). Específicamente, si no se opera a ningún paciente de tipo (gravedad) 2, no puede operarse a pacientes de

INVESTIGACIÓN DE

-

gravedad 1. Ahora se adiciona la condición que el paciente 4 (gravedad 5) únicamente podrá ser operado si tanto el paciente 6 como el 7 son operados. PACIEN TE

INDICE DE GRAVEDAD

TIEMPO (HORAS)

1

3

2

2

2

1.5

3

2

3

4

5

2.5

5

1

1.5

6

4

3

7

4

2

8

1

1

Caso 10 Par a promover l a seguridad en el campus, el Departamento de Seguridad Pública de la Municpalida se encuentra en proceso de instalación de teléfonos de emergencia en lugares seleccionados. El departamento desea instal ar una cant idad mínima de estos aparatos que presten servicio a c a da un a l a s c a l l e s principales del campus. La Figura muestra un mapa de dichas calles con las posibles ubicaciones de los teléfonos (es lógico maximizar la utilidad de los teléfonos si se les coloca en intersecciones de calles, de modo que una sola unidad puede prestar servicio al menos a dos calles). Usted debe preparar un modelo de PLE que ayude a la UPC a tomar la mejor decisión. Caso 11 Una línea aérea necesita asignar sus tripulaciones para cubrir todos sus vuelos programados. Se estudiará el problema de asignar tres tripulaciones con base en San Francisco (SF) a los vuelos enumerados en la tabla adjunta. Las otras 12 columnas muestran 12 secuencias de vuelos factibles de una tripulación. (Los números en cada columna indican el orden de los vuelos.) Es necesario elegir tres de estas secuencias (una por tripulación) de tal manera que se cubran todos los vuelos (se permite tener más de una

INVESTIGACIÓN DE tripulación en un vuelo, en el cual los miembros de la tripulación adicional volarían como pasajeros, pero los contratos colectivos de trabajo requieren que se pague el tiempo de la tripulación adicional como si estuviera en horario de trabajo). El costo de asignar una tripulación a una secuencia de vuelos específica se muestra (en miles de dólares) en el renglón inferior de la tabla. El objetivo es minimizar el costo total de asignar las tres tripulaciones de manera que cubran todos los vuelos.

Caso 12 Existen seis barrios en una ciudad. La alcaldía debe determinar cómo construir estaciones de bomberos. Se desea construir el número mínimo de estaciones de bomberos, de forma de asegurar que al menos una estación esté a menos de 15 minutos de cada barrio. Los tiempos de viaje entre cada barrio de la ciudad se muestran en el cuadro. Formule un modelo de PLE que permita determinar cuántas estaciones deben construirse y dónde deben estar ubicadas. Caso 13 El departamento de Marketing de Gandalf, S.A. ha calculado la demanda agregada prevista para los próximos meses: enero (2.000 unid.), febrero (1.500 unid.), marzo (800 unid.), abril (500 unid.), mayo (2.500unid) y junio (3.OOO unid.). AntonioMena, director deoperaciones de la

INVESTIGACIÓN DE empresa, está elaborando un nuevo plan agregado, que comenzaría en enero, con un inventario inicial de 350 unidades (no existe inventario a final junio). El costo de rotura de stocks se estima en 80 euros/unidad y el costo de almacenamiento en 15 euros/unidad y mes. Ayuda al Sr. Mena a decidir, sabiendo que: -

-

La plantilla actual es de 20 trabajadores, con una productividad media de 3,5 horas/ unidad y un salario medio de 15 euros/hora. El costo de contratación es de 400 euros/ trabajador y el costo de despido de 600 euros/trabajador (suponer una jornada laboral de 8 horas y 30 días laborales al mes). Se puede utilizar la subcontratación a un costo adicional de 60 euros/unidad. Se puede usar horas extraordinarias hasta un máximo 20% del total con un costo adicional de 4 euros/hora. La capacidad de nuestro almacén limita el máximo inventario posible a 380 unidades....