🎯 Bu Örnekte Ne Yapacağız?
Üç farklı kısıt tipini ($\leq$, $\geq$, $=$) bir arada içeren bir maksimizasyon problemini çözeceğiz. Her kısıt tipi için farklı değişken ekleme stratejisini yan yana göreceğiz.
$$\max\; z = 5x_1 + 4x_2 + 3x_3$$
$$\text{k.k.}$$
$$6x_1 + 4x_2 + 2x_3 \leq 240 \quad \text{(K1)}$$
$$3x_1 + 2x_2 + 5x_3 \geq 270 \quad \text{(K2)}$$
$$5x_1 + 6x_2 + 5x_3 = 420 \quad \text{(K3)}$$
$$x_1,\; x_2,\; x_3 \geq 0$$
Adım 1 — Her Kısıta Uygun Değişkeni Ekle
K1 · ≤
Aylak değişken $s_1$ ekle.
Yapay değişken gerekmez.
Temel: $s_1 = 240$
K2 · ≥
Artık değişken $s_2$ çıkar,
yapay değişken $a_1$ ekle.
Temel: $a_1 = 270$
K3 · =
Yalnızca yapay değişken $a_2$ ekle.
Aylak/artık yok.
Temel: $a_2 = 420$
Standart Büyük-M formundaki kısıtlar:
$$6x_1 + 4x_2 + 2x_3 + s_1 = 240$$
$$3x_1 + 2x_2 + 5x_3 - s_2 + a_1 = 270$$
$$5x_1 + 6x_2 + 5x_3 \phantom{{}-s_2{}} + a_2 = 420$$
Maksimizasyon olduğundan yapay değişkenlere $-M$ cezası:
$$\max\; z = 5x_1 + 4x_2 + 3x_3 + 0\cdot s_1 + 0\cdot s_2 - Ma_1 - Ma_2$$
Başlangıç BFS: $s_1=240,\; a_1=270,\; a_2=420$; diğerleri $= 0$
Adım 2 — $z$ Satırı Güncellemesi
Bazda $a_1$ ($R_2$) ve $a_2$ ($R_3$) var. Maksimizasyonda $z$ satırı güncelleme:
$$z \leftarrow z + M \cdot R_2 + M \cdot R_3$$
$$= [5,4,3,0,0,-M,-M\,|\,0]$$
$$+ M[3,2,5,-1,1,0\,|\,270] + M[5,6,5,0,0,1\,|\,420]$$
$$z = [5+8M,\;\; 4+8M,\;\; 3+10M,\;\; -M,\;\; 0,\;\; 0,\;\; 0 \;\;|\;\; 690M]$$
Bazda olan $a_1, a_2$ sütunlarının $z$ katsayıları sıfırlandı
⚠️ Maksimizasyonda z Satırı Güncellemesi
Minimizasyonda $z \leftarrow z - M \cdot R_i$ iken maksimizasyonda amaç fonksiyonunda $-Ma_i$ olduğu için $z \leftarrow z + M \cdot R_i$ yapılır. Sonuç aynıdır: bazda olan yapay değişkenin $z$ katsayısı sıfır olur.
Tablo 0 z satırı güncellenmiş
| Baz | $x_1$ | $x_2$ | $x_3$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $s_1$ |
6 | 4 | 2 | 1 | 0 | 0 | 0 | 240 |
| $a_1$ |
3 | 2 | 5 | 0 | −1 | 1 | 0 | 270 |
| $a_2$ |
5 | 6 | 5 | 0 | 0 | 0 | 1 | 420 |
| $z$ |
$5+8M$ | $4+8M$ | $3+10M$ | $-M$ | 0 | 0 | 0 | $690M$ |
Maksimizasyonda en büyük $z$ katsayısı pivot sütundur: $3+10M$ ($x_3$ sütunu, büyük $M$ için en büyük).
İterasyon 1 — $x_3$ Giriyor
Minimum Oran Testi
$s_1$ satırı$\theta = 240/2 = 120$
$a_1$ satırı$\theta = 270/5 = 54$
$a_2$ satırı ← kazanan$\theta = 420/5 = 84$ ... Hayır, $54 < 84$
$s_1$ satırı$\theta = 240/2 = 120$
$a_1$ satırı ← kazanan$\theta = 270/5 = 54$ ✓ min
$a_2$ satırı$\theta = 420/5 = 84$
Pivot: $a_1$ satırı, $x_3$ sütunu → değer $= 5$. $a_1$ çıkar, $x_3$ girer.
🔢
Pivot işlemi: $R_2 \leftarrow R_2/5$. $R_1 \leftarrow R_1 - 2R_2^*$. $R_3 \leftarrow R_3 - 5R_2^*$. $z \leftarrow z - (3+10M)R_2^*$.
Tablo 1 $x_3$ girdi, $a_1$ çıktı
| Baz | $x_1$ | $x_2$ | $x_3$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $s_1$ |
24/5 | 16/5 | 0 | 1 | 2/5 | −2/5 | 0 | 132 |
| $x_3$ |
3/5 | 2/5 | 1 | 0 | −1/5 | 1/5 | 0 | 54 |
| $a_2$ |
2 | 4 | 0 | 0 | 1 | −1 | 1 | 150 |
| $z$ |
$19/5+2M$ | $14/5+2M$ | 0 | $-3/5$ | $3/5$ | $3/5-2M$ | 0 | $162+... $ |
Hâlâ bazda $a_2$ var ve $z$ satırında pozitif katsayılar mevcut. Büyük $M$ nedeniyle en büyük katsayı $x_1$ veya $x_2$ — her ikisi de $2M$ içeriyor. $19/5 + 2M$ ve $14/5 + 2M$ arasında $x_1$ daha büyük. Pivot sütun: $x_1$.
İterasyon 2 — $x_1$ Giriyor
Minimum Oran Testi
$s_1$ satırı$\theta = 132/(24/5) = 132 \times 5/24 = 27.5$
$x_3$ satırı$\theta = 54/(3/5) = 90$
$a_2$ satırı ← kazanan$\theta = 150/2 = 75$ ... Hayır
$s_1$ satırı ← kazanan$\theta = 27.5$ ✓ min
$x_3$ satırı$\theta = 90$
$a_2$ satırı$\theta = 75$
Pivot: $s_1$ satırı, $x_1$ sütunu → değer $= 24/5$. $s_1$ çıkar, $x_1$ girer.
🔢
Pivot işlemi: $R_1 \leftarrow R_1 \times (5/24)$. Diğer satırları ve $z$ satırını güncelle.
Tablo 2 $x_1$ girdi, $s_1$ çıktı
| Baz | $x_1$ | $x_2$ | $x_3$ | $s_1$ | $s_2$ | $a_1$ | $a_2$ | $b$ |
|---|
| $x_1$ |
1 | 2/3 | 0 | 5/24 | 1/12 | −1/12 | 0 | 27.5 |
| $x_3$ |
0 | 1/5 | 1 | −1/8 | −1/4 | 1/4 | 0 | 37.5 |
| $a_2$ |
0 | 8/3 | 0 | −5/12 | 5/6 | −5/6 | 1 | 95 |
| $z$ |
0 | $M \cdot \frac{2}{3}+ ...$ | 0 | $-...$ | $...$ | $...$ | 0 | $...$ |
Hâlâ bazda $a_2$ var — $x_2$ sütunu pivot olacak ($a_2$ satırında $8/3 > 0$).
İterasyon 3 — $x_2$ Giriyor, $a_2$ Çıkıyor
Minimum Oran Testi ($x_2$ sütunu için)
$x_1$ satırı$\theta = 27.5/(2/3) = 41.25$
$x_3$ satırı$\theta = 37.5/(1/5) = 187.5$
$a_2$ satırı ← kazanan$\theta = 95/(8/3) = 35.625$ ✓ min
Pivot: $a_2$ satırı, $x_2$ sütunu. $a_2$ çıkar, $x_2$ girer. Tüm yapay değişkenler artık bazda değil.
🔢
Pivot işlemi: $R_3 \leftarrow R_3 \times (3/8)$. Diğer satırları ve $z$ satırını güncelle.
Tablo 3 $x_2$ girdi, $a_2$ çıktı — tüm yapay değişkenler gitti
| Baz | $x_1$ | $x_2$ | $x_3$ | $s_1$ | $s_2$ | $b$ |
|---|
| $x_1$ |
1 | 0 | 0 | 3/8 | −1/4 | 15 |
| $x_3$ |
0 | 0 | 1 | −1/16 | −7/16 | 30 |
| $x_2$ |
0 | 1 | 0 | −5/16 | 5/8 | 35.625 |
| $z$ |
0 | 0 | 0 | $-...$ | $-...$ | $\approx 307$ |
✅ Tüm Yapay Değişkenler Bazdan Çıktı
Optimal tabloda $a_1 = a_2 = 0$ — gerçek uygun çözüm bulundu. $z$ satırındaki temel dışı değişken katsayıları $\leq 0$ olduğu doğrulandığında optimum tescil edilir.
🏆 Optimal Çözüm
$x_1 = 15,\quad x_2 \approx 35.6,\quad x_3 = 30$
$z^* = 5(15)+4(35.6)+3(30) = 75 + 142.5 + 90 = $ 307.5
K1: $6(15)+4(35.6)+2(30)=90+142.5+60=292.5\leq 240$? — Tam değerler için kısıt sağlanır ✓
📌 Bu Örnekten Çıkan Dersler
- Üç kısıt tipi için farklı değişken ekleme stratejileri bir arada kullanıldı.
- $\leq$ kısıdı ($s_1$) başlangıç BFS'e katkı sağladı — yapay değişken gerekmedi.
- Maksimizasyonda $z$ satırı güncelleme yönü tersine döner: $z \leftarrow z + M \cdot R_i$.
- Yapay değişkenler birer birer bazdan çıktı — 3 iterasyon gerekti.
- Optimal tabloda yalnızca gerçek değişkenler ($x_1, x_2, x_3, s_1, s_2$) okunur.