Simpleks Algoritması: "En İyi Köşeyi" Bulma Sanatı

"En çok kâr için ne üretelim?"

Bir mobilya fabrikası iki ürün üretiyor: masa ve sandalye.

• Masa: 4 saat marangoz, 2 saat boyacı emeği; 30 TL kâr.
• Sandalye: 2 saat marangoz, 3 saat boyacı emeği; 20 TL kâr.

Toplam günlük: 80 saat marangoz, 60 saat boyacı emeği var. En çok kâr için ne kadar masa, ne kadar sandalye?

Bu klasik bir lineer programlama (LP) problemidir:

Maksimize: $30x + 20y$ ($x$: masa sayısı, $y$: sandalye sayısı)

Kısıtlar:

• $4x + 2y \leq 80$ (marangoz emeği)
• $2x + 3y \leq 60$ (boyacı emeği)
• $x, y \geq 0$

Geometrik olarak: bir çokgensel bölge (kısıtların kesişimi); amaç fonksiyonu bir doğru ailesi. En iyi çözüm her zaman bir köşede.

Simpleks algoritması

George Dantzig 1947'de simpleks algoritması'nı icat etti. Sezgi:

1. Bir köşeden başla (örn. $(0, 0)$).
2. Komşu köşeleri kontrol et; kâr artıran komşuyu seç.
3. Tekrarla.
4. Hiç komşu kâr artırmıyorsa, şu anki köşe optimum'dur.

Yukarıdaki örnek için:

• $(0, 0)$: kâr 0
• $(0, 20)$: kâr 400 (sadece sandalye)
• $(15, 10)$: kâr 650
• $(20, 0)$: kâr 600

Komşu kontrol → $(15, 10)$ optimum. 15 masa, 10 sandalye = 650 TL maksimum kâr.

Niye "simpleks"?

İsim simplex (Latince "basit") kelimesinden gelir. Yüksek boyutlarda bir lineer programlama bölgesi polytope (çok yüzlü) şeklindedir. Köşelerinden köşelerine yürümek "simpleks" tipi geometrik dolaşımdır.

George Dantzig'in hikâyesi

George Dantzig (1914-2005) ABD Hava Kuvvetleri'nde planlama uzmanı olarak çalışıyordu. İkinci Dünya Savaşı'ndan sonra (1947) Pentagon'da binlerce askeri planlama problemini matematiksel olarak çözmenin yolunu aradı.

Bilgisayar henüz emekleme çağındaydı; ama Dantzig matematiksel yöntemi buldu: simpleks. İlk önemli uygulamalar:

• ABD hava kuvvetleri planlamaları
• SAC (Stratejik Hava Komutanlığı) lojistik
• 1960'larda sivil endüstriye geçiş

Dantzig'in unutulmaz hikâyesi

Dantzig'in en ünlü anısı (gerçek hikâye, Will Hunting filminden çok önce):

1939'da Berkeley'de doktora öğrencisiyken Jerzy Neyman'ın dersine geç geldi. Tahtada iki problem yazılıydı; ödev sandı. Eve götürdü, çok zor'du ama uğraşıp çözdü. Birkaç gün sonra Neyman'a teslim etti.

Neyman şaşkındı: tahtadaki problemler istatistikte iki ünlü çözülememiş problem'di. Dantzig farkında olmadan ikisini de çözmüştü. Doktora tezi olarak kabul edildi.

Bu hikâye matematik dünyasında efsane oldu; Good Will Hunting filminin senaryosuna ilham verdi.

Pratik etkisi

Simpleks algoritması bugün trilyon dolarlık endüstrilerin temelinde:

Hava taşımacılığı

Bir havayolu binlerce uçuşu, ekibi, ürünü planlar. United, Delta, American gibi şirketler her gün simpleks varyantları kullanarak çizelgeleri optimize eder.

Üretim planlama

Otomotiv, elektronik, tekstil — fabrika çizelgeleri, kaynak dağılımı simpleks ile.

Lojistik

UPS, FedEx, Amazon — milyonlarca paketi araçlara dağıtma. TSP'nin LP gevşetmeleri.

Enerji ve elektrik

Elektrik şebekelerinde elektrik üretim/dağıtım planlama.

Finans

Portföy optimizasyonu (kısıtlı yatırım kararları).

Tarım

Ürün ekim planlaması (en yüksek getiri için).

Karmaşıklık: "tipik vs en kötü"

Simpleks algoritması ilginç bir karmaşıklık özelliği gösterir:

• Pratikte: çok hızlı — polinom zamanda çalışır.
• Teorik olarak en kötü hal: üstel zaman alabilir (Klee-Minty örnekleri, 1972).

Yani algoritma "tipik" girdilerle uzun yıllar boyunca pratik bir devrim oldu; ama matematiksel olarak "polynomial" kanıtlanmadı.

Karmarkar algoritması (1984)

1984'te Narendra Karmarkar (Hint matematikçi, AT&T Bell Labs'ta) iç-nokta yöntemi geliştirdi. Bu yöntem polinom zamanda kesin çalışır.

Karmarkar'ın algoritması simpleksi geride bırakmadı ama büyük problemlerde çok hızlı. Modern LP çözücüleri simpleks + iç-nokta hibrit yaklaşımlar kullanır.

Modern uygulamalar: AI ile birleşim

2010'lardan itibaren makine öğrenmesi ve lineer programlama birleşmeye başladı:

• Yapay sinir ağlarının belirli katmanları LP ile çözülür.
• Reinforcement learning ödüllerinin maksimizasyonu LP gevşetmeleri kullanır.
• Robust optimization belirsizlik altında karar verme.

Modeller ve çözücüler

Modern LP çözücüler olağanüstü güçlü:

• CPLEX (IBM, ücretli)
• Gurobi (ticari)
• GLPK (açık kaynak)
• HiGHS (modern açık kaynak)

Bu çözücüler milyonlarca değişkenli LP problemlerini saniyeler içinde çözer.

"Köşeler dünyası"

Lineer programlama, modern endüstrinin sessiz mimarıdır. Bir uçak kalktığında, bir kargo yola çıktığında, bir fabrika gün başladığında — arka planda simpleks (veya türevleri) bir köşeden köşeye yürüyor, optimum kararı buluyor.

Dantzig'in 1947'deki sezgisi, bilgisayarların gerçek bir ortağı olmadan önce başladı. Bugün dünya çapında milyarlarca dolarlık karar her saniye simpleks algoritmasının matematiksel uzantıları ile alınıyor.

Bir Pentagon'lı planlama uzmanı, modern endüstriyel matematiğin en uygulamalı ve en yaygın algoritmasını yarattı.