GRUPO 3

Vista previa del material en texto

PROGAMACIÓN ENTERA
Docente: 	 BENAVIDES MIRANDA, MARIA ADELINA
Curso:	 INVESTIGACION DE OPERACIONES II
Ciclo:	 V
Turno/ Sección: M/A
INTRUDUCCIÓN:
La programación entera es una forma práctica de toma decisiones generales puesto trabaja con las variables para que tengan sentido de interpretación lógico – real. Algunos ejemplos que mencionar serian el control de personas, vehículos y maquinas ya que estos estarán relacionados al proceso de cada área en específico de la empresa. Ya entrando al modelo de implementación y las diversas nomenclaturas del programa PEM y PEB los cuales el primero hace seguimiento de los conocimientos que ya se tienen en programación lineal de los capítulos y cursos anteriores por lo tanto la segunda profundiza un poco más donde es una forma de toma de decisiones directa a preguntas como: ¿se debe invertir en cierto campo productivo?, ¿debe se localizarle un establecimiento en cierta zona geográfica?, etc. 
PROGRAMACIÓN ENTERA BINARIA (PEB):
Las aplicaciones de esta herramienta son de suma importancia en la toma de decisiones básicas puesto los modelos de resultados me arrojan la afirmación o negación de mi cuestionamiento en el acto de un proceso. Al ser respuestas mutuamente excluyentes se tendrá que considerar, recopilar y relacionar bien las restricciones es dicha operación. Hay casos que las conclusiones de tipo sí carecen de contingencia pues esta correlacionado con las respuestas anteriores. Por ejemplo, se dice que una decisión es contingente respecto a otra si se permite que sea si sólo si la otra es sí. Esto se entiende que es una forma secuencial o en cadena es decir si hay una que da negativa en respuesta ya no permitiría una buena correlación en resultados finales.
OPCIONES DE SOFTWARE PARA RESOLVER:
Los softwares usados para resolver estos modelos presentados son muy diversos algunos son de conocimiento general como el Solver encontrado en Excel o también siendo más curiosos el Lindo/Lingo. Con los algoritmos ya puestos en escena, nos damos cuenta de que la resolución de la forma binaria es mucho más útil que la pura o mixta ya que el rango de cobertura es mucho más amplio en la binaria. Excel es la herramienta recomendad más disponible a todos los interesados a implementar este algoritmo entero. 
ALGUNAS APLICACIONES PEB:
Análisis de inversión:
Como se puede analizar es muy distinto la opción de saber cuanto podremos invertir por el método lineal a como nos resultara por PE ósea acá ya vemos lo que es un montón fijado para dicho proceso y sí ello será factible o no (1 = sí, 0 = no).
Elección del sitio:
Con estos análisis veremos la referencia de la mejor elección de zona geográfica y demográfica con las variables de decisión (1 = sí, 0 = no).
Diseño de una red de producción y distribución:
Por lo ya mencionado en la prevista anterior ahora veremos si el sitio seleccionado es de un rango muy amplio de cobertura geográfica, siendo esto confirmado entonces se verá el tema de red de producción (o sucursales de dicha servís) y para la mejora en la distribución del transporte de envió o entrega del producto terminado, relacionado con los costos que se tienen del mismo.
Tener presente siguientes ítems:
. ¿Debe cierta planta permanecer abierta?
. ¿Debe seleccionarse cierto sitio para una nueva planta?
. ¿Debe cierto centro de distribución permanecer abierto?
. ¿Debe cierto sitio elegirse para instalar un nuevo centro de distribución?
Despacho de envíos:
Con las decisiones ya tomadas del dónde y la capacidad de producción o atención con la mayor ganancia posible ahora nos sumergimos un poco más el como realizarlo ya que algunas decisiones en esta área también son binarias. Ya obtenido los datos mencionados ahora nos enfocaremos en la ruta de entrega o la secuencia de clientes atendidos, ya que esta decisión poniendo un ejemplo fugaz seria la de camioneros seleccionando la ruta con menos tráfico, mas cercana a la residencia de los clientes o tiendas ósea ya véase que parece algo irrelevante y cotidiano, pero se da a conocer que se puede mejorar para mayor ganancia empresarial.
Programación de actividades interrelacionadas:
Como profesionales debemos entender que algunas decisiones se toman de manera conjunta con varios factores los cuales nos llevan a la interrelación de estas, por eso el de la programación que se realiza para apoyo de dichas decisiones. El inicio de una producción en especifico suena algo simple pero cuando se dice maximizar su potencial es donde entramos nosotros a poner en praxis lo aprendido y quitar las dudas semejantes como ¿Cuándo deben comercializarse los productos? O también ¿Cuándo deben realizarse las inversiones del capital para aumentar el volumen de producción?, etc. 
Aplicaciones a líneas aéreas:
Por todo lo explicado pondremos un ejemplo de apoyo, las líneas aéreas. 
	Uno de los problemas a mencionar será la asignación de flota: Es la relación de tipo de avión con la ruta tomada ósea el tema va que en el tipo de avión veremos una capacidad limita variable pues es por modelos de tamaño de avión, su velocidad en aires y demás factores complementarios, entonces si tengo el dónde viajaran me toca el cómo ósea la ruta de selección por preferencia para ganancia. Entonces se podría plantear una pregunta (qué nos daría la respuesta binaria) dándole forma cómo la siguiente: ¿Deberías asignarse el avión (con características específicas) en tal ruta en particular para tal destino (en común de los clientes)? 
