Big M & Two Phase Methods

Big M ve İki Aşamalı (Two Phase) Metotlar

Simplex metotu, doğrusal programlama (Linear Programming) problemlerinin çözümünde yaygın olarak kullanılan bir yöntemdir. Ancak bazı durumlarda, alışık olmadığımız kısıtlar veya yapılandırmalar nedeniyle standart Simplex metot doğrudan uygulanamaz. İşte bu noktada Big M ve İki Aşamalı (Two Phase) Metotlar devreye girer. Bu makalede, bu metotların ne olduğunu, neden ihtiyaç duyulduğunu ve nasıl uygulandığını birlikte inceleyeceğiz.

Alışılmadık (Unstructured) Doğrusal Programlama Problemleri

Standart simplex metotta, genellikle küçük eşitsizlikli ($\leq$) kısıtlarla karşılaşırız. Ancak bazı problemlerde büyük eşitsizlikli ($\geq$) kısıtlar bulunabilir. Örneğin:

$$\begin{align*} \text{Maksimize edin: } & 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 \end{align*}$$

Bu tür kısıtlar, standart simplex metotla doğrudan çözülemez çünkü başlangıç temel uygulanabilir çözüm (basic feasible solution) elde etmek zorlaşır.

Standart Forma Dönüştürme

Problemi standart forma dönüştürmek için, kısıtlardaki eşitsizlikleri eşitliğe çevirmemiz gerekir:

1. Büyük eşitsizlikli ($\geq$) kısıtlar için bir fazlalık değişkeni (surplus variable) çıkarırız.
2. Küçük eşitsizlikli ($\leq$) kısıtlar için bir eksiklik değişkeni (slack variable) ekleriz.
3. Eşitlik kısıtlarında değişiklik yapmayız.

Yukarıdaki problemi standart forma dönüştürelim:

$$\begin{align*} \text{Maksimize edin: } & z = -4x_1 + 3x_2 \\ \text{Kısıtlar: } & x_1 + 2x_2 - x_3 = 10 \\ & 3x_1 + 2x_2 + x_4 = 24 \\ & x_1, x_2, x_3, x_4 \geq 0 \end{align*}$$

Burada $x_3$ fazlalık değişkeni, $x_4$ ise eksiklik değişkenidir.

Yapay Değişkenlerin (Artificial Variables) Eklenmesi

Sorun şu ki, ilk tabloda temel değişken olarak kullanılacak birim vektörler elde edemiyoruz. Özellikle, $x_3$'ün katsayıları birim vektör oluşturmuyor. Bu durumda, yapay değişkenler ekleyerek tabloyu çözülebilir hale getiriyoruz:

$$\begin{align*} x_1 + 2x_2 - x_3 + x_5 = 10 \\ 3x_1 + 2x_2 + x_4 = 24 \end{align*}$$

Burada $x_5$ yapay bir değişkendir ve amacı başlangıç temel uygulanabilir çözümü elde etmektir.

Big M Metodu

Big M Metodu, yapay değişkenleri cezalandırarak onları çözümden çıkarmayı hedefler. Amaç fonksiyonuna yapay değişkenler için büyük bir ceza katsayısı ekleriz:

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

Burada $M$ çok büyük bir pozitif sayıdır. Bu sayede, optimizasyon sürecinde yapay değişkenlerin değeri sıfıra zorlanır.

Uygulama Adımları:

1. Problemi standart forma dönüştürün.
2. Yapay değişkenleri ekleyin ve amaç fonksiyonunda cezalandırın.
3. Simplex metotla çözümü bulun.
4. Eğer yapay değişkenlerin değeri sıfırsa, çözüme devam edin. Değilse, problem uygulanabilir değildir (infeasible).

İki Aşamalı (Two Phase) Metot

İki Aşamalı Metot, yapay değişkenleri kullanırken amaç fonksiyonunu değiştirmeden, ancak iki farklı aşamada çözümü bulmayı hedefler.

Aşama 1: Yapay Değişkenleri Minimize Etme

Yeni bir amaç fonksiyonu tanımlarız:

$$\text{Minimize edin: } W = x_5$$

Bu aşamada, yapay değişkenlerin toplamını minimize ederek onların sıfıra indirgenmesini hedefleriz.

Aşama 2: Orijinal Amaç Fonksiyonuna Dönüş

Eğer Aşama 1 sonucunda yapay değişkenler sıfıra indirgenebilirse, orijinal amaç fonksiyonuna dönerek problemi standart simplex metotla çözeriz.

Uygulama Adımları:

1. Aşama 1 için yapay amaç fonksiyonu tanımlayın ve Simplex metot uygulayın.
2. Eğer yapay değişkenlerin değeri sıfırsa, Aşama 2'ye geçin.
3. Orijinal amaç fonksiyonuyla Simplex metotu tekrar uygulayın.

Big M ve İki Aşamalı Metotların Karşılaştırılması

• Big M Metodu:

  • Tek aşamalıdır.
  • Büyük bir $M$ değeri seçmek gerektiğinden sayısal kararsızlıklara yol açabilir.
  • Hesaplaması daha hızlı olabilir, ancak dikkatli olunmalıdır.

• İki Aşamalı Metot:

  • İki ayrı aşamada çözüm bulunur.
  • Sayısal kararsızlık riski daha düşüktür.
  • Yapay değişkenlerin sıfıra indirilip indirilemeyeceği net olarak görülür.

Sonuç

Big M ve İki Aşamalı Metotlar, simplex metotla doğrudan çözülemeyen doğrusal programlama problemlerini çözmek için etkili yöntemlerdir. Her iki metot da yapay değişkenleri kullanarak başlangıç temel uygulanabilir çözümü elde etmeyi ve ardından bu yapay değişkenleri çözümden çıkarmayı hedefler. Hangi metodu seçeceğiniz, problemin yapısına ve kişisel tercihlerinize bağlıdır; ancak her iki yöntem de doğru uygulandığında size optimal çözümü sunacaktır.