Simpleks Yöntemi

Doğrusal programlama kavramı ve simpleks adıyla bilinen çözüm yöntemi George Dantzig tarafından bulunmuştur. 

Simpleks yönteminin ilk adımı probleme ait doğrusal modelin bir denklemler sistemine çevrilmesidir.

Doğrusal programda (n > m) değişken sayısının denklem sayısından fazla olduğu anlamına gelir. 

Sıfıra eşitlenen ve dolayısıyla çözümde sıfır değeri alanlar değişkenler, temel dışı değişkenler olarak adlandırılır.

Eğer iki uç nokta, uygun çözüm alanına ait bir doğru parçasıyla birbirine bağlanabiliyor ise bu uç noktalar birbirinin komşuluğunda yer almaktadır. Tüm değişkenleri arasından yalnızca bir tanesi aynı değeri alan uç nokta çözümleri birbirinin komşuluğundadır. 

Simpleks yönteminde ardışık yordam ile sonuca ulaşmak için her yinelemede hedefe daha yakın bir değer elde etmek amaçlanır. 

Denklemler sisteminde x₁’in katsayılarına ait vektörel gösterimin (0, 1, 0) olabilmesi için uygulanabilecek cebirsel işlemler;

-   Bir denklemin sıfırdan farklı bir sayıyla çarpılması veya bu sayıya bölünmesi ya da
- Bir denklemin, çarpılmış veya bölünmüş diğer bir denklemle toplanması veya bu denklemden çıkarılmasıdır. 

Başlangıç temel uygun çözümünü elde edebilmek için kullanılan kukla değişkenlere, yapay değişkenler denir. Başlangıçta temel değişken olarak çözümde yer alan bu değişkenler, ardıştırma sürecinde temelden çıkar. Yapay değişkenler negatif olmama kısıtlarını sağlarlar ve problemin çözümünde fiziksel bir anlamları bulunmamaktadır.

Yapay değişkenlerin denklemlerde standart olarak M ile gösterildiği, temelden çıkmalarını kesin kılmak için Z değerini kötüleştirecek yönde çok büyük bir katsayıyla birlikte amaç fonksiyonuna ilave edildiği yönteme, Büyük M Yöntemi denir.  

Bu denklemde, temel dışı değişkenler arasında negatif katsayıya sahip olanlar s₁ ve x₁’dir. Bu değişkenlerden x₁’in katsayısı negatif olarak daha büyüktür. Bu nedenle temel giren değişken x₁ olarak belirlenir.

Bu fonksiyonda x₂ ve s₁ negatif katsayılara sahip olduklarından, sıfırdan büyük değer almaları halinde Z değerini iyileştiremezler. Bu nedenle temel uygun çözüm (10, 0, 0, 42) en iyi çözümdür. Z’nin alabileceği en iyi değer ise 60’tır.

Soruda verilen denklemlere göre s₂'nin değeri 42'dir. 

Verilen denklemde en büyük negatif katsayıya sahip temel dışı değişken x₂'dir. 

Köşegen elemanları 1 diğer elemanları 0 olan bir kare matrise, birim matris denir. 

Simpleks tablosundaki temel değişkenlere ait katsayıların birim matris oluşturması,her bir temel değişkenin sadece bir denklemde yer alması ve her birinin katsayısının 1’e eşit olması, bu tablonun en iyilik sınamasına hazır olduğunu gösterir. 

Simpleks tablosunda anahtar satırı belirleme adımları şunlardır: 

1. Anahtar sütundaki pozitif sayıları ve bulundukları satırların belirlenmesi,

2. Belirlenen satırlardaki sağ taraf sabitinin aynı satır için belirlenen sayıya bölünmesi,

3. Bölümler arasındaki en küçük oranın belirlenmesi ve

4. En küçük orana sahip satırın anahtar satır olarak saptanması.

Anahtar satır ile anahtar sütunun kesişimindeki değer anahtarı sayı olarak adlandırılır. 

Simpleks yönteminde alternatif tablo kullanıldığında temelden çıkan değişkeni belirlemek için en küçük oran testi uygulanır. 

Gerçek hayata dair uygulamalarda modeller, örneklemlerde kullanılanlardan çok daha büyük olabilmektedir. Bu boyutlardaki bir modelin çözümü için harcanacak çaba, çok daha fazladır. Simpleks yöntemi, daha iyi amaç fonksiyonu değerlerine ulaşacak şekilde uç noktaların izini süren bir yordam kullanarak, cebirsel yöntemle harcanacak çabayı azaltmaktadır. Tercih edilmesindeki üstünlük de buradan gelir. 

Temelden çıkan değişkeni belirlemek için daha kısa bir yöntem olarak; denklemler sistemindeki sağ taraf sabitlerini, aynı denklemdeki temel giren değişkenin (x2) katsayısına
bölmek mümkündür.