📋 İçindekiler
- Bellman Optimallik Prensibi
- DP Yaklaşımları: Memoization vs Tabulation
- DP ile Fibonacci — Başlangıç Örneği
- Dijkstra En Kısa Yol — 8 Düğümlü Ağ
- 0-1 Sırt Çantası Problemi — Tam DP Tablosu
- Donanım Değişim Kararı (Equipment Replacement)
- Wagner-Whitin Algoritması — Lot Boyutu
- Üretim Planlama DP
- Gezgin Satıcı Problemi (TSP) — DP Yaklaşımı
- Endüstri Uygulamaları
Bellman Optimallik Prensibi
Richard Bellman (1953), dinamik programlama terimini ve yöntemini geliştirdi. Temel fikir son derece güçlüdür:
"Optimal bir politikanın her alt politikası da kendi başına optimal olmalıdır."
Yani: Eğer A→C→D→F yolu A'dan F'ye en kısa yolsa, bu yol üzerindeki C→D→F de C'den F'ye en kısa yoldur.
Bu prensip, büyük problemi küçük örtüşen alt problemlere (overlapping subproblems) bölmemize ve her alt problemi yalnızca bir kez çözüp sonucu saklamaya olanak verir. Bu, divide and conquer'dan temel farkıdır — DP'de alt problemler birbirinden bağımsız değil, birbirleri üzerine kuruludur.
DP'nin Uygulanabilme Koşulları
- Optimal alt yapı: Büyük problemin optimal çözümü, alt problemlerin optimal çözümlerini içeriyor
- Örtüşen alt problemler: Aynı alt problem tekrar tekrar ortaya çıkıyor (memoization ile sadece 1 kez çözülür)
DP Ne Zaman Kullanılır
- Çok aşamalı karar problemleri
- En uzun/kısa yol problemleri
- Kaynak tahsisi ve bütçe bölüştürme
- Lot boyutlama ve üretim planlama
- Makine yatırım/değiştirme kararları
- Portföy optimizasyonu
DP Yaklaşımları: Memoization vs Tabulation
🔄 Yukarıdan-Aşağı (Memoization)
Problemi özyineleme (recursion) ile çöz; hesaplana her alt problem sonucunu tabloda sakla (cache). Henüz çözülmemiş alt problemi çöz, tabloda varsa tablodan oku. Python örneği:
def dp(i, w):
if i == 0: return 0
if w[i] > w: return dp(i-1, cap)
return max(dp(i-1, cap), v[i] + dp(i-1, cap-w[i]))
📊 Aşağıdan-Yukarı (Tabulation)
En küçük alt problemden başlayarak büyüğe doğru tabloyu doldur. Özyineleme yok, döngü var. Bellek kullanımı daha öngörülebilir, taşma (stack overflow) riski yok. "Tablolama" adıyla da bilinir — iteratif DP.
for i in 1..n:
for w in 0..W:
if weight[i] > w: dp[i][w] = dp[i-1][w]
else: dp[i][w] = max(dp[i-1][w], val[i]+dp[i-1][w-weight[i]])
Dijkstra En Kısa Yol — 8 Düğümlü Ağ
Dijkstra algoritması (1956), tüm kenar ağırlıkları negatif olmayan bir ağda bir kaynak düğümden diğer tüm düğümlere en kısa yolu bulan açgözlü (greedy) bir algoritmadır. Karmaşıklığı O((V+E) log V) (ikili yığınla).
8 istasyon (A=1, B=2, C=3, D=4, E=5, F=6, G=7, H=8)
Kenar ağırlıkları = taşıma süresi (dakika)
Kaynak: A(1), Hedef: H(8) — en kısa rota
Komşuluk listesi:
1→2 (4), 1→3 (2), 2→4 (5), 2→5 (11)
3→2 (1), 3→5 (5), 3→6 (8), 4→7 (3), 5→7 (2), 5→8 (9)
6→5 (3), 6→8 (6), 7→8 (4)
| Adım | Ziyaret Edilen | d[1] | d[2] | d[3] | d[4] | d[5] | d[6] | d[7] | d[8] | Seçilen Düğüm |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | {} | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 (d=0) |
| 1 | {1} | 0 | 4 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | 3 (d=2) ← min |
| 2 | {1,3} | 0 | 3 | 2 | ∞ | 7 | 10 | ∞ | ∞ | 2 (d=3) ← min 3→2=2+1=3 < 4 → güncelle |
| 3 | {1,3,2} | 0 | 3 | 2 | 8 | 7 | 10 | ∞ | ∞ | 5 (d=7) ← min |
| 4 | {1,3,2,5} | 0 | 3 | 2 | 8 | 7 | 10 | 9 | 16 | 4 (d=8) ← min |
| 5 | {1,3,2,5,4} | 0 | 3 | 2 | 8 | 7 | 10 | 9 | 16 | 7 (d=9) ← min 4→7=8+3=11 vs 5→7=7+2=9 → 9 iyi |
| 6 | {1,3,2,5,4,7} | 0 | 3 | 2 | 8 | 7 | 10 | 9 | 13 | 6 (d=10) 7→8=9+4=13 < 16 → güncelle |
| 7 | {1,3,2,5,4,7,6} | 0 | 3 | 2 | 8 | 7 | 10 | 9 | 13 | 6→8=10+6=16 > 13 → güncelle YOK |
| 8 | TÜM | 0 | 3 | 2 | 8 | 7 | 10 | 9 | 13 ← Cevap | 8 (hedef) |
Öncül dizisi ile geri izleme (backtrack): 8'e kim geldi 7 (d=9, 7→8=4). 7'ye kim geldi 5 (d=7, 5→7=2). 5'e kim geldi 3 (d=2, 3→5=5). 3'e kim geldi 1 (d=0, 1→3=2).
Yol: A → C → B → E → G → H, toplam 2+1+5+2+4 = 14dk...
Not: 1→3→2→5→7→8 = 2+1+4+2+4 = 13 — tam hesap tablodan izlenir.
0-1 Sırt Çantası Problemi — Tam DP Tablosu
Bir hırsız (veya mühendis: hangi yatırım projeleri seçilmeli) sınırlı kapasiteli bir sırt çantasına en değerli eşyaları koymak istiyor. Her eşya ya çantaya girer ya da girmez (0-1), kısmen giremez.
Bütçe: W = 10 milyon ₺
6 proje önerisi:
| Proje | Maliyet (M₺) | NPV (M₺) | NPV/Maliyet |
|---|---|---|---|
| P1 — Otomasyon Hattı | 2 | 3 | 1.50 |
| P2 — ERP Sistemi | 3 | 4 | 1.33 |
| P3 — Depo Genişletme | 4 | 5 | 1.25 |
| P4 — Robot Kaynak | 5 | 7 | 1.40 |
| P5 — Güneş Enerji | 3 | 4 | 1.33 |
| P6 — Kalite Lab | 1 | 2 | 2.00 |
dp[i][w] = i. proje dahil edildiğinde, w bütçesiyle elde edilebilecek maksimum NPV
if weight[i] > w: dp[i][w] = dp[i−1][w] (proje çok pahalı, dahil etme)
else: dp[i][w] = max(dp[i−1][w], value[i] + dp[i−1][w − weight[i]])
DP Tablosu (Satır = proje 0..6, Sütun = bütçe 0..10 M₺):
| Proje \ Bütçe | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Hiç proje yok (0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| P1 (maliyet=2, npv=3) | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| +P2 (maliyet=3, npv=4) | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 | 7 | 7 |
| +P3 (maliyet=4, npv=5) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 12 | 12 | 12 |
| +P4 (maliyet=5, npv=7) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 10 | 12 | 13 | 14 |
| +P5 (maliyet=3, npv=4) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 10 | 12 | 13 | 14 |
| +P6 (maliyet=1, npv=2) | 0 | 2 | 3 | 5 | 6 | 7+ | 9 | 10 | 12 | 14 | 16 |
Geri İzleme (Hangi projeler seçildi):
dp[6][10]=16, dp[5][10]=14 → P6 dahil edildi (fark=2). Kalan bütçe: 10−1=9
dp[5][9]=13, dp[4][9]=13 → P5 dahil edilmedi. Kalan bütçe: 9
dp[4][9]=13, dp[3][9]=12 → P4 dahil edildi (fark=7). Kalan bütçe: 9−5=4
dp[3][4]=5, dp[2][4]=4 → P3 dahil edildi (fark=5). Kalan bütçe: 4−4=0
dp[2][0]=0, dp[1][0]=0 → P2 dahil edilmedi.
dp[1][0]=0 → P1 dahil edilmedi.
Seçilen projeler: P3 (4M₺) + P4 (5M₺) + P6 (1M₺) = 10 M₺ → NPV = 5+7+2 = 14 M₺
Tablo incelendiğinde 16'ya ulaşan çözüm: P1+P2+P4+P6 = 2+3+5+1=11 → bütçe aşımı! Yanlış okuma. Doğru: P2+P4+P6 = 3+5+1=9 M₺ → NPV=4+7+2=13. P1+P4+P6=2+5+1=8→ 3+7+2=12. P3+P4+P6=4+5+1=10 → 5+7+2=14. En iyisi: 14 M₺.
Donanım Değişim Kararı (Equipment Replacement DP)
Bir fabrikadaki makinenin ne zaman yenilenmesi gerektiği DP ile yıla göre karar verilebilen klasik bir endüstri mühendisliği problemidir.
Planlama ufku: 5 yıl
Yeni makine maliyeti: 200.000 ₺
Elde tutma maliyeti (K): Her yıl artan bakım giderleri
Satış değeri (SV): Her yıl düşen ikinci el değer
| Makine Yaşı (yıl) | Elde Tutma Maliyeti K(yaş) | İkinci El Değer SV(yaş) |
|---|---|---|
| 1 | 30.000 | 160.000 |
| 2 | 40.000 | 130.000 |
| 3 | 55.000 | 100.000 |
| 4 | 75.000 | 70.000 |
| 5 | 100.000 | 50.000 |
Durum: (yıl, makine_yaşı) → makine_yaşı = mevcut makinenin o yıldaki yaşı
Karar: T = Tut (yaşı artır), R = Değiştir (yeni makine al, yaş=1)
Maliyet(t, a) =
Eğer T (tut): K(a) + f(t+1, a+1)
Eğer R (değiştir): [P − SV(a)] + K(1) + f(t+1, 1)
P = 200.000 ₺ (yeni makine fiyatı)
f(t, a) = min{Tut maliyeti, Değiştir maliyeti}
Sınır koşulu: f(5, a) = SV(a) (5. yılın sonunda makineyi sat)
| Yıl(t) \ Yaş(a) | 1 | 2 | 3 | 4 | 5 | Optimal Karar |
|---|---|---|---|---|---|---|
| t=5 (son yıl) SV(a) hesabı | 160.000 | 130.000 | 100.000 | 70.000 | 50.000 | Makineyi sat |
| t=4 | T: 30+160=190 R: — min=190 | T: 40+130=170 R: (200-160)+30+160=230 min=170 | T: 55+100=155 R: (200-130)+30+160=260 min=155 | T: 75+70=145 R: (200-100)+30+160=290 min=145 | T: 100+50=150 R: (200-70)+30+160=320 min=150 | Tüm durumlarda: T (Tut) |
| t=3 | T: 30+190=220 R: — | T: 40+170=210 R: 40+30+190=260 min=210 | T: 55+155=210 R: 70+30+190=290 min=210 | T: 75+145=220 R: 100+30+190=320 min=220 | Tut | |
| t=2 | T: 30+220=250 | T: 40+210=250 R: 40+30+220=290 min=250 | T: 55+210=265 R: 70+30+220=320 min=265 | T: 75+220=295 R: 100+30+220=350 min=295 | Tut | |
| t=1 (başlangıç) | T: 30+250=280 | T: 40+250=290 R: 40+30+280=350 min=290 | T: 55+265=320 R: 70+30+280=380 | Tut 5 yıl boyunca! |
Toplam 5 yıllık maliyet (1 yaşlı makineyle başlanıyorsa): 30+40+55+75+100 = 300.000 ₺ (elde tutma) + satış değeri 50.000 ₺ → Net maliyet 250.000 ₺
Değiştirmek anlamsız: Yeni makine alıp 4 yıl tut → 200.000 + 30+40+55+75 = 400.000 ₺ → Daha pahalı!
Sonuç: Mevcut makineyi değiştirme kararı bu ufukta ekonomik değil.
Wagner-Whitin Algoritması — Lot Boyutu Optimizasyonu
Wagner-Whitin (1958), deterministik talep altında sabit sipariş maliyeti + stok tutma maliyeti minimize eden lot boyutunu DP ile tam optimal bulan algoritmadır. EOQ'dan farkı: değişken talep kabulü.
Sipariş Maliyeti: S = 200 ₺
Stok Tutma: h = 2 ₺/birim/hafta
| Hafta (t) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Talep D(t) | 20 | 30 | 10 | 45 | 25 | 15 |
C(j, k) = t=j'den t=k'ya kadar talebi tek seferde karşılama maliyeti
C(j,k) = S + h × Σ(t=j+1..k) (t−j) × D(t) (sipariş fazlası stok maliyeti)
f(k) = t=1'den t=k'ya kadar minimum toplam maliyet
f(k) = min(j=0..k-1){ f(j) + C(j+1, k) }
f(0) = 0 (başlangıç)
Hesaplama:
C(1,1)=200 (sadece hf1 talebi=20)
C(1,2)=200+h×1×30=200+60=260 (hf1+hf2'yi hf1'de sipariş edersek, 30 birim 1 hafta bekler)
C(1,3)=200+h×1×30+h×2×10=200+60+40=300
C(1,4)=200+60+40+h×3×45=200+60+40+270=570
C(1,5)=570+h×4×25=570+200=770
C(1,6)=770+h×5×15=770+150=920
C(2,2)=200, C(2,3)=200+h×1×10=220, C(2,4)=220+h×2×45=310...
f(1) = C(1,1) = 200
f(2) = min{C(1,2), f(1)+C(2,2)} = min{260, 200+200} = min{260, 400} = 260
f(3) = min{C(1,3), f(1)+C(2,3), f(2)+C(3,3)} = min{300, 200+220, 260+200} = min{300,420,460} = 300
f(4) = min{C(1,4), f(1)+C(2,4), f(2)+C(3,4), f(3)+C(4,4)}
= min{570, 200+310, 260+250, 300+200} = min{570,510,510,500} = 500
f(6) ≈ 740 (optimal 6 haftalık toplam maliyet)
Gezgin Satıcı Problemi (TSP) — DP ile Held-Karp
TSP: n şehri ziyaret edip başa dönen en kısa turu bulmak. Brute force: (n-1)! olasılık → n=15 için 87 milyar yol! DP (Held-Karp): O(n² × 2ⁿ) — n=20 için makul.
dp[S][i] = S kümesindeki şehirleri ziyaret edip şehir i'de biten en kısa yol uzunluğu
(1 = başlangıç şehri, S ⊆ {1,...,n}, i ∈ S, 1 ∈ S)
Başlangıç: dp[{1}][1] = 0
Özyineleme: dp[S][i] = min(dp[S\{i}][j] + dist(j,i)) ∀j ∈ S\{i}
Cevap: min(dp[{1..n}][i] + dist(i,1)) ∀i ≠ 1
4 Şehirli Örnek (mesafe matrisi, km):
d = [[0,10,15,20], [10,0,35,25], [15,35,0,30], [20,25,30,0]]
dp[{1,2}][2] = dp[{1}][1] + d[1][2] = 0 + 10 = 10
dp[{1,3}][3] = 0 + 15 = 15
dp[{1,4}][4] = 0 + 20 = 20
dp[{1,2,3}][3] = min(dp[{1,2}][2] + d[2][3]) = 10+35=45
dp[{1,2,4}][4] = min(dp[{1,2}][2] + d[2][4]) = 10+25=35
...
En iyi tur: 1→2→4→3→1 = 10+25+30+15 = 80 km
Endüstri Uygulamaları
ulusal bir demiryolu işletmesi, Marmaray ve yüksek hızlı tren seferlerinin çizelgesini DP tabanlı araçlarla optimize etmektedir. İstasyon durak kararları, yolcu akışı tahmini ve enerji verimliliği çok aşamalı DP ile birlikte ele alınmaktadır.
büyük bir enerji şirketi Enerji, Türkiye genelindeki rüzgar türbinleri için optimal bakım rotaları oluşturmak amacıyla TSP bazlı DP algoritmaları kullanmaktadır. 2024 itibarıyla teknisyen seyahat süresi %22 azaltıldı.
büyük bir süpermarket zinciri, 2.800 mağazada ürün sipariş politikalarını Wagner-Whitin ve Newsvendor modeli kombiniyle optimize ediyor. Özellikle kısa raf ömürlü ürünlerde (meyve-sebze) en iyi sipariş miktarı DP optimizasyonuyla %18 daha az fire, %12 daha az stok tükenme sağladı (yaklaşık 40 milyon ₺ yıllık etki).