big m method

• yöneylem araştırmasında simplex algoritması ile çözüme ulaşma yöntemlerinden biridir.
  
  kanonik^* formdan standart forma geçirilen kısıtlardan, gevşek değişken^*lerin bulunmayanlarına yapay değişkenlerin eklenmesiyle çözüme gidilmeye çalışılır. yapay değişkenlerin çözüme etki etmemesi için, çözümde bu değişkenlerin 0 olmasının sağlanması gerekmektedir. bunu yapmak için amaç fonksiyonuna m^* olarak göstereceğimiz büyük bir katsayı ile eklenir ve optimum çözümde sistemin bu değişkenleri 0 yapması sağlanır.
• eğer amaç fonksiyonu minimizasyon ise (+m) maksimizasyon ise (-m) eklenerek çözüme gidilir. kısıtlara eklenecek gevşek (slack = s) değerler ise kısıt ">=" ise (-s), kısıt "=<" ise (+s) olmalıdır.
  eğer optimal tablo elde edildiği halde pozitif yapay değişken içeriyorsa, o problem çözümsüzdür.
• en iyi ogrenilebilecek tuturiallardan bir tanesi (ingilizce): http://youtu.be/y7mm8ibremy
• hintli abimiz de iyi anlatıyor.
  https://www.youtube.com/watch?v=hskpohtako0 burdan bakılabilir max çözümüne.
• türkçe: (bkz: büyük m yöntemi)
  doğrusal optimizasyon problemi için kurulan model aylak/gevşek^* değişken dışında yapay değişken gerektiriyorsa çözüm için başvurulacak yöntemlerden bir tanesidir big m method. diğeri ise iki evreli simplex algoritmasıdır. başlık itibari ile konumuz büyük m yöntemi.
  
  model standart biçime dönüştürülürken amaç fonksiyonuna eklenen, yapay değişken katsayısı olan m (- veya + ile) parametresine simplex tablosunda karşılık gelen ve birim matrisi oluşturan temel değişkenlerin (ki bunlar genellikle yapay değişkenler olur) bulunduğu satır ±m değeriyle çarpılarak z satırıyla toplanır. bu işlemler sonucunda z satırındaki yapay değişkenlerin katsayıları "0" olur. bu da yapay değişkenlerin amaç fonksiyonunun değerini değiştirmesini engellemek için yapılır. amaç yapay değişkene çok büyük bir değer atayarak onun temelden çıkmasını sağlamaktır. bu işlemler başlangıç simpleks tablosunu oluşturmak için yapılır.
  
  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.