Standart Simplex metodunun hangi kısıt tiplerinde başlangıç temel uygun çözümü (BFS) bulamadığını göreceğiz. Bu yetersizliği anlamak, Büyük-M metoduna neden ihtiyaç duyduğumuzu netleştirir.
Simplex algoritması her iterasyonda temel uygun çözüm (basic feasible solution — BFS) üzerinde hareket eder. Algoritmanın çalışabilmesi için başlangıçta geçerli bir BFS gerekmektedir.
Yalnızca $\leq$ kısıtları ve negatif olmayan sağ taraf değerlerinden oluşan bir problemde bu başlangıç BFS'i otomatik olarak elde edilir: her kısıta bir aylak (slack) değişken $s_i \geq 0$ eklenir ve başlangıç temel değişkenler olarak alınır.
Aylak değişkenler eklendiğinde başlangıç BFS: $s_1=10,\; s_2=14,\; x_1=x_2=0$ — hemen hazır, tüm değişkenler $\geq 0$.
Bir kısıt $\geq$ işaretliyse eşitliğe dönüştürmek için artık (surplus) değişken çıkarılır:
Şimdi başlangıçta $x_1 = x_2 = 0$ koysak:
$s_1 = -12 < 0$ — bu geçersiz bir temel çözümdür. Simplex, negatif değerli temel değişkenle başlayamaz. Başlangıç BFS yok!
Bir kısıt zaten eşitlik biçimindeyse ne aylak ne artık değişken eklenebilir:
$x_1 = x_2 = 0$ koyduğumuzda $0 \neq 8$ — kısıt sağlanmıyor. Yine geçerli bir başlangıç noktası yok.
| Kısıt Tipi | Standart Forma Dönüşüm | Başlangıç BFS | Sorun Var mı? |
|---|---|---|---|
| $\leq$ | $+ \; s_i$ (aylak değişken ekle) | $s_i = b_i \geq 0$ | ✓ Yok |
| $\geq$ | $- \; s_i$ (artık değişken çıkar) | $s_i = -b_i < 0$ ❌ | ✗ Var |
| $=$ | Değişiklik yok | Başlangıç değişkeni yok ❌ | ✗ Var |
Sorun özünde şu: $\geq$ ve $=$ kısıtlarında "tablo başlangıcında göz ile görülebilecek bir temel değişken" yok. Peki bu değişkeni biz yaratamaz mıyız?
İşte bu fikir bizi yapay (artificial) değişkenlere götürür. Her sorunlu kısıta bir yapay değişken $a_i \geq 0$ eklenir:
Ancak yapay değişkenin gerçek bir anlamı yoktur — sadece algoritmayı başlatmak için eklenir. Optimal çözümde $a_i = 0$ olmalıdır. Bu zorunluluğu sağlamak için amaç fonksiyonuna çok büyük bir ceza katsayısı $M$ eklenir — işte bu yüzden yönteme Büyük-M Metodu denir.
$M$'i "çok büyük bir sayı" olarak düşünün — milyar, trilyon, sonsuza yakın. Amaç fonksiyonu bu değişkeni sıfıra zorlamak için her şeyi yapar. Eğer optimal çözümde hâlâ $a_i > 0$ ise problem uygun çözümü olmayan bir problemdir.
$\leq$ kısıtı: aylak değişken ekle → doğrudan BFS var.
$\geq$ kısıtı: artık değişken çıkar + yapay değişken ekle → BFS yapay değişkenle kurulur.
$=$ kısıtı: sadece yapay değişken ekle → BFS yapay değişkenle kurulur.
Tüm yapay değişkenler amaç fonksiyonunda $M$ cezasıyla cezalandırılır.