Programación Entera y binaria, ramificacion y acotamiento binario #1

Concepto

La programación entera consiste en encontrar soluciones a problemas de programación lineal donde los valores de las variables deben de ser enteros,

Una de las formas para poder determinar la solución factible de un problema de programación entera, es hacer lo que se denomina una relajación al problema entero, esto se hace realizando de forma gráfica como si fuese un problema de programación lineal.

Tipos

Existen dos tipos de programación entera, están las puras, en las cuales todas las variables de decisión deben ser enteras, y luego las simples, en las que existen variables que NO necesariamente deben de ser enteras.

Entre la programación entera pura, esta una forma particular en la cual solo se aceptan valores cero o uno, esto es programación entera binaria y se usa con mucha frecuencia en ejercicios en los que hayan un elemento este haciendo algo (1) o no (0).

xi (i = 1, 2, 3, 4) {1: Si se hizo la inversión; 0: Si no se hizo la inversión}

Restricciones

Aparte de las condiciones conocidas, existen casos diferentes a los que conocemos en la programación lineal, tomando un ejemplo de inversión que es PE binaria se considera lo siguiente:

1) Se puede invertir cuando mucho en dos inversiones: debido a que solo se puede aceptar cero o uno en las variables, validamos que al hacer la sumatoria, solo existan dos inversiones activas (dos 1).

x1+x2+x3+x4<= 2

2) Si se invierte en la inversión dos, entonces también se debe invertir en la inversión uno: al convertir la inversión 2 con 1, estamos obligando que la inversión uno deba valer también 1, y si hacemos que la inversión 2 valga 0, no estamos obligando que la inversión uno valga 0, dándole libertad de ser 1 si desea.

x2 <= x1

3) Si se invierte en la inversión dos, no puede invertir la inversión cuatro: al hacer la sumatoria de las dos inversiones menor a uno, obligamos que solo una de las dos o ninguna este activas.

x2+x4 <= 1

En otro ejercicio sobre ropa, se puede modelar todo menos el costo fijo, en ese caso se utiliza los valores binarios creando variables de tipo y que pueden tomar 0 o 1.

max z 6x1+4x2+7x3-200y1-150y2-100y3

s.a 3x1+2x2+6x3 <= 150

4x1+3x2+4x3 <= 160

xi >= 0 y enteros

yi = 0,1

En las restricciones de la maquinaria de la ropa, para establecer que si xi > 0 entonces yi = 1, se realiza con un valor de capacidad máxima en xi y se multiplica con mi.

xi <= mi * yi donde mi es la capacidad máxima i

Entonces:

x1 <= 40y1

x2 <= 54y2 

En ese caso da 53.3 pero se garantizamos que se cumpla la restriccion

x3 <= 25y3

Debemos tener en cuenta todas las restricciones como tal.

Método de ramificación y acotamiento binario:

En el ejemplo de la mochila, realizamos una tabla:

Objeto	ci / ai	Clasificacion	Sobrante	Obsevaciones
1	1	3.5(4)	x1 = 10/40 = 1/4	Empate para el 3° o 4°
2	1 3/5	2	70-30 = 20
3	1/3	7
4	1	3.5(3)	2-10=10	Empate para el 3° o 4°
5	2/5	6
6	1/2	5
7	2	1	100-30=70

Como es un ejercicio entero no puro, se puede fraccionar ciertas variables de decisión. El objetivo es satisfacer la función objetivo.

La ramificación consiste en ir ramificando el problema original por medio de nuevas restricciones, se debe ramificar cuando las variables sean fraccionarias, hasta que solo sean enteras o infactibles.

Recordando, una solución es infactible cuando la restricción no entra en la región factible.

• La ramificación se hace con la variable que brinde mas importancia económica en el problema. 
• Deben ser fraccionarios, una vez se encuentra un valor entero no se ramifica mas.
• Funciona con lifo, resolviendo el ultimo problema que se encuentre.

Ver:

Programacion Entera, algo completo