• Author / Uploaded
• Roberto Pablo Tejada Cruzado

• Categories
• Programación lineal
• Ciencias de la Computación
• Informática
• Tecnología
• Áreas de informática

Citation preview

PROGRAMACION BINARIA

Ing. Manuel Sánchez Terán

INVESTIGACION DE OPERACIONES II

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.

ALGUNAS APLICACIONES DE PROGRAMACION ENTERA BINARIA



 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?

Ing. Manuel Sánchez Terán

1

   



 EJEMPLOS

  EJEMPLO 1 (Tareas del hogar)  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:  



 Co mpr as  (A)

 Horas necesarias por semana  C o  Lavar ci n platos ar  (C)  (B )  7.  3.6 8  7.  4.3 2

 Lavar ropa  (D)

 Carlo  4.5  2.9 s (1)  Sara  4.9  3.1 (2)   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   EJEMPLO 2 (Licitación de obras)  Una municipalidad necesita la realización de 4 obras y 5 empresas constructoras (A, B, C, D y E) han presentado sus propuestas económicas. Se ha determinado que, por limitaciones de maquinaria y equipo, cada empresa constructora solamente puede hacerse cargo de una sola obra; excepto la empresa E que puede hacerse cargo hasta de 2 obras. ¿Cómo se debería de realizar la municipalidad la asignación de obras si se pretende un costo total mínimo?   Tabla de costos:  (la X significa que no es posible que la empresa realice la obra) 

   

 Costo por obra (en miles de S/.)

  E m p r e s a  c o n s t r u c t o r a

 O

 O

 A

 18

 16

 B

 16

 15

 C

 X

 X

 D

 17

 16

 E

 16

 X

 O

 X

 O

 30

 25

 32

 23

 31

 22  22

 X  X

      

!VARIABLES: Xij: Se asigna a la empresa "i" (i= A,B,C,D,E) la obra "j" (j=1,2,3,4); !FUNCION OBJETIVO; MIN = 180*XA1 + 160*XA2 + 300*XA4 +  160*XB1 + 150*XB2 + 250*XB3 + 320*XB4 + 230*XC3 + 310*XC4 + 175*XD1 + 165*XD2 + 220*XD3 + 165*XE1 + 220*XE3;

            

!RESTRICCIONES; !Máximo de obras por empresa; XA1 + XA2 + XA4 = 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