La otra sería el problema de programación de tripulaciones: Con lo visto ya anteriormente acabemos una toma de decisiones similar, pero ahora decidiremos la ruta de vuelo (que vendría a ser lo dicho en el punto anterior) conqué tripulación (vendremos a llamar el personal en vuelo: copilotos, asistente, encargos y etc.) vendríamos a distribuir en vuelo. Sí entonces se da a entender que buscaremos la forma más factible tomando una decisión binaria en dicho vuelo comercial. 
ALGUNOS EJEMPLOS DE FORMULACIÓN
Ejemplo 1: Elecciones cuando las variables de decisión son continuas
La división de investigación y desarrollo de la GOOD PRODUCTS COMPANY ha desarrollado tres nuevos productos posibles. Sin embargo, para evitar una diversificación excesiva de la línea de productos de la compañía, la administración ha impuesto las siguientes limitaciones.
Restricción 1: De los tres nuevos productos posibles, deben escogerse, como máximo, sólo dos de ellos.
Se dispone de dos plantas que pueden fabricar los productos elegidos. Por razones administrativas, la administración impuso una segunda restricción a este respecto.
Restricción 2: Sólo una de las dos plantas debe asignarse para la producción de los nuevos productos. 
En esencia, el costo unitario de producción de cada producto sería el mismo en las dos plantas. Sin embargo, por diferencias en las instalaciones, el número de horas de producción por unidad de cada producto puede diferir entre ellas. Estos datos se dan en la tabla, junto con otra información relevante, que incluye las estimaciones del departamento de mercadotecnia sobre el número máximo de unidades de cada producto que podrían venderse a la semana. El objetivo es seleccionar los productos, la planta y las tasas de producción de los bienes elegidos de manera que se maximice la ganancia total.
Datos del ejemplo 1 
En particular, sean x1, x2 y x3 las tasas de producción de los respectivos productos, el modelo sería
Maximizar Z = 5x1 + 7x2 + 3x3,
Sujeta a: 3x1 + 4x2 + 2x3 ≤ 30
 4x1 + 6x2 + 2x3 ≤ 40
