📋 İçindekiler

  1. LP'nin Sınırları: Neden NLP
  2. NLP Problem Sınıflandırması
  3. Lagrange Çarpanları
  4. KKT (Karush-Kuhn-Tucker) Koşulları
  5. Konveks vs Non-Konveks Optimizasyon
  6. Metaheuristik Yöntemler
  7. Dinamik Programlama (DP)
  8. Bellman Denklemi ve Optimallik Prensibi
  9. Sırt Çantası Problemi: Adım Adım
  10. En Kısa Yol Problemi (DP ile)
  11. Vaka 1: Üretim Planlaması
  12. Vaka 2: Yatırım Portföyü
  13. Sonuç

1. LP'nin Sınırları: Neden Doğrusal Olmayan Programlama

Doğrusal Programlama (LP) der ki: "1 sandalye yapmak 10₺ ise 1000 sandalye 10.000₺'dir" — sabit ölçek getirisi. Ancak gerçek hayat doğrusal değildir:

Durum LP Varsayımı Gerçek Hayat (NLP)
Ölçek Ekonomisi Birim maliyet sabit Çok üretince toptan alım → birim maliyet düşer
Azalan Getiri Kâr doğrusal artar Pazar doyması → her ek birim daha az kâr getirir
Portföy Riski Risk yok Varyans (σ²) → karesel fonksiyon
Mesafe Düz çizgi Öklid mesafesi → karesel kök
Kimyasal Reaksiyon Doğrusal oran Arrhenius denklemi → üstel fonksiyon
LP: max Z = 5x₁ + 6x₂    → Simplex ile kolay çözülür ✅
NLP: max Z = 5x₁² + sin(x₂) - log(x₁)    → Simplex çalışmaz ❌

2. NLP Problem Sınıflandırması

Problem Türü Amaç Fonksiyonu Kısıtlar Çözüm Yöntemi
Kısıtsız NLP Doğrusal olmayan Yok Gradyan, Newton, Quasi-Newton
Kısıtlı NLP Doğrusal olmayan Doğrusal veya doğrusal olmayan Lagrange, KKT, SQP
Konveks Programlama Konveks (içbükey minimizasyon) Konveks küme Global optimum garantili
Kuadratik Programlama (QP) Karesel: x'Qx + c'x Doğrusal Portföy optimizasyonu (Markowitz)
Geometrik Programlama Posinomyal fonksiyonlar Posinomyal Mühendislik tasarım optimizasyonu

3. Lagrange Çarpanları: Adım Adım

Eşitlik kısıtlı NLP problemlerinin çözüm yöntemi:

Problem: max f(x₁, x₂) = x₁ · x₂
Kısıt: x₁ + x₂ = 10

Lagrange Fonksiyonu:
L(x₁, x₂, λ) = x₁·x₂ - λ(x₁ + x₂ - 10)

Kısmi türevler = 0:
∂L/∂x₁ = x₂ - λ = 0 → x₂ = λ    ...(1)
∂L/∂x₂ = x₁ - λ = 0 → x₁ = λ    ...(2)
∂L/∂λ = -(x₁ + x₂ - 10) = 0 → x₁ + x₂ = 10    ...(3)

(1) ve (2)'den: x₁ = x₂ = λ
(3)'e koy: 2λ = 10 → λ = 5

Çözüm: x₁* = 5, x₂* = 5, f* = 25
λ = 5 → Kısıtı 1 birim gevşetebilseydik (x₁+x₂=11), f ≈ 30 olurdu

4. KKT (Karush-Kuhn-Tucker) Koşulları

Eşitsizlik kısıtlı NLP problemleri için genelleştirilmiş optimallik koşulları:

Problem: min f(x), kısıt: gi(x) ≤ 0

KKT Koşulları:
1. Stasyonerlik: ∇f(x*) + Σ μi·∇gi(x*) = 0
2. Primal Uygunluk: gi(x*) ≤ 0
3. Dual Uygunluk: μi ≥ 0
4. Tamamlayıcı Gevşeklik: μi·gi(x*) = 0

Tamamlayıcı gevşeklik: Ya kısıt aktiftir (gi=0), ya da çarpan sıfırdır (μi=0). İkisi birden pozitif olamaz!

5. Konveks vs Non-Konveks Optimizasyon

Özellik Konveks Non-Konveks
Yerel Optimum = Global Optimum ✅ Yerel ≠ Global ❌
Çözüm Garantisi Polinomyal zamanda çözülebilir NP-Hard olabilir
Fonksiyon Şekli Tek çukur (bowl) Birden fazla tepe ve çukur
Çözüm Yöntemi Gradyan, interior point Metaheuristik, global arama
Endüstriyel Örnek Portföy optimizasyonu Tesis yeri seçimi, iş çizelgeleme
⚠️
Yerel Maksimum Tuzağı: Non-konveks problemlerde gradyan tabanlı algoritma küçük bir tepenin zirvesinde durabilir — gerçek zirve (global optimum) göremez. Bu nedenle metaheuristik yöntemler kullanılır.

6. Metaheuristik Yöntemler

Yöntem İlham Kaynağı Nasıl Çalışır Endüstriyel Kullanım
Genetik Algoritma (GA) Doğal seleksiyon Çaprazlama + mutasyon ile popülasyon evrimleşir İş çizelgeleme, tesis yerleşimi
Tavlama Benzetimi (SA) Metal soğutma Yüksek sıcaklıkta kötü çözümleri kabul eder, soğudukça sadeleşir TSP, devre kartı tasarımı
Karınca Kolonisi (ACO) Karınca feromon izi Karıncalar kısa yollara daha çok feromon bırakır Araç rotalama (VRP)
Parçacık Sürüsü (PSO) Kuş sürüsü Parçacıklar en iyi konuma doğru hareket eder Sinir ağı eğitimi, parametre ayarı
Tabu Arama Bellek mekanizması Ziyaret edilen çözümleri "tabu" listesine koyar Kapasite planlama

7. Dinamik Programlama (DP)

Richard Bellman tarafından 1953'te geliştirilen DP, büyük bir problemi sıralı alt-problemlere bölerek çözer. NLP'den farklı olarak, DP ayrık/çok aşamalı karar problemlerini hedefler.

💡
Bellman'ın Optimallik Prensibi:
"Önceki kararlarınız sonucu hangi duruma ulaştığınız önemli değildir. Asıl önemli olan, şu an bulunduğunuz durumdan itibaren alacağınız kararların optimal politikasını çizmektir." — Richard Bellman, 1953

7.1 DP Terminolojisi

Terim Tanım Örnek
Aşama (Stage) Karar verilen nokta Yıl 1, Yıl 2, ... Yıl N
Durum (State) Her aşamadaki sistem durumu Kalan bütçe, stok seviyesi
Karar (Decision) Her aşamada alınan eylem Ne kadar yatırım yap
Dönüşüm (Transition) Kararla durum nasıl değişir sn+1 = sn - xn
fn(s) n. aşamadan itibaren optimal getiri Bellman denklemi ile hesaplanır

8. Bellman Denklemi

Geriye Doğru Özyineleme (Backward Recursion):

fn(s) = maxxn { rn(s, xn) + fn+1(s - xn) }

fn(s): n. aşamadan itibaren s durumunda elde edilecek optimal toplam getiri
rn(s, xn): n. aşamada xn kararının anlık getirisi
fN+1(s) = 0 (son aşama sonrası başlangıç koşulu)

9. 0-1 Sırt Çantası Problemi: Adım Adım DP Çözümü

Bir hırsız müzeye girdi. Çantası max 15 kg. İçerideki eşyalar:

Eşya Ağırlık (kg) Değer ($K) Değer/kg ($K)
Heykel 12 500 41.7
Tablo 3 300 100.0
Gümüş Kupa 5 400 80.0
Altın Sikke 6 200 33.3

9.1 DP Tablosu (Geriye Sarma)

Aşama 4 (sadece Altın Sikke):
f4(s) = 200 eğer s ≥ 6, aksi halde 0

Aşama 3 (Gümüş Kupa + kalan):
f3(s) = max{f4(s), 400 + f4(s-5)}   (s ≥ 5 için)
f3(15) = max{200, 400+200} = 600 (Kupa + Sikke)
f3(10) = max{200, 400+200} = 600
f3(5) = max{0, 400} = 400 (sadece Kupa)

