Source: http://docplayer.es/1060786-Fundamentos-de-investigacion-de-operaciones-investigacion-de-operaciones-1-programacion-lineal-entera.html
Timestamp: 2016-10-21 14:02:20+00:00

Document:
⭐Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera
1 Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema de programación lineal entera pura. Por ejemplo: máx z = 3x 1 + 2x 2 s.t. x 1 + x 2 6 x 1, x 2 Z + (1.1) Un LP donde sólo algunas variables deben ser enteras se denomina problema de programación lineal entera mixta. Por ejemplo: máx z = 3x 1 + 2x 2 s.t. x 1 + x 2 6 x 2 0 x 1 Z + (1.2) Un LP donde todas la variables deben ser igual a 1 ó 0 se denomina problema de programación lineal binaria. Por ejemplo: máx z = x 1 x 2 s.t. x 1 + 2x 2 2 2x 1 x 2 1 x 1, x 2 = {0, 1} El concepto de relajación de un problema de programación lineal entera (IP) juega un rol fundamental en la resolución de este tipo de problemas. Definición 1 El LP obtenido eliminando todas las condiciones de valores enteros o binarios para las variables se denomina Relajación del LP. Por ejemplo, la relajación de (1.1) quedaría: (1.3) máx z = 3x 1 + 2x 2 s.t. x 1 + x 2 6 x 1, x 2 0 De la misma forma, la relajación de (1.3) queda: (1.) 12 máx z = x 1 x 2 s.t. x 1 + 2x 2 2 2x 1 x 2 1 x 1, x 2 0 Cualquier IP puede ser visto como el LP relajado más algunas restricciones adicionales. Por lo tanto, el LP relajado es un problema menos restringido, o más relajado, que el IP. En consecuencia la región factible para cualquier IP debe estar contenida en la región factible del correspondiente LP relajado. Luego, si el problema es de maximización: El valor óptimo de z del LP relajado El valor óptimo de z del IP Consideremos el siguiente ejemplo: (1.5) máx z = 21x x 2 s.t. 7x 1 + x 2 13 x 1, x 2 Z + (1.6) La región factible del problema relajado se presenta en la figura 1.1. En este caso, la región factible del IP lo conforma el siguiente conjunto de puntos: S = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1)}. En este caso, mediante la evaluación y comparación de los valores de z en los seis puntos factibles es posible determinar el óptimo. Luego, la solución óptima de (1.6) es z = 33, x 1 = 0, x 2 = 3. x 2 3,0 = punto en la región factible 2,5 7x 1 + x 2 = 13 2,0 1,5 1,0 0, ,5 1,0 1,5 2,0 2,5 3,0 x 1 Figura 1.1: Región Factible del ejemplo 1.6 Si la región factible de la relajación de un IP puro está acotada, la región factible del IP consistirá en un número finito de puntos. En teoría, mediante la enumeración y la evaluación de z en cada uno de los puntos es posible encontrar el mejor valor de z. El problema es que si la región factible contiene miles de puntos factibles, la enumeración completa no es viable desde un punto de vista computacional. Una segunda opción para resolver el IP sería mediante la aproximación de la solución obtenida de la relajación. Por ejemplo si se resolviera la relajación de (1.6) se obtendría: x 1 = 13 7, x 2 = 0. Redondeando esta solución se obtendría: x 1 = 2, x 2 = 0 como posible solución óptima. Sin embargo este punto está fuera de la región factible por lo que no puede ser óptimo. Otro candidato a óptimo se 23 puede obtener redondeando el valor obtenido de la relajación hacia abajo: x 1 = 1, x 2 = 0, valor que tampoco corresponde al óptimo real del problema. Como se ve en este ejemplo, no existen garantías de que la aproximación de soluciones del problema relajado corresponda a la solución óptima real del IP. Por lo tanto, no es un enfoque válido para resolver el problema. Como se estudió previamente, el algoritmo Simplex resuelve un LP a partir de una solución básica factible mejorándola iteración a iteración. Luego, en la mayoría de los casos, Simplex examina sólo una porción de todas las soluciones basales factibles antes de llegar al óptimo. En forma análoga, se podría esperar que existan algoritmos capaces de resolver un IP iterando de una solución factible entera a otra. Lamentablemente, no existen o no son conocidos tales algoritmos. Por lo tanto, como se verá en detalle más adelante, la resolución de un IP es mucho más compleja que la resolución de su relajación. 2. Formulación de IP Los problema de programación lineal entera permiten ampliar el espectro de problemas factibles de plantear como modelos de programación lineal. A continuación se verán algunos ejemplos Problema de Asignación de Capital Ejemplo 1 Una empresa está considerando cuatro posibles inversiones. La opción 1 tiene asociado un valor actualizado neto (VAN) de US$16000, la opción 2 tiene un VAN de US$22000, la inversión 3 representa un VAN de US$12000 y la inversión posee un VAN de US$8000. Cada inversión requiere un cierto capital inicial: US$5000, US$7000, US$000 y US$3000, para las inversiones 1, 2, 3 y respectivamente. Actualmente la empresa dispone $1000 para invertir. Formule un IP que permita determinar la forma de invertir el dinero de forma de maximizar las utilidades. Las opciones son invertir o no en cada una de las posibilidades. Por lo tanto, conviene emplear variables de tipo binaria para indicar si se escoge cada opción: x j = { 1 se invierte en la opción j 0 en caso contrario j = 1... (2.1) La función objetivo para el problema queda (en miles): máx z = 16x x x 3 + 8x (2.2) En la expresión (2.2) se verifica que si la opción j se realiza, entonces x j = 1 y se suma el VAN respectivo al valor de la función objetivo. En caso contrario, la variable x j = 0 y no se contabiliza ese aporte. Se sigue la misma lógica para construir las restricciones. Como existe un capital limitado de U S$1000 para invertir, se debe satisfacer (en miles): 5x 1 + 7x 2 + x 3 + 3x 1 (2.3) Como no existen otras restricciones, el modelo completo para el problema queda: máx z = 16x x x 3 + 8x s.t. 5x 1 + 7x 2 + x 3 + 3x 1 x j = {0, 1} j (2.) Supongamos ahora que se agregan las siguientes restricciones al problema original: 34 1. La empresa puede invertir en a lo más dos opciones. 2. Si la empresa invierte en la opción 2, también debe invertir en Si la empresa invierte en 1, no puede tomar la opción.. Sólo se puede invertir en 3 si se escoge 1 ó 2. El planteo original del problema (2.) se ve modificado de la siguiente forma: 1. En este caso basta con agregar la restricción: x 1 + x 2 + x 3 + x 2 2. Para incorporar esta restricción, se debe imponer que si x 2 = 1 necesariamente x 1 = 1. Luego, se podría emplear: x 2 x 1 ó x 2 x 1 0 Si x 2 = 1 necesariamente se tendrá x 1 = 1. Si x 2 = 0, x 1 podría ser 0 ó 1. Como no existen indicaciones en ese caso, se satisface el requerimiento de la nueva restricción. 3. Esta restricción impone la condición de que las alternativas 1 y sean excluyentes, en otras palabras: x 1 + x 1 Como las variables son binarias, no se permite que ambas puedan ser igual a 1.. Aquí, la variable x 3 puede valer 1 sólo si x 1 o x 2 es igual a 1. No existen restricciones que digan que x 1 y x 2 sean excluyentes, por lo tanto eventualmente se podría escoger ambas. En este caso se puede agregar: x 3 x 1 + x 2 Luego, basta con tener un 1 a la derecha de la desigualdad para que x 3 pueda tomar valor igual a 1. Si se exigiera que deben escogerse 1 y 2 para poder seleccionar 3, la restricción quedaría: 2 x 3 x 1 + x 2 En este caso se requiere tener un 2 a la derecha de la desigualdad para que x 3 pueda ser igual a uno Problemas de Costo Fijo Ejemplo 2 Una compañía es capaz de producir tres tipos de prendas: poleras, shorts y pantalones. La fabricación de cada tipo de prenda requiere de maquinaria especializada. La maquinaria puede ser arrendada a los siguientes costos: US$200, US$150 y US$100 al mes en el caso de las poleras, shorts y pantalones respectivamente. La fabricación de cada prenda requiere las cantidades de tela y mano de obra indicadas en la Cuadro 2.1. Cada mes se dispone de 150 horas de mano de obra y 160 yd 2 de tela. El costo unitario de producción y el precio de venta de cada artículo se muestra en el Cuadro 2.2. Formule un IP que permita maximizar el beneficio de la fábrica. Para plantear el modelo se pueden definir las siguientes variables: x 1 = número de poleras producidas mensualmente x 2 = número de shorts producidos mensualmente x 3 = número de pantalones producidos mensualmente (2.5)5 Mano de Obra [hrs] Tela [yd 2 ] Poleras 3 Shorts 2 3 Pantalones 6 Cuadro 2.1: Requerimientos de Fabricación Precio de Venta US$ Costo Variable US$ Poleras 12 6 Shorts 8 Pantalones 15 8 Cuadro 2.2: Requerimientos de Fabricación Como el costo de arriendo de la maquinaria sólo depende de la prenda producida, será necesario emplear variables binarias para cuantificar el hecho de arrendar o no cada máquina: { 1 se arrienda maquinaria para fabricar prendas tipo i y i = 0 en caso contrario Para que el modelo funcione, se debe garantizar que: j = (2.6) Si x i > 0 y i = 1 Si x i = 0 y i = 0 Para ello, se debe incorporar las restricciones de activación de las variables binarias: (2.7) x 1 M 1 y 1 x 2 M 2 y 2 (2.8) x 3 M 3 y 3 Los valores M i son valores escalares lo suficientemente grandes de forma que sean una cota superior para el valor de x i en el contexto del problema. La restricción (2.8) activa la variable binaria ya que si x i > 0, para que la restricción se pueda satisfacer la variable binaria y i debe ser exactamente igual a 1. En el caso que x i = 0, la variable binaria y i puede o no valer 1 sin afectar la satisfacción de la restricción, sin embargo, si la variable binaria valiera 1 se estaría considerando el costo de arriendo de una maquinaria que no se está empleando. Evidentemente, como el problema es de maximización de ganancias, si no es estrictamente necesario cuantificar un costo, el algoritmo de resolución se encargará de hacer que la variable y i = 0 en el óptimo. En otras palabras, si el problema no obliga a considerar un costo, el algoritmo de resolución se encargará de no contabilizarlo. La función objetivo corresponderá a la diferencia entre los ingresos por venta, menos los costos de producción fijos y variables: z = (12x 1 + 8x x 3 ) (6x } {{ } 1 + x 2 + 8x 3 ) (200y } {{ } y y 3 ) } {{ } Ingresos por venta Costos variables Costos fijos Por lo tanto, la función objetivo a maximizar queda: (2.) z = 6x 1 + x 2 + 7x 3 200y 1 150y 2 100y 3 (2.10) 56 A continuación es preciso construir las restricciones del problema. En este caso existe un disponibilidad máxima de mano de obra y de tela. La restricción de mano de obra queda: y la de tela sería: 3x 1 + 2x 2 + 6x (2.11) x 1 + 3x 2 + x (2.12) Las restricciones (2.11) y (2.12) nos permiten estimar el valor de M i. Por ejemplo si sólo se produjeran artículos de tipo 1, el valor máximo a producir quedaría controlado por: mín{ 150 3, 160 }, es decir, 0. Luego, basta con escoger M 1 = 0, pero en general podría ser cualquier valor mayor. En el caso de x 2 controla y para x 3 basta con M 3 = 25. En términos generales los valores de M i sólo deben ser lo suficientemente grandes para no restringir los valores de x i por lo que se escogerá arbitrariamente M 1 = M 2 = M 3 = 100. De acuerdo a la selección anterior, el modelo final para el problema queda: máx z = 6x 1 + x 2 + 7x 3 200y 1 150y 2 100y 3 s.t. 3x 1 + 2x 2 + 6x x 1 + 3x 2 + x x 1 M 1 y 1 x 2 M 2 y 2 x 3 M 3 y 3 x i Z + i = y i = {0, 1} i = (2.13) 2.3. Problemas de Cubrir Conjuntos Ejemplo 3 Existen 6 barrios en una ciudad. La Alcaldía debe determinar cómo construir estaciones de bomberos. La Alcaldía desea construir el número mínimo de estaciones de bomberos de forma de asegurar que al menos una estación esté a menos de 15 minutos de cada barrio. Los tiempos de viaje entre cada barrio de la ciudad se muestra en el Cuadro 2.3. Formule el IP que permita determinar cuantas estaciones deben ser construidas y donde deben estar ubicadas. Hasta Desde Barrio 1 Barrio 2 Barrio 3 Barrio Barrio 5 Barrio 6 Barrio Barrio Barrio Barrio Barrio Barrio Cuadro 2.3: Tiempo de viaje entre barrios Para resolver el problema se debe buscar la asignación del menor número de estaciones de bomberos de forma de cubrir un conjunto de Barrios. Para construir el IP, conviene definir las siguientes variables: 67 { 1 se construye una estación de bomberos en el barrio i x i = 0 en caso contrario i = (2.1) De acuerdo a las variables definidas, el total de estaciones a construir queda definido por: z = 6 x i (2.15) i=1 Para construir las restricciones, es preciso obtener del Cuadro 2.3 en que lugares es factible construir la estaciones de bomberos para asegurar que cada barrio quede a menos de 15 minutos de al menos una de ellas. Por ejemplo, para asegurar que al menos una estación quede a menos de 15 minutos del Barrio 1 se debe construir en el propio Barrio 1 o bien en el Barrio 2. Siguiendo la misma lógica se construye el Cuadro 2.. Barrio Barrios factibles de construcción 1 1, 2 2 1, 2, 6 3 3, 3,, 5 5, 5, 6 6 2, 5, 6 Cuadro 2.: Lugares factibles de construcción de estaciones de bomberos Luego, para asegurar la condición solicitada para el Barrio 1 se puede agregar: x 1 + x 2 1 (2.16) Incorporando las restricciones para los otros barrios se completa el IP: máx z = x 1 + x 2 + x 3 + x + x 5 + x 6 s.t. x 1 + x 2 1 (Barrio 1) x 1 + x 2 + x 6 1 (Barrio 2) x 3 + x 1 (Barrio 3) x 3 + x + x 5 1 (Barrio ) x + x 5 + x 6 1 (Barrio 5) x 2 + x 5 + x 6 1 (Barrio 6) x i = {0, 1} i = (2.17) 2.. Problemas con restricciones excluyentes o no excluyentes En un modelo matemático puede ocurrir frecuentemente que existan dos o más restricciones que sean mutuamente excluyentes, por ejemplo sean las restricciones: f(x 1, x 2,... x n ) 0 (2.18) g(x 1, x 2,... x n ) 0 (2.1) 78 Si se desea que sólo sea satisfecha una de las restricciones, se puede modificar el planteo de las restricciones de la siguiente forma: f(x 1, x 2,... x n ) My (2.20) g(x 1, x 2,... x n ) M(1 y) (2.21) donde y es una variable binaria y M es una constante lo suficientemente grande para asegurar que las restricciones: f(x 1, x 2,... x n ) M g(x 1, x 2,... x n ) M se satisfacen para toda combinación de valores de x 1, x 2,... x n. Por lo tanto, si y = 1 se tiene que f M y g 0, es decir, sólo existe para efectos prácticos las restricción asociada a g. En caso contrario, si y = 0 se tiene que f 0 y g M, por lo tanto sólo existe la restricción f en términos prácticos. Si se deseara que al menos una de las restricciones fuera satisfecha, el planteo quedaría: f(x 1, x 2,... x n ) My 1 g(x 1, x 2,... x n ) My 2 y 1 + y 2 1 donde y 1 e y 2 son variables binarias independientes. La idea anterior se puede extender a cualquier número de restricciones. Ejemplo Una fábrica de automóviles construye tres tipos de autos: compactos, medianos y grandes. Los requerimientos de materiales, mano de obra y el beneficio obtenido por cada tipo de auto fabricado se muestra en el Cuadro 2.5. Actualmente, la fábrica dispone 6000 toneladas de materiales y horas de mano de obra. Para que la producción de un tipo de vehículo sea económicamente factible, se deben producir al menos 1000 unidades de cada tipo que se fabrique. Formule un IP que permita maximizar el beneficio de la fábrica. Compacto Mediando Grande Materiales [T] 1,5 3 5 Mano de obra [hr] Beneficio [U S$] Cuadro 2.5: Requerimientos y beneficios por tipo de vehículo. Como variables de decisión conviene emplear: x i = número de automóviles de tipo i fabricados (2.22) La función objetivo queda definida por la combinación lineal de las variables por sus respectivos beneficios unitarios (en miles): máx z = 2x 1 + 3x 2 + x 3 (2.23) 89 A continuación se debe agregar la restricción que obligue a que si se produce un determinado tipo de vehículo, se produzcan como mínimo 1000 unidades, es decir: O bien: x i 0 ó x i 1000 i = (2.2) x i 0 ó 1000 x i 0 i = (2.25) Introduciendo la variable binaria y i, las restricciones quedan: x i M i y i (2.26) 1000 x i M i (1 y i ) (2.27) y i = {0, 1} (2.28) Un valor posible para M i se puede obtener a partir de la disponibilidad de materiales y de mano de obra, por ejemplo para los vehículos compactos sería: M 1 = mín{ ,5, } = Siguiendo la misma lógica se puede obtener: M 2 = 2000 y M 3 = Por otro lado, se deben incorporar las restricciones relativas a la disponibilidad de materiales y mano de obra: Finalmente, el IP queda: 1,5x 1 + 3x 2 + 5x (Materiales) 30x x 2 + 0x (Mano de Obra) máx z = 2x 1 + 3x 2 + x 3 s.t. x y x (1 y 1 ) x y x (1 y 2 ) x y x (1 y 3 ) 1,5x 1 + 3x 2 + 5x x x 2 + 0x x i Z + i = y i = {0, 1} i = (2.2) (2.30) 2.5. Problemas con restricciones de tipo si... entonces En un modelo matemático puede ocurrir que si la restricción: se satisface, entonces la restricción: f(x 1, x 2,... x n ) > 0 (2.31) g(x 1, x 2,... x n ) 0 (2.32)10 tenga también que satisfacerse, mientras que si f 0 la restricción g 0 pueda o no satisfacerse. Para garantizar esta condición se pueden incorporar las siguientes restricciones: g(x 1, x 2,... x n ) My (2.33) f(x 1, x 2,... x n ) M(1 y) (2.3) y = {0, 1} (2.35) El valor de M debe ser escogido de tal forma que si f M y g M se asegure que todos los valores de x 1, x 2,... x n satisfagan las restricciones. Si la variable binaria vale cero, se tiene f M, en particular f > 0. Por otro lado, si y = 0 se tiene g 0 o bien g 0. En caso contrario, cuando y = 1 se tiene f 0, es decir, no se puede cumplir que f > 0. Si y = 1 se tiene g M, es decir, se cumple si g 0 o si g < 0. En suma, si se satisface f > 0, la variable binaria debe valer 1 lo que obliga a satisfacer g 0. A modo de ejemplo, supongamos que en el problema de la fábrica de automóviles si se fabrican autos compactos no se pueden fabricar vehículos de otro tipo. En otras palabras se tiene: En forma equivalente se tiene: Por lo tanto, basta incorporar: Si x 1 > 0 x 2 = x 3 = 0 (2.36) Si x 1 > 0 x 2 + x 3 0 ó x 2 x 3 0 (2.37) x 2 + x 3 My (2.38) x 1 M(1 y) (2.3) y = {0, 1} (2.0) El valor de M no tiene porqué ser único. En este caso, podemos emplear los valores de M i calculados previamente: x 2 + x 3 (M 2 + M 3 )y = 3200y (2.1) x 1 M 1 (1 y) = 2000(1 y) (2.2) y = {0, 1} (2.3) 2.6. Problemas con funciones lineales definidas por tramos Una función lineal definida por tramos corresponde a un conjunto de segmentos rectos. Los puntos donde se producen cambios de pendiente se denominan puntos de quiebre. Sea f(x) una función lineal por tramos con puntos de quiebre b 1, b 2,... b n, para cualquier k = 1, 2,... n, b k x b k+1. Entonces, para algún número z k (0 z k 1), x puede ser escrito como: Como f(x) es lineal para b k x b k+1, se puede escribir: x = z k b k + (1 z k )b k+1 (2.) 1011 f(x) = z k f(b k ) + (1 z k )f(b k+1 ) (2.5) La expresión anterior representa una parametrización entre los valores extremos de la función en ese intervalo, en términos del parámetro z k 1. La idea geométrica se ilustra en la Figura 2.1. f(x) f(b 3 ) f(b 2 ) b 1 b 2 b 3 x La función objetivo puede ser escrita como: Figura 2.1: Función lineal por tramos f(x) = z 1 f(b 1 ) + z 2 f(b 2 ) z n f(b n ) (2.6) Evidentemente, se debe cumplir que z k+1 + z k = 1 para algún k. Sea y k una variable binaria auxiliar que indica la presencia de la variable x dentro del intervalo k (k = 1... n 1). Entonces se puede escribir las siguientes restricciones: z 1 y 1 z 2 y 1 + y 2 z 3 y 2 + y 3. z n 1 y n 2 + y n 1 z n y n 1 (2.7) Por lo tanto, si la variable x está en el intervalo k, se tiene y k = 1 y sólo z k y z k+1 pueden ser distintas de cero. Evidentemente, la variable x sólo puede pertenecer a un intervalo: Cómo z k+1 = 1 z k, se debe agregar la restricción: De acuerdo a la ecuación (2.) se tiene: y 1 + y y n 1 = 1 (2.8) z 1 + z z n = 1 (2.) x = z 1 b 1 + z 2 b z n b n (2.50) Para ilustrar la incorporación de funciones lineales definidas por tramos consideremos el siguiente ejemplo: 1112 Ejemplo 5 Una refinería produce dos tipos de gasolina a partir de dos tipos de petróleos. Cada galón de gasolina tipo 1 debe contener a lo menos 50 % de petróleo 1 y cada galón de gasolina tipo 2 debe contener al menos 60 % de petróleo tipo 1. Cada galón de gasolina tipo 1 puede ser vendido a $12 y cada galón de tipo 2 puede ser vendido a $1. Actualmente se dispone de 500 galones de petróleo tipo 1 y 1000 galones de petróleo de tipo 2. Se puede comprar hasta 1500 galones adicionales de petróleo tipo 1 al siguiente precio: los primeros 500 galones se deben pagar a $25 el galón; los siguientes 500 galones se deben pagar a $20 el galón; los siguientes 500 galones se compran a $15 el galón. Formule un IP que permita determinar la forma de maximizar las utilidades. Para plantear el modelo se pueden definir las siguientes variables: x = cantidad de petróleo tipo 1 comprado x ij = cantidad de petróleo de tipo i empleado para producir gasolina de tipo j (2.51) La función objetivo queda: máx z = 12(x 11 + x 21 ) + 1(x 12 + x 22 ) c(x) (2.52) donde: 25x 0 x 500 c(x) = 25x x x x 1500 La restricción relativa a la disponibilidad de petróleo tipo 1 queda: (2.53) La restricción relativa a la disponibilidad de petróleo tipo 2 queda: x 11 + x 12 x (2.5) x 21 + x (2.55) Para obligar que la gasolina tipo 1 tenga al menos un 50 % de petróleo tipo 1 se agrega: x 11 x 11 + x 21 0,5 (2.56) Para obligar que la gasolina tipo 2 tenga al menos un 60 % de petróleo tipo 1 se agrega: En la función objetivo se reemplaza c(x) por: x 12 x 12 + x 22 0,6 (2.57) El valor de la variable x se calcula según: c(x) = 0z 1 + c(500)z 2 + c(1000)z 3 + c(1500)z c(x) = 12500z z z (2.58) x = 0z z z z (2.5) Las variables continuas z k se relacionan con las binarias y k seún: z 1 y 1 z 2 y 1 + y 2 z 3 y 2 + y 3 z y 3 (2.60) 1213 Además se tiene que: z 1 + z 2 + z 3 + z = 1 y 1 + y 2 + y 3 = 1 Finalmente se agrega la naturaleza de las variables: z i 0 i = 1... y j = {0, 1} j = x kr 0 k r (2.61) (2.62) 3. Resolución de IP - Método de Ramificación y Acotamiento El método de ramificación y acotamiento consiste en una técnica de enumeración eficiente de los puntos factibles de subproblemas de un cierto problema original. Evidentemente, si se resuelve la relajación de un problema de programación lineal entera pura o mixta y se encuentra que todas las variables que deben ser enteras o binarias cumplen la condición de enteridad, el óptimo encontrado será también el óptimo del IP original. Por ejemplo si se resuelve la relajación del siguiente problema: Ejemplo 6 máx z = 3x 1 + 2x 2 s.t. 2x 1 + x 2 6 x 1, x 2 Z + (3.1) se obtiene como solución: x 1 = 0, x 2 = 6 y z = 12, que corresponde exactamente a la solución del IP original. Tal como se ve en la Figura 3.1, la región factible del IP es un subconjunto de la relajación, por lo tanto el óptimo del IP no puede ser mejor que el óptimo de su relajación. La generalización de esta idea es el principio básico del método de ramificación y acotamiento. x = punto en la región factible 2x 1 + x 2 = x 1 Figura 3.1: Región Factible del ejemplo 3.1 Para ilustrar como opera la técnica, consideremos el siguiente ejemplo: Ejemplo 7 Una mueblería fabrica mesas y sillas. Una mesa requiere de 1 hora de mano de obra y pies cuadrados de madera, una silla requiere de 1 hora de mano de obra y 5 pies cuadrados de madera. Actualmente, la mueblería dispone de 6 horas de mano de obra y 5 pies cuadrados de madera. Cada 1314 mesa genera una utilidad de US$8, cada silla representa una utilidad de US$5. Formule y resuelva un IP para maximizar el beneficio de la mueblería. Consideremos: x 1 = número de mesas fabricadas x 2 = número de sillas fabricadas Como x 1 y x 2 deben ser enteras, el IP que resuelve el problema queda: (3.2) máx z = 8x 1 + 5x 2 s.t. x 1 + x 2 6 x 1 + 5x 2 5 x 1, x 2 Z + (3.3) En primer lugar se resuelve la relajación del IP, llamaremos a este problema el Subproblema 1: máx z = 8x 1 + 5x 2 s.t. x Subproblema 1: 1 + x 2 6 (3.) x 1 + 5x 2 5 x 1, x 2 0 La resolución gráfica del Subproblema 1 se muestra en la Figura 3.2. En este caso, la solución óptima corresponde al punto x 1 = 15 = 3,75 y x 2 = 165 = 2,25, con valor de la función objetivo z =. Como se mencionó anteriormente, la solución del IP no puede ser mejor a la del IP relajado, por lo que z = 165 es una Cota Superior para la función objetivo. x 2 8 x 1 + 5x 2 = óptimo x1 + x 2 = Figura 3.2: Región Factible del Subproblema 1 El próximo paso es seleccionar una partición de la región factible de la relajación de forma de intentar obtener la solución óptima del IP. Para ello, arbitrariamente se escoge una variable que no satisfaga las condiciones del IP, es decir, una variable fraccionaria que debería ser entera, por ejemplo x 1. Cómo se busca un valor entero para x 1 interesa que x 1 3 o bien que x 1, ya que no puede haber una solución factible entera en el intervalo 3 < x 1 <, en otras palabras se buscan soluciones 1 x 115 en los valores enteros más cercanos al valor fraccionario obtenido. De acuerdo a ello, ramificaremos la variable x 1 definiendo los siguientes subproblemas: Subproblema 2: Subproblema 1 + restricción: x 1 3 Subproblema 3: Subproblema 1 + restricción: x 1 Nótese que ambos subproblemas excluyen el valor x 1 = 15, es decir, la solución óptima de los subproblemas no puede ser igual al de la relajación. Por otro lado, como se está resolviendo un problema más restrictivo que la relajación original el valor de la función objetivo no puede ser mejor. La ramificación de las variables se ordena en un árbol de ramificación como se muestra en la Figura 3.3. La región factible del subproblema 2 se muestra en la Figura 3.. Los puntos extremos de la región factible: D, E, F y G son los candidatos a óptimos, evaluando se obtiene: z D = 0, z E = 2, z F = 3 y z G = 30, por lo que la mejor solución corresponde al punto F (x 1 = 3, x 2 = 3), con valor de la función objetivo: z = 3. En este caso, la solución obtenida satisface las condiciones de enteridad, por lo que es posible definir como cota superior z = 3. Subproblema z = 15 x 1 = x 2 = x 1 3 x 1 Subproblema 2 Subproblema 3 (3.5) Figura 3.3: Árbol de ramificación subproblemas 2 y 3 x 2 8 x 1 + 5x 2 = G x1 = F 1 0 D E x1 + x 2 = Figura 3.: Región Factible del subproblema 2 Si bien la solución obtenida del subproblema 2 satisface todas las condiciones del problema, debemos completar la ramificación ya que aún hay esperanzas de obtener una solución menor o igual al valor 15 x 116 óptimo del subproblema 1, pero mejor a la cota superior actual. La región factible del subproblema 3 se muestra en la figura 3.5. Los puntos extremos de la región factible son: A, B y C, con respectivos valores de la función objetivo: z A = 0, z B = 32 y z C = 1. Por lo tanto el óptimo corresponde a: x 1 = y x 2 = 5, valor que no satisface la condición de enteridad. x 2 8 x 1 + 5x 2 = x1 + x 2 = 6 x1 = C 1 0 B A Figura 3.5: Región Factible del subproblema 3 Si bien hasta ahora se dispone de una solución entera con valor de la función objetivo de 3, en el subproblema 3 se obtuvo como valor óptimo: z = 1. Si bien el subproblema 3 no representa una solución factible para el IP, al ramificar a partir de éste problema se podría esperar un valor de la función objetivo que sea menor o igual a 1 pero que podría ser mejor que 3, por lo que no se puede dar como finalizada las ramificaciones. De acuerdo a ello, podemos definir dos nuevos subproblemas a partir el subproblema 3. Como la variable x 2 = 5 no es entera, conviene buscar valores con las siguientes particiones de la región factible: x 2 1 y x 2 2. En otras palabras, se deben resolver los siguientes subproblemas: Subproblema : Subproblema 3 + restricción: x 2 1 Subproblema 5: Subproblema 3 + restricción: x 2 2 El árbol de ramificación con los dos nuevos subproblemas se muestra en la Figura 3.6. La región factible para los subproblemas y 5 se indican en la Figura 3.7. Para el subproblema, los nuevos candidatos a óptimos son los puntos H e I, con valores de la función objetivo: z H = 37 y z I = 365 = 0,556. Entre los puntos A, B, H e I, el mejor valor se obtiene para el punto I con x 1 = 0 y x 2 = 1. Respecto del subproblema 5 se observa que no existen puntos que satisfagan simultáneamente las restricciones del subproblema 3 y x 2 2, por lo que tiene solución imposible. Como la solución óptima del subproblema es superior a la cota, es necesario volver a ramificar ya que eventualmente se podría encontrar una solución que sea menor o igual a z = 365, pero mejor que z = 3. En este caso, la variable no entera es x 1 = 0, por lo que conviene definir los siguientes subproblemas: x 1 (3.6) Subproblema 6: Subproblema + restricción: x 1 Subproblema 7: Subproblema + restricción: x 1 5 (3.7) 1617 Subproblema z = 15 x 1 = x 2 = x 1 3 x 1 Subproblema 2 z = 3 x 1 = 3 x 2 = 3 Subproblema 3 z = 1 x 1 = x 2 = 5 x 2 1 x 2 2 Subproblema Subproblema 5 Figura 3.6: Árbol de ramificación subproblemas y 5 x 2 8 x 1 + 5x 2 = x1 + x 2 = 6 x1 = x 2 = 2 x 2 = 1 H I B A Figura 3.7: Región Factible del subproblemas y 5 x 1 El nuevo árbol de ramificación se muestra en la Figura 3.8. Se agregan las nuevas restricciones referentes a x 1 y se completa la región factible para los subproblemas 6 y 7 en la Figura 3.. En este caso, la región factible para el subproblema 6 se reduce al segmento de línea entre los puntos B y H, con valores para la función objetivo de: z B = 32 y z H = 37, por lo que el óptimo corresponde al punto H. Como en el punto H los valores de las variables son enteros, se podría pensar que H es un candidato a óptimo. Sin embargo, el valor de la función objetivo en H es inferior a la cota definida previamente, por lo que se descarta. En el subproblema 7, el único punto que satisface todas las restricciones es el punto A, con valor de la función objetivo z = 0. Como en el subproblema 7 el valor de las variables es entero (x 1 = 5 y x 2 = 0) y dado que el valor de la función objetivo es mejor que la cota actual, 0 se transforma en la nueva cota. Como el subproblema 6 presenta un valor de la función objetivo 1718 inferior a la cota, no tiene sentido seguir ramificando pues se ha alcanzado el óptimo del IP. El árbol de ramificación completo se muestra en la Figura 3.10 donde se identifica la solución óptima. Subproblema z = 15 x 1 = x 2 = x 1 3 x 1 Subproblema 2 z = 3 x 1 = 3 x 2 = 3 Subproblema 3 z = 1 x 1 = x 2 = 5 x 2 1 Subproblema 365 z = 0 x 1 = x 2 = 1 x 1 x 1 5 x 2 2 Subproblema 5 Imposible Subproblema 6 Subproblema 7 Figura 3.8: Árbol de ramificación subproblemas 6 y 7 x 2 8 x 1 + 5x 2 = x1 + x 2 = 6 x1 = x1 = x 2 = 1 H B A Figura 3.: Región Factible del subproblemas 6 y 7 x 1 1819 Subproblema z = 15 x 1 = x 2 = x 1 3 x 1 Subproblema 2 z = 3 x 1 = 3 x 2 = 3 Subproblema 3 z = 1 x 1 = x 2 = 5 x 2 1 Subproblema 365 z = 0 x 1 = x 2 = 1 x 2 2 Subproblema 5 Imposible x 1 x 1 5 Subproblema 6 z = 37 x 1 = x 2 = 1 Subproblema 7 z = 0 x 1 = 5 x 2 = 0 Figura 3.10: Árbol de ramificación final Ejemplo 8 Considere un problema de programación lineal entera mixta cuyo objetivo es la maximización de una función z involucrando las variables binarias x 1, x 2 y x 3 y la variable continua x 0. El Cuadro 3.1 presenta la solución óptima para todos los problemas relajados posibles de obtener (un guión en la columna correspondiente a las variables x 1, x 2 y x 3 significa que la variable está libre en el problema relajado). x 1 x 2 x 3 x z x 1 x 2 x 3 x z x 1 x 2 x 3 x z (0.2,1,0,0) (0,1,0.67,0) (1,0,0,0) (0.2,1,0,0) (0,1,0,2) (1,0,0,0) (0,0.8,1,0) (0,0.8,1,0) (1,0,1,0) (0.7,0,0,0) Imposible (1,0,0,0) (0.7,0,0,0) Imposible (1,0,0,0) (0.,0,1,0) Imposible (1,0,1,0) (0.2,1,0,0) (0,1,0.67,0) (1,1,0,0) (0.2,1,0,0) (0,1,0,2) (1,1,0,0) (0,1,1,0.5) (0,1,1,0.5) (1,1,1,0) Cuadro 3.1: Soluciones de todas las relajaciones posibles Resuelva este problema aplicando la técnica de ramificación y acotamiento. 120 En primer lugar se resuelve el problema relajado completo, es decir, se libera el valor de las tres variables binarias. De acuerdo al Cuadro 3.1, se tiene: Subproblema 1 x 1 = 0.2 x 2 = 1 x 3 = 0 x = 0 z = En la solución del subproblema 1 el valor de la variable x 1 no satisface la condición de binaria, por lo tanto se ramifica en función de los valores que puede tomar: (3.8) De acuerdo al Cuadro 3.1 se tiene: Subproblema 2: Subproblema 1 + (x 1 = 0) Subproblema 3: Subproblema 1 + (x 1 = 1) Subproblema 2 Subproblema 3 x 1 = 0 x 2 = 1 x 3 = 0.67 x = 0 z = x 1 = 1 x 2 = 0 x 3 = 0 x = 0 z = 7.00 (3.) (3.10) (3.11) Se obtiene entonces un primer candidato a óptimo: x 1 = 1, x 2 = 0, x 3 = 0, x = 0 y z =7.00. Se selecciona entonces como cota: z =7.00. El subproblema 2 no representa una solución factible para el problema original pero posee un valor de la función objetivo superior a la cota, por lo que conviene ramificar: Subproblema : Subproblema 1 + (x 1 = 0) + (x 3 = 0) Subproblema 5: Subproblema 1 + (x 1 = 0) + (x 3 = 1) De acuerdo al Cuadro 3.1 se tiene: Subproblema Subproblema 5 x 1 = 0 x 2 = 1 x 3 = 0 x = 2 z = x 1 = 0 x 2 = 0.8 x 3 = 1 x = 0 z = 7.0 (3.12) (3.13) (3.1) El subproblema presenta una solución factible, pero muy por debajo de la cota superior por lo que se puede descartar. El subproblema 5 tiene un asociado un valor óptimo de la función objetivo superior 20 Mostrar más
Contenido INVESTIGACIÓN DE OPERACIONES Modelos y aplicaciones de programación lineal(página 3) Modelos de Transporte y transbordo(página 41) Modelos de Asignación(página 57) Modelos de gestión de proyectos Más detalles Problemas resueltos de Programación Lineal
Problemas resueltos de Programación Lineal Objetivos: Entender la idea de la Programación lineal y sus aplicaciones a problemas prácticos. Plantear problemas de programación lineal en dos variables. Conocer Más detalles -Teoría y Problemas resueltos de Programación Lineal
-Teoría y Problemas resueltos de Programación Lineal Objetivos: Entender la idea de la Programación lineal y sus aplicaciones a problemas prácticos. Plantear problemas de programación lineal en dos variables. Más detalles UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM
UNIVERSIDAD DEL BÍO-BÍO FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL PROFESOR GUÍA: SR. CARLOS OBREQUE NIÑEZ UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM TRABAJO Más detalles EVALUACION ECONOMICA DE PROYECTOS EJERCICIO RESUELTOS
UNIVERSIDAD DE CONCEPCION FACULTAD DE CIENCIAS ECONOMICAS Y ADMINISTRATIVAS DEPARTAMENTO DE ECONOMIA EVALUACION ECONOMICA DE PROYECTOS EJERCICIO RESUELTOS (VERSIÓN CORREGIDA) PROFESORES : JOSE FUENTES Más detalles MAGDA BUITRAGO Profesional en mercadeo
MATEMATICAS FINANCIERAS CONCEPTOS GENERALES OBJETIVOS Al finalizar el estudio del capítulo, el lector será capaz de: 1) Explicar y definir las matemáticas financieras y conceptuar sobre su importancia Más detalles Métodos Cuantitativos para la Toma de Decisiones. Daniel Serra de La Figuera
Métodos Cuantitativos para la Toma de Decisiones Daniel Serra de La Figuera Octubre Prólogo Este libro se refiere al uso de modelos cuantitativos en la resolución de problemas de gestión y administración Más detalles Split Delivery Vehicle Routing Problem: Heuristic based Algorithms
Split Delivery Vehicle Routing Problem: Heuristic based Algorithms Sandro Moscatelli Instituto de Computación, Facultad de Ingeniería Universidad de la República moscatel@fing.edu.uy Diciembre 2007 Resumen Más detalles CURSO DE METODOS NUMERICOS SEGUN DA PART E SOLUCION APROXIMADA DE ECUACIONES DE UNA VARIABLE
CURSO DE METODOS NUMERICOS SEGUN DA PART E SOLUCION APROXIMADA DE ECUACIONES DE UNA VARIABLE V. Muto Ecuaciones de una variable: Preliminares Cap. V CAPITULO V. SOLUCION APROXIMADA DE ECUACIONES DE UNA Más detalles 1.1 INTRODUCCIÓN INVESTIGACIÓN DE OPERACIONES I 2 INGENIERIA INDUSTRIAL 5TO SEM
1.1 INTRODUCCIÓN Sabemos que las matemáticas son una herramienta fundamental para realizar cálculos, operaciones y obtener resultados. Por lo tanto dentro del estudio de investigación de operaciones es Más detalles FUNCIONES. Una función tiene tres partes: Dos conjuntos A y B, no vacios, y una regla que relaciona dichos conjuntos.
FUNCIONES Muchas cantidades dependen de otras por ejemplo: - Los costos totales de producción, c, dependen de la cantidad de artículos a producir, q - El nivel de contaminación en una determinada región Más detalles 10 DECISIONES BAJO INCERTIDUMBRE 1
10 DECISIONES BAJO INCERTIDUMBRE 1 Ay, cómo es cruel la incertidumbre! Si ella merece mi dolor o yo la tengo que olvidar. Gonzalo Curiel. Incertidumbre...Aureliano saltó once páginas para no perder el Más detalles Como determinar el precio de exportación
Como determinar el precio de exportación ProMéxico tu aliado en el exterior www.promexico.gob.mx @ProMexicoTw ProMexicoOficial Formación del precio de exportación Actualización a marzo del 2010 3 Índice Más detalles cinve CAPITULO 1: Economía, principales conceptos Versión revisada Centro de Investigaciones Económicas
cinve Centro de Investigaciones Económicas CAPITULO 1: Economía, principales conceptos Versión revisada Montevideo, 5 de enero de 2005 1 Indice 1.1 LA ECONOMÍA COMO CIENCIA: DEFINICIÓN Y OBJETO DE ESTUDIO... Más detalles Benemérita Universidad Autónoma de Puebla
Benemérita Universidad Autónoma de Puebla Facultad de Ciencias Físico Matemáticas Aplicación de la Teoría de Inventarios a una empresa Poblana Tesis Que para obtener el Título de Lic. En Matemáticas Aplicadas Más detalles PARTE I. INTRODUCCION
PARTE I. INTRODUCCION TEMA I. CONCEPTOS Y PROBLEMAS BÁSICOS DE ORGANIZACIÓN ECONOMICA. LA ESCASEZ Y LA NECESIDAD DE ELEGIR: LA FRONTERA DE POSIBILIDADES DE PRODUCCIÓN. LA ECONOMIA Y LA NECESIDAD DE ELEGIR Más detalles Capítulo 2 Interés y descuento simple
Capítulo 2 Interés y descuento simple Introducción Los problemas de la teoría del interés son relativamente elementales, cada problema se restringe a calcular las siguientes variables: a) El capital invertido Más detalles COMPLETE STOCHASTIC FORESTRY PLANNING PROBLEM USING PROGRESSIVE HEDGING ALGORITHM
UNIVERSIDAD DE CHILE FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS DEPARTAMENTO DE INGENIERIA INDUSTRIAL COMPLETE STOCHASTIC FORESTRY PLANNING PROBLEM USING PROGRESSIVE HEDGING ALGORITHM TESIS PARA OPTAR Más detalles PROPUESTA DE CONSTRUCCIÓN DE UN INDICE DE PRECIOS Y CANTIDADES DEL POS COMO HERRAMIENTA PARA AJUSTAR ANUALMENTE LA UPC.
PROPUESTA DE CONSTRUCCIÓN DE UN INDICE DE PRECIOS Y CANTIDADES DEL POS COMO HERRAMIENTA PARA AJUSTAR ANUALMENTE LA UPC. DOCUMENTO TÉCNICO MINISTERIO DE LA PROTECCIÓN SOCIAL PROGRAMA DE APOYO A LA REFORMA Más detalles EJERCICIOS RESUELTOS DE PROGRAMACIÓN LINEAL USANDO LA HOJA DE CÁLCULO EXCEL
EJERCICIOS RESUELTOS DE PROGRAMACIÓN LINEAL USANDO LA HOJA DE CÁLCULO EXCEL (Ejercicios propuestos por los estudiantes) (No tienen un orden establecido por dificultad o por tipo de problemas, se incluyen Más detalles Unidad 10. Anualidades Simples Vencidas
Unidad 10 Anualidades Simples Vencidas INTRODUCCIÓN Una anualidad es una serie de pagos, por lo general iguales, efectuados a intervalos iguales de tiempo. El término anualidad parece implicar que los Más detalles Capítulo 18. Análisis de regresión lineal: El procedimiento Regresión lineal. Introducción
Capítulo 18 Análisis de regresión lineal: El procedimiento Regresión lineal Introducción El análisis de regresión lineal es una técnica estadística utilizada para estudiar la relación entre variables. Más detalles 1. Juegos de suma cero con dos jugadores
Teoría de juegos Jesús López Fidalgo Esta teoría está íntimamente relacionada con la teoría de la decisión. Lo que diferencia una de otra es el rival contra el que se entra en juego. En la teoría de la Más detalles Parte III. La economía de pleno empleo
Parte III La economía de pleno empleo De Gregorio - Macroeconomía Capítulo 6 La economía cerrada En los capítulos anteriores estudiamos los principales determinantes del consumo y la inversión. Asimismo, Más detalles APUNTES DE LA ASIGNATURA DE:
Tecnológico de Estudios Superiores del Oriente del Estado de México APUNTES DE LA ASIGNATURA DE: " PROFESOR: Ing. Israel Escobar Ojeda La Paz, Estado de México a 30 de julio de 2011 i Índice... i Administración Más detalles CAPÍTULO 2 APLICACIONES DE LA DERIVADA
CAPÍTULO 2 APLICACIONES DE LA DERIVADA 2.1 ANÁLISIS Y TRAZO DE CURVAS 2.1.1 Estudio de la Variación de una Función a) Tabulación y Graficación de una Función b) Dominio y Rango de una Función 2.1.2 Intersecciones Más detalles PROGRAMACIÓN LINEAL PARA ADMINISTRACIÓN
PROGRAMACIÓN LINEAL PARA ADMINISTRACIÓN RENZO DEVOTO RATTO EDUARDO RUIZ VIDAL EDICIONES UNIVERSITARIAS DE VALPARAÍSO PONTIFICIA UNIVERSIDAD CATÓLICA DE VALPARAÍSO Quedan rigurosamente prohibidas, sin la Más detalles Capacitadores. Diana Janet Belzusarri Padilla Artemio Gonzáles Ramírez Teodoro Llallihuamán Antúnez James Alexander Pajuelo Orbegoso
CAPÍTULO 1 Importancia e incidencia del estudio de posibilidades que ofrece el mercado y del resumen ejecutivo en los procesos de contrataciones a cargo de las Entidades públicas Capacitadores Diana Janet Más detalles LOCALIZACIÓN DE INSTALACIONES
AdministracióndelasOperaciones La localización de la instalación es el proceso de elegir un lugar geográfico para realizar las operaciones de una empresa. LOCALIZACIÓN DE INSTALACIONES Los gerentes de Más detalles Curso de Contabilidad para No Especialistas Texto del Alumno
CONTRALORÍA GENERAL DE LA REPÚBLICA Curso de Contabilidad para No Especialistas Texto del Alumno www.contraloria.cl ÍNDICE MATERIA PÁG. Presentación... 4 1.- Repaso de contenidos del diagnóstico... 6 2.- Más detalles 2016 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución