Metodo Gomory

631 palabras 3 páginas
METODO DE GOMORY
Gomory fue el primer creador del algoritmo para resolver métodos de programación entera, el algoritmo de gomory consiste en resolver el problema sin considerar las restricciones del carácter entero de las variables y si la solución no es entera añade restricciones que reduce el conjunto de soluciones del problema lineal continuo asociado, sin excluir ninguna solución entera
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
…ver más…

Además debe cumplir las condiciones para aplicar el método dual simplex (optimalidad inicial y al menos un negativo en la solución): 1) Condición de optimalidad

2) Valor de variable básica < 0.

Definición: Un vector es lexicográficamente positivo si el primer componente diferente de cero es positivo. Cuando un vector X es lexicográficamente positivo se escribe X}0.
Ejemplo:
X= (0. 3, -2, 9) X = 0
X = (0,0,-3,12) X no es 0
Definición: un vector X es lexicográficamente 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 lexicográficamente mayor que Y
X - Y = 0, por tanto Y es lexicográficamente mayor que X.
Y – X = (1, -1, 4)
Los pasos del método son:
1) Elige la XBi más negativa. Se designa a esa fila con r. Si el método dual simplex genera un pivote -1, aplicar el método dual simplex. Si no continuar con el método.
2) Elige aquella columna no-básica con arj<0 que sea lexicográficamente 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:

Documentos relacionados

  • Ejercicios
    5946 palabras | 24 páginas
  • Programación entera
    2591 palabras | 11 páginas
  • Elementos Cuantitativos Y Cualitativos
    4269 palabras | 18 páginas
  • Origen y evolución de la investigación de operaciones
    4160 palabras | 17 páginas
  • generalidades de la investigacion de operaciones
    4635 palabras | 19 páginas
  • Modelos operacionales
    5655 palabras | 23 páginas
  • antologia
    5647 palabras | 23 páginas