Sondeo (I)

Un subproblema se puede vencer (sondear) y por lo tanto ya no tomarse en cuenta, en las tres formas que se describen a continuación.

Una de estas formas se ilustra con los resultados del subproblema 1 dados en el nodo x1 = 0, en la figura 13.3. Nótose que la solución óptima (única) de esta soltura de PL, (x1, x2, x3, x4) = (0,1, 0, 1), es una solución entera. Entonces, esta solución debe ser también la solución óptima para el subproblema 1 en sí. Esta solución debe almacenarse como la primera solución incumbente o de apoyo (la primera solución factible que se ha encontrado hasta ahora) para el problema completo, junto con su valor de Z. Este valor se denota por

Z* = valor de Z para la solución de apoyo actual,

de manera que en este punto Z* = 9. Una vez almacenada esta solución, no hay razón para seguir tomando en cuenta el subproblema 1 y ramificar el nodo x1 = 0. Hacerlo sólo conduciría a otras soluciones factibles inferiores a la de apoyo que no son de interés. Ahora, como ya se resolvió, el subproblema 1 se sondea (elimina).