---
title: "Alıştırmalar"
url: https://acik-matematik.com/dersler/lineer-programlama/alistirmalar
course: "Lineer Programlama"
language: tr
license: CC BY-NC-SA 4.0 (https://creativecommons.org/licenses/by-nc-sa/4.0/deed.tr)
format: acik-matematik-md/2
source: de3e2ec851c8d2e5647445b468d00cc63a45d6e2
---
# 14  Alıştırmalar

Bu bölümdeki alıştırmalar kitabın yöntemlerini baştan sona uygular. Önce bir problemin bütün temel çözümlerini tarayacak, sonra grafik yöntem, simpleks yöntem ve büyük M yöntemiyle problemler çözeceğiz. Ardından bir optimal tablo üzerinde duyarlılık analizi yapacak, bir problemi duali üzerinden çözecek ve son olarak dal-sınır yöntemiyle bir tam sayılı programlama problemini ele alacağız. Her çözüm, kullandığı yöntemin anlatıldığı bölüme bağlanır ve bütün tablolarını içerir.

## 14.1 Temel Çözümler

İlk iki alıştırma, simpleks yöntemden önceki en doğrudan yolu izler: bütün temel çözümleri hesaplayıp amaç değerlerini karşılaştırmak.

**Alıştırma 14.1 (Bütün temel çözümler)** $$\begin{aligned}
x_1 + 2x_2 + 3x_3 - x_4 &= 8 \\
2x_1 - 3x_2 + x_4 + x_5 &= 12 \\
x_j &\ge 0, \quad j = \overline{1,5} \\
\min z &= x_1 + x_2 - x_4
\end{aligned}$$ lineer programlama probleminin bütün temel çözümlerini bulunuz. Bunlardan hangilerinin uygun temel çözüm, hangilerinin dejenere olduğunu belirleyiniz ve her temel çözümde $z$ değerini hesaplayınız.

Çözüm

[Temel çözümler ve konveks kümeler](./temel-cozumler-ve-konveks-kumeler.md) bölümündeki dört adımlı reçeteyi izliyoruz ([Tanım 2.3](temel-cozumler-ve-konveks-kumeler.md#def-tck-temel-cozum), [Tanım 2.5](temel-cozumler-ve-konveks-kumeler.md#def-tck-uygun-temel-cozum), [Tanım 2.6](temel-cozumler-ve-konveks-kumeler.md#def-tck-dejenere)).

**Sayı.** Problem zaten standart formdadır: iki kısıt da eşitliktir, sağ taraflar $8$ ve $12$ negatif değildir ve bütün değişkenler $\ge 0$’dır. $m = 2$ denklem ve $n = 5$ değişken vardır. Her seçimde $n - m = 3$ değişken sıfırlanır ve kalan iki değişken için $2 \times 2$ bir sistem çözülür. En fazla $C(5, 2) = 10$ seçim vardır; hiçbirini atlamamak için temel değişken çiftlerini $\{x_1, x_2\}, \{x_1, x_3\}, \dots, \{x_4, x_5\}$ sırasıyla alıyoruz.

**a) $x_3 = x_4 = x_5 = 0$; temel değişkenler $x_1$, $x_2$.** $$\begin{aligned}
x_1 + 2x_2 &= 8 \\
2x_1 - 3x_2 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 1 & 2 \\ 2 & -3 \end{vmatrix} = -7 \ne 0 .$$ Birinci denklemden $x_1 = 8 - 2x_2$; ikincide yerine koyarsak $16 - 4x_2 - 3x_2 = 12$, yani $x_2 = \tfrac{4}{7}$ ve $x_1 = 8 - \tfrac{8}{7} = \tfrac{48}{7}$ bulunur: $$X_1 = \left(\tfrac{48}{7}, \tfrac{4}{7}, 0, 0, 0\right), \qquad z = \tfrac{48}{7} + \tfrac{4}{7} = \tfrac{52}{7}.$$

**b) $x_2 = x_4 = x_5 = 0$; temel değişkenler $x_1$, $x_3$.** $$\begin{aligned}
x_1 + 3x_3 &= 8 \\
2x_1 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 1 & 3 \\ 2 & 0 \end{vmatrix} = -6 \ne 0 .$$ İkinci denklemden $x_1 = 6$; birinciden $3x_3 = 2$, yani $x_3 = \tfrac{2}{3}$: $$X_2 = \left(6, 0, \tfrac{2}{3}, 0, 0\right), \qquad z = 6 .$$

**c) $x_2 = x_3 = x_5 = 0$; temel değişkenler $x_1$, $x_4$.** $$\begin{aligned}
x_1 - x_4 &= 8 \\
2x_1 + x_4 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 1 & -1 \\ 2 & 1 \end{vmatrix} = 3 \ne 0 .$$ İki denklemi toplarsak $3x_1 = 20$, yani $x_1 = \tfrac{20}{3}$ ve $x_4 = \tfrac{20}{3} - 8 = -\tfrac{4}{3}$: $$X_3 = \left(\tfrac{20}{3}, 0, 0, -\tfrac{4}{3}, 0\right), \qquad z = \tfrac{20}{3} + \tfrac{4}{3} = 8 .$$

**d) $x_2 = x_3 = x_4 = 0$; temel değişkenler $x_1$, $x_5$.** $$\begin{aligned}
x_1 &= 8 \\
2x_1 + x_5 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 1 & 0 \\ 2 & 1 \end{vmatrix} = 1 \ne 0 .$$ $x_1 = 8$ ve $x_5 = 12 - 16 = -4$: $$X_4 = (8, 0, 0, 0, -4), \qquad z = 8 .$$

**e) $x_1 = x_4 = x_5 = 0$; temel değişkenler $x_2$, $x_3$.** $$\begin{aligned}
2x_2 + 3x_3 &= 8 \\
-3x_2 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 2 & 3 \\ -3 & 0 \end{vmatrix} = 9 \ne 0 .$$ İkinci denklemden $x_2 = -4$; birinciden $3x_3 = 8 + 8 = 16$, yani $x_3 = \tfrac{16}{3}$: $$X_5 = \left(0, -4, \tfrac{16}{3}, 0, 0\right), \qquad z = -4 .$$

**f) $x_1 = x_3 = x_5 = 0$; temel değişkenler $x_2$, $x_4$.** $$\begin{aligned}
2x_2 - x_4 &= 8 \\
-3x_2 + x_4 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 2 & -1 \\ -3 & 1 \end{vmatrix} = -1 \ne 0 .$$ İki denklemi toplarsak $-x_2 = 20$, yani $x_2 = -20$ ve $x_4 = 2x_2 - 8 = -48$: $$X_6 = (0, -20, 0, -48, 0), \qquad z = -20 + 48 = 28 .$$

**g) $x_1 = x_3 = x_4 = 0$; temel değişkenler $x_2$, $x_5$.** $$\begin{aligned}
2x_2 &= 8 \\
-3x_2 + x_5 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 2 & 0 \\ -3 & 1 \end{vmatrix} = 2 \ne 0 .$$ $x_2 = 4$ ve $x_5 = 12 + 12 = 24$: $$X_7 = (0, 4, 0, 0, 24), \qquad z = 4 .$$

**h) $x_1 = x_2 = x_5 = 0$; temel değişkenler $x_3$, $x_4$.** $$\begin{aligned}
3x_3 - x_4 &= 8 \\
x_4 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 3 & -1 \\ 0 & 1 \end{vmatrix} = 3 \ne 0 .$$ $x_4 = 12$ ve $3x_3 = 20$, yani $x_3 = \tfrac{20}{3}$: $$X_8 = \left(0, 0, \tfrac{20}{3}, 12, 0\right), \qquad z = -12 .$$

**i) $x_1 = x_2 = x_4 = 0$; temel değişkenler $x_3$, $x_5$.** $$\begin{aligned}
3x_3 &= 8 \\
x_5 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} 3 & 0 \\ 0 & 1 \end{vmatrix} = 3 \ne 0 .$$ $x_3 = \tfrac{8}{3}$ ve $x_5 = 12$: $$X_9 = \left(0, 0, \tfrac{8}{3}, 0, 12\right), \qquad z = 0 .$$

**j) $x_1 = x_2 = x_3 = 0$; temel değişkenler $x_4$, $x_5$.** $$\begin{aligned}
-x_4 &= 8 \\
x_4 + x_5 &= 12
\end{aligned}
\qquad
\Delta = \begin{vmatrix} -1 & 0 \\ 1 & 1 \end{vmatrix} = -1 \ne 0 .$$ $x_4 = -8$ ve $x_5 = 12 + 8 = 20$: $$X_{10} = (0, 0, 0, -8, 20), \qquad z = 8 .$$

**Sınıflandırma.** Hiçbir seçimde $\Delta = 0$ çıkmadığından sistemin tam $10$ temel çözümü vardır. Negatif bileşeni olmayanlar $X_1$, $X_2$, $X_7$, $X_8$ ve $X_9$’dur; bu beşi uygun temel çözümdür. Her birinde iki temel değişkenin ikisi de pozitiftir, dolayısıyla hiçbiri dejenere değildir. $X_3$, $X_4$, $X_5$, $X_6$ ve $X_{10}$’da negatif bir bileşen bulunduğu için bunlar uygun değildir. Sonuçları bir tabloda toplayalım ([Tablo 14.1](#tbl-als-temel)); dejenerelik yalnız uygun temel çözümler için sorulduğundan uygun olmayan satırlarda o sütun boştur.

| Seçim | Sıfırlanan | Temel değişkenler | $\Delta$ | Temel çözüm | Uygun mu? | Dejenere mi? | $z$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| a\) | $x_3, x_4, x_5$ | $x_1, x_2$ | $-7$ | $X_1 = \left(\frac{48}{7}, \frac{4}{7}, 0, 0, 0\right)$ | Evet | Hayır | $\frac{52}{7}$ |
| b\) | $x_2, x_4, x_5$ | $x_1, x_3$ | $-6$ | $X_2 = \left(6, 0, \frac{2}{3}, 0, 0\right)$ | Evet | Hayır | $6$ |
| c\) | $x_2, x_3, x_5$ | $x_1, x_4$ | $3$ | $X_3 = \left(\frac{20}{3}, 0, 0, -\frac{4}{3}, 0\right)$ | Hayır ($x_4 < 0$) | $-$ | $8$ |
| d\) | $x_2, x_3, x_4$ | $x_1, x_5$ | $1$ | $X_4 = (8, 0, 0, 0, -4)$ | Hayır ($x_5 < 0$) | $-$ | $8$ |
| e\) | $x_1, x_4, x_5$ | $x_2, x_3$ | $9$ | $X_5 = \left(0, -4, \frac{16}{3}, 0, 0\right)$ | Hayır ($x_2 < 0$) | $-$ | $-4$ |
| f\) | $x_1, x_3, x_5$ | $x_2, x_4$ | $-1$ | $X_6 = (0, -20, 0, -48, 0)$ | Hayır ($x_2, x_4 < 0$) | $-$ | $28$ |
| g\) | $x_1, x_3, x_4$ | $x_2, x_5$ | $2$ | $X_7 = (0, 4, 0, 0, 24)$ | Evet | Hayır | $4$ |
| h\) | $x_1, x_2, x_5$ | $x_3, x_4$ | $3$ | $X_8 = \left(0, 0, \frac{20}{3}, 12, 0\right)$ | Evet | Hayır | $-12$ |
| i\) | $x_1, x_2, x_4$ | $x_3, x_5$ | $3$ | $X_9 = \left(0, 0, \frac{8}{3}, 0, 12\right)$ | Evet | Hayır | $0$ |
| j\) | $x_1, x_2, x_3$ | $x_4, x_5$ | $-1$ | $X_{10} = (0, 0, 0, -8, 20)$ | Hayır ($x_4 < 0$) | $-$ | $8$ |

Tablo 14.1: Problemin bütün temel çözümleri

$\blacksquare$

