Algoritmo de gomori

El algoritmo de Gomory es un algoritmo que se utiliza para resolver problemas de programación lineal completamente enteros . El algoritmo fue desarrollado en la década de 1950 por el matemático estadounidense Ralph Gomory .

Procedimiento

1. Utilizando el método símplex , sin tener en cuenta el requisito del número entero, obtenemos un conjunto de igualdades:

$x_{i}+\sum {\bar {a}}_{i,j}x_{j}={\bar {b}}_{i},$

donde son variables base y son variables libres $x_{yo}$ $x_{j}$

2. Introducimos una nueva restricción ( corresponde a una variable que en el plan óptimo tiene la máxima parte fraccionaria ): $k$ ${\ estilo de visualización x_ {k},}$

$k={\underset {t}{\operatorname {argmax} }}({\bar {b}}_{t}-\lfloor {\bar {b}}_{t}\rfloor )={ \underset {t}{\nombre del operador {argmax} }}\{b_{t}\}$

$\sum (\lpiso {\bar {a}}_{k,j}\rpiso -{\bar {a}}_{k,j})x_{j}\leqslant \lpiso {\bar { b}}_{k}\rpiso -{\bar {b}}_{k}\quad \sim \quad -\sum \{a_{k,j}\}x_{j}\leqslant -\{{ \bar {b}}_{k}\}\quad \sim \quad \sum \{a_{k,j}\}x_{j}\geqslant \{{\bar {b}}_{k}\ }$

donde esta el piso (ver parte entera ) $\lpiso\cdot\rpiso$

3. Si al resolver con una nueva restricción se obtiene una solución entera, el problema está resuelto. De lo contrario, se debe repetir el segundo paso.

Literatura

L.N.Zemlyanukhina, A.B.Zinchenko, L.I.Santylova. 3 // Lineamientos para estudiantes de los departamentos diurnos y vespertinos de la Facultad de Mecánica y Matemáticas para el curso “Métodos de Optimización” “Programación Lineal y Temas Relacionados”. - Rostov del Don, 1998. - S. 24-33. — 36 s.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial