Szegedi Tudományegyetem - Ahol tudás és szándék találkozik

Könyvfejezet születik. Galambos Gábor az elmúlt 15 évben ládapakolási algoritmusokkal foglalkozik – tapasztalatait összegzi. Fotó: Frank Yvette

Az optimalizálás mint matematikai feladvány irányába lökte Galambos Gábort az orosházi síküveggyárban a kétdimenziós táblák szabászati problémája. A 70-es évek második felében úgy jutott el a megoldáshoz, hogy kiindulópontnak a rudak egydimenziós modell alapján elvégezhető szabását tekintette. E matematikai módszert nevezik ládapakolási modellnek.

– Ha az a feladat, hogy rudakat szabjak kisebb darabokra úgy, hogy a lehető legkisebb legyen a selejt, akkor ezt úgy is meg tudom oldani, hogy egyrészt vannak olyan méretű ládáim, amekkora a rúd; másrészt vannak kisméretű tárgyaim, amelyeket csak egymás tetejére rakhatok a ládában. A cél az, hogy a tárgyak elrendezéséhez a lehető legkevesebb ládát használjam, miközben nem rakodhatok púposra – ismertette a matematikával foglalkozók körében ismert feladványt Galambos professzor. – E problémáról kiderült: ha mindenáron arra törekszem, hogy optimális megoldást adjak minden egyes problémára, és sok tárgyam van, akkor nagyon sok időre lenne szükség. Ezért közelítő algoritmusokat használnak a matematikusok. Ám ezzel megváltoznak a prioritások.

Egzakt algoritmusnál a feltételek között az idő nem számít, mert az optimumot akarjuk megkapni. A közelítő algoritmusnál viszont számít az idő – még akkor is, ha az eredmény távolabb esik az optimumtól. Ha e „gyors algoritmust” akarják gyártási folyamatba illeszteni, akkor meg kell határozni azt is, hogy a megoldás milyen messze van az optimumtól. Ezért vizsgálják a matematikusok, hogy a különböző algoritmusok a legrosszabb esetben milyen távol lehetnek az optimális megoldástól. Így aztán az az algoritmus a legjobb, amelyik a legrosszabb esetben is még viszonylag közeli megoldást ad az optimumhoz.

Újszászi Ilona

forrás: delmagyar.hu