PROGRAMACIÓN LINEAL ENTERA OPTIMIZACIÓN I

ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL[pic 1]

TEMA:

PROGRAMACIÓN LINEAL ENTERA

ASIGNATURA:

OPTIMIZACIÓN I

INTEGRANTES:

PERÍODO LECTIVO:

2016-2017

1.- Introducción

Dentro del estudio de Investigación de Operaciones es común tener que resolver problemas en que se necesite obtener valores enteros como posibles soluciones y la Programación Lineal Entera nace como respuesta a estos problemas, presentando resultados que no se encuentren dentro de un intervalo continuo. La integralidad para las variables de decisión se muestra como condición en una gran cantidad de problemas lineales. Por ejemplo, las variables pueden ser valores binarios, es decir que pueden ser 0 y 1, o también pueden ser valores enteros no negativos como 0, 1, 2, etc.

A pesar de que los problemas en general de P. L. E. puedan parecer sencillos a simple vista, por lo que bastaría con calcular el valor de la variables y se escoge el óptimo dentro del conjunto solución; en la práctica, dentro de situaciones reales, donde hay una gran variedad de soluciones, el análisis individual de cada una de las variables se vuelve complejo. Es necesario mencionar que los métodos de redondeo, en donde se transforma a número entero, no facilitan en la mayoría de los casos las mejores soluciones, puesto que muchas veces incumple algunas restricciones que muestra el problema.

Es por esta causa que a lo largo del tiempo han surgido una colección de métodos para la resolución de problemas P. L. E., generalmente basados en las particularidades de cada problema, con el propósito de facilitar su resolución y obtener sus respectivos valores dentro del menor tiempo posible. Sin embargo, no hay un método genérico para problemas lineales enteros como lo es el método Simplex dentro de la Programación Lineal.

2.- Programación Lineal Entera

El modelo de P. L. E. es una extensión de la Programación Lineal, pero que tiene como característica específica la restricción de que el conjunto solución de las variables sean valores enteros. También se caracteriza por presentar algunos sistemas de mayor complejidad.

Un programa entero recibirá el nombre ya sea puro o mixto dependiendo según su ausencia de las condiciones de totalidad o integridad.

2.1.- Formulación Matemática

En un problema de Programación Lineal Entera con n variables y m restricciones se trata de encontrar el valor de las variables  : [pic 2]

[pic 3]

[pic 4]

[pic 5]

[pic 6]

[pic 7]

[pic 8]

Donde, si J es un subconjunto de , las variables de decisión se pueden encontrar condicionadas. [pic 9]

Según las restricciones, la P. L. E. se divide en tres distintos tipos de modelo que son:

• Programación Lineal Entera Pura: Todas las variables de decisión poseen valores enteros. Conserva una gran similitud en su metodología para resolver problemas con los modelos de la Programación Lineal.

[pic 10]

[pic 11]

 Por ejemplo:

• Programación Lineal Entera Binaria: También llamado P.L.E. Cero-Uno. Son variables en donde se incluyen decisiones de si o no que están interrelacionadas. Dentro de este tipo solo hay dos posibles respuestas y se las puede representar por medio de variables de decisión pero con una restricción de dos posibles valores, usualmente se toman los valores 0 y 1, usados también en datos probabilísticos.

[pic 15]

[pic 16]

Por ejemplo:

• Programación Lineal Entera Mixta: Se considera sólo cuando algunas de las variables deben ser enteros y para el resto de variables se cumple la suposición de divisibilidad.

[pic 21]

[pic 22]

Por Ejemplo:

Técnicas de Resolución de la Programación Entera

• Método Enumeración Exhaustiva
• Método Relajación Lineal
• Método de Ramificación y Acotación (Branch and Bound)
• Método de Ramificación y corte (Branch and Cut)
• Método de los Planos de Corte o Gomory

Método Enumeración Exhaustiva

Consiste en enumerar todas las soluciones posibles, a partir de los valores tomados para las variables enteras y realizar todas las combinaciones posibles hasta encontrar una combinación que nos proporcione el valor óptimo de la función objetivo y que cumpla con todas las restricciones del problema.

...