MTODO DE GOMORY Publicado en 1958 por Ralph Gomory, el mtodo de Gomory mejor conocido como Algoritmo de Plano de Corte, es un mtodo que permite encontrar soluciones ptimas enteras en aquellos problemas de programacin lineal que tienen soluciones fraccionarias o con decimales. Se basa con los planos cortantes (o corte) que es una nueva restriccin funcional que reduce la regin factible del relajamiento de PL sin eliminar soluciones factibles del problema de PE original. Podemos decir que este mtodo es una base de nuevas tcnicas que permiten de igual manera encontrar una solucin ptima entera de un problema de PL, un ejemplo, el mtodo de ramificacin y acotamiento que lo veremos ms adelante. El mtodo de Gomory se inicia en la solucin ptima continua. Se agregan restricciones especiales (los cortes) al espacio de soluciones para que produzcan un punto extremo ptimo entero. La desventaja de este mtodo, es que resulta muy ineficiente para resolver problemas enteros de tamao medio. Estos mtodos generan en cada iteracin una restriccin y una variable extra. Sin embargo, su ventaja es que ilustran lo que se pretende hacer con la regin de factibilidad de problemas entero, para lograr la solucin del mismo. Comenzaremos con un ejemplo prctico para su mejor entendimiento.

Ejemplo:

Lo resolvemos directamente por el mtodo SIMPLEX. Por lo tanto:

Pivoteamos el rengln x3, hacemos el cambio de 10X2 por X3 y nos queda:

Pivoteamos el rengln X4, hacemos el cambio de 7X1 por X4 y nos queda:

La solucin ptima es:

Grfica:

Observamos que nuestras soluciones ptimas no son nmeros enteros, para esto, si bien es donde proseguimos con el mtodo de Gomory. En base a la informacin que nos arroja nuestra tabla ptima, podemos reescribirla de la siguiente manera.

Una vez que tenemos la informacin de la tabla ordenada en las ecuaciones anteriores, debemos escoger una de estas ecuaciones, con la condicin de que siempre el lado derecho sea fraccionario. En caso del ejemplo, las 3 ecuaciones cumplen con la condicin.La ecuacin de restriccin que elijamos, ser nuestra fila origen (o rengln de fuente), con la cual generaremos un corte.Paso 1: Factorizamos todos los coeficientes no enteros de la ecuacin en un valor entero y un componente fraccionario, siempre y cuando el componente fraccionario sea estrictamente positivo. De la ecuacin Z, nos queda como resultado

Paso 2: Los componentes enteros los moveremos al lado izquierdo y los componentes fraccionarios al lado derecho. Obtenemos:

Como X3 y X4 son no negativas y todas las fracciones son positivas por construccin, el lado derecho debe satisfacer la siguiente desigualdad:

Paso 3: Ahora, como el lado izquierdo de la ecuacin (1), es un valor entero por construccin, el lado derecho tambin debe de ser entero. Por lo tanto deducimos que (2) puede ser reemplazada con una desigualdad:

Este resultado de justifica porque un valor entero menor que una fraccin positiva necesariamente debe ser 0. La ltima desigualdad es el corte deseado, y representa una condicin necesaria (ms no suficiente) para obtener una solucin entera. Esta desigualdad se conoce como corte fraccionario porque todos sus coeficientes son fracciones. Antes de demostrar cmo se implementa el corte fraccionario en la tabla ptima, se demostrar como tambin podremos construir los cortes a partir de las otras 2 ecuaciones de restriccin.Ecuacin Por lo tanto, nuestro corte asociado es:

Ecuacin X2: Por lo tanto, nuestro corte asociado es:

Cualquiera de estos tres cortes puede usarse en la primera iteracin del mtodo de Gomory. Seleccionando arbitrariamente el corte generado con la ecuacin, podemos rescribir en forma de ecuacin como:

Paso 4: Esta restriccin se agrega a la tabla ptima de PL, como se muestra:

Paso 5: La tabla es ptima pero no factible. Para esto, aplicamos el mtodo simplex dual, para recuperar la factibilidad.Para encontrar que columna es la que entra y que fila sale, dividiremos el rengln - entre el rengln , y tomaremos el valor absoluto ms pequeo y esa ser nuestra fila que entra. Despus, tomaremos el rengln que acabamos de agregar y ser nuestro rengln pivote.

Paso 6: Ahora que ya tenemos nuestra fila que sale y columna que entra, comenzamos a pivotear por el mtodo SIMPLEX, y obtenemos la siguiente tabla de optimidad:

Observamos que nuestras soluciones siguen siendo fraccionarias con excepcin de la primera, pero esto no significa que el problema est terminado, puesto que todas nuestras soluciones deben de ser enteras. Grfica de la tabla con el primer corte:

Paso 7: Regresamos al paso 4, agregando un segundo corte a esta ltima tabla ptima, de la misma manera que agregamos el primer corte, slo que en este caso, como ya elegimos la ecuacin , podemos elegir la ecuacin como nuestro corte. Nuestra tabla quedara de la siguiente manera:

Resolvemos de la misma manera que cuando agregamos el primer corte, y nos quedara la siguiente tabla:

Observamos en nuestra tabla y todas nuestras soluciones as como nuestro punto ptimo, nos arroja nmeros enteros. Por lo tanto el Mtodo de Gomory se detiene y el problema estar terminado.

Grfica de la tabla ptima anterior: