¿Qué es la programación entera? y escribir su modelo matemático.
En general, se cree que la programación entera no lineal se puede dividir en una parte lineal y una parte entera, por lo que la programación entera a menudo se considera una parte especial de la programación lineal. En los problemas de programación lineal, algunas soluciones óptimas pueden ser fracciones o decimales, pero para algunos problemas específicos, la solución debe ser un número entero. Por ejemplo, la solución es la cantidad de máquinas, la cantidad de personas trabajando o la cantidad de autos cargados. 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.
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. Cada 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 una derivada del problema original que no haya sido abandonada o reemplazada y repita los pasos anteriores hasta que no queden derivadas sin resolver. Actualmente, los métodos más exitosos y populares incluyen el método de rama y unión y el método del plano de corte, los cuales se forman bajo el marco anterior.
La programación 0-1 juega un papel importante en la programación entera. 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.
[editar]
La relación entre la programación entera y la optimización combinatoria
En términos generales, los campos de la programación entera y la optimización combinatoria son los mismos. Solución que cumple ciertos criterios entre un número limitado de alternativas. 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 del conjunto combinado), el problema de la expedición efectiva (problema de cobertura combinada), el problema de distribución, etc. Por lo tanto, el rango 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.
[editar]
Tipos de programación entera
La programación entera se divide en:
1. Programación entera pura: requiere toda decisión. variables Todas son programación entera.
2. Programación entera mixta: Algunas variables de decisión requieren programación entera.
3. Programación entera pura 0-1: todas las variables de decisión deben ser programación entera 0-1.
4. Programación mixta 0-1: una programación entera que requiere que algunas variables de decisión sean 0-1.
La única diferencia entre programación entera y programación lineal es la suma de restricciones de números enteros. La programación lineal que no considera restricciones de números enteros se denomina modelo de relajación lineal de programación entera.
[editar]
Modelo de programación entera
En la vida real, si la variable de decisión representa el número de piezas, conjuntos, cajas, barcos, coches, etc. . Para los productos, las variables sólo pueden tomar valores enteros. Por ejemplo, el modelo de corte es en realidad un modelo de programación entera. La variable de decisión en este caso representa la cantidad de tubos de acero que se cortarán, que obviamente solo puede tomar valores enteros. Por lo tanto, los modelos de programación entera también se utilizan ampliamente, como puede verse en los siguientes ejemplos.
Una idea natural para resolver la programación entera es si la solución óptima de la programación entera se puede obtener redondeando la solución óptima del modelo de relajación lineal de la programación entera. La respuesta es no, porque el resultado de dicho redondeo ni siquiera es una solución factible.
La programación entera es más difícil de resolver que la programación lineal habitual. Hasta ahora, la idea básica de resolver la programación entera es seguir ciertas reglas de búsqueda para encontrar la solución óptima entera (o confirmar que no existe una solución óptima entera) dentro del dominio factible del modelo de relajación lineal de la programación entera. Se necesita tiempo para encontrar la solución a la programación entera. Más tiempo. Los métodos de solución más utilizados actualmente incluyen principalmente el método de ramificación y unión, el método del plano de corte y el método exhaustivo.