<div dir="ltr"><div><div><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font size="4"><b>MeghĂvĂł</b></font><br></span></div><span style="background-color:rgb(255,255,255)"><font size="4"><br></font></span><div style="text-align:left"><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font>Szeretettel vĂĄrunk minden</font> kedves ĂŠrdeklĹdĹt a BME<br><span>OptimalizĂĄlĂĄs</span> <span><span>SzeminĂĄrium</span></span>ĂĄn!</span><span style="background-color:rgb(255,255,255)"></span><br><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span><br></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"></span></div></div><span style="background-color:rgb(255,255,255)">Az elĹadĂĄs rĂŠszletei:<br><br></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><i><b>februĂĄr 25. (csĂźtĂśrtĂśk), 14.15, H306</b></i><br></span></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><br></span></span></div><b>MolnĂĄr-Szipai RichĂĄrd (BME)<br></b>PolinomiĂĄlis pivot algoritmusok maximĂĄlis folyam feladaton
<br>
<br>
<b>Absztrakt</b>:<br>
A maximĂĄlis folyam feladatra speciĂĄlis struktĂşrĂĄval rendelkezĹ lineĂĄris
programozĂĄsi feladatkĂŠnt is tekinthetĂźnk. A pivotalgoritmusok fontosabb
fogalmainak (bĂĄzis, primĂĄl ĂŠs duĂĄl megengedettsĂŠg, stb) szemlĂŠletes
megfelelĹjĂŠt mĂĄr Dantzig is leĂrta lineĂĄris programozĂĄsrĂłl szĂłlĂł
kĂśnyvĂŠben. Ezen felĂźl a gyakorlatban is a hĂĄlĂłzati szimplexet tartjĂĄk az
egyik leghatĂŠkonyabb eljĂĄrĂĄsnak.<br><br>Ennek ellenĂŠre az elsĹ
bizonyĂtottan polinomiĂĄlis vĂĄltozatokat csak 1984-ben (duĂĄl szimplex,
Orlin), illetve 1990-ben (primĂĄl szimplex, Goldfarb ĂŠs Hao) publikĂĄltĂĄk.
Az elĹadĂĄsban a primĂĄl szimplexhez hasznĂĄlt technika ismertetĂŠse utĂĄn
rĂśviden bemutatjuk az MBU pivot algoritmus kĂźlĂśnbĂśzĹ vĂĄltozatainak
(fĂzibilitĂĄsi, primĂĄl, duĂĄl) polinomialitĂĄsĂĄt, illetve Hochbaum egy
kombinatorikus algoritmusĂĄt, ami szintĂŠn tekinthetĹ egy se nem tisztĂĄn
primĂĄl, se nem duĂĄl pivot algoritmuskĂŠnt.<br><br><br></div>ĂdvĂśzlettel,<br></div>Majoros Csilla<br></div>