Big M Method for Simplex Algorithm

Lineer programlama (LP) problemlerinin çözümünde Simpleks Metodu yaygın olarak kullanılır. Ancak bazı durumlarda, alışık olmadığımız kısıt türleriyle karşılaşırız. Özellikle büyük eşitlik ($\geq$) ve eşitlik ($=$) kısıtları, standard simpleks metoduyla doğrudan çözülemez. Bu noktada, Big M Metodu devreye girer ve bu tür problemleri çözmemize yardımcı olur.

Standart Form ve Alışık Olmadığımız Kısıtlar

Simpleks Metodu uygulayabilmek için LP problemini standart forma dönüştürmemiz gerekir. Standart formda tüm kısıtlar küçük eşitlik ($\leq$) şeklindedir ve tüm değişkenler sıfırdan büyük veya eşittir ($x_i \geq 0$).

Örnek bir LP problemi düşünelim:

$$\begin{align*} \text{Maksimize} \quad & Z = -4x_1 + 3x_2 \\ \text{Kısıtlar} \quad & x_1 + 2x_2 \geq 10 \\ & 3x_1 + 2x_2 \leq 24 \\ & x_1, x_2 \geq 0 \\ \end{align*}$$

Burada ilk kısıtımız $\geq$ şeklinde, yani alışık olmadığımız bir kısıt türü.

Büyük Eşitlik Kısıtlarının Standart Forma Dönüşümü

Büyük eşitlik kısıtlarını standart forma dönüştürmek için excess variable (artık değişken) ekleriz. Bu değişkenleri çıkararak kısıtı eşitliğe dönüştürürüz:

$$x_1 + 2x_2 - x_3 = 10 \quad \text{(} x_3 \geq 0 \text{)}$$

Küçük eşitlik kısıtlarına ise slack variable (fazla değişken) ekleriz:

$$3x_1 + 2x_2 + x_4 = 24 \quad \text{(} x_4 \geq 0 \text{)}$$

Ancak bu dönüşüm sonrası $x_3$ değişkeni temel (basic variable) olmaya uygun değildir, çünkü birim matrisin bir sütununu oluşturmaz. Bu durumda başlangıç baz çözümü elde edemeyiz.

Yapay Değişkenlerin (Artificial Variables) Tanıtılması

Bu sorunu aşmak için yapay değişkenler (artificial variables) ekleriz. İlk kısıta bir yapay değişken $x_5$ ekleyelim:

$$x_1 + 2x_2 - x_3 + x_5 = 10 \quad \text{(} x_5 \geq 0 \text{)}$$

Artık $x_5$ temel değişken olmaya uygundur, çünkü birim matrisin bir sütununu oluşturur.

Big M Metodu Nedir?

Big M Metodu, yapay değişkenlerin varlığını cezalandıran büyük bir $M$ katsayısı kullanarak problemi çözer. Amaç fonksiyonunu güncelliyoruz:

$$Z = -4x_1 + 3x_2 - Mx_5$$

Burada $M$ çok büyük bir pozitif sayı (örneğin $M = 10^6$). Bu yöntemle, yapay değişkenlerin çözümde yer almasını istemediğimizi vurgularız.

Big M Metodunun Adımları

1. Problemi Standart Forma Dönüştürün: Tüm kısıtlar eşitlik formatında ve tüm değişkenler sıfırdan büyük veya eşit olacak şekilde dönüştürülür.

2. Yapay Değişkenleri Ekleyin: Büyük eşitlik ve eşitlik kısıtlarına yapay değişkenler eklenir.

3. Amaç Fonksiyonunu Güncelleyin: Yapay değişkenleri cezalandırmak için amaç fonksiyonuna $-M$ katsayısıyla eklenir.

4. Simpleks Tablosunu Kurun: Güncellenmiş amaç fonksiyonu ve kısıtlarla başlangıç tablosu oluşturulur.

5. Simpleks Metodunu Uygulayın: Normal simpleks adımlarıyla çözüm bulunur.

6. Yapay Değişkenleri Kontrol Edin: Eğer çözümde yapay değişkenler sıfır değilse, orijinal problemin feasible (uygulanabilir) bir çözümü yoktur.

Örnek Uygulama

Amaç fonksiyonumuzu güncelleyelim:

$$Z = -4x_1 + 3x_2 - Mx_5$$

Simpleks tablosunu kurup işlemleri yaptığımızda, hedefimiz $x_5$'i temel değişkenlerden çıkarmak ve nihai çözümde $x_5 = 0$ olmasını sağlamaktır.

Big M Metodunun Avantajları ve Dezavantajları

• Avantajları:

  • Yapay değişkenlerle çalışırken doğrudan cezalandırma yöntemi kullanır.
  • Tek bir fazda çözüm bulunabilir.

• Dezavantajları:

  • $M$ değerinin çok büyük seçilmesi nümerik hesaplamalarda hatalara neden olabilir.
  • İnfeasible (uygulanamaz) çözümleri son aşamada tespit etmek zor olabilir.

Two-Phase Method (İki Aşamalı Metot) ile Karşılaştırma

Two-Phase Method, Big M Metoduna alternatif bir yaklaşımdır ve yapay değişkenleri kullanırken amaç fonksiyonunu iki aşamada ele alır.

Two-Phase Method'un Adımları

1. Faz 1:

   • Yapay değişkenlerin toplamını minimize eden geçici bir amaç fonksiyonu oluşturulur: $$\text{Minimize} \quad W = x_5$$
   • Simpleks Metodu uygulanarak yapay değişkenlerin toplamı minimize edilir.
   • Eğer minimum değer sıfır ise, feasible bir başlangıç çözümü bulunmuştur.

2. Faz 2:

   • Orijinal amaç fonksiyonuna geçilir.
   • Bulunan başlangıç çözümü ile Simpleks Metodu yeniden uygulanır.

Two-Phase Method'un Avantajları

• Faz 1 sonunda, problem feasible değilse hemen tespit edilir.
• Nümerik hesaplama hataları azaltılır çünkü büyük bir $M$ değeri kullanılmaz.

Sonuç

Big M Metodu, Simpleks Metodunda alışık olmadığımız kısıtları ve yapay değişkenleri ele almak için etkili bir yöntemdir. Yapay değişkenleri cezalandırarak, çözümde yer almamalarını sağlarız. Ancak, büyük $M$ değerleri nümerik sorunlara yol açabileceğinden, bazı durumlarda Two-Phase Method tercih edilebilir. Her iki yöntem de, LP problemlerinin çözümünde esneklik sağlayarak, daha geniş bir kısıt kümesiyle çalışmamıza olanak tanır.