Big M Method

Simpleks Metodunda Alışık Olmadığımız LP'lerin Çözümü ve Big M Metodu

Lineer programlama (LP) problemlerini çözerken genellikle simpleks metodu kullanırız. Ancak bazı durumlarda alışık olmadığımız LP'lerle karşılaşırız; örneğin, maksimize etme problemlerinde büyük eşittir ($\geq$) kısıtlarının bulunması gibi. Bu tür kısıtlar, standard formata dönüştürülürken ve başlangıç çözümünü bulurken zorluklar yaratır.

Standart Forma Dönüşüm ve Sorunlar

Maksimize etme problemlerinde standart olarak kısıtlarımız küçük eşittir ($\leq$) şeklindedir. Ancak büyük eşittir ($\geq$) kısıtlarıyla karşılaştığımızda, standart forma dönüştürmek için bazı adımlar izlememiz gerekir:

• Büyük eşittir ($\geq$) kısıtlarında artık değişken (surplus variable) çıkarırız.
• Küçük eşittir ($\leq$) kısıtlarında ise sıkıştırma değişkeni (slack variable) ekleriz.

Örneğin, elimizde aşağıdaki LP olsun:

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

Standart forma dönüştürürken:

1. İlk kısıtımız büyük eşittir ($\geq$) olduğundan, bir artık değişken çıkarırız:

   $$x_1 + 2x_2 - x_3 = 10$$

2. İkinci kısıtımız küçük eşittir ($\leq$) olduğundan, bir sıkıştırma değişkeni ekleriz:

   $$3x_1 + 2x_2 + x_4 = 24$$

3. Tüm değişkenlerin pozitif olduğunu belirtiriz:

   $$x_1, x_2, x_3, x_4 \geq 0$$

Başlangıç Temel Uygun Çözümün Bulunmasındaki Zorluk

Simpleks metodu uygulamak için başlangıçta bir temel uygun çözüm (basic feasible solution) bulmamız gerekir. Ancak standart formata dönüştürdüğümüzde, artık değişkenlerin katsayı matrisinde birim matris oluşturmadığını görürüz. Bu nedenle, başlangıç temel çözümü elde edemeyiz.

Örneğin, yukarıdaki kısıtlarda $x_3$'ün katsayıları birim matris oluşturmuyor:

• $x_3$'ün katsayıları: $[-1, 0]$

Bu durumda, $x_3$'ü temel değişken olarak seçemeyiz.

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

Bu sorunu aşmak için denklem sistemine yapay değişkenler (artificial variables) ekleriz. Yapay değişkenler, başlangıç temel uygun çözümü elde etmemizi sağlar.

Yukarıdaki örnekte, ilk kısıta bir yapay değişken $x_5$ ekleyelim:

$$x_1 + 2x_2 - x_3 + x_5 = 10$$

Artık $x_5$ temel değişken olarak seçilebilir, çünkü katsayısı 1 ve diğer denklemlerde katsayısı 0.

Big M Metodu ile Yapay Değişkenlerin Ele Alınması

Yapay değişkenler problemi çözmek için kullanışlıdır, ancak nihai çözümde yer almamaları gerekir. Bunun için Big M Metodu kullanılır. Bu metotta, yapay değişkenlere nesnel fonksiyonda (objective function) büyük bir ceza katsayısı atanır.

Ceza Katsayısının Eklenmesi

Nesnel fonksiyonu yeniden tanımlayalım, yapay değişken için büyük bir negatif ceza katsayısı ($-M$) ekleyelim:

$$\text{Maksimize} \quad Z = -4x_1 + 3x_2 - M x_5$$

Burada $M$ çok büyük bir pozitif sayıdır. Bu şekilde, yapay değişkenin çözümde yer alması durumunda nesnel fonksiyon değeri büyük ölçüde azalacaktır.

Simpleks Tablosunun Oluşturulması

Simpleks tablosunda yapay değişken de yer alır ve standart simpleks algoritması uygulanır. Amaç, iterasyonlar sonucunda yapay değişkenin değeri sıfıra indirgenerek bazisten çıkarılmasıdır.

Feasibility Kontrolü

Eğer çözüm sonunda yapay değişkenin değeri sıfır değilse, bu problemin uygun bir çözümü olmadığını (infeasible) gösterir.

Two Phase Metodu ile Yapay Değişkenlerin Ele Alınması

Two Phase Metodu, yapay değişkenlerin ele alınmasında alternatif bir yaklaşımdır. Bu metot, problemi iki aşamada çözer:

Faz 1: Yapay Değişkenlerin Minimizasyonu

İlk aşamada, orijinal nesnel fonksiyon yerine yapay değişkenlerin toplamını minimize ederiz:

$$\text{Minimize} \quad W = x_5$$

Bu adımda amaç, yapay değişkenlerin toplamını sıfıra indirgemektir. Simpleks metodu uygulanarak yapay değişkenlerin bazisten çıkarılması sağlanır.

Faz 2: Orijinal Problemin Çözümü

Eğer Faz 1 sonunda yapay değişkenlerin değeri sıfır ise, problem uygun bir çözüme sahiptir. İkinci aşamada orijinal nesnel fonksiyona geri dönülür ve simpleks metodu uygulanarak problem çözülür.

Big M ve Two Phase Metotlarının Karşılaştırılması

• Big M Metodu'nda, yapay değişkenler nesnel fonksiyona büyük bir ceza katsayısı ile eklenir.

  • Avantajı: Tek aşamada çözüm sağlar.
  • Dezavantajı: $M$ değerinin çok büyük seçilmesi gerekir; bu da sayısal kararlılık sorunlarına yol açabilir.

• Two Phase Metodu'nda, problem iki aşamada çözülür.

  • Avantajı: $M$ değeri kullanmadan yapay değişkenlerin bazisten çıkarılmasını sağlar.
  • Dezavantajı: İki aşamalı olduğundan hesaplama süresi biraz daha uzun olabilir.

Özet ve Sonuç

Alışık olmadığımız LP'lerin çözümünde, standart simpleks metoduna doğrudan uygulanamaz. Yapay değişkenler ekleyerek başlangıç temel uygun çözümü elde ederiz. Big M Metodu ve Two Phase Metodu, yapay değişkenlerin problemin çözümüne olan etkilerini ortadan kaldırmak için kullanılan iki temel yaklaşımdır. Her iki metodun da amacı, yapay değişkenlerin bazisten çıkarılarak orijinal problemin doğru ve uygun bir çözümünün bulunmasını sağlamaktır.