Introducción y casos de aplicación

Programación entera

Introducción y casos de aplicación.

Definición y modelos de programación entera y binario.

Método de Gomory.

Método de bifurcación y acotación.

Uso de software.

INTRODUCCIÓN Y CASOS DE APLICACIÓN

Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de modelos lineales enteros y sus métodos de solución es en la actualidad bastante extenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad. No siempre es admisible que las variables de un PL tomen valores continuos, existen: • • Decisiones dicotómicas (si-no) Decisiones que deben tomarse en unidades discretas

Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta. En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital); si se requiere que solamente algunas de las variables tomen valores de cero o uno, se tiene un problema de Programación Lineal Entera Binaria Mixta. La PE tiene gran cantidad de aplicaciones en todos los campos.

3

Hay problemas que no pueden resolverse con las técnicas actuales por: • • Disponibilidad de tiempo de ordenador Capacidad de memoria

Para evitar esto parece sensato calcular la solución de un PE redondeando la solución continua. Pero el redondeo no es aconsejable debido a: • La solución redondeada no es necesariamente óptima. En muchos casos, ni siquiera estará cerca del óptimo. • La solución redondeada puede no ser factible.

Programacion entera

* Tipos de modelos de Programación Entera:

* Programación Entera es un término general para los modelos de programación matemática que presentan condiciones de integridad (condiciones que estipulan que algunas o todas las variables de decisión deben tener valores enteros).

* Ya hemos apuntado que los modelos de programación lineal entera son modelos de programación lineal que tienen la característica adicional de que algunas de las variables de decisión deben tener valores enteros. Existen diversas clasificaciones de esta categoría de modelos.

* Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros.

* P.E pura: Todas las variables de decisión tienen valores enteros.

* P.E mixta (PEM) : Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad

* 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) sería un problema de programación lineal

* Programas Enteros Mixtos

* 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 anterior solo x1 y x2 deben ser enteros y x3 no. El problema resultante es:

* 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; x1 y x2 enteros

Programas Enteros 0–1

* En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 0–1. Son de particular interés debido a que se pueden usar las variables 0–1 para representar decisiones dicotómicas (sí o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0–1.

* 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.

* - Método de planos de corte.

* En ambos métodos las restricciones agregadas eliminan partes del espacio de soluciones, pero nunca alguno de los puntos enteros factibles. Desafortunadamente, ninguno de los dos métodos es efectivo en la solución de problemas de programación lineal entera. No obstante los métodos de ramificar y acotar son mucho mejores en cuanto al cálculo se refiere que los métodos de plano de corte. Por esta razón, la mayoría de los códigos comerciales se basan en el procedimiento de ramificar y acotar.

METODO DE PLANOS DE CORTE (METODO DE GOMORY)

En optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.

En primer lugar, hemos de resolver el problema relajado, es decir sin tener en cuenta que algunas o todas las variables del problema deben ser enteras, si la solución obtenida x* es entera, ésa será la solución a nuestro problema original, en caso contrario se construye un plano de corte que divide el conjunto de oportunidades x, en dos subconjuntos, uno de ellos contiene la solución no entera x* y el otro contiene el conjunto de soluciones enteras del problema.

A partir de una solución no entera se van construyendo planos de corte, de tal forma que los cortes asociados a los mismos generan de forma iterada la solución

...