<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>