x1 ≤ 7
x2 ≤ 5
x3 ≤ 9
y, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
La limitación 1 necesita que se agregue al modelo la siguiente restricción:
El número de variables de decisión estrictamente positivas (x1, x2, x3) debe ser ≤ 2.
Si las variables de decisión fueran binarias, entonces la restricción se expresaría como x1 + x2+ x3 ≤ 2
La limitación 2 necesita que se sustituyan las dos primeras restricciones funcionales 
(3x1 + 4x2 + 2x3 ≤ 30 y 4x1 + 6x2 + 2x3 ≤ 40) por la restricción
Ya sea 3x1 + 4x2 + 2x3 ≤ 30 o bien 4x1 + 6x2 + 2x3 ≤ 40
Formulación con variables binarias auxiliares. 
Para manejar la limitación 1, se introducen tres variables binarias auxiliares (y1, y2, y3) con la interpretación
Para j = 1, 2, 3. Para incluir esta interpretación en el modelo con la ayuda de M (un número positivo muy grande), se agregan las restricciones
x1 ≤ My1
x2 ≤ My2
x3 ≤ My3
y1 + y2 + y3 ≤ 2
yj es binaria,	para j = 1, 2, 3.
La restricción de una o la otra y las restricciones de no negatividad proporcionan una región acotada para las variables de decisión, con lo que cada xj ≤ M en toda la región. Por tanto, para cada xj ≤ Myj la restricción yj =1 permite que xj tome cualquier valor en la región factible, mientras que yj = 0 fuerza a que xj = 0. 
Para manejar la limitación 2 se introduce otra variable binaria auxiliar y4 con la interpretación.
Esta interpretación se toma en cuenta al agregar las restricciones,
3x1 + 4x2 + 2x3 ≤ 30 + My4
4x1 + 6x2 + 2x3 ≤ 40 + M (1 — y4)
y4 es binaria.
El examen cuidadoso de las restricciones en este ejemplo revela que el valor factible mínimo de M es M = 9.
En consecuencia, después de mover todas las variables al lado izquierdo de las restricciones, el modelo completo es
Maximizar	Z = 5x1 + 7x2 + 3x3,
Sujeta a: x1 ≤ 7
x2 ≤ 5
x3 ≤ 9
x1 - My1 ≤ 0
x2 - My2 ≤ 0
x3 - My3 ≤ 0
y1 + y2 + y3 ≤ 2
3x1 + 4x2 + 2x3 - My4 ≤ 30
4x1 + 6x2 + 2x3 + My4 ≤ 40 + M
y x1 ≤ 0, x2 ≤ 0, x3 ≤ 0
yj es binaria, para j = 1, 2, 3, 4.
Éste es ahora un modelo de PEM, con tres variables (las xj) que no tienen que ser enteras y cuatro variables binarias, por lo cual es posible usar un algoritmo de PEM para resolverlo. Luego de ello (después de sustituir M por un valor numérico grande), la solución óptima es y1 = 1, y2 = 0, y3 = 1, y4 = 1, x1 = 5 , x2 = 0 y x3 = 9; es decir, se eligen los productos 1 y 3 para producción, se elige la planta 2 y las tasas de producción deben ser 5 unidades por semana del producto 1 y 9 unidades por semana del producto 3. La ganancia total resultante es de $54 500 semanales.
EJEMPLO 2: Cobertura de todas las características
SOUTHWESTERN AIRWAYS necesita asignar sus tripulaciones para cubrir todos sus vuelos programados. Se estudiará el problema de asignar tres tripulaciones con base en San Francisco (SF) a los vuelos enumerados en la tabla. Las otras 12 columnas muestran 12 secuencias de vuelos factibles de una tripulación. (Los números en cada columna indican el orden de los vuelos.) Es necesario elegir tres de estas secuencias (una por tripulación) de tal manera que se cubran todos los vuelos. (Se permite tener más de una tripulación en un vuelo, en el cual los miembros de la tripulación adicional volarían como pasajeros, pero los contratos colectivos de trabajo requieren que se pague el tiempo de la tripulación adicional como si estuviera en horario de trabajo.) El costo de asignar una tripulación a una secuencia de vuelos específica se muestra (en miles de dólares) en el renglón inferior de la tabla. El objetivo es minimizar el costo total de asignar las tres tripulaciones de manera que cubran todos los vuelos.
Datos del ejemplo 2 
Formulación con variables binarias. 
Con 12 secuencias factibles de vuelos, se deben enfrentar 12 decisiones sí o no:
¿Debe asignarse la secuencia j a la tripulación? 
(j = 1, 2, . . . , 12)
Por tanto, se usan 12 variables binarias para representar las respectivas decisiones:
Sujeta a
x1 + x4 + x7 + x10 ≥ 1 (SF a LA)
x2 + x5 + x8 + x11 ≥ 1 (SF a Denver)
x3 + x6 + x9 + x12 ≥ 1 (SF a Seattle)
x4 + x7 + x9 + x10 + x12 ≥ 1 (LA a Chicago)
x1 + x6 + x10 + x11 ≥ 1 (LA a SF)
x4 + x5 + x9 ≥ 1 (Chicago a Denver)
x7 + x8 + x10 + x11 + x12 ≥ 1 (Chicago a Seattle)
x2 + x4 + x5 + x9 ≥ 1 (Denver a SF)
x5 + x8 + x11 ≥ 1 (Denver a Chicago)
x3 + x7 + x8 + x12 ≥ 1 (Seattle a SF)
x6 + x9 + x10 + x11 + x12 ≥ 1 (Seattle a LA)
Y xj es binaria, para j = 1, 2, . . . , 12.
x6 + x9 + x10 + x11 + x12 ≥ 1
Con restricciones similares para los otros 10 vuelos, el modelo completo de PEB es
Minimizar:	
Z = 2x1 + 3x2 + 4x3 + 6x4 + 7x5 + 5x6 + 7x7 + 8x8 + 9x9 + 9x10 + 8x11 + 9x12
Una solución óptima para este modelo de PEB es
X3 = 1 (asignar la secuencia 3 a una tripulación)
X4 = 1 (asignar la secuencia 4 a una tripulación)
X11 = 1 (asignar la secuencia 11 a una tripulación)
y todas las demás xj = 0, con un costo total de $18 000 
(otra solución óptima es x1 = 1, x5 = 1, x12 = 1, y todas las demás xj = 0).
Nota:
De manera estricta, un problema de cobertura de conjunto no incluye otras restricciones funcionales como la última del ejemplo de programación de tripulaciones. Algunas veces se supone que todos los coeficientes de la función objetivo que se quiere minimizar son iguales a uno, y entonces cuando este supuesto no se cumple se usa el nombre de problema de cobertura de conjunto ponderada.
ALGUNAS PERSPECTIVAS ACERCA DE LA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN ENTERA
Existen dos falacias en esta línea de razonamiento. Una falacia es que tener un número finito de soluciones factibles asegura que el problema se puede resolver. Los números finitos pueden ser astronómicamente grandes. Por ejemplo, considere el caso sencillo de problemas de PEB. Si se tienen n variables, existen 2n soluciones que considerar (algunas de las cuales se pueden descartar por violar las restricciones funcionales). En consecuencia, cada vez que n aumenta en 1, el número de soluciones se duplica. Este patrón se llama crecimiento exponencial de la dificultad del problema. 
La segunda falacia es que si se eliminan algunas soluciones factibles (las no enteras) de un problema de programación lineal, será más fácil resolverlo. Por el contrario, sólo cuando todas estas soluciones factibles están ahí, se puede garantizar que existe una solución factible en el vértice (FEV) [y por ende la solución básica factible (BF) correspondiente] que es óptima para el problema completo. 
ALGUNAS PERSPECTIVAS ACERCA DE LA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN ENTERA
El problema correspondiente de programación lineal se conoce como su relajamiento de PL. .
LA TECNICA DEL REDONDEO: Este enfoque puede ser adecuado en algunas aplicaciones, en especial si los valores de las variables son tan grandes que el redondeo introduce un error muy pequeño; sin embargo, debe tenerse cuidado al poner en práctica este procedimiento, pues se corren dos riesgos.
Una desventaja es que una solución óptima de programación lineal no necesariamente es factible después de redondearla. Con frecuencia es difícil decidir en qué sentido redondear para conservar la factibilidad. Incluso, podría ser necesario cambiar el valor de algunas variables en una o más unidades después de redondear.
Para ilustrar este método, considere el siguiente problema:
Ejemplo de un problema de PE donde la solución óptima del relajamiento de PL no se puede redondear de ninguna manera que conserve la factibilidad.
Como se muestra en la figura, la solución óptima para el relajamiento de PL es x1 = 1, x2 = 2, pero es imposible redondear la variable no entera x1 a 1 o 2 (o a cualquier otro entero) y conservar la factibilidad. Esta factibilidad sólo se puede conservar si también se cambia el valor entero de x2. Es fácil imaginar la complejidad a la que puede llevar este tipo de dificultades cuando se tiene en frente decenas o cientos de restricciones y variables.
Aun cuando una solución óptima para el relajamiento de PL se pueda redondear con éxito, todavía queda otra dificultad. No existe garantía de que esta solución redondeada sea la solución óptima de programación entera. En realidad, puede ser que se encuentre muy lejos del óptimo en términos del valor de la función objetivo. 
El siguiente problema ejemplifica este hecho:
Como sólo setienen dos variables de decisión, este problema se puede graficar como se muestra en la figura siguiente. Se puede usar esta gráfica o el método símplex para encontrar que la solución óptima del relajamiento de PL es x1 = 2, x2 = , con Z = 11. Si no se dispusiera de una solución gráfica óptima (que sería el caso con más variables de decisión), la variable con el valor no entero x2 = se redondearía en la dirección factible a x2 = 1. La solución entera que se obtendría sería x1 = 2, x2 = 1, de donde se obtiene Z = 7. Observe que esta solución está muy lejos de la óptima (x1, x2) = (0, 2) donde Z = 10.
Ejemplo de un problema de PE donde la solución óptima del relajamiento de PL no se puede redondear de ninguna manera que conserve la factibilidad.
EJERCICIO
Una joven pareja, Eve y Steven, quiere 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 el tiempo total para hacer estas tareas sea 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:
a) Formule un modelo de PEB para este problema.
1. Definir variables:
Variables binarias:
 0, no hace el deber 
 xj
 1, si hace el deber 
j= 1,2,3,….,8
x1 = ¿Eve compra?
x2 = ¿Steven compra?
x3 = ¿Eve cocina?
x4 = ¿Steven cocina?
x5 = ¿Eve lava los platos?
x6 = ¿Steven lava los platos?
x7 = ¿Eve lava ropa?
x8 = ¿Steven lava ropa?
 
2. Definir función objetivo:
Minimizar: 
T = 4.5x1+4.9x2+7.8x3+7.2x4+3.6x5+4.3x6+2.9x7+3.1x8
3. Fijar restricciones:
x1+x3+x5+x7 = 2
x2+x4+x6+x8 = 2
x1+x2 = 1
x3+x4 = 1
x5+x6 = 1
x7+x8 = 1
x1,x2,x3,x4,x5,x6,x7,x8  {0,1}
TÉCNICA DE RAMIFICACIÓN Y ACOTAMIENTO Y SUS APLICACIONES A LA PROGRAMACIÓN ENTERA BINARIA
Esta técnica y algunas de sus variantes se han aplicado con cierto éxito a diversos problemas de investigación de operaciones, pero es más conocida por sus aplicaciones a los problemas de programación entera.
Como es demasiado complicado resolver en forma directa el problema original “grande”, se divide en subproblemas cada vez más pequeños hasta que éstos se puedan vencer. La división (ramificación) se hace mediante una partición del conjunto completo de soluciones factibles en subconjuntos más pequeños. En parte, la conquista (sondeo) se hace mediante el acotamiento de la mejor solución del subconjunto para después descartar los subconjuntos cuya cota indique que no es posible que contenga una solución óptima para el problema original.
A continuación, se describirá cada uno de estos pasos básicos 
Ramificación
Cuando se manejan variables binarias, la forma más sencilla de partir el conjunto de soluciones factibles es fijar el valor de una variable (por ejemplo, x1) en x1 = 0 para un subconjunto y en x1 = 1 para el otro. Al hacer esto en el ejemplo prototipo, el problema completo queda dividido en dos subproblemas más pequeños, como se presentan a continuación.
La variable que se utiliza en la ramificación de una iteración cuando se asignan valores a la variable (como x1) se llama variable de ramificación. (Una parte importante de algunos algoritmos de ramificación y acotamiento son ciertos métodos elaborados para seleccionar la variable de ramificación, pero, por simplicidad, en esta sección se seleccionan en su orden natural: x1, x2, . . . , xn.
que uno de estos subproblemas se puede vencer (sondear) de inmediato, mientras que el otro requiere una nueva división en subproblemas más pequeños si se establece x2 = 0 o x2 = 1. 
NOTA:
En otros problemas de PE, donde las variables enteras pueden tener más de dos valores posibles, la ramificación se puede hacer a través de establecer la variable de ramificación igual a cada valor, lo que crea más de dos subproblemas. Otro buen enfoque es especificar el intervalo de valores (por ejemplo, xj<= 2 o xj >= 3) para la variable de ramificación en cada nuevo subproblema.
Acotamiento
Ahora es necesario obtener, para cada subproblema, una cota que muestre el nivel de precisión de su mejor solución factible.
Casi siempre, el relajamiento de un problema se obtiene eliminando (“relajando”) un conjunto de restricciones que dificultan obtener una solución.
En consecuencia, el relajamiento que más se usa es el relajamiento de PL que elimina este conjunto de restricciones.
el relajamiento que más se usa es el relajamiento de PL que elimina este conjunto de restricciones. Su relajamiento de PL se obtiene mediante la sustitución del último renglón del modelo (xj es binaria, para j = 1, 2, 3, 4) por la siguiente nueva (relajada) versión de su restricción
Usando el método símplex para resolver con rapidez su relajación PL que se obtiene de su solución óptima.
Por tanto, Z <= 16 1/2 para todas las soluciones factibles del problema original de PEB (puesto que estas soluciones son un subconjunto de las soluciones factibles del relajamiento de PL). En realidad, como se indica en el resumen del algoritmo, esta cota de 16 1/2 se puede redondear a 16, porque todos los coeficientes de la función objetivo son enteros y, por ende, deben dar un valor entero de Z.
CONTINUACION DEL METODO DE ACOTAMIENTO
Ahora se obtendrá, de la misma manera, las cotas de los subproblemas. En el subproblema 1, donde x1 = 0, puede expresarse de manera apropiada en su relajación PL mediante la suma de la restricción que x1 <=0 puesto que cuando se combinan con la restricción actual 0 <= x1 <= 1 obliga a que x1 = 0. 
De manera similar, si se fija x1 = 1 en el subproblema 2 nos lleva a sumar la restricción x1 >= 1 para su relajamiento de PL. Aplicando el método simplex obtenemos las soluciones óptimas que se muestran en seguida de estos relajamientos de PL
De manera similar, si se fija x1 = 1 en el subproblema 2 nos lleva a sumar la restricción x1 >= 1 para su relajamiento de PL. Aplicando el método simplex obtenemos las soluciones óptimas que se muestran en seguida de estos relajamientos de PL
 Las cotas que se obtienen son, entonces
 Cota del subproblema 1: Z <= 9, 
 Cota del subproblema 2: Z <= 16. 
Sondeo
PRIMERA FORMA
Un subproblema se puede sondear y, por tanto, ya no tomarse en cuenta, en las tres formas que se describen a continuación.
Una forma se ilustra con los resultados del subproblema 1 que se dieron en el nodo x1 = 0, Observe que la solución óptima (única) de este relajamiento de PL, (x1, x2, x3, x4) = (0, 1, 0, 1), es una solución entera. En consecuencia, esta solución debe ser también la solución óptima del subproblema 1, que debe guardarse como la primera solución incumbente o de apoyo.
de manera que en este punto Z* = 9. Como esta solución se guarda, no hay razón para seguir considerando el subproblema 1 y ramificar el nodo x1 = 0
SEGUNDA FORMA
Los resultados anteriores sugieren una segunda prueba de sondeo importante. Como Z* = 9, Establecido en forma general, un subproblema se sondea siempre que su Cota <= Z*. 
TERCERA FORMA
La tercera forma de sondeo es bastante directa. Si el método símplex encuentra que el relajamiento de PL de un subproblema no tiene soluciones factibles, entonces el subproblema en sí no debe tener soluciones factibles, de forma que puede eliminarse (sondearse).
ALGORITMO DE RAMIFICACIÓN Y ACOTAMIENTO PARA PROGRAMACIÓN ENTERA MIXTA
el problema general de programación entera mixta, PEM, donde algunas variables (por ejemplo, I de ellas) están restringidas a valores enteros (pero no necesariamente sólo 0 y 1), y el resto son variables continuas comunes. Por conveniencia en la notación, estas variables se ordenarán de manera que las primeras I de ellas sean variables con restricción de enteros. 
PEM
(Cuando I = n, este problema se convierte en uno de PE pura.) Se describirá un algoritmo básico de ramificación y acotamiento para resolver este problema que, un poco más elaborado, ha proporcionado el enfoque estándar a la PEM. 
La estructura de este algoritmo es bastante parecidaa la del algoritmo de PEB que se presentó en la sección anterior. De nuevo la solución de un relajamiento de PL proporciona la base tanto para el paso de acotamiento como para el de sondeo.
se necesitan cuatro cambios al algoritmo de PEB para manejar la generalización de variables enteras binarias generales y de PE pura a PE mixta.
Un cambio involucra la elección de la variable de ramificación. Antes se elegía de manera automática la siguiente variable en el orden natural (x1, x2, . . . , xn). Ahora, las únicas variables que se toman en cuenta son las variables con restricción de enteros que tienen un valor no entero en la solución óptima del relajamiento de PL para el subproblema actual.
El segundo cambio se refiere a los valores asignados a la variable de ramificación para crear los nuevos subproblemas. Ahora, la variable general con restricción de entera puede tener un número grande de valores enteros posibles, y sería ineficiente crear y analizar muchos subproblemas mediante la determinación de cada valor entero de la variable.
Pasos
1. Ramificación: Entre los subproblemas restantes (no sondeados), se selecciona el de creación más reciente. (Los empates se rompen con la cota más grande.) Entre las variables restringidas a enteros, que tienen valores no enteros en la solución óptima del relajamiento de PL del subproblema, se elige la primera en el orden natural como la variable de ramificación. Si xj es esta variable y xj * su valor en esta solución se debe ramificar desde el nodo del subproblema para crear dos nuevos subproblemas luego de agregar las restricciones respectivas 
2. Acotamiento: Se obtiene la cota de cada subproblema si se aplica el método símplex (o el método símplex dual si se reoptimiza) al relajamiento de PL y se utiliza el valor de Z para la solución óptima resultante.
3. Sondeo: Se aplican las pruebas de sondeo que se presentan a continuación a cada nuevo subproblema y se descartan aquellos que quedan sondeados por cualquiera de las pruebas.
ENFOQUE DE RAMIFICACIÓN Y CORTE PARA RESOLVER PROBLEMAS DE PEB pura
A finales de la década de 1960 y principios de la de 1970 hubo un cambio grande en el desarrollo y refinamiento del enfoque de ramificación y acotación. Más tarde, a mediados de la década de 1980, se publicaron un par de artículos innovadores, como el de Johnson et al. (1985), Hoffman (1991). El artículo de 1985 suponía un refinamiento del algoritmo presentado por Crowder (1983), que ganó el galardón Lancaster Prize otorgado por la Operations Research Society of America.
Técnicas de resolución de problemas de PEB pura
Preprocesado automático del problema
Generación de planos de corte
Técnicas de ramificación y acotación
Preprocesado automático del problema de PEB pura
Incluye una “inspección por computadora” de la formulación del problema de PE que proporciona el usuario.
Se clasifica en tres categorías:
Fijación de variables
Identificar las variables que pueden fijarse en uno de sus dos valores (0,1).
Eliminación de restricciones redundantes
Identificar y eliminar restricciones redundantes.
Estrechamiento de restricciones
Estrechar algunas restricciones de manera que se reduzca la región factible sin eliminar soluciones factibles. 
Preprocesado automático del problema de PEB pura
Fijación de variables:
El principio general para fijar variables es:
 Si el valor de una variable no puede satisfacer cierta restricción, aun cuando las otras variables sean iguales a sus mejores valores que tratan de satisfacer la restricción, entonces esa variable debe fijarse en el otro valor.
 
 
Ejemplo 1:
 
3x1  2 
 x1  0, puesto que 3(1) > 2.
3x1  x2  2 
5x1 + x2  2x3  2
 x1  0, puesto que 3(1)  1(0) > 2.
 x1  0, puesto que 5(1)  1(0)  2(1) > 2.
con el coeficiente positivo mayor, y si la suma de ese coeficiente y cualesquiera coeficientes negativos excede la cantidad del lado derecho, entonces esa variable debe fijarse en 0. Este procedimiento se puede repetir con las demás variables.
Para cualquier restricción 
Primero identificamos la variable
Preprocesado automático del problema de PEB pura
Ejemplo 2:
3x1  2 
 
 x1  1, puesto que 3(0) < 2
3x1  x2  2 
 x1  1, puesto que 3(0)  1(1) < 2
3x1 + x2  2x3  2 
 x1  1, puesto que 3(0)  1(1)  2(0) < 2
Para restricciones 
Es un procedimiento análogo al de las restricciones , permite fijar una variable en 1.
Ejemplo 3:
x1 + x2  2x3  1 
 
 x3  0, puesto que 1(1) + 1(1)  2(1) < 1
También puede permitir que se fije una variable en 0.
Preprocesado automático del problema de PEB pura
Ejemplo 4:
3x1 + x2  3x3  2  x1  1, puesto que 3(0) + 1(1)  3(0) < 2
 y  x3  0, puesto que 3(1) + 1(1)  3(1) < 2
Ejemplo 5:
 3x1  2x2  1  x1  0, puesto que 3(1)  2(1) > 1 
 y  x2  1, puesto que 3(0)  2(0) > 1
 
 
Preprocesado automático del problema de PEB pura
Ejemplo 6:
3x1 + x2  2x3  2  x1  1 (como el ejercicio anterior)
 Entonces
 x1 + x4  x5  1  x4  0, x5  0
 En consecuencia, 
 x5  x6  0  x6  0
Fijar una variable a partir de una restricción puede llegar a generar una reacción en cadena que permita después fijar otras variables a partir de otras restricciones.
Ejemplo 7:
 8x1  4x2  5x3  3x4  2
 
 x2 + x3  1 
 
x1  0,
puesto que 8(1)  máx. {4, 5}(1) + 3(0) > 2.
2. Eliminación de restricciones redundantes:
Si una restricción funcional satisface incluso la solución binaria de mayor reto, entonces las restricciones binarias las han convertido en redundantes y en adelante pueden eliminarse. 
Preprocesado automático del problema de PEB pura
Ejemplos:
3x1 + 2x2  6 es redundante porque 3(1) + 2(1)  6.
3x1  2x2  3 es redundante porque 3(1)  2(0)  3.
3x1  2x2  3 es redundante porque 3(0)  2(1)  3.
En el caso de una restricción de tipo  la solución binaria más demandante tiene variables iguales a 1 cuando tiene coeficientes no negativos y otras variables son iguales a 0. (Estos valores se invierten si se trata de una restricción de tipo .)
Preprocesado automático del problema de PEB pura
3. Estrechamiento de restricciones:
Procedimiento para estrechar o reducir una restricción de tipo 
Denote la restricción por a1x1 + a2x2 +. . . + anxn  b.
1. Calcule S  suma de los positivos.
2. Identifique cualquier ≠ 0 tal que S < b + ||.
 a) Si no existen, el procedimiento se detiene; la restricción ya no se puede reducir.
 b) Si > 0, vaya al paso 3.
 c) Si < 0, vaya al paso 4.
