Igual que para el algoritmo de PEB, los dos primeros criterios se aplican resolviendo una soltura para obtener una cota sobre el subproblema y después verificar si esta cota es ≤ Z* (prueba I) o si la soltura no tiene soluciones factibles (prueba 2). Si la soltura difiere del subproblema sólo en que se eliminaron (o se relajaron) algunas restricciones, entonces se aplica el tercer criterio verificando si la solución óptima de la soltura es factible para el subproblema, en cuyo caso debe ser óptima para el subproblema. En otras solturas (como la de Lagrange), se requiere un análisis adicional par determinar si la solución óptima para la soltura es óptima para el subproblema.
Si el problema original involucra minimización en lugar de maximización, se tienen dos opciones. Una es convertirlo a maximización en la forma usual (véase la sección 4.6). La otra es convertir directamente el algoritmo de ramificación y acotamiento a la forma de minización, en donde el ajuste más importante es cambiar la dirección de la desigualdad para la prueba de sondeo 1, de
Es la cota del subproblema ≤ Z*?
a
Es la cota del subproblema ≥ ZZ*?
No hay comentarios.:
Publicar un comentario