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 bölümündeki dört adımlı reçeteyi izliyoruz (Tanım 2.3, Tanım 2.5, Tanım 2.6).
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); 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\) |
\(\blacksquare\)
Alıştırma 14.2 (Uygun temel çözümlerle optimumun aranması) Önceki alıştırmadaki (Alıştırma 14.1) 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) 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), 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 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). 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): 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
Uç noktalar ve grafik yöntem bölümündeki beş adımı (Bölüm 3.3) 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): 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):
| 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\) |
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 bölümündeki tabloyu (Bölüm 4.3) ve dönüşüm kurallarını (Bölüm 4.4) 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) 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\) |
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\) |
Birinci iterasyon tablosunda (Tablo 14.4) çö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\) |
İkinci iterasyon tablosunda (Tablo 14.5) çö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\) |
Sonuç. Üçüncü iterasyon tablosunda (Tablo 14.6) 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 bölümünde kurulup çözülen örneğin (Örnek 4.6) 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 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) 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) 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): \[ \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) 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). 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\) |
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\) |
İ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\) |
Üçü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}\) |
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}\) |
Sonuç. Dördüncü iterasyon tablosunda (Tablo 14.11) bütün \(z_j - c_j \le 0\)’dır ve bazda yapay değişken yoktur. Teorem 5.1 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). 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 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
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\) |
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\) |
İ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\) |
Sonuç. Negatif simpleks kriteri kalmadı; maksimum problemi için optimal tabloya (Tablo 14.14) ulaşıldı. Bazda yapay değişken yoktur (Teorem 5.1) 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).
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) çö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), 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\) |
\(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\) |
İ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\) |
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}\) |
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) 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) 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\) |
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).
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) 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). 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) 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
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\) |
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\) |
İ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}\) |
Üçü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\) |
Dualin çözümü. Üçüncü iterasyon tablosunda (Tablo 14.23) 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 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 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 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.
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.
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ş sayfasından dönebilirsiniz.