Büyük-M Yöntemi Nedir?

⊞ Tüm Modüller ← Modül 00: Neden Büyük-M? Modül 02: Algoritma →

🎯 Bu Sayfada Ne Öğreneceğiz?

$M$ sabitinin ne anlama geldiğini, kısıt tipine göre hangi değişkenlerin eklendiğini, amaç fonksiyonunun nasıl dönüştürüldüğünü ve başlangıç Büyük-M tablosunun nasıl kurulduğunu öğreneceğiz.

$M$ Sabiti Nedir?

$M$, pozitif ve çok büyük bir sayıyı temsil eden sembolik bir sabittir. "Sonsuz büyük" olarak düşünebilirsiniz — pratikte probleminizin katsayılarından en az birkaç kat büyük seçilir (örneğin katsayılar tek haneli ise $M = 1000$ yeterlidir).

Büyük-M yönteminin tek yaptığı şey: gerçek çözümde var olmaması gereken yapay değişkenleri amaç fonksiyonunda ağır biçimde cezalandırmaktır.

💡 Sezgi

Minimizasyon probleminde $+Ma_i$ eklemek, algoritmanın $a_i$'yi sıfıra indirmek için her şeyi yapmasını sağlar — çünkü $a_i > 0$ tutmak amaç değerini astronomik biçimde artırır. Maksimizasyonda ise $-Ma_i$ eklenir, $a_i > 0$ tutmak bu sefer amaç değerini çok düşürür.

Kısıt Tipine Göre Değişken Ekleme Kuralları

Büyük-M metodunun kalbi bu kurallardır. Her kısıt tipine farklı muamele edilir:

≤ Küçük Eşit Kısıt

Yalnızca aylak (slack) değişken $s_i \geq 0$ eklenir. Başlangıç BFS için yapay değişken gerekmez.

$$a_1 x_1 + a_2 x_2 \leq b$$ $$\downarrow$$ $$a_1 x_1 + a_2 x_2 + s_i = b$$ Temel değişken: $s_i = b \geq 0$ ✓

≥ Büyük Eşit Kısıt

Artık (surplus) değişken $s_i$ çıkarılır, yapay değişken $a_i$ eklenir.

$$a_1 x_1 + a_2 x_2 \geq b$$ $$\downarrow$$ $$a_1 x_1 + a_2 x_2 - s_i + a_i = b$$ Temel değişken: $a_i = b \geq 0$ ✓

= Eşitlik Kısıtı

Ne aylak ne artık değişken eklenir; yalnızca yapay değişken $a_i$ eklenir.

$$a_1 x_1 + a_2 x_2 = b$$ $$\downarrow$$ $$a_1 x_1 + a_2 x_2 + a_i = b$$ Temel değişken: $a_i = b \geq 0$ ✓

Kısıt	Eklenen Değişken(ler)	Başlangıç Temel Değ.	Amaç Fon. Cezası
$\leq$	$+s_i$ (aylak)	$s_i = b_i$	Yok
$\geq$	$-s_i$ (artık) + $+a_i$ (yapay)	$a_i = b_i$	$+Ma_i$ (min) veya $-Ma_i$ (max)
$=$	$+a_i$ (yapay)	$a_i = b_i$	$+Ma_i$ (min) veya $-Ma_i$ (max)

Amaç Fonksiyonunun Dönüştürülmesi

Yapay değişkenler kısıtlara eklendikten sonra amaç fonksiyonu da güncellenir. Kural basittir:

✅ MAKSİMİZASYON PROBLEMİ

Her yapay değişken için $-Ma_i$ terimi eklenir. Bu, $a_i > 0$ olduğunda amaç değerini çok düşürür ve algoritmanın $a_i$'yi bazdan çıkarmasını zorunlu kılar.

