premium üyelik: Sırt çantası problemi

Sırt çantası problemi (İngilizce: "knapsack problem") bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.

"Sırt çantası problemi"nin tanımlanması için şu notasyon kullanılmaktadır: İsimleri 1 ile n arasında sayı ile ifade edilen n değişik madde bulunur. Her bir madde i için değerin v_i ve ağırlığın w_i olduğu bilinmektedir. Genel olarak her bir değer ve her bir ağırlık negatif olamazlar. Çanta içinde taşınabilecek tüm maddelerin toplam ağırlığının en çok W olup, bunun bir üst sınır olup aşalamıyacağı bilinir.
Bu problem tipi değişik sınırlama koşullarına göre değişik problem tipi şekilini alabilir. Bunlardan bazıları şöyle tanımlanabilir:

"0-1 sırt çantası problemi": "Sirt çantası problem" tipleri arasında en iyi bilinen problem "0-1 sırt çantası problemi"dir. Bu tip problemde mevcut n maddeden her biri ya 1 birim olarak çantaya konulur yahut çantaya konulmaz, yani 0 birim çantaya koyulur. Her bir madde tek birim olarak çantaya konulur ya koyulmaz. Çantaya konulup konulmama, sadece 1 ve 0 değerleri alan "çantada mevcut olup olmama" adı verilebilen iki kategorili değer alan bir karar değişkeni olur. Böylece karar değiskeni olan x_i ya 0 ya da 1 değeri alan iki kategorili "tamsayı değişkeni" olur. Matematik formulasyon şöyle verilir:

maksimumu bulunacak objektif fonksiyon: $\qquad \sum_{i=1}^n v_ix_i$

sınırlamalar: $\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1\}$

"Sınırlı sırt çantası problemi": Bu tür problemde sırt çantası içine her maddeden birden fazla yerleştirilebilmek imkânı olduğu kabul edilir. Ama her bir madde için mevcut madde adedi sınırlıdır; i maddesi için mevcut sayı olan $x_i$ , 0 ile tam sayı olan $c_i$ arasında olabilir. Bu tür "sınırlı sırt çantası problemi"nin matematik formülasyonu şöyledir: .

maksimum bulunacak objektif fonksiyon: $\qquad \sum_{i=1}^n v_ix_i$

sınırlamalar: $\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots,c_i\}$

"Sınırsız sırt çantası problemi": Bu tür problemde her madde sıfırdan sınırsız sayıya kadar sırt çantası içine yerleştirilebilir. i maddesi için sırt çantasına yerleştirilen sayı, yani $x_i$ , 0 ile tam sayı olan +∞ arasında olabilir.

İlgi çeken başka iki özel sırt-çantası problemi şu özellikleri ile tanımlanır:
- Bu bir karar verme problemidir.
- Bu problem için karar değişkeni sadece 0-1 değerleri alabilir;
- Her bir madde için ağırlık o maddenin değerine eşittir; yani $w_i=v_i$ .

Bu şekildeki özel problem şu değişik şekilde de ifade edilebilir: bir negatif olmayan sayılar seti verilmiş ise, bunun herhangi bir altsetinin toplamı W toplam ağırlık/değer sınırına eşit olabilir mi?
Buna benzer diğer bir özel problem, eğer her bir madde için negatif olan ağırlık mümkünse (yani −∞ < w_i < +∞ ise) ve toplam ağırlık sınırı en çok W sıfıra eşit ise (yani W=0 olursa) ortaya çıkar. Problem şu olur: bir tamsayılar veri seti verilirse, bunun herhangi bir alt-seti tam olarak 0a eşit olabilir mi? Buna "alt-set toplamı problemi" adı verilir. Kriptografi alanında sırt-çantası problemi" ismi sadece bu çok özel "alt-set toplam∞ problemi" olarak görülür.
Eğer tek bir değil ama birden fazla sırt-çantası yüklemek mümkün ise, bu yeni tip probleme "kutu paketleme" problemi adı verilir.

premium üyelik

3 Haziran 2012 Pazar

Sırt çantası problemi

0 Yorum:

Yorum Gönder

Hakkımda

Önceki Kayıtlar