Plano de corte

Método de plano de corte

El método del plano de corte fue desarrollado por Schrijver, está destinado a resolver problemas de optimización combinatoria (POC) que se formulan en forma de un programa lineal (PL):

plano de corte

En el caso de que el POC sea grande para representarlo explícitamente en la memoria o para que encaje en un solucionador de programación lineal, se utiliza una técnica que consiste en eliminar algunas de estas restricciones y resolver el problema relajado (POCR). La solución óptima de (PL) está contenida en el conjunto de soluciones factibles de esta relajación. Para un problema de minimización, la solución óptima del problema (POCR) es menor o igual que la solución óptima dada por (POC)

plano de corte

Este método consiste en resolver un problema relajado y en agregar restricciones iterativamente al problema inicial. Definimos una restricción para el problema de minimización por la pareja (s, s0) donde s está en Rno ys0 en R, se dice que esta restricción es violada por la solución actual x (bar) si para todos:

Estas restricciones se denominan entonces secciones planas. Se detiene el algoritmo cuando no hay más restricciones violadas por la solución actual, se obtiene así una solución óptima para el problema inicial.

El método de sección plana no es muy eficiente, pero su rendimiento mejora cuando se combina con el método Branch and Bound.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: