Cómo utilizar matlab para resolver el problema de planificación 0-1

La programación entera tipo 0 ?1 es un caso especial de programación entera en el que la variable j x solo toma el valor 0 o 1. La condición de que j x solo tome los valores 0 o 1 se puede reemplazar por la siguiente restricción:

0 ≤ ≤ 1 j x, un número entero, que es consistente con las restricciones de la programación entera general. En problemas prácticos, si se introducen 0?1 variables, es posible unificar en un solo problema los problemas de programación lineal que deben discutirse por separado en múltiples situaciones. Primero presentamos el problema práctico después de introducir la variable 0?1 y luego estudiamos su solución.

Si existen m restricciones mutuamente excluyentes:

a x a x b i m i in n i 1,2, , 1 1 +L+ ≤ = L

Para garantizar que m Sólo una de las restricciones tiene efecto. Introducimos m 0?1 variables y (i 1,2, ,m) i = L

y una constante M lo suficientemente grande. El siguiente es un conjunto de m +. 1 Restricciones

. 1 restricción

a x a x b y M i m i in n i i i 1,2, , 1 1 +L+ ≤ + = L (1)

1 1 y + + y = m ?L m (2 )

Cumplir con los requisitos anteriores. Esto se debe a que, según (2), sólo uno de m i y puede tomar el valor 0. Supongamos que 0 * = i y,

Al poner en (1), solo la restricción i = i* es válida y otras ecuaciones son redundantes.

3.2 Una de las soluciones a la programación entera tipo 0?1 (filtrado de enumeración implícita)

Para resolver la programación entera tipo 0?1, al igual que resolver la programación entera general. Asimismo, la más simple El método es el método exhaustivo,

es decir, verificar cada combinación de variables con un valor de 0 o 1 y comparar el valor de la función objetivo para encontrar la solución óptima, lo cual requiere verificar

2n combinaciones de valores variables. Esto requiere verificar

2n combinaciones de valores de variables. Para una gran cantidad de variables n (por ejemplo, n >100), esto es casi imposible. Por esta razón, la gente suele idear métodos para encontrar la solución óptima a un problema examinando sólo un subconjunto de combinaciones de valores variables. Este tipo de método se denomina método de enumeración implícita y la restricción de rama también es un método de enumeración implícita. Por supuesto, hay algunos problemas en los que la enumeración implícita no funciona, por lo que a veces todavía es necesaria una enumeración exhaustiva.

Método de Monte Carlo (método de muestreo aleatorio)

Los métodos de programación entera comúnmente utilizados presentados anteriormente son principalmente para programación entera lineal y para programación entera no lineal.

Planificación Actualmente no existe un método maduro y preciso, porque aún no se ha encontrado una solución general efectiva para la programación no lineal en sí, y mucho menos para la programación entera no lineal.

Sin embargo, aunque la programación de enteros se vuelve más difícil al restringir las variables a números enteros, el hecho de que el número de soluciones enteras sea limitado

Esto proporciona comodidad para los métodos de enumeración. Por supuesto, cuando las variables independientes tienen muchas dimensiones y una amplia gama de valores, no es práctico intentar calcular el valor óptimo mediante una enumeración explícita (es decir, una enumeración exhaustiva), pero la aplicación de la teoría de la probabilidad muestra que se puede < / p>

Se obtiene una solución satisfactoria dentro del tiempo computacional.

Soluciones informáticas a problemas de asignación

Los problemas de programación entera se pueden resolver utilizando software especializado como Lingo. Para problemas generales de programación entera, las funciones de Matlab no se pueden usar directamente. La programación de Matlab debe usarse para implementar soluciones de ramas y límites y soluciones de planos de corte. Pero para los problemas de programación de enteros 0?1 (como los problemas de asignación), puede utilizar directamente la función bintprog de Matlab para resolverlos.