Programacion entera

PROGRAMACION ENTERA

INTRODUCCION

Un enfoque primitivo de resolución consiste en evaluar cada una de las combinaciones de valores enteros para las variables del problema. Pero en este caso, analizar diez variables y diez valores en un problema tendríamos un número grande (diez mil millones) de posibles soluciones, lo que hace necesario planteamientos de solución inteligentes. Estos se handirigido por una parte hacia los "métodos exactos", es decir, aquellos que conducen a una solución óptima exacta para el problema combinatorio empleando técnicas que reduzcan la búsqueda de soluciones.
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 queeste tipo de variables permiten representar condiciones lógicas. Este tipo de modelos permite representar modelos mucho más complejos, aunque 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 óptimo. Siendo así que problemas con una sola decenas de variables pueden ser casi imposibles deresolver
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 LinealEntera Binaria (Digital).

DEFINICIÓN DE MODELOS
Un modelo es una representación de un objeto, sistema o idea, de forma diferente al de la entidad misma. El propósito de los modelos es ayudarnos a explicar, entender o mejorar un sistema. Un modelo de un objeto puede ser una réplica exacta de éste o una abstracción de las propiedades dominantes del objeto.
El uso de modelos no es algo nuevo. Elhombre siempre ha tratado de representar y expresar ideas y objetos para tratar de entender y manipular su medio. Un requerimiento básico para cualquier modelo, es que debe describir al sistema con suficiente detalle para hacer predicciones válidas sobre el comportamiento del sistema. Más generalmente, las características del modelo deben corresponder a algunas características del sistema modelado.Un modelo se utiliza como ayuda para el pensamiento al organizar y clasificar conceptos confusos e inconsistentes. Al realizar un análisis de sistemas, se crea un modelo del sistema que muestre las entidades, las interrelaciones, etc. La adecuada construcción de un modelo ayuda a organizar, evaluar y examinar la validez de pensamientos.
Al explicar ideas o conceptos complejos, los lenguajesverbales a menudo presentan ambigüedades e imprecisiones. Un modelo es la representación concisa de una situación; por eso representa un medio de comunicación más eficiente y efectivo.

METODO DE RAMIFICAR Y ACORTAR
Resolución de problemas de programación entera pura mediante el método de ramificar y acotar

En la práctica, la mayoría de los problemas de programación entera se resuelven medianteel uso de la técnica de ramificar y acotar los métodos de ramificar y acotar encuentra la solución óptima para una PE mediante la enumeración eficiente de los puntos en la región factible de un subproblema. Antes de explicar cómo funciona la ramificación y el acotamiento, es necesario hacer la siguiente observación elemental, pero importante: si resuelve la relajación PL de una PE pura y obtieneuna solución en la cual todas las variables son números enteros, entonces la solución óptima de la relajación L será también la solución óptima del PE.
Para darse cuenta de la validez de esta observación, considérese la PE siguiente:
Max z = 3X1+X2
S.a. = 2X1+X2 ≤6
X1, X2 ≥0;X1,X2 entero
La solución óptima para la relajación PL de esta PE puro es X1 = 0, X2 = 6, z = 12. Ya que esta...