INSITUTO TECNOLOGICO DE VILLAHERMOSA

INGENIERIA INDUSTRIAL

INVESTIGACION DE OPERACIONES 1

UNIDAD 5

INTRODUCCION A LA PROGRAMACION ENTERA Y CASOS DE APLICACIN

JAIRO MANUEL CHACN MONTEJO

INTRODUCCION

Como introduccin tenemos que la programacion entera nos ayuda en facilitar la toma de deseciones sobre diversos problema, la programacin entera es una herramienta importante en la invstigacion de operaciones que se aplica en diferentes campos de la vida diaria. La programacin entera o prgramacion lineal s una herramienta matematica que a travez de formulas y algoritmos nos simplican losproblemas y nos ayudan a tomar una mejor decisin.

5 introducciones a la programacin entera

Los problemas de programacin lineal en que se requiere que algunas o todas las variables tomen valores enteros, son de programacin entera. La programacin entera a llegado a ser un rea muy especializada de la ciencia de la administracin. Un enfoque prctico: Una empresa que fabrica costales para alimento de ganado y una solucin lineal requiere que se fabriquen 3000,472 costales, carecer de sentido. En tales situaciones, a menudo se adopta la solucin no entera al requerimiento de enteros simplemente redondeando los resultados al entero ms prximo. Esto produce lo que se llama la solucin redondeada. Mediante ese recurso se obtienen soluciones aceptables para el administrador en aquellas situaciones en las que, con sentido practico, sencillamente no importa el redondeo. Por ejemplo, no hay diferencia significativa, ya sea en la funcin objetivo o en las restricciones, entre producir 19.283,64 y 19.283 costales de alimento para ganado, En realidad, probablemente baste para el ajuste de los datos del modelo que satisfaga al administrador una produccin cercana a los 19.000 costales. Cuando tienen importancia las soluciones enteras Existen muchos problemas importantes en los que la solucin redondeada simplemente no funciona. Esta complicacin puede deberse a la escala de las variables por considerar. Por ejemplo, si la solucin de un modelo de programacin lineal recomienda que la Boeing construya 11,6 aparatos 747 y 6,8 aparatos 727, el administrador probablemente no quedara contento con la simple medida de tomar la decisin de construir 11 de los primeros y 6 de los segundos, o cualquier otra solucin redondeada. La magnitud del rendimiento y la asignacin de recursos asociados con cada unidad del problema aconsejan determinar la mejor solucin entera posible. Con otro ejemplo, s vera que muchos modelos usan variables enteras para indicar decisiones lgicas Grandes limitaciones Suposicin de divisibilidad

Exigir Valores enteros

Problema De Programacin entera (PE)

5.1. Definicin y modelos de programacin entera

Tipos Decisin entero de Variables de

Modelo

Completamente (PLE)

Todas son enteras

Mixto (MILP)

Algunas, pero no todas son enteras Todas son binarias (0 1)

Binaria (BILP)

Modelo completamente entero: Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisin tengan valores enteros. Por ejemplo: * Min 61 + 52 + 43 * s.a. 1081 + 922 + 583 >= 576 * 71 + 182 + 223 >= 83 * x1, x2, x3 ><0 y enteros Modelo Mixto: Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier numero no negativo (es decir, cualquier valor continuo) se llama programacin lineal entera mixta (PLEM). Por ejemplo, supngase que en el problema anterior solo x1 y x2 deben ser enteros y x3 no. El problema resultante es: * Min 61 + 52 + 43 * s.a. 1081 + 922 + 583 >= 576 * 71 - 182 + 223 >= 83 * x1, x2, x3 >=0; x1 y x2 enteros Modelo Binario: En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 01. Son de particular inters debido a que se pueden usar las variables 01 para representar

