Doğrusal Programlama (LP)

Doğrusal programlama, max c^T x s.t. Ax ≤ b, x ≥ 0 kanonik formundaki problem sınıfıdır; burada c ∈ R^n maliyet vektörü, A ∈ R^(m×n) katsayı matrisi, b ∈ R^m sağ taraf vektörü ve x ∈ R^n karar değişkenleri sürekli reel sayılardır. Fizibil bölge X = {x : Ax ≤ b, x ≥ 0} dışbükey bir politoptur ve dışbükey amaç bu küme üzerinde optimumunu bir köşe noktasında (basic feasible solution) bulur. Yöntemin doğuşu George B. Dantzig'in 1947'de geliştirdiği simpleks algoritmasıdır; Dantzig askeri planlama probleminden ('programming' terimi buradan gelir, modern bilgisayar yazılımı anlamında değil) yola çıkarak basic feasible solution kavramını formalize etmiştir. Dualite teorisi (von Neumann 1947) her LP'ye karşılık bir dual LP atar ve güçlü dualite teoremi optimum değerlerin (primal ve dual fizibil ise) eşit olduğunu söyler; gölge fiyatlar (shadow prices) dual değişkenlerden okunur. Algoritma karmaşıklığı: Klee ve Minty (1972) simpleksin en kötü durumda üstel olabileceğini gösterdi; Khachiyan (1979) ellipsoid yöntemiyle ilk polinom-zaman LP çözücüsünü kurdu (teorik); Karmarkar (1984) iç-nokta yöntemini sundu ve pratikte de polinom hız elde etti. Modern çözücüler simpleks (revize edilmiş) ve iç-nokta yöntemini birlikte sunar; presolve, sparse LU faktörizasyonu ve crash başlangıcıyla milyon-değişken problemleri saniyeler içinde çözer. Pratik uygulama alanları üretim planlama, karışım problemleri, ulaşım modelleri, finansman akış planlama ve diyet problemidir.