PROGRAMACION ENTERA BINARIA

[pic 3]

[pic 4]

[pic 5]

[pic 6]

[pic 7]

[pic 8]

PROGRAMACION BINARIA

Ing. Manuel Sánchez Terán

PROGRAMACION ENTERA BINARIA[pic 9]

❑        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[pic 10]

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?

❑        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:

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

Un entrenador pretende elegir la alineación inicial para su equipo de basquetbol. Su equipo consta de 9 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:

D: Defensiva, C: Central, O: Ofensiva

...