Método de planos de corte

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 \le \; \left \lfloor \bar b_n \right \rfloor


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

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Corte Suprema de Justicia de la Nación Argentina — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor …   Wikipedia Español

  • Ramificación y poda — Saltar a navegación, búsqueda El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica… …   Wikipedia Español

  • Línea de empujes — Conjunto de sólidos (dovelas) formando un arco en equilibrio …   Wikipedia Español

  • Historia del desnudo artístico — David (1501 1504), de Miguel Ángel, Galería de la Academia de Florencia. La evolución histórica del desnudo artístico ha corrido en paralelo a la historia del arte en general, salvo pequeñas particularidades derivadas de la distinta aceptación de …   Wikipedia Español

  • Fresadora — universal con sus accesorios …   Wikipedia Español

  • Historia de la ciencia y la tecnología en España — Fragmento del Atlas catalán de Abraham Cresques, 1375. Historia de la ciencia y la tecnología en España es la denominación …   Wikipedia Español

  • Leonardo da Vinci — «Leonardo» redirige aquí. Para otras acepciones, véase Leonardo (desambiguación). Para otros usos de este término, véase Da Vinci (desambiguación). Leonardo da Vinci …   Wikipedia Español

  • Historia del arte — Para la historiografía de la historia del arte, véase Estudio de la historia del arte. La creación …   Wikipedia Español

  • Geometría analítica — La geometría analítica estudia las figuras geométricas mediante técnicas básicas del análisis matemático y del álgebra en un determinado sistema de coordenadas. Su desarrollo histórico comienza con la geometría cartesiana, impulsada con la… …   Wikipedia Español

  • Árbol kd — Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”