Programación Lineal

•

•

•

PROGRAMACIÓN ENTERA: P.E.

Programación Lineal con la restricción adicional de que los valores de las variables de decisión son enteros. (Vs suposición de divisibilidad)

* 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 toman valores reales o continuos (cumplen con la suposición de divisibilidad).

La programación entera tiene que ver con la solución de problemas de programación matemática en a las cuales algunas o todas las variables solo pueden tomar valores enteros o negativos.

Un programa entero reside el nombre de mixto o puro, dependiendo de si en ausencia de las condiciones de integridad o totalidad.

Uno de las dificultades principales en los procedimientos del cálculo e la programación entera es el efecto que tiene el error de redondeo que se genera a partir del uso inevitable de la computadora digital para resolver problemas enteros.

* APLICACIONES DE LA PROGRAMACION ENTERA :

Alunas de estas aplicaciones se refieren a l a formulación directa del problema, la contribución mas importante será el uso de esta programación para reformular modelos mal construidos.

En este caso la técnica mas conveniente puede utilizarse para resolver problenas que de otra manera pueden ser dificilmente abordados.

* Optimización de la ombinación de cifras comerciales en una red lineal de distribución de agua.

* Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.

* Soporte para toma de decisión en tiempo real para operación de un sistema de obras hidráulicas.

* Solución de problemas de transporte.

METODOS DE PROGRAMACION ENTERA:

* METODO DE CORTE:

Utilizado para problemas lineales, enteros, comenzando por el óptimo continuo, que representan básicamente condiciones necesarias de integridad.

* METODO DE BUSQUEDA.

La idea básica es la de desarrollar pruebas sutiles que consideren solo una porción de los enteros factibles en forma explicita pero que tomen ni cuenta automáticamente los puntos restantes. El método más sobresaliente es la técnica de ramificar y acortar. Un caso especial de los métodos de búsquedas se aplica cuando todas las variables enteras son binarias.

* ALOGORITMO DE PLANOS DE CORTE:ALGORITMO FRACCIONAL(ENTERO O PURO);ALGOGARTIMO MXTO

CASO PRÁCTICO:

Éste es un caso curioso, con solo 6 variables (un caso real de problema de transporte puede tener fácilmente más de 1.000 variables) en el cual se aprecia la utilidad de este procedimiento de cálculo.

Existen tres minas de carbón cuya producción diaria es:

* La mina "a" produce 40 toneladas de carbón por día;

* La mina "b" otras 40 t/día; y,

* La Mina "c" produce 20 t/día.

En la zona hay dos centrales termoeléctricas que consumen:

* La central "d" consume 40 t/día de carbón; y,

* La central "e" consume 60 t/día

Los costos de mercado, de transporte por tonelada son:

* De "a" a "d" = 2 monedas

* De "a" a "e" = 11 monedas

* De "b" a "d" = 12 monedas

* De "b" a "e" = 24 monedas

* De "c" a "d" = 13 monedas

* De "c" a "e" = 18 monedas

Si preguntáramos a una asamblea de pobladores de la zona, cómo organizar el transporte, con certeza, la gran mayoría opinaría que debemos aprovechar el precio ofrecido por el transportista que va de "a" a "d", porque es mucho más conveniente que los otros.

En este caso, el costo total del transporte seria:

* Transporte de 40 t de "a" a "d" = 80 monedas

* Transporte de 20 t de "c" a "e" = 360 monedas

* Transporte de 40 t de "b" a "e" = 960 monedas

* Total 1.400 monedas.

Sin embargo, formulando el problema para ser resuelto por la programación lineal tendríamos las siguientes ecuaciones:

* Restricciones de la producción:

Da----d + Da----e = 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

Los problemas de programación lineal en que se requiere que algunas o todas las variables tomen valores enteros, son de programación entera. La programación entera a llegado a ser un área muy especializada de la ciencia de la administración.

Un enfoque práctico:

Una empresa que fabrica costales para alimento de ganado y una solución lineal requiere que se fabriquen 3000,472 costales, carecerá de sentido. En tales situaciones, a menudo se adopta la solución no entera al requerimiento de enteros simplemente redondeando los resultados al entero más próximo. Esto produce lo que se llama la “solución redondeada”. Mediante ese recurso se obtienen soluciones aceptables para el administrador en aquellas situaciones en las que, con sentido practico, sencillamente no importa el redondeo. Por ejemplo, no hay diferencia significativa, ya sea en la función objetivo o en las restricciones, entre producir 19.283,64 y 19.283 costales de alimento para ganado, En realidad, probablemente baste para el ajuste de los datos del modelo que satisfaga al administrador una producción cercana a los 19.000 costales.

Tipos de modelos de Programación Entera:

Programación Entera es un termino 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.

Programas Enteros Puros

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.

...