Çubuk Kesme Algoritması

[mikser]

Herkese selamlar,

senaryo şu:
elimizde 1200 cm lik çubuklar var. Bunlar belli uzunlukda kesilecek.

veri girisi şu sekilde

boy adet
200 3
275 1
100 5
900 4
754 1
300 8

gibi yani 3 tane 200 cm 1 tane 275 cm 5 tane 100 cm ......... gibi

problem : en az zaiyatla bu iş nası yapılır...

simdi 1200 lük çubugu aldık kesmeye basladık.
900 ü kestik (4 tane) kaldi 300 (4 tane) bu 300 ü kaldirip atmıycaz. 300 den cikabilecek parca varsa bu 300 den o parcayi kesecez... diyelim ki 275 ligi bundan kestik kaldi 25 bu 25 den kesebilecegimiz parca varmı ona bakacaz.
bu bööle gitcek....

bu konuda fikri olan bilgisi olan arkadaslarin yardımlarını rica ediyorum.

herkese iyi calismalar.

[rsimsek]

Yapılacak iş basit gibi görünsede birazcık matematik gerektiriyor Kesilecek olan en büyük boydan başlayıp büyük çubuk üzerine yerleştirilir. Kalan kısma hangi küçük parça yerleşiyorsa yerleştirilir. Daha sonra sığabilecek diğer boylar hesap edilir. Kalan fire bir yerde tutulur. Bu işlemi döngü içinde yapmak gerekir. Hatta büyük parçanın birini eksiltip onun yerine diğer parçalardan birer hatta iki birinden bir birinden, hatta her birinden birer tane koyup yeni fire hesaplanabilir.. En az fiye hangi yerleşimde ise o şekilde kesim dökümü listelenir. Bu olayın daha zoru çam, saç ve kumaş için de yapılmakta fakat şahsen uğraşmadığım için sadece fikrimi söyleyebildim

[aLonE CoDeR]

Merhaba.
Bunun için "Mod" komutunu kullanabilirsiniz.

Çıkabilecek adetleri buradan hesaplayarak kalan boru miktarına ulaşır ve diğer uzunluklar aynı işlemi gerçekleştirirsiniz..

Kolay gelsin.

[ibr_ozdemir]

ya bu algoritma buram buram okek obeb kokmuyomu
hay Allah matematiğimde berbattır ha
kolay gelsin

[rsimsek]

Farklı bir yapı daha kullanılabilir. Kesilecek çubuklar peşpeşe başlangıç ve bitiş noktaları belli olmak üzere birbirine eklendiği varsayılırsa, eldeki kesilmesi gereken parçalar sınırlar içerisine en az fire ile nasıl yerleştirilir o döngü halinde yapılabilir. Bunu da tüm parçalar yerleştirilip parçadan sınıra kadar olan kısımlar hesaplanıp en az fire verecek şekilde döngüye sokulabilir?? Tabi ki önce en iyi ve verimli yöntemi tespit edip ondan sonra kodlamak gerekir. Önceki mesajda söylendiği gibi en büyük ve en küçük ortak bölenden gidilerek net çıkabilecek kesimler yapılıp sıradan çıkarılarak kalan parçalar için çevrim sayısı azaltılabilir

[fduman]

bkz Lineer programlama. Optimizasyon.

Okulda bu tarz problemlerin hesaplanması için Lineer Programlama dersi vardı. Mühendislik fak. okuyan tanıdıklarınızla bir görüşün. Bunun için çeşitli hesaplama yolları var.Monte Karlo, Markov vs.. gibi. Çok zaman oldu.Aklımdan uçmuş. Ancak hesaplaması çok zor değildir. Gerçi biraz matris hesabına girer ama kolaydır. Önemli olan problemin matematiksel olarak net bir şekilde ortaya konabilmesi. Kısıtlar, kazançlar vs. gibi.

[fduman]

Bir de tek çubuk için düşünmeyin. Çubuk toplamına göre algoritmayı kurmanız gerekir. Yoksa optimum çözüme her zaman ulaşamayabilirsiniz.

[t-hex]

Merhaba,

Ben olayı bir grup veriyi 1200'e yakın toplamlar halinde nasıl gruplayabiliriz diye düşünüp şöyle bir kod yazdım, denedim bir sorun çıkmadı

Umarım işine yarar.

Kod: Tümünü seç

const Limit = 1200;
var
 Data : Tlist;
 i,J,Kalan : Integer;
 bitti:boolean;
begin
 // sonucu ekranda görmek için bir form üzerine bir listbox atıp
 // bu koduda bir buton click olayına ekleyebilirsin
 Data := TList.Create;
 // datayı yükleyelim, örneğin 900'lükten 4 tane ise ; listeye 4 adet 900 atıyoruz.
 for i := 1 to 4 do Data.Add(Pointer(900));
 for i := 1 to 4 do Data.Add(Pointer(300));
 for i := 1 to 2 do Data.Add(Pointer(275));
 // listeyi büyükten küçüğe sıralatıyoruz
 repeat
   bitti := true;
   Kalan := Limit;
   for i := 0 to Data.Count-1 do begin
      if Integer(Data[i]) > Kalan then continue;
      if Integer(Data[i]) =-1 then continue;
      Kalan :=Kalan - Integer(Data[i]);
      ListBox1.Items.Add(IntToStr(Integer(Data[i])));
      Data[i]:=Pointer(-1);
   end;
   ListBox1.Items.Add('-----');
   for  i:=0 to Data.Count-1 do bitti := (bitti) and (Integer(Data[i])=-1);
 until bitti;
 Data.Free;
end;

[mikser]

cevaplar için herkese tesekkur ederim...

t-hex, verdigin kodu derledim... bende farkli veriler girip denedim..
ilk etapda sonuclar guzel... daha fazla ve daha karmaşık verilerde ne yapacagini deneyecegim...


herkese tekrar tesekkurler...

[aLonE CoDeR]

Bir de tek çubuk için düşünmeyin. Çubuk toplamına göre algoritmayı kurmanız gerekir. Yoksa optimum çözüme her zaman ulaşamayabilirsiniz.

Bu tür algoritmalar kurulurken "Tüme varmak" yerine "Tümden gelme" yöntemi kullanılır..O nedenle elimizdeki toplam malzemeyle en az fire vermek şartıyla ne kadar sonuç alınabilir bu önemlidir..

Kolay gelsin.

[arl_13]

Herkese merhaba ben bu işlem için bir algoritma geliştirdim ancak en iyi sonucu bir türlü alamadım. Algoritmada fireleri ve varsayılan çubuk uzunluğumu kullanarak malzemeler arasında en büyük parçadan başlayarak kesim işlemini gerçekleştirdim.
Örneğin:
Elimde 3255 mm 13 adet, 1260 mm 21 adet, 4280 mm 9 adet, 2740 mm 33 adet fireler olsun Bir de 6000 mm den çok sayıda çubuğum olsun.Fireler öncelikli olmak üzere 3750 mm 16 adet, 2420 mm 8 adet, 2150 mm 24 adet, 425 mm 65 adet, 1530 mm 18 adet, 1050 mm 45 adet, 2890 mm 17 adet malzemeleri en az fire verecek şekilde nasıl kesmeliyim? Lineer programlama veya dinamik programlamayla tüm olasılıklar bulunabilir ancak uygun algoritmayı bir türlü oluşturamadım. Fireleri kullanarak kesimi tamamlayabiliyorum ancak en iyi sonuca ulaşamadım. Acaba bu konuda yardımcı olabilir misiniz? Nasıl bir yol izlemeliyim?