Programación Entera Introducción y casos de aplicación

Unidad 5:

Programación Entera Introducción y casos de aplicación

5.1 DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA

Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras solo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones lógicas.

Este tipo de modelos permite representar sistemas mucho más complejos. A cambio, la resolución de los mismos se complica excesivamente. No se puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del ´optimo.

En general, un problema de Programación Lineal Entera puede surgir por varios motivos:

Directos: las variables que se utilizan son cuantitativas y enteras.

Codificados: Se utilizan variables enteras para representar el cumplimiento o no de ciertas condiciones (normalmente son variables 0−1).

Transformados: Las variables enteras aparecen para facilitar la modelización de algunas condiciones (implicaciones, disyunciones, etc.).

Existen tres tipos de modelos de programación entera:

Pura: Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros. Por ejemplo Min 6×1 + 5×2 + 4×3 s.a. 108×1 + 92×2 + 58×3 >= 576 7×1 + 18×2 + 22×3 >= 83 x1, x2, x3 >= 0 y enteros Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteros (o sea las condiciones de integralidad) seria un problema de programación lineal

Binaria: En algunos problemas se restringe el valor de las variables a 0 o 1. Son de particular interés debido a que se pueden usar las variables 0–1 para representar decisiones dicotómicas (sí o no). Programación Entera Binaria. Existen dos métodos para generar las restricciones especiales que fuercen la solución óptima del problema, hacia la solución óptima entera deseada: - Método de ramificar y acotar

METODO DE RAMIFICACION 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.

Por ejemplo si se resuelve la relajación del siguiente problema:

max z = 3x1 + 2x2

s.t. 2x1 + x2 <= 6

x1; x2 ..Z

se obtiene como solución: x1 = 0, x2 = 6 y z = 12, que corresponde exactamente a la solución del IP original.

MIXTA: Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad. Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier número no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM). Por ejemplo, supóngase que en el problema solo x1 y x2 deben ser enteros y x3 no.

MÉTODOS DE RESOLUCIÓN

Aunque en un principio pueda parecer que los problemas lineales enteros son más fáciles de resolver que los continuos, dado que el número de soluciones factibles a analizar, cuando el conjunto de oportunidades está acotado, es finito, éste número suele ser lo suficientemente grande (en un problema binario con n variables el número de soluciones factibles a estudiar es 2n ) como para que resulte imposible su comparación.

La resolución del PLA en primer lugar, tiene una ventaja y es que si la solución a dicho problema verifica las condiciones de integridad de las variables, esta será la solución al problema entero, con lo cual no será necesario aplicar ninguna técnica especial para resolverlo.

Si la solución al PLA no verifica las condiciones de integridad , lo que ocurre la mayoría de las veces, entonces habrá que utilizar algún método que nos permita resolver el problema entero. Algo que no debemos hacer, es caer en la tentación de redondear la solución obtenida al PLA a valores enteros y tomarla como válida, pues si bien esto puede ser aceptable en aquellos problemas en el que los valores de las variables son muy grandes y en consecuencia el error puede ser mínimo, en general nos puede generar dos graves `problemas que son: a) La solución obtenida por redondeo no es la óptima e incluso puede ser muy diferente de ella, como ocurre con el siguiente problema

b)

Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 ≤ 24

8x1 + 3x2 ≤ 24

x1≥0,x2≥0, x1,x2∈Z+ resolviendo el PLA asociado

Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 ≤ 24

8x1 + 3x2 ≤ 24

x1≥0,x2≥0

Solución x1=2,x2=8/3,F(X)= 128/3

Redondeo al punto x1=2,x2=3, infactible

Redondeo al punto x1=2,x2=2 F(X)=36

Solución optima: x1=0,x2=4, F(X)=40.

Así pues si queremos obtener la solución óptima al problema entero, necesariamente habremos de utilizar algún método de resolución para problemas enteros. Únicamente se trataran los dos métodos, que consideramos más representativos y además pioneros en la resolución de problemas enteros, como son los métodos de corte (algoritmo fraccional de Gomory) y el de ramificación y acotación (Branch and Bound).

5.3 METODO RAMIFICAR Y ACOTAR

El método de ramificación y acotación comienza por resolver el PLA, de modo que si la solución al PLA verifica las condiciones de integridad, entonces también es la solución al problema entero, en caso contrario se comienza con la ramificación del problema.

La ramificación consiste en dividir cada problema en dos nuevos subproblemas, obtenidos mediante la imposición de restricciones excluyentes que dividen el conjunto de oportunidades del problema original en dos partes, pero eliminando en ambas partes la solución no entera del problema original. Cuando en la solución al PLA una variable que ha de ser entera xi toma el valor xbi no entero, entonces se generan a partir de dicho valor dos restricciones xi ≤ [xbi] y xi ≥ [xbi]+1 (siendo [xbi] la parte entera por defecto de xbi ), que añadidas cada uno por separado al problema original, da lugar a dos nuevos subproblemas. Vamos a explicar este proceso a traves de un ejemplo particular:

EJEMPLO:

Max F(x) = 4x1 + 5x2 (1)

...