Programación entera

PROGRAMACIÓN LINEAL ENTERA

INVESTIGACIÓN OPERATIVA

3º A DIPLOMATURA EN CIENCIAS EMPRESARIALES

INDICE PÁGINAS

1. Introduccion.................................................................... 2
2. Programación enterapura.............................................. 3- 12
2.1 Método de ramificación y acote
2.2 Ejemplos
2.3 Problema resuelto con WINQSB.
3. Programación entera mixta............................................ 12- 15 3.1 Ramificación y acotamiento para un
problema entero mixto.
4. Programación enterabinaria.......................................... 16- 28
* 4.1 Ejemplo resuelto
* 4.2 Situaciones frecuentes que pueden modelarse
con variables binarias. Alternativas mutuamente
excluyentes y decisiones contingentes. EJEMPLO.
4.3 Otras situaciones.
4.4 Aplicación de la ramificación y acote en la
programación binaria. Ejemplo resuelto con
WINQSB. Solución gráfica.

5.EJERCICIOS PROPUESTOS SIN RESOLVER......................... 29-32
6. BIBLIOGRAFÍA................................................................ 33


1. INTRODUCCIÓN

Una vez conocida la programación lineal, en este tema desarrollamos el concepto añadiendo la restricción de que las variables de decisión solo tienen sentido real si su valor es entero, programación entera pura.Las variables afectan a decisiones del tipo: nº de personas, nº de maquinas. Si sólo es necesario que algunas de las variables tomen valores enteros y el supuesto de divisibilidad se cumple para el resto, el modelo se conoce como programación entera mixta. Hay algunos problemas en los que sólo se permite que las variables de decisión tomen valores binarios (0,1) como en el caso de decisiones deaceptación o rechazo (aceptación = 1, rechazo =0)
Se comienza con la aplicación de algunos procedimientos sencillos de programación entera como son el de enumeración exhaustiva o explicita y el de aproximación por redondeo. Tales procedimientos son fácilmente criticables y objetables, lo que llevo a desarrollar a partir d de los años cincuenta otros métodos como el de ramificación y acotación.1. El método del redondeo se basa en usar el método del símplex (ignorando en consecuencia la restricción entera) y después redondear los valores no enteros a enteros, en la solución resultante. Aunque esto es adecuado a menudo, existen riesgos en este enfoque. Uno de ellos es que la solución optima de programación lineal no es necesariamente factible después de redondearla. Es difícil ver, confrecuencia en que sentido debe redondearse para mantener la factibilidad. Puede incluso ser necesario cambiar el valor de algunas variables en una o más unidades después del redondeo.

2. Por otro lado, con la enumeración exhaustiva, el numero de soluciones posibles dentro de la región factible en este tipo de problemas es finito, si bien puede ser bastante elevado para problemas de unascuantas variables. El número de soluciones posibles para un problema de n variables es del orden de , excluyendo algunas que no cumplan las restricciones, por lo que, aunque podríamos hallar a solución optima examinando el resultado de la función objetivo con todas las soluciones posibles, no parece recomendable.

3. Los procedimientos específicamente designados para la solución de problemas deprogramación entera incluyen un método de ramificación y acote. En muchos problemas reales de programación entera la enumeración completa de todas las posibles soluciones no es factible. Lo más frecuente es el uso de este método en el que solamente es necesaria una enumeración parcial, si se aplica sistemáticamente, en el hallazgo de una solución óptima entera. Este método es una técnica para el...