Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Programación entera




Enviado por Pablo Turmero



    Monografias.com
    1 Introducción y ejemplos de modelamiento a) Problema de
    la mochila. Una empresa está pensando invertir en cuatro
    proyectos diferentes, cada proyecto se finaliza a lo más
    en 3 años. Los flujos de caja requeridos en cada
    año junto con el Valor Presente Neto de cada proyecto,
    concluídos los años de ejecución, y las
    disponibilidades de recursos financieros se resumen en la
    siguiente tabla:

    Monografias.com
    Interesa determinar en cuáles proyectos invertir de modo
    de conseguir el mayor V.P.N. de la inversión.

    Monografias.com
    Variables de decisión: Función objetivo: Max 35×1 +
    18×2 + 24×3 + 16×4 Restricciones (tres alternativas): 1°
    Reinvirtiendo el dinero no utilizado en un período
    Año 1: 10×1 + 8×2 + 6×3 + 12×4 + s1 = 30 Año 2: 8×1
    + 15×2 + 4×3 + s2 = 15 + s1 Año 3: 18×1 + 16×3 ? 12 + s2
    xi ? {0,1} i = 1,2,3,4 (Gp:) { (Gp:) 1,2,3,4 (Gp:) (Gp:) i (Gp:)
    (Gp:) con (Gp:) (Gp:) i, (Gp:) (Gp:) proyecto (Gp:) (Gp:) el
    (Gp:) (Gp:) en (Gp:) (Gp:) invierte (Gp:) (Gp:) se (Gp:) (Gp:) si
    (Gp:) (Gp:) no (Gp:) (Gp:) si (Gp:) (Gp:) 0 (Gp:) (Gp:) (Gp:) =
    (Gp:) = (Gp:) 1 (Gp:) xi

    Monografias.com
    2° Sin invertir el dinero no utilizado en un período,
    pero utilizando el retorno de los proyectos concluídos:
    Año 1: 10×1 + 8×2 + 6×3 + 12×4 ? 30 Año 2: 8×1 +
    15×2 + 4×3 ? 15 + 16×4 Año 3: 18×1 + 16×3 ? 12 + 18×2 Xi ?
    {0,1} i = 1,2,3,4 3° Reinvirtiendo dinero no utilizado en un
    período y retorno de proyectos concluídos:
    Año 1: 10×1 + 8×2 + 6×3 + 12×4 + s1 = 30 Año 2: 8×1
    + 15×2 + 4×3 + s2 ? 15 + s1 + 16×4 Año 3: 18×1 + 16×3 ? 12
    + s2 + 18×2 Xi ? {0,1} i = 1,2,3,4

    Monografias.com
    Notar que el conjunto de las soluciones factibles es finito. Esto
    ocurrirá generalmente con los problemas de
    programación entera (puros). En el ejemplo, el
    número de soluciones factibles no supera el número
    de las soluciones binarias del problema (variables restringidas
    sólo a valores 0 o 1) que son 24 = 16, dado el
    número de variables utilizadas, de hecho las soluciones
    factibles son menos de 16 pues en particular xi=1 para i=1,2,3 y
    4 no satisface las disponibilidades de capital en cualquiera de
    las tres alternativas.

    Monografias.com
    Supongamos que adicionalmente la inversión efectuada
    requiera nuevas restricciones. Se debe invertir en al menos 1 de
    los 3 primeros proyectos: El proyecto 2 no puede ser tomado a
    menos que el proyecto 3 si sea tomado: Se puede tomar el proyecto
    3 o 4 pero no ambos: No se puede invertir en más de dos
    proyectos: (Gp:) 3 (Gp:) 2 (Gp:) x (Gp:) x (Gp:) £ (Gp:) 1
    (Gp:) 4 (Gp:) 3 (Gp:) £ (Gp:) + (Gp:) x (Gp:) x (Gp:) 2
    (Gp:) 4 (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) £ (Gp:) + (Gp:) +
    (Gp:) + (Gp:) x (Gp:) x (Gp:) x (Gp:) x (Gp:) 1 (Gp:) 3 (Gp:) 2
    (Gp:) 1 (Gp:) ³ (Gp:) + (Gp:) + (Gp:) x (Gp:) x (Gp:)
    x

    Monografias.com
    b) Cumplimiento de un subconjunto de las restricciones de un
    problema. Consideremos un problema que posee las siguientes
    restricciones: 12×1 + 24×2 + 18×3 ? 2400 15×1 + 32×2 + 12×3 ?
    1800 20×1 + 15×2 + 20×3 ? 2000 Supongamos que nos basta con
    obtener alguna solucion óptima que verifique el
    cumplimiento de al menos 2 de las 3 restricciones
    anteriores.

    Monografias.com
    Variables de decisión Cada inecuación anterior la
    reemplazamos por: 12×1 + 24×2 + 18×3 ? 2400 + M1 (1-y1) 15×1 +
    32×2 + 12×3 ? 1800 + M2 (1-y2) 20×1 + 15×2 + 20×3 ? 2000 + M3
    (1-y3) Además, debemos agregar la restricción que
    permita que a lo más una de las restricciones no se
    cumpla: y1 + y2 + y3 ? 2 Mi = constante lo suf. grande (Gp:) {
    (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) (Gp:) Si la
    restricción j no se satisface (Gp:) (Gp:) 0 (Gp:) (Gp:)
    (Gp:) = (Gp:) 1 (Gp:) yi (Gp:) La restricción j se
    satisface

    Monografias.com
    c) Inclusión de costos fijos. Supongamos que se desea
    tener lotes de compra de un producto dado, para satisfacer
    demandas que fluctúan en el tiempo sobre un horizonte de
    planificación dividido en T períodos. Asumimos
    conocidos: una estimación de la demanda dt, con t = 1, 2,
    …, T, los costos fijos asociados a la compra de una unidad pt,
    los costos asociados a la mantención de una unidad en
    inventario de cada período ht y los costos fijos asociados
    a la gestión de compra en el período t, st.
    Observación: no se permite unidades de faltante.

    Monografias.com
    Variables de decisión xt: número de unidades
    compradas en t. It: nivel de inventario al final del
    período t. yt 1 si se hace una compra en el período
    t. 0 si no t: 1, 2, …, T Función objetivo (Gp:) å
    (Gp:) = (Gp:) + (Gp:) + (Gp:) T (Gp:) t (Gp:) t (Gp:) t (Gp:) t
    (Gp:) t (Gp:) t (Gp:) t (Gp:) I (Gp:) h (Gp:) x (Gp:) p (Gp:) y
    (Gp:) s (Gp:) 1

    Monografias.com
    Restricciones xt + It-1 – It = dt t = 1, 2, …, T I0 =
    inventario inicial xt ? Mt yt t = 1, 2, …, T Mt = cte.
    grande

    Monografias.com
    d) Problema de cobertura: Dado un número de regiones o
    zonas en las cuales se ha subdividido una comuna, cuidad,
    país, etc., digamos que un total de m, se desea instalar
    un cierto número de servidores ( escuelas, centros de
    atención primaria de salud, compañías de
    bomberos, etc.) de entre un conjunto de n potenciales servidores
    ubicados en alguna de las zonas dadas. Se conoce la
    información relativa a que zonas pueden ser atendidas por
    cada uno de los n potenciales servidores, es decir, se conoce la
    matriz de incidencia A =( aij ) donde : si la zona i se puede ser
    atendida por el servidor j. si no i = 1,2,…..,m. j =
    1,2,…..,n. (Gp:) î (Gp:) í (Gp:) ì (Gp:) =
    (Gp:) 0 (Gp:) , (Gp:) 1 (Gp:) ij (Gp:) a

    Monografias.com
    Se desea determinar cuáles son los servidores que deben
    ser instalados de modo de dar cobertura a cada zona, dados los
    costos de instalación Cj del servidor j. Variables de
    desición : si se instala el servidor j. si no
    Función objetivo: Restricciones : Min ?j cjxj ; j
    =1,…,n. ?j aijxj ?1 ; i =1,…,m. Si adicionalmente, hay
    algún limite en el número de servidores que se
    pueden instalar, digamos k : ?j xj ? k (Gp:) î (Gp:)
    í (Gp:) ì (Gp:) = (Gp:) 0 (Gp:) , (Gp:) 1 (Gp:) j
    (Gp:) x

    Monografias.com
    e) Problema de transporte y localización : Si se tiene un
    conjunto de m clientes que demandan di unidades de un producto
    determinado. Una compañía desea satisfacer esas
    demandas desde un cierto conjunto de plantas elegidas de n
    potenciales lugares donde se instalarán. Sean cj los
    costos asociados a la instalación de la planta j , vj el
    costo unitario de producción de la planta j y tij el costo
    de transporte de una unidad desde la planta j al cliente i . Se
    desea decidir cuáles plantas abrir y el tamaño de
    cada una de modo de satisfacer las demandas estimadas.

    Monografias.com
    (Gp:) î (Gp:) í (Gp:) ì (Gp:) = (Gp:) 0 (Gp:)
    , (Gp:) 1 (Gp:) j (Gp:) y (Gp:) Si se abre la planta j. Si no xij
    = el número de unidades elaboradas en la planta j para
    satisfacer el cliente i, con j = 1,…,n. y i = 1,….,m. .
    Función objetivo : ?cjyj + ?vj (?xij) + ? ? tijxij costo
    instalación costo producción costo transporte

    Monografias.com
    Restricciones : demanda cliente i: ?xij ? di i = 1,….,m
    Relacionar variables de producción con las asociadas a la
    apertura de plantas (variables binarias ): ?xij ? Mjyj ; j =
    1,…,n donde Mj es una constante grande (por ejemplo, capacidad
    máxima de producción de la planta j). xij ? 0 ; yj
    ? { 0, 1}

    Monografias.com
    2 Resolución de problemas de Programación Entera
    Supongamos que tenemos el siguiente problema de
    programación lineal: PL) Max cTx s.a. A x = b x ? 0 Pero
    todas o una parte de las variables deben restringir su valor a
    números enteros, dando origen a un problema de
    Programación Entera (puro) o de Programación
    Entera- Mixta, respectivamente.

    Monografias.com
    Por ejemplo: PLE) Max cTx s.a. A x = b x ? 0, xj entero El
    problema PL) corresponde a la relajación continua del
    problema PLE), que resulta de eliminar las condiciones de
    integralidad de las variables de decisión en PLE). El
    valor óptimo de PL) provee sólo una cota superior
    del valor óptimo de PLE). Notar sin embargo, que si la
    solución óptima de PL) cumple con la integralidad
    de los valores requiridos, entonces esta solución es
    también solución óptima de PLE).

    Monografias.com
    Ejemplo PLE) Max x2 s.a. – 2×1 + 2×2 ? 1 + 2×1 + 2×2 ? 7 x1 ? 0,
    x2 ? 0 enteros 7 3.5 1.5 – 2×1 + 2×2 ? 1 2×1 + 2×2 ? 7 x1 x2 . .
    . . . . . . .

    Monografias.com
    Notar que en el ejemplo la solución óptima puede
    ser hallada por simple enumeración de todas las soluciones
    factibles, aquí las soluciones óptimas son: x1* = 1
    o x1* = 2 x2* = 1 x2* = 1 Esta alternativa de enumeración
    queda naturalmente restringida a problemas muy pequeños.
    Alternativamente, podemos resolver la relajación continua
    asociada al problema PLE). Si la solución óptima de
    la relajación continua da una solución entera, esa
    es la solución óptima no solo del problema lineal
    sino que también lo es del problema lineal entero.

    Monografias.com
    En el ejemplo, la solución de la relajación
    continua es: x1 = 3/2 x2 = 2 A partir de esta última
    solución podemos redondear o truncar los valores que no
    salieron enteros, obteniendo respectivamente en el ejemplo: x1 =
    2 x1 = 1 x2 = 2 x2 = 2 las cuales no son soluciones factibles de
    PLE), de modo que desde el punto de vista de una
    resolución numérica no es suficiente con resolver
    la relajación continua.

    Monografias.com
    Todavía podrían resultar soluciones factibles de
    PLE) pero no neceasariamente óptimas. Por ejemplo: PLE)
    Max f(x1, x2) = x1 + 5×2 s.a. x1 + 10×2 ? 10 x1 ? 1 x1 ? 0, x2 ?
    0 enteros Solución óptima de PL) x1 = 1
    f(1,9/10)=5,5 x2 = 9/10 Redondeando o truncando los valores x1 =
    1 infactible x1 = 1 f(1,0)=1 x2 = 1 x2 = 0 Pero la
    solución óptima de PLE) x1=0; x2=1; v(PLE)=5

    Monografias.com
    3 Método de Branch and Bound Consideremos el siguiente
    problema de programación entera: PLE) Max 21×1 + 11×2 s.a.
    7×2 + 4×2 ? 13 x1 ? 0 x2 ? 0 x1, x2 enteros Consideremos
    inicialmente la resolución de la relajación
    continua de PLE), que consiste en eliminar las condiciones de
    integralidad.

    Monografias.com
    x1 x2 1 2 3 21×1+11×2 21×1+11×2=39 7×1+4×2=13 X2 = 3 X2 = 2 X2 =
    1 X1 = 1 X1 = 2 13/7 sol. relajada 3/2

    Monografias.com
    Descripción del método Branch and Bound
    (maximización) Paso 0 Hacer P0, la relajación
    continua de PLE) fijar la cota inferior del v(PLE) en -?. Paso 1
    Seleccionar un problema no resuelto, Pi Resolver Pi) como
    problema de programación lineal. Agotar este problema,
    usando: (i) que se encontró una solución entera
    (ii) que el problema resulta infactible (iii) que el problema no
    provee un valor mejor que la actual cota del valor óptimo
    v(PLE).

    Monografias.com
    Si el problema Pi resulta agotado y da solución entera,
    mejorar el valor de la cota inferior de v(PLE). Si todos los
    problemas están agotados parar. Solución
    óptima de PLE), la solución entera asociada a la
    actual cota inferior de v(PLE), si existe (si no existe entonces
    PLE) es infactible) Si el problema no está agotado pasar
    al paso 2.

    Monografias.com
    Paso 2 Seleccionar una variable xj=ûj, cuyo valor en la
    solución óptima de Pi) no de entero. Eliminamos la
    región correspondiente a ?ûj? < ûj <
    ?ûj? +1 Crear dos nuevos problemas de programación
    lineal que incorporan a Pi) dos restricciones mutuamente
    excluyentes: xj ? ?ûj? xj ? ?ûj? +1 una en cada
    problema y volver al paso 1.

    Monografias.com
    (Gp:) P0 (Gp:) P1 (Gp:) P2 (Gp:) P11 (Gp:) P12 (Gp:) P121 (Gp:)
    P122 (Gp:) P1211 (Gp:) P1212 (Gp:) infactible (Gp:) infactible
    (Gp:) infactible (Gp:) x2?4 (Gp:) x2?2 (Gp:) x1?2 (Gp:) x1?1
    (Gp:) x2?3 (Gp:) x2?1 (Gp:) x1?1 (Gp:) x1 = 13/7 x2 = 0 z = 39
    (Gp:) x1 = 1 x2 = 3/2 z = 37.5 (Gp:) x1 = 1 x2 = 1 z = 32 (Gp:)
    x1 = 5/7 x2 = 2 z = 37 (Gp:) x1 = 0 x2 = 13/4 z = 35.75 (Gp:) x1
    = 0 x2 = 3 z = 33 P0) Relajación continua -?< z ? 39
    P1) Max 21×1 + 11×2 s.a. 7×1 + 4×2 ? 13 x1 ? 1 x1 ? 0 x2 ? 0 P2)
    Max 21 x1 + 11×2 s.a. 7×1 + 4×2 ? 13 x1 ? 1 x2 ? 1 x1 ? 0 x2 ? 0
    De donde 32 ? z ? 39 ? ? ? Solución óptima X1* = 0
    X2* = 3 Z = 33

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter