Rama de programación lineal entera y método ligado. Método de bifurcación y ligada de programación entera. Conceptos básicos. Resolver el problema del viajante online

El método de rama y unión se basa en la idea de partición secuencial de un conjunto. soluciones admisibles en subconjuntos. En cada paso del método, se realiza una verificación de los elementos de partición para determinar si este subconjunto contiene solución óptima O no. Para hacer esto, calcule el límite inferior función objetivo en este subconjunto.

Si la estimación más baja no es menor que el récord (la mejor solución encontrada), entonces es posible que el subconjunto ya no se considere. El subconjunto marcado también se puede descartar si es posible encontrar mejor solución. Si el valor de la función objetivo de la solución encontrada es menor que el registro, entonces el registro cambia. Al final del algoritmo, el registro es el resultado de su trabajo. Si es posible descartar todos los elementos de la partición, entonces el registro es la solución óptima al problema. De lo contrario, se selecciona el más prometedor de los subconjuntos no descartados (por ejemplo, con valor más bajo estimación más baja), y está dividido. Los nuevos subconjuntos se vuelven a comprobar, etc. El cálculo del límite inferior es el elemento más importante de este esquema.

para cada tarea específica En programación entera (en otras palabras, optimización discreta), el método de ramificación y unión se implementa a su manera. Hay muchas modificaciones de este método.

Consideremos la implementación del método de sucursal y encuadernación para el problema del viajante y el problema de la mochila.

Consideremos el algoritmo de Little (por el método de rama y ligado) para el problema del viajante. La idea se puede formular de la siguiente manera. En cada fila de la matriz de distancias, se encuentra el elemento mínimo y se resta de todos los elementos de la fila correspondiente. El resultado es una matriz reducida fila por fila. La matriz se muestra de manera similar por columnas. El resultado es una matriz que se muestra en filas y columnas. Sumando los elementos mínimos durante la reducción, obtenemos la constante de reducción, que será el límite inferior del conjunto de todos los contornos hamiltonianos admisibles. Luego se encuentran los grados de ceros para la matriz dada (la suma de los elementos mínimos de la fila y columna correspondientes a este cero) y se selecciona el arco para el cual el grado del elemento cero alcanza valor máximo. El conjunto de todos los contornos hamiltonianos se divide en dos subconjuntos, uno de los cuales contiene el arco y el segundo no contiene este arco. Después de esto, se dan las matrices resultantes de contornos hamiltonianos y se comparan los límites inferiores de un subconjunto de contornos hamiltonianos para seleccionar el conjunto con el límite inferior más pequeño para una mayor partición. El proceso de dividir conjuntos en subconjuntos va acompañado de la construcción de un árbol de ramas. Al comparar la longitud del contorno hamiltoniano con los límites inferiores de las ramas colgantes, se selecciona un subconjunto con un límite inferior más pequeño que el contorno resultante para una mayor ramificación hasta que se obtiene una ruta con la longitud más corta o queda claro que dicha ruta no existe.

Ejemplo.

Que se dé el problema del viajante siguiente matriz costos de mudanza

Encontramos el elemento mínimo en cada fila de la matriz y lo restamos de todos los elementos de la fila correspondiente. Obtenemos una matriz, reducida fila por fila, con elementos

.

Si la matriz, dada fila por fila, contiene columnas que no contienen cero, entonces la reducimos por columna. Para hacer esto, seleccione el elemento mínimo en cada columna de la matriz y réstelo de todos los elementos de la columna correspondiente. Consigamos la matriz

,

cada fila y columna que contenga al menos un cero. Esta matriz se llama reducida por filas y columnas.

Sumando los elementos y , obtenemos la constante de reducción:

.

Encontramos las potencias de ceros para la matriz dada en filas y columnas. Para hacer esto, reemplace mentalmente los ceros en la matriz con un signo y encuentre la suma de los elementos mínimos de la fila y columna correspondientes a este cero. Lo escribimos a la derecha. esquina superior células:

.

Seleccionamos el arco para el cual el grado del elemento cero alcanza el valor máximo

Dividimos el conjunto de todas las rutas válidas en dos subconjuntos:

– un subconjunto que contiene el arco;

– un subconjunto que no contiene un arco

Para calcular el costo estimado de rutas que incluyen el arco, tachamos la fila y la columna en la matriz y reemplazamos el elemento simétrico con el signo. Presentamos la matriz resultante y calculamos la suma de las constantes de reducción.

Consideremos el problema programación discreta en general:

Encontrar -vector de incógnitas, D- finito

muchos valores aceptables de este vector, F(x) es la función objetivo dada.

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 sólo 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 la región admisible en su conjunto.

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, de alguna manera debemos encontrar 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.

Uno de los más famosos y tareas importantes logística de transporte (y la clase de problemas de optimización en general) – problema del vendedor ambulante(Inglés "Problema del viajante", TSP). También se encuentra el nombre " problema del comerciante errante" La esencia del problema se reduce a encontrar el camino óptimo, es decir, el camino más corto que pasa por ciertos puntos uno por uno. Por ejemplo, el problema del viajante se puede utilizar para encontrar la ruta más rentable que le permita recorrer determinadas ciudades con sus mercancías una vez y regresar a su punto de partida. La medida de la rentabilidad de la ruta será tiempo minimo tiempo de viaje, los costes mínimos de viaje o, en el caso más simple, la duración mínima del viaje.

Se desconoce quién y cuándo empezó a estudiar el problema del viajante, pero fue uno de los primeros en proponer una solución. problema similar destacado matemático del siglo XIX. –William Hamilton. Aquí consideraremos una versión cerrada del problema (es decir, una en la que finalmente volvemos al punto de partida) y su solución. método de rama y enlace.

Plan general para solucionar el problema del viajante.

Para resolver el problema del viajante utilizando el método de sucursal y encuadernado, debe hacer lo siguiente: algoritmo(secuencia de acciones):

1. Construcción de una matriz con datos iniciales.
2. Encontrar el mínimo por filas.
3. Reducción de línea.
4. Encontrar el mínimo por columnas.
5. Reducción de columnas.
6. Cálculo de puntuaciones de celda cero.
7. Reducción de matriz.
8. Si aún no se ha encontrado la ruta completa, vaya al punto 2, si la encuentra, vaya al punto 9.
9. Cálculo de la longitud final del camino y construcción de la ruta.

Estas etapas para resolver el problema de un comerciante ambulante se describen con más detalle a continuación.

Metodología detallada para resolver el problema del viajante.

Para comprender mejor el problema, no operaremos con los conceptos de un grafo, sus vértices, etc., sino con conceptos simples y lo más cercanos posible a la realidad: los vértices del grafo se llamarán “ciudades”, las Los bordes que los conectan se llamarán "caminos".

Entonces, el método para resolver el problema del viajante de comercio:

1. Construcción de una matriz con datos iniciales

Primero, debe presentar las longitudes de las carreteras que conectan las ciudades en la siguiente tabla:

En nuestro ejemplo, tenemos 4 ciudades y la tabla muestra la distancia de cada ciudad a otras 3, dependiendo del sentido de viaje (ya que algunas vías de tren pueden ser de un solo sentido, etc.).

La distancia de una ciudad a la misma ciudad se indica con la letra M. También se utiliza un signo de infinito. Esto se hace para que este segmento del camino se acepte condicionalmente como infinitamente largo. Entonces no tendrá sentido elegir el movimiento de la 1ª ciudad a la 1ª, de la 2ª a la 2ª, etc. como segmento de ruta.

2. Encontrar el mínimo por filas

encontramos valor mínimo en cada línea ( di) y escríbalo en una columna separada.

3. Reducción de cuerdas

Realizamos una reducción de fila: de cada elemento de la fila restamos el valor correspondiente del mínimo encontrado (di).

Como resultado, cada línea tendrá al menos una celda cero.

4. Encontrar el mínimo por columnas

5. Reducción de columnas

Restamos el dj correspondiente de cada elemento de la matriz.

Como resultado, cada columna tendrá al menos una celda cero.

6. Cálculo de puntuaciones de celda cero

Para cada celda cero de la matriz transformada resultante encontramos " evaluación" Será la suma del elemento mínimo de una fila y el elemento mínimo de una columna en la que se ubica esta celda cero. Esto en sí no se tiene en cuenta. Di y dj encontrados anteriormente no se tienen en cuenta. Escribimos la estimación resultante junto a cero, entre paréntesis.

Y así sucesivamente para todas las celdas cero:

7. Reducción de matriz

Seleccionamos la celda cero con mayor puntuación. Lo reemplazamos con " METRO" Encontramos uno de los tramos del camino. Lo anotamos (de qué ciudad nos trasladamos a cuál, en nuestro ejemplo del 4 al 2).

Tachamos por completo esa línea y esa columna donde se formaron dos “M”. En la celda correspondiente camino de regreso , pon otra letra “M” (ya que no volveremos).

8. Si aún no se ha encontrado la ruta completa, vaya al punto 2, si la encuentra, vaya al punto 9.

Si aún no hemos encontrado todos los segmentos del camino, volvemos a 2 el punto ésimo y nuevamente buscar mínimos en filas y columnas, realizar su reducción, calcular las estimaciones de celdas cero, etc.

Si se han encontrado todos los segmentos del camino (o aún no se han encontrado todos los segmentos, pero el resto del camino es obvio), vaya al punto 9 .

9. Cálculo de la longitud final del camino y construcción de la ruta.

Habiendo encontrado todos los tramos del camino, solo queda conectarlos y calcular la longitud total del camino (coste del viaje por esta ruta, tiempo empleado, etc.). Tomamos las longitudes de las carreteras que conectan ciudades de la primera tabla con los datos iniciales.

En nuestro ejemplo, la ruta es la siguiente: 4 → 2 → 3 → 1 → 4 .

Longitud total del camino: L=30.

Aplicación práctica del problema del viajante.

Las aplicaciones prácticas del problema del viajante son bastante amplias. En particular, se puede utilizar para encontrar la ruta más corta cuando un grupo pop recorre ciudades, encontrar una secuencia de operaciones tecnológicas que asegure el menor tiempo para completar todo el ciclo de producción, etc.

Resolver el problema del viajante online

Galyautdinov R.R.

© La copia de material está permitida sólo si hay un hipervínculo directo a

Definiciones

es un conjunto finito no vacío que consta de dos subconjuntos y . Primer subconjunto (vértices) consta de cualquier conjunto de elementos. El segundo subconjunto (arcos) consta de pares ordenados de elementos del primer subconjunto. . Si los vértices y son tales que , entonces son vértices adyacentes.

Ruta en la columna

es una secuencia de vértices que no son necesariamente distintos por pares, donde para cualquier adyacente a . Una ruta se llama cadena si todos sus bordes son distintos por pares. Si entonces la ruta se llama cerrada. circuito cerrado llamado ciclo.

Declaración del problema

El viajante de comercio debe viajar norte ciudades. Para reducir costos, quiere construir una ruta tal que recorra todas las ciudades exactamente una vez y regrese a la original con un costo mínimo.

En términos de teoría de grafos, el problema se puede formular de la siguiente manera. Colocar norte vértices y matriz ( do ij), donde do ij ≥0 – longitud (o precio) del arco ( i , j),

. Bajo ruta del vendedor ambulante z entendamos el ciclo i 1 , i 2 ,…, i norte , i 1 puntos 1,2,…, n. De este modo, ruta es un conjunto de arcos. Si entre ciudades i Y j no hay transición, entonces el símbolo "infinito" se coloca en la matriz. Debe colocarse en diagonal, lo que significa que está prohibido volver a un punto por el que ya has pasado. ruta del vendedor ambulante, longitud de la ruta yo (z) es igual a la suma de las longitudes de los arcos incluidos en el recorrido. Dejar z– el conjunto de todas las rutas posibles. Pico inicial i 1 – fijo. Necesitamos encontrar una ruta z 0 О z, tal que yo (z 0)=mín. yo (z), z Î z .

solución del problema

La idea principal del método de rama y límite es que primero se construye un límite inferior φ en las longitudes del conjunto de rutas Z. Luego, el conjunto de rutas se divide en dos subconjuntos para que el primer subconjunto

consistía en rutas que contenían algún arco (i, j), y otro subconjunto no contenía este arco. Para cada uno de los subconjuntos, los límites inferiores se determinan según la misma regla que para el conjunto original de rutas. Los límites inferiores resultantes de los subconjuntos resultan ser nada menos que el límite inferior del conjunto de todas las rutas, es decir φ(Z)≤ φ (), φ(Z) ≤ φ ().

Comparando límites inferiores φ (

) Y φ (), podemos seleccionar el subconjunto de rutas que más probable contiene una ruta de longitud mínima.

Entonces uno de los subconjuntos

o, según regla similar, se divide en dos nuevos y . Se vuelven a encontrar límites inferiores para ellos. φ (), Y φ (), etc. El proceso de bifurcación continúa hasta que se encuentra una única ruta. Se llama primer registro. Luego miran entre las ramas arrancadas. Si sus límites inferiores son mayores que la longitud del primer registro, entonces el problema está resuelto. Si hay aquellos cuyos límites inferiores son menores que la longitud del primer registro, entonces el subconjunto con el límite inferior más pequeño sufre más ramificaciones hasta que se convence de que no contiene el mejor ruta .

Si se encuentra uno, entonces el análisis de las ramas rotas continúa con respecto al nuevo valor de la longitud de la ruta. Se llama segundo registro. El proceso de solución finaliza cuando se han analizado todos los subconjuntos.

Para implementación práctica El método de rama y límite, aplicado al problema del viajante de comercio, indicará una técnica para determinar los límites inferiores de subconjuntos y dividir un conjunto de rutas en subconjuntos (ramificación).

Para encontrar el límite inferior, usamos la siguiente consideración: si se suma o resta un cierto número de los elementos de cualquier fila de la matriz del problema del viajante (fila o columna), entonces la optimización del plan no será cambiar. La longitud de cualquier ruta del vendedor ambulante cambiará en esta cantidad.

Resta de cada línea un número igual al elemento mínimo de esta línea. Resta de cada columna un número igual al elemento mínimo de esa columna. La matriz resultante se llama reducida por filas y columnas. La suma de todos los números restados se llama constante de reducción.

Se debe elegir una constante de lanzamiento como límite inferior para la longitud de las rutas.

Dividir un conjunto de rutas en subconjuntos

Para identificar candidatos a ser incluidos en el conjunto de arcos a lo largo de los cuales se realiza la ramificación, consideramos todos los elementos de la matriz dada que son iguales a cero. Encontremos los grados Θ ij de los elementos cero de esta matriz. El grado del elemento cero Θ ij es igual a la suma del elemento mínimo en la fila i y el elemento mínimo en la columna j(al elegir estos mínimos do ij – no tomado en cuenta). Con la mayor probabilidad, la ruta requerida pertenece a arcos con un grado máximo de cero.

Para obtener la matriz de pago de rutas, incluyendo el arco ( i , j) tachamos la fila en la matriz i y columna j, y para evitar la formación de un ciclo en la ruta, reemplazamos el elemento que cierra la cadena actual hasta el infinito.

Muchas rutas que no incluyen un arco ( i , j) se obtiene reemplazando el elemento do ij al infinito.

Un ejemplo de resolución del problema del viajante utilizando el método de sucursal y encuadernado

Un viajante de comercio debe viajar a 6 ciudades. Para reducir costos, quiere construir una ruta tal que recorra todas las ciudades exactamente una vez y regrese a la original con un costo mínimo. Ciudad de origen A. Los costos de moverse entre ciudades vienen dados por la siguiente matriz:

A	B	do	D	mi	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
do	20	13	∞	35	5	0
D	21	16	25	∞	18	18
mi	12	46	27	48	∞	5
F	23	5	5	9	5	∞

solución del problema

Para facilitar la presentación, en todas partes a continuación en la matriz de pagos reemplazaremos los nombres de las ciudades (A, B, ..., F) con los números de las filas y columnas correspondientes (1, 2, ..., 6).

Encontremos el límite inferior de las longitudes del conjunto de todas las rutas. Restemos de cada fila un número igual al elemento mínimo de esta fila, luego restemos de cada columna un número igual al elemento mínimo de esta columna, y así presentemos una matriz en filas y columnas. Mínimo de fila: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

Luego de restarlos línea por línea obtenemos:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Mínimo de columna: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.

Luego de restarlos por columnas, obtenemos la siguiente matriz:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Encontremos el límite inferior φ (z) = 15+1+0+16+5+5+5 = 47.

Para identificar candidatos a incluir en el conjunto de arcos a lo largo de los cuales se realiza la ramificación, encontramos los grados Θ ij de los elementos cero de esta matriz (la suma de los mínimos en la fila y la columna). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. El grado más alto es Θ 14 = 10. Realizamos ramificaciones a lo largo del arco (1, 4).

Resolveremos el problema usando una calculadora. Tomemos como ruta arbitraria:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Entonces F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Para determinar el límite inferior del conjunto, utilizamos operación de reducción o reduciendo la matriz fila por fila, para lo cual es necesario encontrar el elemento mínimo en cada fila de la matriz D.
d i = min(j) d i j

yo j	1	2	3	4	5	yo
1	METRO	90	80	40	100	40
2	60	METRO	40	50	70	40
3	50	30	METRO	60	20	20
4	10	70	20	METRO	50	10
5	20	40	50	20	METRO	20

Luego restamos d i de los elementos de la fila en cuestión. En este sentido, en la matriz recién obtenida habrá al menos un cero en cada fila.

yo j	1	2	3	4	5
1	METRO	50	40	0	60
2	20	METRO	0	10	30
3	30	10	METRO	40	0
4	0	60	10	METRO	40
5	0	20	30	0	METRO

Realizamos la misma operación de reducción a lo largo de las columnas, para lo cual encontramos el elemento mínimo en cada columna:
d j = mín(i) d j

yo j	1	2	3	4	5
1	METRO	50	40	0	60
2	20	METRO	0	10	30
3	30	10	METRO	40	0
4	0	60	10	METRO	40
5	0	20	30	0	METRO
dj	0	10	0	0	0

Luego de restar los elementos mínimos, obtenemos una matriz completamente reducida, donde los valores d i y d j se llaman constantes de fundición.

yo j	1	2	3	4	5
1	METRO	40	40	0	60
2	20	METRO	0	10	30
3	30	0	METRO	40	0
4	0	50	10	METRO	40
5	0	10	30	0	METRO

La suma de las constantes de reducción determina el límite inferior de H:
H = ∑d yo + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Los elementos de la matriz d ij corresponden a la distancia del punto i al punto j.
Como hay n ciudades en la matriz, entonces D es una matriz nxn con elementos no negativos d ij >=0
Cada ruta válida representa un ciclo en el que el viajante visita la ciudad una sola vez y regresa a la ciudad original.
La longitud de la ruta está determinada por la expresión:
F(M k) = ∑d ij
Además, cada fila y columna se incluye en la ruta solo una vez con el elemento d ij.
Paso #1.
Determinar el borde de ramificación

yo j	1	2	3	4	5	yo
1	METRO	40	40	0(40)	60	40
2	20	METRO	0(20)	10	30	10
3	30	0(10)	METRO	40	0(30)	0
4	0(10)	50	10	METRO	40	10
5	0(0)	10	30	0(0)	METRO	0
dj	0	10	10	0	30	0

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
La mayor suma de constantes de reducción es (40 + 0) = 40 para el borde (1,4), por lo tanto, el conjunto se divide en dos subconjuntos (1,4) y (1*,4*).

H(1*,4*) = 140 + 40 = 180
Eliminamos la arista (1,4) reemplazando el elemento d 14 = 0 con M, luego de lo cual realizamos la siguiente reducción de la matriz de distancias para el subconjunto resultante (1*,4*), como resultado obtenemos una matriz reducida.

yo j	1	2	3	4	5	yo
1	METRO	40	40	METRO	60	40
2	20	METRO	0	10	30	0
3	30	0	METRO	40	0	0
4	0	50	10	METRO	40	0
5	0	10	30	0	METRO	0
dj	0	0	0	0	0	40

La inclusión del borde (1,4) se lleva a cabo excluyendo todos los elementos de la 1.ª fila y 4.ª columna, en los que el elemento d 41 se reemplaza por M para eliminar la formación de un ciclo no hamiltoniano.
El resultado es otra matriz reducida (4 x 4), que está sujeta a la operación de reducción.

∑d yo + ∑d j = 10

yo j	1	2	3	5	yo
2	20	METRO	0	30	0
3	30	0	METRO	0	0
4	METRO	50	10	40	10
5	0	10	30	METRO	0
dj	0	0	0	0	10

El límite inferior del subconjunto (1,4) es igual a:
H(1,4) = 140 + 10 = 150 ≤ 180
Dado que el límite inferior de este subconjunto (1,4) es menor que el subconjunto (1*,4*), incluimos el borde (1,4) en la ruta con un nuevo límite H = 150
Paso #2.
Determinar el borde de ramificación y divida el conjunto completo de rutas relativas a este borde en dos subconjuntos (i,j) y (i*,j*).
Para ello, para todas las celdas de la matriz con elementos cero, reemplazamos los ceros uno por uno con M (infinito) y determinamos para ellos la suma de las constantes de reducción resultantes que se dan entre paréntesis;

yo j	1	2	3	5	yo
2	20	METRO	0(20)	30	20
3	30	0(10)	METRO	0(30)	0
4	METRO	40	0(30)	30	30
5	0(30)	10	30	METRO	10
dj	20	10	0	30	0

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
La mayor suma de constantes de reducción es (0 + 30) = 30 para la arista (3,5), por lo tanto, el conjunto se divide en dos subconjuntos (3,5) y (3*,5*).
El límite inferior de los ciclos hamiltonianos de este subconjunto es:
H(3*,5*) = 150 + 30 = 180
Eliminamos la arista (3.5) reemplazando el elemento d 35 = 0 con M, luego de lo cual realizamos la siguiente reducción de la matriz de distancias para el subconjunto resultante (3*,5*), como resultado obtenemos una matriz reducida .

yo j	1	2	3	5	yo
2	20	METRO	0	30	0
3	30	0	METRO	METRO	0
4	METRO	40	0	30	0
5	0	10	30	METRO	0
dj	0	0	0	30	30

La inclusión del borde (3.5) se lleva a cabo excluyendo todos los elementos de la 3.ª fila y la 5.ª columna, en los que el elemento d 53 se reemplaza por M para eliminar la formación de un ciclo no hamiltoniano.
Como resultado, obtenemos otra matriz reducida (3 x 3), que está sujeta a la operación de reducción.
La suma de las constantes de reducción de la matriz reducida:
∑d yo + ∑d j = 10
Después de la operación de reducción, la matriz reducida tendrá el siguiente aspecto:

yo j	1	2	3	yo
2	20	METRO	0	0
4	METRO	40	0	0
5	0	10	METRO	0
dj	0	10	0	10

El límite inferior del subconjunto (3.5) es igual a:
H(3,5) = 150 + 10 = 160 ≤ 180
Dado que el límite inferior de este subconjunto (3,5) es menor que el subconjunto (3*,5*), incluimos el borde (3,5) en la ruta con un nuevo límite H = 160
Paso #3.
Determinar el borde de ramificación y divida el conjunto completo de rutas relativas a este borde en dos subconjuntos (i,j) y (i*,j*).
Para ello, para todas las celdas de la matriz con elementos cero, reemplazamos los ceros uno por uno con M (infinito) y determinamos para ellos la suma de las constantes de reducción resultantes que se dan entre paréntesis;

yo j	1	2	3	yo
2	20	METRO	0(20)	20
4	METRO	30	0(30)	30
5	0(20)	0(30)	METRO	0
dj	20	30	0	0

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
La mayor suma de constantes de reducción es (0 + 30) = 30 para la arista (5,2), por lo tanto, el conjunto se divide en dos subconjuntos (5,2) y (5*,2*).
El límite inferior de los ciclos hamiltonianos de este subconjunto es:
H(5*,2*) = 160 + 30 = 190
Eliminamos la arista (5,2) reemplazando el elemento d52 = 0 con M, luego de lo cual realizamos la siguiente reducción de la matriz de distancias para el subconjunto resultante (5*,2*), como resultado obtenemos una arista reducida matriz.

yo j	1	2	3	yo
2	20	METRO	0	0
4	METRO	30	0	0
5	0	METRO	METRO	0
dj	0	30	0	30

La inclusión del borde (5.2) se lleva a cabo excluyendo todos los elementos de la quinta fila y la segunda columna, en los que el elemento d 25 se reemplaza por M para eliminar la formación de un ciclo no hamiltoniano.
Como resultado, obtenemos otra matriz reducida (2 x 2), que está sujeta a la operación de reducción.
La suma de las constantes de reducción de la matriz reducida:
∑d i + ∑d j = 20
Después de la operación de reducción, la matriz reducida tendrá el siguiente aspecto:

yo j	1	3	yo
2	20	0	0
4	METRO	0	0
dj	20	0	20

El límite inferior del subconjunto (5,2) es igual a:
H(5,2) = 160 + 20 = 180 ≤ 190
Dado que el límite inferior de este subconjunto (5,2) es menor que el subconjunto (5*,2*), incluimos el borde (5,2) en la ruta con un nuevo límite H = 180
De acuerdo con esta matriz, incluimos los bordes (2,1) y (4,3) en la ruta hamiltoniana.
Como resultado, a lo largo del árbol ramificado del ciclo hamiltoniano, se forman los bordes:
(1,4), (4,3), (3,5), (5,2), (2,1),
La longitud de la ruta es F(Mk) = 180