🎯 Bu Örnekte Ne Yapacağız?
Yalnızca $\geq$ kısıtları içeren bir minimizasyon problemini baştan sona Büyük-M metoduyla çözeceğiz. Her adımı tabloda göstereceğiz.
$$\min\; w = 4x_1 + x_2$$
$$\text{k.k.}$$
$$3x_1 + x_2 \geq 6$$
$$x_1 + x_2 \geq 4$$
$$x_1,\; x_2 \geq 0$$
Adım 1 — Standart Büyük-M Formuna Getirme
Her iki kısıt da $\geq$ tipinde. Kurala göre her kısıta artık değişken çıkarılır, yapay değişken eklenir:
$$3x_1 + x_2 - s_1 + a_1 = 6$$
$$x_1 + x_2 - s_2 + a_2 = 4$$
Minimizasyon olduğundan her yapay değişken amaç fonksiyonuna $+M$ ile eklenir:
$$\min\; w = 4x_1 + x_2 + 0\cdot s_1 + 0\cdot s_2 + Ma_1 + Ma_2$$
Başlangıç BFS: $a_1 = 6,\; a_2 = 4,\; x_1=x_2=s_1=s_2=0$.
Adım 2 — Başlangıç Tablosu ve $w$ Satırı Güncellemesi
Ham w satırı güncellenmeden önce
| Baz | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $a_1$ | 3 | 1 | −1 | 0 | 1 | 0 | 6 |
| $a_2$ | 1 | 1 | 0 | −1 | 0 | 1 | 4 |
| $w$ | 4 | 1 | 0 | 0 | $M$ | $M$ | 0 |
Bazda $a_1$ ve $a_2$ var. $w$ satırı güncellemesi:
$$w \leftarrow w - M \cdot R_1 - M \cdot R_2$$
$$[4,1,0,0,M,M\,|\,0] - M[3,1,-1,0,1,0\,|\,6] - M[1,1,0,-1,0,1\,|\,4]$$
$$= [4-4M,\;\; 1-2M,\;\; M,\;\; M,\;\; 0,\;\; 0\;\;|\;\; -10M]$$
Tablo 0 w satırı güncellenmiş — iterasyona hazır
| Baz | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $a_1$ |
3 | 1 | −1 | 0 | 1 | 0 | 6 |
| $a_2$ |
1 | 1 | 0 | −1 | 0 | 1 | 4 |
| $w$ |
$4-4M$ | $1-2M$ | $M$ | $M$ | 0 | 0 | $-10M$ |
İterasyon 1
Pivot Sütun Seçimi
$w$ satırındaki en negatif değer: $4-4M$ ($x_1$ sütunu) ve $1-2M$ ($x_2$ sütunu). $M$ büyük olduğundan $4-4M < 1-2M$ (fark: $3-2M < 0$). Pivot sütun: $x_1$.
Minimum Oran Testi
$a_1$ satırı ← kazanan
$\theta = 6/3 = 2$ ✓ min
$a_2$ satırı
$\theta = 4/1 = 4$
Pivot eleman: $a_1$ satırı, $x_1$ sütunu → değer $= 3$. $a_1$ çıkar, $x_1$ girer.
🔢
Pivot işlemi: $R_1 \leftarrow R_1 / 3$. $R_2 \leftarrow R_2 - 1 \cdot R_1^*$. $w \leftarrow w - (4-4M) \cdot R_1^*$.
Tablo 1 $x_1$ girdi, $a_1$ çıktı
| Baz | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $x_1$ |
1 | 1/3 | −1/3 | 0 | 1/3 | 0 | 2 |
| $a_2$ |
0 | 2/3 | 1/3 | −1 | −1/3 | 1 | 2 |
| $w$ |
0 |
$1/3 - 2M/3$ |
$4M/3 - 4/3$ |
$M$ |
$4/3 - M/3$ |
0 |
$8 - 2M$ |
$w$ satırında hâlâ negatif katsayı: $1/3 - 2M/3 < 0$ ($x_2$ sütunu). Devam.
İterasyon 2
Pivot Sütun: $x_2$
Minimum Oran Testi
$x_1$ satırı
$\theta = 2 / (1/3) = 6$
$a_2$ satırı ← kazanan
$\theta = 2 / (2/3) = 3$ ✓ min
Pivot eleman: $a_2$ satırı, $x_2$ sütunu → değer $= 2/3$. $a_2$ çıkar, $x_2$ girer.
🔢
Pivot işlemi: $R_2 \leftarrow R_2 \times (3/2)$. $R_1 \leftarrow R_1 - (1/3) \cdot R_2^*$. $w \leftarrow w - (1/3 - 2M/3) \cdot R_2^*$.
Tablo 2 $x_2$ girdi, $a_2$ çıktı — tüm yapay değişkenler bazdan çıktı
| Baz | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $x_1$ |
1 | 0 | −1/2 | 1/2 | 1/2 | −1/2 | 1 |
| $x_2$ |
0 | 1 | 1/2 | −3/2 | −1/2 | 3/2 | 3 |
| $w$ |
0 | 0 |
$M - 1/2$ |
$M - 1/2$ |
$M/2 + 5/2$ |
$M/2 - 1/2$ |
7 |
Optimallik Kontrolü
$w$ satırındaki tüm temel dışı değişken katsayıları $\geq 0$ mi?
- $s_1$: $M - 1/2 > 0$ ✓
- $s_2$: $M - 1/2 > 0$ ✓
- $a_1$: $M/2 + 5/2 > 0$ ✓
- $a_2$: $M/2 - 1/2 > 0$ ✓ (büyük $M$ için)
✅ Optimal — Yapay Değişkenler Bazdan Çıktı
$a_1 = a_2 = 0$ ve bazda değiller. Gerçek optimal çözüm bulundu.
🏆 Optimal Çözüm
$x_1 = 1,\quad x_2 = 3$
$w^* = 4(1) + 1(3) = $ 7
K1: $3(1)+3 = 6 \geq 6$ ✓ K2: $1+3 = 4 \geq 4$ ✓
📌 Bu Örnekten Çıkan Dersler
- Her $\geq$ kısıtına artık + yapay değişken eklendi ($-s_i + a_i$).
- $w$ satırı başlangıçta iki satır eliminasyonuyla güncellendi.
- 2 iterasyonda her iki yapay değişken de bazdan çıktı — problem uygun çözümlü.
- Optimal tablo okunurken yalnızca $x_1, x_2, s_1, s_2$ sütunları önemlidir; yapay değişken sütunları yok sayılır.