UNIVERSIDAD COOPERATIVA DE COLOMBIA
CRISTIAN MANUEL SAAVEDRA DUARTE
GUSTAVO SILVA RODRÍGUEZ
PROGRAMACIÓN ENTERA ALGORITMO DAKIN
PROGRAMACIÓN Y CONTROL DE LA PRODUCCIÓN
BOGOTA
2019
Programación lineal entera
una limitación importante que impide muchas otras aplicaciones es el supuesto de
divisibilidad, que requiere que las variables de decisión puedan tomar valores no enteros.
En muchos problemas prácticos, las variables de decisión sólo tienen sentido real si su
valor es entero. Por ejemplo, con frecuencia es necesario asignar a las actividades
cantidades enteras de personas, máquinas o vehículos. Si el hecho de exigir valores enteros
es la única diferencia que tiene un problema con la formulación de programación lineal,
entonces se trata de un problema de
programación entera (PE). El modelo matemático para programación entera es
sencillamente el modelo de programación lineal con la restricción adicional de que las
variables deben tener valores en-teros. Si sólo es necesario que algunas de las variables
tengan valores enteros y el supuesto de divisibilidad se cumple para el resto.
Programación entera binaria
Método bifurcación y acotamiento
Como su nombre lo indica, consiste en partir del problema original, el cual se ira
dividiendo en ramas. Cada una de las cuales va acotando la región factible de solución,
conservando las soluciones enteras hasta que se encuentre la solución óptima.
El procedimiento del método consiste en los siguientes pasos.
1. Se resuelve el problema original de programación lineal, sin limitarse a una
solución entera si la solución obtenida es entera, esta será la optima para el
problema, pero se es fraccionaria en algunas de las variables de decisión se continua
al paso siguiente.
2. De las variables de decisión que hayan resultado fraccionarias en el paso anterior, se
toma una de ellas, por decir Xi la cual quedara comprendida entre los números
enteros consecutivos, los cuales desinaremos por K1 y K2 entonces:
De aquí el problema tendrá su primera ramificación en 2 partes o nuevos
subproblemas, los cuales serán idénticos al problema que les dio origen, añadiendo
una restricción adicional cada uno de ellos, los cuales serán:
Con esto cada rama abarcara una región factible de solución mas limitada que la del
problema original, lo cual implica haber dividido este en 2 subproblemas mas
pequeños. En el caso de haber varias variables de decisión fraccionarias que sean
candidatas para efectuar ramificaciones, deberá tomarse aquella que quede más
próxima a la fracción intermedia entre dos enteros consecutivos, es decir. (0,5).
3. Resolver cada rama del paso anterior por medio de programación lineal, de aquí
podemos tener varias posibilidades, por decir.
Que la solución encontrada no sea factible, en este caso esta rama ya no se
investiga mas
Que la solución hallada sea entera. En este caso esta solución se convertirá
en una cota que será inferior para problemas de maximización y superior
para los de minimización. Esto viene siendo el proceso de acotación, de esta
rama ya no se prosigue la búsqueda de nuevas opciones
Que la solución encontrada sea fraccionaria. De aquí esta rama será
candidata para seguir haciendo bifurcaciones, siempre y cuando el valor
hallado para la función objetivo sea mejor que el de alguna cota fijada en
una etapa anterior, pues de no suceder así, ya no se proseguiría la búsqueda
y esa cota anterior sería la solución óptima. Si la búsqueda hubiese
continuado y se encontrará una nueva solución entera cuya función objetivo
fuese mejor que la de la cota anterior, dicha rama tomaría el lugar de la
nueva cota en sustitución de la anterior.
Este procedimiento se continua hasta que ya no haya posibilidades de ramificación
posteriores con esto tendremos la certeza de que se encontrara la solución entera optima en
caso de haberla, siendo esta ultima cota que haya prevalecido como tal hasta el final del
problema.
Resumen algoritmo Dakin
Por conveniencias se ordenan de manera que las primeras i de ellas sean variables con
restricción a enteras, la forma general del problema que se va a estudiar es:
Es similar al que se estudia para [Link]. De nuevo la soltura de P.L. proporciona la
base tanto para la ramificación como para el acotamiento. Se necesitan 4 cambios al
algoritmo de P.E.B. para generalización de variables enteras binarias a generales y de P.E.
pura a P.E. mixta.
primer: la elección de la “variable de ramificación” (antes se elegía la siguiente
variable en el orden natural X1 hasta Xn). Ahora las únicas que se toman son las
variables enteras y que tienen un valor no entero en la solución de la soltura P.L
para el subproblema actual. El orden será la primera de la lista en el orden natural.
segundo: es el valor asignado a las variables de ramificación (mientras que antes era
“0” o “1”) ahora puede existir un número grande de valores enteros posibles), pero
igual se crean 2 subproblemas especificando 2 intervalos. Esto se hace partiendo del
valor de la variable en la solución de soltura P.L. y eligiendo los 2 números enteros
(anterior y posterior) y quedan determinados 2 intervalos ejemplo:
Ej Si Xj = 3 ½ Se toma Xj ≤3 y Xj ≥ 4
se agregan estas desigualdades a las restricciones para cada uno de los nuevos
subproblemas. Puede ocurrir, que en el paso de ramificación siguiente haya que
volver a tomar la misma variable. (esto es variable de ramificación recurrente)
tercero: en el paso de acotamiento (antes se tomaba como 1er cota. el valor de Z
solución óptima de la soltura de P.L. y se redondeaba hacia abajo pues los
coeficientes de Z son enteros y las variables deben ser enteras, Z no puede ser
decimal). Ahora algunas variables son enteras y otras no por lo tanto la cota es el
valor de Z sin redondear
cuarto: está en la prueba de “sondeo” que referimos con el número 3 en el apunte de
PE Binaria: ' La solución óptima para su “soltura de P.L.” es entera ' En este caso se
sondea si la solución resulta en valores enteros en aquellas variables restringidas a
que sean enteras. Por supuesto el valor de Z para esta solución resultará en un Z
incumbente: Z*. Si en el proceso se ha encontrado por otra rama otro valor Z*, en el
caso de máxima el mayor debe considerarse la cota.
Ejemplo
Libros
En este libro encontré la información relevante sobre programación entera binaria
Acotamiento y ramificación
En este libro aparece mi algoritmo dakin, anexo pantallazos en donde encontré la
información.
Bibliografía
Frederick S. Hillier & Gerald J. Lieberman, Introducción a la investigación de
operaciones, 9na Edición. Editorial Mcgraw-Hill, 2010. Pag 428, 464-465
Izar Landeta Juan Manuel, Fundamentos de Investigación de Operaciones para
Administración. Editorial Universidad Potosina, México 1996. Pag 116-117
