Ninguno

Solo disponible en BuenasTareas
  • Páginas : 7 (1690 palabras )
  • Descarga(s) : 0
  • Publicado : 20 de agosto de 2012
Leer documento completo
Vista previa del texto
En matemática, y más en concreto en optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.
Funciona resolviendo un programa lineal no entero, después comprobando si la optimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución noentera pero no corta ningún otro punto de la región factible. Esto se repite hasta que se encuentra la solución entera óptima .
Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.
Cortes de gomory:
Tengo una solución x admisible y tengo una base B asociada a x tal que

Si tengo una solución fraccionaria entoncestengo un elemento enésimo de x fraccionario.

es un corte o formulación entera del corte de Gomory.

Programación entera:
En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenidaconsiderando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cadavariable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.
La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominadafunción objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
.1 Introducción

La programación lineal entera se ocupa básicamente de programas lineales en los que algunas o todas las variables suponen valores enteros o discretos. Se dice que la PLE es mixta o pura si alguna o todas lasvariables están restringidas a tomar sólo valores enteros.

Aunque se han creado varios algoritmos para la programación entera, ninguno de ellos es totalmente confiable desde el punto de vista del cálculo, sobre todo, cuando el número de variables enteras se incrementa.
La dificultad de cálculo con los algoritmos disponibles para la programación entera ha conducido a los usuarios a buscar otrosmedios para resolver el problema. Uno de tales medios es resolver el modelo como un problema lineal continuo y luego redondear la solución óptima a los valores enteros factibles más cercanos. Sin embargo, en este caso no hay garantía de que la solución redondeada satisfaga las restricciones. Esto es siempre cierto si la programación entera original tiene una o más restricciones de igualdad.

Segúnla teoría de programación lineal, una solución redondeada en este caso no puede ser factible, ya que significa que la misma base   (con todas las variables básicas a nivel cero) puede generar dos soluciones distintas.
La infactibilidad creada por redondeo puede tolerarse ya que, en general, los parámetros de los problemas no son exactos. Pero existen restricciones de igualdad características enlos problemas enteros donde los parámetros son exactos.
La restricción de elección múltiple x1+x2+…+xn=1 , donde xj=(0,1) para toda j, no es sino un ejemplo. En tales condiciones el redondeo no puede utilizarse y será esencial contar con un algoritmo exacto.
Para destacar además lo inadecuado del redondeo, observe que aunque las variables enteras comúnmente se piensa que representan un...
tracking img