decisiones dicotmicas (s o no). Diversos problemas de asignacin, ubicacin de plantas, planes de produccin y elaboracin de cartera, son de programacin lineal entera 01. Existen dos mtodos para generar las restricciones especiales que fuercen la solucin ptima del problema, hacia la solucin ptima entera deseada: - Mtodo de ramificar y acotar. - Mtodo de planos de corte. En ambos mtodos las restricciones agregadas eliminan partes del espacio de soluciones, pero nunca alguno de los puntos enteros factibles. Desafortunadamente, ninguno de los dos mtodos es efectivo en la solucin de problemas de programacin lineal entera. No obstante los mtodos de ramificar y acotar son mucho mejores en cuanto al calculo se refiere que los mtodos de plano de corte. Por esta razn, la mayora de los cdigos comerciales se basan en el procedimiento de ramificar y acotar.

5.2. Mtodo ramificar y acotar

Pasos: Ramificacion: Variables Acotacin: Valor de la funcin objetivo A partir de la solucin del PLA: La ramificacin consiste en dividir cada problema en dos nuevos subproblemas, obtenidos mediante la imposicin de restricciones excluyentes que dividen el conjunto de oportunidades del problema original en dos partes, pero eliminando en ambas partes la solucin no entera del problema original. Si 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 aadidas cada uno por separado al problema original, da lugar a dos nuevos subproblemas. Por ejemplo la variable x1 tiene que ser entera, pero en la solucin anterior (PLA u otro), la variable vale: x1 = 6.8. Esta solucin no es valida, ya que no es admisible un valor fraccional, por tanto se introduciran las siguientes restricciones: x1 6 y x1 7, de forma que se ha eliminado una porcin del conjunto donde no hay soluciones enteras, pero se mantienen las enteras: Asi se prosigue con todas las variables hasta que sean enteras. Si al proceso de ramificacin no se mejora de alguna forma, llegariamos a analizar TODAS las soluciones enteras (Enumeracion Total). Por eso, se aade la fase de Acotacin, esta tiene que ver con el valor de la funcin objetivo. A medida que se va ramificando se obtienen soluciones enteras y otras que no lo son. No podemos asegurar que la primera solucin entera obtenida sea la solucin optima, sino que es necesario comprobar si existen otras soluciones enteras o no. El anlisis del PLA: Ramificacin se realiza siempre a partir de aquel problema que tiene el mejor valor de la funcin objetivo, y siempre que exista alguna solucin (no entera) con un valor de la funcin objetivo

5.3. Metodos Planos cortantes

Como en el algoritmo de ratificacin y acotamiento, el del plano cortante tambin se inicia en la solucin optima del programa lineal continuo. Al espacio de soluciones se agregan restricciones especiales, llamadas cortes, en una forma que produzca un punto extremo entero. Maximizar Z = 7 X1 + 10 X2 S.A. - X1 + 3 X2 6 7 X1 + X2 35 X1, X2 0 y enteras. El algoritmo del plano de corte modifica el espacio de soluciones agregando cortes que producen un punto extremo entero ptimo. La siguiente figura muestra un ejemplo de dos cortes de esos. Se parte del ptimo del programa lineal continuo, Z = 66 , X1 = 4 , X2 = 3 , a continuacin se agrega el corte I, que produce la solucin lineal optima continua Z= 62, X1 = 4 [pic], X2 = 3. A continuacin se agrega el corte II, que junto con el corte I y las restricciones originales, llega al optimo del programa lineal Z = 58, X1 = 4, X2 = 3. La ltima solucin es entera, que era lo que se buscaba. Los cortes agregados no eliminan alguno de los puntos enteros factibles originales, pero deben pasar por al menos un punto entero, factible o no factible. Estos son los requisitos bsicos de cualquier corte.

5.4. Algoritmo aditivo de balas

Ejemplo de Algoritmo Aditivo: Resolver el siguiente problema 0-1: Max w=3y1+2y2-5y3-2y4+3y5 Sujeta a: y1 + y2 + y3 + 2y4 - y5 " 4 7y1 +3y3 - 4y4 - 3y5 " 8 11y1 -6y2 +3y4 - 3y5 " 5 y1,y2,y3,y4,y5 = (0_1) El problema se puede poner en la forma inicial requerida por el algoritmo aditivo, utilizando las siguientes operaciones: Multiplique la funcin objetivo por -1. Multiplique la tercera restriccin por -2. Aada las variables s1,s2 y s3 para convertir las tres restricciones en ecuaciones. Sustituya y1=1-x1 , y2=1-x2 , y5=1-x5 , y3=x3 , y y4=x4 para producir todos los coeficientes objetivo positivos.

