# data[].attributes.headline
Introduccion a la optimizacion con enteros

# data[].attributes.subject
Introduccion a la optimizacion con enteros

# data[].attributes.body
Un modelo de Progrmacion Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisiones toman valores restringidos a numeros enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programacion Lineal.
En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

# data[].attributes.headline
Tipos de modelos de Programación Lineal con Enteros

# data[].attributes.subject
Tipos de modelos de Programación Lineal con Enteros

# data[].attributes.body
Atendiendo al tipo de variables: Enteros puros: son aquellos en que todas las variables únicamente pueden tomar valores enteros. también se distinguen dentro de estos los problemas totalmente enteros como aquellos en que tanto las variables como todos los coeficientes que intervienen en el problema han de ser enteros. Mixtos: son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden tomar valores enteros. Binarios: las variables sólo pueden tomar los valores cero o uno.

# data[].attributes.attachment_link.title
Programación Lineal Entera - Solución Solver Excel

# data[].attributes.headline
Tipos de modelos de Programacion Lineal con Enteros

# data[].attributes.subject
Tipos de modelos de Programacion Lineal con Enteros

# data[].attributes.body
Atendiendo al criterio del tipo de problema:
Directo: Si el problema de decisión involucra variables enteras.
Codificado: Cuando se trata de un problema que contiene además de
aspectos cuantitativos, alguna consideración de tipo cualitativos, y por ello para tratar este tipo de aspectos se requiere el uso de variable enteras o binarias.
Transformado: Cuando el problema no incluye variables enteras, pero para ser tratado analíticamente requiere el uso de variable enteras artificiales.

# data[].attributes.headline
Interpretaciones gráficas de modelos de PLE

# data[].attributes.subject
Interpretaciones gráficas de modelos de PLE

# data[].attributes.body
Para resolver este modelo con un método gráfico, recomendamos tres pasos:
1. Encuentre el conjunto factible para la relajación de PL del modelo de PLE.
2. Identifique los puntos correspondientes a valores enteros dentro del conjunto
determinado en el paso 1.
3. Entre los puntos determinados en el paso 2, encuentre uno que optimice la
función objetivo.
Los dos primeros pasos han sido efectuados a través del método gráfico. La región
sombreada corresponde al conjunto factible para la relajación de PL.
1. En un modelo Max el VO de la relajación de PL siempre proporciona una cota
superior sobre el VO del modelo de PLE original. Agregar la restricción de enteros
puede perjudicar o dejar intacto el VO de la PL. En un modelo Max, perjudicar el
VO significa hacerlo más pequeño.
2. En un modelo Min, el VO de la relajación de PL siempre proporciona una cota
inferior sobre el VO del modelo de PLE original. Una vez más, agregar la restricción
sobre enteros puede perjudicar o dejar intacto el VO de la PL. En un modelo Min,
perjudicar el VO significa hacerlo más grande.

# data[].attributes.attachment_link.title
Ejemplo Método Gráfico en Programación Lineal

# data[].attributes.headline
El algoritmo de ramificación y acotamiento

# data[].attributes.subject
El algoritmo de ramificación y acotamiento

# data[].attributes.body
El método de ramificación y acotación comienza por resolver el
PLA, de modo que si la solución al PLA verifica las condiciones de
integridad, entonces también es la solución al problema entero, en caso contrario se comienza con la ramificación del problema. La ramificación consiste en dividir cada problema en dos nuevos
subproblemas, obtenidos mediante la imposición de restricciones
excluyentes que dividen el conjunto de oportunidades del problema original en dos partes, pero eliminando en ambas partes la solución no entera del problema original. Cuando en la solución al PLA una variable que ha de ser entera xi toma el valor xbi no entero, entonces se generan a partir de dicho valor dos restricciones xi ≤ [xbi] y xi ≥ [xbi]+1 (siendo [xbi] la parte entera por defecto de xbi), que añadidas cada uno por separado al problema original, da lugar a dos nuevos subproblemas.

# data[].attributes.attachment_link.readable_text
Plano de corte, ramificación y acotamiento

1. 1. PROGRAMACIÓN LINEAL ENTERA FCC BUAP Luis Alfredo Moctezuma 5/24/2016 1Programación lineal entera

2. 2. Introducción * PROGRAMACIÓN LINEAL ENTERA - Ramificación y acotamiento - Método de plano de corte 5/24/2016 Programación lineal entera 2

3. 3. Introducción * Algunas o todas las variables están restringidas a tener valores enteros (o discretos) - Personas necesarias para realizar una tarea * No existe un programa de cómputo para programas lineales enteros que pueda resolverlos en forma consistente O(2n) 5/24/2016 Programación lineal entera 3

