Bir kapasite (bütçe, iş gücü, kapasite saati) kısıtı altında N aday öğeden alt-küme seçimi: her öğenin değeri ve ağırlığı verili; toplam ağırlık kapasiteyi aşmadan toplam değer maksimum. Akademik literatürde Knapsack Problem; ayrık seçim problemlerinin atası.
Kısaca
Tanıdık geliyor mu?
- Yıllık yatırım komitesinde 50-200 aday proje, toplam bütçe 50-500M TRY arası sabit — proje sıralaması sezgisel ve siyasi; 'NPV / yatırım oranı' tablosu hazırlanır ama matematik optimum garanti edilmez.
- Aday projelerin her biri için NPV tahmini, gerekli yatırım, gerekli iş-gücü saati, gerekli kapasite saati (üç boyutlu kısıt) verisi hazır — ama bunların hepsini birden hesaba katan bir seçim modeli kurmadık.
- Bütçe planlamasında 'sırala üstten seç' kullanılıyor — ama bütçenin son %5-10'una sığan küçük ama yüksek NPV/birim oranlı projeler genelde yer bulamıyor.
- Dijital pazarlama kampanya seçimi: 30-80 kampanya teklifi, sabit aylık veya çeyreklik bütçe; hangi alt-küme seçilsin ki erişim/dönüşüm maksimum olsun?
- Aday projeler arasında bağımlılık var (Proje A seçilirse Proje B'nin maliyeti düşer; Proje C ile Proje D karşılıklı dışlayıcı) — bunu klasik knapsack modeli yakalamıyor, ek kısıt eklemek gerekiyor.
- Lojistik tarafında: kapasiteli kargo uçağı veya konteyner yüklemesi — her paketin değeri ve ağırlığı var, kapasiteyi aşmadan toplam değer maksimum.
- Hisse senedi fonu yöneticisi: küçük-cap evren 200-500 hisse, sabit fon büyüklüğü, her hisse için tahmini getiri ve minimum işlem büyüklüğü; hangi alt-küme seçilsin?
- Tedarik anlaşması: 100+ tedarikçi adayı, sabit yıllık satınalma bütçesi; her tedarikçinin minimum ve maksimum sipariş tutarı var; hangi alt-küme seçilsin ki toplam değer maksimum?
Niye önemli?
Nasıl çözülür?
Teknik derinlik
Nasıl çözülür?
Teknik derinlikTek cümlede: Adayları birim-ağırlık başına değer oranına göre sırala (greedy başlangıç); kesin sonuç için dinamik programlama (kapasite 10K altı) ya da MIP (özellikle çok-boyutlu kısıt veya bağımlılık varsa) çalıştır — dakikalar içinde en iyi alt-küme çıkar.
Bu problem yöneylem araştırması (matematik ve bilgisayar kullanarak işletme kararı çözen disiplin) ve bilgisayar bilimleri literatüründe Knapsack Problem (Sırt Çantası Problemi) olarak çalışılır — N aday öğe, her birinin değeri (vᵢ) ve ağırlığı (wᵢ); kapasite W; hangi alt-küme seçilsin ki Σwᵢ ≤ W ve Σvᵢ maksimum? 1950’lerden bu yana çalışılan klasik bir problemdir; dinamik programlama, branch-and-bound ve modern MIP çözücüleriyle endüstri-standardı çözümleri vardır. Çözüm üç aşamalı:
1. Modelleme — varyant seçimi ve veri girdileri. Problem ailesi geniş; uygulama hangi varyantı çağırıyor önce belirlenir:
- 0/1 Knapsack (Binary Knapsack): Her öğe ya seçilir ya seçilmez; aynı öğenin birden fazlası yok. Klasik yatırım projesi seçimi bu sınıftadır. Karar değişkeni xᵢ ∈ {0, 1}.
- Bounded Knapsack: Her öğenin sınırlı sayıda kopyası alınabilir (xᵢ ∈ {0, 1, …, cᵢ}). Tedarik sözleşmelerinde “her tedarikçiden 1-5 lot al” gibi.
- Unbounded Knapsack: Her öğeden istenildiği kadar alınabilir (xᵢ ≥ 0 tamsayı). Kapasiteli üretim hattı bin paketleme veya hisse senedi tam sayı işlem birimleri.
- Multi-Dimensional Knapsack (MKP): m kısıt; her öğenin m boyutta ağırlığı var (bütçe + iş-gücü saati + makine saati + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ tüm j boyutlar için. Çok daha zor.
- Quadratic Knapsack (QKP): Hedef fonksiyon ikinci-derece — Σᵢvᵢxᵢ + ΣᵢΣⱼpᵢⱼxᵢxⱼ; öğeler arasında etkileşim değeri var (sinerji). Tedarik anlaşmasında “A ve B birlikte alınırsa ekstra indirim” gibi.
- Multiple-Choice Multi-Dimensional Knapsack: Öğeler gruplar halinde; her gruptan tam bir öğe seçilir.
- Subset-Sum: Hedef değer = ağırlık; toplam ağırlık kapasiteye olabildiğince yakın (eşit). Para üstü, bütçe tam-kullanım.
- Knapsack with Set-Up: Bir öğeyi seçmek için bir set-up maliyeti var (gruplar halinde). Üretim hatları, fabrika kurulum.
Veri girdileri: aday öğe listesi N, her öğenin değer ve ağırlık tahmini (yatırım örneğinde NPV ve gerekli yatırım; pazarlama örneğinde tahmini dönüşüm değeri ve kampanya maliyeti), kapasite W (yıllık bütçe, aylık bütçe, kargo uçağı yük kapasitesi), çok-boyutlu kısıtlar (iş-gücü saati, kapasite saati, kategori-bazlı alt-bütçe), bağımlılık yapısı (öncelik, karşılıklı dışlayıcı, kapasite indirimi).
2. Çözüm — algoritmik araçlar.
- Greedy + LP-relaxation: En basit yaklaşım — öğeleri değer/ağırlık oranına göre sırala, üstten kapasite dolana kadar seç. Optimum garanti etmez (klasik karşı örnek: kapasite 10, üç öğe (v,w) = (6,5), (5,4), (4,3) — greedy 6+5=11 verir ama 5+4+3=12 optimum); LP-relaxation alt-sınırı sağlar, branch-and-bound için kullanılır. Pratik tek-defalık quick check için iyi.
- Dinamik programlama (DP): Klasik pseudo-polinom algoritma (zaman kapasite W’ya bağlı). State: dp[i][w] = ilk i öğe içinden, kapasite w’yu aşmadan, alınabilir maksimum değer. Geçiş: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). Karmaşıklık O(N×W). N = 1000 öğe, W = 100.000 TRY birim = 10⁸ işlem, modern hesaplayıcıda saniyeler. Pratik gerçek: orta ölçek (N ≤ 1000, W ≤ 10⁶) DP ile dakikalar içinde optimum; pratisyenin “NP-hard, çözülmez” sezgisi yanlış. W üstel büyürse (örn. milyon TRY birim) DP yavaşlar.
- Branch-and-bound (dallandır-sınırla — olası çözümleri ağaç gibi tarayıp budama yöntemi): her dalda LP-relaxation üst-sınırı ile prune. Çekirdek değişken (core variables) tekniği milyon-öğe 0/1 knapsack için pratik state-of-the-art.
- MIP (Mixed-Integer Linear Programming — bir kısım değişkeni 0/1 bir kısmı sürekli olan eniyileme): çok-boyutlu (MKP) ve karmaşık bağımlılıkları olan instance için doğal araç. Açık-kaynak veya ticari MIP çözücüler 100-1000 öğeli MKP’leri dakikalar-saatler içinde optimum (ya da iyi gap’le yakın-optimum) çözer.
- FPTAS (Fully Polynomial-Time Approximation Scheme — herhangi ε > 0 için optimumun (1-ε) kadarını polinom zamanda garanti eden algoritma): ε = 0.01 için optimumun %99’unu garanti eder, çok büyük instance için pratik.
- Metaheuristik (genetik, tabu, simulated annealing): Çok büyük çok-boyutlu MKP veya bağımlılık zengin instance için son çare; optimum garanti yok ama pratik kalite.
Yatırım projesi seçimi (50-200 öğe, tek bütçe veya 2-4 kısıt): MIP veya 0/1 DP saniyeler içinde optimum. Çok büyük çok-boyutlu (500+ öğe, 5+ kısıt): MIP yakın-optimum veya FPTAS. Pratikte MIP çoğu kurumsal senaryoda yeterli; özel knapsack algoritması nadiren gerekir.
3. Saha entegrasyonu ve duyarlılık analizi. Çıktı: seçilen alt-küme + toplam değer + her kısıt kullanımı + LP-relaxation tabanlı duyarlılık (hangi proje kıl payı seçildi, hangisi kıl payı düştü). Yatırım komitesi raporu: seçim önerisi, alternatif senaryolar (bütçe ±%10 ise hangi proje farklı, iş-gücü kısıtı gevşetilirse hangi proje gelir), bağımlılık ve siyasi-strateji kısıtlarının açıkça raporlanması. Çeyreklik yeniden-planlama: yeni proje teklifleri eklenir, gerçekleşen NPV ile karşılaştırma, model yeniden çözülür.
Alternatifler
Manuel + spreadsheet sıralama
ÜcretsizSıfır lisans
Kim için: Küçük ölçek, 10-30 aday öğe, tek bütçe kısıtı, basit bağımlılık
- + Sıfır kurulum
- + Yatırım komitesinin siyasi-strateji müdahalesi kolay
- + Hızlı 'üst-N' tartışması için yeterli
- − Sıralama-ile-seçim en iyi alt-kümeyi garanti etmez — tipik %5-15 değer kaybı
- − Çok-boyutlu kısıt (iş-gücü + kapasite) elden modellenmez
- − Bağımlılık yapısı (öncelikli proje, karşılıklı dışlayıcı çift) kaba
- − Duyarlılık analizi (bütçe ±%10 ise ne değişir?) yok
Açık-kaynak MIP çözücü + iç model
Açık KaynakLisans ücretsiz; iç geliştirme 4-12 hafta veya 200K-600K TRY danışmanlık
Kim için: OR veya analitik ekibi olan kurum, yıllık 50M+ TRY yatırım bütçesi
- + Lisans bedeli yok
- + Proje seçimi modeli açık-kaynak çözücülerle iyi karşılığı vardır
- + Senaryo analizi (bütçe, iş-gücü, kapasite parametre değişimi) hızlı
- + İçeride sahiplik — model şeffaf, varsayımlar denetlenebilir
- − Optimizasyon uzmanı + veri mühendisi gerekir
- − Model bakımı işletmeye düşer
- − Getiri tahmini sapması açık-kaynak çözücüde de aynen sürüyor — model girdisinin kalitesi belirleyici
Ticari MIP çözücü + iç model
KurumsalYıllık 200K-1.5M TRY lisans (TR pazar gözlemi); büyük kurum 2-5M TRY
Kim için: Büyük holding, yıllık 500M+ TRY yatırım bütçesi, çok-boyutlu kısıt
- + Endüstri-düzeyinde optimum çözüm motoru
- + Yüksek-performans paralel çözüm
- + Modelleme arayüzü olgun (skript + modelleme dili desteği)
- + Endüstriyel destek
- − Yüksek lisans
- − İçeride model geliştirme ve bakım için yine optimizasyon uzmanı gerekir
- − Tedarikçi bağımlılığı riski — model bir başka çözücüye taşıma 4-12 hafta
Kapsamlı kurumsal planlama / proje portföy yönetimi yazılımı
KurumsalYıllık 500K-3M TRY lisans (TR pazar gözlemi), kurum ölçeğine göre
Kim için: Çoklu portföy, çoklu kategori, çoklu coğrafya holding
- + Proje teklif sürecinden seçime kadar bütünleşik akış
- + Bağımlılık yapısı (öncelikli proje, dışlayıcı çift, sinerji indirimi) arayüzde modellenebilir
- + Çeyreklik yeniden-planlama ve gerçekleşen getiri karşılaştırması yerleşik
- + Yatırım komitesi raporları hazır
- − Yüksek lisans + 6-12 ay kurulum
- − Optimum çözücü modülü genelde sınırlı — büyük portföy için yetersiz olabilir
- − Tedarikçi bağımlılığı
- − Sektörel özelleştirme proje süresi ekler
Tavsiye
Çözüm görüşmesinde sor
- Proje seçimi modülü hangi varyantları destekliyor — 0/1 seçim, sınırlı sayıda lot, tek-bütçe, çok-boyutlu kısıt, gruplu seçim, set-up maliyeti?
- Çözüm motoru hangi yöntemi kullanıyor — optimum garanti veren çözücü, dinamik program, yaklaşıklık, gelişmiş arama? 200-1000 projeli çok-kısıtlı portföyde tipik çözüm süresi nedir?
- Bağımlılık yapısı (öncelikli proje, karşılıklı dışlayıcı çift, sinerji indirimi, set-up maliyeti) arayüzde modellenebilir mi, yoksa kurallar elle mi yazılıyor?
- Duyarlılık analizi — bütçe ±%10 veya iş-gücü kısıtı ±%20 senaryolarında hangi proje değişir, raporlama otomatik mi?
- Getiri girdisinin belirsizlik bandı modellenebilir mi (belirsizlik altında portföy seçimi), yoksa sadece nokta tahmini mi?
- Çok-kısıtlı çözümde elde edilen değer ile teorik üst-sınır arasındaki fark (yüzde sapma) raporlanıyor mu — kullanıcı 'optimum mu yakın-optimum mu' bilir mi?
- Çözüm sonucu yatırım komitesi sunumu için doğrudan rapor üretiyor mu — seçilen alt-küme, kullanılan bütçe yüzdesi, kıl payı kararlar?
- Sözleşme biterse aday proje verisi, model girdisi, çözüm geçmişi, duyarlılık raporları hangi standart formatta dışa aktarılabilir?
Teknik detay
Editör notu
Bu problem halk dilinde “proje seçimi”, “bütçe dağıtımı” veya “yatırım önceliklendirme” diye anılır. Akademik literatürde adı Knapsack Problem (Sırt Çantası Problemi) — adı kapasiteli sırt çantasına en değerli yükü koyma metaforundan gelir (Dantzig 1957). Ayrık seçim problemlerinin atasıdır. Portföy seçimi (#018 Markowitz Mean-Variance) ile karıştırılmamalıdır: Markowitz sürekli ağırlıklar verir (her varlığa portföyün ne kadarı düşsün, %0-100 arası reel sayı) ve varyans + korelasyon üzerinden risk modeller; knapsack ayrık ya seç ya seçme kararıdır (xᵢ ∈ {0, 1}) ve bütçe + NPV üzerinden değer maksimize eder. Klasik karar problemlerinin pek çoğunun altında knapsack vardır — yatırım projesi seçimi, kampanya seçimi, kapasiteli kargo yükleme, tedarikçi alt-küme seçimi. Cutting stock (#005, çok-boyutlu geometrik kesim) ve 3D bin packing (#015, hacimsel paketleme) yakın akrabalardır ama farklı problemlerdir: knapsack değer maksimum, cutting stock rulo sayısı minimum, 3D bin packing paket sığdırma. Assortment planning (#017, perakende raf seçimi) bir özel knapsack varyantıdır — ürün-bazlı talep modeli ile birleştirilmiş.
Sektörde en sık atlanan nokta: pseudo-polinom DP ile karmaşıklık sınıflandırması arasındaki fark. Knapsack NP-hard sınıfındadır — yani genel girdi büyüklüğüne (öğe sayısı ve kapasitenin bit sayısı) göre polinom çözüm bilinmiyor. Bu pratisyenin sezgisinde “çözülmez” diye yorumlanır — yanlış. Bellman’ın dinamik programı O(N×W) zamanda çalışır — W kapasite. Yatırım örneğinde W = 50M TRY ama biz bunu binlik birimde modelleriz (W = 50.000), N = 200 proje, 10⁷ işlem, modern hesaplayıcıda saniyeler. Pseudo-polinom: zaman W’nın değerine polinom (W’nın bit sayısına üstel). Pratik sonuç: W küçük tutulduğunda (binler, on binler) DP milyon-öğe-ölçekli knapsack instance’larını dakikalar içinde optimum çözer. Pratisyen yatırım komitesinde “matematiksel optimum bilemeyiz, sadece sezgiyle seçeriz” sonucuna sıçramamalı — pratik knapsack çözümü için MIP veya DP araçları herkesin elinde.
İkinci atlanan nokta: NPV / değer girdisi belirsizliği. Knapsack matematiği, girdi NPV ve ağırlık değerlerinin kesin olduğu varsayımına dayanır. Gerçekte NPV tahmini 5-yıllık projeksiyona dayanır, ±%20-40 sapma normaldir; özellikle yeni teknoloji ve dijital dönüşüm projelerinde belirsizlik daha büyüktür. Klasik knapsack çözümü bu belirsizliği yutar ve “optimum” diye tek bir alt-küme önerir; oysa NPV ±%20 senaryosunda alt-küme tamamen değişebilir. Çözüm: stokastik knapsack (Bertsimas ve Sim 2003 robust optimization yaklaşımı, NPV belirsizlik kümesi içinde worst-case optimum) veya chance-constrained knapsack (bütçe aşma olasılığı en fazla %5) veya basit duyarlılık analizi (NPV ±%20 senaryoları arasında istikrarlı kalan projeleri raporla). Üçüncü atlanan nokta: bağımlılık yapısı. Klasik knapsack öğelerin bağımsız olduğunu varsayar — proje A ile proje B’nin değeri toplanır. Gerçekte sinerjik (A + B birlikte ekstra değer), karşılıklı dışlayıcı (A xor B), öncelikli (A → B aktiflik), kapasite-indirimi (A seçilirse B’nin maliyeti düşer) yapılar vardır. Bunlar MIP kısıtları ile modellenir; standart knapsack arayüzünden MIP’e geçmeyi gerektirir.
Adım adım yol — KOBİ için
Aşama 1 — Önce ölç, sonra plan. Son 3-5 yılın aday yatırım projeleri (kabul edilen + edilmeyen): teklif edilen NPV tahmini, gerçekleşen NPV (kabul edilenler için), yatırım tutarı, iş-gücü saati, kapasite saati. NPV tahmini sapma istatistiği: kategorisine (genişletme, modernizasyon, dijital, IT) ve büyüklüğüne göre tahmin/gerçekleşen oranı, ±%? band. Bütçe ve diğer kısıtlar (iş-gücü, kapasite saati, kategori-bazlı alt-bütçe) için yıllık planlamanın hangi noktasında kesinleştiğini belgeleyin.
Aşama 2 — Bilgi sermayesini çıkar. Aday öğelerin tipik bağımlılık yapısı (öncelikli proje çiftleri, karşılıklı dışlayıcı çiftler, kapasite-indirimi sinerji). NPV tahmini güvenilirlik bandı: küçük standart proje ±%10, dijital dönüşüm projesi ±%30-40, AR-GE ±%50. Kategori-bazlı alt-bütçe siyasi gereklilikleri (bölge dengesi, sektör çeşitlendirme).
Aşama 3 — Pilot. 6-10 hafta. Bir yıllık yatırım komitesi döneminde mevcut sezgisel seçim ile paralel olarak açık-kaynak MIP çözümü çalıştır. Aynı aday öğe seti için iki sonucu yan yana raporla; farkları açıkla (greedy hangi projeyi seçti, MIP hangisini, neden). Karar yine yatırım komitesindedir; MIP öneri verir. Başarı kriteri önceden belirlenmiş: MIP-önerili portföyün NPV’si greedy’ye göre +%5 minimum.
Aşama 4 — Yaygınlaştırma. 6-12 ay sürede tam yatırım komitesi sürecinde MIP. Çeyreklik yeniden-planlama (yeni teklifler eklenir, kapatılmış projeler düşürülür). Yıllık duyarlılık analizi (bütçe ±%10 senaryolar). Stokastik knapsack veya robust optimization adımı NPV belirsizlik tabanı kurulduktan sonra. Üç aylık yatırım komitesi: MIP önerisi vs onaylanan portföy karşılaştırması, kıl payı kararların listesi, NPV tahmin/gerçekleşen kalibrasyonu.
Riskler — ne yanlış gidebilir
- NPV / getiri tahmini sapması. Knapsack çözümü girdi NPV’lere matematiksel olarak optimumdur; ama NPV ±%20-40 sapsa optimum alt-küme değişebilir. Robust veya stokastik knapsack uzantısı veya en az duyarlılık analizi (NPV ±%20 senaryoları arasında istikrarlı projeler) şart. Tahmin kalibrasyonu için tarihsel gerçekleşen NPV / tahmini NPV oranını kategori-bazlı izleyin.
- Proje bağımsızlığı varsayımı. Klasik knapsack öğelerin değerinin toplanır olduğunu varsayar; oysa pratikte sinerji (A + B birlikte ekstra değer), karşılıklı dışlayıcı (A xor B), öncelikli (A → B aktiflik), kapasite-indirimi (A seçilirse B daha ucuz) yapılar vardır. Bunlar MIP kısıtları ile modellenir; standart knapsack arayüzünden MIP’e geçmek gerek.
- Risk dağılımı dikkate alınmıyor. Saf knapsack toplam değer maksimumu hedefler; portföy riskini (varyans, kovaryans, kuyruk riski) modellemez. Aynı sektörde 5 proje seçmek toplam NPV yüksek verebilir ama sektör çakışmasında portföyü riskli yapar. Sektör / coğrafya / kategori alt-bütçe kısıtları ek olarak modellenmeli, veya portföy seçimi ile birlikte CVaR (#063) tipi risk ölçütü eklenmeli.
- Tek tedarikçi yatırım planlama yazılımı bağımlılığı. Sözleşmede “aday öğe verisi, model girdisi, çözüm geçmişi, duyarlılık raporları yıllık standart format ihracı” maddesi olmazsa, yazılımı değiştirmek kurumsal yatırım planlama hafızasını sıfırlamak demektir. Açık-kaynak MIP + iç-model yaklaşımı orta ölçekte tedarikçi bağımsızlığı sağlar.
Çözüm yöntemine teknik bakış
| Yaklaşım | Tipik ölçek | Çözüm süresi | Optimum garanti? |
|---|---|---|---|
| Greedy (NPV/yatırım sırala) | Her ölçek | anında | Hayır (%85-95 optimum tipik) |
| LP-relaxation üst-sınırı | Her ölçek | anında | Hayır (üst-sınır) |
| Dynamic Programming (Bellman 1957) | Orta (N≤1000, W≤10⁶) | saniyeler-dakikalar | Evet |
| Branch-and-Bound (Martello-Toth 1990) | Orta-büyük 0/1 KP | dakikalar-saatler | Evet |
| Pisinger expanding-core (1997) | Çok büyük 0/1 KP | dakikalar | Evet |
| MIP (genel çözücü) | Genel (MKP, QKP, set-up dahil) | saniyeler-saatler | Evet (gap içinde) |
| FPTAS (Ibarra-Kim 1975) | Çok büyük, ε-yaklaşım kabul | dakikalar | (1-ε) optimum garanti |
| Metaheuristik (genetik, tabu, SA) | Çok büyük MKP, bağımlılık zengin | dakikalar-saatler | Hayır, iyi pratik kalite |
Knapsack varyantları karşılaştırması:
- 0/1 Knapsack: Her öğe ya seçilir ya seçilmez. Klasik yatırım projesi seçimi. xᵢ ∈ {0, 1}.
- Bounded Knapsack: Her öğenin sınırlı sayıda kopyası alınabilir. Tedarik lot sayısı. xᵢ ∈ {0, …, cᵢ}.
- Unbounded Knapsack: Her öğeden istenildiği kadar. Kapasiteli üretim, hisse tam-birim. xᵢ ≥ 0 tamsayı.
- Multi-Dimensional Knapsack (MKP): m kısıt — bütçe + iş-gücü + kapasite + kategori. Çok daha zor; orta ölçekte hâlâ MIP ile saatlerde optimum.
- Quadratic Knapsack (QKP): Öğe çiftleri arası sinerji veya çakışma değeri. Tedarik anlaşmasında “A + B birlikte indirim” gibi.
- Multiple-Choice MKP: Öğeler gruplara bölünmüş, her gruptan tam bir öğe. Modüler seçim (CPU + RAM + disk paketi).
- Subset-Sum: Hedef = ağırlık; toplam ağırlık kapasiteye olabildiğince yakın. Para üstü, bütçe tam-kullanım.
- Knapsack with Set-Up: Bir grup öğeyi etkinleştirmek için sabit set-up maliyeti. Üretim hattı, fabrika açma.
Hedef fonksiyonu seçimi:
- Hedef 1 — Toplam değer (NPV, dönüşüm değeri) maksimum: Klasik.
- Hedef 2 — Bütçe kullanım yüzdesi maksimum (subset-sum yakın): Bütçe tam-tüketim disiplini.
- Hedef 3 — Robust / worst-case değer maksimum (NPV belirsizlik bandı içinde): Bertsimas-Sim robust optimization.
- Hedef 4 — Beklenen değer maksimum + varyans cezası (stokastik): Mean-variance knapsack, portföy mantığı.
Bağımlılık modelleme (MIP’de):
- Öncelik (A → B): xB ≤ xA (B seçilirse A da seçilmiş olmalı).
- Karşılıklı dışlayıcı (A xor B): xA + xB ≤ 1.
- Sinerji indirimi: ek karar yA·B; A ve B birlikteyse maliyet düşer.
- Set-up maliyeti: ek karar yk grup için; grup içinde öğe seçilirse set-up devreye girer.
- Kategori alt-bütçe: Σᵢ∈Cwᵢxᵢ ≤ Wc her kategori C için.
Akademik kaynaklar
Sayfanın frontmatter’ında sources alanında listelidir.
Kaynaklar
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. Knapsack ve ayrık optimizasyonun LP/IP çerçevesinin temel kaynağı.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. Dinamik programlamanın temel kitabı; knapsack DP’nin kanonik örneğidir.
- Martello, S. ve Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. Klasik kapsamlı kitap; branch-and-bound algoritmaları, deneysel karşılaştırmalar.
- Kellerer, H., Pferschy, U. ve Pisinger, D. (2004). Knapsack Problems. Springer. Modern kapsamlı kaynak; tüm varyantlar, FPTAS, MKP, QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. 0/1 knapsack için pratik state-of-the-art expanding-core algoritması.
- Ibarra, O. H. ve Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. Knapsack FPTAS’ın temel kaynağı.
- YÖK Tez Merkezi — anahtar kelime: ‘sırt çantası’, ‘knapsack’ veya ‘proje seçimi’ — TR akademisinden 25+ tez. tez.yok.gov.tr
Sözlük
- Knapsack Problem
- Bir kapasite kısıtı altında N aday öğeden alt-küme seçimi: her öğenin değeri ve ağırlığı verili; toplam ağırlık kapasiteyi aşmadan toplam değer maksimum. Ayrık optimizasyonun temel problemi.
- Dynamic Programming
- Çok-aşamalı karar problemlerini örtüşen alt-problemlere özyinelemeli olarak ayırarak ve ara sonuçları saklayarak çözen OR / bilgisayar bilimleri tekniği; Bellman (1957) tarafından geliştirilmiştir.
- MIP
- Karar değişkenlerinin bir kısmının tam sayı (örn. 'kaç kamyon', 'kaç vardiya') olduğu optimizasyon türü.
Benzer problemler
Çoklu Girdi + Çoklu Çıktı — Şube/Birim Verimliliğini Diğerlerine Kıyasla Nasıl Ölçerim?
100-500 şubeli bir banka, 200-1.500 yataklı çok-merkezli bir hastane zinciri, yüzlerce okullu bir eğitim müdürlüğü ya da il-il karşılaştırma yapan bir kamu kurumu işletiyorsanız bu sayfa size yöneliktir. Temel soru: hangi şube/hastane/okul verimli, hangisi değil — ve verimsiz olanlar hangi 'akran' birimi örnek alarak ne kadar iyileşmeli? Her birim aynı anda birden fazla girdi tüketir (personel, alan, bütçe) ve birden fazla çıktı üretir (gelir, müşteri/hasta/öğrenci sayısı, kalite); 'gelir/personel' gibi tek-oran metrikler bu çoklu yapıyı yansıtmaz ve verimsiz görüneni aslında verimli ya da tersi gösterebilir. Yöntem doğru kurgulandığında — akran benchmark'ı somut bir iyileştirme kanıtı verdiği için — verimsiz birimler için iyileştirme planlarının kabul oranı %40-70 artar; orta-ölçekli bir banka şubesi ağında bu yıllık 10-50 milyon TRY operasyonel marja denk gelir.
Hangi ATM'e Ne Kadar Nakit Koysam, Ne Sıklıkta Yenilesem — Boş ATM Şikayetiyle Yüksek İmmobilizasyon Maliyeti Arasında Denge?
50-500 ATM işleten orta ölçekli bir ticari banka ya da katılım bankasıysanız, her sabah üç soruya cevap vermek zorundasınız: hangi ATM'e ne kadar para konsun, hangisi kaç günde bir yenilensin, zırhlı araç hangi rotada hangi ATM'leri dolaşsın. Yanlış uçlar pahalı: gereğinden fazla nakit ATM'in içinde bekleyince yıllık %5-15 faiz fırsat maliyeti + sigorta primi şişer; az nakit konunca ATM boşalır, müşteri çekemez, şikayet ve marka kaybı gelir. AVM, otobüs durağı, kampüs, ofis gibi farklı lokasyonların talep deseni çok farklı olduğu için sezgisel 'hepsine aynı miktar' kuralı her iki ucu birden zarar verir. Bu sayfa, üç kararı veriyle birlikte vermek isteyen banka operasyon ekiplerine yöneliktir.
Paranın Hangi Oranda Hangi Yatırıma Gitsin?
Bir KOBİ veya bireysel yatırımcının önündeki temel sorulardan biri: elinde belli bir sermaye var, önünde birden çok yatırım seçeneği (hisse senedi, tahvil, döviz, emtia, mevduat, gayrimenkul, kendi işine yatırım), her birinin beklenen getirisi ve risk düzeyi farklı, üstelik bu yatırımlar arasında korelasyon var (biri düşerken diğeri yükselir, vs.). Hangi yatırıma sermayenin yüzde kaçı gidecek? Bu sorunun matematiksel adı Portfolio Optimization Problem'dır. 1952'de Harry Markowitz mean-variance framework'ünü kurdu — Nobel ödüllü bu yaklaşım modern portföy teorisinin temelidir. Beklenen getiriyi maksimize edip varyansı (riski) minimize etme problemi quadratic programming ile çözülür.