• Author / Uploaded
• Jean Brian

Citation preview

PROGRAMACION ENTERA BINARIA INTRODUCCION Existen numerosas aplicaciones de programación entera en la que el problema incluye cierto número de decisiones sí o no interrelacionadas. En situaciones de este tipo, las únicas dos elecciones posibles son sí o no. Por ejemplo, ¿Debe emprenderse un determinado proyecto?, ¿Debe hacerse cierta inversión de capital? ¿Debe ubicarse la planta de producción en un determinado lugar? Debido a que estos problemas involucran sólo dos posibilidades, este tipo de decisiones se pueden representar mediante variables de decisión restringida a sólo dos valores, 0 y 1. De esta forma, la i-ésima decisión sí o no se puede representar por xi , tal que

xi =

1 si la decisión i es sí 0 si la decisión i es no

Las variables de este tipo se llaman binaria (o variables 0-1). En consecuencia, algunas veces se hace referencia a los problemas de programación entera que contienen sólo variables binarias como problemas de programación entera binaria (PEB o PB) o problemas 0-1 de programación entera.

1

ALGUNAS APLICACIONES DE PROGRAMACION ENTERA BINARIA

2



Análisis de la inversión  ¿Debe preferirse cierto proveedor?  ¿Debe agregarse una nueva línea de producción?



Elección del sitio  ¿Debe elegirse cierto lugar para la ubicación de cierta instalación nueva?



Diseño de una red de producción y distribución  ¿Debe cierta planta permanecer abierta?  ¿Debe abrirse una nueva sucursal de distribución?



Asignaciones  ¿Debe ubicarse a cierto operario en determinado puesto de trabajo?  ¿Debe asignarse cierto tipo de avión a una ruta en particular?



Programación de actividades interrelacionadas  ¿Cuándo se debe iniciar la producción de las nuevas órdenes?  ¿Cuándo deben comercializarse los nuevos productos?

EJEMPLOS EJEMPLO 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 Cocinar Lavar platos Lavar ropa (A) (B) (C) (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.

Modelo: VARIABLES: ij : Se realiza o no la actividad i por j, (i =A,B,C,D) (j =1:Carlos, 2:Sara) FUNCION OBJETIVO: MIN = 4.5*A1 + 7.8*B1 + 3.6*C1 + 2.9*D1 + 4.9*A2 + 7.2*B2 + 4.3*C2 + 3.1*D2; RESTRICCIONES: A1+B1+C1+D1=2; A2+B2+C2+D2=2; A1+A2=1; B1+B2=1; C1+C2=1; D1+D2=1; @BIN(A1);@BIN(B1);@BIN(C1);@BIN(D1); @BIN(A2);@BIN(B2);@BIN(C2);@BIN(D2); Asignación: A1, C1, B2, D2; Z=18.4

3

EJEMPLO 2 Un entrenador pretende elegir la alineación inicial para su equipo de basquetbol. Su selección consta de 7 jugadores que están calificados (con una escala de 1: malo, 2: regular y 3: excelente) de acuerdo con su manejo del balón, disparos, rebotes y habilidades en recuperación del balón. Las posiciones en la que a cada jugador se le permite jugar y las capacidades del jugador son las siguientes: Jugador Posición 1 2 3 4 5 6 7 8 9

D C D-O O-C D-O O-C D-O O-C D-C

Dominio de balón 3 2 2 1 3 3 2 1 3

Disparos Rebote 3 1 3 3 3 1 2 2 1

1 3 2 3 3 2 2 2 3

Recuperaci ón de balón 3 2 2 1 3 3 1 3 2

D: Defensiva, C: Central, O: Ofensiva El equipo inicial de cinco jugadores tiene que satisfacer las condiciones siguientes: 

  



Por lo menos 3 miembros deben ser capaces de jugar en la posición defensiva, por lo menos 2 elementos deben ir en la posición ofensiva y al menos uno estará en la posición central. El nivel promedio de dominio de balón, disparos y rebotes de los jugadores en la alineación inicial tiene que ser por lo menos de 2. Debe empezar el jugador 2 o el jugador 3, pero no ambos. Si es que el jugador 4 empezara a jugar, entonces el jugador 6 no puede jugar (podrían no entrar ambos o entrar solamente el jugador 6) Si el jugador 1 inicia, entonces los miembros 4 y 9 también deben jugar; si no, alguno de éstos últimos o ambos podrían entrar.

Dadas estas restricciones, el entrenador desea maximizar la capacidad del equipo inicial en recuperación del balón. Formule un PEB que ayude al entrenador a escoger a su equipo inicial. Modelo matemático: !VARIABLES: Xi = Ingresa o no el jugador i al equipo inicial, donde (i=1,2,3,4,5,6,7,8,9) FUNCION OBJETIVO; MAX = 3*X1 + 2*X2 + 2*X3 + X4 + 3*X5 + 3*X6 + X7 + 3*X8 + 2*X9; !(Maximizar capacidad de recuperar el balón); !RESTRICCIONES; 4

X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 = 5; !(5 jugadores); X1 + X3 + X5 + X7 + X9 >= 3; !(posición defensiva); X3 + X4 + X5 + X6 + X7 + X8 >= 2; !(posición ofensiva); X2 + X4 + X6 + X8 + X9 >= 1; !(posición central); (3*X1+2*X2+2*X3+X4+3*X5+3*X6+2*X7+X8+3*X9)/5 >= 2; !(nivel promedio de dominio); (3*X1+X2+3*X3+3*X4+3*X5+X6+2*X7+2*X8+X9)/5 >= 2; !(nivel promedio de disparos); (X1+3*X2+2*X3+3*X4+3*X5+2*X6+2*X7+2*X8+3*X9)/5 >= 2; !(nivel promedio de rebote) ; X2 + X3 = 1; !(jugador 2 ó 3 inicia); X4 + X6