🎯 Bu Sayfada Ne Öğreneceğiz?
Büyük-M tablosu kurulduktan sonra $z$ satırını nasıl güncelleyeceğimizi, pivot sütun ve satırını nasıl seçeceğimizi, pivot işlemini nasıl uygulayacağımızı ve optimal tabloda sonucu nasıl yorumlayacağımızı öğreneceğiz. Tüm adımları somut bir problem üzerinde izleyeceğiz.
Üzerinde Çalışacağımız Problem
Modül 01'de başlangıç tablosunu kurduğumuz problemi kullanıyoruz:
$$\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$$
Modül 01'den hatırlayalım — standart Büyük-M formuna getirdik:
$$\min\; w = 2x_1 + 3x_2 + 0 \cdot s_1 + Ma_1 + Ma_2$$
$$x_1 + x_2 - s_1 + a_1 = 4$$
$$2x_1 + x_2 \phantom{{}-s_1{}} + a_2 = 6$$
Temel değişkenler: $a_1 = 4,\; a_2 = 6$ | Temel dışı: $x_1=x_2=s_1=0$
Büyük-M Algoritması — 7 Adım
1
Başlangıç tablosunu yaz
Kısıtları satır, değişkenleri sütun olarak yerleştir. Sağ taraf ($b$) sütununu ekle. Temel değişkenleri ilk sütuna yaz.
2
$z$ (veya $w$) satırını güncelle — eliminasyon
Bazda olan her yapay değişken için: $z$ satırı ← $z$ satırı $- M \times$ (o değişkenin kısıt satırı).
Bu işlem, $z$ satırında bazda olan değişkenlerin katsayısını sıfırlar. Minimizasyonda $w$ satırı aynı şekilde güncellenir.
Neden? Simplex'in doğruluk koşulu: bazda olan her değişkenin $z$ satırındaki katsayısı $= 0$ olmalıdır.
3
Optimallik kontrolü
Minimizasyon: $w$ satırındaki tüm katsayılar $\geq 0$ ise optimal.
Maksimizasyon: $z$ satırındaki tüm katsayılar $\leq 0$ ise optimal.
Değilse devam et.
4
Pivot sütununu seç (giren değişken)
Minimizasyon: $w$ satırında en negatif katsayılı sütun.
Maksimizasyon: $z$ satırında en pozitif katsayılı sütun.
Eşitlik durumunda herhangi birini seç.
5
Pivot satırını seç (çıkan değişken) — Minimum Oran Testi
Her satır için $\theta = b_i / a_{ij}$ hesapla — yalnızca $a_{ij} > 0$ olan satırlar için.
En küçük $\theta$ değerini veren satır pivot satırıdır.
Eğer tüm $a_{ij} \leq 0$ ise problem sınırsız (unbounded).
6
Pivot işlemini uygula
Pivot elemanı: seçilen satır ve sütunun kesişimi.
a) Pivot satırını pivot elemana böl → pivot satırının yeni hali.
b) Diğer tüm satırlar (z satırı dahil): satır ← satır $-$ (o satırdaki pivot sütun katsayısı) × yeni pivot satırı.
Pivot sütununda yalnızca pivot satırı 1, diğerleri 0 olur.
7
Baz güncelle ve 3. adıma dön
Giren değişkeni pivot satırının baz değişkeni olarak yaz; çıkan değişken tablodan ayrılır. Adım 3'ten devam et.
Problemi Adım Adım Çözelim
Adım 1 — Başlangıç Tablosu
Başlangıç Ham tablo — w 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 |
| $w$ |
2 | 3 | 0 | $M$ | $M$ | 0 |
Adım 2 — $w$ Satırını Güncelle
Bazda $a_1$ ve $a_2$ var. $w$ satırındaki katsayıları sıfırlamak için:
$$\text{Yeni } w = w - M \cdot R_1 - M \cdot R_2$$
$$= [2,\;3,\;0,\;M,\;M \;|\; 0] - M[1,\;1,\;-1,\;1,\;0\;|\;4] - M[2,\;1,\;0,\;0,\;1\;|\;6]$$
$$= [2-3M,\;\;3-2M,\;\;M,\;\;0,\;\;0\;\;|\;\;-10M]$$
$w$ satırı güncellendi — artık $a_1$ ve $a_2$ katsayıları sıfır
Tablo 0 w satırı güncellenmiş — pivot seçimine hazır
| 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 |
| $w$ |
$2-3M$ | $3-2M$ | $M$ | 0 | 0 | $-10M$ |
Adım 3–4 — Optimallik Kontrolü ve Pivot Sütun Seçimi (İterasyon 1)
$w$ satırında negatif katsayılar var: $2-3M$ ve $3-2M$. $M$ büyük olduğundan her ikisi de negatiftir. En negatif: $2-3M$ (çünkü $3M > 2M$). Dolayısıyla $x_1$ sütunu pivot sütun.
Adım 5 — Minimum Oran Testi (İterasyon 1)
$a_1$ satırı
$\theta = 4 / 1 = 4$
$a_2$ satırı ← kazanan
$\theta = 6 / 2 = 3$ ✓ min
Pivot satırı: $a_2$ satırı. Pivot eleman: $a_{22} = 2$. $a_2$ çıkar, $x_1$ girer.
🔢
Pivot işlemi: $a_2$ satırını $2$'ye böl → yeni $R_2$. Ardından $a_1$ satırı ← $R_1 - 1 \times$ yeni $R_2$. $w$ satırı ← $w - (2-3M) \times$ yeni $R_2$.
Tablo 1 İterasyon 1 sonrası — $x_1$ bazda, $a_2$ çıktı
| Baz | $x_1$ | $x_2$ | $s_1$ | $a_1$ | $a_2$ | $b$ |
|---|
| $a_1$ |
0 |
1/2 |
−1 |
1 |
−1/2 |
1 |
| $x_1$ |
1 |
1/2 |
0 |
0 |
1/2 |
3 |
| $w$ |
0 |
$2-M/2$ |
$M$ |
0 |
$M/2 - 1$ |
$6 - 7M$ |
$w$ satırında hâlâ negatif katsayı var: $2 - M/2 < 0$ (büyük $M$ için). $x_2$ sütunu yeni pivot sütun.
Adım 5 — Minimum Oran Testi (İterasyon 2)
$a_1$ satırı ← kazanan
$\theta = 1 / (1/2) = 2$ ✓ min
$x_1$ satırı
$\theta = 3 / (1/2) = 6$
Pivot satırı: $a_1$ satırı. Pivot eleman: $1/2$. $a_1$ çıkar, $x_2$ girer.
🔢
Pivot işlemi: $a_1$ satırını $1/2$'ye böl (yani $2$ ile çarp) → yeni $R_1$. Ardından $x_1$ satırı ← $R_2 - (1/2) \times$ yeni $R_1$. $w$ satırı ← $w - (2-M/2) \times$ yeni $R_1$.
Tablo 2 İterasyon 2 sonrası — $x_1, x_2$ bazda, tüm yapay değişkenler çıktı
| Baz | $x_1$ | $x_2$ | $s_1$ | $a_1$ | $a_2$ | $b$ |
|---|
| $x_2$ |
0 | 1 | −2 | 2 | −1 | 2 |
| $x_1$ |
1 | 0 | 1 | −1 | 1 | 2 |
| $w$ |
0 | 0 | $2M-4$ | $4-3M$ | $M-2$ | 10 |
Adım 3 — Optimallik Kontrolü (Son)
$w$ satırındaki temel dışı değişkenlerin ($s_1, a_1, a_2$) katsayılarına bakalım. $M$ çok büyük olduğundan:
- $s_1$: katsayı $= 2M - 4 > 0$ ✓
- $a_1$: katsayı $= 4 - 3M < 0$ — ama $a_1$ artık gerçek bir değişken değil, devre dışı
- $a_2$: katsayı $= M - 2 > 0$ ✓
💡 Yapay Değişken Yorumu
Optimal tabloda $a_1$ ve $a_2$ sıfır değerinde ve bazda değil. Bu, gerçek bir uygun çözüm bulunduğunu gösterir. Yapay değişkenlerin $w$ satırındaki negatif katsayıları, onların bir daha baza giremeyeceğini güvence altına alır.
Optimal Çözüm
$$x_1 = 2, \quad x_2 = 2, \quad s_1 = 0$$
$$w^* = 2(2) + 3(2) = \mathbf{10}$$
Optimal minimum değer $w^* = 10$
✅ Kısıt Doğrulaması
1. kısıt: $x_1 + x_2 = 2 + 2 = 4 \geq 4$ ✓
2. kısıt: $2x_1 + x_2 = 4 + 2 = 6 = 6$ ✓
Optimal Tablo Nasıl Yorumlanır?
✅ Optimal Çözüm Bulundu
Optimal tabloda tüm yapay değişkenler sıfır değerinde ve bazda değil. Gerçek uygun çözüm mevcuttur.
❌ Çözüm Yok (Infeasible)
Optimal tabloda herhangi bir yapay değişken sıfırdan büyük ve bazda ise problem uygun çözümsüzdür.
Algoritmanın Özet Akışı
①Kısıtlara değişken ekle: $\leq$ → aylak | $\geq$ → artık + yapay | $=$ → yapay
②Amaç fonksiyonuna $M$ cezası ekle (min: $+M$, max: $-M$)
③$w/z$ satırını güncelle: her yapay değişken için eliminasyon satır işlemi uygula
④Optimallik kontrolü: tüm $w$ katsayıları $\geq 0$ mu? (min için) → evet ise dur
⑤Pivot sütun: en negatif $w$ katsayısı (min) veya en pozitif $z$ katsayısı (max)
⑥Pivot satır: minimum oran testi $\theta = b_i / a_{ij}$ ($a_{ij} > 0$)
⑦Pivot işlemi → baz güncelle → adım ④'e dön
⑧Optimal tabloda: tüm $a_i = 0$ → çözüm gerçek | herhangi $a_i > 0$ → çözümsüz
📌 Standart Simplex'ten Tek Fark
Büyük-M metodunun standart Simplex'ten tek farkı başlangıç tablosundadır: yapay değişkenler eklenir ve $z/w$ satırı başlangıçta güncellenir. Bundan sonrası tamamen aynı Simplex iterasyonlarıdır. Algoritmaların kalıbını biliyorsanız, Büyük-M ile çözmek yalnızca "daha uzun bir başlangıç hazırlığı" demektir.