Scribd
Cargar
205 vistas5 páginas

Método de Planos de Corte en Optimización

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 . Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.

Cargado por

Christian Lorenzo Flores Lolo
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
205 vistas5 páginas

Método de Planos de Corte en Optimización

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 . Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.

Cargado por

Christian Lorenzo Flores Lolo
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

INTRODUCCION

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.
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.

ALGORITMOS DE PLANOS DE CORTE


La idea del algoritmo de plano de corte es cambiar el conjunto convexo del
espacio de solucin.
De tal manera que los puntos extremos apropiados lleguen a ser todos enteros
Tales cambios en la frontera del espacio de solucin deben ser convexos
Tambin este cambio debe hacerse sin partir ninguna de las soluciones
enteras factibles del problema original.
Se muestra como dos restricciones secundarias (arbitrariamente elegidas) se
agrega al problema proporcionando la solucin optima entera en el punto
extremo nuevo.
El anlisis siguiente muestra cmo se desarrollan sistemticamente las
restricciones secundarias para los problemas de enteros mixtos y puros.

Ilustracin de un problema:
Maximizar Z = 7X1 + 9X2
s.a.:

-X1 + 3X2 <= 6


7X1 + X2 <= 35

Solucin continua optima (ignorando la condicin discreta)


De la grfica:
Maximizar Z = 63
s.a.:
X1 = 9/2
X2 = 7/2
Lo cual no es entero.
Note que el rea cerrada de solucin no muestra ningn valor entero
El anlisis siguiente muestra cmo se desarrollan sistemticamente las
restricciones secundarias para los problemas de enteros mixtos y puros.

CORTES DE GOMORY
Tengo una solucin x admisible y tengo una base B asociada a x tal que:

Si tengo una solucin fraccionaria entonces tengo un elemento ensimo de x


fraccionario.

Es un corte o formulacin entera del corte de Gomory.


"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.

Definicin: Un vector es lexicogrficamente positivo si el primer componente


diferente de cero es positivo. Cuando un vector X es lexicogrficamente
positivo se escribe X}0.

Ejemplo:
X= (0. 3, -2, 9)
X = (0,0,-3,12)

X=0
X no es 0

Definicin:
un vector X es lexicogrficamente mayor que otro vector Y si X - Y =0

Ejemplo:
X = (0, 3, -2)

Y = (1, 2, 2)

X Y = (-1, 1, -4)

X no es lexicogrficamentemayor que Y

Y X = (1, -1, 4)

X - Y = 0, por tanto Y es lexicogrficamente


mayor que X.

Los pasos del mtodo son:


1) Elige la XBi 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 arj<0 que sea lexicogrficamente la
menor. Se designa una columna por k. Al primer elemento distinto de cero de
dicha columna se le designa por apk(>0) siendo su fila correspondiente la p.

3) Para la columna arj<0 se calcula el ndice uij = [akj/apk] si es que apj es el


primer elemento diferente de cero en la columna j. De otra manera uj=.
4) Se calcula =max [ !arj! / uj ]para arj<0 y uj.
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 XB0
entonces se tiene la solucin ptima, si no ir al paso 1.

También podría gustarte