Calculadora en línea del método de rama y encuadernación. Método de ramificación y ligada para la resolución de problemas de programación lineal entera. Vea qué es el “Método de ramificación y vinculación” en otros diccionarios

¡Hola Habr! dándose cuenta varios algoritmos Para encontrar el ciclo hamiltoniano al menor coste, encontré una publicación que ofrecía su propia versión. Después de probarlo, obtuve la respuesta incorrecta:

Otras búsquedas en Internet no arrojaron el resultado esperado: o una descripción teórica difícil para los no matemáticos o comprensible, pero con errores.

Debajo del corte encontrará un algoritmo corregido y una calculadora en línea.

El método en sí, publicado por Little, Murthy, Sweeney y Carel en 1963, es aplicable a muchos problemas NP-completos y es un material muy teórico que, sin buen conocimiento idioma en Inglés y las matemáticas no pueden aplicarse inmediatamente a nuestro problema del viajante de comercio.

Brevemente sobre el método: este es búsqueda completa todos opciones posibles con la eliminación de soluciones claramente subóptimas.

Algoritmo corregido para encontrar una ruta verdaderamente mínima.

El algoritmo consta de dos etapas:

Primera etapa

Reducción y cálculo de la matriz de costos. estimación más baja costo de ruta r.

1. Calcule el elemento más pequeño en cada fila (constante de conversión para la fila)
2. Pasamos a una nueva matriz de costos, restando su constante de reducción de cada fila.
3. Calcule el elemento más pequeño en cada columna (constante de coerción para la columna)
4. Pasamos a una nueva matriz de costos, restando su constante de reducción de cada columna.
Como resultado, tenemos una matriz de costos en la que cada fila y cada columna tiene al menos un elemento cero.
5. Calcula el límite en en esta etapa como la suma de constantes de reducción para columnas y filas (este límite será el costo por debajo del cual es imposible construir la ruta requerida)

Segunda etapa (principal)

1. Cálculo de la penalización por falta de uso para cada elemento cero de la matriz de costos dada.
La penalización por no usar un elemento con índice (h,k) en la matriz significa que esta arista no está incluida en nuestra ruta, lo que significa que el costo mínimo de “no usar” esta arista es igual a la suma de los elementos mínimos en fila h y columna k.

A) Buscamos todos los elementos cero en la matriz dada.
b) Para cada uno de ellos calculamos su penalización por no utilización.
c) Seleccionar el elemento que corresponde a la pena máxima (cualquiera, si son varios)

2. Ahora dividimos nuestro conjunto S en conjuntos: aquellos que contienen la ventaja con la penalización máxima (S w) y aquellos que no contienen esta ventaja (S w/o).
3. Cálculo de estimaciones de costes para las rutas incluidas en cada uno de estos conjuntos.
a) Para el conjunto S sin todo es simple: como no tomamos la ventaja correspondiente con la penalización máxima (h,k), entonces para ello el costo estimado es igual al costo estimado del conjunto S + la penalización por no usar el borde (h,k)
b) Al calcular los costos para el conjunto S w, tomamos en cuenta que como el borde (h,k) está incluido en la ruta, significa que el borde (k,h) no se puede incluir en la ruta, por lo tanto en en la matriz de costos escribimos c(k,h) =infinito, y como “ya hemos salido” del punto h, y “ya hemos llegado” del punto k, entonces ni una sola arista sale de h ni una sola arista llega en k ya no se puede utilizar, por lo que tachamos de la matriz de costos la fila h y la columna k. Después de esto, reducimos la matriz, y luego el costo estimado para S w es igual a la suma del costo estimado para S y r(h,k), donde r(h,k) es la suma de las constantes de reducción para la matriz de costos modificada.
4. De todos de conjuntos no particionados, se selecciona el que tiene la puntuación más baja.

Continuamos de esta manera hasta que quede una fila sin cruzar y una columna sin cruzar en la matriz de costos.

Pequeña optimización: agregar heurísticas

Sí, de verdad, ¿por qué no introducimos heurísticas? De hecho, en el algoritmo de rama y unión, en realidad construimos un árbol, en cuyos nodos decidimos tomar el borde (h,k) o no, y colgar dos hijos: Sw(h,k) y Sw/o( h,k). Pero mejor opción para la siguiente iteración seleccionamos solo por estimación. Así que elijamos el mejor no sólo en términos de calificación, sino también en términos de profundidad en el árbol, porque... Cuanto más profundo sea el elemento seleccionado, más cerca estará del final del conteo. De esta manera finalmente podremos esperar una respuesta.

Ahora, en realidad, sobre los errores en esa publicación.

Sólo hubo un error: deberías elegir dividir el conjunto con el límite mínimo de todos. formas posibles, y no de los dos hijos obtenidos como resultado de la última división.

Prueba

Volvamos a la imagen del inicio del post:

Y aquí está la solución con el algoritmo corregido:

Respuesta: ruta:3=>4=>2=>1=>5=>3 longitud: 41
Como puede ver, incluir la ventaja 5:2 en la solución sería un error. Q.E.D.

Gráfico que compara el método de bifurcación y encuadernación y el tiempo invertido en una tabla aleatoria de 5x5 a 10x10:


Gráfica del tiempo máximo y mínimo empleado para matrices de 5x5 a 66x66.


Pruebe con solución detallada Poder

El método de rama y unión es uno de los métodos combinatorios. Su esencia radica en una selección ordenada de opciones y la consideración solo de aquellas que resultan prometedoras según ciertos criterios y el rechazo de las opciones poco prometedoras.

El método de rama y enlace es el siguiente: set soluciones admisibles(planes) se divide de alguna manera en subconjuntos, cada uno de los cuales se divide nuevamente en subconjuntos de la misma manera. El proceso continúa hasta el óptimo. solución entera problema original.

Algoritmo de solución:

Inicialmente encontramos método simplex o método base artificial plan optimo problemas sin tener en cuenta la naturaleza entera de las variables. Sea el plan X 0 . Si no hay números fraccionarios entre los componentes de este plan, entonces se ha encontrado la solución deseada a este problema y

Si entre los componentes del plan X 0 hay números fraccionarios, entonces X 0 no satisface la condición de número entero y es necesario realizar una transición ordenada a nuevos planes hasta encontrar una solución al problema. Demostremos cómo se puede hacer esto, observando primero que F(X 0) F(X) para cualquier plan X posterior.

Suponiendo que el plan óptimo encontrado X 0 no satisface la condición de variables enteras, asumimos que entre sus componentes hay números fraccionarios. Supongamos, por ejemplo, que la variable tome un valor fraccionario en términos de X 0. Entonces, en el plan de enteros óptimo, su valor será al menos menor o igual que el entero menor más cercano, o mayor o igual que el entero mayor más cercano. Al determinar estos números, encontramos la solución a dos problemas usando el método simplex. programación lineal:

Encontremos una solución a los problemas de programación lineal (I) y (II). Obviamente, aquí es posible uno de los cuatro casos siguientes:

• 1. Uno de los problemas no tiene solución y el otro tiene un plan óptimo entero. Entonces este plan y el valor de la función objetivo que contiene proporcionan la solución al problema original.
• 2. Uno de los problemas no tiene solución y el otro tiene un plan óptimo, entre cuyos componentes se encuentran los números fraccionarios. Luego consideramos el segundo problema y en su plan óptimo seleccionamos uno de los componentes cuyo valor es igual a un número fraccionario y construimos dos problemas, similar a las tareas(I) y (II).
• 3. Ambos problemas tienen solución. Uno de los problemas tiene un plan entero óptimo y el plan óptimo del otro problema tiene números fraccionarios. Luego calculamos los valores de la función objetivo en estos planes y los comparamos entre sí. Si en un plan entero óptimo el valor de la función objetivo es mayor o igual a su valor en el plan, entre cuyos componentes hay números fraccionarios, entonces este plan entero es óptimo para el problema original y, junto con el El valor de la función objetivo en él, da la solución deseada.

Si el valor de la función objetivo es mayor en el plan, entre cuyos componentes hay números fraccionarios, entonces se debe tomar uno de estos números y para el problema cuyo plan se está considerando, es necesario construir dos problemas similares a (I) y (II).

