Doğrusal malzemeleri kesmek için program. Kesme optimizasyon programı

Malzemelerin ekonomik doğrusal kesimi (kalıpların kesilmesi) birçok endüstri ve inşaat için geçerlidir. Bu, ağaç işleme, kesme çubukları, takviye çubukları, köşebentler, kanallar, borular, I-kirişlerde boşluklara kütükler ve levhalar kesmektir ...

Metal yapıların ve makine mühendisliğinin üretiminde, kağıt hamuru ve hafif sanayide ruloların kağıt ve kumaş ile enine kesilmesi.

Görünen basitliğe rağmen, lineer kesme problemlerinin çözümü çok kolay değil, buna değer. Kalıplanmış malzemeleri kesmek için bilimsel bir yaklaşımın tanıtılması, bunların maliyetini bazen %10'dan fazla azaltmanıza olanak tanır! Makaleyi sonuna kadar okuyun ve bu kelimelerin doğru olduğundan emin olun.

Ele alınan konu, görevlerle ilgilidir. doğrusal programlama. Bu tür sorunları çözmek için son 70 yılda bilim adamları birkaç farklı yöntem geliştirdiler.

Endeks yöntemi L.V. Kantorovich ve V.A. Belli bir beceriye sahip Zalgallera, kullanmadan "manuel" yapmanızı sağlar. bilgisayar Bilimi Doğrusal kesmeyi etkin bir şekilde gerçekleştirin. Meraklı okuyuculara, yukarıda adı geçen yazarların “Endüstriyel Malzemelerin Rasyonel Kesimi” kitabını okuyarak bu yöntemi tanımalarını tavsiye ederim.

L.V.'nin fikirlerine dayanan simpleks yöntemi. Kantorovich, 20. yüzyılın ortalarında ABD'den bir dizi bilim adamı tarafından ayrıntılı olarak tanımlanmış ve geliştirilmiştir. Eklenti MS Excel "Çözüm arayın" (Çözücü) bu algoritmayı kullanır. İşte bu yöntemlemükemmelbu yazımızda lineer kesim problemini çözeceğiz.

Daha sonra genetik, açgözlü ve karınca kolonisi algoritmaları ortaya çıkmış ve geliştirilmiştir. Bununla birlikte, teoriler ormanına tırmanmadan kendimizi onları listelemek ve işe koyulmakla sınırlayacağız (orada, “vahşi doğada” olmasına rağmen, çok ilginçtir).

Excel'i açın ve basit örnek metal çubukları parçalara ayırmak, çözümlerden biriyle tanışalım pratik görevler doğrusal kesme. Matematikçiler genellikle bu probleme "kesme problemi" derler.

Örnek için ilk verileri icat etmedim, ancak Pokrovsky M.A.'nın makalesinden aldım. FGBOU VPO "MSTU im. N.E. Bauman (bağlantı:ingilizce. bmstu. tr/ doktor/775784. html).

Takip ettiğim amaç, sorunu çözmenin sonuçlarını karşılaştırmaktı.

MS Excel'de doğrusal kesme problemini çözme örneği.

Şunda anlaşalım:

1. Kütük, çubuk, şerit, çubuk vb. şeklinde hammaddedir. aynı uzunlukta.

2. Detaylar, orijinal boşlukları parçalara ayırarak elde edilmesi gereken unsurlardır.

3. Testere genişliği, kesme, ovma sıfıra eşit alınır.

Görev:

Siparişlerden birini tamamlamak için, tedarik bölümü, 1500 mm uzunluğundaki aynı çubuk-boşluklardan kombine makaslarda üç standart boyutta parça parçalamalıdır:

151 adet 330 mm uzunluğunda

206 adet 270 mm uzunluğunda

163 adet 190 mm uzunluğunda

Minimum malzeme kullanan ve buna bağlı olarak minimum fire veren optimal kesim planının bulunması gerekmektedir.

İlk veri:

1. Orijinal boşlukların uzunluğu Lh milimetre cinsinden birleşik hücreye yazıyoruz

D3E3F3: 1500

2. numaralar atarız i hücrelerde en uzundan en kısaya kadar tüm standart boyutlardaki parçalar

D4; E 4; F4: 1; 2; 3

3. Parça uzunlukları Ldi milimetre cinsinden yazıyoruz

D5; E5; F5: 330; 270; 190

4. Detay sayısı Ndi parçalar halinde koymak

D6; E6; F6: 151; 206; 163

5. çok başlayalım dönüm noktası- kesme seçeneklerini doldurma.

Hatırlamak ve anlamak gerekir Bu işi yapmak için 2 ilke.

1. Atık uzunlukları en küçük parçadan ( 0< lo j < Lddk ).

2. Parçaları, en büyük ve en fazla sayıda iş parçasına, sürekli olarak azalan yönde hareket ederek “döşemeye” başlıyoruz.

Kesim seçeneğinde parça boyutu yoksa hücreyi boş bırakırız, tablonun görsel algısını kolaylaştırmak için sıfır yazmayacağız.

1 numaralı kesme seçeneği:

1 numaralı 5 parçayı bir boşluktan kesme girişimi imkansızdır, bu yüzden hücreye yazıyoruz

Yuvaya 2 numaralı parçayı veya 3 numaralı parçayı eklemek de imkansız, bu yüzden hücreleri boş bırakıyoruz

2 numaralı kesme seçeneği:

