[es] - Algoritam za optimalno secenje materijala (sipke, etc.)

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.

Profil

Algoritam za optimalno secenje materijala (sipke, etc.)

^{15.09.2006. u 17:03}

Potreban mi je algoritam za optimalno secenje materijala, tj:
- imam metalne sipke odredjene duzine,
- imam skup elemenata razlicite duzine (manje od duzine sipke),
Potrebno je najoptimalnije iskombinovati elemente, tako da se dobije sto veca iskoriscenost matrerijala.

P.S. Da li bi mogao da se iskoristi knapsack algoritam (naravno uz odredjene modifikacije) za resenje ovog problema?

Inace kombinacija svakog elementa sa svakim (neki klasican metod) i racunanje iskoriscenosti dosta dugo traje tj n! tako da mi je potreban neki efikasniji algoritam...

cu.

^{15.09.2006. u 17:03}

broker

Član broj: 2415
Poruke: 8514
212.62.59.*

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{15.09.2006. u 17:06}

Ne zaboravi debljinu reza.

^{15.09.2006. u 17:06}

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
62.162.20.*

Jabber: dimitarmisev@gmail.com

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{15.09.2006. u 19:31}

Bas isti zadatak sam resavao na USACO (http://train.usaco.org).
U atachment je tekst zadatka i resenje.

Prikačeni fajlovi

Fence Rails.rar - 3.26k

^{15.09.2006. u 19:31}

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{15.09.2006. u 22:45}

Dobro, debljina reza je po meni trivijalnost kod ovog problema...

Vazan mi je algoritam, mozda ne i algoritam nego sam pristup problemu ;)

^{15.09.2006. u 22:45}

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{24.09.2006. u 15:21}

Pa sta je, zar se niko nije bavio ovim problemom?

^{24.09.2006. u 15:21}

genuine
Dragisa Jankovic
Beograd

Član broj: 101510
Poruke: 33
194.106.175.*

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{25.09.2006. u 01:38}

sta je optimalno iskoriscenje?

Necu vise da radim ,bre !

^{25.09.2006. u 01:38}

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{25.09.2006. u 07:45}

Pod optimalnim iskoriscenjem se podrazumeva da uradis takvu(e) kombinaciju(e) elemenata, da imas sto manji otpad.
Npr.
duzina elemenata: 3,4,5,8
duzina sipke: 8

Kombinacija koja nije optimalna je npr:
- na prvu sipku od 8m stavi se: 3+4 (iskoriscenost 7m + 1m otpad) 87%
- na drugu sipku od 8m stavi se: 5 (iskoriscenost 5m + 3m otpad) 62%
- na trecu sipku od 8m stavi se: 8 (iskoriscenost 8m + 0m otpad) 100%
Potroseno je ukupno 3 sipke od 8 metara, iskoriscenost je 20 a otpad su dve sipke od 1m i 3m.
Broj secenja je 2+1=3

Kombinacija koje je optimalnija od prethodne:
- na prvu se stavi: 3+5 (iskoriscenost 8m + 0m otpad) 100%
- na drugu se stavi: 8 (iskoriscenost 8m + 0m otpad) 100%
- na trecu se stavi: 4 (iskoriscenost 4m + 4m otpad) 50%
Potroseno je 3 sipke od 8m, iskoriscenost je 20m, otpad je sipka od 4m.
Broj secenja je 1+0+1=2

Vidi se da je druga kombinacija optimalnija, jer je otpad jedna veca sipka potreban je manji broj rezova...

Ovo je samo neki primer sa malim brojem elemenata, tako da se ovo moze uraditi i rucno. Ukupan broj svih kombinacija je 4!.
Ali kod veceg broja elemenata broj kombinacija naraste id do 30! (za 30 elemenata), tako da brute force bas i nije najzgodniji algoritam za ovaj posao...

Meni se cini da je ovaj problem slican kao knapsack algoritam, sa kojim sam i probao nesto (a verovatno cu i nastaviti), ali ako neko ima neko prostije resenje...

P.S.
Na netu sam pronasao, kod vise izvora, da kod problema gde se broj "resenja" uvecava eksponencijalno, pozeljno je koristiti genetske algoritme (malo teze za implementaciju).

^{25.09.2006. u 07:45}

genuine
Dragisa Jankovic
Beograd

Član broj: 101510
Poruke: 33
194.106.175.*

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{26.09.2006. u 01:52}

Jos par pitanja... da li mozes da klasifikujes predmete u kategorije .. recimo sve sto se ralikuje za recimo par % stavis u kategoriju sipke duzine 4 +- 2% komada 10 i sl.. pa da umesto sa konkretnim primercima da radis sa kategorijama... nije najoptimalnije ali mislim da ne bi trebalo da % ili %% uticu na kvalitet algoritma... isto tako ako bi recimo sklapao sipke na osnovu kategoria mogao bi da primenis foru iz nekog algoritma za nalazenje minimalnog rasplinuceg stabla... fora je valjda da ako odaberes kombinaciju koja daje najmanju gresku od svih ostalih onda ona ulazi u krajnje resenje.. problem je kako je pronaci.. mozda ukoliko bi resenje trazio po intervalima .. recimo nadji sva resenja koja imaju gresku manju od 1%.. ako je samo jedno onda ga prihvati ako ih ima vise onda ih trazi polovljenjem intervala...

ja nisam neki programer sto se tice ovakvih zezancija.. nadam se da nisam previse lupao... ako jesam ne zamerite mi .. pozdrav...

Necu vise da radim ,bre !

^{26.09.2006. u 01:52}

trodon
Bojan Petrovic
Beograd

Član broj: 14115
Poruke: 212
*.dynamic.sbb.co.yu.

Sajt: (none)

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{12.05.2007. u 15:43}

Moze se reshiti i linearnim programiranjem (operaciona istrazivanja).

^{12.05.2007. u 15:43}

Promaja
Beograd

Član broj: 145514
Poruke: 2
80.93.243.*

Profil

Re: Algoritam za optimalno secenje materijala (sipke, etc.)

^{17.05.2007. u 10:26}

Kao sto je neko ovde naveo i meni ovo mnogo vise lici na problem ranca.

A ukoliko te zainteresuje problem pakovanja i secenja preporucio bih ti da pogledas nesto o linearnom programiranju, genetskim i algoritmima simuliranog kaljenja

^{17.05.2007. u 10:26}