El método de ramificación y encuadernación es un ejemplo de resolución de un registro. Trabajo de curso: selección de parámetros de control mediante el método de programación dinámica y el método de rama y ligado. Reduciendo la matriz de costos y calculando la estimación menor del costo de la ruta r
Al hacer clic en el botón "Descargar archivo", descargará el archivo que necesita de forma totalmente gratuita.
Antes de descargar este archivo Recuerde esos buenos ensayos, exámenes, trabajos finales, tesis, artículos y otros documentos que se encuentran no reclamados en su computadora. Este es vuestro trabajo, debe participar en el desarrollo de la sociedad y beneficiar a las personas. Encuentre estos trabajos y envíelos a la base de conocimientos.
Nosotros y todos los estudiantes, estudiantes de posgrado y jóvenes científicos que utilizan la base de conocimientos en sus estudios y trabajos le estaremos muy agradecidos.
Para descargar un archivo con un documento, ingrese un número de cinco dígitos en el campo a continuación y haga clic en el botón "Descargar archivo"
Documentos similares
Características del método de rama y enlace como uno de los métodos de solución comunes problemas con números enteros. Descomposición del problema programación lineal en el algoritmo de rama y enlace. Método gráfico símplex para la resolución de problemas de programación lineal.
trabajo del curso, añadido el 05/03/2012
Planteamiento del problema del viajante. Descubrimiento solución óptima utilizando el método de rama y encuadernación. El principio básico de este método, el orden de su aplicación. Utilizar el método del límite superior en el procedimiento para construir un árbol de opciones posibles.
trabajo del curso, añadido el 01/10/2009
La esencia y descripción del método simplex y el método simplex mejorado (método matriz inversa), ventajas y desventajas de su uso en programación lineal. Listado y diagrama de bloques de un programa en Turbo Pascal para resolver un problema matemático.
trabajo del curso, añadido el 30/03/2009
Forma de organización de la producción principal de flujo variable. Características del reajuste de la máquina como tarea. programación dinámica. Características generales Algoritmo para formar el método de rama y enlace. La esencia del concepto es la configuración combinatoria.
trabajo del curso, añadido el 20/12/2008
Enunciado de un problema entero lineal. Método del plano de corte. Algoritmo fraccionario para resolver problemas completamente enteros. Eficacia del corte de Gomori. Comparación capacidades informáticas método del plano de corte y método de rama y encuadernado.
trabajo del curso, añadido el 25/11/2011
Formulación y solución de problemas de optimización discreta utilizando el método. programación discreta y el método de rama y enlace como ejemplo problema clásico viajante de comercio Etapas de la construcción de un algoritmo de rama y ligado y su efectividad, construcción de un árbol de gráficos.
trabajo del curso, añadido el 08/11/2009
Revisión de problemas resueltos por el método de programación dinámica. Planificación de ruta longitud óptima. Multiplicar una cadena de matrices. Problema de "escaleras". Análisis de la necesidad de utilizar métodos especiales de programación dinámica probabilística.
trabajo del curso, añadido el 28/06/2015
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 el subconjunto dado contiene la solución óptima o no. Para ello, se calcula la estimación inferior de la función objetivo en un subconjunto determinado.
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 se divide. 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 programación entera(en otras palabras, optimización discreta), el método de rama y enlace 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.
El método de rama y unión es uno de los métodos combinatorios. A diferencia del método Gomori, es aplicable a problemas tanto enteros como parcialmente enteros.
Su esencia radica en una selección ordenada de opciones y la consideración sólo de aquellas que, según determinados criterios, son útiles para encontrar la solución óptima.
Idea método de rama y enlace es el siguiente: supongamos que un problema debilitado se resuelva sin una restricción de número entero, y es una variable entera cuyo valor está en plan optimo es fraccionario. Entonces el intervalo
no contiene soluciones factibles con coordenadas enteras 
. Por lo tanto, el valor entero válido es 
debe satisfacer
o 
, o 
La introducción de estas condiciones en el problema genera dos problemas no relacionados con la misma función objetivo, pero áreas de valores permisibles de las variables que no se superponen. En este caso se dice que la tarea está bifurcada.
Evidentemente, uno de los cuatro casos siguientes es posible.
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 proporcionan la solución al problema original.
Uno de los problemas no tiene solución y el otro tiene un plan óptimo cuyos componentes incluyen 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 sobre nuevas restricciones sobre esta variable, obtenidas dividiendo sus valores enteros más cercanos. a la solución.
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.
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, ramificar a lo largo de la variable fraccionaria y construir dos nuevos problemas.
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, seleccionamos uno de los componentes cuyo valor es numero fraccionario, y se ramifica en dos nuevas tareas, dividiendo el rango de cambio de esta variable en dos, limitado por números enteros a la derecha e izquierda, respectivamente.
Por lo tanto, el proceso de construcción de más y más tareas nuevas se puede representar en la figura en forma de un árbol ramificado, con el vértice designado "tarea 1" y las ramas que se extienden desde este vértice. Esta secuencia de acciones a la hora de encontrar la solución óptima a un problema de programación entera se refleja en el nombre de este método.
El vértice original corresponde al plan óptimo del problema original 1, y cada vértice conectado a él por una rama corresponde a los planes óptimos de nuevos problemas construidos para nuevas restricciones sobre una de las variables que tienen un valor en forma de fraccionario. número en el plan óptimo del problema 1.
Cada uno de los vértices tiene sus propias ramas, y en cada paso se selecciona el vértice para el cual el valor de la función objetivo es mayor.
Si en algún paso se obtiene un plan con valores enteros y el valor de la función en él resulta ser mayor o igual al 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.
Ejemplo. Encuentre una solución de ramificación y límite para un problema de programación entera
Solución. Encontrar el plan óptimo para el problema formulado. método simplex sin tener en cuenta la naturaleza entera de las variables, es decir, resolvemos el problema 1.
Plan óptimo para el problema de programación lineal 1.
en 
.
Para el problema original, teniendo en cuenta la naturaleza entera de las variables, la solución resultante no es óptima.
Para encontrar una solución óptima entera, dividimos el intervalo de variación de la variable incógnita 1 en dos áreas, a saber incógnita 1 y incógnita 1 = 10, y dividámoslo tarea dada para dos nuevas tareas.
|
|
|
Límite inferior función lineal no ha cambiado: z 0 = 0. Resolvemos uno de los problemas, por ejemplo el problema 3, utilizando el método simplex. Encontramos que las condiciones del problema son contradictorias.
Resolvemos el problema 2 usando el método simplex. Obtenemos el plan entero óptimo para la tarea 2, que también es el plan óptimo para la tarea 1:
en 
.
Así, como resultado de una ramificación del problema, se encontró su solución óptima.
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 .
El modelo de programación entera debe incluir las expresiones (5), así como restricciones adicionales, con la ayuda de las cuales variables no enteras incógnita se reemplazan con valores enteros. En la siguiente subsección se analizan expresiones de modelos específicos con variables enteras.
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 fondo de salario q= 135 pies cúbicos mi.
De esta decisión situado solución entera Método de rama y encuadernació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 con 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
El desarrollo de este enfoque, llamado método de ramificación y acotación, comenzó con el trabajo de Land y Doig (1960). Más bien, esto ni siquiera es un método, sino un concepto o capa de procedimiento, a partir del cual comenzaron a desarrollar algoritmos para resolver problemas de números enteros de diversa naturaleza. El valor de la idea propuesta se hizo especialmente notable después de la aparición del primer algoritmo exacto para resolver el problema del viajante, construido según el esquema de rama y acotación (Little et al., 1963). El método se puede aplicar a problemas tanto enteros como parcialmente enteros.
La esencia de la idea es similar al famoso chiste sobre atrapar un león en el desierto: dividimos el desierto por la mitad; si no hay león en la primera mitad, lo buscamos en la segunda, que dividimos por la mitad, etc. A diferencia del león, el óptimo no se mueve, y en este sentido nuestra tarea es más fácil.
El método consiste en construir un árbol de problemas, cuya raíz es el problema original, posiblemente sin la condición de entero (IC). Los problemas subyacentes son generados por los superiores de tal manera que sus conjuntos admisibles (AS) son subconjuntos disjuntos del DM del problema suprayacente. El crecimiento del árbol se produce gracias a las ramas prometedoras. Las perspectivas están determinadas por evaluación de criterios tarea de terminal de sucursal V Yregistro Z. tarea de terminal de sucursal Calificación z– el valor del criterio del problema original alcanzado durante el proceso de solución (un valor obviamente peor que el óptimo puede tomarse como valor inicial). Esto significa que el problema será generativo sólo si su estimación es mejor que el registro. En este caso, no importa el nivel en el que se encuentre la tarea.
Consideremos el método aplicado a un problema entero lineal. Aunque no hay restricciones en la cantidad de tareas generadas directamente por una prometedora, los algoritmos, por regla general, utilizan una división en dos tareas, es decir, se construye un árbol binario (Fig. 7.5). En este caso, para conjuntos de números enteros se mantienen las siguientes relaciones:
ACERCA DE 
Es obvio que si, por ejemplo, tarea de terminal de sucursal 22 será peor que el récord o D
22 =, se rompe la rama derecha (también dicen que está sondeada). Si la evaluación tarea de terminal de sucursal 22 será mejor z,
se produce ramificación: muchas D
22 se divide en 2 subconjuntos. La solución se completará cuando todas las sucursales
será investigado.
El tipo de evaluación depende de la dirección del criterio: cuando se maximiza, se utiliza la estimación superior, cuando se minimiza, se utiliza la estimación más baja. La presentación posterior del método se referirá al problema máximo.
Para implementar algorítmicamente la rama y el límite, es necesario abordar dos preguntas fundamentales:
Cómo dividir un conjunto prometedor en subconjuntos;
Cómo determinar la estimación superior de un criterio en el conjunto considerado.
Las respuestas dependen del tipo de problema (parcial o completamente entero, tiene propiedades especiales o no, con variables booleanas o no booleanas). El caso general se considera a continuación.
Que se conozca el rango de valores posibles jésima variable
0 incógnita j d j ,
que en la solución óptima continua resultó ser no entera e igual a incógnita j *
. Entonces el valor entero de esta variable se puede lograr en el intervalo 0 incógnita j
, o en el intervalo 
+1
incógnita j
d j, Dónde 
- parte entera 
(Figura 7.6).
mi 
entonces corresponde a una partición de un conjunto continuo D norte en dos subconjuntos disjuntos D 1
norte
Y D 2
norte, cuya unión no es igual D norte. Al mismo tiempo, tal partición de un conjunto entero satisface las relaciones (7.9). En este caso, los conjuntos de enteros, tanto los originales como los generados, se incluyen en los correspondientes conjuntos continuos. Por lo tanto, buscar una solución entera en conjunto continuo dará el mismo resultado que con un número entero. Es fácil ver que la selección anterior de subintervalos para una variable conduce a una división del conjunto original en dos subconjuntos para cualquier número de variables.
Ahora pasemos a la segunda pregunta. Dado que un conjunto entero es un subconjunto del correspondiente continuo, valor optimo el criterio en un conjunto continuo siempre será no menor que en un conjunto entero. Por lo tanto, como límite superior tarea de terminal de sucursal puedes tomar el valor óptimo del criterio l * tarea continua.
La elección del valor del registro inicial depende de la situación:
si se conoce algún valor entero, entonces el registro se toma igual al criterio de esta decisión;
Si todos los coeficientes del criterio son positivos, podemos tomar valor nulo registro;
en otros casos, el valor inicial del registro se toma de la siguiente manera: METRO, Dónde METRO- el número máximo que se puede representar en una computadora.
A medida que avanza la partición, se forman tareas generadas, que se colocan en lista de tareas. La lista inicial contiene solo una tarea: problema original sin condiciones enteras. Y en el futuro la lista contendrá sólo tareas continuas.
Por lo tanto, el algoritmo básico que implementa el método de bifurcación y vinculación incluye los siguientes pasos.
El algoritmo dado es básico, ya que no incluye reglas inequívocas para seleccionar una tarea de una lista y una variable de ramificación. Para problemas de enteros parciales, las variables continuas se excluyen al elegir una variable para ramificar.
Ejemplo 7.3 . Apliquemos el algoritmo de rama y ligada al problema.
l= 9incógnita 1 + 5incógnita 2 máx;
3incógnita 1 - 6incógnita 2 1;
5incógnita 1 +2incógnita 2 28;
incógnita j 0 , entero.
ACERCA DE 
Eliminando la condición numérica, obtenemos una tarea continua, que colocamos en la lista de tareas. Dado que los coeficientes del criterio son positivos, el valor inicial del registro se considera igual a cero. Tomamos un solo problema de la lista y lo solucionamos. Obtenemos la solución óptima en el vértice A (Fig. 7.7): incógnita 1 * =4,72;
incógnita 2* =2,19. Ramificamos según la variable. incógnita 1. Agregar una restricción a un problema resuelto incógnita 1 4, formamos el problema 2, y la suma incógnita 1 5 da el problema 3. Los conjuntos admisibles de nuevos problemas se muestran en la figura. 7.7. Colocamos estas tareas en la lista de tareas. La solución al problema 2 se logra en el punto B y al problema 3 en el punto C. Todo el proceso de resolución del problema original se presenta en forma de árbol de decisión en la figura. 7.10. El orden de resolución de los problemas de la lista se refleja en el contador de iteraciones. k. En la tercera iteración (tarea 4), se obtuvo una solución entera con un valor de criterio de 41 (punto D en la Fig. 7.8). Por lo tanto el registro cambia: z=41. El problema 6 tiene una solución no entera (vértice E en la figura 7.9), el problema 8 tiene una solución entera en el punto F. Como resultado, después de la séptima iteración el registro pasa a ser 50.
ACERCA DE 
Los problemas del acero no tienen soluciones factibles, es decir, la lista de problemas está agotada y, por tanto, afirmamos que hemos obtenido una solución óptima al problema original, igual a la solución del problema continuo 8.
En el árbol de decisiones anterior se puede ver que la cantidad de tareas en la lista podría ser menor si las tareas se resolvieran en un orden diferente. De hecho, si los problemas de la rama derecha con el registro se resolvieran primero z= 50, luego de resolver el Problema 2 no habría bifurcación, ya que la estimación superior sería menor que el registro ( V=L * =45,17<50).
mi 
Naturalmente surge la pregunta: ¿cómo puede afectar la elección de otra variable para la ramificación al número de tareas y al árbol de decisiones? Entonces, en nuestro ejemplo, si después de la primera iteración hacemos una bifurcación según la variable incógnita 2, entonces obtenemos el árbol que se muestra en la Fig. 7.11. Contiene 2 tareas más que en la Fig. 7.10. Por supuesto, también puede ser diferente si los problemas se resuelven en un orden diferente.
Por tanto, el número de tareas a resolver depende significativamente de la elección de la tarea de la lista y de la variable para la bifurcación.
Del algoritmo y del ejemplo dado, se deduce que la rama finaliza por una de tres razones:
insolubilidad del problema;
el problema tiene solución entera;
la estimación superior no es más que un récord.
Ahora haremos una serie de comentarios sobre el método de rama y enlace. Como ya se señaló, el algoritmo básico no especifica las reglas para seleccionar una tarea y una variable. La mayoría de las implementaciones de software del método utilizan reglas basadas en evaluaciones heurísticas de las perspectivas de tareas y variables. Algunos paquetes, por ejemplo, “LP in ACS”, ofrecen varias opciones para gestionar el proceso de solución: desde automático hasta manual, en el que el usuario puede elegir tanto la tarea como la variable. Además, los algoritmos basados en el método de ramificación y unión pueden diferir significativamente debido a las características de la clase de problemas. Por ejemplo, para el problema del viajante, la determinación de la estimación se simplifica enormemente (no es necesario resolver un problema lineal continuo).
El método de rama y encuadernación tiene ventajas sobre el método de corte:
la acumulación de errores es menos significativa, ya que la solución va por diferentes ramas;
cuando el proceso de solución se ve obligado a detenerse, existe una alta probabilidad de obtener un resultado entero, pero sin establecer su optimización;
Al resolver problemas continuos, los tamaños de las tablas simplex no aumentan.
Desventajas del método de rama y encuadernación:
Es imposible estimar el número de problemas que habrá que resolver. Cuanto más cerca esté el valor inicial del registro desde abajo y la estimación del criterio del problema desde arriba al valor óptimo deseado del criterio, menos vértices tendrá el árbol de decisión y, por tanto, menos recursos gastará. Sin embargo, sobreestimar el registro inicial puede llevar a que el problema sea irresoluble, lo que siempre se debe tener en cuenta.
No hay señales de optimidad. La solución óptima se puede obtener mucho antes de que se detenga el algoritmo, pero en el caso general esto no se puede detectar. La optimización se establece sólo cuando se agota la lista de tareas.
Es obvio que la eficiencia del método aumenta al disminuir los rangos de valores de las variables y el número de variables no enteras al resolver el primer problema continuo.