\max\; z = c_1 x_1 + c_2 x_2 \;{\color{#fb7185}-\; Ma_1 - Ma_2 - \cdots}

✅ MİNİMİZASYON PROBLEMİ

Her yapay değişken için $+Ma_i$ terimi eklenir. Bu, $a_i > 0$ olduğunda amaç değerini çok yükseltir.

\min\; w = c_1 x_1 + c_2 x_2 \;{\color{#fbbf24}+\; Ma_1 + Ma_2 + \cdots}

Tam Bir Örnek: Başlangıç Tablosunu Kurmak

Aşağıdaki problemi ele alalım ve Büyük-M başlangıç tablosunu adım adım kuralım:

$\min\; w = 2x_1 + 3x_2$$ $$\text{k.k.}\quad x_1 + x_2 \geq 4, \quad 2x_1 + x_2 = 6, \quad x_1,x_2 \geq 0$$ 1. kısıt: $\geq$  |  2. kısıt: $=

1. kısıtı standart forma getir ($\geq$)

Artık değişken $s_1$ çıkar, yapay değişken $a_1$ ekle:

$$x_1 + x_2 - s_1 + a_1 = 4$$

2. kısıtı standart forma getir ($=$)

Yalnızca yapay değişken $a_2$ ekle:

$$2x_1 + x_2 + a_2 = 6$$

Amaç fonksiyonunu güncelle (minimizasyon)

Her yapay değişken için $+M$ cezası eklenir:

\min\; w = 2x_1 + 3x_2 + 0 \cdot s_1 + Ma_1 + Ma_2

Başlangıç BFS'i yaz

Temel değişkenler $a_1 = 4$, $a_2 = 6$; temel dışı değişkenler $x_1 = x_2 = s_1 = 0$.

Başlangıç Büyük-M tablosunu oluştur

$z$ satırı kurulurken yapay değişkenler bazda olduğundan $z$ satırının güncelleştirilmesi (eliminasyon) gerekir — bunu Modül 02'de göreceğiz.

Başlangıç Büyük-M Tablosu (ham — z satırı henüz güncellenmedi)

Baz	$x_1$	$x_2$	$s_1$	$a_1$	$a_2$	$b$
$a_1$	1	1	−1	1	0	4
$a_2$	2	1	0	0	1	6
$z$	2	3	0	$M$	$M$	0

⚠️ Dikkat: Z Satırı Güncellenmeli

Başlangıç tablosunda $a_1$ ve $a_2$ bazda olduğu hâlde $z$ satırındaki katsayıları henüz sıfır değil ($M$). Simplex algoritması, bazda olan değişkenlerin $z$ satırı katsayısının sıfır olmasını gerektirir. Bu nedenle tabloya başlamadan önce $z$ satırı üzerinde satır işlemleri yapılmalıdır. Bunu bir sonraki modülde adım adım göreceğiz.

Özet: Büyük-M Tablosunu Kurma Adımları

①

Her kısıtın tipini belirle: $\leq$, $\geq$, $=$

Sağ taraf $b_i$ her zaman $\geq 0$ olmalı. Negatifse kısıtın iki tarafını $-1$ ile çarp ve işareti tersine çevir.

②

Kurala göre değişkenleri ekle / çıkar

$\leq$: $+s_i$ | $\geq$: $-s_i + a_i$ | $=$: $+a_i$

③

Amaç fonksiyonuna $M$ cezası ekle

Minimizasyon: $+Ma_i$ | Maksimizasyon: $-Ma_i$

④

Başlangıç tablosunu yaz

Temel değişkenler: yapay ve aylak değişkenler. Temel dışı değişkenler: $x_j = 0$.

⑤

$z$ satırını güncelle (eliminasyon)

Bazda olan her yapay değişken için satır işlemi yapılarak $z$ satırındaki katsayılar sıfırlanır. Bundan sonra standart Simplex adımları başlar.

📌 Özet

$M$: çok büyük pozitif sayı — yapay değişkenlere verilen ceza katsayısı.

Yapay değişken ($a_i$): yalnızca başlangıç BFS'i oluşturmak için eklenir; gerçek bir fiziksel anlamı yoktur.

Artık değişken ($s_i$): $\geq$ kısıtlarında "fazlayı" temsil eder; negatif olamaz.

Kural: $\leq$ → aylak | $\geq$ → artık + yapay | $=$ → yapay

← Modül 00: Neden Büyük-M? Modül 02: Adım Adım Algoritma →