Utilice el método del plano de corte para resolver programación entera
El método del plano de corte se utiliza principalmente para resolver problemas de programación entera. 1958 fue propuesto por American Gomorra. La idea básica es resolver el problema de programación lineal correspondiente sin considerar restricciones de números enteros. Si la solución óptima a un problema de programación lineal resulta ser una solución entera, entonces esta solución es la solución óptima al problema de programación entera. De lo contrario, se agrega una nueva restricción llamada plano de corte.
El plano de corte debe tener dos propiedades: al menos es una solución óptima no entera cortada del dominio factible del problema de programación lineal; no corta ningún dominio factible entero y luego continúa en el; Resolver problemas de programación lineal. Repitiendo la práctica anterior, después de un número finito de cortes, se puede obtener la solución óptima al problema de programación entera en el polo entero de la región factible reducida.
El método del plano de corte es un método relativamente sencillo para resolver programación entera, propuesto por el académico estadounidense R.E. La idea básica es básicamente la misma que la del método de rama y límite, es decir, el método simplex se utiliza para resolver la programación lineal correspondiente sin considerar las restricciones de números enteros de las variables.
Si la solución óptima obtenida es una solución entera, entonces también es la solución óptima al problema de programación entera original. 3. Si la solución óptima no es una solución entera, entonces el método de rama y ligada divide la programación entera original en dos ramas seleccionando arbitrariamente una variable con un valor numérico Xk=bk.
La esencia es dividir la región factible original R en dos regiones factibles R1 y R2 de dos planos paralelos perpendiculares al eje de coordenadas Xk=[bk] y Xk=[bk] 1, y eliminar uno de los dos planos paralelos. La parte de la región factible de la solución entera no se incluye en el intervalo para reducir la región factible.
El método del plano de corte fue propuesto por Ralph Gomory en la década de 1950 y se utiliza para resolver programación entera y programación entera mixta. Sin embargo, la mayoría de los expertos en ese momento, incluido el propio Gomory, creían que este método no tenía valor práctico debido a la inestabilidad numérica; al mismo tiempo, debido a la necesidad de múltiples rondas de corte durante el proceso de solución, este método también puede resultar ineficaz; .