Planos De Corte De Gomory

METODO DE PLANOS DE CORTE
En optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.
En primer lugar,hemos de resolver el problema relajado, es decir sin tener en cuenta que algunas o todas las variables del problema deben ser enteras, si la solución obtenida x* es entera, ésa será la solución anuestro problema original, en caso contrario se construye un plano de corte que divide el conjunto de oportunidades x, en dos subconjuntos, uno de ellos contiene la solución no entera x* y el otrocontiene el conjunto de soluciones enteras del problema.
A partir de una solución no entera se van construyendo planos de corte, de tal forma que los cortes asociados a los mismos generan de formaiterada la solución entera buscada.
Para ello se añade a las restricciones que definen el conjunto de oportunidades, restricciones de desigualdad que verifican todas las soluciones enteras del problema yeliminan del conjunto de oportunidades algunas de las no enteras.

Ejercicio
Mín Z=3x1+4x2
Sujeta a:
Restricción1: 3x1+x2≥4
Restricción2: x1+2x2≥4
x1,x2≥0 y enteras

Solución
Se relaja elproblema y se resuelve por el método simplex obteniendo así la solución óptima del problema asumiendo las variables continuas.

Solución por el método gráfico

Solución por el método Simplex

Lasrestricciones se convierten en ecuaciones para poder resolver el problema por el método simplex, entonces tenemos:
3x1+x2-C1+X1=4
x1+2x2-C2+X2=4
Primera iteración del simplex

Segunda iteracióndel simplex

Tercera y última tabla simplex

Solución óptima:
x1=45 ;x2=85 ;Z=445;PSR1=25 ;PSR2=95
Creación del plano de corte de Gomory para encontrar una solución entera
Fijándonos en lavariable básica x1 de la última tabla del simplex, tenemos:
x1-25C1+15C2=45

Para realizar el Corte de Gomory es necesario separar la parte entera de la parte fraccionaria de la siguiente manera:...