Hátizsák feladat: 10 méretű a hátizsákunk, amibe tehetünk 4, 5, 5, 6 méretű tárgyakat,…
- 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).
- 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.
-
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.
-
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.
- 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.
- 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.
- 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:
- lépés: T1A és T1B létrejönnek.
- lépés: T2A és T2B létrejönnek.
- lépés: T3A és T3B létrejönnek.
- lépés: -
- lépés: T4A és T4B létrejönnek.
-
- 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).
- 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.
-
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.
-
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.
- 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.
- 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.
- 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:
- lépés: T1A és T1B létrejönnek.
- lépés: T2A és T2B létrejönnek.
- lépés: T3A és T3B létrejönnek.
- lépés: -
- lépés: Nincs további lépés, mivel nincs hely a T4 számára.
-
- 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?
- 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.
-
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.
-
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.
- 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.
- 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.
- 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.
-
- 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?
- 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.
-
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.
-
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.
- 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.
- 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.
- 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.
-