Gomoriho algoritmus

Gomoryho algoritmus je algoritmus , který se používá k řešení problémů lineárního programování s úplnými celočíselnými hodnotami . Algoritmus byl vyvinut v 50. letech 20. století americkým matematikem Ralphem Gomorym .

Postup

1. Pomocí simplexové metody , aniž bychom vzali v úvahu celočíselný požadavek, získáme sadu rovností:

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

kde jsou základní proměnné a jsou volné proměnné $x_{i}$ $x_{j}$

2. Zavedeme nové omezení ( odpovídá proměnné , která má v optimálním plánu maximální zlomkovou část ): $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}\rpodlaží -{\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}\ }$

kde je podlaha (viz celočíselná část ) $\lpodlaha\cdot\rpodlaha$

3. Pokud se při řešení s novým omezením získá celočíselné řešení, problém je vyřešen. V opačném případě je nutné opakovat druhý krok.

Literatura

L.N.Zemlyanukhina, A.B.Zinchenko, L.I.Santylova. 3 // Pokyny pro studenty denních a večerních kateder Fakulty mechaniky a matematiky pro předmět „Optimalizační metody“ „Lineární programování a související problémy“. - Rostov na Donu, 1998. - S. 24-33. — 36 s.

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování