PROGRAMACI N ENTERA Jdsjdhkjsdhkja
Páginas: 6 (1497 palabras)
Publicado: 6 de agosto de 2015
PROGRAMACIÓN ENTERA
OBJETIVO
Formulación de modelos de optimización y aplicación de programación lineal con variables de valores enteros a partir de problemas en donde las empresas buscan optimizar la función objetivo.
INTRODUCCIÓN
Programación entera es el nombre que recibe un conjunto de técnicas que pueden usarse para encontrar la mejor solución entera posible para un problema deprogramación lineal. Se utiliza para resolver problemas en que las variables deben ser enteras y para problemas enteros mixtos, es decir, los que tienen algunas variables enteras y algunas continuas. Es una técnica de optimización ya que lleva a la mejor solución entera posible.
El redondeo de una solución óptima es peligroso, ya que no es obvio el hecho de que la solución que resulte sea óptima osiquiera posible. Por tanto, se tienen que emplear otros métodos cuantitativos que permitan sólo el uso de variables enteras y que generen soluciones enteras.
En ese sentido, los estudiosos de la investigación de operaciones han desarrollado varias técnicas que cumplen con dichas características, entre las que se pueden citar el algoritmo branch and bound y el método de variables binarias, entreotros.
En este apartado se explican con detalle los métodos señalados y se muestra un ejemplo desarrollado, así como las características que lo diferencian de otras técnicas de programación.
VARIABLES ENTERAS
Las variables estudiadas en una empresa pueden ser referidas mediante un símbolo (X, Y o cualquier letra) que puede representar a cualquier elemento dentro de la organización. Por ejemplo,la variable X puede ser un producto de la empresa o los trabajadores de la misma.
La programación entera se diferencia de la programación lineal, en que los valores de las variables de decisión sólo pueden tomar valores enteros. Así pues, las variables enteras no pueden tomar números fraccionarios o decimales.
Como ejemplo de las variables enteras podemos citar el número de productos al día,que pueden ser 50 o 120, pero no pueden ser 50.23 ni 120.32 productos.
ALGORITMO BRANCH AND BOUND.
Es una herramienta que emplea algoritmos para encontrar la solución óptima con variables enteras. Al inicio, los problemas se deben resolver empleando la programación lineal, a través de la cual se obtienen fracciones; es de gran ayuda emplear el algoritmo de branch and bound.
Este métododenominado en español ramificación y acotamiento forma parte de la programación entera. Puede ser usado para dos o más variables dependiendo del problema que se presente.
Ramificación y acotamiento es una estrategia de búsqueda sistemática que reduce mucho el número de combinaciones que se deben examinar. Comienza con la solución óptima del simplex en donde se ignoraron las restricciones de variablesenteras. Se selecciona después una variable con valor no entero y se crean dos ramas mutuamente excluyentes. Esto da lugar a dos nuevos problemas de programación lineal que se deben resolver. Si ninguna solución es entera, se crean nuevas ramas y se resuelven nuevos problemas.
En cada paso, la solución que se encuentra proporciona una cota para esa rama en el sentido de que ninguna otra soluciónpuede ser mejor. Por ejemplo, se inicia el proceso con una solución óptima no entera; se sabe que no existe ninguna otra solución no entera que sea mejor.
Para explicar mejor el método, se presenta a continuación un ejercicio resuelto:
Maximizar Z = $ 60X + 100Y
Sujeto a: 2 X + 3 Y 7
4 X + 3 Y 10
X 0 Y 0 Enteros
Para comenzar, se debe resolver el ejercicio empleando programación lineal(método gráfico o método simplex). Los resultados para este problema son: X= 3/2 e Y= 4/3, con una contribución (VC) de $223.33. Como podemos observar, los valores de las variables X e Y son valores fraccionarios y en las restricciones del método sólo se permiten valores enteros.
Para usar el método de branch and bound se deben escoger cualquiera de las dos variables; para este ejemplo, se...
OBJETIVO
Formulación de modelos de optimización y aplicación de programación lineal con variables de valores enteros a partir de problemas en donde las empresas buscan optimizar la función objetivo.
INTRODUCCIÓN
Programación entera es el nombre que recibe un conjunto de técnicas que pueden usarse para encontrar la mejor solución entera posible para un problema deprogramación lineal. Se utiliza para resolver problemas en que las variables deben ser enteras y para problemas enteros mixtos, es decir, los que tienen algunas variables enteras y algunas continuas. Es una técnica de optimización ya que lleva a la mejor solución entera posible.
El redondeo de una solución óptima es peligroso, ya que no es obvio el hecho de que la solución que resulte sea óptima osiquiera posible. Por tanto, se tienen que emplear otros métodos cuantitativos que permitan sólo el uso de variables enteras y que generen soluciones enteras.
En ese sentido, los estudiosos de la investigación de operaciones han desarrollado varias técnicas que cumplen con dichas características, entre las que se pueden citar el algoritmo branch and bound y el método de variables binarias, entreotros.
En este apartado se explican con detalle los métodos señalados y se muestra un ejemplo desarrollado, así como las características que lo diferencian de otras técnicas de programación.
VARIABLES ENTERAS
Las variables estudiadas en una empresa pueden ser referidas mediante un símbolo (X, Y o cualquier letra) que puede representar a cualquier elemento dentro de la organización. Por ejemplo,la variable X puede ser un producto de la empresa o los trabajadores de la misma.
La programación entera se diferencia de la programación lineal, en que los valores de las variables de decisión sólo pueden tomar valores enteros. Así pues, las variables enteras no pueden tomar números fraccionarios o decimales.
Como ejemplo de las variables enteras podemos citar el número de productos al día,que pueden ser 50 o 120, pero no pueden ser 50.23 ni 120.32 productos.
ALGORITMO BRANCH AND BOUND.
Es una herramienta que emplea algoritmos para encontrar la solución óptima con variables enteras. Al inicio, los problemas se deben resolver empleando la programación lineal, a través de la cual se obtienen fracciones; es de gran ayuda emplear el algoritmo de branch and bound.
Este métododenominado en español ramificación y acotamiento forma parte de la programación entera. Puede ser usado para dos o más variables dependiendo del problema que se presente.
Ramificación y acotamiento es una estrategia de búsqueda sistemática que reduce mucho el número de combinaciones que se deben examinar. Comienza con la solución óptima del simplex en donde se ignoraron las restricciones de variablesenteras. Se selecciona después una variable con valor no entero y se crean dos ramas mutuamente excluyentes. Esto da lugar a dos nuevos problemas de programación lineal que se deben resolver. Si ninguna solución es entera, se crean nuevas ramas y se resuelven nuevos problemas.
En cada paso, la solución que se encuentra proporciona una cota para esa rama en el sentido de que ninguna otra soluciónpuede ser mejor. Por ejemplo, se inicia el proceso con una solución óptima no entera; se sabe que no existe ninguna otra solución no entera que sea mejor.
Para explicar mejor el método, se presenta a continuación un ejercicio resuelto:
Maximizar Z = $ 60X + 100Y
Sujeto a: 2 X + 3 Y 7
4 X + 3 Y 10
X 0 Y 0 Enteros
Para comenzar, se debe resolver el ejercicio empleando programación lineal(método gráfico o método simplex). Los resultados para este problema son: X= 3/2 e Y= 4/3, con una contribución (VC) de $223.33. Como podemos observar, los valores de las variables X e Y son valores fraccionarios y en las restricciones del método sólo se permiten valores enteros.
Para usar el método de branch and bound se deben escoger cualquiera de las dos variables; para este ejemplo, se...
Leer documento completo
Regístrate para leer el documento completo.