Gomorin algoritmi

Gomoryn algoritmi on algoritmi , jota käytetään ratkaisemaan täysin lineaarisia kokonaislukuohjelmointiongelmia . Amerikkalainen matemaatikko Ralph Gomory kehitti algoritmin 1950-luvulla .

Toimenpide

1. Käyttämällä simpleksimenetelmää , ottamatta huomioon kokonaislukuvaatimusta, saadaan joukko yhtäläisyyksiä:

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

missä ovat kantamuuttujat ja ovat vapaita muuttujia $x_{i}$ $x_{j}$

2. Otamme käyttöön uuden rajoitteen ( vastaa muuttujaa , jolla on optimaalisessa suunnitelmassa suurin murto-osa ): $k$ $x_{k},$

$k={\underset {t}{\operaattorinimi {argmax} }}({\bar {b}}_{t}-\lfloor {\bar {b}}_{t}\rfloor )={ \underset {t}{\operaattorinimi {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}\ }$

missä on kerros (katso kokonaislukuosa ) $\lfloor\cdot\rfloor$

3. Jos uudella rajoituksella ratkaistaessa saadaan kokonaislukuratkaisu, ongelma on ratkaistu. Muussa tapauksessa toinen vaihe on toistettava.

Kirjallisuus

L.N.Zemlyanukhina, A.B.Zinchenko, L.I.Santylova. 3 // Ohjeet mekaniikan ja matematiikan tiedekunnan päivä- ja iltaosastojen opiskelijoille "Optimointimenetelmät" -kurssille "Lineaarinen ohjelmointi ja siihen liittyvät kysymykset". - Rostov-on-Don, 1998. - S. 24-33. – 36 s.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi