Hasta ahora se ha descrito cómo usar la técnica de ramificación y acotamiento para encontrar una solución óptima. Sin embargo, en el caso de empates a veces es deseable identificar todas estas soluciones óptimas para que la elección final entre ellas pueda hacerse sobre factores intangibles que no se incorporaron al modelo matemático. Para encontrarlas todas es necesario hacer unos cuantos cambios al procedimiento. Primero, se cambia la desigualdad débil en la prueba de sondeo 1 (Es la cota del subproblema ≤ Z*?) or una desigualdad estricta (Es la cota del subproblema < Z*?) para que el sondeo no ocurra si el subproblema puede tener una solución factible igual a la de apoyo. Segundo, si la prueba de sondeo 3 pasa y la solución óptima para el subproblema tiene Z = Z*, entonces se almacena esta solución como otra solución de apoyo (empatada o no), se verifica si la solución óptima obtenida para la soltura es única. Si no lo es, se identifican las otras soluciones óptimas de la soltura y se verifica que sean óptimas también para el subproblema, en cuyo caso se convierten en incumbentes. Por último, cundo la prueba de optimalidad encuentra que no hay subconjuntos restantes (sin sondear), todas las soluciones de apoyo actuales serán soluciones óptimas.
No hay comentarios.:
Publicar un comentario