Algoritmul lui Gomori

Algoritmul Gomory este un algoritm care este folosit pentru a rezolva probleme de programare liniară completă . Algoritmul a fost dezvoltat în anii 1950 de matematicianul american Ralph Gomory .

Procedura

1. Folosind metoda simplex , fără a ține cont de cerința întregului, obținem o mulțime de egalități:

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

unde sunt variabile de bază și sunt variabile libere $x_{i}$ $x_{j}$

2. Introducem o noua constrangere ( corespunde unei variabile care in planul optim are partea fractionara maxima ): $k$ $x_{k},$

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

$\sum (\lfloor {\bar {a}}_{k,j}\rfloor -{\bar {a}}_{k,j})x_{j}\leqslant \lfloor {\bar { b}}_{k}\rfloor -{\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}\ }$

unde este podeaua (vezi partea întreagă ) $\lfloor\cdot\rfloor$

3. Dacă se obține o soluție întreagă la rezolvarea cu o nouă constrângere, problema este rezolvată. În caz contrar, al doilea pas trebuie repetat.

Literatură

L.N.Zemlyanukhina, A.B.Zinchenko, L.I.Santylova. 3 // Instrucțiuni pentru studenții catedrelor de zi și de seară ale Facultății de Mecanică și Matematică pentru cursul „Metode de optimizare” „Programare liniară și probleme conexe”. - Rostov-pe-Don, 1998. - S. 24-33. — 36 s.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică