Ejercicios resueltos Programación Entera-Binaria - IOP PDF

Preview

Summary

Para hallar el nuevo valor de la F. O., hay que ver el precio dual correspondiente:Row Slack or Surplus Dual Price PROD_HERRAM( 2) 0 -4.La función objetivo se perjudica en $4 por el aumento de una unidad en la producción mínima de herramientas H2. Como se pretende aumentar en 60 la producción mínima...

Description

p

=, la fu

2. MODELOS DE PROGRAMACIÓN LINEAL CON VARIABLES DE DECISIÓN BINARIAS. Ejercicio 2.1 (Winston Wayne, página 502) 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, su rebote y sus habilidades en defensa. En la Tabla 1 se encuentran las posiciones que cada jugador puede ocupar y sus habilidades. La alineación inicial de cinco 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 debe 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 uno inicia, entonces los jugadores 4 y 5 deben iniciar al mismo tiempo. Ya sea el jugador 2 o el jugador 3 debe iniciar. El entrenador Night se ha caracterizado por que sus equipos son muy hábiles en la defensa. Las posiciones que cada jugador puede ocupar y sus habilidades se presentan en la siguiente tabla: Jugador Posición Manejo Tiros Rebote Defensa 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 a)

Defina las variables de decisión: Variables de decisión:

b)

X(i) : Asignar o no asignar al jugador i (i=1,2,3,4,5,6,7)

Formule el modelo de programación lineal binaria que permita determinar qué jugadores deben conformar la alineación inicial del equipo. Datos: Manejo(i) Tiros(i) Rebote(i) Defensa

: Puntuación en el manejo de la pelota del jugador i. : Puntuación en los tiros del jugador i. : Puntuación en el rebote del jugador i. : Puntuación en habilidades de defensa del jugador i.

Página 7

7

∑

()

()

1

. .: 7

∑

()

5

[La alineación inicial es de 5 jugadores]

3

[Por lo menos 5 jugadores deben poder jugar en defensa]

2

[Por lo menos 2 jugadores deben poder jugar en ataque]

1

(1)

(3)

(5)

(7)

7

∑

()

3

(2)

(4)

(6)

1

7

[Por lo menos 1 jugador debe poder jugar en centro] 7

∑

()

2∑

()

1

()

[Nivel medio de manejo de pelota por lo menos = 2]

()

[Nivel medio de tiros por lo menos = 2]

()

[Nivel medio de rebote por lo menos = 2]

1

7

7

∑

()

2∑

()

1

1

7

7

∑

()

2∑

()

1

(3) (6) (1) (1) (2) (3) : ()

1

1

[Si inicia el jugador 3, el jugador 6 no debe iniciar] [Si inicia el jugador 1, el jugador 4 debe iniciar] [Si inicia el jugador 1, el jugador 5 debe iniciar] [El jugador 2 ó 3 debe inciar]

(4) (5) 1 :

Ejercicio 2.2 La Facultad de Sistemas desea programar la asignación de alumnos al desarrollo de programas. Se considera que un alumno solo puede desarrollar un solo programa, un programa debe ser desarrollado solamente por un alumno. Se tienen 5 alumnos y 4 programas, para tomar la decisión se estimaron los tiempos que tomaría desarrollar el programa de acuerdo a la habilidad del alumno y a las características del programa.

Alumno 1 2 3 4 5

1 12 10 11 13 12

Programas (horas) 2 3 11 10 10 11 10 12 9 13 10 14

4 11 10 14 10 11

Entre los programadores: 1, 2 y 3 se deben asignar a dos como máximo. Defina las variables de decisión del presente problema y formule el modelo de programación lineal binaria correspondiente. Variables de decisión:

X(i,j): Asignar o no asignar al alumno i el desarrollo del programa j (i=1,2,3,4,5 ; j=1,2,3,4)

Datos del problema:

Tiempo(i,j): Tiempo que le tomaría al alumno i desarrollar el programa j

Página 8

5

4

(, )

∑∑ 1

(, )

1

. .: 4

:∑ ( , )

1

[A cada alumno se le puede asignar a lo más un programa]

1

[Cada programa debe ser asignado a un alumno]

2

[Entre los programadores 1, 2 y 3 se deben asignara dos como máximo]

1 5

:∑ ( , ) 1 3

4

∑∑ 1

(, )

1

, :

(, )

Ejercicio 2.3 (Winston Wayne, página 505) En una planta de máquinas herramientas se debe terminar 5 trabajos cada día. El tiempo que toma efectuar cada trabajo depende de la máquina usada para efectuar dicho trabajo. Si se usa en modo alguno una máquina, entonces hay un tiempo de preparación o de puesta a punto necesario independiente del número de trabajos que se hagan en ella. Los tiempos relacionados se proporcionan en la siguiente tabla. Tiempo de operación (en min) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Trabajo 5 42 70 93 ------1 ---85 45 ------2 58 ------37 ---3 58 ---55 ---38 4 ---60 ---54 ---5 De la tabla anterior puede leerse, por ejemplo, que la máquina 1 no puede hacer trabajos de tipo 4 y 5. Máquina

Tiempo de preparación (min) 30 40 50 60 20

El objetivo de la planta es minimizar la suma de los tiempos de preparación y de operación necesaria para completar todos los trabajos. Defina las variables de decisión y plantee el modelo de programación lineal correspondiente. Variables de decisión:

X(i,j): Asignar o no asignar en la máquina i el trabajo j (i=1,2,3,4,5 ; j=1,2,3,4,5). Y(i): Utilizar o no la máquina i.

Datos del problema:

TpoOperacion(i,j): Tiempo de operación por tipo de máquina y por tipo de trabajo. En LINGO, al ingresar los datos en esta matriz, colocar 99999 a las celdas que posean ---TpoPreparacion(i): Tiempo de preparación de la máquina i.

5

()

∑ 1

()

5

5

∑∑ 1

(, )

(, )

1

. .: 5

:∑ ( , )

5

()

[En cada máquina, se puede asignar hasta 5 trabajos]

1 5

:∑ ( , )

1

[Cada trabajo debe ser asignado]

1

: () , : (, ) Ejercicio 2.4 (Winston Wayne, página 553) La decisión de una corte estableció que la matrícula de cada escuela de bachillerato en Metropolis debe tener por lo menos 20% de estudiantes de bajos recursos económicos. El número de estudiantes de altos y bajos recursos económicos en cada uno de los 5 distritos escolares se muestra a continuación:

Página 9

Distrito 1 80 30 110

De altos recursos De bajos recursos Total

Distrito 2 70 5 75

Distrito 3 90 10 100

Distrito 4 50 40 90

Distrito 5 60 30 90

La distancia, en millas, que un estudiante debe viajar a cada escuela de bachillerato en cada distrito se proporciona a continuación: A De Escuela 1 Escuela 2

Distrito 1

Distrito 2

Distrito 3

Distrito 4

Distrito 5

1 2

0.5 1.7

0.8 0.8

1.3 0.4

1.5 0.6

La política escolar establece que todos los estudiantes en un distrito dado asistan a la misma escuela. Si cada escuela debe tener por lo menos 150 estudiantes, determine las variables de decisión y formule un modelo de programación lineal que minimice la distancia total que los estudiantes tienen que recorrer hasta la escuela. Variables de decisión:

X(i,j): Asignar o no asignar a los estudiantes del distrito j a la escuela i (i = 1,2 ; j=1,2,3,4,5)

Datos del problema:

NumEstBR(j): Total(j): Dist(i,j):

2

Número de estudiantes de bajos recursos 1 que viven en el distrito j Total de estudiantes que viven en el distrito j. Distancia en millas entre la escuela i y el distrito j.

5

∑∑ 1

( )

(, )

(, )

1

. .: 2

:∑ (, )

[En c/ distrito, se puede asignar a sus estudiantes a lo más en una escuela]

1

1 5

5

:∑

( )

(, )

0.2

1 5

:∑

∑

( )

( , ) [En c/ escu ela, por lo menos 20% de la matrícula son de bajos recursos]

1

( )

(, )

150

[En c/ escuela, debe haber por lo menos 150 estudiantes]

1

, : (, )

3. Modelos de programación lineal enteros puros y mixtos. Ejercicio 3.1 Gandhi Company puede fabricar tres tipos de ropa: camisas, calzoncillos y pantalones. Para poder fabricar cada tipo de ropa, Gandhi tiene que disponer de la maquinaria adecuada. Hay que rentar la maquinaria requerida para fabricar una tipo de ropa, a la siguiente tarifa: maquinaria para camisas 200 dólares por semana; maquinaria para calzoncillos, 150 dólares por semana; maquinaria para pantalones, 100 dólares por semana. La fabricación de cada tipo de ropa también requiere las cantidades de tela y de trabajo que se dan en la Tabla 1. Cada semana se dispone de 150 horas de trabajo y de 160 yardas cuadradas de tela. En la Tabla 2 se dan los cosos unitarios variables y los precios de venta de cada tipo de ropa. Tabla 1 Tabla 2 Tipo Trabajo (horas) Tela (yardas 2 ) Precio de venta Costo variable Tipo Camisa 3 4 ($ / unidad) ($ / unidad) Calzoncillo 2 3 Camisa 12 6 Pantalón 6 4 Calzoncillo 8 4 Pantalón 15 8 Defina las variables de decisión y formule el modelo de programación lineal entera binaria que permita optimizar las operaciones de Gandhi Company

