Metodo de Gomory

METODO DE GOMORY
Introduccin:
En matemtica, y ms en concreto en optimizacin, el mtodo de los planos de corte es un
procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por
Gomory. Fue el primer creador del algoritmo para resolver mtodos de programacin entera, el
algoritmo de Gomory consiste en resolver el problema sin considerar las restricciones del carcter
entero de las variables y si la solucin no es entera aade restricciones que reduce el conjunto de
soluciones del problema lineal continuo asociado, sin excluir ninguna solucin entera.
Funciona resolviendo un programa lineal no entero, despus comprobando si la optimizacin
encontrada es tambin una solucin entera. Si no es as, es aadida una nueva restriccin que corta
la solucin no entera pero no corta ningn otro punto de la regin factible. Esto se repite hasta que
se encuentra la solucin entera ptima
. Interpretacin geomtrica, una restriccin es equivalente

a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.

MTODO DE LOS PLANOS CORTANTES DE GOMORY

ste mtodo sirve para solucionar problemas de ms de dos (2) variables.
Algoritmo
1. Encontrar la solucin, empleando el mtodo simplex.
2. Si la solucin es entera, entonces estamos en el ptimo.
3. Si no es entera, introducir una restriccin nueva para la variable no entera, que tenga la mayor
parte fraccional (Quebrar empates arbitrariamente) y resolver el nuevo problema mediante el
mtodo dual simplex.
Nueva restriccin a partir de la restriccin actual que tenga la variable cuyo valor en su parte
fraccional sea mayor.
a) Escriba cada constante como la suma de: Un nmero entero de cualquier signo y una fraccin no
negativa, menor que uno (1).
b) Cambiar la ecuacin trasladando los coeficientes enteros al lado derecho.

Ejemplo Max: Z = X
1
+ 5X
2
Max:

C.S.R. X
1
+ 10X
2
<
20
C.S.R. X1 + 10X2 + X3 = 20
X1 < 2 X1 + X4 = 2
Xj > 0 y enteros
para toda j
Xj > 0 y enteros para toda j

A continuacin solucionamos el problema por el mtodo simplex, tal como se hara si el problema
fuese de programacin lineal continua.

Solucin ptima pero no entera: X1 = 2 ; X2 = 9/5 ; X3 = 0 ; X4 = 0 ; Z* = 11
Ecuacin 1 (Fila 1) para construir la nueva restriccin; ya que tiene la variable (X2), cuyo valor en
su parte fraccional es mayor.

Clculo de la nueva restriccin, a partir de la ecuacin 2.
X2 + 1/10X3 1/10X4 = 9/5
Remplazamos cada constante por la suma de un nmero entero de cualquier signo y una fraccin no
negativa menor que uno (1).
(1+0)X2 + (0+1/10)X3 + (-1+9/10)X4 = (1+4/5) Simplificando
X2 + 1/10X3 X4 + 9/10X4 = 4/5 + 1 ; Trasladamos los trminos con coeficiente entero, al lado
derecho.

1/10X3 + 9/10X4 = 4/5 + 1 X2 + X4 ; Fjese que el lado izquierdo subrayado debe ser positivo y
el lado derecho subrayado, debe ser entero, luego podemos asegurar que:

1/10X3 + 9/10X4 > 4/5 ; Multiplicando por (-1) ; -1/10X3 9/10X4 < -4/5 ; Adicionando una
variable de holgura; -1/10X3 9/10X4 + X5 = -4/5 ; Ecuacin sta que adicionamos, as:

X1 = 10/9 = 1 + 1/9 ; X2 = 17/9 = 1 + 8/9 ; X3 = 0 ; X4 = 8/9 ; X5 = 0 ; Z = 95/9 = 10,5
Escogemos la variable bsica con mayor parte fraccionaria, en caso de empate, escoja al azar.
Escojo X4

