Método de planos de corte

En matemática, y más en concreto 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.

Funciona resolviendo un programa lineal no entero, después comprobando si la optimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución no entera pero no corta ningún otro punto de la región factible. Esto se repite hasta que se encuentra la solución entera óptima $X^{*}\,$.

Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.

Cortes de Gomory

Tengo una solución x admisible y tengo una base B asociada a x tal que:

${\begin{bmatrix}B&F\end{bmatrix}}{\begin{bmatrix}x_{b}\\x_{f}\end{bmatrix}}=b\Rightarrow Bx_{b}+Fx_{f}=b\Rightarrow$

$\Rightarrow x_{b}=B^{-1}b-B^{-1}Fx_{f}={\bar {b}}\$ $-{\bar {A}}\ x_{f}\Rightarrow$ $x_{b}+{\bar {A}}\ x_{f}={\bar {b}}\$

Si tengo una solución fraccionaria entonces tengo un elemento enésimo de x fraccionario.

$(1)\,$

$x_{n}+\sum _{j\in \ \zeta \ }^{N}$ ${\bar {a}}_{n,j}x_{j}={\bar {b}}_{n}$

${\begin{bmatrix}\\x_{b}\\\\\end{bmatrix}}$$+{\begin{bmatrix}&&\\&{\bar {A}}\ &\\&&\end{bmatrix}}$${\begin{bmatrix}x_{f}\end{bmatrix}}$$={\begin{bmatrix}\\{\bar {b}}\ \\\\\end{bmatrix}}$

$(2)\,$

$x_{n}+\sum _{j\in \ \zeta \ }^{N}$ $\left\lfloor {\bar {a}}_{n,j}x_{j}\right\rfloor \leq \;$ $\left\lfloor {\bar {b}}_{n}\right\rfloor$

es un corte o formulación entera del corte de Gomory.

Véase también

• Ramificación y poda (Branch and Bound))

Enlaces externos

• Algoritmo del Plano de Corte en el Problema del Vendedor Viajero
• Método de Ramificar y Acotar (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Método de Branch and Bound: Ramificar y Acotar

• Datos: Q1762039