9. fejezet - Feladatok

Tartalom

Kombinatorikus optimalizálás
Átfogó problémák

Kombinatorikus optimalizálás

A következőkben [Imreh05]-ben szereplő feladatokat sorolunk fel. Minden egyes feladathoz implementálja a feladat megoldásához szükséges adatszerkezetet, és alkalmazza rá a jegyzetben ismertetett általános módszereket! Keresse meg az egyes feladattípusokhoz kifejlesztett módszerek implementációt, és hasonlítsa össze a futási eredményeiket, és futási idejüket a jegyzetben szereplő módszerek futási eredményeivel, és futási időivel!

  1. Munkák optimális kiosztása: Adott bizonyos számú munka, és ugyanannyi dolgozó. Az egyes dolgozók a munkákat különböző költséggel tudják végrehajtani. Osszuk szét az összes munkát a különböző dolgozók közt úgy, hogy minden dolgozó pontosan egy munkát kapjon, és a munkavégzés összköltsége minimális legyen!

  2. Házasságkötési játék: A telepesek egy n legényemberből álló kolóniája kiegészül n potenciális menyasszonnyal. Rövid udvarlás után a fiatalemberek elhatározzák, hogy haladéktalanul megházasodnak. Minden egyes menyasszonyjelölt kap névsort, melyen az n fiatalember neve szerepel, és ezen kell sorba rendeznie a férjjelölteket: a számára legmegfelelőbb kapja az 1-es számot, a következő választottja a 2-t, és így tovább. Tegyük fel, hogy bármely rögzített párválasztásnál a telep boldogsága a menyasszonyjelöltek által adott pontszámok összegével fordítottan arányos, azaz minél kisebb az összeg, annál nagyobb a boldogság. Határozzunk meg egy olyan párválasztást, amely az egész telep számára maximális boldogságot eredményez! (A közelítő módszerekkel nyert megoldások jóságát a magyar módszerrel ellenőrizze!)

  3. Raktárfelszámolási feladat: Adott egy raktár, ahol 2n páronként különböző tartalmú konténert tartalmaz. A szállítójárművek olyanok, hogy csak bizonyos párosokat képesek elszállítani. Minden szállítandó konténerpárra ismert az elszállítás költsége, mely függhet az illető konténerektől, a fogadó állomástól, stb. A feladat a raktár egy olyan kiürítése, amely minimális szállítási költséggel jár.

  4. Klaviatúra tervezése: Adott egy üres klaviatúra, és ismertek a billentyűk közti távolságok. Továbbá adott a klaviatúrára felvivendő jelkészlet, és ismert minden jelpárra a szövegekben egymás után történő előfordulásuk gyakorisága. Vigyük fel a billentyűzetre a jeleket úgy, hogy a gyakoriságszor a billentyűtávolságok minden jelpárra képzett összege minimális legyen. Ez azt eredményezi, hogy a lehető legkevesebb kézmozgással lehet begépelni a különféle szövegeket.

  5. Klaviatúra tervezése 2: Szeghalmy Szilvia diplomamunkájában hasonló módszerrel határozott meg egy optimális billentyűkiosztást. A billentyűk távolsága helyett a parlamenti gépírónők által az egyes billentyűk leütése közti időtartam lett figyelembe véve. Ezért a gépelés sebességét lehet ezzel a módszerrel gyorsítani

  6. Ütemezési modellek: Adottak bizonyos páronként különböző gépek és m számú munka, melyeket az 1, ..., m számokkal fogunk sorszámozni. A feladat az, hogy ütemezzük az egyes munkák végrehajtását a gépeken, úgy, hogy valamely cél szerint optimális ütemezést kapjunk. A munkák végrehajtásának ütemezésén azt értjük, hogy a j-edik munkát hozzárendeljük valamely géphez egy Sj kezdési és Cj befejezési idővel minden j-re. A munkákhoz minden modellben tartozik egy végrehajtási idő, amit pj-vel szokás jelölni. Ez azt adja meg, hogy mennyi ideig tart a munkát elvégezni. Ennek megfelelően a munkához rendelt kezdési és befejezési időkre a Cj-Sj=pj feltételnek kell teljesülni.

    A legismertebb modell az, ahol a munka befejezési idejét akarjuk minimalizálni. Szintén gyakran használt célfüggvény a befejezési idők összegfüggvénye, amelyet általánosíthatunk azzal, hogy a munkák szerint súlyozzuk a befejezési időket az összegben.

    Tovább bonyolítható a feladat azzal, hogy bizonyos munkák csak előírt sorrendben végezhetők el. (A tetőt csak azután lehet elkészíteni, ha állnak a falak.)

    Azzal is általánosítható a feladat, hogy más és más gépeken ugyanannak a munkának az elvégzése eltérő időtartamig tart.

  7. Adott a síkon bizonyos számú kliens, akiknek meghatározott igénye van egyfajta homogén szolgáltatásokra. Helyezzünk el adott számú kiszolgáló egységet a síkban úgy, hogy egyrészt biztosítsák a kliensek igényeinek kiszolgálását, másrészt a teljes kiszolgálás optimális legyen valamilyen szempont szerint.

    1. Például a kliensek legyenek falvak, míg a kiszolgálók iskolák. Helyezzük el az iskolákat úgy a falvakban, hogy a diákoknak összességében minimális távolságot kelljen utazni az iskolába!

    2. Legyenek a kliensek továbbra is falvak, míg a kiszolgálók tűzoltóállomások. Helyezzük el a tűzoltóállomásokat úgy a falvakban, hogy leghamarabb jussanak el a tűzoltók minden faluba!