1/9X3 + X4 10/9X5 = 8/9 (0+1/9)X3 + (1+0)X4 + (-2+8/9)X5 = 8/9
1/9X3 + X4 2X5 + 8/9X5 = 8/9 Entero
8/9 X4 + 2X5 Positivo

Solucin factible, ptima y entera

X1* = 0
X2* = 2
X3* = 0
X4* = 2
X5* = 1
X6* = 0
Zx* = 10
Y1* = 3/8
Y2* = 0
Y3* = 0
Y4* = 5/8
Y5* = 0
Y6* = 0
ZY* = 10

MTODO FRACCI ONAL DE GOMORY
Este mtodo solo resuelve modelos enteros puros y consta de los siguientes pasos:
1. Resolver el modelo relajado, es decir, que las variables sean continuas.
2. Si el resultado es entero, entonces ya se tiene la solucin ptima, sino seguir con el mtodo.
3. Seleccionar el Max
incluyendo al renglon
, fraccionarioy generar un
nuevo corte o nueva restriccin:

4. Aadir este corte como una nueva restriccin y resolver utilizando el mtodo Dual Simplex;
ir al paso 2.
Nota: Z es entero si y solo si los coeficientes de la funcin objetivo son enteros y as utilizar al
rengln
en la tabla simplex.

MTODO PURO DE GOMORY
El algoritmo puro de Gomory es una variacin del mtodo fraccional de Gomory, al igual que
este mtodo la matriz A debe ser entera. Adems debe cumplir las condiciones para aplicar el
mtodo dual simplex (optimalidad inicial y al menos un negativo en la solucin):
1) Condicin de optimalidad
[
]
2) Valor de variable bsica < 0
[
]

Los pasos del mtodo son:
1) Elige la
ms negativa. Se designa a esa fila con r. Si el mtodo dual simplex genera un

pivote -1, aplicar el mtodo dual simplex. Si no continuar con el mtodo.
2) Elige aquella columna no-bsica con
que sea lexicogrficamente la menor. Se designa

una columna por k. Al primer elemento distinto de cero de dicha columna se le designa por
siendo su fila correspondiente la p.

3) Para la columna
se calcula el ndice

si es que
es el primer
elemento diferente de cero en la columna j. De otra manera

4) Se calcula para

5) Se deriva el corte:
[
]
6) Se anexa este a la tabla junto con su variable de holgura correspondiente y se aplica el mtodo
dual simplex sobre el entero. Si el resultado es
entonces se tiene la solucin ptima, si no ir

al paso 1.

CONCLUSION:
Podemos concluir que para nuestro problema que nos sea dado; sin tener en cuenta que algunas o
todas las variables del problema deben ser enteras, de manera que si la solucin obtenida es entera,
esa ser la solucin del problema entero. Es por eso que ocupamos el mtodo de Gomory; para que
nuestra solucin que obtengamos sea entera, siendo entonces la solucin a nuestro problema
original
REFERENCIAS BIBLIOGRAFICAS:
http://es.scribd.com/doc/144316517/Metodo-de-Gomory
https://sites.google.com/site/optimizacionenteraydinamica/introduccion/metodos-de-solucion-en-
programacion-entera/metodos-de-planos-de-corte
http://eco-mat.ccee.uma.es/mateco/Docencia/PM/Leccion%203/L3P1.pdf
http://www.lainter.edu.mx/pdfs/materias/cap%2012%20Programacion%20Lineal%20Entera%20y
%20Binaria.pdf

Metodo de Gomory

Cargado por

Copyright:

Formatos disponibles

Metodo de Gomory

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Metodo de Gomory

Cargado por

Copyright:

Formatos disponibles

METODO DE GOMORY

. Interpretacin geomtrica, una restriccin es equivalente

ms negativa. Se designa a esa fila con r. Si el mtodo dual simplex genera un

que sea lexicogrficamente la menor. Se designa

siendo su fila correspondiente la p.

entonces se tiene la solucin ptima, si no ir

También podría gustarte