Clasificación de la programación entera
Definición:
En problemas de programación lineal, algunas soluciones óptimas pueden ser fracciones o decimales, pero para algunos problemas específicos, ciertas La solución de la variable debe ser un número entero. Por ejemplo, cuando la variable representa el número de máquinas, el número de personas trabajando, o el número de coches cargados, etc. Para satisfacer el requisito del número entero, a primera vista parece que todo lo que hay que hacer es redondear el número no entero resultante. De hecho, los números enteros no son necesariamente soluciones óptimas factibles, por lo que debería haber métodos especiales para resolver la programación entera. En la programación de enteros, si todas las variables están restringidas a números enteros, se llama programación de enteros pura; si solo algunas variables están restringidas a números enteros, se llama programación de enteros mixta. Un caso especial de programación entera es el programa 01, cuyas variables están limitadas a 0 o 1. A diferencia de los problemas de programación lineal, aún no se han encontrado soluciones polinomiales generales para problemas de programación entera y 01.
Optimización combinatoria
La optimización combinatoria generalmente se puede expresar como un problema de programación entera. Ambos buscan la mejor solución que satisfaga ciertas restricciones entre opciones limitadas. Hay muchos problemas típicos que reflejan los amplios antecedentes de la programación entera. Por ejemplo, el problema de la mochila (o carga), el problema del costo fijo, el problema de la expedición armoniosa (problema dual combinado), el problema de la expedición efectiva (problema de cobertura combinada), el problema del viajante, el problema de la ruta del vehículo, etc. Por lo tanto, el ámbito de aplicación de la programación entera también es extremadamente amplio. Tiene muchas aplicaciones no sólo en el diseño de ingeniería industrial y la investigación científica, sino también en el diseño de computadoras, confiabilidad de sistemas, codificación y análisis económico.
Programación Entera
Desde que R.E. Gomory propuso el método del plano de corte en 1958, la programación entera se ha convertido en una rama independiente. En los últimos 30 años, se han desarrollado muchos métodos para resolver diversos problemas. . La forma más típica de resolver la programación entera es generar gradualmente un problema relacionado, llamado derivada del problema original. Todo problema derivado va acompañado de un problema de relajación que es más fácil de resolver (el problema derivado se llama problema fuente del problema de relajación). El destino del problema fuente se determina resolviendo el problema de holgura, es decir, si el problema fuente debe abandonarse o si se deben generar uno o más problemas derivados propios para reemplazarlo. Luego, seleccione un problema derivado del problema original que no haya sido abandonado o reemplazado y repita los pasos anteriores hasta que no queden problemas derivados sin resolver. Los métodos más exitosos y populares ahora son el método de rama y unión y el método del plano de corte, los cuales se forman bajo el marco anterior.
Programación 0-1
La programación 0-1 juega un papel importante en la programación de enteros. Por un lado, muchas cuestiones prácticas como la asignación, la selección y la entrega de tierras pueden reducirse a este tipo de planificación. Por otro lado, la programación entera con variables acotadas arbitrarias es equivalente a la programación 0-1. Muchos problemas de programación no lineal se pueden expresar como problemas de programación entera utilizando el método de programación 0-1, por lo que muchas personas están comprometidas con la investigación en esta dirección. El método común para resolver la planificación 0-1 es el método de rama y unión. También existen algunos métodos especiales para varios problemas especiales, como el método húngaro para resolver problemas de asignación.