**Alıştırma 14.2 (Uygun temel çözümlerle optimumun aranması)** Önceki alıştırmadaki ([Alıştırma 14.1](#exr-als-temel-a)) problemin optimum uygun çözümünü belirleyiniz. Problem şudur: $$\begin{aligned}
x_1 + 2x_2 + 3x_3 - x_4 &= 8 \\
2x_1 - 3x_2 + x_4 + x_5 &= 12 \\
x_j &\ge 0, \quad j = \overline{1,5} \\
\min z &= x_1 + x_2 - x_4
\end{aligned}$$

Çözüm

**Uygun temel çözümlerin karşılaştırılması.** Önceki alıştırmanın tablosuna ([Tablo 14.1](#tbl-als-temel)) göre beş uygun temel çözüm ve amaç değerleri şunlardır: $$\begin{aligned}
X_1&: \ z = \tfrac{52}{7}, & X_2&: \ z = 6, & X_7&: \ z = 4, \\[1mm]
X_8&: \ z = -12, & X_9&: \ z = 0 .
\end{aligned}$$ En küçük değer $X_8 = \left(0, 0, \tfrac{20}{3}, 12, 0\right)$ noktasındaki $z = -12$’dir. Uygun olmayan $X_5$ ve $X_6$’nın $z$ değerleri aday değildir, çünkü bu noktalar $x_j \ge 0$ koşulunu bozar.

**Tarama ne zaman geçerli?** Uygun temel çözümleri tarama sonucu ([Sonuç 3.4](uc-noktalar-ve-grafik-yontem.md#cor-ucg-utc-tarama)), bunlar arasındaki en iyi değerin optimum olduğunu ancak problemin bir optimal çözümü **varsa** söyler. Uygun bölge sınırlı olsaydı optimum kendiliğinden var olurdu; burada bölgenin sınırlı olduğunu bilmiyoruz. Bu yüzden $X_8$’den daha iyi bir uygun çözüm olup olmadığını ayrıca kontrol etmeliyiz.

**$X_8$ bazında simpleks kriteri.** $X_8$’in bazı $B = (v_3, v_4)$’tür; burada $v_3 = (3, 0)^T$ ve $v_4 = (-1, 1)^T$. Baz dışındaki $v_2 = (2, -3)^T$ vektörünü baz vektörleri cinsinden yazalım: $v_2 = y_{32} v_3 + y_{42} v_4$ eşitliği $$3y_{32} - y_{42} = 2, \qquad y_{42} = -3$$ sistemini verir; buradan $y_{42} = -3$ ve $3y_{32} = -1$, yani $y_{32} = -\tfrac{1}{3}$. Baz maliyetleri $\vec{c}_B = (c_3, c_4)^T = (0, -1)^T$ olduğundan $$z_2 - c_2 = 0 \cdot \left(-\tfrac{1}{3}\right) + (-1) \cdot (-3) - 1 = 2 > 0 .$$ Minimum probleminde pozitif simpleks kriteri, $v_2$ baza alınırsa amaç değerinin küçüleceğini söyler. Üstelik $v_2$’nin iki katsayısı da negatiftir; oran testi yapılamaz. [Önerme 4.2](simpleks-yontem.md#prp-smp-sinirsiz) gereği amaç fonksiyonu uygun bölgede alttan sınırsızdır.

**Açık bir yarı doğru.** Aynı sonucu doğrudan görelim. $\vec{d} = \left(0, 1, \tfrac{1}{3}, 3, 0\right)$ vektörü için kısıtların sol tarafları $$\begin{aligned}
&0 + 2 \cdot 1 + 3 \cdot \tfrac{1}{3} - 3 = 0, \\[1mm]
&2 \cdot 0 - 3 \cdot 1 + 3 + 0 = 0
\end{aligned}$$ olur ve $\vec{d} \ge 0$’dır; yani $\vec{d}$ uygun bölgenin bir yön vektörüdür ([Tanım 7.2](sinirsiz-ve-alternatif-optimal-cozum.md#def-sao-yon)). O halde her $\lambda \ge 0$ için $$X(\lambda) = X_8 + \lambda \vec{d} = \left(0,\ \lambda,\ \tfrac{20}{3} + \tfrac{\lambda}{3},\ 12 + 3\lambda,\ 0\right)$$ bir uygun çözümdür. Kontrol edelim: $$\begin{aligned}
&2\lambda + 3\left(\tfrac{20}{3} + \tfrac{\lambda}{3}\right) - (12 + 3\lambda) = 20 - 12 = 8, \\[1mm]
&-3\lambda + (12 + 3\lambda) + 0 = 12 .
\end{aligned}$$ Bu çözümlerde amaç değeri $$z\big(X(\lambda)\big) = 0 + \lambda - (12 + 3\lambda) = -12 - 2\lambda$$ olur. $\lambda$ büyüdükçe $z$ sınır tanımadan küçülür. Örneğin $\lambda = 1$ için $X(1) = (0, 1, 7, 15, 0)$ uygun çözümdür ve $z = -14 < -12$’dir.

Neden böyle olduğunu kısıtlardan da okuyabiliriz. Birinci denklemden $x_4 = x_1 + 2x_2 + 3x_3 - 8$ yazıp amaçta yerine koyarsak $z = 8 - x_2 - 3x_3$ çıkar. $x_2$ büyüdükçe $x_4$ de büyür ve ikinci denklem $x_5$’i negatif yapmaz; bu yüzden $x_2$’yi istediğimiz kadar artırıp $z$’yi istediğimiz kadar küçültebiliriz.

**Sonuç.** Problemin sınırsız çözümü vardır ([Tanım 7.1](sinirsiz-ve-alternatif-optimal-cozum.md#def-sao-sinirsiz-cozum)): amaç fonksiyonu uygun çözümler üzerinde alttan sınırlı değildir ve **optimal çözüm yoktur**. Uygun temel çözümler arasındaki en küçük değer $X_8$’deki $z = -12$’dir, ama bu bir minimum değildir. Bu alıştırma, uygun temel çözümleri karşılaştırmadan önce optimumun var olduğundan emin olmak gerektiğini gösteriyor.

$\blacksquare$

## 14.2 Grafik Yöntem

İki değişkenli bir problemde uygun bölgeyi çizerek optimumu doğrudan görebiliriz.

**Alıştırma 14.3 (Grafik yöntemle bir maksimum problemi)** $$\begin{aligned}
x_1 + x_2 &\le 4 \\
20x_1 + 10x_2 &\le 40 \\
x_1 &\le 2 \\
x_2 &\le 3 \\
x_1, x_2 &\ge 0 \\
\max z &= 180x_1 + 120x_2
\end{aligned}$$ lineer programlama problemini grafik yöntemle çözünüz.

Çözüm

Uygun bölge OABC dörtgenidir; x₁ + x₂ ≤ 4 kısıtı bölgeye hiç değmez, x₁ = 2 doğrusu bölgeye yalnız A köşesinde değer. Kesikli doğrular z = 180x₁ + 120x₂ amaç fonksiyonunun z = 360 (A ve C'den geçer) ve z = 450 seviye doğrularıdır. Seviye doğrusu gradyan yönünde kaydırıldığında bölgeden en son B(1/2, 3) köşesinde ayrılır: max z = 450.

[Uç noktalar ve grafik yöntem](./uc-noktalar-ve-grafik-yontem.md) bölümündeki beş adımı ([Bölüm 3.3](uc-noktalar-ve-grafik-yontem.md#sec-ucg-grafik)) izliyoruz.

**1–2. Kısıt doğruları ve yarı düzlemler.** Her kısıtı eşitlik olarak çizip $O(0, 0)$ test noktasını yerine koyalım:

- $x_1 + x_2 = 4$ doğrusu $(4, 0)$ ve $(0, 4)$’ten geçer. $O$’da $0 \le 4$ doğrudur; uygun taraf $O$’nun bulunduğu taraftır.
- $20x_1 + 10x_2 = 40$ doğrusunun iki yanını $10$’a bölersek $2x_1 + x_2 = 4$ olur; doğru $(2, 0)$ ve $(0, 4)$’ten geçer. $O$’da $0 \le 40$ doğrudur; uygun taraf $O$’nun bulunduğu taraftır.
- $x_1 = 2$ düşey bir doğrudur. $O$’da $0 \le 2$ doğrudur; uygun taraf doğrunun soludur.
- $x_2 = 3$ yatay bir doğrudur. $O$’da $0 \le 3$ doğrudur; uygun taraf doğrunun altıdır.

$x_1, x_2 \ge 0$ koşulları birinci bölgeyi verir.

**3. Uygun bölge.** Bu yarı düzlemlerin kesişimi $OABC$ dörtgenidir. İki kısıt bölgenin biçimine katkı yapmaz. $2x_1 + x_2 \le 4$ ve $x_2 \ge 0$ olduğundan $2x_1 \le 4$, yani $x_1 \le 2$ kendiliğinden sağlanır. Ayrıca $$x_1 + x_2 = \tfrac{1}{2}(2x_1 + x_2) + \tfrac{1}{2}x_2 \le \tfrac{1}{2} \cdot 4 + \tfrac{1}{2} \cdot 3 = \tfrac{7}{2} < 4$$ olduğundan $x_1 + x_2 \le 4$ kısıtı da bölgenin hiçbir noktasında sıkı değildir.

**4. Köşeler.** Her köşe iki kısıt doğrusunun kesişimidir:

- $O(0, 0)$: iki eksenin kesişimi.
- $A$: $x_2 = 0$ ile $2x_1 + x_2 = 4$; $x_1 = 2$, yani $A(2, 0)$. $x_1 = 2$ doğrusu da bu noktadan geçer; $A$’da üç kısıt doğrusu kesişir.
- $B$: $x_2 = 3$ ile $2x_1 + x_2 = 4$; $2x_1 = 1$, yani $B(\tfrac{1}{2}, 3)$.
- $C$: $x_1 = 0$ ile $x_2 = 3$; $C(0, 3)$.

Köşelerin diğer kısıtları sağladığını kontrol edelim. $B$ için $x_1 + x_2 = \tfrac{7}{2} \le 4$ ve $x_1 = \tfrac{1}{2} \le 2$; $A$ için $x_1 + x_2 = 2 \le 4$ ve $x_2 = 0 \le 3$; $C$ için $20 \cdot 0 + 10 \cdot 3 = 30 \le 40$, $0 + 3 \le 4$ ve $0 \le 2$’dir.

$A$’da üç kısıt birden sıkı olduğu için bu köşeye karşılık gelen uygun temel çözüm dejeneredir ([Tanım 2.6](temel-cozumler-ve-konveks-kumeler.md#def-tck-dejenere)): standart formda $x_1 = 2$, $x_2 = 0$ iken $2x_1 + x_2 = 4$ ve $x_1 = 2$ kısıtlarının aylak değişkenleri de sıfırdır.

**5. Optimum.** Gradyan $\vec{c} = (180, 120) = 60 \cdot (3, 2)$’dir. $z$ seviye doğruları $180x_1 + 120x_2 = z$, yani $3x_1 + 2x_2 = \tfrac{z}{60}$ biçiminde paralel doğrulardır. Amaç maksimum olduğundan seviye doğrusunu gradyan yönünde, yani sağ yukarıya doğru kaydırırız. $z = 360$ seviye doğrusu $3x_1 + 2x_2 = 6$’dır ve hem $A(2, 0)$’dan hem $C(0, 3)$’ten geçer; bölgenin bu doğrunun üstünde kalan kısmında $z$ daha büyüktür. Kaydırmaya devam edince doğru bölgeden en son $B(\tfrac{1}{2}, 3)$ köşesinde ayrılır: $z = 450$ seviye doğrusu $3x_1 + 2x_2 = \tfrac{15}{2}$ bölgeye yalnız $B$’de değer.

Bölge sınırlı olduğu için köşelerdeki değerleri karşılaştırmak da yeter ([Sonuç 3.1](uc-noktalar-ve-grafik-yontem.md#cor-ucg-uc-nokta-tarama)):

|    Köşe    | $O(0, 0)$ | $A(2, 0)$ | $B(\frac{1}{2}, 3)$ | $C(0, 3)$ |
|:----------:|:----------:|:----------:|:----------:|:----------:|
| $z = 180x_1 + 120x_2$ | $0$ | $360$ | $450$ | $360$ |

Tablo 14.2: Grafik yöntem alıştırmasında köşelerdeki amaç değerleri

En büyük değer $B$’dedir. Optimal çözüm $$x_1 = \tfrac{1}{2}, \quad x_2 = 3, \qquad \max z = 180 \cdot \tfrac{1}{2} + 120 \cdot 3 = 90 + 360 = 450$$ dir.

$\blacksquare$

## 14.3 Simpleks Yöntem

Şimdi aynı karşılaştırmayı bütün köşeleri gezmeden, komşu uç noktadan komşu uç noktaya geçerek yapalım.

**Alıştırma 14.4 (Simpleks yöntemle bir minimum problemi)** $$\begin{aligned}
x_1 - 2x_2 + x_3 &= 2 \\
2x_1 + x_2 + x_4 &= 6 \\
x_1 + 2x_2 + x_5 &= 5 \\
-x_1 + x_2 + x_6 &= 2 \\
x_j &\ge 0, \quad j = \overline{1,6} \\
\min z &= -4x_1 - 5x_2
\end{aligned}$$ lineer programlama problemini simpleks yöntemle çözünüz.

Çözüm

Çözümde [Simpleks yöntem](./simpleks-yontem.md) bölümündeki tabloyu ([Bölüm 4.3](simpleks-yontem.md#sec-smp-tablo)) ve dönüşüm kurallarını ([Bölüm 4.4](simpleks-yontem.md#sec-smp-donusum)) kullanıyoruz.

**Çözülebilir hal.** Problem standart formdadır: bütün kısıtlar eşitliktir, sağ taraflar $2, 6, 5, 2$ negatif değildir ve bütün değişkenler $\ge 0$’dır. Amaç fonksiyonunu sıfır katsayılarla birlikte yazalım: $$\min z = -4x_1 - 5x_2 + 0x_3 + 0x_4 + 0x_5 + 0x_6 .$$ $x_3$, $x_4$, $x_5$, $x_6$ değişkenlerinin her biri yalnız bir denklemde ve katsayısı $1$ ile görünür; $v_3, v_4, v_5, v_6$ sütunları $4 \times 4$ birim matrisi oluşturur. Demek ki problem simpleks yöntem ile çözülebilir haldedir ([Tanım 1.9](lineer-programlama-problemi.md#def-lpp-cozulebilir-hal)) ve yapay değişken gerekmez. (Bu dört değişken aslında $x_1 - 2x_2 \le 2$, $2x_1 + x_2 \le 6$, $x_1 + 2x_2 \le 5$, $-x_1 + x_2 \le 2$ kısıtlarının aylak değişkenleridir.)

**Başlangıç tablosu.** Başlangıç bazı $B_0 = (v_3, v_4, v_5, v_6)$, başlangıç çözümü $X_0 = (0, 0, 2, 6, 5, 2)$ ve $z_0 = 0$’dır. $\vec{c}_B = \vec{0}$ olduğu için $z_j - c_j = -c_j$: $z_1 - c_1 = 4$, $z_2 - c_2 = 5$; baz vektörlerininki $0$’dır.

Minimum probleminde en büyük pozitif $z_j - c_j$ baza girer ve bütün $z_j - c_j \le 0$ olunca durulur. $\max\{4, 5\} = 5$ olduğundan $v_2$ baza girer. $v_2$ sütununda $y_{32} = -2 < 0$ olduğundan $x_3$ satırı oran testine girmez: $$\min\left(\frac{6}{1}, \frac{5}{2}, \frac{2}{1}\right) = 2 .$$ En küçük oran $x_6$ satırındadır; $v_6$ bazdan çıkar ve pivot $y_{62} = 1$’dir.

|  |  | $c_j$ | $-4$ | $-5$ | $0$ | $0$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | Oran |
| $x_3$ | $0$ | $2$ | $1$ | $-2$ | $1$ | $0$ | $0$ | $0$ | $-$ |
| $x_4$ | $0$ | $6$ | $2$ | $1$ | $0$ | $1$ | $0$ | $0$ | $\frac{6}{1}$ |
| $x_5$ | $0$ | $5$ | $1$ | $2$ | $0$ | $0$ | $1$ | $0$ | $\frac{5}{2}$ |
| $x_6$ | $0$ | $2$ | $-1$ | $[1]$ | $0$ | $0$ | $0$ | $1$ | $\frac{2}{1} \Rightarrow$ |
| $z_j - c_j$ |  | $z_0 = 0$ | $4$ | $5 \Uparrow$ | $0$ | $0$ | $0$ | $0$ |  |

Tablo 14.3: Başlangıç tablosu

**Birinci iterasyon.** Satırları baz değişkenlerinin indisleriyle $S_3, S_4, S_5, S_6$ diye adlandıralım. Pivot $1$ olduğundan $S_6$ aynen kalır ve $c_B$ değeri $-5$ olan $x_2$ satırı olur. $v_2$ sütununu birim vektöre çevirmek için $$\begin{aligned}
S_3 &\leftarrow S_3 + 2S_6, & S_4 &\leftarrow S_4 - S_6, \\
S_5 &\leftarrow S_5 - 2S_6, & (z_j - c_j) &\leftarrow (z_j - c_j) - 5S_6
\end{aligned}$$ işlemlerini yaparız. Örneğin $S_6 = (2 \mid -1, 1, 0, 0, 0, 1)$ olduğundan kriter satırı $$\begin{aligned}
&(0 - 10 \mid 4 + 5,\ 5 - 5,\ 0,\ 0,\ 0,\ 0 - 5) \\[1mm]
&\quad = (-10 \mid 9, 0, 0, 0, 0, -5)
\end{aligned}$$ olur.

|  |  | $c_j$ | $-4$ | $-5$ | $0$ | $0$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | Oran |
| $x_3$ | $0$ | $6$ | $-1$ | $0$ | $1$ | $0$ | $0$ | $2$ | $-$ |
| $x_4$ | $0$ | $4$ | $3$ | $0$ | $0$ | $1$ | $0$ | $-1$ | $\frac{4}{3}$ |
| $x_5$ | $0$ | $1$ | $[3]$ | $0$ | $0$ | $0$ | $1$ | $-2$ | $\frac{1}{3} \Rightarrow$ |
| $x_2$ | $-5$ | $2$ | $-1$ | $1$ | $0$ | $0$ | $0$ | $1$ | $-$ |
| $z_j - c_j$ |  | $z_0 = -10$ | $9 \Uparrow$ | $0$ | $0$ | $0$ | $0$ | $-5$ |  |

Tablo 14.4: Birinci iterasyon tablosu

Birinci iterasyon tablosunda ([Tablo 14.4](#tbl-als-smp-birinci)) çözüm $X_1 = (0, 2, 6, 4, 1, 0)$ ve $z = -5 \cdot 2 = -10$’dur. Tek pozitif kriter $z_1 - c_1 = 9$ olduğundan $v_1$ baza girer. $v_1$ sütununda $x_3$ ve $x_2$ satırlarının elemanları $-1$’dir, bu satırlar teste girmez: $\min\left(\tfrac{4}{3}, \tfrac{1}{3}\right) = \tfrac{1}{3}$. $v_5$ bazdan çıkar; pivot $y_{51} = 3$.

**İkinci iterasyon.** Pivot satırı $3$’e bölünür ve $c_B$ değeri $-4$ olan $x_1$ satırı olur: $$S_1 = \left(\tfrac{1}{3} \mid 1, 0, 0, 0, \tfrac{1}{3}, -\tfrac{2}{3}\right).$$ Diğer satırlar $$\begin{aligned}
S_3 &\leftarrow S_3 + S_1, & S_4 &\leftarrow S_4 - 3S_1, \\
S_2 &\leftarrow S_2 + S_1, & (z_j - c_j) &\leftarrow (z_j - c_j) - 9S_1
\end{aligned}$$ ile bulunur. Örneğin $x_3$ satırı $$\begin{aligned}
S_3 + S_1 &= \left(6 + \tfrac{1}{3} \mid 0,\ 0,\ 1,\ 0,\ \tfrac{1}{3},\ 2 - \tfrac{2}{3}\right) \\[1mm]
&= \left(\tfrac{19}{3} \mid 0,\ 0,\ 1,\ 0,\ \tfrac{1}{3},\ \tfrac{4}{3}\right)
\end{aligned}$$ olur; kriter satırının $v_6$ elemanı da $-5 - 9 \cdot \left(-\tfrac{2}{3}\right) = 1$’dir.

|  |  | $c_j$ | $-4$ | $-5$ | $0$ | $0$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | Oran |
| $x_3$ | $0$ | $\frac{19}{3}$ | $0$ | $0$ | $1$ | $0$ | $\frac{1}{3}$ | $\frac{4}{3}$ | $\frac{19/3}{4/3}$ |
| $x_4$ | $0$ | $3$ | $0$ | $0$ | $0$ | $1$ | $-1$ | $[1]$ | $\frac{3}{1} \Rightarrow$ |
| $x_1$ | $-4$ | $\frac{1}{3}$ | $1$ | $0$ | $0$ | $0$ | $\frac{1}{3}$ | $-\frac{2}{3}$ | $-$ |
| $x_2$ | $-5$ | $\frac{7}{3}$ | $0$ | $1$ | $0$ | $0$ | $\frac{1}{3}$ | $\frac{1}{3}$ | $\frac{7/3}{1/3}$ |
| $z_j - c_j$ |  | $z_0 = -13$ | $0$ | $0$ | $0$ | $0$ | $-3$ | $1 \Uparrow$ |  |

Tablo 14.5: İkinci iterasyon tablosu

İkinci iterasyon tablosunda ([Tablo 14.5](#tbl-als-smp-ikinci)) çözüm $X_2 = \left(\tfrac{1}{3}, \tfrac{7}{3}, \tfrac{19}{3}, 3, 0, 0\right)$ ve $z = -\tfrac{4}{3} - \tfrac{35}{3} = -13$’tür. Pozitif kriter $z_6 - c_6 = 1$ kaldığı için $v_6$ baza girer. $x_1$ satırındaki $-\tfrac{2}{3}$ teste girmez: $$\min\left(\frac{19/3}{4/3}, \frac{3}{1}, \frac{7/3}{1/3}\right) = \min\left(\frac{19}{4}, 3, 7\right) = 3 .$$ $v_4$ bazdan çıkar; pivot $y_{46} = 1$.

**Üçüncü iterasyon.** Pivot $1$ olduğundan $S_4 = (3 \mid 0, 0, 0, 1, -1, 1)$ aynen kalır ve $c_B$ değeri $0$ olan $x_6$ satırı olur. Diğer satırlar $$\begin{aligned}
S_3 &\leftarrow S_3 - \tfrac{4}{3}S_4, & S_1 &\leftarrow S_1 + \tfrac{2}{3}S_4, \\[1mm]
S_2 &\leftarrow S_2 - \tfrac{1}{3}S_4, & (z_j - c_j) &\leftarrow (z_j - c_j) - S_4
\end{aligned}$$ ile bulunur. Pivot satırında yalnız $v_0$, $v_4$, $v_5$, $v_6$ sütunları sıfırdan farklı olduğu için yalnız bu sütunlar değişir; örneğin $x_3$ satırında $\tfrac{19}{3} - 4 = \tfrac{7}{3}$, $0 - \tfrac{4}{3} = -\tfrac{4}{3}$, $\tfrac{1}{3} + \tfrac{4}{3} = \tfrac{5}{3}$ bulunur.

|  |  | $c_j$ | $-4$ | $-5$ | $0$ | $0$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ |
| $x_3$ | $0$ | $\frac{7}{3}$ | $0$ | $0$ | $1$ | $-\frac{4}{3}$ | $\frac{5}{3}$ | $0$ |
| $x_6$ | $0$ | $3$ | $0$ | $0$ | $0$ | $1$ | $-1$ | $1$ |
| $x_1$ | $-4$ | $\frac{7}{3}$ | $1$ | $0$ | $0$ | $\frac{2}{3}$ | $-\frac{1}{3}$ | $0$ |
| $x_2$ | $-5$ | $\frac{4}{3}$ | $0$ | $1$ | $0$ | $-\frac{1}{3}$ | $\frac{2}{3}$ | $0$ |
| $z_j - c_j$ |  | $z_0 = -16$ | $0$ | $0$ | $0$ | $-1$ | $-2$ | $0$ |

Tablo 14.6: Üçüncü iterasyon tablosu (optimal tablo)

**Sonuç.** Üçüncü iterasyon tablosunda ([Tablo 14.6](#tbl-als-smp-optimal)) bütün $z_j - c_j \le 0$’dır; minimum problemi için optimal tabloya ulaşıldı. Optimal çözüm $$X^{*} = (x_1, \dots, x_6) = \left(\tfrac{7}{3}, \tfrac{4}{3}, \tfrac{7}{3}, 0, 0, 3\right),
\qquad
\min z = -4 \cdot \tfrac{7}{3} - 5 \cdot \tfrac{4}{3} = -16$$ dır. Amaç değeri iterasyonlar boyunca $0 \to -10 \to -13 \to -16$ diye azaldı.

Bu problem, [Simpleks yöntem](./simpleks-yontem.md) bölümünde kurulup çözülen örneğin ([Örnek 4.6](simpleks-yontem.md#exm-smp-ornek-iterasyonlar)) standart formudur. Orada yöntemin uygun bölgenin köşeleri üzerinde izlediği $(0, 0) \to (0, 2) \to (\tfrac{1}{3}, \tfrac{7}{3}) \to (\tfrac{7}{3}, \tfrac{4}{3})$ yolu şekil üzerinde de gösterilir.

$\blacksquare$

## 14.4 Büyük M Yöntemi

Kısıtlarda $\ge$ bulununca standart form birim matris içermez ve yapay değişken gerekir. Bir sonraki alıştırmada kanonik formdan simpleks yöntem ile çözülebilir hale kadar bütün adımları açıkça yazıyoruz.

**Alıştırma 14.5 (Büyük M yöntemiyle üç değişkenli bir minimum problemi)** $$\begin{aligned}
3x_1 - 4x_2 - 6x_3 &\le 2 \\
2x_1 + x_2 + 2x_3 &\ge 11 \\
x_1 + 3x_2 - 2x_3 &\le 5 \\
x_1, x_2, x_3 &\ge 0 \\
\min z &= 2x_1 - 3x_2 + 6x_3
\end{aligned}$$ lineer programlama problemini M yöntemiyle çözünüz.

Çözüm

Problemi [Büyük M yöntemi](./buyuk-m-yontemi.md) bölümündeki adımlarla çözeceğiz. Önce üç formu bu problem üzerinde birbirinden ayıralım.

**Kanonik form.** Minimum probleminde kanonik form ([Tanım 1.6](lineer-programlama-problemi.md#def-lpp-kanonik-form)) bütün kısıtların $\ge$ olmasını ister. Birinci ve üçüncü kısıtlar $\le$ olduğundan onları $-1$ ile çarparız: $$\begin{aligned}
-3x_1 + 4x_2 + 6x_3 &\ge -2 \\
2x_1 + x_2 + 2x_3 &\ge 11 \\
-x_1 - 3x_2 + 2x_3 &\ge -5 \\
x_1, x_2, x_3 &\ge 0 \\
\min z &= 2x_1 - 3x_2 + 6x_3
\end{aligned}$$ Bu problem kanonik formdadır, ama sağ taraflarında $-2$ ve $-5$ vardır. Kanonik form dual problemi yazmak için gereklidir; simpleks yöntem için ondan geçmek zorunlu değildir.

**Standart form.** Standart form ([Tanım 1.7](lineer-programlama-problemi.md#def-lpp-standart-form)) eşitlik kısıtları ve negatif olmayan sağ taraflar ister. Verilen problemin sağ tarafları $2, 11, 5$ zaten negatif değildir; bu yüzden verilen problemden doğrudan ilerleriz. (Kanonik formdan başlasaydık birinci ve üçüncü satırları yeniden $-1$ ile çarpıp aynı yere dönerdik.) $\le$ olan birinci ve üçüncü kısıtlara $x_4$ ve $x_6$ aylak değişkenlerini ekler, $\ge$ olan ikinci kısıttan $x_5$ artık değişkenini çıkarırız ([Tanım 1.8](lineer-programlama-problemi.md#def-lpp-aylak-artik)): $$\begin{aligned}
3x_1 - 4x_2 - 6x_3 + x_4 &= 2 \\
2x_1 + x_2 + 2x_3 - x_5 &= 11 \\
x_1 + 3x_2 - 2x_3 + x_6 &= 5 \\
x_j &\ge 0, \quad j = \overline{1,6} \\
\min z &= 2x_1 - 3x_2 + 6x_3 \\
&\quad + 0x_4 + 0x_5 + 0x_6
\end{aligned}$$

**Simpleks yöntem ile çözülebilir hal.** Standart formun katsayılar matrisi $$\begin{bmatrix}
3 & -4 & -6 & 1 & 0 & 0 \\
2 & 1 & 2 & 0 & -1 & 0 \\
1 & 3 & -2 & 0 & 0 & 1
\end{bmatrix}$$ dir. $x_4$ yalnız birinci, $x_6$ yalnız üçüncü denklemde ve katsayısı $1$ ile görünür; bu iki denklemin birim sütunu hazırdır. İkinci denklemde ise $x_5$’in katsayısı $-1$’dir ve $(0, 1, 0)^T$ birim sütunu yoktur. Standart form birim matris içermediği için henüz simpleks yöntem ile çözülebilir halde değildir. Yalnız ikinci denkleme $x_{u_1}$ yapay değişkenini ([Tanım 1.10](lineer-programlama-problemi.md#def-lpp-yapay-degisken)) ekleriz; minimum problemi olduğundan amaç katsayısı $+M$’dir: $$\begin{aligned}
3x_1 - 4x_2 - 6x_3 + x_4 &= 2 \\
2x_1 + x_2 + 2x_3 - x_5 + x_{u_1} &= 11 \\
x_1 + 3x_2 - 2x_3 + x_6 &= 5 \\
x_1, \dots, x_6, x_{u_1} &\ge 0 \\
\min z &= 2x_1 - 3x_2 + 6x_3 + 0x_4 \\
&\quad + 0x_5 + 0x_6 + Mx_{u_1}
\end{aligned}$$ Artık $v_4$, $v_{u_1}$, $v_6$ sütunları $3 \times 3$ birim matrisi oluşturur ve problem simpleks yöntem ile çözülebilir haldedir. Başlangıç bazı $B_0 = (v_4, v_{u_1}, v_6)$, başlangıç çözümü $x_4 = 2$, $x_{u_1} = 11$, $x_6 = 5$ ve diğer değişkenler $0$’dır.

**Başlangıç tablosu.** Baz maliyetleri $\vec{c}_B = (0, M, 0)$’dır. Her sütun için $c_B$ sütunuyla $v_j$ sütununun karşılıklı çarpımlarını toplayıp $c_j$’yi çıkarırız: $$\begin{aligned}
z_1 - c_1 &= (0 \cdot 3 + M \cdot 2 + 0 \cdot 1) - 2 = 2M - 2, \\[1mm]
z_2 - c_2 &= (0 \cdot (-4) + M \cdot 1 + 0 \cdot 3) - (-3) = M + 3, \\[1mm]
z_3 - c_3 &= (0 \cdot (-6) + M \cdot 2 + 0 \cdot (-2)) - 6 = 2M - 6, \\[1mm]
z_5 - c_5 &= (0 \cdot 0 + M \cdot (-1) + 0 \cdot 0) - 0 = -M, \\[1mm]
z_0 &= 0 \cdot 2 + M \cdot 11 + 0 \cdot 5 = 11M .
\end{aligned}$$ Baz vektörleri $v_4$, $v_{u_1}$, $v_6$’nın kriterleri $0$’dır.

Minimum probleminde en büyük pozitif $z_j - c_j$ girer. Pozitif kriterler $2M - 2$, $M + 3$ ve $2M - 6$’dır. $M$’nin katsayısı en büyük olan ikisi $2M - 2$ ile $2M - 6$’dır; katsayılar eşit olduğundan sabit terimlere bakarız: $-2 > -6$ ([Önerme 5.2](buyuk-m-yontemi.md#prp-bym-karsilastirma)). En büyük kriter $2M - 2$’dir ve $v_1$ baza girer. $v_1$ sütununun üç elemanı da pozitiftir: $$\min\left(\frac{2}{3}, \frac{11}{2}, \frac{5}{1}\right) = \frac{2}{3} .$$ $v_4$ bazdan çıkar; pivot $3$’tür.

|  |  | $c_j$ | $2$ | $-3$ | $6$ | $0$ | $0$ | $0$ | $M$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | $v_{u_1}$ | Oran |
| $x_4$ | $0$ | $2$ | $[3]$ | $-4$ | $-6$ | $1$ | $0$ | $0$ | $0$ | $\frac{2}{3} \Rightarrow$ |
| $x_{u_1}$ | $M$ | $11$ | $2$ | $1$ | $2$ | $0$ | $-1$ | $0$ | $1$ | $\frac{11}{2}$ |
| $x_6$ | $0$ | $5$ | $1$ | $3$ | $-2$ | $0$ | $0$ | $1$ | $0$ | $\frac{5}{1}$ |
| $z_j - c_j$ |  | $z_0 = 11M$ | $2M-2 \Uparrow$ | $M+3$ | $2M-6$ | $0$ | $-M$ | $0$ | $0$ |  |

Tablo 14.7: Başlangıç tablosu

**Birinci iterasyon.** Pivot satırı $3$’e bölünür ve $c_B$ değeri $c_1 = 2$ olan $x_1$ satırı olur: $$\left(\tfrac{2}{3} \mid 1,\ -\tfrac{4}{3},\ -2,\ \tfrac{1}{3},\ 0,\ 0,\ 0\right).$$ $x_{u_1}$ satırının $v_1$ elemanı $2$ olduğundan bu satırdan yeni pivot satırının $2$ katı, $x_6$ satırından da $1$ katı çıkarılır: $$\begin{aligned}
x_{u_1}&: \ \left(11 - \tfrac{4}{3} \mid 0,\ 1 + \tfrac{8}{3},\ 2 + 4,\ -\tfrac{2}{3},\ -1,\ 0,\ 1\right) \\[1mm]
&\quad = \left(\tfrac{29}{3} \mid 0,\ \tfrac{11}{3},\ 6,\ -\tfrac{2}{3},\ -1,\ 0,\ 1\right), \\[1mm]
x_6&: \ \left(5 - \tfrac{2}{3} \mid 0,\ 3 + \tfrac{4}{3},\ -2 + 2,\ -\tfrac{1}{3},\ 0,\ 1,\ 0\right) \\[1mm]
&\quad = \left(\tfrac{13}{3} \mid 0,\ \tfrac{13}{3},\ 0,\ -\tfrac{1}{3},\ 0,\ 1,\ 0\right).
\end{aligned}$$ Yeni baz maliyetleri $\vec{c}_B = (2, M, 0)$ ile kriterler: $$\begin{aligned}
z_2 - c_2 &= 2 \cdot \left(-\tfrac{4}{3}\right) + M \cdot \tfrac{11}{3} + 0 + 3 = \tfrac{11}{3}M + \tfrac{1}{3}, \\[1mm]
z_3 - c_3 &= 2 \cdot (-2) + M \cdot 6 + 0 - 6 = 6M - 10, \\[1mm]
z_4 - c_4 &= 2 \cdot \tfrac{1}{3} + M \cdot \left(-\tfrac{2}{3}\right) + 0 - 0 = -\tfrac{2}{3}M + \tfrac{2}{3}, \\[1mm]
z_5 - c_5 &= 2 \cdot 0 + M \cdot (-1) + 0 - 0 = -M, \\[1mm]
z_0 &= 2 \cdot \tfrac{2}{3} + M \cdot \tfrac{29}{3} + 0 = \tfrac{29}{3}M + \tfrac{4}{3} .
\end{aligned}$$ Pozitif kriterler $\tfrac{11}{3}M + \tfrac{1}{3}$ ve $6M - 10$’dur. $M$’nin katsayıları $6 > \tfrac{11}{3}$ olduğundan en büyüğü $6M - 10$’dur ve $v_3$ baza girer. $v_3$ sütununda $x_1$ satırının elemanı $-2$, $x_6$ satırınınki $0$’dır; bu satırlar teste girmez. Tek oran $\tfrac{29/3}{6} = \tfrac{29}{18}$’dir; $v_{u_1}$ bazdan çıkar ve pivot $6$’dır.

|  |  | $c_j$ | $2$ | $-3$ | $6$ | $0$ | $0$ | $0$ | $M$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | $v_{u_1}$ | Oran |
| $x_1$ | $2$ | $\frac{2}{3}$ | $1$ | $-\frac{4}{3}$ | $-2$ | $\frac{1}{3}$ | $0$ | $0$ | $0$ | $-$ |
| $x_{u_1}$ | $M$ | $\frac{29}{3}$ | $0$ | $\frac{11}{3}$ | $[6]$ | $-\frac{2}{3}$ | $-1$ | $0$ | $1$ | $\frac{29/3}{6} \Rightarrow$ |
| $x_6$ | $0$ | $\frac{13}{3}$ | $0$ | $\frac{13}{3}$ | $0$ | $-\frac{1}{3}$ | $0$ | $1$ | $0$ | $-$ |
| $z_j - c_j$ |  | $z_0 = \frac{29}{3}M+\frac{4}{3}$ | $0$ | $\frac{11}{3}M+\frac{1}{3}$ | $6M-10 \Uparrow$ | $-\frac{2}{3}M+\frac{2}{3}$ | $-M$ | $0$ | $0$ |  |

Tablo 14.8: Birinci iterasyon tablosu

**İkinci iterasyon.** Pivot satırı $6$’ya bölünür ve $c_B$ değeri $c_3 = 6$ olan $x_3$ satırı olur: $$\left(\tfrac{29}{18} \mid 0,\ \tfrac{11}{18},\ 1,\ -\tfrac{1}{9},\ -\tfrac{1}{6},\ 0\right).$$ $x_{u_1}$ bazdan çıktığı için $v_{u_1}$ sütunu artık yazılmaz. $x_1$ satırının $v_3$ elemanı $-2$ olduğundan bu satıra yeni pivot satırının $2$ katı eklenir: $$\begin{aligned}
&\left(\tfrac{2}{3} + \tfrac{29}{9} \mid 1,\ -\tfrac{4}{3} + \tfrac{11}{9},\ 0,\ \tfrac{1}{3} - \tfrac{2}{9},\ -\tfrac{1}{3},\ 0\right) \\[1mm]
&\quad = \left(\tfrac{35}{9} \mid 1,\ -\tfrac{1}{9},\ 0,\ \tfrac{1}{9},\ -\tfrac{1}{3},\ 0\right).
\end{aligned}$$ $x_6$ satırının $v_3$ elemanı $0$ olduğundan bu satır değişmez. $\vec{c}_B = (2, 6, 0)$ ile kriterler: $$\begin{aligned}
z_2 - c_2 &= 2 \cdot \left(-\tfrac{1}{9}\right) + 6 \cdot \tfrac{11}{18} + 0 + 3 = \tfrac{58}{9}, \\[1mm]
z_4 - c_4 &= 2 \cdot \tfrac{1}{9} + 6 \cdot \left(-\tfrac{1}{9}\right) + 0 - 0 = -\tfrac{4}{9}, \\[1mm]
z_5 - c_5 &= 2 \cdot \left(-\tfrac{1}{3}\right) + 6 \cdot \left(-\tfrac{1}{6}\right) + 0 - 0 = -\tfrac{5}{3}, \\[1mm]
z_0 &= 2 \cdot \tfrac{35}{9} + 6 \cdot \tfrac{29}{18} + 0 = \tfrac{70}{9} + \tfrac{87}{9} = \tfrac{157}{9} .
\end{aligned}$$ Bazda yapay değişken kalmadığı için $M$ tablodan kayboldu. Bu tablonun çözümü $\left(\tfrac{35}{9}, 0, \tfrac{29}{18}, 0, 0, \tfrac{13}{3}\right)$ artık orijinal problemin uygun bir çözümüdür.

Tek pozitif kriter $z_2 - c_2 = \tfrac{58}{9}$ olduğundan $v_2$ baza girer. $x_1$ satırındaki $-\tfrac{1}{9}$ teste girmez: $$\min\left(\frac{29/18}{11/18}, \frac{13/3}{13/3}\right) = \min\left(\frac{29}{11}, 1\right) = 1 .$$ $v_6$ bazdan çıkar; pivot $\tfrac{13}{3}$’tür.

|  |  | $c_j$ | $2$ | $-3$ | $6$ | $0$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | Oran |
| $x_1$ | $2$ | $\frac{35}{9}$ | $1$ | $-\frac{1}{9}$ | $0$ | $\frac{1}{9}$ | $-\frac{1}{3}$ | $0$ | $-$ |
| $x_3$ | $6$ | $\frac{29}{18}$ | $0$ | $\frac{11}{18}$ | $1$ | $-\frac{1}{9}$ | $-\frac{1}{6}$ | $0$ | $\frac{29/18}{11/18}$ |
| $x_6$ | $0$ | $\frac{13}{3}$ | $0$ | $[\frac{13}{3}]$ | $0$ | $-\frac{1}{3}$ | $0$ | $1$ | $\frac{13/3}{13/3} \Rightarrow$ |
| $z_j - c_j$ |  | $z_0 = \frac{157}{9}$ | $0$ | $\frac{58}{9} \Uparrow$ | $0$ | $-\frac{4}{9}$ | $-\frac{5}{3}$ | $0$ |  |

Tablo 14.9: İkinci iterasyon tablosu

**Üçüncü iterasyon.** Pivot satırı $\tfrac{13}{3}$’e bölünür, yani $\tfrac{3}{13}$ ile çarpılır ve $c_B$ değeri $c_2 = -3$ olan $x_2$ satırı olur: $$\left(1 \mid 0,\ 1,\ 0,\ -\tfrac{1}{13},\ 0,\ \tfrac{3}{13}\right).$$ $x_1$ satırına yeni pivot satırının $\tfrac{1}{9}$ katı eklenir, $x_3$ satırından $\tfrac{11}{18}$ katı çıkarılır: $$\begin{aligned}
x_1&: \ \left(\tfrac{35}{9} + \tfrac{1}{9} \mid 1,\ 0,\ 0,\ \tfrac{1}{9} - \tfrac{1}{117},\ -\tfrac{1}{3},\ \tfrac{3}{117}\right) \\[1mm]
&\quad = \left(4 \mid 1,\ 0,\ 0,\ \tfrac{4}{39},\ -\tfrac{1}{3},\ \tfrac{1}{39}\right), \\[1mm]
x_3&: \ \left(\tfrac{29}{18} - \tfrac{11}{18} \mid 0,\ 0,\ 1,\ -\tfrac{1}{9} + \tfrac{11}{234},\ -\tfrac{1}{6},\ -\tfrac{33}{234}\right) \\[1mm]
&\quad = \left(1 \mid 0,\ 0,\ 1,\ -\tfrac{5}{78},\ -\tfrac{1}{6},\ -\tfrac{11}{78}\right).
\end{aligned}$$ $\vec{c}_B = (2, 6, -3)$ ile kriterler: $$\begin{aligned}
z_4 - c_4 &= 2 \cdot \tfrac{4}{39} + 6 \cdot \left(-\tfrac{5}{78}\right) + (-3) \cdot \left(-\tfrac{1}{13}\right) \\[1mm]
&= \tfrac{8}{39} - \tfrac{15}{39} + \tfrac{9}{39} = \tfrac{2}{39}, \\[1mm]
z_5 - c_5 &= 2 \cdot \left(-\tfrac{1}{3}\right) + 6 \cdot \left(-\tfrac{1}{6}\right) + (-3) \cdot 0 = -\tfrac{5}{3}, \\[1mm]
z_6 - c_6 &= 2 \cdot \tfrac{1}{39} + 6 \cdot \left(-\tfrac{11}{78}\right) + (-3) \cdot \tfrac{3}{13} \\[1mm]
&= \tfrac{2}{39} - \tfrac{33}{39} - \tfrac{27}{39} = -\tfrac{58}{39}, \\[1mm]
z_0 &= 2 \cdot 4 + 6 \cdot 1 + (-3) \cdot 1 = 11 .
\end{aligned}$$ Pozitif kriter $z_4 - c_4 = \tfrac{2}{39}$ kaldığı için $v_4$ baza girer. $v_4$ sütununda yalnız $x_1$ satırının elemanı pozitiftir; oran $\tfrac{4}{4/39} = 39$’dur. $v_1$ bazdan çıkar; pivot $\tfrac{4}{39}$’dur.

|  |  | $c_j$ | $2$ | $-3$ | $6$ | $0$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ | Oran |
| $x_1$ | $2$ | $4$ | $1$ | $0$ | $0$ | $[\frac{4}{39}]$ | $-\frac{1}{3}$ | $\frac{1}{39}$ | $\frac{4}{4/39} \Rightarrow$ |
| $x_3$ | $6$ | $1$ | $0$ | $0$ | $1$ | $-\frac{5}{78}$ | $-\frac{1}{6}$ | $-\frac{11}{78}$ | $-$ |
| $x_2$ | $-3$ | $1$ | $0$ | $1$ | $0$ | $-\frac{1}{13}$ | $0$ | $\frac{3}{13}$ | $-$ |
| $z_j - c_j$ |  | $z_0 = 11$ | $0$ | $0$ | $0$ | $\frac{2}{39} \Uparrow$ | $-\frac{5}{3}$ | $-\frac{58}{39}$ |  |

Tablo 14.10: Üçüncü iterasyon tablosu

**Dördüncü iterasyon.** Pivot satırı $\tfrac{39}{4}$ ile çarpılır ve $c_B$ değeri $c_4 = 0$ olan $x_4$ satırı olur: $$\left(39 \mid \tfrac{39}{4},\ 0,\ 0,\ 1,\ -\tfrac{13}{4},\ \tfrac{1}{4}\right).$$ $x_3$ satırına yeni pivot satırının $\tfrac{5}{78}$ katı, $x_2$ satırına $\tfrac{1}{13}$ katı eklenir: $$\begin{aligned}
x_3&: \ \left(1 + \tfrac{5}{2} \mid \tfrac{5}{8},\ 0,\ 1,\ 0,\ -\tfrac{1}{6} - \tfrac{5}{24},\ -\tfrac{11}{78} + \tfrac{5}{312}\right) \\[1mm]
&\quad = \left(\tfrac{7}{2} \mid \tfrac{5}{8},\ 0,\ 1,\ 0,\ -\tfrac{3}{8},\ -\tfrac{1}{8}\right), \\[1mm]
x_2&: \ \left(1 + 3 \mid \tfrac{3}{4},\ 1,\ 0,\ 0,\ -\tfrac{1}{4},\ \tfrac{3}{13} + \tfrac{1}{52}\right) \\[1mm]
&\quad = \left(4 \mid \tfrac{3}{4},\ 1,\ 0,\ 0,\ -\tfrac{1}{4},\ \tfrac{1}{4}\right).
\end{aligned}$$ $\vec{c}_B = (0, 6, -3)$ ile kriterler: $$\begin{aligned}
z_1 - c_1 &= 0 + 6 \cdot \tfrac{5}{8} + (-3) \cdot \tfrac{3}{4} - 2 = \tfrac{15}{4} - \tfrac{9}{4} - 2 = -\tfrac{1}{2}, \\[1mm]
z_5 - c_5 &= 0 + 6 \cdot \left(-\tfrac{3}{8}\right) + (-3) \cdot \left(-\tfrac{1}{4}\right) - 0 = -\tfrac{3}{2}, \\[1mm]
z_6 - c_6 &= 0 + 6 \cdot \left(-\tfrac{1}{8}\right) + (-3) \cdot \tfrac{1}{4} - 0 = -\tfrac{3}{2}, \\[1mm]
z_0 &= 0 \cdot 39 + 6 \cdot \tfrac{7}{2} + (-3) \cdot 4 = 9 .
\end{aligned}$$

|  |  | $c_j$ | $2$ | $-3$ | $6$ | $0$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | $v_6$ |
| $x_4$ | $0$ | $39$ | $\frac{39}{4}$ | $0$ | $0$ | $1$ | $-\frac{13}{4}$ | $\frac{1}{4}$ |
| $x_3$ | $6$ | $\frac{7}{2}$ | $\frac{5}{8}$ | $0$ | $1$ | $0$ | $-\frac{3}{8}$ | $-\frac{1}{8}$ |
| $x_2$ | $-3$ | $4$ | $\frac{3}{4}$ | $1$ | $0$ | $0$ | $-\frac{1}{4}$ | $\frac{1}{4}$ |
| $z_j - c_j$ |  | $z_0 = 9$ | $-\frac{1}{2}$ | $0$ | $0$ | $0$ | $-\frac{3}{2}$ | $-\frac{3}{2}$ |

Tablo 14.11: Dördüncü iterasyon tablosu (optimal tablo)

**Sonuç.** Dördüncü iterasyon tablosunda ([Tablo 14.11](#tbl-als-bym-optimal)) bütün $z_j - c_j \le 0$’dır ve bazda yapay değişken yoktur. [Teorem 5.1](buyuk-m-yontemi.md#thm-bym-optimal) gereği optimal çözüm $$X^{*} = (x_1, \dots, x_6) = \left(0, 4, \tfrac{7}{2}, 39, 0, 0\right),
\qquad
\min z = -3 \cdot 4 + 6 \cdot \tfrac{7}{2} = 9$$ dur. Baz dışındaki bütün kriterler negatif olduğundan optimal çözüm tektir ([Sonuç 7.1](sinirsiz-ve-alternatif-optimal-cozum.md#cor-sao-tek)). Kısıtlarda kontrol edelim: $3 \cdot 0 - 16 - 21 = -37 \le 2$ (aradaki fark $x_4 = 39$), $0 + 4 + 7 = 11$ (ikinci kısıt tam sağlanır, $x_5 = 0$) ve $0 + 12 - 7 = 5$ (üçüncü kısıt tam sağlanır, $x_6 = 0$). Amaç değeri iterasyonlar boyunca $$11M \to \tfrac{29}{3}M + \tfrac{4}{3} \to \tfrac{157}{9} \to 11 \to 9$$ diye azaldı.

$\blacksquare$

## 14.5 Duyarlılık Analizi

Optimal tablo yalnız çözümü vermez; problemin verileri değişince bu çözümün ne kadar dayanıklı olduğunu da söyler. Aşağıdaki üç alıştırma aynı problem üzerindedir: önce problem çözülür, sonra amaç fonksiyonu katsayıları ve sağ taraf sabitleri için [Duyarlılık analizi](./duyarlilik-analizi.md) bölümündeki inceleme yapılır.

**Alıştırma 14.6 (Duyarlılık problemi: M yöntemiyle çözüm)** $$\begin{aligned}
7x_1 + 6x_2 &\le 84 \\
4x_1 + 2x_2 &\ge 32 \\
x_1, x_2 &\ge 0 \\
\max z &= 11x_1 + 4x_2
\end{aligned}$$ lineer programlama problemini M yöntemiyle çözünüz.

Çözüm

Uygun bölge (8, 0), (12, 0) ve (12/5, 56/5) köşeli üçgendir. Büyük M yöntemi uygun bölgenin dışındaki X₀ = (0, 0) noktasından başlar, X₁ = (8, 0) köşesine ve oradan optimal X₂ = (12, 0) köşesine gider. Kesikli doğrular z = 11x₁ + 4x₂ amaç fonksiyonunun z = 88 ve z = 132 seviye doğrularıdır.

**Kanonik form.** Maksimum probleminde bütün kısıtlar $\le$ olmalıdır; ikinci kısıtı $-1$ ile çarparsak kanonik form $7x_1 + 6x_2 \le 84$, $-4x_1 - 2x_2 \le -32$ olur. Sağ tarafta $-32$ bulunduğu için standart forma verilen problemden geçeriz.

**Standart form.** Birinci kısıta $x_3$ aylak değişkenini ekler, ikinci kısıttan $x_4$ artık değişkenini çıkarırız: $$\begin{aligned}
7x_1 + 6x_2 + x_3 &= 84 \\
4x_1 + 2x_2 - x_4 &= 32 \\
x_1, x_2, x_3, x_4 &\ge 0 \\
\max z &= 11x_1 + 4x_2 + 0x_3 + 0x_4
\end{aligned}$$

**Simpleks yöntem ile çözülebilir hal.** $v_3 = (1, 0)^T$ birim sütundur, ama ikinci denklemde $x_4$’ün katsayısı $-1$’dir. İkinci denkleme $x_{u_1}$ yapay değişkenini ekleriz; maksimum problemi olduğundan amaç katsayısı $-M$’dir: $$\begin{aligned}
7x_1 + 6x_2 + x_3 &= 84 \\
4x_1 + 2x_2 - x_4 + x_{u_1} &= 32 \\
x_1, x_2, x_3, x_4, x_{u_1} &\ge 0 \\
\max z &= 11x_1 + 4x_2 + 0x_3 \\
&\quad + 0x_4 - Mx_{u_1}
\end{aligned}$$ Başlangıç bazı $B_0 = (v_3, v_{u_1})$, başlangıç çözümü $x_3 = 84$, $x_{u_1} = 32$’dir.

**Başlangıç tablosu.** $\vec{c}_B = (0, -M)$ ile $$\begin{aligned}
z_1 - c_1 &= (0 \cdot 7 + (-M) \cdot 4) - 11 = -4M - 11, \\[1mm]
z_2 - c_2 &= (0 \cdot 6 + (-M) \cdot 2) - 4 = -2M - 4, \\[1mm]
z_4 - c_4 &= (0 \cdot 0 + (-M) \cdot (-1)) - 0 = M, \\[1mm]
z_0 &= 0 \cdot 84 + (-M) \cdot 32 = -32M .
\end{aligned}$$ Maksimum probleminde en negatif $z_j - c_j$ girer ve bütün $z_j - c_j \ge 0$ olunca durulur. Negatif kriterler $-4M - 11$ ve $-2M - 4$’tür; $M$’nin katsayıları $-4 < -2$ olduğundan en negatifi $-4M - 11$’dir ve $v_1$ baza girer. Oranlar $\tfrac{84}{7} = 12$ ve $\tfrac{32}{4} = 8$’dir; $v_{u_1}$ bazdan çıkar ve pivot $4$’tür.

|  |  | $c_j$ | $11$ | $4$ | $0$ | $0$ | $-M$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_{u_1}$ | Oran |
| $x_3$ | $0$ | $84$ | $7$ | $6$ | $1$ | $0$ | $0$ | $\frac{84}{7}$ |
| $x_{u_1}$ | $-M$ | $32$ | $[4]$ | $2$ | $0$ | $-1$ | $1$ | $\frac{32}{4} \Rightarrow$ |
| $z_j - c_j$ |  | $z_0 = -32M$ | $-4M-11 \Uparrow$ | $-2M-4$ | $0$ | $M$ | $0$ |  |

Tablo 14.12: Başlangıç tablosu

**Birinci iterasyon.** Pivot satırı $4$’e bölünür ve $c_B$ değeri $11$ olan $x_1$ satırı olur: $\left(8 \mid 1, \tfrac{1}{2}, 0, -\tfrac{1}{4}\right)$. $v_{u_1}$ sütunu artık yazılmaz. $x_3$ satırından yeni pivot satırının $7$ katı çıkarılır: $$\left(84 - 56 \mid 0,\ 6 - \tfrac{7}{2},\ 1,\ \tfrac{7}{4}\right) = \left(28 \mid 0,\ \tfrac{5}{2},\ 1,\ \tfrac{7}{4}\right).$$ $\vec{c}_B = (0, 11)$ ile $$\begin{aligned}
z_2 - c_2 &= 0 \cdot \tfrac{5}{2} + 11 \cdot \tfrac{1}{2} - 4 = \tfrac{3}{2}, \\[1mm]
z_4 - c_4 &= 0 \cdot \tfrac{7}{4} + 11 \cdot \left(-\tfrac{1}{4}\right) - 0 = -\tfrac{11}{4}, \\[1mm]
z_0 &= 0 \cdot 28 + 11 \cdot 8 = 88 .
\end{aligned}$$ Tek negatif kriter $-\tfrac{11}{4}$ olduğundan $v_4$ baza girer. $x_1$ satırındaki $-\tfrac{1}{4}$ teste girmez; tek oran $\tfrac{28}{7/4} = 16$’dır. $v_3$ bazdan çıkar; pivot $\tfrac{7}{4}$’tür.

|  |  | $c_j$ | $11$ | $4$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ | Oran |
| $x_3$ | $0$ | $28$ | $0$ | $\frac{5}{2}$ | $1$ | $[\frac{7}{4}]$ | $\frac{28}{7/4} \Rightarrow$ |
| $x_1$ | $11$ | $8$ | $1$ | $\frac{1}{2}$ | $0$ | $-\frac{1}{4}$ | $-$ |
| $z_j - c_j$ |  | $z_0 = 88$ | $0$ | $\frac{3}{2}$ | $0$ | $-\frac{11}{4} \Uparrow$ |  |

Tablo 14.13: Birinci iterasyon tablosu

**İkinci iterasyon.** Pivot satırı $\tfrac{4}{7}$ ile çarpılır ve $c_B$ değeri $0$ olan $x_4$ satırı olur: $\left(16 \mid 0, \tfrac{10}{7}, \tfrac{4}{7}, 1\right)$. $x_1$ satırına yeni pivot satırının $\tfrac{1}{4}$ katı eklenir: $$\left(8 + 4 \mid 1,\ \tfrac{1}{2} + \tfrac{5}{14},\ \tfrac{1}{7},\ 0\right) = \left(12 \mid 1,\ \tfrac{6}{7},\ \tfrac{1}{7},\ 0\right).$$ $\vec{c}_B = (0, 11)$ ile $$\begin{aligned}
z_2 - c_2 &= 0 \cdot \tfrac{10}{7} + 11 \cdot \tfrac{6}{7} - 4 = \tfrac{38}{7}, \\[1mm]
z_3 - c_3 &= 0 \cdot \tfrac{4}{7} + 11 \cdot \tfrac{1}{7} - 0 = \tfrac{11}{7}, \\[1mm]
z_0 &= 0 \cdot 16 + 11 \cdot 12 = 132 .
\end{aligned}$$

|  |  | $c_j$ | $11$ | $4$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| $x_4$ | $0$ | $16$ | $0$ | $\frac{10}{7}$ | $\frac{4}{7}$ | $1$ |
| $x_1$ | $11$ | $12$ | $1$ | $\frac{6}{7}$ | $\frac{1}{7}$ | $0$ |
| $z_j - c_j$ |  | $z_0 = 132$ | $0$ | $\frac{38}{7}$ | $\frac{11}{7}$ | $0$ |

Tablo 14.14: İkinci iterasyon tablosu (optimal tablo)

**Sonuç.** Negatif simpleks kriteri kalmadı; maksimum problemi için optimal tabloya ([Tablo 14.14](#tbl-als-dya-optimal)) ulaşıldı. Bazda yapay değişken yoktur ([Teorem 5.1](buyuk-m-yontemi.md#thm-bym-optimal)) ve optimal çözüm $$x_1 = 12, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 16, \qquad \max z = 11 \cdot 12 = 132$$ dir. Birinci kısıt tam sağlanır ($7 \cdot 12 = 84$), ikinci kısıtın gereksinimi $x_4 = 16$ birim aşılır ($4 \cdot 12 = 48 = 32 + 16$). Baz dışındaki kriterler $\tfrac{38}{7}$ ve $\tfrac{11}{7}$ pozitif olduğundan optimal çözüm tektir ([Sonuç 7.1](sinirsiz-ve-alternatif-optimal-cozum.md#cor-sao-tek)).

Grafikle karşılaştıralım. Uygun bölge $(8, 0)$, $(12, 0)$ ve iki kısıt doğrusunun kesiştiği $(\tfrac{12}{5}, \tfrac{56}{5})$ köşeli üçgendir; bu köşelerde $z$ sırasıyla $88$, $132$ ve $\tfrac{132}{5} + \tfrac{224}{5} = \tfrac{356}{5}$ değerini alır. En büyüğü gerçekten $132$’dir. Başlangıç tablosunun çözümü $(x_1, x_2) = (0, 0)$ bölgenin dışındadır, birinci iterasyon tablosununki $(8, 0)$ köşesidir.

$\blacksquare$

**Alıştırma 14.7 (Amaç fonksiyonu katsayıları için duyarlılık analizi)** Önceki alıştırmada ([Alıştırma 14.6](#exr-als-dya-a)) çözülen $$\begin{aligned}
7x_1 + 6x_2 &\le 84 \\
4x_1 + 2x_2 &\ge 32 \\
x_1, x_2 &\ge 0 \\
\max z &= 11x_1 + 4x_2
\end{aligned}$$ problemi için amaç fonksiyonu katsayılarında duyarlılık analizi yapınız: her $c_j$ katsayısı, diğerleri sabit kalırken hangi aralıkta değişirse optimal çözüm değişmez?

Çözüm

Bir $c_j$ değişince tablonun gövdesi, yani $v_0$ sütunu ve $y_{ij}$ değerleri değişmez; bunlar yalnız kısıtlara ve baza bağlıdır. Değişen yalnız $z_j - c_j$ satırı ve amaç değeridir. Dolayısıyla optimal tablo ([Tablo 14.14](#tbl-als-dya-optimal)), maksimum probleminde bütün $z_j - c_j \ge 0$ kaldığı sürece optimal kalır ve aynı çözümü, $x_1 = 12$, $x_2 = 0$’ı verir. Optimal tabloda temel değişkenler $x_4$ ve $x_1$, temel dışı değişkenler $x_2$ ve $x_3$’tür.

**Temel dışı değişken $x_2$.** Optimal tabloda $c_2 = 4$ yerine $c_2$ yazalım. $x_2$ bazda olmadığından $\vec{c}_B = (0, 11)$ değişmez ve yalnız $v_2$ sütununun kriteri etkilenir: $$\begin{aligned}
z_1 - c_1 &= (0, 11) \begin{bmatrix} 0 \\ 1 \end{bmatrix} - 11 = 0, \\[1mm]
z_2 - c_2 &= (0, 11) \begin{bmatrix} \frac{10}{7} \\ \frac{6}{7} \end{bmatrix} - c_2 = \frac{66}{7} - c_2 \ge 0 \;\Rightarrow\; c_2 \le \frac{66}{7}, \\[1mm]
z_3 - c_3 &= (0, 11) \begin{bmatrix} \frac{4}{7} \\ \frac{1}{7} \end{bmatrix} - 0 = \frac{11}{7}, \\[1mm]
z_4 - c_4 &= (0, 11) \begin{bmatrix} 1 \\ 0 \end{bmatrix} - 0 = 0 .
\end{aligned}$$

|  |  | $c_j$ | $11$ | $c_2$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| $x_4$ | $0$ | $16$ | $0$ | $\frac{10}{7}$ | $\frac{4}{7}$ | $1$ |
| $x_1$ | $11$ | $12$ | $1$ | $\frac{6}{7}$ | $\frac{1}{7}$ | $0$ |
| $z_j - c_j$ |  | $z_0 = 132$ | $0$ | $\frac{66}{7} - c_2$ | $\frac{11}{7}$ | $0$ |

Tablo 14.15: Temel dışı bir değişkenin değişim aralığı

$c_2 \le \tfrac{66}{7}$ alınırsa optimumluk bozulmaz. Yani $x_2$’nin birim kârı $\tfrac{66}{7} \approx 9{,}43$’ü aşmadıkça $x_2$ üretmek kârlı değildir; aştığında $v_2$ baza girer ve çözüm değişir. $c_2 = \tfrac{66}{7}$ sınırında $z_2 - c_2 = 0$ olur: $(12, 0)$ ile $(\tfrac{12}{5}, \tfrac{56}{5})$ köşeleri aynı amaç değerini, $132$’yi verir.

**Temel değişken $x_1$.** Şimdi $c_1 = 11$ yerine $c_1$ yazalım. $x_1$ bazda olduğundan $c_1$ hem $c_j$ satırında hem $c_B$ sütununda görünür ve bütün kriterler yeniden hesaplanır; $\vec{c}_B = (0, c_1)$: $$\begin{aligned}
z_1 - c_1 &= (0, c_1) \begin{bmatrix} 0 \\ 1 \end{bmatrix} - c_1 = c_1 - c_1 = 0, \\[1mm]
z_2 - c_2 &= (0, c_1) \begin{bmatrix} \frac{10}{7} \\ \frac{6}{7} \end{bmatrix} - 4 = \frac{6c_1}{7} - 4 = \frac{6c_1 - 28}{7}, \\[1mm]
z_3 - c_3 &= (0, c_1) \begin{bmatrix} \frac{4}{7} \\ \frac{1}{7} \end{bmatrix} - 0 = \frac{c_1}{7}, \\[1mm]
z_4 - c_4 &= (0, c_1) \begin{bmatrix} 1 \\ 0 \end{bmatrix} - 0 = 0 .
\end{aligned}$$

|  |  | $c_j$ | $c_1$ | $4$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| $x_4$ | $0$ | $16$ | $0$ | $\frac{10}{7}$ | $\frac{4}{7}$ | $1$ |
| $x_1$ | $c_1$ | $12$ | $1$ | $\frac{6}{7}$ | $\frac{1}{7}$ | $0$ |
| $z_j - c_j$ |  | $z_0 = 12c_1$ | $0$ | $\frac{6c_1}{7} - 4$ | $\frac{c_1}{7}$ | $0$ |

Tablo 14.16: Temelde olan $x_1$ değişkeninin değişim aralığı

İki koşul gerekir: $$\frac{6c_1 - 28}{7} \ge 0 \;\Rightarrow\; c_1 \ge \frac{14}{3}, \qquad \frac{c_1}{7} \ge 0 \;\Rightarrow\; c_1 \ge 0 .$$ İkisinin birden sağlanması için $c_1 \ge \tfrac{14}{3}$ olmalıdır. $c_1 \ge \tfrac{14}{3}$ olursa optimumluk bozulmaz; optimal çözüm yine $(12, 0)$ ve optimal değer $12c_1$’dir.

**Temel değişken $x_4$.** $x_4$ bir artık değişkendir ve amaçtaki katsayısı $0$’dır; aynı soruyu onun katsayısı için de sorabiliriz. $c_4 = 0$ yerine $c_4$ yazalım; $\vec{c}_B = (c_4, 11)$: $$\begin{aligned}
z_1 - c_1 &= (c_4, 11) \begin{bmatrix} 0 \\ 1 \end{bmatrix} - 11 = 0, \\[1mm]
z_2 - c_2 &= (c_4, 11) \begin{bmatrix} \frac{10}{7} \\ \frac{6}{7} \end{bmatrix} - 4 = \frac{10c_4 + 66}{7} - 4 = \frac{10c_4 + 38}{7}, \\[1mm]
z_3 - c_3 &= (c_4, 11) \begin{bmatrix} \frac{4}{7} \\ \frac{1}{7} \end{bmatrix} - 0 = \frac{4c_4 + 11}{7}, \\[1mm]
z_4 - c_4 &= (c_4, 11) \begin{bmatrix} 1 \\ 0 \end{bmatrix} - c_4 = 0 .
\end{aligned}$$

|  |  | $c_j$ | $11$ | $4$ | $0$ | $c_4$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $x_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2$ | $v_3$ | $v_4$ |
| $x_4$ | $c_4$ | $16$ | $0$ | $\frac{10}{7}$ | $\frac{4}{7}$ | $1$ |
| $x_1$ | $11$ | $12$ | $1$ | $\frac{6}{7}$ | $\frac{1}{7}$ | $0$ |
| $z_j - c_j$ |  | $z_0 = 16c_4 + 132$ | $0$ | $\frac{10c_4 + 38}{7}$ | $\frac{4c_4 + 11}{7}$ | $0$ |

Tablo 14.17: Temelde olan $x_4$ değişkeninin değişim aralığı

Koşullar $$10c_4 + 38 \ge 0 \;\Rightarrow\; c_4 \ge -\frac{19}{5}, \qquad 4c_4 + 11 \ge 0 \;\Rightarrow\; c_4 \ge -\frac{11}{4}$$ dir. $-\tfrac{11}{4} = -2{,}75$ sayısı $-\tfrac{19}{5} = -3{,}8$’den büyük olduğundan ikisi birden $c_4 \ge -\tfrac{11}{4}$ iken sağlanır. $c_4 \ge -\tfrac{11}{4}$ olursa optimumluk bozulmaz.

**Temel dışı değişken $x_3$.** Son olarak aylak değişken $x_3$’ün katsayısını $c_3$ ile gösterelim. $x_3$ bazda olmadığından yalnız kendi kriteri değişir: $z_3 - c_3 = \tfrac{11}{7} - c_3 \ge 0$, yani $c_3 \le \tfrac{11}{7}$.

**Özet.**

|   Katsayı   | Şimdiki değer | Optimumluğun bozulmadığı aralık |
|:-----------:|:-------------:|:-------------------------------:|
| $c_1$ |  $11$  |           $c_1 \ge \frac{14}{3}$           |
| $c_2$ |  $4$  |           $c_2 \le \frac{66}{7}$           |
| $c_3$ |  $0$  |           $c_3 \le \frac{11}{7}$           |
| $c_4$ |  $0$  |           $c_4 \ge -\frac{11}{4}$           |

Tablo 14.18: Amaç fonksiyonu katsayılarının değişim aralıkları

Her aralık katsayının şimdiki değerini içerir; bu, hesabın kolay bir sağlamasıdır. Aralığın içinde optimal çözüm $(x_1, x_2) = (12, 0)$ olarak kalır, yalnız optimal değer değişebilir.

$\blacksquare$

**Alıştırma 14.8 (Sağ taraf sabitleri için duyarlılık analizi)** Önceki alıştırmalardaki $$\begin{aligned}
7x_1 + 6x_2 &\le 84 \\
4x_1 + 2x_2 &\ge 32 \\
x_1, x_2 &\ge 0 \\
\max z &= 11x_1 + 4x_2
\end{aligned}$$ problemi için sağ taraf sabitlerinde duyarlılık analizi yapınız: $b_1 = 84$ ve $b_2 = 32$ sabitlerinin her biri, diğeri sabit kalırken hangi aralıkta değişirse optimal baz değişmez?

Çözüm

Bir $b_i$ değişince $z_j - c_j$ satırı değişmez, çünkü o satır yalnız $\vec{c}_B$’ye ve $y_{ij}$ değerlerine bağlıdır. Optimal tablonun ([Tablo 14.14](#tbl-als-dya-optimal)) optimallik koşulu bu yüzden korunur. Değişen $v_0$ sütunudur: $B$ optimal bazın matrisi olmak üzere yeni temel çözüm $B^{-1}\vec{b}$’dir. Baz uygun kalmalı, yani $$B^{-1}\vec{b} \ge 0$$ eşitsizliği gerçeklenmelidir.

**$B$ matrisi.** Temel değişkenler tablodaki sırayla $x_4$ ve $x_1$’dir. $B$’nin sütunları bu değişkenlerin standart formdaki ([Alıştırma 14.6](#exr-als-dya-a)) sütunlarıdır: $4x_1 + 2x_2 - x_4 = 32$ denkleminden $v_4 = (0, -1)^T$ ve $v_1 = (7, 4)^T$. O halde $$B = [\, v_4 \ \ v_1 \,] = \begin{bmatrix} 0 & 7 \\ -1 & 4 \end{bmatrix}, \qquad \det B = 0 \cdot 4 - 7 \cdot (-1) = 7 \ne 0,$$ dolayısıyla $B$’nin tersi vardır. $2 \times 2$ matrisin tersi formülüyle $$B^{-1} = \frac{1}{7} \begin{bmatrix} 4 & -7 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} \frac{4}{7} & -1 \\ \frac{1}{7} & 0 \end{bmatrix}$$ bulunur. Kontrol: $B B^{-1} = \begin{bmatrix} 0 + 1 & 0 + 0 \\ -\frac{4}{7} + \frac{4}{7} & 1 + 0 \end{bmatrix} = I$. $B^{-1}$’in birinci sütununun optimal tablodaki $v_3$ sütunu $\left(\tfrac{4}{7}, \tfrac{1}{7}\right)^T$ olduğuna da dikkat edelim: başlangıçta birim sütun olan $v_3$’ün son tablodaki katsayıları $B^{-1}v_3$’tür. Şimdiki değerlerle $$B^{-1}\vec{b} = \left(\tfrac{4}{7} \cdot 84 - 32,\ \tfrac{1}{7} \cdot 84\right)^T = (16, 12)^T$$ bulunur; bu, tablodaki $v_0$ sütununun ta kendisidir.

**$b_1$ için inceleme.** $b_2 = 32$ sabit, $b_1$ değişken: $$B^{-1}\vec{b} = \begin{bmatrix} \frac{4}{7} & -1 \\ \frac{1}{7} & 0 \end{bmatrix} \begin{bmatrix} b_1 \\ 32 \end{bmatrix} = \begin{bmatrix} \frac{4}{7}b_1 - 32 \\ \frac{1}{7}b_1 \end{bmatrix} \ge 0 .$$ Birinci bileşenden $\tfrac{4}{7}b_1 \ge 32$, yani $b_1 \ge 56$; ikinci bileşenden $b_1 \ge 0$. İkisi birlikte $b_1 \ge 56$ verir. Bu aralıkta optimal çözüm $x_1 = \tfrac{b_1}{7}$, $x_4 = \tfrac{4}{7}b_1 - 32$ ve optimal değer $z = \tfrac{11}{7}b_1$’dir. Anlamı şudur: $x_2 = 0$ iken birinci kısıt $x_1 \le \tfrac{b_1}{7}$, ikinci kısıt $x_1 \ge 8$ der; $b_1 < 56$ olunca $\tfrac{b_1}{7} < 8$ olur ve bu köşe uygunluğunu kaybeder.

**$b_2$ için inceleme.** $b_1 = 84$ sabit, $b_2$ değişken: $$B^{-1}\vec{b} = \begin{bmatrix} \frac{4}{7} & -1 \\ \frac{1}{7} & 0 \end{bmatrix} \begin{bmatrix} 84 \\ b_2 \end{bmatrix} = \begin{bmatrix} 48 - b_2 \\ 12 \end{bmatrix} \ge 0 .$$ Birinci bileşenden $b_2 \le 48$; ikinci bileşen $12 \ge 0$ her zaman doğrudur. Demek ki $b_2 \le 48$ olmalıdır. Bu aralıkta çözüm $x_1 = 12$, $x_4 = 48 - b_2$ ve $z = 132$ olarak kalır: $x_1 = 12$ için $4x_1 = 48$’dir ve gereksinim $48$’i aşmadıkça karşılanır.

**Özet.**

|    Sabit    | Şimdiki değer | Optimal bazın korunduğu aralık | Optimal değer |
|:-----------:|:-------------:|:------------------------------:|:-------------:|
| $b_1$ |  $84$  |          $b_1 \ge 56$           |  $z = \frac{11}{7}b_1$  |
| $b_2$ |  $32$  |          $b_2 \le 48$           |  $z = 132$  |

Tablo 14.19: Sağ taraf sabitlerinin değişim aralıkları

Sonuç olarak $b_1 \ge 56$ ve $b_2 \le 48$ olursa optimumluk bozulmaz.

$\blacksquare$

## 14.6 Dualite

Bir problemi çözmenin bir yolu da onun dualini çözmektir. Aşağıdaki iki alıştırmada önce dual problem kurulur, sonra dualin optimal tablosundan esas problemin çözümü okunur ([Dualite](./dualite.md)).

**Alıştırma 14.9 (Dual problemin kurulması)** $$\begin{aligned}
2x_1 + x_2 &\ge 6 \\
x_1 + x_2 &= 3 \\
x_1 + 2x_2 &\le 5 \\
x_1, x_2 &\ge 0 \\
\min z &= 3x_1 + x_2
\end{aligned}$$ lineer programlama probleminin dual problemini oluşturunuz.

Çözüm

**Kanonik form.** Amaç fonksiyonu minimum olduğu için kanonik formda ([Tanım 1.6](lineer-programlama-problemi.md#def-lpp-kanonik-form)) bütün kısıtlar $\ge$ olmalıdır. Üçüncü kısıtı $-1$ ile çarparız: $-x_1 - 2x_2 \ge -5$. Eşitlik kısıtı ise iki eşitsizliğe ayrılır: $x_1 + x_2 \ge 3$ ve $x_1 + x_2 \le 3$; ikincisini $-1$ ile çarparsak $-x_1 - x_2 \ge -3$ olur. Kanonik form: $$\begin{aligned}
2x_1 + x_2 &\ge 6 \\
x_1 + x_2 &\ge 3 \\
-x_1 - x_2 &\ge -3 \\
-x_1 - 2x_2 &\ge -5 \\
x_1, x_2 &\ge 0 \\
\min z &= 3x_1 + x_2
\end{aligned}$$

**Dual problem.** Kanonik formdaki $\min z = \vec{c}^{\,T}\vec{x}$, $A\vec{x} \ge \vec{b}$, $\vec{x} \ge 0$ probleminin duali $\max g = \vec{b}^{\,T}\vec{y}$, $A^T\vec{y} \le \vec{c}$, $\vec{y} \ge 0$ problemidir: her kısıta bir dual değişken karşılık gelir, katsayılar matrisi transpoze edilir, sağ taraflar ile amaç katsayıları yer değiştirir. Burada $$A = \begin{bmatrix} 2 & 1 \\ 1 & 1 \\ -1 & -1 \\ -1 & -2 \end{bmatrix}, \qquad
\vec{b} = \begin{bmatrix} 6 \\ 3 \\ -3 \\ -5 \end{bmatrix}, \qquad
\vec{c} = \begin{bmatrix} 3 \\ 1 \end{bmatrix}$$ dir. Dört kısıta sırasıyla $y_1$, $y_2'$, $y_2''$, $y_3$ dual değişkenlerini verelim. $A^T$’nin satırları $A$’nın sütunlarıdır; dual problem $$\begin{aligned}
2y_1 + y_2' - y_2'' - y_3 &\le 3 \\
y_1 + y_2' - y_2'' - 2y_3 &\le 1 \\
y_1, y_2', y_2'', y_3 &\ge 0 \\
\max g &= 6y_1 + 3y_2' - 3y_2'' - 5y_3
\end{aligned}$$ olur.

**İşaretsiz değişkenle yazım.** $y_2'$ ve $y_2''$ her yerde $y_2' - y_2''$ farkı olarak görünür. $y_2 = y_2' - y_2''$ dersek $y_2$ her işareti alabilir ([İşaret kısıtlaması olmayan değişkenler](./isaret-kisitlamasiz-degiskenler.md)). Dual problem kısaca $$\begin{aligned}
2y_1 + y_2 - y_3 &\le 3 \\
y_1 + y_2 - 2y_3 &\le 1 \\
y_1, y_3 \ge 0, \quad y_2 &\ \text{işaretçe kısıtsız} \\
\max g &= 6y_1 + 3y_2 - 5y_3
\end{aligned}$$ biçiminde yazılır. Yani esas problemin eşitlik kısıtına işaretçe kısıtsız bir dual değişken karşılık gelir.

$\blacksquare$

**Alıştırma 14.10 (Dual problemi çözerek esas problemin çözümü)** Önceki alıştırmada ([Alıştırma 14.9](#exr-als-dua-a)) kurulan dual problemi simpleks yöntemle çözünüz ve dualin optimal tablosundan esas problemin, yani $$\begin{aligned}
2x_1 + x_2 &\ge 6 \\
x_1 + x_2 &= 3 \\
x_1 + 2x_2 &\le 5 \\
x_1, x_2 &\ge 0 \\
\min z &= 3x_1 + x_2
\end{aligned}$$ probleminin çözümüne geçiniz.

Çözüm

Açık boyalı bölge 2x₁ + x₂ ≥ 6 ve x₁ + 2x₂ ≤ 5 eşitsizliklerinin ortak bölgesidir. Eşitlik kısıtı yüzünden uygun çözümler x₁ + x₂ = 3 doğrusu üzerinde olmalıdır ve bu doğru bölgeye yalnız (3, 0) noktasında değer: esas problemin tek uygun çözümü (3, 0)'dır.

**Standart form ve çözülebilir hal.** İşaretsiz $y_2$ yerine $y_2 = y_2' - y_2''$ ($y_2', y_2'' \ge 0$) yazılmış duali kullanıyoruz. İki $\le$ kısıta $y_4$ ve $y_5$ aylak değişkenlerini ekleriz: $$\begin{aligned}
2y_1 + y_2' - y_2'' - y_3 + y_4 &= 3 \\
y_1 + y_2' - y_2'' - 2y_3 + y_5 &= 1 \\
y_1, y_2', y_2'', y_3, y_4, y_5 &\ge 0 \\
\max g &= 6y_1 + 3y_2' - 3y_2'' - 5y_3 \\
&\quad + 0y_4 + 0y_5
\end{aligned}$$ $v_4$ ve $v_5$ sütunları $2 \times 2$ birim matrisi oluşturur; problem simpleks yöntem ile çözülebilir haldedir ve yapay değişken gerekmez. Sütunları $v_1, v_2', v_2'', v_3, v_4, v_5$ diye adlandırıyoruz; amaç değerini $g_0$ ile gösteriyoruz.

**Başlangıç tablosu.** $\vec{c}_B = \vec{0}$ olduğundan $z_j - c_j = -c_j$: sırasıyla $-6, -3, 3, 5, 0, 0$. Maksimum probleminde en negatif $z_j - c_j$ girer ve bütün $z_j - c_j \ge 0$ olunca durulur. En negatifi $-6$ olduğundan $v_1$ baza girer. Oranlar $\tfrac{3}{2}$ ve $\tfrac{1}{1} = 1$’dir; $v_5$ bazdan çıkar ve pivot $1$’dir.

|  |  | $c_j$ | $6$ | $3$ | $-3$ | $-5$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $y_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2'$ | $v_2''$ | $v_3$ | $v_4$ | $v_5$ | Oran |
| $y_4$ | $0$ | $3$ | $2$ | $1$ | $-1$ | $-1$ | $1$ | $0$ | $\frac{3}{2}$ |
| $y_5$ | $0$ | $1$ | $[1]$ | $1$ | $-1$ | $-2$ | $0$ | $1$ | $\frac{1}{1} \Rightarrow$ |
| $z_j - c_j$ |  | $g_0 = 0$ | $-6 \Uparrow$ | $-3$ | $3$ | $5$ | $0$ | $0$ |  |

Tablo 14.20: Başlangıç tablosu

**Birinci iterasyon.** Pivot $1$ olduğundan $y_5$ satırı aynen kalır ve $c_B$ değeri $6$ olan $y_1$ satırı olur: $(1 \mid 1, 1, -1, -2, 0, 1)$. $y_4$ satırından bu satırın $2$ katı çıkarılır, kriter satırına $6$ katı eklenir: $$\begin{aligned}
y_4&: \ (3 - 2 \mid 0,\ 1 - 2,\ -1 + 2,\ -1 + 4,\ 1,\ -2) = (1 \mid 0, -1, 1, 3, 1, -2), \\[1mm]
z_j - c_j&: \ (0 + 6 \mid 0,\ -3 + 6,\ 3 - 6,\ 5 - 12,\ 0,\ 6) = (6 \mid 0, 3, -3, -7, 0, 6).
\end{aligned}$$ Negatif kriterler $-3$ ve $-7$’dir; en negatifi $-7$ olduğundan $v_3$ baza girer. $y_1$ satırındaki $-2$ teste girmez; tek oran $\tfrac{1}{3}$’tür. $y_4$ bazdan çıkar; pivot $3$’tür.

|  |  | $c_j$ | $6$ | $3$ | $-3$ | $-5$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $y_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2'$ | $v_2''$ | $v_3$ | $v_4$ | $v_5$ | Oran |
| $y_4$ | $0$ | $1$ | $0$ | $-1$ | $1$ | $[3]$ | $1$ | $-2$ | $\frac{1}{3} \Rightarrow$ |
| $y_1$ | $6$ | $1$ | $1$ | $1$ | $-1$ | $-2$ | $0$ | $1$ | $-$ |
| $z_j - c_j$ |  | $g_0 = 6$ | $0$ | $3$ | $-3$ | $-7 \Uparrow$ | $0$ | $6$ |  |

Tablo 14.21: Birinci iterasyon tablosu

**İkinci iterasyon.** Pivot satırı $3$’e bölünür ve $c_B$ değeri $-5$ olan $y_3$ satırı olur: $\left(\tfrac{1}{3} \mid 0, -\tfrac{1}{3}, \tfrac{1}{3}, 1, \tfrac{1}{3}, -\tfrac{2}{3}\right)$. $y_1$ satırına bu satırın $2$ katı, kriter satırına $7$ katı eklenir: $$\begin{aligned}
y_1&: \ \left(1 + \tfrac{2}{3} \mid 1,\ 1 - \tfrac{2}{3},\ -1 + \tfrac{2}{3},\ 0,\ \tfrac{2}{3},\ 1 - \tfrac{4}{3}\right) \\[1mm]
&\quad = \left(\tfrac{5}{3} \mid 1,\ \tfrac{1}{3},\ -\tfrac{1}{3},\ 0,\ \tfrac{2}{3},\ -\tfrac{1}{3}\right), \\[1mm]
z_j - c_j&: \ \left(6 + \tfrac{7}{3} \mid 0,\ 3 - \tfrac{7}{3},\ -3 + \tfrac{7}{3},\ 0,\ \tfrac{7}{3},\ 6 - \tfrac{14}{3}\right) \\[1mm]
&\quad = \left(\tfrac{25}{3} \mid 0,\ \tfrac{2}{3},\ -\tfrac{2}{3},\ 0,\ \tfrac{7}{3},\ \tfrac{4}{3}\right).
\end{aligned}$$ Tek negatif kriter $-\tfrac{2}{3}$ olduğundan $v_2''$ baza girer. $y_1$ satırındaki $-\tfrac{1}{3}$ teste girmez; tek oran $\tfrac{1/3}{1/3} = 1$’dir. $y_3$ bazdan çıkar; pivot $\tfrac{1}{3}$’tür.

|  |  | $c_j$ | $6$ | $3$ | $-3$ | $-5$ | $0$ | $0$ |  |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $y_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2'$ | $v_2''$ | $v_3$ | $v_4$ | $v_5$ | Oran |
| $y_3$ | $-5$ | $\frac{1}{3}$ | $0$ | $-\frac{1}{3}$ | $[\frac{1}{3}]$ | $1$ | $\frac{1}{3}$ | $-\frac{2}{3}$ | $\frac{1/3}{1/3} \Rightarrow$ |
| $y_1$ | $6$ | $\frac{5}{3}$ | $1$ | $\frac{1}{3}$ | $-\frac{1}{3}$ | $0$ | $\frac{2}{3}$ | $-\frac{1}{3}$ | $-$ |
| $z_j - c_j$ |  | $g_0 = \frac{25}{3}$ | $0$ | $\frac{2}{3}$ | $-\frac{2}{3} \Uparrow$ | $0$ | $\frac{7}{3}$ | $\frac{4}{3}$ |  |

Tablo 14.22: İkinci iterasyon tablosu

**Üçüncü iterasyon.** Pivot satırı $\tfrac{1}{3}$’e bölünür, yani $3$ ile çarpılır ve $c_B$ değeri $-3$ olan $y_2''$ satırı olur: $(1 \mid 0, -1, 1, 3, 1, -2)$. $y_1$ satırına bu satırın $\tfrac{1}{3}$ katı, kriter satırına $\tfrac{2}{3}$ katı eklenir: $$\begin{aligned}
y_1&: \ \left(\tfrac{5}{3} + \tfrac{1}{3} \mid 1,\ \tfrac{1}{3} - \tfrac{1}{3},\ 0,\ 1,\ \tfrac{2}{3} + \tfrac{1}{3},\ -\tfrac{1}{3} - \tfrac{2}{3}\right) \\[1mm]
&\quad = (2 \mid 1, 0, 0, 1, 1, -1), \\[1mm]
z_j - c_j&: \ \left(\tfrac{25}{3} + \tfrac{2}{3} \mid 0,\ \tfrac{2}{3} - \tfrac{2}{3},\ 0,\ 2,\ \tfrac{7}{3} + \tfrac{2}{3},\ \tfrac{4}{3} - \tfrac{4}{3}\right) \\[1mm]
&\quad = (9 \mid 0, 0, 0, 2, 3, 0).
\end{aligned}$$

|  |  | $c_j$ | $6$ | $3$ | $-3$ | $-5$ | $0$ | $0$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| $y_B$ | $c_B$ | $v_0$ | $v_1$ | $v_2'$ | $v_2''$ | $v_3$ | $v_4$ | $v_5$ |
| $y_2''$ | $-3$ | $1$ | $0$ | $-1$ | $1$ | $3$ | $1$ | $-2$ |
| $y_1$ | $6$ | $2$ | $1$ | $0$ | $0$ | $1$ | $1$ | $-1$ |
| $z_j - c_j$ |  | $g_0 = 9$ | $0$ | $0$ | $0$ | $2$ | $3$ | $0$ |

Tablo 14.23: Üçüncü iterasyon tablosu (optimal tablo)

**Dualin çözümü.** Üçüncü iterasyon tablosunda ([Tablo 14.23](#tbl-als-dua-optimal)) bütün $z_j - c_j \ge 0$’dır; maksimum problemi için optimal tabloya ulaşıldı. Dual problemin çözümü $$(y_1, y_2', y_2'', y_3, y_4, y_5) = (2, 0, 1, 0, 0, 0), \qquad y_2 = y_2' - y_2'' = -1$$ ve $$\max g = 6 \cdot 2 + 3 \cdot 0 - 3 \cdot 1 - 5 \cdot 0 = 9$$ dur. ($v_5$ baz dışında olduğu halde kriteri $0$’dır ve sütununda pozitif eleman yoktur; bu yüzden dualin başka optimal çözümleri de vardır, örneğin $(3, 0, 3, 0, 0, 1)$ için de $g = 18 - 9 = 9$ olur. Esas problemin çözümünü okumak için bu fark etmez.)

**Esas problemin çözümü.** Esas problemin $x_1$ ve $x_2$ değişkenleri dualin birinci ve ikinci kısıtlarına, dolayısıyla bu kısıtların $y_4$ ve $y_5$ aylak değişkenlerine karşılık gelir: $$\begin{bmatrix} y_4 \\ y_5 \end{bmatrix} \longleftrightarrow \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}.$$ Dualin optimal tablosunda bu aylak sütunların simpleks kriterleri esas problemin optimal çözümünü verir: $x_1 = z_4 - c_4 = 3$ ve $x_2 = z_5 - c_5 = 0$. Bunun nedeni, başlangıçta birim sütun olan bir aylak sütunun kriterinin $\vec{c}_B^{\,T}B^{-1}$ satır vektörünün ilgili bileşeni olmasıdır; ayrıntısı [Dualite](./dualite.md) bölümündedir. Bulduğumuz noktayı doğrudan da sağlayalım.

**$X^{*} = (3, 0)$ uygundur:** $2 \cdot 3 + 0 = 6 \ge 6$, $3 + 0 = 3$ ve $3 + 0 = 3 \le 5$; amaç değeri $z = 3 \cdot 3 + 0 = 9$’dur.

**$X^{*}$ optimaldir.** Kanonik formdaki esas problemin her uygun $\vec{x}$ çözümü ve dualin her uygun $\vec{y}$ çözümü için $$z = \vec{c}^{\,T}\vec{x} \ge (A^T\vec{y})^T\vec{x} = \vec{y}^{\,T}(A\vec{x}) \ge \vec{y}^{\,T}\vec{b} = g$$ dir. Birinci eşitsizlik $\vec{x} \ge 0$ ve $\vec{c} \ge A^T\vec{y}$ olduğundan, ikincisi $\vec{y} \ge 0$ ve $A\vec{x} \ge \vec{b}$ olduğundan doğrudur. Yani esas problemin hiçbir uygun çözümünün değeri, dualin bir uygun çözümünün değerinden küçük olamaz. $X^{*}$ ile dualin bulduğumuz çözümü aynı değeri verdiğine göre $$\min z = 9 = \max g$$ olur ve ikisi de kendi probleminde optimaldir. Esas problemin optimal çözümü $x_1 = 3$, $x_2 = 0$ ve $\min z = 9$’dur.

Grafik de aynı sonucu gösteriyor: $x_1 + x_2 = 3$ ve $x_2 \ge 0$ iken $2x_1 + x_2 \ge 6$ kısıtı $x_1 \ge 3$ demektir; bu da yalnız $(3, 0)$ noktasında mümkündür. Esas problemin tek uygun çözümü bu noktadır.

$\blacksquare$

## 14.7 Dal-Sınır Yöntemi

Son alıştırmada değişkenlerin tam sayı olması istenir. Problemi [Tam sayılı programlama ve dal-sınır yöntemi](./dal-sinir-yontemi.md) bölümündeki yöntemle, alt problemleri grafik yöntemle çözerek ele alıyoruz.

**Alıştırma 14.11 (Dal-sınır yöntemiyle bir tam sayılı problem)** $$\begin{aligned}
6x_1 + 2x_2 &\le 19 \\
2x_1 + 3x_2 &\le 13 \\
x_1, x_2 &\ge 0, \quad x_1, x_2 \ \text{tam sayı} \\
\max z &= 5x_1 + 4x_2
\end{aligned}$$ lineer programlama problemini çözünüz.

Çözüm

Dal-sınır yönteminde önce tam sayı koşulu kaldırılır ve kalan lineer programlama problemi çözülür. Çözüm tam sayılı değilse kesirli bir $x_k = t$ değişkeni seçilir ve problem iki alt probleme ayrılır: birine $x_k \le \lfloor t \rfloor$, diğerine $x_k \ge \lfloor t \rfloor + 1$ kısıtı eklenir. Aradaki $\lfloor t \rfloor < x_k < \lfloor t \rfloor + 1$ şeridinde tam sayılı nokta bulunmadığından hiçbir tam sayılı çözüm kaybolmaz. Tam sayılı çözüm veren alt problemler **aday çözümdür** ve en iyi adayın değeri optimum için bir alt sınırdır (A.S). Budama kuralları bölümdeki gibidir: rahatlatılmış değeri A.S’yi aşmayan (D1), uygun çözümü olmayan (D2) ya da tam sayılı çözüm veren (D3) alt problem bir daha dallandırılmaz.

**Alt Problem 1.** Tam sayı koşulu olmadan problemi grafik yöntemle çözelim. $6x_1 + 2x_2 = 19$ doğrusu $\left(\tfrac{19}{6}, 0\right)$ ve $\left(0, \tfrac{19}{2}\right)$’den, $2x_1 + 3x_2 = 13$ doğrusu $\left(\tfrac{13}{2}, 0\right)$ ve $\left(0, \tfrac{13}{3}\right)$’ten geçer; $O(0, 0)$ iki kısıtı da sağladığından uygun taraflar $O$’nun bulunduğu taraflardır. İki doğrunun kesişimini bulmak için ikinci denklemi $3$ ile çarpıp birinciyi çıkaralım: $$(6x_1 + 9x_2) - (6x_1 + 2x_2) = 39 - 19 \;\Rightarrow\; 7x_2 = 20 \;\Rightarrow\; x_2 = \tfrac{20}{7},$$ ve $2x_1 = 13 - \tfrac{60}{7} = \tfrac{31}{7}$, yani $x_1 = \tfrac{31}{14}$. Uygun bölgenin köşeleri ve amaç değerleri: $$\begin{aligned}
(0, 0)&: \ z = 0, & \left(\tfrac{19}{6}, 0\right)&: \ z = \tfrac{95}{6}, \\[1mm]
\left(\tfrac{31}{14}, \tfrac{20}{7}\right)&: \ z = \tfrac{155}{14} + \tfrac{160}{14} = \tfrac{45}{2}, & \left(0, \tfrac{13}{3}\right)&: \ z = \tfrac{52}{3} .
\end{aligned}$$ Maksimum değer $\left(\tfrac{31}{14}, \tfrac{20}{7}\right)$ noktasındaki $z = \tfrac{45}{2} = 22{,}5$’tir. Tam sayı koşulu eklenince uygun küme küçülür; bu yüzden aradığımız tam sayılı optimum $22{,}5$’i aşamaz. **Üst sınır** $22{,}5$’tir.

**Dallanma.** $x_1 = \tfrac{31}{14} \approx 2{,}21$ tam sayı değildir ve $2 < x_1 < 3$’tür. İki alt problem kurulur: $$\begin{aligned}
\text{Alt Problem 2} &= \text{Alt Problem 1} \cup \{x_1 \le 2\}, \\[1mm]
\text{Alt Problem 3} &= \text{Alt Problem 1} \cup \{x_1 \ge 3\}.
\end{aligned}$$

Alt Problem 1'in (tam sayı koşulsuz problemin) uygun bölgesi dörtgendir ve LP optimumu (31/14, 20/7) noktasındadır. x₁ ≤ 2 ve x₁ ≥ 3 dalları bölgenin iki şeridini ayırır; aradaki 2 \< x₁ \< 3 şeridinde hiç tam sayılı nokta yoktur. Alt Problem 2'nin optimumu (2, 3), Alt Problem 3'ünkü (3, 1/2) noktasıdır. Küçük noktalar bölgedeki tam sayılı noktalardır.

**Alt Problem 2.** Kısıtlar $6x_1 + 2x_2 \le 19$, $2x_1 + 3x_2 \le 13$, $x_1 \le 2$, $x_1, x_2 \ge 0$’dır. $x_1 = 2$ doğrusu $2x_1 + 3x_2 = 13$ doğrusunu $x_2 = 3$’te keser ve bu nokta birinci kısıtı sağlar: $12 + 6 = 18 \le 19$. Köşeler ve amaç değerleri: $$(0, 0): \ z = 0, \quad (2, 0): \ z = 10, \quad (2, 3): \ z = 22, \quad \left(0, \tfrac{13}{3}\right): \ z = \tfrac{52}{3} .$$ Optimal çözüm $x_1 = 2$, $x_2 = 3$, $\max z = 22$’dir. Bütün değişkenler tam sayı olduğundan bu bir **aday çözümdür**; artık tam sayılı optimumun $22$’den küçük olmadığını biliyoruz: $\text{A.S} = 22$. Bu alt problem D3 kuralıyla budanır, yani daha fazla dallandırılmaz.

**Alt Problem 3.** Kısıtlara $x_1 \ge 3$ eklenir. $x_1 = 3$ doğrusu $6x_1 + 2x_2 = 19$ doğrusunu $x_2 = \tfrac{1}{2}$’de keser ($2 \cdot 3 + 3 \cdot \tfrac{1}{2} = 7{,}5 \le 13$). Uygun bölge köşeleri $(3, 0)$, $\left(\tfrac{19}{6}, 0\right)$, $\left(3, \tfrac{1}{2}\right)$ olan küçük bir üçgendir: $$(3, 0): \ z = 15, \quad \left(\tfrac{19}{6}, 0\right): \ z = \tfrac{95}{6}, \quad \left(3, \tfrac{1}{2}\right): \ z = 17 .$$ Optimal çözüm $x_1 = 3$, $x_2 = \tfrac{1}{2}$, $\max z = 17$’dir ve $x_2$ tam sayı değildir.

Burada bir sınır gözlemi yapabiliriz: bu dalın bütün tam sayılı çözümleri Alt Problem 3’ün uygun bölgesindedir, dolayısıyla değerleri $17$’yi aşamaz. Elimizde zaten $22$ değerli bir aday olduğundan bu dal $22$’den iyi bir çözüm veremez: $17 \le \text{A.S} = 22$ olduğu için Alt Problem 3 D1 kuralıyla burada budanabilir. Yöntemin bütün adımlarını görmek için dalı yine de sonuna kadar açalım; sonucun değişmediğini göreceğiz.

$0 < x_2 = \tfrac{1}{2} < 1$ olduğundan $$\begin{aligned}
\text{Alt Problem 4} &= \text{Alt Problem 3} \cup \{x_2 \le 0\}, \\[1mm]
\text{Alt Problem 5} &= \text{Alt Problem 3} \cup \{x_2 \ge 1\}
\end{aligned}$$ kurulur.

**Alt Problem 5.** Alt Problem 3’te $x_1 \ge 3$ ve $6x_1 + 2x_2 \le 19$ olduğundan $2x_2 \le 19 - 18 = 1$, yani $x_2 \le \tfrac{1}{2}$’dir. $x_2 \ge 1$ ile $x_2 \le \tfrac{1}{2}$’nin ortak noktası yoktur. Alt Problem 5’in uygun çözümü yoktur ve D2 kuralıyla budanır.

**Alt Problem 4.** $x_2 \le 0$ ile $x_2 \ge 0$ birlikte $x_2 = 0$ verir. Uygun küme $x_1$ ekseni üzerinde $3 \le x_1 \le \tfrac{19}{6}$ doğru parçasıdır ve uç noktaları $(3, 0)$ ile $\left(\tfrac{19}{6}, 0\right)$’dır: $$(3, 0): \ z = 15, \qquad \left(\tfrac{19}{6}, 0\right): \ z = \tfrac{95}{6} \approx 15{,}83 .$$ Optimal çözüm $x_1 = \tfrac{19}{6}$, $x_2 = 0$, $\max z = \tfrac{95}{6}$’dır; $x_1$ tam sayı olmadığından bu bir aday değildir. $\tfrac{95}{6} \le 22$ olduğundan bu alt problem de D1 ile budanabilirdi; dallandırmayı sürdürelim. $3 < x_1 = \tfrac{19}{6} < 4$ olduğundan $$\begin{aligned}
\text{Alt Problem 6} &= \text{Alt Problem 4} \cup \{x_1 \le 3\}, \\[1mm]
\text{Alt Problem 7} &= \text{Alt Problem 4} \cup \{x_1 \ge 4\}
\end{aligned}$$ kurulur.

**Alt Problem 6.** Doğru parçasının $x_1 \le 3$ ile kesişimi yalnız $(3, 0)$ noktasıdır. $x_1 = 3$ ve $x_2 = 0$ tam sayılardır; Alt Problem 6 bir aday çözüm verir: $\max z = 15$. Bu değer A.S’yi büyütmez; alt sınır $22$ olarak kalır.

**Alt Problem 7.** Alt Problem 4’te $x_1$ en fazla $\tfrac{19}{6}$ olur; $x_1 \ge 4$ ile $x_1 \le \tfrac{19}{6}$’nın ortak noktası yoktur. Alt Problem 7’nin uygun çözümü yoktur ve D2 kuralıyla budanır.

Alt Problem 3'ün uygun bölgesi (3, 0), (19/6, 0), (3, 1/2) köşeli küçük üçgendir. x₂ ≥ 1 yarı düzlemi bu üçgene değmez (Alt Problem 5 uygun değildir); x₂ ≤ 0 ile kesişimi kalın çizilen doğru parçasıdır (Alt Problem 4). Bu parçanın x₁ ≤ 3 ile kesişimi yalnız (3, 0) noktasıdır (Alt Problem 6), x₁ ≥ 4 ile kesişimi boştur (Alt Problem 7).

**Sonuç.** Bütün dallar kapandı. Aday çözümler Alt Problem 2 ($z = 22$) ve Alt Problem 6 ($z = 15$)’dır; ikisi de üst sınır $22{,}5$’ten küçüktür. Maksimum aradığımız için adaylar arasında en büyük değeri veren Alt Problem 2 seçilir. Optimal çözüm $$x_1 = 2, \quad x_2 = 3, \qquad \max z = 22$$ dir. Bütün alt problemler aşağıdaki ağaçta toplanmıştır.

Dal-sınır ağacı. Her kutuda alt problemin LP optimumu, amaç değeri ve budama kuralı yazılıdır; oklar eklenen dal kısıtını gösterir. Alt Problem 3 ve 4, değerleri A.S = 22'yi aşmadığı için D1 ile budanabilirdi; yöntemin adımlarını göstermek için dallandırıldılar. Aday çözümler Alt Problem 2 (z = 22) ve Alt Problem 6 (z = 15)'dır; en büyüğü Alt Problem 2'nin (2, 3) çözümüdür.

Tam sayılı $x_1, x_2$ için $z = 5x_1 + 4x_2$ de tam sayıdır. $z \le 22{,}5$ olduğundan tam sayılı çözümlerde $z \le 22$’dir; Alt Problem 2’de $22$ bulunduğu anda optimum aslında belli olmuştu.

**Sağlama.** Bölgedeki tam sayılı noktaları $x_1$’e göre tarayalım. $6x_1 \le 19$ olduğundan $x_1 \le 3$’tür. Her $x_1$ için en büyük tam sayı $x_2$ şöyledir: $x_1 = 0$ için $3x_2 \le 13$ ve $x_2 \le 4$, $z = 16$; $x_1 = 1$ için $2x_2 \le 13$ ve $3x_2 \le 11$, yani $x_2 \le 3$ ve $z = 17$; $x_1 = 2$ için $2x_2 \le 7$ ve $3x_2 \le 9$, yani $x_2 \le 3$ ve $z = 22$; $x_1 = 3$ için $2x_2 \le 1$, yani $x_2 = 0$ ve $z = 15$. En büyük değer gerçekten $(2, 3)$’teki $22$’dir.

$\blacksquare$

Bu alıştırmalarla kitabın bütün yöntemleri bir kez daha, baştan sona uygulanmış oldu. Konuların listesine ve bölümlere [Müfredat ve Giriş](./index.md) sayfasından dönebilirsiniz.
