iki evreli simplex algoritması

• simplex algoritması kullanılarak çözüme ulaşma yöntemlerindendir. bir başkası için;
  (bkz: big m method)
  
  ilk evrede, amaç fonksiyonunu standart forma geçilirken eklenen yapay değişkenler oluşturur ve temel uygun çözüm bu amaç fonksiyonu için bulunur. ilk evre sonunda bu değişkenlerden kurtulma hedeflenir.
  
  ikinci evrede ise; yapay değişkenlerden kurtulmuş simplex tablosundan yola çıkarak en iyi çözüm aranır.
• ingilizcesi two phase method diye gecer literatürde.
• simpleks algoritması uygulanırken standart biçime dönüştürülen doğrusal karar modeli yapay değişken içeriyorsa uygulanacak iki yöntemden biridir. diğeri ise büyük m yöntemidir^**. başlık itibari ile konumuz iki evreli simplex algoritması yöntemi.
  
  tabi burada büyük m yöntemindeki m katsayısıyla uğraşılmayacağı için sadece z satırı yapay değişkenlerin katsayılarından oluşur. mesela problemimiz enbüyükleme (maksimizasyon) ise ilk tablomuzdaki z satısındaki bütün yapay değişken katsayıları "-1"dir. başlangıçta temel değişken olarak belirlenen yapay değişkenlerin altındaki katsayılar birim matrisi oluşturur. buradaki birim matristeki "1" katsayıları yukarıdaki z satırındaki yapay değişken katsayıları ile toplanarak değerleri "0" yapar. işte tam bu noktada başlangıç simpleks tablosu oluşturulmuş olur.
  
  bundan sonraki kısım big m method'a yazdığım kısım ile aynı:
  
  "
  daha sonra temel dışı değişkenler arasında en büyük katsayılı değişken temele girecek değişken olarak belirlenir. temelden çıkacak değişken ise aynı sütundaki değerlerin/katsayıların çözüm sütunundaki değerlere bölünmesiyle bulunur. bölme işleminden sonra en küçük değerin elde edildiği satırdaki yapay değişken temelden çıkartılır. işte tam olarak bu noktada başlangıç simpleks tablosunun oluşması beklenir. eğer başlangıç simpleks tablosu oluşturulamıyorsa ve temele girecek değişkenin olduğu sütundaki değişkenlerin katsayıları negatif ise problemin çözümü yoktur. ayrıca yapay değişken diğer bütün optimum koşullar sağlandıktan sonra pozitif değer alıyorsa yine çözüm yoktur. yani çözüm kümesi boş kümedir: ç. k. = {}
  
  bunların dışında diğer bütün optimum koşullar sağlanırken temel değişken "0" değeri alıyorsa bulunan çözüme dejenere çözüm denir.
  
  temele girecek değişken belli iken temelden çıkacak değişken belirlenemiyorsa (bölme işleminden sonra alternatif ve eşit değerler bulunuyorsa) bu sefer de alternatif çözüm vardır denir.
  
  simpleks algoritması gerek büyük m yöntemi olsun gerekse de iki evreli simplex algoritması yöntemi olsun optimum çözümü uygun çözüm alanının uç noktalarında gezerek arar. yani sayı düzleminde kesişen doğrularla beraber oluşan konveks çözüm alanındaki uç noktalarda gezerek optimizasyon probleminin en iyi değeri araştırılır. normalde aylarca sürecek çözüm işlemi simpleks algoritması ile çok çok kısaltılmış olur. örnek vermek gerekirse; 25 değişken ve 25 kısıttan oluşan bir doğrusal modelinin optimum çözümünü bulmak için 126.410.606.437.752 tane aday çözüm araştırılması gerekirken, simpleks ile yaklaşık 75 adımda (tabloda) optimum çözüm bulunabilir.
  "