Optimalizálás szeminárium

Időpont: 
2016. 02. 25. 14:15
Hely: 
BME H épület 306-os terem
Előadó: 
Molnár-Szipai Richárd

                                                                                             

BME DET Opkut hirdetesi logo 50 %.jpg                                 

           

                                        Meghívó                             

          Szeretettel várunk minden kedves érdeklődőt a BME

                      Optimalizálás Szemináriumán!

 

 

 

Az előadás részletei:

február 25. (csütörtök), 14.15, H306
 

Molnár-Szipai Richárd (BME)
Polinomiális pivot algoritmusok maximális folyam feladaton

Absztrakt:
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.

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.

 

Üdvözlettel,

Majoros Csilla