Sziasztok!
A következő lenne a feladat:
Vannak termékek: T1 T2 T2 ..., minden terméknek van egy ára.
Minden terméknek van valamilyen tulajdonsága: A B C D ...
Mondjuk T1(AAB) T2(ABCC) T3(AABB)
Van egy tulajdonság zsákom (AABBCC). Ki kell választanom az optimális termékcsomagot, amivel a tulajdonságaim megvalósíthatók. Optimálisnak a legolcsóbbat tekintjük. Eddig még nem jutott eszembe viszonylag hatékony algoritmus :(
Van ötlete valakinek?
- 1903 megtekintés
Hozzászólások
igen,
pl. konvex burok meghatározása ill. a költség koordináta szerinti minimuma adja a megoldást
- A hozzászóláshoz be kell jelentkezni
ez is csak ugyanaz a ló, tehát ez egy lináris programozási feladat
amire egy lehetséges megoldás a szimplex módszer
(ez az egész egyébként egyetemi tananyag operciókutatás név alatt fut, talán nem véletlenül :p)
- A hozzászóláshoz be kell jelentkezni
Igen, valami ilyesmi derengett nekem is, majd előkotrom az opkut jegyzeteimet. Köszi!
- A hozzászóláshoz be kell jelentkezni
Biztosan van ugyesebb megoldas, de most ezt tanulom, uh:
PTi: Az i-ik termek ara
PTiA: Az i-ik termek A tulajdonsagainak szama.
A: A cel A-k szama.
min(sum(PTi))
sum(PTiA) >= A
sum(PTiB) >= B
...
sum(PTiZZ) >= ZZ
ezt ugy tudod leirni, h felveszel egy vektort e, ami >= 0 erteket tartalmaz, aszerint, h az adott termekbol hany lesz.
p: a termekek aranak vektora
ta: a termekek a tulajdonsagainak vektora
min(e˙p)
e˙ta > A
...
e˙tzz > ZZ
e(i) >= 0
- A hozzászóláshoz be kell jelentkezni
Csak egy kérdés a feladat pontosításához:
A "tulajdonság zsákot" pontosan le kell fedni, vagy a kiválasztott termékek tulajdonságai lehetnek bővebbek is, mint a zsákban megadott? Pl. Baj-e ha a zsákban két "A" tulajdonság van, és a termékek összessége pedig három "A" tulajdonságot eredményezne?
- A hozzászóláshoz be kell jelentkezni
A termékek tulajdonságai lehetnek bővebbek is. Sőt, ha kell (AA) és a T(AAA) olcsóbb, mint 2db T(A) akkor azt kellene választani.
Időközben utánanéztem kicsit a szimplex algoritmusnak és kiderült, hogy egész számokra nem nagyon működik.
http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html#Q3
- A hozzászóláshoz be kell jelentkezni
mielott elolvasnam az URL-t, mondom: ez egy halmazfedesi feladat, koltseggel. hiszen specialis esetben, ha a zsakod csak ABCDEFGH..., akkor az alaphalmaz elemei az abece nagybetui, a reszhalmazok meg a portfoliok.
NP-nehez.
de van ra approximacios algoritmusok tomkelege.
ide meg soksok marhasagot irt mindenki, aki folytonosra vette a figurat, mert szerintem egeszerteku megoldasokat keresel, mar ha ertelmesen van megfogalmazva a feladat.
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne
- A hozzászóláshoz be kell jelentkezni
Hogy állsz "pentike" az algoritmus megvalósításával?
Van valami hatékony módszer a megoldásra? Érdekelne, mire jutottál.
- A hozzászóláshoz be kell jelentkezni