La conversin da por resultado la siguiente funcin objetivo: Min z'=3x1+2x2+5y3-2x4+3x5-8 Para mayor facilidad, ignoremos la constante -8 y reemplazaremos z' +8 con z, de manera que el problema convertido resultante se lee como: Min z=3x1+2x2+5y3-2x4+3x5 Sujeta a: x1 - x2 + x3 + 2x4 - x5 -s1 = 1 -7x1 +3x3 - 4x4 - 3x5 -s2 = -2 11x1 -6x2 -3x4 - 3x5 -s3 = 5 x1,x2,x3,x4,x5 = (0_1) Debido a que el problema modificado busca la minimizacin de una funcin objetivo con todos los coeficientes positivos, una solucin inicial lgica debe consistir en variables binarias todas cero. En este caso, las holguras actuarn como

variables bsicas y sus valores los dan los lados derechos de la ecuacin. La solucin se resume en la siguiente tabla: Solucin bsica factible Soluci n 1 -3 -3 3 010 001 2 1

X1

X2

X3

X4 2 S1

X5 -1 -7 11 3

S1 1 0 -6 2

S2 0 3 0 5

S3 0 -4 -3 2

S1

-1

-1

S1 Coeficientes objetivo

Dada una solucin binaria inicial toda cero, la solucin de holgura asociada es: (s2 ,s2 ,s3 ) = (1,-2,-1) , z=0 Si todas las variables fueran no negativas, concluiramos que la solucin binaria toda cero es ptima. Sin embargo, debido a que algunas de las variables son no factibles (negativas), necesitamos elevar una o ms variables binarias al nivel 1 para lograr la factibilidad (o concluimos que el problema no tiene una solucin factible). La elevacin de una (o de algunas) de las variables binarias cero al nivel 1 ocurre en el algoritmo aditivo una a la vez. La variable elegida se llama variable de ramificacin y su seleccin se basa en el empleo de pruebas especiales. La variable de ramificacin debe tener el potencial de reducir la no factibilidad de las holguras. Si venos la tabla anterior x3 no se puede seleccionar como una variable de ramificacin, debido a que sus coeficientes de restriccin en la segunda y tercera restricciones son no negativos. Por tanto, la determinacin de x3=1 solo puede empeorar la no factibilidad de s2 y s3. A la inversa, cada una de las variables restantes tiene por lo menos un coeficiente de restriccin negativo en las restricciones 2 y 3, de all que una combinacin de estas variables puede producir holguras factibles. Por consiguiente, podemos excluir a x3 ya a considerar x2, x3, x4 y x5 como las nicas candidatas posibles para la variable de ramificacin. La seleccin de la variable de ramificacin entre las candidatas x2, x3, x4 y x5 se basa en el empleo de la medida de no factibilidad de holgura. Esta medida, que se basa en la suposicin de que una variable cero xj se elevar al nivel 1, se define como Ij = " min {0,si-aij} Donde s1 es el valor actual de la variable i y aij es el coeficiente de restriccin de la variable x1 en la restriccin i.

De hecho, Ij no es ms que la suma de las variables negativas resultantes de elevar xj al nivel 1. La frmula, aparentemente complicada, se puede simplificar a: Ij = " (negativos sj valor dado xj=1) Por ejemplo, cuando determinamos x1=1, obtenemos s1=1-(-1)=2, s2= -2-(-7)=5 y s3= -1-11= -12. As I1= -12. De manera similar I2=-2, I4=-1 y I5=0 (recordando que x3 se excluy como no prometedora). Debido a que I5 produce la medida ms pequea de no factibilidad, se selecciona x5 como la variable de ramificacin. Fa figura 9-10 muestra las dos variables asociadas con x5=1 y x5=0 y la creacin de nodos 1 y 2. el nodo 1 produce los valores de holguras factibles (s1 ,s2 ,s3 )= (2,1,2) y z=3. por tanto, se sondea el nodo 1 y z=3 se define como la cota superior actual sobre el ptimo valor objetivo.