Aşama 2 (Tablo + kalan):
f2(s) = max{f3(s), 300 + f3(s-3)}
f2(15) = max{600, 300+600} = 900 (Tablo + Kupa + Sikke)
f2(12) = max{600, 300+400} = 700

Aşama 1 (Heykel + kalan):
f1(15) = max{f2(15), 500 + f2(15-12)}
= max{900, 500 + f2(3)}
f2(3) = max{f3(3), 300+f3(0)} = max{0, 300} = 300
= max{900, 500+300} = max{900, 800} = 900

Optimal Çözüm: Tablo (3kg) + Kupa (5kg) + Sikke (6kg) = 14 kg, $900K
Heykel en değerli eşya ama çantaya daha az sığdırıyor. "En pahalı = En iyi" yanılgısı!

10. En Kısa Yol Problemi (DP ile)

Bir şehir ağında A'dan F'ye en kısa yolu DP ile bulalım:

Ağ yapısı (mesafeler km):
A→B: 4 | A→C: 2 | B→D: 5 | B→E: 10 | C→D: 8
C→E: 3 | D→F: 6 | E→F: 7

Geriye Sarma (F'den başla):
f(F) = 0
f(D) = 6 (D→F)
f(E) = 7 (E→F)
f(B) = min{5+f(D), 10+f(E)} = min{11, 17} = 11 (B→D→F)
f(C) = min{8+f(D), 3+f(E)} = min{14, 10} = 10 (C→E→F)
f(A) = min{4+f(B), 2+f(C)} = min{15, 12} = 12 (A→C→E→F)

En kısa yol: A → C → E → F = 12 km

11. Vaka Çalışması 1: Üretim Planlaması (DP)

🏭 Mobilya Fabrikası — 4 Aylık Üretim Planı

Problem: Talep değişken, stok maliyeti var, fazla mesai pahalı. Her ay ne kadar üretilmeli

Ay Talep Normal Kapasite Normal Maliyet Fazla Mesai Maliyet Stok Maliyeti
1 100 80 ₺200/birim ₺300/birim ₺50/birim/ay
2 120 80 ₺200 ₺300 ₺50
3 60 80 ₺200 ₺300 ₺50
4 90 80 ₺200 ₺300 ₺50

DP çözümü: Her ayı bir aşama, dönem sonu stoğu bir durum (state) olarak tanımla. Bellman denklemi ile geriye doğru çözerek toplam maliyeti minimize et.

Sonuç: Ay 1'de 100 (80 normal + 20 FM), Ay 2'de 120 (80 normal + 40 FM), Ay 3'te 80 (60 talep + 20 stok), Ay 4'te 70 (90 talep - 20 stoktan) = Toplam maliyet: ₺79.000 (sezgisel yönteme göre %12 tasarruf).

12. Vaka Çalışması 2: Yatırım Portföyü (NLP)

📈 Markowitz Portföy Optimizasyonu — Kuadratik Programlama

Problem: 3 hisse senedi arasında ₺1M yatırım dağıtımı. Beklenen getiriyi maximize ederken riski (varyansı) minimize et.

Kuadratik Amaç Fonksiyonu:
min σ²p = x'Qx = Σi Σj xi·xj·σij

Kısıtlar:
Σ xi = 1 (tüm para yatırılır)
Σ ri·xi ≥ Rmin (minimum getiri hedefi)
xi ≥ 0 (açığa satış yok)

Bu problem QP (Kuadratik Programlama) — NLP'nin özel bir halidir. Konveks olduğu için global çözüm garantidir.

13. Sonuç

🏁
İleri Optimizasyon Karar Rehberi:

📊 Problem doğrusal mı → LP / Simplex
📈 Doğrusal olmayan ama konveks mi → KKT, Interior Point
🌀 Non-konveks / çok tepeli mi → Metaheuristik (GA, SA, PSO)
📅 Çok aşamalı karar mı → Dinamik Programlama
🎒 Tamsayılı karar (al/alma) → 0-1 Knapsack, Branch & Bound
💰 Portföy / risk minimizasyonu → Kuadratik Programlama