4. Ambos problemas tienen solución y los planes óptimos para ambos problemas incluyen números fraccionarios. Luego calculamos el valor de la función objetivo en estos planes óptimos y consideramos el problema para el cual el valor de la función objetivo es mayor. En el plan óptimo para este problema, elegimos uno de los componentes cuyo valor es numero fraccionario, y construya dos problemas similares a (I) y (II).

Así, el proceso iterativo descrito anteriormente se puede representar en forma de árbol en el que el vértice inicial corresponde al plan óptimo X 0 del problema (1)-(3), y cada vértice conectado a él por una rama corresponde al Planes óptimos de los problemas (I) y (II). Cada uno de estos vértices tiene sus propias ramas. En este caso, en cada paso, se selecciona el vértice para el cual el valor de la función es mayor. Si en algún paso se obtiene un plan que tiene componentes enteros y el valor de la función en él resulta ser mayor o igual que el valor de la función en otros vértices posibles para la ramificación, entonces este plan es el plan óptimo para el problema de programación entera original y el valor de la función objetivo es máximo.

Entonces, el proceso de encontrar una solución al problema de programación entera (1)-(4) utilizando el método de rama y ligada incluye las siguientes etapas principales:

• 1. Encuentre una solución al problema de programación lineal (1)-(3).
• 2. maquillar restricciones adicionales para una de las variables, cuyo valor en el plan óptimo del problema (1)-(3) es un número fraccionario.
• 3. Encuentre una solución a los problemas (I) y (II), que se obtienen de los problemas (1)-(3) como resultado de agregar restricciones adicionales.
• 4. Si es necesario, cree restricciones adicionales para una variable cuyo valor sea fraccionario, formule problemas similares a los problemas (I) y (II) y encuentre su solución. El proceso iterativo continúa hasta que se encuentra un vértice que corresponde al plan entero del problema (1)-(3) y tal que el valor de la función en este vértice sea mayor o igual al valor de la función en otros vértices. posible para la ramificación.

El método de rama y unión descrito anteriormente tiene un método más simple. circuito lógico cálculos que el método Gomori. Por lo tanto, en la mayoría de los casos, para encontrar una solución. tareas específicas Este método se utiliza para la programación de números enteros usando una computadora.

problema de programación entera mochila del vendedor ambulante

El método de rama y límite se propuso por primera vez en 1960 en el trabajo de Land y Doig en relación al problema de la programación lineal entera. Sin embargo, este trabajo no tuvo un impacto directo notable en el desarrollo. programación discreta. De hecho, el "renacimiento" del método de sucursal y encuadernación está asociado con el trabajo de Little, Murthy, Sweeney y Carel sobre el problema del viajante; En el mismo trabajo, se propuso por primera vez el nombre ahora generalmente aceptado del método "método de ramificación y unión". A partir de este momento aparecieron un gran número de obras dedicadas al método de rama y encuadernación y sus diversas modificaciones. Un éxito tan grande (e incluso en relación con el “clásico difícil” problema del viajante) se explica por el hecho de que Little, Murthy, Sweeney y Carel fueron los primeros en llamar la atención sobre la amplitud de posibilidades del método de sucursal y encuadernación. señalaron la importancia de utilizar los detalles del problema y ellos mismos aprovecharon con mucho éxito estos detalles.

La sección 1 de este capítulo establece idea general método de rama y encuadernación; en el § 2, el algoritmo de Land y Doig para el problema de programación lineal entera, en el § 3, el método de Little y otros autores para el problema del viajante.

§ 1. La idea del método de rama y ligado.

1.1. Considere el problema de programación discreta en la siguiente forma general.

Minimizar

dado que

Aquí G es un conjunto finito.

1.2. El método de rama y enlace se basa en las siguientes construcciones, que en algunos casos permiten reducir significativamente el tamaño de la búsqueda.

I. Cálculo del límite inferior (estimación).

