Simpleks algoritması

Karşılık gelen lp'yi çözmek için simpleks yöntemiyle alınan olası bir yolla (kırmızı) birlikte doğrusal bir programlama politopunu gösterir.

Simpleks algoritması, doğrusal programlama problemlerinde optimum çözümü pratik olarak bulmak amacıyla George Dantzig tarafından 1947 yılında geliştirilen bir algoritmadır.

Bu algoritma kısıtlamalardan ortaya çıkan düzeyleri birçok değişirli polihedron (iki değişkenli problemde "uygunluk alanı") olarak görmekte ve bu polihedronda kesişme noktalarını yani polihedron köşelerini (iki değişkenli problemde kısıtlama çizgilerinin kesişme noktalarını) birer mümkün çözüm olarak görmektedir. Şayet kısıtların tanımladığı polihedron boş değilse (lineer eşitsizlik sisteminin çözüm kümesinin kardinalitesi 0'dan büyükse) köşelerden birisi her zaman optimal çözüm yahut optimal çözümlerden biridir.

Simpleks algoritması bir köşeden başlayıp bu köşeyi tayin eden kenarlar takip edilerek amaç fonksiyonun iyileşmesini sağlayan kenarlar teşhis edilmekte; bunlardan amaç fonksiyonuna en iyi sonuç çıkaracak kenar takip edilip bir diğer polihedron köşesi bulunmaktadır. Bu yeni bulunan polihedron köşesi de aynı yöntem kullanılarak daha iyi bir başka köşeye gidebilme imkânı aranmaktadır. Eğer elde bulunan bir polihedron köşesinden daha iyi amaç sonuç sağlayan bir köşeye gitme imkânı yoksa, bu son köşe optimum çözum olarak kabul edilmektedir.

Genel aktarım

Daha fazla bilgi: Doğrusal programlama

Doğrusal programlamada simpleks algoritması aşağıda gösterilen standart formda uygulanır:

En yüksek büyüklüğe çıkar

$\mathbf {c^{T}} \cdot \mathbf {x}$

Aşağıdaki koşullar altında

$\mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,x_{i}\geq 0$

$x=(x_{1},\,\dots ,\,x_{n})$ problemin değişkenleri, $c=(c_{1},\,\dots ,\,c_{n})$ amaç fonksiyonunun sabitleri, A bir p×n matrisi ve $b=(b_{1},\,\dots ,\,b_{p})$, $x_{i}\geq 0$ koşulu ile sabitler.