0 00
 |
Kesirli sırt çantası problemi (fractional knapsack problem) nedir? |
Kesirli sırt çantası problemi, nesnelerin kısmi olarak seçilebildiği durumda nesnelerden çantanın kapasitesini aşmayacak en değerli seçim nasıl yapılmalıdır, sorusuna cevap arayan bir optimizasyon yaklaşımdır.
Sırt çantası problemi
Sırt çantası problemi, kaynak optimizasyonu yani kaynakların en verimli şekilde tahsis edilmesi sorunudur.
Kesirli sırt çantası problemi
Kesirli sırt çantası problemi (fractional knapsack problem), 0/1 sırt çantası probleminden farklı olarak tercih edilecek olan kaynakların bölünebildiği durumları ifade eder. Örneğin bir fabrikaya bir iş makinesinin ancak alınması ya da alınmaması yönünde karar verilirken, fabrikaya 10 ton ya da 15 ton hammadde satın alınması için karar verilebilir. Benzer biçimde bir çantaya ancak bir el feneri koyulur ya da koyulmaz. Fakat çanya bir ekmek ya da yarım ekmek koyulabilir.
Tanım
Bir çantayı kapasitesini aşmayacak şekilde en değerli olan nesnelerle doldurmak için parçalara ayrılabilir bu nesnelerden hangileri çantaya koyulmalıdır. Nesnelerin parçalabilir olması, her bir nesnenin kısmi olarak seçilebildiğini ifade eder.
Problem
Kapasitesi 15 kg olan bir çantaya malzemeler yerleştirilecektir. Aşağıda verilen tabloda malzemelerin ağırlıkları ve değerleri verilmiştir. Bu durumda çantanın kapasitesini aşmayacak fakat çantayı en değerli kılacak seçim nasıl yapılmalıdır?
Çözüm
Problemin çözümünün en etkin yöntemi açgözlü yaklaşımı kullanmaktır. Bu yöntem her zaman seçimin optimal (en iyi/uygun seçim) olarak yapılmasını sağlar.
Malzemeler birim değerlerine göre sıralandığında birim ağırlığı en değerli malzeme b'dir. Çantaya alınabildiği kadar çok b malzemesi almak en akıllı stratejidir. Kapasiteden daha az b varsa diğer malzemelerden en değerliden başlamak üzere seçim yapılmaya devam edilir. En değersiz malzemelerden mümkün olduğunca az seçilmedir.
b ve c malzemeleri seçildikten sonra e malzemesi de eklendiğinde toplam ağırlık 16 kg olur ve 15 kg olan kapasite aşılmış olur. Bu durumda e'nin tamamı değil, kapasiteyi aşmayacak miktarı yani 7 kg alınır.
Fayda, birim değer ile seçilen miktarın çarpımından elde edilir. Yukarıdaki tablodaki gösterildiği gibi çantaya 1 kg b, 7 kg c ve 7 kg e malzemesi seçildiğinde toplam fayda 30 tl olmaktadır.
Sırt çantası problemi, kaynak optimizasyonu yani kaynakların en verimli şekilde tahsis edilmesi sorunudur.
Kesirli sırt çantası problemi
Kesirli sırt çantası problemi (fractional knapsack problem), 0/1 sırt çantası probleminden farklı olarak tercih edilecek olan kaynakların bölünebildiği durumları ifade eder. Örneğin bir fabrikaya bir iş makinesinin ancak alınması ya da alınmaması yönünde karar verilirken, fabrikaya 10 ton ya da 15 ton hammadde satın alınması için karar verilebilir. Benzer biçimde bir çantaya ancak bir el feneri koyulur ya da koyulmaz. Fakat çanya bir ekmek ya da yarım ekmek koyulabilir.
Tanım
Bir çantayı kapasitesini aşmayacak şekilde en değerli olan nesnelerle doldurmak için parçalara ayrılabilir bu nesnelerden hangileri çantaya koyulmalıdır. Nesnelerin parçalabilir olması, her bir nesnenin kısmi olarak seçilebildiğini ifade eder.
Problem
Kapasitesi 15 kg olan bir çantaya malzemeler yerleştirilecektir. Aşağıda verilen tabloda malzemelerin ağırlıkları ve değerleri verilmiştir. Bu durumda çantanın kapasitesini aşmayacak fakat çantayı en değerli kılacak seçim nasıl yapılmalıdır?
| malzeme | ağırlık (kg) | değer (tl) |
| a | 10 | 5 |
| b | 1 | 9 |
| c | 7 | 14 |
| d | 2 | 1 |
| e | 8 | 8 |
Çözüm
Problemin çözümünün en etkin yöntemi açgözlü yaklaşımı kullanmaktır. Bu yöntem her zaman seçimin optimal (en iyi/uygun seçim) olarak yapılmasını sağlar.
- Her objenin birim ağırlığının değeri hesaplanır. Buna değerlik yoğunluğu denilebilir.
- Birim ağırlıkların değeri büyükten küçüğe doğru sıralanır.
- En değerli olandan başlayarak kapasiteyi aşana kadar devam edilir.
- Kapasitenin aşıldığı noktada, en son koyulan objeden ancak yeteri kadar alınır. Burası kapasitenin aşılmadığı ve objeden kesirli/kısmi miktarda alındığı noktadır.
| malzeme | ağırlık (kg) | değer (tl) | birim değer (tl/kg) |
| a | 10 | 5 | 0.5 |
| b | 1 | 9 | 9 |
| c | 7 | 14 | 2 |
| d | 4 | 1 | 0.25 |
| e | 8 | 8 | 1 |
Malzemeler birim değerlerine göre sıralandığında birim ağırlığı en değerli malzeme b'dir. Çantaya alınabildiği kadar çok b malzemesi almak en akıllı stratejidir. Kapasiteden daha az b varsa diğer malzemelerden en değerliden başlamak üzere seçim yapılmaya devam edilir. En değersiz malzemelerden mümkün olduğunca az seçilmedir.
| mazleme | birim değer (tl/kg) | ağırlık (kg) | toplam ağırlık (kg) |
| b | 9 | 1 | 1 |
| c | 2 | 7 | 8 |
| e | 1 | 8 | 16 |
| a | 0.5 | 10 | |
| d | 0.25 | 4 |
b ve c malzemeleri seçildikten sonra e malzemesi de eklendiğinde toplam ağırlık 16 kg olur ve 15 kg olan kapasite aşılmış olur. Bu durumda e'nin tamamı değil, kapasiteyi aşmayacak miktarı yani 7 kg alınır.
| mazleme | birim değer (tl/kg) | seçilen miktar (kg) | fayda (tl) |
| b | 9 | 1 | 9 |
| c | 2 | 7 | 14 |
| e | 1 | 7 | 7 |
| a | 0.5 | 0 | |
| d | 0.25 | 0 | |
| toplam | 15 kg | 30 tl | |
Fayda, birim değer ile seçilen miktarın çarpımından elde edilir. Yukarıdaki tablodaki gösterildiği gibi çantaya 1 kg b, 7 kg c ve 7 kg e malzemesi seçildiğinde toplam fayda 30 tl olmaktadır.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)
Henüz yorum yapılmamış.