4. 4. Introducción * Problema lineal entero - Puro * Todas las variables son enteras - Mixto * No todas las variables son enteras 5/24/2016 Programación lineal entera 4

5. 5. ALGORITMOS DE PROGRAMACIÓN ENTERA * En la estrategia de esos algoritmos intervienen tres pasos 1. Relajar el espacio de soluciones del programa lineal entero omitiendo la restricción entera en todas las variables enteras, y sustituyéndola con cualquier variable binaria y que tenga el intervalo continuo 0 ... y ... 1 5/24/2016 Programación lineal entera 5

6. 6. ALGORITMOS DE PROGRAMACIÓN ENTERA,~ 2. Resolver el programa lineal e identificar su óptimo continuo 3. Iniciar en el punto óptimo continuo e ir agregando restricciones especiales que modifiquen en forma iterativa el espacio de soluciones del programa lineal, en una forma que al final produzca un punto extremo que satisfaga los requisitos enteros 1. Método de ramificación y acotamiento 2. Método del plano cortante 5/24/2016 Programación lineal entera 6

7. 7. Algoritmo de ramificación y acotamiento(B&B) * Detecta en qué ramificación, las soluciones dadas ya no están siendo óptimas, para podar esa rama del árbol y no continuar malgastando recursos y procesos 5/24/2016 Programación lineal entera 7

8. 8. Algoritmo de ramificación y acotamiento, ejemplo Maximizar z = 5x1 + 4x2 Sujeto a x1+x2 ≤ 5 10x1+6x2 ≤ 45 x1,x2 enteros no negativos 5/24/2016 Programación lineal entera 8

9. 9. Algoritmo de ramificación y acotamiento, ejemplo,~ * Los puntos de red de la f i g u r a d e f i n e n e l espacio de soluciones del programa lineal entero. * E l p r o b l e m a l i n e a l asociado, el "0", se define eliminando las restricciones enteras. Su solución óptima es: 5/24/2016 Programación lineal entera 9

10. 10. Algoritmo de ramificación y acotamiento, ejemplo,~ * Como la solución óptima del programa lineal 0 no satisface los requisitos enteros, el algoritmo de ramificación y acotamiento modifica el espacio de soluciones de tal manera que al final se identifica el programa lineal entero óptimo * Primero se selecciona una de las variables enteras,cuyo valor óptimo en el programa 0 no sea entero 5/24/2016 Programación lineal entera 10

11. 11. Algoritmo de ramificación y acotamiento, ejemplo,~ * Si se selecciona x1=3.75 en forma arbitraria, la región 3<x1<4 del espacio de soluciones del programa 0 no contiene valores enteros de x1 y se puede eliminar * Eso equivale a reemplazar el programa lineal 0 original con dos nuevos programas lineales, el 1 y el 2 (PL1 y PL2): - Espacio de PL1 = Espacio de PL0 + (x1 ≤ 3) - Espacio de PL2 = Espacio de PL0 + (x1 ≥ 4) * x1 es la variable de ramificación 5/24/2016 Programación lineal entera 11

12. 12. Algoritmo de ramificación y acotamiento, ejemplo,~ * Se deben examinar ambos subproblemas. En forma arbitraria se examinará primero PL1,asociado con x1≤3 * Maximizar z = 5x1 + 4x2 x1 + x2 ≤ 5 10x1 + 6x2 ≤ 45 x1 ≤ 3 x1 , x2 ≥ 0 5/24/2016 Programación lineal entera 12

13. 13. Algoritmo de ramificación y acotamiento, ejemplo,~ 5/24/2016 Programación lineal entera 13

14. 14. Algoritmo de ramificación y acotamiento, ejemplo,~ * Esta solución satisface los requisitos de ser entero para x1 y x2 . Por consiguiente, se dice que PL1 está agotado. No puede producir una solución mejor del programa lineal entero z* = 23 es una cota inferior 5/24/2016 Programación lineal entera 14

15. 15. Algoritmo de ramificación y acotamiento, ejemplo,~ * Se examina el PL2. - Como la z* es 23.75 en el programa 0 y sucede que todos los coeficientes de la función objetivo son enteros, es imposible que el PL2 produzca una mejor solución entera. En consecuencia se descarta al PL2 y se llega a la conclusión que se ha agotado 5/24/2016 Programación lineal entera 15

16. 16. Algoritmo de ramificación y acotamiento, resumen * Suponiendo un problema de maximización, se establece una cota inferior inicial z=-∞ del valor objetivo óptimo del programa lineal entero. i=0 * Paso 1 - (Agotamiento/acotamiento). Se selecciona PLi, el siguiente subproblema a examinar. Se resuelve PLi y se trata de agotarlo, usando una de las tres siguientes condiciones. * a) El valor de z óptimo del PLi no puede producir un valor objetivo mejor que la cota inferior actual * b) PLi produce una solución entera factible mejor, que la cota inferior actual * c) PLi no tiene solución factible 5/24/2016 Programación lineal entera 16

17. 17. Algoritmo de ramificación y acotamiento, resumen * Se presentarán dos casos: a) Si PLi está agotado y se encuentra una solución mejor, actualizar la cota inferior. Si todos los subproblemas se han agotado, detenerse; el programa lineal entero óptimo corresponde a la cota inferior actual, si la hay. En caso contrario, i=i + 1 y repetir el paso 1. b) Si PLi no está agotado, seguir en el paso 2, para ramificar 5/24/2016 Programación lineal entera 17

18. 18. Algoritmo de ramificación y acotamiento, resumen * Paso 2. (Ramificación.) Seleccionar uno de los valores enteros, xj , cuyo valor óptimo x*j en la solución del PLi no sea entero. Eliminar la región (en la que [v] define el mayor entero ≤ v) creando dos subproblemas lineales que corresponden a i =i +1 e ir al paso 1 5/24/2016 Programación lineal entera 18

19. 19. Algoritmo de ramificación y acotamiento, resumen 5/24/2016 Programación lineal entera 19

20. 20. Algoritmo de plano de corte * Como en el algoritmo de B&B, el del plano cortante también se inicia en la solución óptima del programa lineal continuo * Al espacio de soluciones se agregan restricciones especiales, llamadas cortes, en una forma que produzca un punto extremo entero * Requisitos - Los cortes agregados no deben eliminar alguno de los puntos enteros factibles originales, pero deben pasar por al menos un punto entero, factible o no factible 5/24/2016 Programación lineal entera 20

21. 21. Algoritmo de plano de corte * En el siguiente ejemplo se demostrará cómo se usan los cortes en forma gráfica para producir una solución entera y después implementar algebraicamente esta idea 5/24/2016 Programación lineal entera 21

22. 22. Algoritmo de plano de corte, ejemplo * Max Z= 7x1 + 10x2 s.a -x1 + 3x2 ≤ 6 7x1 + x2 ≤ 35 x1,x2 ≥0 y enteras Este algoritmo modifica el espacio de soluciones agregando cortes que producen un punto extremo entero óptimo 5/24/2016 Programación lineal entera 22

23. 23. Algoritmo de plano de corte, ejemplo,~ * Se parte del óptimo del programa lineal continuo, z= 66.5 x1=4.5 x2=3.5 * Se agrega el corte I, que produce la solución lineal óptima continua, z=62 x1=4.57143 x2= 3 5/24/2016 Programación lineal entera 23

24. 24. Algoritmo de plano de corte, ejemplo,~ * Se agrega el corte II, que junto con el corte I y las restricciones originales, llega al óptimo del programa lineal, z= 58 x1=4 x2=3 5/24/2016 Programación lineal entera 24

25. 25. Algoritmo de plano de corte, ejemplo,~ * La cantidad de cortes es independiente del tamaño del problema - aunque finita, en el sentido que un problema con una cantidad pequeña de variables y restricciones puede necesitar más cortes que un problema mayor * En este caso sólo fue casualidad que un problema con 2 variables necesitara de exactamente 2 cortes para llegar a la solución entera óptima 5/24/2016 Programación lineal entera 25

26. 26. Algoritmo de plano de corte, ejemplo,~ * Resuelto algebraicamente 5/24/2016 Programación lineal entera 26

27. 27. Algoritmo de plano de corte, ejemplo,~ * Se sacan todos los coeficientes de la ecuación como factor común, con un valor entero y un componente fraccionario, siempre y cuando el componente fraccionario que resulte sea estrictamente positivo 5/24/2016 Programación lineal entera 27

28. 28. Algoritmo de plano de corte, ejemplo,~ * Se sacan todos los coeficientes de la ecuación como factor común, con un valor entero y un componente fraccionario, siempre y cuando el componente fraccionario que resulte sea estrictamente positivo 5/24/2016 Programación lineal entera 28