Despus de sondear el nodo 1, avanzamos al nodo, para lo cual x5=0. Aqu tenemos: (s1 ,s2 ,s3 )= (-1,2,-1), z=2 Que no es factible. Las variables x1,x2,x3 y x4 son las candidatas para la variable de ramificacin. (Observe que aun cuando las soluciones en el nodo 0 u el nodo 2 son idnticas, el nodo 2 difiere en que x5 ya no es candidata para la ramificacin. Para las variables restantes, x2 y x4, calculamos las medidas de factibilidad como: I2 = -2 , I4 = -1 Por consiguiente, x4 es la variable de ramificacin en el nodo 2. La figura 9-11 muestra las ramificaciones x4 = 1 y x4 = 0, que conducen a los nodos 3 y 4. en el nodo 3 (definido al determinar x5 = 0 y x4 = 1), obtendremos: (s1 ,s2 ,s3 )= (-1,2,2), z=2

sta solucin an no es an factible. Las candidatas para la ramificacin son x1,x2 y x3. Sin embargo la elevacin cualquiera de stas variables al nivel 1 empeorar el valor de z en relacin a la cota superior actual z=3. Por consiguiente, todas las variables candidato se excluyen y el nodo 3 se sondea. Despus, en el nodo restante 4, definido por x5 = x4 = 0 tenemos: (s1 ,s2 ,s3 )= (1,-2,-1), z=0 Las variables x5 y x3, se excluyen por medio de la prueba de la cota superior. (Observe que tambin se puede excluir debido a que no reduce la factibilidad de la holgura). La variable faltante x2 no puede ser excluida por la cota superior o por la promesa de factibilidad. Por tanto x2 es la variable de ramificacin. La figura 9-12 muestra la adicin de los nodos 5 y 6 que emanan el nodo 4. en el nodo 5 tenemos: (s1 ,s2 ,s3 )= (2,-2,5), z=2 Y x1 y x3 como las candidatas a la ramificacin. La variable x1 se excluye por medio de la prueba de la cota superior y x3 se excluye por medio de las pruebas tanto de la factibilidad de la holgura como de la cota superior. Esto significa que el nodo 5 se sondea. El nodo 6 tambin es sondeado debido a que ni x1 ni x3 pueden producir una mejor solucin factible.

Ahora que se han sondeado todos los pendientes en la anterior figura y termina el algoritmo de R y A la solucin ptima est asociada con el nodo 1, es decir, x5 = 1, z = 3 y todas las dems variables son cero. En trminos de las variables originales, la solucin es y1= y2=1 y y3= y4= y5= 0 con w=5. La figura anterior muestra que, mientras ms pequeo es el nmero de ramificaciones conducentes a un nodo sondeado, ms eficiente es el algoritmo. Por ejemplo, el nodo 1 se define fijando una ramificacin (x5=1) y su sondeo implica automticamente de 25-1 = 16 soluciones binarias (todas aquellas que tienen x5=1). A la inversa, el nodo 3 se define fijando dos variables binarias y su sondeo implcitamente implica de 25-1=8 soluciones binarias nicamente.

5.5. Programacin dinmica

La programacin dinmica es un enfoque general para la solucin de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolucin futura del sistema, afectando a las situaciones en las que el sistema se encontrar en el futuro (denominadas estados), y a las decisiones que se plantearn en el futuro. Conviene resaltar que a diferencia de la programacin lineal, el modelado de problemas de programacin dinmica no sigue una forma estndar. As, para cada problema ser necesario especificar cada uno de los componentes que caracterizan un problema de programacin dinmica. El procedimiento general de resolucin de estas situaciones se divide en el anlisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la ltima y pasando en cada iteracin a la etapa antecesora. El anlisis de la primera etapa finaliza con la obtencin del ptimo del problema. MODELOS DE PROGRAMACIN DINMICA * Problema de la diligencia * Problema de la mochila * programacin de produccin e inventarios

Conclusin

En conclusin tenemos la importancia de la programacin entero o lineal y su campo de aplicacin; que es una herramienta importante en la investigacin de operaciones y en la vida diaria que nos ayuda a simplificar los problemas a travez de distintas formulas, algoritmos y la aplicacin de modelos matematicos.