3. ( > 0) Calcule  S  b y  S  aj. Restablezca  y b  . Regrese al paso 1.
4. ( < 0) Aumente a  b  S. Regrese al paso 1.
3. Estrechamiento de restricciones:
Ejemplo:
Maximizar: Z = 3x1 + 3x2
 s.a 2x1 + 3x2  4 y x1 y x2 binarias
Preprocesado automático del problema de PEB pura
Procedimiento:
La restricción es 
2x1  3x2  4 (  2,  3, b  4).
S  3 + 2  5.
2. satisface S < b + ||, puesto que 5 < 4 + 2. Además satisface 
S < b + ||, puesto que 5 < 4 + 3. Seleccione en forma arbitraria.
3.  5  4  1 y  5  2  3, se restablece  1 y b  3. La nueva restricción reducida es x1 + 3x2  3 (  1,  3, b  3).
3. Estrechamiento de restricciones:
Procedimiento:
1. S  1 + 3  4.
2. a2 satisface S< b + |a2|,puesto que 4 < 3 + 3.
3. a2  4  3  1 y  4  3  1, se restablece a2  1 y b  1. La nueva restricción reducida o estrecha es x1 + x2  1 (a1  1, a2  1, b  1).
1. S  1 + 1  2.
2. Ninguna aj ≠ 0 satisface S < b + |aj|, por lo cual el procedimiento se detiene; x1 + x2  1 es la restricción reducida que se busca.
Preprocesado automático del problema de PEB pura
Generación de planos cortantes para PEB pura
Un plano cortante (o corte) de un problema de PE es una nueva restricción funcional que reduce la región factible del relajamiento de PL sin eliminar soluciones factibles del problema de PE original.
En el ejercicio anterior estudiamos la manera de generar planos cortantes en problemas de PE pura, esto es, la aplicación del procedimiento anterior para estrechar restricciones.
Además de este procedimiento, se ha desarrollado un buen número de técnicas para generar planos cortantes que tenderán a acelerar la rapidez con la que el método de ramificación y acotamiento puede encontrar una solución óptima a un problema de PEB pura.
Procedimiento general que se utiliza para generar este corte.
Procedimiento para generar planos cortantes:
1. Considere cualquier restricción funcional de la forma  con solo coeficientes no negativos.
2. Encuentre un grupo de variables (llamado cubierta mínima de la restricción) tales que 
 a) La restricción se viola si todas las variables del grupo son iguales a 1 y todas las demás variables son iguales a 0.
 b) Pero la restricción se satisface si el valor de cualquiera de estas variables cambia de 1 a 0.
3. Si N denota el número de variables del grupo, el plano cortante obtenido tiene la forma
 Suma de variables del grupo  N  1.
Generación de planos cortantes para PEB pura
El enfoque de ramificación y cortadura implica la generación de muchas cortaduras en forma parecida antes de aplicar las ingeniosas técnicas de ramificación y acotamiento. Los resultados que se obtienen cuando se incluyen cortes pueden ser importantes para estrechar los relajamientos de PL.
Una combinación acertada de los cortes y las técnicas de ramificación y acotamiento (junto con el preprocesado automático del problema) proporciona un enfoque algorítmico poderoso para resolver problemas de PEB a gran escala. Esta es una razón por la que se ha dado el nombre de algoritmo de ramificación y corte a este nuevo enfoque.
Problema de programación entera por el método de ramificación.
Arbol del metodo de ramificacion y acotamiento 
conclusiones
Los problemas de PE surgen con frecuencia cuando los valores de algunas o de todas las variables de decisión deben restringirse a valores enteros. 
También es importante para decisiones sí o no (aquí se incluyen las relaciones combinatorias que pueden expresarse en términos de tales decisiones) que se puede representar por variables binarias (0-1).
Los factores que determinan el tiempo de cálculo son el número de variables enteras y el hecho de que el problema tenga una estructura especial que pueda explotarse.
En la actualidad es común que se disponga de paquetes de computadora para algoritmos de PE en el software de programación matemática. Estos algoritmos casi siempre se basan en la técnica de ramificación y acotamiento o en alguna variación de esta.
Hoy en día, los algoritmos más modernos de PE emplean el enfoque de ramificación y corte. Este enfoque algorítmico involucra la combinación del preprocesado automático del problema, la generación de cortes y las técnicas de ramificación y acotamiento.
Gracias