Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 4, 5, 5, 6 méretű tárgyakat,…

  1. User

    Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 4, 5, 5, 6 méretű tárgyakat, rendre 6, 3, 5, 2 értékkel.

    Töltsd ki a táblázatot pontosan 2 tizedes jegyre kerekített értékekkel ("tizedesponttal", pl. 1.50 vagy 2.00):

    Tárgyak Méret Érték Rel.haszn. T1 4 6 T2 5 3 T3 5 5 T4 6 2 Old meg a Branch&Bound fa első 5 részfeladatát úgy, hogy válaszd mindig a legnagyobb célfüggvényértékű lezáratlan részfeladatot szétválasztásra! Szétválasztásnál az xi= 0 eset a kisebb sorszámú, xi= 1 eset a nagyobb sorszámú részfeladat lesz (csak törtértékű változót választunk szét).

  2. Assistant

    Először is kiszámítjuk a relatív hasznosítási értékeket a tárgyaknak, ami az érték/méret hányadosa lesz:

    Tárgyak Méret Érték Rel.haszn. T1 4 6 1.50 T2 5 3 0.60 T3 5 5 1.00 T4 6 2 0.33

    Ezután elindítjuk a Branch&Bound algoritmust.

    Megjegyzés: A-zal jelölt részfeladatok az xi=0 esetek, B-zal az xi=1 esetek.

    1. lépés (gyökér részfeladat): A legnagyobb relatív hasznosítást T1 hozza, így ezt választjuk szétválasztásra. T1A és T1B részfeladatok létrejönnek.

    2. lépés: T1A részfeladat célfüggvényértéke: 10 méretből 0 T1 esetén 10 marad a többi tárgyra. T1B részfeladat célfüggvényértéke: 10 méretből 1 T1 esetén 6 marad, és az értéke 6.

    T1B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T2 szétválasztásra kerül: T2A és T2B részfeladatok létrejönnek.

    1. lépés: T2A részfeladat célfüggvényértéke: 6 méretből 0 T2 esetén 6 marad a többi tárgyra, érték: 6. T2B részfeladat célfüggvényértéke: 6 méretből 1 T2 esetén 1 marad, érték: 6+3=9.

    T2B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T3 szétválasztásra kerül: T3A és T3B részfeladatok létrejönnek.

    1. lépés: T3A részfeladat célfüggvényértéke: 1 méretből 0 T3 esetén 1 marad. T3B részfeladat célfüggvényértéke: Nem létezik, mivel nem fér el több T3 a hátizsákban.

    Az új lezáratlan részfeladatok közül T2B-nek van a legnagyobb célfüggvényértéke, így tovább folytatjuk vele.

    1. lépés: T2B részfeladatban T4-t választjuk szétválasztásra: T4A és T4B részfeladatok létrejönnek.

    T4A részfeladat célfüggvényértéke: Nem létezik, mivel nem fér el további tárgy a hátizsákban. T4B részfeladat célfüggvényértéke: Nem létezik, mivel nem fér el T4 a hátizsákban.

    Összefoglalva:

    1. lépés: T1A és T1B létrejönnek.
    2. lépés: T2A és T2B létrejönnek.
    3. lépés: T3A és T3B létrejönnek.
    4. lépés: -
    5. lépés: T4A és T4B létrejönnek.
  3. User

    Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 4, 5, 5, 6 méretű tárgyakat, rendre 6, 3, 5, 2 értékkel.

    Töltsd ki a táblázatot pontosan 2 tizedes jegyre kerekített értékekkel (“tizedesponttal”, pl. 1.50 vagy 2.00):

    Tárgyak Méret Érték Rel.haszn. T1 4 6 T2 5 3 T3 5 5 T4 6 2 Old meg a Branch&Bound fa első 5 részfeladatát úgy, hogy válaszd mindig a legnagyobb célfüggvényértékű lezáratlan részfeladatot szétválasztásra! Szétválasztásnál az xi= 0 eset a kisebb sorszámú, xi= 1 eset a nagyobb sorszámú részfeladat lesz (csak törtértékű változót választunk szét).

  4. Assistant

    Először is kiszámítjuk a relatív hasznosítási értékeket a tárgyaknak, ami az érték/méret hányadosa lesz:

    Tárgyak Méret Érték Rel.haszn. T1 4 6 1.50 T2 5 3 0.60 T3 5 5 1.00 T4 6 2 0.33

    Ezután elindítjuk a Branch&Bound algoritmust.

    Megjegyzés: A-zal jelölt részfeladatok az xi=0 esetek, B-zal az xi=1 esetek.

    1. lépés (gyökér részfeladat): A legnagyobb relatív hasznosítást T1 hozza, így ezt választjuk szétválasztásra. T1A és T1B részfeladatok létrejönnek.

    2. lépés: T1A részfeladat célfüggvényértéke: 10 méretből 0 T1 esetén 10 marad a többi tárgyra. T1B részfeladat célfüggvényértéke: 10 méretből 1 T1 esetén 6 marad, és az értéke 6.

    T1B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T2 szétválasztásra kerül: T2A és T2B részfeladatok létrejönnek.

    1. lépés: T2A részfeladat célfüggvényértéke: 6 méretből 0 T2 esetén 6 marad a többi tárgyra, érték: 6. T2B részfeladat célfüggvényértéke: 6 méretből 1 T2 esetén 1 marad, érték: 6+3=9.

    T2B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T3 szétválasztásra kerül: T3A és T3B részfeladatok létrejönnek.

    1. lépés: T3A részfeladat célfüggvényértéke: 1 méretből 0 T3 esetén 1 marad. T3B részfeladat célfüggvényértéke: Nem létezik, mivel nem fér el több T3 a hátizsákban.

    Az eddig négy lépéseben T1-t, T2-t és T3-at vettük figyelembe. A 5. lépésben T4-et kell szétválasztanunk.

    1. lépés: T4 helyett azonban nincs lezáratlan részfeladat, amelyben elegendő hely lenne a hátizsákban a T4 számára. Ezért további részfeladat nem generálható.

    Összefoglalva:

    1. lépés: T1A és T1B létrejönnek.
    2. lépés: T2A és T2B létrejönnek.
    3. lépés: T3A és T3B létrejönnek.
    4. lépés: -
    5. lépés: Nincs további lépés, mivel nincs hely a T4 számára.
  5. User

    Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 2, 6, 5, 6 méretű tárgyakat, rendre 4, 4, 6, 3 értékkel.

    Töltsd ki a táblázatot pontosan 2 tizedes jegyre kerekített értékekkel ("tizedesponttal", pl. 1.50 vagy 2.00):

    Tárgyak Méret Érték Rel.haszn. T1 2 4 T2 6 4 T3 5 6 T4 6 3 Old meg a Branch&Bound fa első 5 részfeladatát úgy, hogy válaszd mindig a legnagyobb célfüggvényértékű lezáratlan részfeladatot szétválasztásra! Szétválasztásnál az xi= 0 eset a kisebb sorszámú, xi= 1 eset a nagyobb sorszámú részfeladat lesz (csak törtértékű változót választunk szét).

    Válaszolj az alábbi kérdésekre (ha nincs megfelelő részfeladat, vagy érték írj "-"-t, több esetén növekvő sorrendben, szóközzel elválasztva, pl: "1 2 4"):

    a) Hányas részfeladat(ok) lezárt(ak)?

    b) Hányas részfeladat(ok) kizárt(ak)?

    c) Mi az aktuális alsókorlát (pl. 2)?

    d) Mi az eddigi legjobb megoldás értéke (pl. 5)?

    e) Az eddigi legjobb megoldásban az x értéke? (pl. "1 0 1 1" ha csak x2=0)

    f) Optimális?

  6. Assistant

    Először is kiszámítjuk a relatív hasznosítási értékeket a tárgyaknak, ami az érték/méret hányadosa lesz:

    Tárgyak Méret Érték Rel.haszn. T1 2 4 2.00 T2 6 4 0.67 T3 5 6 1.20 T4 6 3 0.50

    Ezután elindítjuk a Branch&Bound algoritmust.

    1. lépés (gyökér részfeladat): A legnagyobb relatív hasznosítást T1 hozza, így ezt választjuk szétválasztásra. T1A és T1B részfeladatok létrejönnek.

    2. lépés: T1A részfeladat célfüggvényértéke: 10 méretből 0 T1 esetén 10 marad a többi tárgyra. T1B részfeladat célfüggvényértéke: 10 méretből 1 T1 esetén 8 marad, és az értéke 4.

    T1A részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T3 szétválasztásra kerül: T3A és T3B részfeladatok létrejönnek.

    1. lépés: T3A részfeladat célfüggvényértéke: 10 méretből 0 T3 esetén 10 marad. T3B részfeladat célfüggvényértéke: 10 méretből 1 T3 esetén 5 marad, és az értéke 6.

    T3B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T1 szétválasztásra kerül: T1C és T1D részfeladatok létrejönnek.

    1. lépés: T1C részfeladat célfüggvényértéke: 5 méretből 0 T1 esetén 5 marad, érték: 6. T1D részfeladat célfüggvényértéke: 5 méretből 1 T1 esetén 3 marad és az értéke 6+4=10.

    T1C részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű (közös célfüggvényérték esetén a kisebb sorszámú részfeladatot választjuk) és T2 szétválasztásra kerül: T2C és T2D részfeladatok létrejönnek.

    1. lépés: T2C részfeladat célfüggvényértéke: 5 méretből 0 T2 esetén 5 marad, érték: 6. T2D részfeladat célfüggvényértéke: Nem létezik, mivel nem fér el T2 a hátizsákban.

    Válaszok:

    a) Hányas részfeladat(ok) lezárt(ak)? 2C és 2D

    b) Hányas részfeladat(ok) kizárt(ak)? 2D

    c) Mi az aktuális alsókorlát (pl. 2)? 6 (a még nyitott T1A és T3A célfüggvényértékéből)

    d) Mi az eddigi legjobb megoldás értéke (pl. 5)? 10

    e) Az eddigi legjobb megoldásban az x értéke? (pl. "1 0 1 1" ha csak x2=0) "1 0 1 0"

    f) Optimális? Nem feltétlenül, mivel a T1A és T3A részfeladatok még mindig nyitottak, és további vizsgálatra szorulnak a tárgyak optimális elrendezésének megtalálása érdekében.

  7. User

    Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 2, 6, 5, 6 méretű tárgyakat, rendre 4, 4, 6, 3 értékkel.

    Töltsd ki a táblázatot pontosan 2 tizedes jegyre kerekített értékekkel (“tizedesponttal”, pl. 1.50 vagy 2.00):

    Tárgyak Méret Érték Rel.haszn. T1 2 4 T2 6 4 T3 5 6 T4 6 3 Old meg a Branch&Bound fa első 5 részfeladatát úgy, hogy válaszd mindig a legnagyobb célfüggvényértékű lezáratlan részfeladatot szétválasztásra! Szétválasztásnál az xi= 0 eset a kisebb sorszámú, xi= 1 eset a nagyobb sorszámú részfeladat lesz (csak törtértékű változót választunk szét).

    Válaszolj az alábbi kérdésekre (ha nincs megfelelő részfeladat, vagy érték írj “-”-t, több esetén növekvő sorrendben, szóközzel elválasztva, pl: “1 2 4”):

    a) Hányas részfeladat(ok) lezárt(ak)?

    b) Hányas részfeladat(ok) kizárt(ak)?

    c) Mi az aktuális alsókorlát (pl. 2)?

    d) Mi az eddigi legjobb megoldás értéke (pl. 5)?

    e) Az eddigi legjobb megoldásban az x értéke? (pl. “1 0 1 1” ha csak x2=0)

    f) Optimális?

  8. Assistant

    Először is kiszámítjuk a relatív hasznosítási értékeket a tárgyaknak, ami az érték/méret hányadosa lesz:

    Tárgyak Méret Érték Rel.haszn. T1 2 4 2.00 T2 6 4 0.67 T3 5 6 1.20 T4 6 3 0.50

    Ezután elindítjuk a Branch&Bound algoritmust.

    1. lépés (gyökér részfeladat): A legnagyobb relatív hasznosítást T1 hozza, így ezt választjuk szétválasztásra. T1A és T1B részfeladatok létrejönnek.

    2. lépés: T1A részfeladat célfüggvényértéke: 10 méretből 0 T1 esetén 10 marad a többi tárgyra. T1B részfeladat célfüggvényértéke: 10 méretből 1 T1 esetén 8 marad, és az értéke 4.

    T1A részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T3 szétválasztásra kerül: T3A és T3B részfeladatok létrejönnek.

    1. lépés: T3A részfeladat célfüggvényértéke: 10 méretből 0 T3 esetén 10 marad. T3B részfeladat célfüggvényértéke: 10 méretből 1 T3 esetén 5 marad, és az értéke 6.

    T3A részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T2 szétválasztásra kerül: T2A és T2B részfeladatok létrejönnek.

    1. lépés: T2A részfeladat célfüggvényértéke: 10 méretből 0 T2 esetén 10 marad, érték: 0. T2B részfeladat célfüggvényértéke: 10 méretből 1 T2 esetén 4 marad és az értéke 4.

    T3B részfeladatot választjuk szétválasztásra, mivel a legnagyobb célfüggvényértékű és T1 szétválasztásra kerül: T1C és T1D részfeladatok létrejönnek.

    1. lépés: T1C részfeladat célfüggvényértéke: 5 méretből 0 T1 esetén 5 marad, érték: 6. T1D részfeladat célfüggvényértéke: 5 méretből 1 T1 esetén 3 marad és az értéke 6+4=10.

    Válaszok:

    a) Hányas részfeladat(ok) lezárt(ak)? T2A és T2B

    b) Hányas részfeladat(ok) kizárt(ak)? Nincs kizárt részfeladat az első 5 lépésben.

    c) Mi az aktuális alsókorlát (pl. 2)? 0 (T2A részfeladat értéke)

    d) Mi az eddigi legjobb megoldás értéke (pl. 5)? 10 (T1D részfeladat értéke)

    e) Az eddigi legjobb megoldásban az x értéke? (pl. "1 0 1 1" ha csak x2=0) "1 0 1 0"

    f) Optimális? Nem feltétlenül, mivel a T1A és T3A részfeladatok még mindig nyitottak, és további vizsgálatra szorulnak a tárgyak optimális elrendezésének megtalálása érdekében.