1

Nótese que no se necesita tener como datos del problema el número de estudiantes de altos recursos que viven en cada distrito. Página 10

Variables de decisión:

X(i) : Cantidad de prendas de tipo i a fabricar Y(i) : Arrendar o no arrendar la máquina para fabricar las prendas de tipo i.

Datos del problema:

Precio(i) CostoVar(i) CostoRenta(i) ReqTrabajo(i) ReqTela(i)

(i = 1,2,3)

: Precio de venta ($/und) de una prenda de tipo i. : Costo variable ($/und) de una prenda de tipo i. : Costo por rentar la máquina para fabricar el tipo de prenda i. : Requerimiento de horas de trabajo por cada prenda i. : Requerimiento de tela por cada prenda i.

3

∑

()

()

()

()

()

1

. .: :

()

()

150

( ) [Disponibilidad horaria de cada tipo de máquina]

3

∑

()

()

160

[Disponibilidad de tela]

1

:

( ),

()

Ejercicio 3.2 DUCTOGAS S.A. es un fabricante de tubos especiales para las redes de distribución de gas. Actualmente fabrica 2 tipos de tubos según el tipo de red en que se va a utilizar: Red secundaria y Red domiciliaria; estos tubos se pueden producir en cualquiera de sus dos líneas de producción: A y B. En la siguiente tabla se indican las horas que se requiere en cada línea para producir cada uno de los tipos de tubos. Tubos (según tipo de red) Secundaria Domiciliaria

Tiempo de producción (horas / tubo) Línea A Línea B 0.34 0.35 0.20 0.25

Cada línea de producción funciona 16 horas diarias, 6 días a la semana, y los costos de producción (costo de mano de obra + costos de operación) de cada tubo según la línea de producción se presenta en la siguiente tabla: Tubos (según tipo de red) Secundaria Domiciliaria

Costo producción ($ / tubo) Línea A Línea B 25 26 17 18

Los tubos son vendidos a los siguientes precios: Tubos (según tipo de red) Secundaria Domiciliaria

Precio de venta ($ / tubo) 30 23

DUCTOGAS tiene la posibilidad de comprar tubos de ambos tipos de red, ya hechos, a 3 proveedores distintos. La utilidad neta que se obtendría por tipo de tubo según el proveedor se específica en la siguiente tabla: Tubos Secundaria Domiciliaria

Proveedor 1 3 4

Proveedor 2 4 3

Proveedor 3 3 3

Si se decide realizar pedido de tubos a determinado proveedor, se incurrirá en un costo fijo por trámites administrativos independiente de la cantidad que se pida. Además estos proveedores han impuesto un tamaño de pedido mínimo. Los costos fijos y las cantidades mínimas mencionados se presentan en la siguiente tabla: Pedido mínimo - secundaria Pedido mínimo - domiciliaria Costo fijo ($)

Proveedor 1 70 80 400

Proveedor 2 70 80 400

Proveedor 3 60 50 300

Página 11

Debido a que estos proveedores son en su totalidad MYPES, no tienen la capacidad de aceptar pedidos superiores a 100 tubos por semana, ya sean para redes secundarias o para redes domiciliarias. Si se decide por algún proveedor se le debe hacer pedidos por ambos tipos de tubos. El plan semanal de producción y de compra de los tubos no deben superar los 500 y 600 tubos para redes secundarias y domiciliarias respectivamente. Formule el modelo de programación lineal entera binaria que permita determinar en qué líneas se deben producir los tubos para cada tipo de red, así como determinar a qué proveedores y en qué cantidad se deben adquirir los tubos para cada tipo de red. Variables de decisión:

Datos del problema:

2

2

∑∑ 1

X(i,j) Y(i,k) W(k)

: Cantidad de tubos de tipo i a producir en la línea j para una semana. : Cantidad de tubos de tipo i a pedir al proveedor k para una semana. : Hacer o no hacer pedido al proveedor k.

Pvta(i) Cprod(i,j) Tiempo(i,j) Util(i,k) CFijo(k) CantMax(i) PedidoMin(i,k)

()

(i=1,2 ; j=1,2 ; k = 1,2,3)

: Precio de venta del tubo de tipo i. : Costo de producción del tubo tipo i en la línea j. : Tiempo de producción por cada tubo de tipo i en la línea j. : Utilidad unitaria del tubo tipo i proveniente del proveedor k. : Costo fijo por trámites administrativos del proveedor k. : Cantidad máxima del plan de producción y compras de tubos de tipo i. : Mínima cantidad de tubos de tipo i a pedir al proveedor k.

