SİMPLEKS ALGORİTMASI

Problemlerin çözümünde başvurulan yollardan birisi de problemin gerekliliklerinin ve ulaşılması istenen amacın (enbüyük kar, enküçük maliyet vb.) matematiksel ifadelerle gösterilmesidir. Ardından, eniyi değeri araştırılan bilinmeyenlerin, bu matematiksel ifadelerin oluşturduğu denklem seti yardımıyla çözümü aranır. Bu matematiksel yapılara Karar modeli denir.  

Doğrusal bağımsız vektörlerden oluşan, m denklem ve n değişkenin olduğu (mxn’lik ve m<n) bir sistemin çözümünde, diğer (n-m) tane değişken sıfır değerini almak üzere, ancak denklem sayısı (m) kadar değişkene değer bulunabilir. Örnek olarak iki denklem ve beş değişkenin olduğu bir sistemde, her seferinde üç değişkene sıfır değerini vererek, iki değişken için çözüm bulunabilir. Burada, sıfır değeri verilen değişkenlere temel dışı, değer alması için çözüme alınan değişkenlere ise temel değişken denir.

Temel dışı değişkenler sıfır iken temel değişkenler için bulunan çözüme temel çözüm denir. Bir temel çözümde tüm temel değişkenler sıfır veya sıfırdan büyük değer aldıysa bu çözüme bir temel uygun çözüm denir. 

Bir temel çözümde tüm temel değişkenler sıfır veya sıfırdan büyük değer aldıysa bu çözüme bir temel uygun çözüm denir ve bir temel uygun çözüm aynı zamanda bir uç nokta demektir.

Analitik yöntem, kısıtları eşitlik haline getirilmiş bir denklem sisteminin belirtilen şekilde tüm çözümlerini elde ederek içlerinden temel uygun çözüm (uç nokta) olanlarını bulmaktadır. Temel uygun çözüm olma özelliği sağlayanlar arasından amaç fonksiyonu değerini eniyileyen, problemin eniyi çözümünü verecektir.

Analitik yöntem, problemin uç noktası olmayan başka noktalarını da bulma ve işlem yükü sebepleriyle pratik değildir.

Simpleks Algoritması analitik yöntemin temellerini esas alan fakat temel ve temel olmayan değişkenlerin belirlenmesinden sonra, amaç fonksiyonu değeri iyileşecekse, bir uç noktadan diğerine geçen ardışık bir çözümleme tekniğidir.

Simpleks Algoritması, grafik ve analitik yöntemlerin uygulamadaki güçlüklerini taşımayan, ardışık sayısal çözüm tekniği sınıfında bir yöntemdir. Basitce izlediği yol, bir uç noktadan başlayarak amaca göre daha iyi çözüm verecek başka bir uç noktaya geçmek (eğer varsa) ve istenen yönde iyileşmenin olmadığı durumda da durmaktır.

Simpleks Algoritması ile problemin denklem sistemini çözen, uç nokta olsun olmasın tüm noktalarını bulmak gerekmediği gibi, sadece uç noktaların bile tümünün sınanmasına gerek kalmayabilmektedir. Algoritma, her adımda, uygun çözüm alanının bir uç noktasını bulup irdelemekte ve bu noktanın eniyi çözüm olup olamayacağını sınamaktadır. Nokta eniyi çözüm değilse, amaca göre daha iyi bir çözüm verecek izleyen uç noktayı bulur

Temel değişkenler, temel olmayan değişkenler cinsinden ifade edilir (kısıtlar yardımıyla temel değişkenler çözülür).

Kitabınızın 76. sayfası "Simplex tablo" bölümünü okuyunuz. 

Ardıştırma; bir çözümün eniyi çözüm olmaması halinde temele girecek ve çıkacak olan değişkenlere karar verme, temele girecek değişkenin tabloda kısıtlar bölümüne karşı gelen kısmındaki katsayılarının birim matrisin ilgili sütununa dönüştürülmesi ve x0 satırında karşı gelen değerinin sıfırlanması aşamalarından oluşur.

LINDO, LINGO, GAMS gibi, örnekleri verilebilecek bu tür yazılımların yanında, hemen her bilgisayarda hali hazırda bulunan çalışma tablosu programı Microsoft Excel’in çözücü (solver) modülü ile bile belirli büyüklükteki matematiksel modellere çözüm bulunabilmektedir.

Simpleks Algoritması’nda esas olan, verilen modelin amaç fonksiyonunu ve kısıtlarını, temel olmayan değişkenler cinsinden ifade etmektir. Böylece temel dışı değişkenler sıfır iken ortaya çıkan durum görülebilmiş olur. 

İşlemler, temel değişkenler için birim matrisi oluşturma (temelden çıkan değişkene karşı gelen sütunu yeni temele girecek sütun için oluşturma) ve amaç fonksiyonunu da temel olmayan değişkenler cinsinden ifade ederek, değerini daha iyiye götürecek bir temel dışı değişkenin olup olmadığını sınama şeklinde devam eder. 

Temele alınması halinde amaç fonksiyonu değerini daha iyiye götürecek değişkenin bulunmaması halinde eniyi çözüme erişilmiş demektir. Bu şekilde eniyilik koşullarının sağlanması, temel olmayan değişkenlere
x0
satırında karşı gelen tüm değişkenlerin enbüyükleme için pozitif, enküçükleme için ise negatif olması demektir.

Temele girecek değişken var iken, temelden çıkacak değişkenin bulunması aşamasında sağ taraf sabitlerinin temele girecek değişkenin bulunduğu sütundaki değerlere oranlanması aşamasında, temele girecek değişkenin kısıtlar kısmında altında yer alan tüm değerler sıfır veya sıfırdan küçük ise problemin sınırsız çözümü var demektir.

Temele girecek değişken var iken, temelden çıkacak değişkenin bulunması aşamasında sağ taraf sabitlerinin temele girecek değişkenin bulunduğu sütundaki değerlere oranlanması aşamasında, temele girecek değişkenin kısıtlar kısmında altında yer alan tüm değerler sıfır veya sıfırdan küçük ise problemin sınırsız çözümü var demektir. Temelde yer aldığı halde sıfır değerini alan değişken ise problemin dejenere çözümü olduğunu gösterir. 

2 tane doğrusal bağımsız denklem (m=2) ve 5 tane değişkenin (n=5) olduğu Ax=b şeklindeki bir denklem sisteminde bir çözümde 2 temel değişken yer alır. 

3. değişken temele alınmalıdır. 

2 tane doğrusal bağımsız denklem ve 5 tane değişkenin olduğu bir sistemde bir çözümde 3 temel dışı değişken yer alır.