Simpleks Yöntemi

Simpleks yöntemi, George B. Dantzig'in 1947'de geliştirdiği doğrusal programlama algoritmasıdır ve operasyonel araştırmanın temel algoritmik aracıdır. Çekirdek fikir: max c^T x s.t. Ax = b, x ≥ 0 standart formdaki LP'nin fizibil bölgesi dışbükey bir politop olup, dışbükey amaç optimumunu bir köşede (vertex) bulur; her köşe bir temel-fizibil çözüme (basic feasible solution, BFS) karşılık gelir — yani m temel değişken pozitif, n-m temel-olmayan değişken sıfır. Algoritma şöyle ilerler: (1) bir başlangıç BFS bul (büyük-M veya iki-fazlı yöntemle); (2) azaltılmış maliyetleri (reduced costs) c_j - c_B^T B^(-1) A_j hesapla; tüm temel-olmayan değişkenler için ≥ 0 ise mevcut BFS optimumdur; (3) negatif azaltılmış maliyetli bir değişkeni temele giren (entering) seç (Dantzig kuralı: en negatif), oran testi (minimum ratio test) ile temelden çıkan (leaving) değişkeni belirle, pivot uygula ve adım (2)'ye dön. Geometrik olarak politopun bir köşesinden komşu köşeye doğru hareket eder. Karmaşıklık: Klee ve Minty (1972) Klee-Minty küpü ile en kötü durumda 2^n iterasyon gerektirebileceğini gösterdi (üstel); buna karşın ortalama-durum ve düzlemeleştirilmiş (smoothed) analizi (Spielman ve Teng 2004) polinom olduğunu kanıtlar — bu yüzden pratikte son derece hızlıdır. Çeşitleri: (a) revize edilmiş simpleks (revised simplex) sparse-matrix saklama ile büyük problemlere uyarlanır; (b) dual simpleks (Lemke 1954) dual fizibilite üzerinden ilerler; (c) ağ simpleksi (network simplex) ulaşım ve atama problemlerini ağaç yapılarıyla saniyeler içinde çözer. Cycling — dejenere köşede sonsuz döngü riski — Bland kuralı (1977) veya leksikografik kuralla giderilir. Modern LP çözücülerinde simpleks hâlâ iç-nokta yöntemine paralel sunulur ve warm-start (sıralı LP çözümünde) ile özellikle MILP branch-and-cut bağlamında baskındır.