1 No'lu parça sayısını önceki sürümden 1'er azaltıp içine yazıyoruz.

2 parça No. 2'yi eklemeye çalışıyoruz - çalışmıyor, bu yüzden ekliyoruz

Kesimi 3 numaralı detayla tamamlamak mümkündür. içine giriyoruz

Dile getirilen ilkelere bağlı kalarak, mümkün olan her şeyi analoji ile dolduruyoruz. bu durum 18 kesme seçeneği.

Birkaç kesme seçeneği tablosunu kendiniz yaptıktan sonra, eylemlerin mantığını anlayacaksınız ve bu çalışma için birkaç dakika harcayacaksınız.

Kesim sırasında birinci prensip yerine getirilmezse, çıkış uzunluğu olan hücre otomatik olarak kırmızıya boyanır. Koşullu biçimlendirme hücrelere uygulanan G7…G24 bu çalışmada size açıkça yardımcı olacaktır.

H7 hücrelerinde ... H24 hiçbir şey yazmayın! Çözümün sonucunu göstermek için kullanılırlar!

Çözüm için hazırlanıyor:

* G7 ... G24 hücrelerinde, kesim sonucu kalan atık (kesme) uzunlukları formüle göre hesaplanır.

lo j = L h -Σ (Ldi * Ndij )

6. Uygulanan tüm yerleştirme seçeneklerine göre yapılan her standart boyutun parça sayısı, formüle göre D26, E26 ve F26 hücrelerinde hesaplanacaktır.

Ndikireç = Σ (Ndij * Nhj )

Çözümün sonunda bulunan kesim planındaki parça sayısı aşağıdakilere tam olarak uymalıdır. verilen miktar detaylar!

7. Optimal kesme planını tamamlamak için gereken iş parçası sayısı, formül kullanılarak D27E27F27 birleşik hücresinde belirlenecektir.

N hesap =ΣN hj

8. Tüm parçaların doğrusal bir yerleşimini gerçekleştirmek için gereken tüm boşlukların toplam uzunluğu, formül kullanılarak birleştirilmiş D28E28F28 hücresinde hesaplanacaktır.

Lh Σ = L h*Nhesaplamadan

9. Bulunan kesim planının yürütülmesinden kaynaklanan tüm atıkların toplam uzunluğu, formül kullanılarak kombine D29E29F29 hücresinde hesaplanacaktır.

Lhakkında Σ = Σ (Lhakkındaj * Nhj )

10. Kullanılan toplam malzeme miktarından optimal doğrusal kesim planı tarafından üretilen atık oranı, formül kullanılarak birleştirilmiş D30E30F30 hücresinde hesaplanacaktır.

o = Lo Σ /Lз Σ

Çözüm:

Hazırlık tamamlandı, bir iş parçasının parçalara en uygun şekilde kesilmesi için 18 seçenek belirlendi ve gerekli tüm formüller girildi. Şimdi asıl sorunu çözmemiz gerekiyor: belirlemek optimum kesme planı - kaç boşluk ve hangi kesme seçeneklerine göre kesileceği nihayet gerekli tüm parçaları minimum atıkla doğru miktarda elde etmek.

1. Ana menüde "Servis" - "Çözüm arayın ..." öğesini seçin.

2. Görünen aynı adı taşıyan "Çözüm arayın" penceresinde ayarları yapıyoruz.

2.1. Atamak amaç fonksiyonu toplam atık uzunluğu Lo Σ ve bağlantıyı hedef hücre penceresine girin.

2.2. "Equal:" anahtarını "minimum değer" konumuna getirin.

2.3. Değişken içeren hücreleri belirtin Nz j Hücreleri Değiştirme penceresinde.

2.4. Aynı adı taşıyan pencereye kısıtlamalar giriyoruz. Koşullar olarak, verilenlerin eşitliği ihtiyacını belirtiriz. Nd ben ve yerleşim Nd icalc parça sayısı ve değişkenler Nz j- seçenekleri keserek tahmini boşluk sayısı - bir kısıtlama uyguluyoruz: bunlar tamsayı olmalıdır.

3. "Parametreler" butonuna basıyoruz ve açılan "Çözüm arama parametreleri" penceresinde aşağıdaki ekran görüntüsündeki gibi ayarları yapıyoruz. Tamam butonu ile pencereyi kapatın.

4. "Çözüm ara" penceresinde, "Çalıştır" düğmesini tıklayın ve Excel'in bir çözüm bulmasını bekleyin. Bu bir kaç dakika sürebilir.

5. Bulunan çözümü OK butonu ile kaydettikten sonra, sonuçlar Excel sayfasında H7 ... H24 hücrelerinde görüntülenecektir.

Aşağıdaki resim bulunan optimal lineer kesme planını göstermektedir.

Sonuç nedir?

Bu makalede tartışılan gibi görevler için Excel boşluklarında doğrusal kesim, yukarıda açıklanan yöntemle 10-15 dakika içinde gerçekleştirilir! “Manuel”, Kantorovich indekslerinin yöntemini bilmeden böyle bir zamanda bir çözüm bulamazsınız.

"Çözüm ara"yı farklı arama parametreleriyle birkaç kez çalıştırarak, boşlukları kesmek için 5 farklı plan bulmayı başardık. Tüm 5 plan aynı sayıda boşluk gerektirir - 93 ve sadece %2.21 atık verir!!! Bu planlar, Pokrovsky tarafından hesaplanan plandan neredeyse %6 daha iyi ve "Geleneksel" plandan %10'dan daha ekonomiktir (makalenin ilk bölümündeki orijinal kaynağa bağlantıya bakın). Hızlı ve pahalı programlar kullanılmadan çok değerli bir sonuç elde edildi.

bu not alınmalı Excel eklentisi Doğrusal programlama problemlerinin çözümünde simpleks yöntemini kullanan Çözücü ("Çözüm Arayın") 200'den fazla değişkenle çalışamaz. Ele aldığımız lineer kesme problemine uygulandığında, bu, kesme sayısının 200 varyantı geçemeyeceği anlamına gelir. İçin basit görevler Yeter. Daha karmaşık problemler için, "açgözlü" bir algoritmanın "karışımını" uygulamaya çalışmalısınız ve tek yönlü yöntemÇözücü, arasından seçim tam liste 200'den fazla ekonomik kesim yok. Sonra sabrımızı stoklar ve sonuçlara ulaşırız. Karmaşık bir sorunu birkaç basit soruna bölmeyi deneyebilirsiniz, ancak bulunan çözümün “optimallik düzeyi” büyük olasılıkla daha düşük olacaktır.

Belki de lineer kesme sorunlarını çözmek için düşünülen seçenek “akrobasi” değildir, ancak birçok endüstrideki “geleneksel” yaklaşıma kıyasla kesinlikle bir adım ileridir.

MS Excel "Çözüm Ara" (Çözücü) eklentisinin kullanımı, bir makalede blogda zaten tartışılmıştı. Bu harika aracın yakın ilgiye değer olduğunu ve bir dizi yeni önemsiz sorunu zarif ve hızlı bir şekilde çözmeye bir kereden fazla yardımcı olacağını düşünüyorum.

not İnternette bulduğum en iyi ücretsiz lineer kesme yazılımına bağlantılar:

http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html

http://forum-okna.ru/index.php?app=core&module=attach§ion=attach &attach_id=7508

http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74

http://www.planetcalc.ru/917/

Son iki bağlantıdaki programlar açgözlü buluşsal yöntemler uygular ve 103 boşluk kullanarak makaledeki görevde doğrusal iç içe yerleştirme gerçekleştirir. Açgözlü algoritmaların kullanımı, kesme işleminin toplam süresini çok fazla azaltmanın gerekli olduğu durumlarda haklı çıkar. çok sayıda daha optimal planlarda kesim seçenekleri.

"İncelemeler" bloğundaki yazının altına yorumlarınızı yazabilirsiniz sevgili okurlar.

Yuvalama sorunlarını çözmek için Doğrusal programlama modelleri bölümüne bakın.

Örnek 1. Ürün:% s kağıt şirketi 2 metre - standart genişlikte kağıt rulolar şeklinde verilir. Tüketicilerin özel siparişlerinde şirket, standart ruloların kesildiği diğer boyutlarda rulolar tedarik eder. Tipik rulo siparişleri standart boyutlar tabloda verilmektedir.

Bu tür kombinasyonları bulmak için gereklidir. Çeşitli seçenekler gelen siparişleri minimum kayıpla (atık) tam olarak karşılamak için standart ruloları kesmek.
Standart bir ruloyu kesmek için tüm olası seçenekleri ele alalım, ilgili verileri Tablo'da vereceğiz.

Rulo Genişliği (m)	Rulo kesme seçenekleri						Minimum rulo sayısı
	1	2	3	4	5	6
0,5	0	2	2	4	1	0	150
0,7	1	1	0	0	2	0	200
0,9	1	0	1	0	0	2	300
m cinsinden atık	0,4	0,3	0,1	0	0,1	0,2	-

Değişkenleri tanımlayalım:
X j - seçeneğe göre kesilen standart rulo sayısı j, j=1, 2, 3,4,5, 6.
Sınırlamalar, gerekli sayıda standart dışı rulonun üretilmesini sağlama gerekliliği ile doğrudan ilgilidir. Tablodaki verileri kullanarak şunları elde ederiz:
2X 2 + 2 X 3 + 4 X 4 + X 5 \u003d 150 - 0,5 m genişliğinde rulo sayısı,
X 1 + X 2 + 2 X 5 \u003d 200 - 0,7 m genişliğindeki rulo sayısı,
X 1 + X 3 + 2 X 6 \u003d 300 - 0,9 m genişliğindeki rulo sayısı.

Toplam kağıt kaybı (atık) miktarı (m cinsinden) ifadesi
0,4X 1 + 0,3 X 2 + 0,1 X 3 + 0,1 X 5 + 0,2 X 6.

Böylece, matematiksel model içinde Genel görünüm forma sahip
min f (x) \u003d 0.4 X 1 + 0.3X 2 + 0.1X 3 + 0.1X 5 + 0.2X 6.
kısıtlamalar ile:
2X 2 + 2 X 3 + 4 X 4 + X 5 = 150
X 2 + X 2 + 2 X 5 = 200
X 2 + X 3 + 2 X 6 = 300

Malzeme kesme sorunu

Bu görev, malzemeleri keserken veya sağlarken minimum atıkla (uzunluk, alan, ağırlık, maliyet vb.) gerekli ürün setini sağlayan bir plan geliştirmektir. azami sayıürün setleri. Örnek #2. Standart çelik sacların kesilmesi için optimal bir plan geliştirmek, bir grup çelik sacdan dört tip farklı boşluğun kesilmesi gerektiği biliniyorsa, minimum toplam atık ile farklı türlerde planlanan sayıdaki işlenmemiş parçanın çıktısını sağlamalıdır. b ben (i = 1, 2, ..., 4) adet miktarında. Standart boyutlardaki bir çelik sac dört şekilde kesilebilir. her birine olası yol kesim, kesim tablosuna karşılık gelir. Kesim tablolarından, parçalar halindeki boşlukların çıktısı bilinmektedir. farklı şekiller a ij (i = 1, 2,…4; j = 1,2,…,4) ve ayrıca atık alanı c j (j = 1, 2,…,n) j-th kesme yöntemi. İsrafın minimum düzeyde olması için şu veya bu şekilde kaç çelik levha kesilmelidir?

Tablo 3

Çeşit boşluklar	Boşluk sayısı için görev planı (b 1)	Farklı tiplerde boşlukların (adet) çıktısı yuvalama çizelgelerinden (a ij)
		1	2	3	4
1	240	1	4	0	1
2	200	1	0	4	0
3	120	1	0	0	3
4	140	1	1	0	3
Atık alanı, m 2 (cj)		1,4	0,1	2,1	0,1

Sorunun ekonomik-matematiksel bir modelini yapalım. x j ile gösterelim - j yöntemlerinden birine göre kesilmesi gereken kaynak malzeme (çelik levhalar) miktarı. Görevdeki kısıtlamalar, boşlukların planlanan çıktısına karşılık gelmelidir Çeşitli türler. Amaç fonksiyonu, kesim sırasında minimum israfı bulmaktır.

F=1,4 x 1 +0,1 x 2 +2,1 x 3 +0,1 x 4 →(dk..)
Tüm j kesme yöntemleri için i-th tipi boşlukların çıktısına ilişkin kısıtlamalar:

Örnek #3. Kesmek (kesmek, işlemek) için bir numunenin malzemesi bir birim miktarında sağlanır. Ondan b 1 , b 2 ,…,b l (tamlık koşulu) sayılarıyla orantılı miktarlarda l farklı bileşen yapılması gerekir. Her malzeme parçası kesilebilir n Farklı yollar, ve i-inci yöntemin kullanımı (i = 1, 2,…,n) k-inci öğenin (k = 1, 2,…,l) ik birimlerini verir. Maksimum takım sayısını sağlayan bir kesim planı bulmak gerekir.
Sorunun ekonomik-matematiksel bir modelini yapalım.
x i, i-inci yöntemle kesilen malzeme birimi sayısını ve x üretilen ürün setlerinin sayısını göstersin. Daha sonra amaç fonksiyonu bulmaya indirgenir.

F=x→(maks),
kısıtlamalarla: birimlerinin toplamına eşit toplam malzeme miktarına göre, çeşitli şekillerde kesilir; değişkenlerin tamlık ve olumsuzluk olmaması şartına göre.

Örnek #4. Şirketin, sırasıyla p 1 , p 2 , p 3 miktarında l 1 , l 2 , l 3 m uzunluğunda parçalar halinde kesilmesi gereken L m uzunluğunda kütükleri vardır.
Boşlukların çıkış planına bağlı olarak, minimum atık sağlayan malzemeyi kesmek için optimal bir plan hazırlamak gerekir. İlk veriler tabloda verilmiştir.

Bir görev	Uzunluk	Boşluk boyutları, m			Boşluk sayısı, adet.
		1	ben 2	l3	p1	p2	p 3
68	6,5	2,1	2,3	1,4	600	720	900

Çözüm: Önce problemimizin matematiksel bir modelini yapalım. Olası seçenekler her biri için kesme ve atık bir tablo şeklinde yazılacaktır.

iş parçası uzunluğu	Kesme seçenekleri							boşluk sayısı
	1	2	3	4	5	6	7
2,1	3	2	2	1	1	0	0	600
2,3	0	1	0	1	0	2	1	720
1,4	0	0	1	1	3	1	3	900
kalan, m	0,2	0	0,9	0,7	0,2	0,5	0

x i ile i-inci seçeneğe göre kesilen kütük sayısını belirtin (i=1..7). Daha sonra toplam artık atık doğrusal bir fonksiyon olarak yazılacaktır:
Z = 0.2x1 + 0x2 + 0.9x3 + 0.7x4 + 0.2x5 + 0.5x6 + 0x7
Aynı zamanda, boşluk sayısı açısından planın yerine getirilmesi için koşullar yerine getirilmelidir, yani.
3x1 + 2x2 + 2x3 + x4 + x5 = 600
x2 + x4 + 2x6 + x7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900

Bu nedenle, belirtilen problemi çözmek için minZ'yi kısıtlamalar altında bulmak gerekir. minZ = -max(-Z(x)) olduğundan, fonksiyon minimizasyon problemi yerine fonksiyon maksimizasyon problemini çözeceğiz:
Z = -(0.2x 1 + 0x 2 + 0.9x 3 + 0.7x 4 + 0.2x 5 + 0.5x 6 + 0x 7)

Örnek numarası 5. Bir ürünü dikmek için kumaştan 6 parça kesmeniz gerekir. Giysi fabrikasında kumaşı kesmek için iki seçenek geliştirildi. Tablo (aşağıda yer almaktadır) 10 m 2 kumaş, tamlık, yani. bir ürünü dikmek için gereken belirli bir türdeki parça sayısı. Terzilik için aylık kumaş temini bu türden 405 m2'dir. Önümüzdeki akşam 90 parça dikilmesi planlanıyor.
Gelecek ay minimum miktarda atıkla terzilik planını tamamlamanıza izin veren problemin matematiksel bir modelini oluşturun.

Tablo - 10m 2 kumaş parçalarını kesmek için seçeneklerin özellikleri

Kesme seçeneği	Parça sayısı, parça/kesim						Atık, m 2 / kesim
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Tamlık, parça/ürün	1	2	2	2	2	2

Problemin matematiksel ifadesi

Görev Değişkenleri
Bu problemde gerekli değerler açıkça belirtilmemiş ancak 90 adet ürün dikmek için aylık bir planın tamamlanması gerektiği söylenmektedir. Ayda 90 ürünü dikmek için kesinlikle kesmek gerekir belli bir miktar detaylar. Kesimi 10 m 2 kumaş parçalarından iki farklı şekilde yapılır, bu sayede farklı numara detaylar. İlk yöntemle ne kadar kumaşın ve ikinci yöntemle ne kadar kumaşın kesileceği önceden bilinmediğinden, istenen değerler olarak, yöntemlerin her biri ile 10 m2'lik kumaş segmentlerinin sayısını ayarlayabilirsiniz:
x 1 - Ay boyunca ilk yöntemle kesilen 10m 2 kumaş parçası sayısı, [kesim / ay];
x 2 - ay boyunca ilk yöntemle kesilen kumaş parçalarının sayısı, her biri 10m 2, [kesim / ay];

amaç fonksiyonu
Problemi çözmenin amacı, planı minimum miktarda israfla gerçekleştirmektir. Ürün sayısı kesin olarak planlandığından (90 adet/ay), bu parametre CF'yi tanımlamaz, ancak bir kısıtlamayı ifade eder, başarısız olması sorunun çözülmediği anlamına gelir. Ve planın uygulanmasının etkinliği için kriter, en aza indirilmesi gereken "atık miktarı" parametresidir. 1. seçeneğe göre tek parça (10m 2) kumaş kesildiğinde, 0,5m 2 atık elde edildiğinden ve 2. seçeneğe göre - 0,35m 2 (bkz. tablo 1), o zaman Toplam keserken atık (CF) formuna sahiptir
L(x) = 0,5x1 + 0,35x2 = dk,

Kısıtlamalar
Çeşitli şekillerde kumaş kesimlerinin sayısı aşağıdaki koşullarla sınırlıdır:

• Ürünleri dikmek için bir plan yerine getirilmelidir, başka bir deyişle, toplam kesilen parça sayısı, ayda 90 ürün dikilebilecek şekilde olmalıdır, yani: 1. tipten en az 90 ve diğer tiplerden parçalar olmalıdır. - en az 180 (tablodaki eksiksizliğe bakın).
• Kumaş tüketimi, depodaki aylık stoğu aşmamalı;
• Kesilen kumaş parçası sayısı negatif olamaz.

Palto dikme planındaki kısıtlama, aşağıdaki anlamlı giriş biçimine sahiptir.
(Tüm seçenekler için 1 numaralı kesim toplam parça sayısı) ≥ (90 adet);
(Tüm seçenekler için toplam 2 numaralı kesim) ≥ (180 adet);
(Tüm seçenekler için kesilen toplam parça sayısı 6 numara) ≥ (180 adet);

Matematiksel olarak, bu kısıtlamalar şu şekilde yazılır: :
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;

Doku tüketim limiti aşağıdaki kayıt biçimlerine sahiptir:
anlamlı
(aylık toplam kumaş kesimi)≤ (405m2)
matematiksel
x 1 + x 2 ≤405/10

Kesilen segment sayısının negatif olmaması şeklinde verilir.
x 1 ≥ 0, x 2 ≥ 0

Böylece, problemin matematiksel modeli şu şekildedir:
L(x) \u003d 0,5x 1 + 0,35x 2 \u003d dak [m 2 atık / ay],
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;
x 1 + x 2 ≤40.5
x 1 ≥ 0, x 2 ≥ 0

Örnek numarası 6. Isıtma şebekesi için her biri 1070 cm olan 69 boru bulunmaktadır. 130, 150 ve 310 cm'lik borular halinde kesilmeleri gerekir, gelen boruları kesmek için, atığın minimum olacağı böyle bir seçenek bulun.

Aşama 1. Boruların en uygun şekilde kesilmesi için seçenekleri belirliyoruz.

Kesme seçenekleri	1	2	3	4	5	6	7	8	9	10	11	12	13
310	3	2	2	2	2	1	1	1	1	0	0	0	0
150	0	3	2	1	0	3	2	1	0	3	2	1	0
130	1	0	1	2	3	2	3	4	5	4	5	7	8
Kalıntılar	10	0	20	40	60	50	70	90	110	100	120	10	30

2. aşama.
Sorunun ekonomik-matematiksel bir modelini yapalım. x j ile gösterelim - j yollarından birine göre kesilmesi gereken boru sayısı. Amaç fonksiyonu, kesim sırasında minimum israfı bulmaktır:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min

x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69

Cevap: sadece ikinci kesim seçeneği kullanılmalıdır (sıfır atık)

Program, profillerin ve diğer uzun malzemelerin (çubuk, kütük, boru, pencere pervazına) kesilmesini optimize etmek için tasarlanmıştır.
"Yoğun istifleme" algoritması kullanılır, yani alınan ürün, üzerine yerleştirildiği iş parçasının en kısa kalan kısmına yerleştirilir. Herhangi bir yere sığmıyorsa yeni bir boşluk alınır. Optimizasyonun görevi, daha az boşluğun kullanılacağı ve iş düzeltmelerinin uzunluğunun daha uzun olacağı bir ürün dizisi bulmaktır. İlk ölçümde ürünler kamçılara yerleştirilir. rastgele sıra. Bir "ilk nüfus" var. Çözme sürecinde popülasyon mutasyona uğrar ve çoğalır, başarısız örnekler ölür ve en iyileri gelişmeye devam eder. Her şey, hayvan ve bitki dünyasında olduğu gibi + yapay seçilim.

Sitede canlı demo

Aşağıdaki örnek statik bir resim değil, çalışan bir web uygulamasıdır.
butonu ile profil kesimine başlayabilirsiniz. Başlama, ürün ve iş parçası ölçülerinizi belirleyin, optimizasyon ayarlarını değiştirin ve çözümü değerlendirin.
Tabii ki, tarayıcıdaki optimize edici yerel programdan daha yavaştır, ancak bilgisayarınıza herhangi bir şey indirip yüklemenize gerek kalmadan ücretsiz olarak uygulanabilir sonuçlar elde etmenizi sağlar.

Avantajlar

• Windowsoft:kesme, kesme haritaları sağlar Yüksek kalite. Çok sayıda uygulama, 30 konturdan (~120 kesim) partileri optimize ederken gerçek kesme faktörünün %1'den fazla olmadığını doğrular
• İlk verileri okumak ve kesme sonuçlarını yazmak için program şunları kullanır: basit biçimler metin dosyaları Müşteri tarafından uygulanan muhasebe sistemleriyle entegrasyonu basitleştiren
• Gerekirse, url, web soketi veya javascript nesneleri aracılığıyla parametreleri aktararak bir tarayıcı veya Node.js'de Linux veya OS X altında yuvalama yapılabilir.

Doğrusal optimize edici algoritmalar

Windowsoft'ta: kullanılan kesme genetik Algoritma. Özü şudur:
Ürünlerin her bir kamçı dağıtımına bir çözüm diyelim. Çözümlerin kalitesini karşılaştırmamıza izin veren bir amaç fonksiyonu tanımlayalım. birkaç tane oluşturalım keyfi kararlar Onlara bir nesil diyelim. Gelecek nesli elde etmek için kuralları tanımlayalım. En iyi amaç işlevine sahip örnekler başarılı çoğu onların "gen havuzundan", bu bizim "yapay seçilimimiz"dir. Artık sistemi kendi haline bırakmak, mutasyona uğramasına ve kesme sonuçlarını optimize etmesine izin vermek kaldı.
Geliştirme sürecinde, "instance"larımızın rastgele olduğu ve birbirine bağlı olmadığı durumlarda "Monte Carlo" yöntemi ve "Karınca algoritmaları" (ACO-ant koloni optimizasyonu) test edilmiştir. Tüm yöntemlerin oldukça verimli olduğu kanıtlandı, ancak genetik algoritmanın biraz daha verimli olduğu ortaya çıktı.

Teslim seçenekleri

Oknosoft kesme modülü için iki teslimat seçeneği vardır: kesme - bir parçası olarak tam çözümÖzel üretimlerin yönetimi ve ayrı bir formda çalıştırılabilir dosya. İlk senaryoda kesim programı ile etkileşim kullanıcıdan tamamen gizlenmiştir. Operatör ile çalışır standart belgeler 1C:

• Müşteri siparişlerine göre üretim planı oluşturulur.
• Bir ürün listesi ve gerekli malzemeler ile plan - vardiya görevleri temelinde
• Üretim emri içinde yerleştirme optimize edildi
• Optimizasyon sürecinde, program, devam etmekte olan işten iş detayını çıkarır ve yeni oluşturulan iş detayını hücresel depoya yerleştirir.
• Bir vardiya işi, manuel üretim için kesim formları yazdırabilir veya CNC makineleri için dosyalar oluşturabilir
• Ayrıca, bir vardiyadan kesilen ürünler için etiketler ve arabalar ve piramitler için yerleşim şemaları yazdırılır.
• Üretim görevleri temelinde, gereksinimler oluşturulur - ihtiyaçlar ve standart ambalaj dikkate alınarak malzemelerin atölyeye aktarılması için faturalar

Yazılım Arayüzü (Linear Nesting API)

Girdi veri dosyası setup.ini, yürütülebilir dosyanın bulunduğu klasöre yerleştirilir.
Çıktı veri dosyaları - result.txt, resultproduct.txt ve resultstick.txt - aynı klasörde oluşturulur.
Oknosoft:cuting demo verilerini sayfanın sonundaki bağlantıdan indirebilirsiniz. Dosyalar aşağıdaki etiketleri kullanır:

• Outputvariant - dosyanın çıktı dosyasının yapısı. Olası değerler: sekme, oknosoft, varsayılan oknosoft
  • "Oknosoft" seçeneğinde, sonuçürün.txt ve resultstick.txt dosyaları, ürünlerin boşluklara yerleştirilmesi ve sonuçta ortaya çıkan trim hakkında bilgilerle oluşturulur.
  • "Sekme" varyantı, "sekme" karakterleriyle ayrılmış beş değer görüntüler: ürün uzunluğu, kamçı numarası, kamçı uzunluğu, kesim numarası ve iş parçasının geri kalanı
• Algoritma - kullanılan algoritma. Olası değerler: rastgele, muhafazakar, genetik, varsayılan genetik
  • Rastgele - seçeneklerin rastgele seçimi
  • Muhafazakar - bir sonraki yinelemenin örnekleri aynı "üst öğeden" gelir
  • Genetik - iki ebeveynden
• Varyasyon - değişkenlik, "muhafazakar" ve "genetik" algoritmaların parametresi. Ne kadar yüksek olursa, ebeveynlere "benzer" olan yavrular o kadar az olur. Varsayılan 1'dir.
• Nesiller - algoritma yineleme sayısı, varsayılan 40000
• Kişiler - "nüfus"taki "örneklerin" sayısı, bir yinelemede kullanılan çözümlerin sayısı. "Rastgele" algoritma, bir örnekle (çözüm) nesiller * yinelemeler yapar
• Bıçak Genişliği - testere genişliği
• StickLength - yeni çubuğun uzunluğu
• Ürünler - ürün uzunluğu
• Hurda - yuvada kullanılan hurdanın uzunluğu
• Yanlış nipmin- Minimum uzunluk"kötü" desen
• Yanlışnipmax- maksimum uzunluk"kötü" budama
  Optimizasyon sonuçlarında, Wrongsnipmin ve Wrongsnipmax arasında uzunluklara sahip kırpmalar olmayacak

çift ​​kesim

Çift testereyi destekleyen makineler için veri hazırlarken kullanılır. Bu durumda, makineye aynı anda iki profil kamçı yerleştirilir ve bir kesme döngüsünde iki özdeş yarı mamül ürün oluşturulur.

Çift kesme görevi, verileri optimizasyon programına aktarmadan önce gruplandırarak ve ardından kesme sonuçlarını ürün ve iş parçası çiftleri halinde çoğaltarak çözülür. UPZP'nin içine yerleştirme yaparken, sistem terminolojinin özelliklerini dikkate alır ve kesme makinelerinin özelliklerine bağlı olarak tekli veya çiftli kesme kullanır.

Çok sayıda ürünün kesilmesi

Bir yandan, yüksek kalitede bir optimizasyon elde etmek için, programın girişinde, optimize edicinin "ne sıralayacağını" bilmesi için, farklı uzunluklarda önemli sayıda ürünün alınması gerekir. Öte yandan, çok büyük partilerle, numaralandırmanın sabit sayıda yinelemesinde maksimumu bulma olasılığı azalır. Deneyler, 60-120 boşluktan oluşan bir partinin optimal olduğunu göstermiştir (ki bu, çiftler halinde kesim yaparken 30-60 üründen oluşan bir üretim döngüsüne karşılık gelir). 120'den fazla boşluğu optimize etmeniz gerekiyorsa, en iyi sonuçlar problem N parçaya bölünerek ve her parça için ardışık optimizasyonlar yapılarak elde edilebilir. Üretim görevleri partilerinin oluşumunu işlemek, ürünleri profil tipine göre gruplayabilir ve vardiya görevlerinde maksimum dağılıma sahip ürünleri seçebilir, operatörü üretim belgelerini derleme rutin işinden kurtarır.

Kesim örneklerini ve belgeleri indirin

• Demo tek ve çift kesim kartları: 60.01 Kesme yaprağı
• Belgeler ve örnek dosyalar:

Kes, Onayla, Görüntüle, Etiketler, Yardım, Kapat

Seçenekler

• "Malzeme varlık türleri" filtresi, seçilen malzeme varlık türü veya alt türüne dahil edilen makalelerin listesi, "Profiller" sekmesi, "Dolgular" sekmesi
• "Malzeme varlıklarının türleri" filtresi, kesim için bir dizi kalıplanmış ve levha bileşeninin aktarılması gerekiyorsa, malzeme varlıklarının belirli türlerini ve alt türlerini arama kolaylığı için tasarlanmıştır.
  Makalelerin listesi aşağıdaki sütunları içeren bir tabloda sunulmaktadır: "Makale", "Ad" ve "Doku", "Dahili", "Dış". Makale listesi, seçilen projelerden ve bileşenlerin herhangi bir türü veya alt türü ile ilgili tüm makaleleri içerir.
  Kesme parametreleri aşağıdakiler tarafından düzenlenir:
• Kamçının varsayılan uzunluğunun "Maddi Öğeler" kataloğundan alındığı veya manuel olarak değiştirilebildiği "Profiller". Değiştirilen uzunluk, tüm makale listesine uygulanacaktır.
  "Yöntem" kaydırıcısı, kesim için bir öncelik seçmenize olanak tanır: Minimum atık elde etmek için "Minimum malzeme" (eşleştirilmiş kesimlerin analizi) ve sonuçta elde edilen trimden en büyük kalıntıları elde etmek için "Kalıntıların tahmini". İkinci yöntem daha fazla malzeme tüketir, ancak ortaya çıkan süsleme daha fazla kullanım için daha uygundur. Doğrudan kesim tablosunda boyut işaretlemesi mümkündür, yani. "kesme sayfada" veya ayrı bir "tabloda", yuvalama haritasına yalnızca ortaya çıkan yuvanın sayfa kodları girilecektir. İkinci yöntem, küçük boyutlu kesimler için gerekli hale gelir. Derin Analiz yöntemi, matematiksel aparat kesme süresini artıran daha karmaşık bir hesaplama algoritması ile, ancak bazı durumlarda iş parçalarını diğer yöntemlerden daha optimum şekilde ayrıştırabilir.
  "Dokusuz" bayrağının ayarlanması, dokuları hesaba katmadan iş artıklarının kullanılmasına izin verir (profillerin daha fazla yeniden boyanması için geçerlidir).
  "Uzun uzunlukları dahil et" bayrağının ayarlanması, raporda boşluklar görüntülemenize olanak tanır uzunluğa eşit kesme gerektirmeyen bütün kamçılar - uzun boyları satarken kullanılır.
  "Kesim çizimlerini göster" bayrağını ayarlamak, raporda görüntülemenizi sağlar Grafik sunum profil kesme kalıpları.
  "Yalnızca iş artıklarının sayısı" bayrağının ayarlanması - bir sayının yalnızca iş artıklarına atanmasını sağlar.

Filtre

"Bütün kütükler stokta" - kesim için tüm kütüklerin alınacağı stoğu belirlemenizi sağlar.

"Raporda çıktı" - kesme haritasının ilgili sütununda donatı sayısını (ana profilin sayısına karşılık gelir) veya konteynerin eşyasını (bu donatının kurulu olduğu) görüntüleyin.

Düğmeler

• "Nest", makaleler listesinde seçilen makalelerin optimizasyonunu başlatır (seçim fare işaretçisi ile yapılır. çift ​​tıklama tüm konumları seçer), kesimden sonra ise formun alt kısmında yuvalama haritasını görüntüleyebilirsiniz.
• "Onayla", spesifikasyonları optimize edilmiş üretime projelerin gönderilmesini iptal etmeyi yasaklar ve ortaya çıkan trimi trim deposuna yerleştirir. Üretime gönderilmeyen projeler için yerleştirme onayı mümkün değildir.
• "Görüntüle", ortaya çıkan kesme haritasını görüntülemenize, uygulamalardan birinde açmanıza olanak tanır Microsoft Office, bir dosyaya kaydedin veya yazdırın. Grup profili ve dolgu optimizasyonlarında rapor tablolarına eleman sıra numaralı sütunlar eklendi. Toplu dolgu optimizasyon raporuna eklendi grafik atama makalenin ana dokusunun yönü
• "Etiketler" - iş bakiyeleri için barkod etiketleri raporu oluşturma.

Profillerin grup kesimine ilişkin raporun tablosunda, her ürünün eleman numarasına göre 'Kol No.' sütunu tanıtılır (her birine karşılık gelen takviyeli kesme profillerin sıralanması - içindeki eleman numarasına göre). ürün)

Profillerin grup kesimine ilişkin önceden tanımlanmış rapor, kanat profilleri için bir tutamak yüksekliği sütunu ile genişletildi (kesildikten hemen sonra yaprak profilinde tutamağın altında delmek için işaretleme için - iş parçasının kesilmesi)

Kesme Hattı - Doğrusal kesme programı

Sürüm: 2.49
Geliştirici: Shibaev Yury Anatolyevich Ukrayna, Cherkasy
Geliştirici sitesi: http://www.cuttinghome.com/
Bit derinliği: 32bit
Windows 7 ile uyumlu: evet
Arayüz dili: İngilizce + Rusça
Tabletka: Kürlenmiş
Sistem Gereksinimleri: Minimum
Açıklama: KESME programı, malzemenin en uygun şekilde kesilmesi için tasarlanmıştır. doğrusal ayrıntılar. Program ağaç işleme, mobilya üretimi, metal kesme, cam kesme vb. alanlarda kullanılabilir. Programlar, minimum atıkla hızlı bir şekilde kesim yapmanızı sağlayan benzersiz, yüksek hızlı bir algoritmaya dayanmaktadır.
Programların algoritmik kısmını geliştirirken ana kriter olarak atık minimizasyonu ilkesi seçilmiş, arayüz kısmını geliştirirken yazar programları günlük kullanımda basit ve kullanışlı hale getirmeye çalışmıştır.

Doğrusal boşlukların parçalara en uygun şekilde kesilmesi programı

Uygulanan program aşağıdaki özellikler ve olasılıklar:
. egzersiz yapmak Rasgele sayı boşlukları kes ve parçaları kes
. örneğin ad ve renk gibi belirli özelliklere göre boşlukları ve bölümleri ayarlama
. malzeme türünü dikkate alarak hesaplama (malzeme adı, renk)
. kesici takımın genişliğini ayarlama
. segmentlerin ve artıkların toplam uzunluklarının hesaplanması
. egzersiz yapmak farklı modlar kesme
. geçerli oturumun önceki yuvalarını geri yükleme
. belirtilen iş parçalarını ve kesimleri spesifikasyon olarak kaydetme
. yeni bir analiz seçeneğine kaydedilmiş bir malzeme listesi ekleme
. yuvayı daha sonra kurtarma olasılığı olan bir dosyaya kaydetme
. kesim sonuçlarının hem grafik hem de tablo biçiminde görüntülenmesi ve yazdırılması
. komple sistem referans bilgisi.