29. 29. Algoritmo de plano de corte, ejemplo,~ * Como x3 y x4 son no negativas, y todas las fracciones originalmente son estrictamente positivas, el lado derecho debe satisfacer la siguiente desigualdad: * Ahora, como z + 2x3+ 1x4 - 66, el lado izquierdo, por construcción tiene valor entero, el lado derecho, tambien debe ser entero - Es el corte que se desea, y representa una condición necesaria para obtener una solución entera - También se le llama corte fraccionario, porque todos sus coeficientes son fracciones 5/24/2016 Programación lineal entera 29

30. 30. Algoritmo de plano de corte, ejemplo,~ * Cómo se pueden obtener los cortes de las ecuaciones de restricción * Corte asociado 5/24/2016 Programación lineal entera 30

31. 31. Algoritmo de plano de corte, ejemplo,~ * Si en forma arbitraria se selecciona el corte generado a partir del renglón x2, se puede escribir como sigue, en forma de ecuación: - La tabla es óptima, pero no factible. Aplicar el método dual símplex para recuperar la factibilidad 5/24/2016 Programación lineal entera 31

32. 32. Algoritmo de plano de corte, ejemplo,~ * La última solución todavía no es entera en x1 y x3. Se selecciona a x1, en forma arbitraria, como el siguiente renglón de fuente; esto es * Corte asociado 5/24/2016 Programación lineal entera 32

33. 33. Algoritmo de plano de corte, ejemplo,~ * Con el método símplex dual se obtiene el siguiente cuadro: 5/24/2016 Programación lineal entera 33

34. 34. Algoritmo de plano de corte, ejemplo,~ * La solución óptima es x1=4, x2=3 z=58 - Todas las variables básicas son enteras 5/24/2016 Programación lineal entera 34

35. 35. Referencias * Hamdy A. Taha. (2004). Investigación de operaciones. México: Pearson. * * Código 5/24/2016 Programación lineal entera 35

# data[].attributes.attachment_link.description
Plano de corte, ramificación y acotamiento 1. PROGRAMACIÓN LINEAL ENTERA FCC BUAP Luis Alfredo Moctezuma 5/24/2016 1Programación lineal entera 2. Introducción * PROGRAMACIÓN LINEAL ENTERA - Ramificación y acotamiento - Método de plano de corte 5/24/2016 Programación lineal entera 2 3.

# data[].attributes.body
Existen dos razones principales para usar variables enteras cuando se modelan problemas como programas lineales:

1. Las variables enteras representan cantidades que solo pueden ser enteras. Por ejemplo, no es posible construir 3.7 vehículos.

2. Las variables enteras representan decisiones, por lo que deberían tomar solo los valores 0 ó 1.

Estas consideraciones ocurren frecuentemente en la práctica y por consiguiente la programación lineal en enteros puede ser usada en muchas áreas de aplicación, algunas de las cuales son brevemente descritas a continuación.

Plan de producción

La PLEM tiene muchas aplicaciones en la producción industrial, incluyendo modelado trabajo-tienda. El plan de producción en la agricultura implica determinar el rendimiento de la producción para varios cultivos que pueden compartir recursos (e.g., tierra, labor, fondo para fertilizador de semillas, etc.). Un objetivo posible es maximizar la producción total, sin exceder los recursos disponibles. En algunos casos, esto puede ser expresado en términos de un programa lineal, pero las variables deben ser restringidas a los enteros.

# data[].attributes.body
Planificación

Estos problemas involucran planificación de vehículos y servicios en redes de transportación. Por ejemplo, un problema puede implicar asignar autobuses o metros a rutas individuales para que un horario sea cumplido, y también equiparlos con chóferes. Aquí las variables de decisión binarias indican dónde un autobús o metro es asignado a una ruta y dónde un chófer es asignado a un tren o metro en particular.

Redes de telecomunicaciones

El objetivo de estos problemas es diseñar una red de líneas para instalar por lo que un conjunto predefinido de requerimientos de comunicación es conocido y el costo total de la red es minimal. Esto requiere optimizar la topología de la red junto con la configuración de capacidades de las diferentes líneas. En muchos casos, las capacidades están restringidas a cantidades enteras. Usualmente existen, dependiendo de la tecnología usada, restricciones adicionales que pueden ser modeladas como desigualdades lineales con variables enteras o binarias.

Redes celulares
La tarea de planificar frecuentemente en redes de teléfonos GSM implica distribuir frecuencias disponibles a través de las antenas para que los usuarios puedan ser servidos y la interferencia sea minimizada entre las antenas.​ Este problema puede ser formulado como un programa lineal en enteros en el cual las variables binarias indican donde una frecuencia es asignada a una antena.