(, )

(, )

1

2

3

∑∑ 1

1

(, )

(, )

3

∑

( )

( )

1

. .: 2

:∑

(, )

(, )

16(6)

[Disponibilidad horaria de c/ línea]

1

2

:∑

(, )

1

: (, )

,

: (, )

,

: :

(, )

()

[Cantidad máxima de producción y ventas de c/tipo de tubo]

1

,

,

3

∑

100

( )

[Por c/tipo de tubo y c/prov., se acepta como máximo 100 tubos] (, )

(, )

0

: (, )

0

( ) [Mínima cantidad de c/tipo detubo a pedir a c/proveedor]

( )

Ejercicio 3.3 El departamento de producción de una fábrica de clavos desea establecer un programa de producción para los siguientes tres meses. Cuenta con los siguientes datos: Costo de producción (soles / caja) Mes Demanda (cajas) Turno normal Turno extra Enero 900 2 2.5 Febrero 1000 3 5.0 Marzo 1300 4 6.5 La capacidad de producción en el turno normal es de 900 cajas y la capacidad en el turno extra es de 200 cajas en cada mes. La fábrica de clavos cuenta adicionalmente con un almacén que tiene una capacidad de 250 cajas con un costo de almacenamiento de S/1 por caja por mes y un costo fijo de S/50 por mes, si se usa el almacén en el mes. El inventario inicial en enero es de cero unidades. Finalmente, si en el tercer mes se producen más de 100 cajas de clavos en el turno extra se incurre en un costo fijo de S/80 en este mes. Determine las variables de decisión y formule el modelo de programación lineal entera correspondiente en la forma matemática compacta. Variables de decisión:

Datos del problema:

X(i,j) Inv(i) Y(i) W

: Cajas de clavos a producir en el mes i, turno j. : inventario de cajas de clavos al final del mes i. : Utilizar o no utilizar el almacén en el mes i. : Producir o no producir más de 100 cajas de clavos en el mes 3

CProd(i,j) Cap(j) Dem(j)

(i=1,2,3 ; j=1,2)

: Costo de producción por caja en el mes i, turno j. : Capacidad mensual de producción en el turno j. : Demanda de cajas de clavos en el mes j. Página 12

3

2

3

∑∑ 1

(, )

(, )

1

∑1

3

( ) 50∑ ( ) 80

1

. .: , : (, ) : () (3, 2)

1

( ) 250 ( ) 100 (200 100)

[Capacidad disponible en cada mesy en cada turno] [Límite de inventario en cada mes] [Límite de producción en el mes 3 en el turno extra]

2

1: 0

∑

(, )

()

()

[Ecuación del inventario en el primer mes]

()

()

[Ecuación del inventario en los demás meses]

1 2

1:

(

1)

∑

(, )

1

, : (, ) , : (, ) : () : ()

0 0

Ejercicio 3.4 Una compañía constructora, está estudiando la posibilidad de construir viviendas en uno de los terrenos de su propiedad cuya área es de 60000 m2. La compañía se especializa en la construcción de tres clases de viviendas: pequeña, mediana y grande. El área requerida, costo de construcción y precio de venta de cada tipo de vivienda se presenta en la siguiente tabla. Información Área requerida (m2/vivienda) Costo de construcción (Miles $/vivienda) Precio de venta (Miles $/vivienda)

Pequeña 80 60 100

Tipo de vivienda Mediana Grande 100 120 100 150 160 200

En un estudio de mercado se ha determinado el número mínimo y máximo de viviendas que deben construir de cada tipo en caso que se decida construir. Tipo de vivienda Pequeña Mediana Grande Cantidad mínima 220 180 30 Cantidad máxima 420 380 100 La compañía constructora se ha caracterizado por ofrecer viviendas de calidad, además de brindar zonas de recreación. Existe la opción de construir las siguientes zonas de recreación: un Parque Infantil, una Alameda o un Pequeño bosque. A continuación se presenta la información relativa a estas tres zonas de recreación: Zona de recreación Parque infantil Alameda Bosque Área requerida (m 2) 4000 8000 6000 Costo (Miles $) 500 900 750 Se deben tener las siguientes condiciones: Se debe construir por lo menos 2 zonas de recreación. Las viviendas pequeñas y grandes en conjunto no deben superar al 50% del total de las viviendas. El número total entre los tres tipos de viviendas no deben exceder de 620 viviendas. Defina el significado de cada variable de decisión y formule el modelo de programación lineal entera binaria que permit...