A menudo es posible encontrar un límite inferior (estimación) de la función objetivo en un conjunto de planes (o en algún subconjunto del mismo, es decir, un número tal que para

(en consecuencia, para la partición en subconjuntos (ramificación). La implementación del método está asociada con la división gradual de un conjunto de planes en un árbol de subconjuntos (ramificación). La ramificación se produce de acuerdo con el siguiente esquema de varios pasos.

0º paso. Hay un conjunto. De alguna manera está dividido en un número finito de subconjuntos (generalmente disjuntos). Hay conjuntos que aún no han sufrido ramificación. Según una determinada regla (especificada a continuación), se selecciona un conjunto entre ellos y se divide en un número finito de subconjuntos:

Conjuntos que aún no se han dividido

redesignado por

Varios pasos de este proceso de partición secuencial se representan esquemáticamente en la Fig. 10.1.1.

III. Nuevo cálculo de calificaciones. Si hay un conjunto entonces obviamente

Por lo tanto, dividir un determinado conjunto en subconjuntos en el proceso de resolución

EN situaciones especificas A menudo resulta posible mejorar la estimación, es decir, obtener al menos para algunos la desigualdad estricta.

IV. Cálculo de planos. Para tareas específicas se puede especificar varias maneras encontrar planes en subconjuntos sucesivamente ramificados. Cualquier método de este tipo depende significativamente de las características específicas del problema.

V. Signo de optimización. Dejar

y el plan X pertenece a algún subconjunto Si, además,

entonces X es el plan óptimo para el problema (1.1) - (1.2).

La prueba se deriva directamente de la definición de estimación.

Por lo general, esta característica se utiliza en alguna etapa de la ramificación (es decir, formalmente hablando, en ; consulte el párrafo II).

VI. Estimación de la precisión de una solución aproximada. Dejar

Si X es algún plan del problema original (es decir), entonces

La prueba aquí se deriva inmediatamente de la definición de estimación.

Obviamente, si la diferencia es pequeña (es decir, no excede un cierto número elegido para un problema dado), entonces X puede tomarse como una solución aproximada, como una estimación de la precisión de la aproximación.

1.3. Resumamos el esquema formal del método de rama y ligado.

0º paso. Calculamos la estimación. Si es posible encontrar un plan X tal que

entonces X es el plan óptimo.

Si no se encuentra el plan óptimo, entonces, utilizando algún método, dividimos el conjunto en un número finito de subconjuntos.

y pasar al paso.

1er paso. Calcular estimaciones Si es posible encontrar un plan X tal que para algunos y

entonces X es el plan óptimo.

Si no se encuentra el plan óptimo, seleccionamos el conjunto "más prometedor" para una mayor partición de acuerdo con la siguiente regla:

Dividimos el conjunto en varios subconjuntos (generalmente disjuntos).

Consideremos el problema de programación discreta en forma general:

Encontrar -vector de incógnitas, D- finito

conjunto de valores admisibles de este vector, F(x) es un dado función objetivo.

La idea del método es dividir D en subconjuntos disjuntos Di (este procedimiento se llama ramificación) y calcular los límites superior e inferior de la función objetivo en cada uno de los subconjuntos. Denotaremos el límite inferior con H y el superior con E. En consecuencia, Hola Eo, entonces este subconjunto no contiene el punto óptimo y puede excluirse de una consideración adicional. Si el límite superior es Ei H, reemplace H con min Hi. Si E=H, entonces el problema está resuelto; de lo contrario, es necesario continuar con el procedimiento de bifurcación y calcular los límites superior e inferior. En este caso, todos o solo algunos subconjuntos se pueden dividir en el siguiente paso hasta que se logre la igualdad de los límites superior e inferior, y no en un subconjunto separado, sino para área válida generalmente.

La idea simple del método de rama y límite requiere cálculos adicionales para determinar los límites. Como regla general, esto conduce a la solución de un problema de optimización auxiliar. Si estos cálculos adicionales requieren gran número operaciones, la eficacia del método puede ser baja.

Esquema programación dinámica al pasar del punto inicial al punto final (Fig. 5.1) se puede representar como un procedimiento de ramificación.

El conjunto de todas las trayectorias admisibles (una secuencia de transiciones paso a paso) es el conjunto inicial D, en el que debemos encontrar los límites inferior y superior, así como la trayectoria en la que la función objetivo alcanza el límite superior y declarar el valor correspondiente de la función objetivo como registro. La construcción del conjunto de estados obtenido tras el primer paso es la primera rama.

Arroz. 5.1.

Ahora bien, los subconjuntos de Di son conjuntos de trayectorias, cada una de las cuales pasa por el i-ésimo punto correspondiente.

En pasos posteriores, después de rechazar todos los caminos que conducen a cualquier estado (i-oe) excepto uno, el subconjunto correspondiente es este camino restante con todas sus continuaciones válidas (Fig. 5.1). Para cada uno de estos subconjuntos, debemos encontrar de alguna manera los límites superior e inferior. Si el límite inferior excede el valor del registro actual, se rechaza el estado correspondiente y todas sus continuaciones. Si se alcanza el límite superior en una determinada trayectoria y es menor que el valor del registro actual, obtenemos un nuevo registro.

La eficacia de este enfoque depende de la precisión de las estimaciones obtenidas, es decir, de Ei - Hola, y del tiempo dedicado a su cálculo.

De hecho, de forma simplificada, ya hemos utilizado este método al resolver el problema de protección de superficies (Sección 4.6), cuando rechazamos estados para los cuales los costos actuales excedieron los costos totales para la aproximación inicial. En este caso, los costos actuales son el límite inferior, si asumimos costos cero para todo el camino restante, y los costos totales correspondientes a la aproximación inicial son un récord. Con este enfoque, el registro no se actualizó, aunque esto se podría hacer construyendo una aproximación inicial (límite superior) para el camino restante de la misma manera que se hizo para toda la trayectoria al construir la aproximación inicial. El límite inferior obtenido sin cálculos corresponde a costes cero para todo el camino restante y es una estimación extremadamente aproximada, pero obtenida “gratis”, es decir. sin cálculos.

Le mostraremos cómo obtener y usar más estimaciones precisas al resolver los problemas anteriores y varios otros. En este caso, nos esforzaremos por obtener los límites más precisos posibles con un mínimo de cálculos.

A continuación se muestra la condición del problema y la parte textual de la solución. Toda la solución es formato de documento en el archivo, puedes descargar. Es posible que algunos caracteres no aparezcan en la página, pero documento de word todo se muestra. Se pueden ver más ejemplos de trabajos en EMMM.

DECLARACIÓN DEL PROBLEMA

La editorial debe completar el trabajo de mecanografía en una semana (número de días m = 5) con la ayuda de trabajadores de n categorías (alta, media, inferior a la media, baja). Es necesario determinar el número óptimo de empleados por categoría, lo que garantiza la finalización del trabajo con un gasto mínimo del fondo salarial bajo determinadas restricciones. Los datos iniciales se muestran en las tablas 1 y 2.

Tabla 1

Tabla 2

El problema debe resolverse utilizando el método de programación lineal entera en Mathcad 2000/2001.

CONSTRUYENDO UN MODELO MATEMÁTICO
SOLUCIONESTAREAS

Para calcular el número óptimo de empleados, que garantice un gasto mínimo del fondo salarial, se modelo matemático programación lineal entera, ya que el número de empleados no puede ser un valor fraccionario.

La resolución de un problema de programación entera se realiza en dos etapas.

En la primera etapa se realiza un problema de programación lineal sin tener en cuenta números enteros.

En la segunda etapa se hace proceso paso a paso reemplazar variables no enteras con los valores enteros superiores o inferiores más cercanos.

Primero, el problema se resuelve sin tener en cuenta la condición de número entero.

La función objetivo está determinada por la fórmula:

Dónde q- fondo general de salarios para el desempeño del trabajo;

incógnita 1 , incógnita 2 , …, xn- número de empleados por categoría;

norte - número de categorías de trabajadores;

do 1 , do 2 ,…, c norte- durante el día tasa arancelaria un empleado por categoría;

metro- número de días laborables por semana, metro = 5.

La función objetivo se puede escribir en forma vectorial:

Al resolver problemas se debe cumplir lo siguiente: las siguientes restricciones. Límite superior

incógnita ≤ d (1)

especifica el número máximo de empleados por categoría, donde d es un vector que determina el número de empleados por categoría.

En limitación

se tiene en cuenta que el número total de empleados no debe exceder k máx..

En la restricción desde abajo

r× x≥P(3)

se refleja que todos los trabajadores juntos deben completar una determinada cantidad de trabajo R.

Como última restricción, se escribe la condición de no negatividad del vector de variables.

incógnita≥0 (4)

El modelo matemático para resolver el problema sin tener en cuenta la condición de número entero incluye las siguientes expresiones:

incógnita ≤ d

r× x≥P,

incógnita ≥ 0 .

Un modelo de programación entera debe incluir expresiones (5), así como restricciones adicionales por las cuales las variables no enteras incógnita se reemplazan con valores enteros. Las expresiones de modelos específicos con variables enteras se analizan en la siguiente subsección.

SOLUCIONANDO EL PROBLEMA DE OPTIMIZACIÓN ENMATEMÁTICAS

Los datos de origen para el ejemplo se dan en la tabla. 1 y 2.

Para solucionar el problema, utilice el paquete Mathcad con la función Minimizar. Esta función determina el vector de solución del problema:

incógnita:= Minimizar ( q, incógnita),

Dónde q— expresión de la función objetivo que determina el fondo del salario mínimo, incógnita- vector de variables.

Primero, el problema se resuelve sin tener en cuenta la condición de número entero. Esta solución se proporciona en el Apéndice 1. La primera línea contiene valores iniciales cero del vector. incógnita y función objetivo q(incógnita) . Después de la palabra Dado y antes de la función Minimizar, se indican las restricciones. Como resultado, se obtuvo un número óptimo no entero por categoría:

incógnita =

con el fondo de salario q= 135 pies cúbicos mi.

De esta decisión Se encuentra una solución entera utilizando el método de rama y unión.

Primero, la solución resultante analiza el valor fraccionario x 4 =
= 1,143. Puede establecerle dos valores enteros: x 4 = 1 y x 4 = 2. Comienza la construcción de un árbol de decisión (Apéndice 2). El nodo cero inicial se reserva en el árbol de decisión. Luego se conecta por el primer nodo x4, y de este nodo se dibujan dos ramas correspondientes a las restricciones: x4 = 1 y x4 = 2.

Para una rama con la restricción x 4 = 1, el problema de programación lineal dado en el Apéndice 1 se resuelve teniendo en cuenta esta restricción.

Como resultado se obtuvo una solución a este problema. La variable x 1 se convirtió en un número entero, pero la variable x 2 se volvió fraccionaria x 2 = 0,9.

Para continuar con la rama, se crean un nodo x 3 y una rama x 3 = 1. El problema de programación lineal se ejecuta nuevamente con las tres restricciones: x 4 = 1, x 2 = 1, x 3 = 1. Con estas restricciones, el problema tiene solución x T =
= (1,938 1 1 1).

Para continuar la rama, se crean un nodo x 1 y una rama x 1 = 2. El problema de programación lineal se ejecuta nuevamente con las tres restricciones: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2. . Con estas restricciones, el problema tiene solución x T = = (2 1 1 1).

El proceso de construir un árbol de soluciones y ejecutar un problema de programación lineal se repite hasta que se construyen todas las ramas.

El Apéndice 2 proporciona un árbol completo de posibles soluciones enteras, de lo que se deduce que el problema tiene 4 soluciones efectivas.

Se selecciona la mejor de los resultados y se acepta como la solución entera óptima de todo el problema con el valor mínimo. q(incógnita) . En nuestro caso tenemos dos soluciones enteras óptimas.

q(INCÓGNITA) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

En consecuencia, la organización editorial debe contratar dos trabajadores altamente calificados para mecanografiar textos, un trabajador categoria media, un trabajador por debajo de la categoría media y un trabajador de la categoría baja. También es posible otra opción equivalente para atraer trabajadores: un empleado de categoría alta, un empleado de categoría media, dos empleados de categoría inferior a la media y dos empleados de categoría baja. En ambas opciones, los costes serán mínimos y ascenderán a 140 den. unidades

Descarga la solución al problema:

Nombre del archivo: 2.rar
Tamaño del archivo: 24,99 Kb

Si la descarga del archivo no comienza después de 10 segundos, haga clic en