Ezen probléma mind a mai napig intenzíven kutatott területe a matematikai programozásnak. Ez annak köszönhető, hogy az elméleti eredmények mellett széles körű, és fontos gyakorlati alkalmazásai vannak a mérnöki és gazdasági feladatokban egyaránt.
A lineáris programozási feladatokkal ellentétben az LCP-feladatok nem oldhatók meg polinomális idő alatt. Abban az esetben, ha a probléma együttható mátrixa úgynevezett elégséges mátrix, akkor rendelkezésünkre áll hatékony megoldó algoritmus. Ebből kifolyólag kiemelkedő figyelmet fordítottunk a szakdolgozat címét is adó elégséges mátrixok megismerésére. Azonban az együttható mátrix elégségessége nehezen ellenőrizhető tulajdonság, ezidáig csak Väliaho -kinek nevéhez számos eredmény kötődik a területen- által kifejlesztett rekurzív módszer létezik, mely nem polinomális.
Így szakdolgozatom önálló eredményeként, különböző módszerekkel konstruáltunk elégséges mátrixokat.
Elsőként Väliaho rekurzív eljárását beprogramozva végeztünk kísérleteket, kerestünk elégséges mátrixokat. Majd (3 x 3)-as elégséges mátrixokat határoztunk meg úgy, hogy a bal felső (2 x 2)-es négyzetes részre egy elégséges mátrixot helyeztünk, a többi elemet pedig úgy választottuk meg, hogy elégségessége ne sérüljön.
Végül szimmetrikus pozitív szemidefinit mátrixokhoz közeli elégséges mátrixokat kerestünk tetszőleges diagonális alatti elemük megváltoztatásával.
| oktatás | vissza a főoldalra | írj nekem |
 |
 |
 |