[Mat08] BME Optimalizálás Szeminárium

[Csilla Majoros]

*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
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.math.bme.hu/pipermail/mat08/attachments/20160223/cf9d5f86/attachment.html>