Optimalizálási feladat megoldása korlátos programozással

Tanszéki konzulens: 
A munkatárs fényképe
docens
Szoba: IE423
Tel.:
+36 1 463-4394
Email: strausz (*) mit * bme * hu
Külső konzulens: 
Kovács András, MTA SZTAKI

A kiírás adatai

A téma státusza: 
Törölt (nem látszik a listákban)
Kiírás éve: 
2009
A kiírás jellege: 
önálló labor, szakdolgozat/diplomaterv

Önálló labor téma 1 vagy 2 BSc hallgató számára

Konzulens: Kovács András
E-mail: akovacs@sztaki.hu 

Web: www.sztaki.hu/~akovacs 

Az élet különböző területein előforduló tervezési, optimalizálási feladatok gyakori jellemzője, hogy a megoldásnak sokféle műszaki, gazdaságossági, és egyéb feltételnek kell megfelelnie. Ezek a feltételek ráadásul gyakran változnak, más-más szituációban más-más feltételeket kell figyelembe venni.

A fentiekre jó példát szolgáltatnak a pakolási feladat különböző változatai, pl. a konténer rakodási feladat. A matematikai alapfeladat 3 dimenziós testek átlapolás nélküli elhelyezése egy befoglaló alakzatban. A gyakorlatban viszont sok más követelmény is felbukkanhat:

  • - a dobozoknak nem szabad maguktól leborulniuk;
  • - egyes dobozok megsérülhetnek, ha túl nagy súly kerül rájuk;
  • - ha az egyes doboznak más-más a célállomása, akkor adott sorrendben kipakolhatóknak kell lenniük a - - konténerből más dobozok ki-be rakodása nélkül is;
  • - az azonosító címkéknek láthatónak kell lenniük;
  • - a rakomány súlypontja egy meghatárzott régióban kell, hogy legyen, stb. 

Ilyen feladatok modellezésére és megoldására ígéretes megközelítés a korlátozás programozás, mely a mesterséges intelligencia és az operációkutatás területéről származó módszereket ötvözi. A megoldandó feladatot deklaratívan, azaz a döntési változók és a rájuk vonatkozó korlátok felsorolásával modellezi, az így kapott modellt pedig egy általános korlátozás-alapú megoldó szoftver automatikusan megoldja. A feladat változása esetén elegendő a tömör, deklaratív modellt módosítani. Mindazonáltal, ha a cél egy bonyolult feladat gyors megoldása, akkor érdemes a megoldón belül futó algoritmusok, különféle keresési és következtetési módszerek részleteiben is elmerülni, és a feladat igényeinek megfelelően módosítani azokat.

A félév során a cél a pakolási feladat egy formális modelljének a definíciója, egy választott korlátozás-alapú megoldó megismerése, abban a feladat deklaratív modelljének az elkészítése. Különböző megoldási eljárásokkal fogunk kísérletezni, és néhány új, a feladathoz illeszkedő algoritmust fogunk fejleszteni.

 Szükséges előismeretek: algoritmuselméleti alapok, C++ vagy Java programozási nyelv, angol szövegértés. 

© 2010-2024 BME MIT | Hibajelentés | Használati útmutató