13 Tam Sayılı Programlama ve Dal-Sınır Yöntemi
Şimdiye kadar çözdüğümüz bütün problemlerde değişkenler sürekli değerler alabiliyordu: \(x_1 = 13/7\) ton hammadde ya da \(x_2 = 9/4\) saat çalışma anlamlı cevaplardı. Oysa pek çok problemde değişken bir sayım sonucudur: kaç makine alınacağı, kaç kamyon gönderileceği, kaç kişinin işe alınacağı. Bu değişkenlerin tam sayı olması gerekir ve \(2{,}25\) makine bir cevap değildir. Dual simpleks algoritması bölümüyle simpleks ailesinin yöntemlerini tamamladık; bu son konu bölümünde tam sayı şartını da işin içine katıyoruz.
İlk akla gelen yol tam sayı şartını unutup problemi alışık olduğumuz gibi çözmek, sonra da çıkan kesirli değerleri yuvarlamaktır. Bunun neden güvenilir olmadığını bir örnekle göreceğiz. Onun yerine dal-sınır yöntemini kuracağız: problem gittikçe küçülen alt problemlere bölünür (dallanma), her alt problemin varabileceği en iyi değer tam sayı şartı kaldırılarak hesaplanır (sınır) ve umut vermeyen alt problemler bir daha bakılmamak üzere atılır (budama).
13.1 Tam Sayılı Programlama Problemi
Önce problemi tanımlayalım; kısıtlar ve amaç fonksiyonu tanıdıktır, yeni olan yalnız değişkenlere konan şarttır.
Tanım 13.1 (Tam Sayılı Programlama Problemi) Bir lineer programlama problemine (Tanım 1.1) değişkenlerin tam sayı değer alması şartı da eklenirse elde edilen probleme tam sayılı programlama (TP) problemi denir. Bütün değişkenlerin tam sayı olması isteniyorsa probleme pür (saf) TP problemi denir. Örneğin \[ \begin{aligned} x_1 + x_2 &\le 6 \\ 9x_1 + 5x_2 &\le 45 \\ x_1, x_2 &\ge 0 \text{ ve tam sayı} \\ \max z &= 8x_1 + 5x_2 \end{aligned} \] bir pür TP problemidir.
Yani TP problemi, işaret koşullarının yanına “ve tam sayı” ibaresi eklenmiş bir lineer programlama problemidir. Değişkenlerin yalnız bir kısmı tam sayı olmak zorundaysa problem karma TP problemi olur; bu bölümde yalnız pür TP problemleriyle çalışacağız ve kısaca TP diyeceğiz. Bir TP probleminin uygun çözümü, bütün kısıtları sağlayan ve bütün bileşenleri tam sayı olan bir \(\vec{x}\) vektörüdür.
Uygun bölge sınırlıysa bir TP probleminin uygun çözümleri sonlu sayıdadır; bu yüzden ilke olarak her birini tek tek deneyip önce uygun olup olmadığına, sonra amaç değerine bakabiliriz. Küçük bir problemde bu gerçekten işe yarar.
Örnek 13.1 (Uygun Çözümleri Tek Tek Denemek) \[ \begin{aligned} 7x_1 + 4x_2 &\le 13 \\ x_1, x_2 &\ge 0 \text{ ve tam sayı} \\ \max z &= 21x_1 + 11x_2 \end{aligned} \] TP probleminin bütün uygun çözümlerini yazarak optimal çözümünü bulunuz.
Çözüm
\(x_2 \ge 0\) olduğundan \(7x_1 \le 13\), yani \(x_1 \le 13/7 < 2\); tam sayı olduğu için \(x_1 \in \{0, 1\}\).
- \(x_1 = 0\) ise \(4x_2 \le 13\), yani \(x_2 \le 13/4\) ve \(x_2 \in \{0, 1, 2, 3\}\).
- \(x_1 = 1\) ise \(4x_2 \le 6\), yani \(x_2 \le 3/2\) ve \(x_2 \in \{0, 1\}\).
Altı uygun çözüm ve amaç değerleri şöyledir:
| \((x_1, x_2)\) | \((0, 0)\) | \((0, 1)\) | \((0, 2)\) | \((0, 3)\) | \((1, 0)\) | \((1, 1)\) |
|---|---|---|---|---|---|---|
| \(z = 21x_1 + 11x_2\) | \(0\) | \(11\) | \(22\) | \(33\) | \(21\) | \(32\) |
En büyük değer \((0, 3)\) noktasındadır: optimal çözüm \(x_1 = 0\), \(x_2 = 3\) ve \(\max z = 33\)’tür. \(\blacksquare\)
Ne var ki bu yol değişken sayısı arttıkça hızla imkânsız hâle gelir. Örneğin her değişkeni yalnız 0 ya da 1 değerini alabilen \(n\) değişkenli bir TP probleminde denenecek \(2^n\) aday vardır. Her yeni değişken aday sayısını iki katına çıkarır; 30 değişkende aday sayısı \(2^{30} = 1\,073\,741\,824\), yani bir milyardan fazladır. Bu olguya problem zorluğunun üstel büyümesi denir. Dal-sınır yöntemi, uygun çözümlerin yalnız küçük bir kısmına açıkça bakarak bu engeli aşmaya çalışır.
Yöntemin her adımında aynı yardımcı problemi kullanacağız: tam sayı şartı kaldırılmış problem.
Tanım 13.2 (Rahatlatılmış LP Problemi) Bir TP probleminde tam sayı şartları kaldırılarak elde edilen lineer programlama problemine rahatlatılmış LP problemi (ya da gevşetilmiş problem) denir.
Yani rahatlatılmış problemin kısıtları, işaret koşulları ve amaç fonksiyonu TP probleminin aynısıdır; yalnız “ve tam sayı” ibaresi silinmiştir. Rahatlatılmış problem sıradan bir lineer programlama problemidir; iki değişkende grafik yöntemle (Uç noktalar ve grafik yöntem), genel olarak simpleks yöntemle çözülür.
Örnek 13.2 (Rahatlatılmış Problemin Çözümü) Önceki örnekteki (Örnek 13.1) TP probleminin rahatlatılmış LP problemini yazınız ve çözünüz.
Çözüm
Tam sayı şartını kaldırırız: \[ \begin{aligned} 7x_1 + 4x_2 &\le 13 \\ x_1, x_2 &\ge 0 \\ \max z &= 21x_1 + 11x_2 \end{aligned} \] Uygun bölge \((0, 0)\), \((13/7, 0)\) ve \((0, 13/4)\) köşeli üçgendir. Köşelerde \[ z(0, 0) = 0, \quad z\big(\tfrac{13}{7}, 0\big) = 21 \cdot \tfrac{13}{7} = 39, \quad z\big(0, \tfrac{13}{4}\big) = \tfrac{143}{4} = 35{,}75 \] olur. Bölge sınırlı olduğundan optimum bir köşededir (Sonuç 3.1): rahatlatılmış problemin optimal çözümü \(x_1 = 13/7\), \(x_2 = 0\) ve \(\max z = 39\)’dur. \(\blacksquare\)
13.2 Yuvarlama Neden Yetmez
Rahatlatılmış problemin çözümünü yuvarlamak cazip görünür. Aynı örnek bunun iki ayrı şekilde yanlış gidebileceğini gösteriyor.
Örnek 13.3 (Yuvarlamanın Başarısız Olduğu Bir Problem) \(7x_1 + 4x_2 \le 13\), \(x_1, x_2 \ge 0\) ve tam sayı kısıtları altında \(\max z = 21x_1 + 11x_2\) problemini ele alalım. Rahatlatılmış problemin optimal çözümünü (Örnek 13.2) yuvarlayarak TP probleminin optimal çözümü bulunabilir mi?
Çözüm
Rahatlatılmış problemin optimal çözümü \((13/7, 0)\), yani yaklaşık \((1{,}86;\ 0)\)’dır.
En yakın tam sayıya yuvarlama. \(x_1 = 13/7\) en yakın tam sayıya yuvarlanırsa \((2, 0)\) elde edilir. Bu nokta kısıtı sağlamaz: \(7 \cdot 2 + 4 \cdot 0 = 14 > 13\). Yuvarlanmış çözüm uygun bile değildir.
Aşağı yuvarlama. Uygunluğu korumak için aşağı yuvarlayalım: \((1, 0)\) noktası uygundur ama \(z = 21\) verir. Oysa Örnek 13.1 içinde TP probleminin optimumunu \((0, 3)\) noktasında \(z = 33\) olarak bulduk. Aşağı yuvarlanmış çözüm optimumdan çok uzaktadır.
Nedeni şekilde görülüyor: rahatlatılmış problemin optimumu \(x_1\) ekseni üzerindeki köşededir, tam sayılı optimum ise bölgenin öbür ucunda, \(x_2\) ekseni üzerindedir. İki nokta birbirine hiç yakın değildir.
Demek ki yuvarlama ne uygun bir çözüm ne de iyi bir çözüm garanti eder. Çok değişkenli problemlerde durum daha da kötüdür: her değişken yukarı ya da aşağı yuvarlanabildiği için \(2^n\) yuvarlama seçeneği vardır ve bunların hiçbiri uygun olmayabilir. \(\blacksquare\)
Yine de rahatlatılmış problem boşa çözülmüş değildir: \(z\) değeri TP probleminin optimumu hakkında kesin bir bilgi verir. Bu örnekte rahatlatılmış optimum \(39\), TP optimumu \(33\)’tür ve \(33 \le 39\) olduğuna dikkat edelim.
13.3 Rahatlatılmış Problem Bir Sınır Verir
Son gözlemin tesadüf olmadığını gösterelim. Bütün fikir, TP probleminin uygun çözümlerinin rahatlatılmış problemin uygun çözümleri arasında bulunmasıdır.
Teorem 13.1 (Rahatlatılmış Problemin Verdiği Sınır) Bir TP problemi ve onun rahatlatılmış LP problemi verilsin.
- Rahatlatılmış problemin uygun çözümü yoksa TP probleminin de uygun çözümü yoktur.
- Maksimum probleminde rahatlatılmış problemin optimal değeri \(z_R\) ise TP probleminin her uygun çözümü için \(z \le z_R\)’dir. Özellikle TP probleminin optimal değeri \(z_T\) varsa \(z_T \le z_R\) olur.
- Minimum probleminde aynı koşullarda TP probleminin her uygun çözümü için \(z \ge z_R\), dolayısıyla \(z_T \ge z_R\)’dir.
İspat
TP probleminin uygun çözümlerinin kümesini \(S_T\), rahatlatılmış problemin uygun çözümlerinin kümesini \(S_R\) ile gösterelim. \(\vec{x} \in S_T\) ise \(\vec{x}\) bütün kısıtları ve işaret koşullarını sağlar; tam sayı olması da ek bir bilgidir. O hâlde \(\vec{x} \in S_R\)’dir, yani \[ S_T \subseteq S_R . \]
1. \(S_R = \varnothing\) ise \(S_T \subseteq S_R\) gereği \(S_T = \varnothing\) olur.
2. \(\vec{x} \in S_T\) olsun. \(\vec{x} \in S_R\) olduğundan ve \(z_R\), amaç fonksiyonunun \(S_R\) üzerindeki en büyük değeri olduğundan \(z(\vec{x}) \le z_R\)’dir. TP probleminin optimal çözümü \(\vec{x}^{\,*}\) ise \(z_T = z(\vec{x}^{\,*})\) ve \(\vec{x}^{\,*} \in S_T\) olduğundan \(z_T \le z_R\) çıkar.
3. Aynı akıl yürütme, \(z_R\) bu kez \(S_R\) üzerindeki en küçük değer olduğu için \(z(\vec{x}) \ge z_R\) verir. \(\blacksquare\)
Yani daha az şart koyan problem daha çok çözüm arasından seçer ve bu yüzden en az onun kadar iyi bir değere ulaşır. Maksimumda “iyi” büyük demek olduğu için rahatlatılmış optimum TP optimumunun üstünde, minimumda altında kalır: \[ \begin{pmatrix} \text{TP problemi için} \\ \text{optimal } z \text{ değeri} \end{pmatrix} \le \begin{pmatrix} \text{Rahatlatılmış LP problemi} \\ \text{için optimal } z \text{ değeri} \end{pmatrix} \quad (\max) . \]
Tanım 13.3 (Üst Sınır ve Alt Sınır) Maksimum tipindeki bir TP probleminde rahatlatılmış LP probleminin optimal \(z\) değerine TP problemi için üst sınır (Ü.S) denir. Minimum tipindeki bir TP probleminde aynı değere alt sınır (A.S) denir.
Yani maksimum probleminde Ü.S, TP optimumunun asla aşamayacağı değerdir; minimum probleminde A.S, TP optimumunun asla altına inemeyeceği değerdir. Örnek 13.2 içindeki problemde \(\text{Ü.S} = 39\)’dur.
Sınır çoğu zaman aşılamaz bir tavandır ama bazen tam olarak ulaşılır. Bu durumda iş hemen biter.
Sonuç 13.1 (Tam Sayılı Rahatlatılmış Optimum) Rahatlatılmış LP probleminin optimal çözümünde bütün değişkenler tam sayı değer alıyorsa bu çözüm TP probleminin de optimal çözümüdür.
İspat
Rahatlatılmış problemin optimal çözümü \(\vec{x}^{\,*}\) ve optimal değeri \(z_R = z(\vec{x}^{\,*})\) olsun. \(\vec{x}^{\,*}\) bütün kısıtları sağlar ve bileşenleri tam sayıdır; yani TP probleminin bir uygun çözümüdür. Maksimum probleminde Teorem 13.1 gereği TP probleminin her uygun \(\vec{x}\) çözümü için \(z(\vec{x}) \le z_R = z(\vec{x}^{\,*})\) olur. Demek ki \(\vec{x}^{\,*}\) TP probleminin optimal çözümüdür. Minimum probleminde eşitsizlikler yön değiştirir, sonuç aynıdır. \(\blacksquare\)
Örnek 13.4 (Rahatlatılmış Optimumun Tam Sayı Çıkması) \[ \begin{aligned} x_1 + x_2 &\le 4 \\ x_1 &\le 3 \\ x_1, x_2 &\ge 0 \text{ ve tam sayı} \\ \max z &= 2x_1 + x_2 \end{aligned} \] TP problemini rahatlatılmış problemi yardımıyla çözünüz.
Çözüm
Rahatlatılmış problemin uygun bölgesi \((0, 0)\), \((3, 0)\), \((3, 1)\) ve \((0, 4)\) köşeli dörtgendir. \((3, 1)\) köşesi \(x_1 = 3\) ile \(x_1 + x_2 = 4\) doğrularının kesişimidir. Köşelerde \[ z(0, 0) = 0, \quad z(3, 0) = 6, \quad z(3, 1) = 7, \quad z(0, 4) = 4 \] olur; rahatlatılmış optimum \(x_1 = 3\), \(x_2 = 1\), \(z = 7\)’dir. İki değişken de tam sayı olduğundan Sonuç 13.1 gereği TP probleminin optimal çözümü de \(x_1 = 3\), \(x_2 = 1\) ve \(\max z = 7\)’dir. \(\blacksquare\)
13.4 Dallanma ve Budama
Rahatlatılmış optimum kesirliyse ne yapacağız? Dal-sınır yöntemi iki temel işleme dayanır.
Tanım 13.4 (Dallandırma) TP probleminin rahatlatılmış LP problemine Alt Problem 1 diyelim. Bir alt problemin rahatlatılmış optimal çözümünde bir \(x_j\) değişkeni kesirli bir \(a\) değeri alsın; \(k = \lfloor a \rfloor\) ile \(k + 1 = \lceil a \rceil\) arasında, yani \(k < a < k + 1\) olsun. Bu alt problemden iki yeni alt problem kurulur: \[ \begin{aligned} &\text{Alt problem} \cup \{x_j \le k\}, \\[1mm] &\text{Alt problem} \cup \{x_j \ge k + 1\}. \end{aligned} \] Yeni alt problemlere sıradaki numaralar verilir. Bu işleme \(x_j\) değişkeninden dallandırma (dallanma) denir.
Yani \(x_j\) tam sayı olacaksa ya \(k\)’dan küçük eşit ya da \(k + 1\)’den büyük eşit olmak zorundadır; iki seçeneği iki ayrı dala ayırırız. “\(\cup\)” işareti, alt problemin kısıtlarına yeni kısıtın eklendiğini anlatır. Yeni alt problemler yine TP problemleridir ve onların da rahatlatılmış problemleri çözülür. Birden fazla kesirli değişken varsa hangisinden dallanılacağı keyfidir; hangi dala hangi numaranın verildiği de önemli değildir. Dallanmalar, kökünde Alt Problem 1 bulunan bir ağaç yapısıyla gösterilir.
Dallanmanın hiçbir tam sayılı çözümü kaybetmediğini ama rahatlatılmış optimumu dışarıda bıraktığını gösterelim.
Önerme 13.1 (Dallanmanın Özellikleri) Bir alt problem, rahatlatılmış optimumunda \(k < x_j = a < k + 1\) olan \(x_j\) değişkeninden dallandırılsın.
- Alt problemin tam sayılı her uygun çözümü, iki yeni alt problemden tam olarak birinin uygun çözümüdür.
- Alt problemin rahatlatılmış optimal çözümü, yeni alt problemlerin hiçbirinin uygun çözümü değildir.
- Maksimum probleminde yeni alt problemlerin rahatlatılmış optimal \(z\) değerleri, dallandırılan alt probleminkini aşamaz; minimum probleminde onun altına inemez.
İspat
1. \(\vec{x}\) alt problemin tam sayılı bir uygun çözümü olsun. \(x_j\) bir tam sayıdır ve \(k\) ile \(k + 1\) ardışık tam sayılar olduğundan aralarında başka tam sayı yoktur. O hâlde ya \(x_j \le k\) ya da \(x_j \ge k + 1\)’dir; ikisi birden olamaz, çünkü \(k < k + 1\). \(\vec{x}\) alt problemin bütün kısıtlarını zaten sağladığından, eklenen kısıtı sağladığı yeni alt problemin uygun çözümüdür, öbürünün değildir.
2. Rahatlatılmış optimumda \(x_j = a\) ve \(k < a < k + 1\)’dir. \(a \le k\) ve \(a \ge k + 1\) eşitsizliklerinin ikisi de yanlıştır; optimal çözüm eklenen kısıtların hiçbirini sağlamaz.
3. Yeni alt problemin kısıtları eskisinin kısıtlarını ve bir kısıt daha içerir. Bu yüzden yeni rahatlatılmış problemin uygun çözümleri eskisinin uygun çözümleri arasındadır. Maksimum probleminde daha küçük bir küme üzerindeki en büyük değer, daha büyük küme üzerindeki en büyük değeri aşamaz; minimumda en küçük değer onun altına inemez. \(\blacksquare\)
Geometrik olarak dallanma, uygun bölgeden \(k < x_j < k + 1\) şeridini kesip atar. Şeridin içinde hiç tam sayılı nokta yoktur, rahatlatılmış optimum ise tam bu şeridin içindedir.
Örnek 13.5 (Bir Dallanma Adımı) \(7x_1 + 4x_2 \le 13\), \(x_1, x_2 \ge 0\) ve tam sayı kısıtları altında \(\max z = 21x_1 + 11x_2\) problemini ele alalım. Alt Problem 1’in (rahatlatılmış problemin) optimumu \(x_1 = 13/7\), \(x_2 = 0\) idi (Örnek 13.2). \(x_1\) değişkeninden dallanarak iki alt problem kurunuz ve rahatlatılmış problemlerini çözünüz.
Çözüm
\(1 < 13/7 < 2\) olduğundan \(k = 1\)’dir: \[ \begin{aligned} \text{Alt Problem 2} &= \text{Alt Problem 1} \cup \{x_1 \le 1\}, \\[1mm] \text{Alt Problem 3} &= \text{Alt Problem 1} \cup \{x_1 \ge 2\}. \end{aligned} \]
Alt Problem 3. \(x_1 \ge 2\) ise \(7x_1 + 4x_2 \ge 14 > 13\) olur; kısıt sağlanamaz. Alt Problem 3’ün uygun çözümü yoktur.
Alt Problem 2. Uygun bölge \((0, 0)\), \((1, 0)\), \((1, 3/2)\) ve \((0, 13/4)\) köşeli dörtgendir; \((1, 3/2)\) köşesi \(x_1 = 1\) ile \(7x_1 + 4x_2 = 13\) doğrularının kesişimidir. Köşelerde \[ \begin{aligned} z(0, 0) &= 0, & z(1, 0) &= 21, \\[1mm] z\big(1, \tfrac32\big) &= 21 + \tfrac{33}{2} = \tfrac{75}{2}, & z\big(0, \tfrac{13}{4}\big) &= \tfrac{143}{4} \end{aligned} \] olur. \(75/2 = 37{,}5\) en büyüğüdür; Alt Problem 2’nin rahatlatılmış optimumu \(x_1 = 1\), \(x_2 = 3/2\) ve \(z = 75/2\)’dir.
Önerme 13.1 burada gözle görülüyor: altı tam sayılı uygun çözümün (Tablo 13.1) hepsinde \(x_1 \le 1\) olduğundan hepsi Alt Problem 2’dedir; \((13/7, 0)\) noktası iki alt problemin de dışında kalır; \(75/2 \le 39\)’dur. Alt Problem 2’nin optimumunda \(x_2 = 3/2\) kesirli olduğu için yöntem bu kez \(x_2\) değişkeninden dallanarak devam eder. \(\blacksquare\)
Dallanma tek başına ağacı durmadan büyütür. Onu durduran şey, bazı alt problemlerin bir daha dallandırılmamasıdır. Bunun için önce elimizdeki en iyi tam sayılı çözümü adlandıralım.
Tanım 13.5 (Aday Çözüm) Bir alt problemin rahatlatılmış optimal çözümünde bütün değişkenler tam sayı ise bu çözüm TP probleminin bir uygun çözümüdür; buna aday çözüm denir. Maksimum probleminde o ana kadar bulunan aday çözümlerin en büyük \(z\) değeri TP optimumu için bir alt sınırdır (A.S). Henüz aday yoksa \(\text{A.S} = -\infty\) alınır. Minimum probleminde adayların en küçük \(z\) değeri bir üst sınırdır (Ü.S) ve başlangıçta \(\text{Ü.S} = +\infty\) alınır.
Yani aday çözüm, TP problemi için gerçekten kullanılabilecek bir cevaptır; optimal olup olmadığı henüz bilinmez. Maksimum probleminde optimal değer en iyi adayın değerinden küçük olamaz, rahatlatılmış problemin değerinden de büyük olamaz: \[ \text{A.S} \le z_T \le \text{Ü.S} . \] Yöntem ilerledikçe daha iyi adaylar bulundukça A.S büyür ve iki sınır birbirine yaklaşır.
Tanım 13.6 (Budama) Bir alt problemin bir daha dallandırılmamasına alt problemin budanması denir. Maksimum probleminde bir alt problem şu durumlarda budanır:
- D1) Alt problemin rahatlatılmış optimal \(z\) değeri mevcut A.S değerini aşmıyorsa (\(z \le \text{A.S}\)). Minimum probleminde: \(z\) değeri mevcut Ü.S değerinden küçük değilse (\(z \ge \text{Ü.S}\)).
- D2) Alt problemin uygun çözümü yoksa.
- D3) Alt problemin rahatlatılmış optimal çözümü tam sayılıysa. Bu çözüm bir aday çözümdür; \(z\) değeri mevcut A.S değerinden büyükse yeni A.S olur ve en iyi aday bu çözüm olur.
Yani budanan bir alt problemde, elimizdeki en iyi adaydan daha iyi bir tam sayılı çözüm bulunamayacağı bilindiği için arama sürdürülmez. D2’de alt problemde tam sayılı çözüm yoktur (Teorem 13.1). D3’te alt problemin en iyi tam sayılı çözümü zaten elimizdedir: rahatlatılmış optimumun kendisi (Sonuç 13.1). D1’de alt problemin tam sayılı çözümlerinin hiçbiri elimizdeki adaydan daha iyi olamaz, çünkü Teorem 13.1 gereği hepsinin \(z\) değeri alt problemin rahatlatılmış \(z\) değerini aşmaz. Tek bir alt problemi çözerek çok sayıda tam sayılı çözümü incelemeden eleriz; TP probleminin bütün uygun çözümleri böylece örtülü olarak, açıkça tek tek bakılmadan ele alınmış olur.
Yöntemin gerçekten durduğunu ve durduğunda doğru cevabı verdiğini ispatlayalım.
Önerme 13.2 (Dal-Sınır Yöntemi Sonlu Adımda Durur) Rahatlatılmış LP probleminin uygun bölgesi sınırlıysa dal-sınır yöntemi sonlu sayıda alt problem çözdükten sonra durur.
İspat
Uygun bölge sınırlı olduğundan her \(j\) için bölgede \(x_j \le U_j\) olacak şekilde bir \(U_j\) sayısı vardır. Her alt problemin kısıtları Alt Problem 1’in kısıtlarını içerdiği için bu sınır bütün alt problemlerde geçerlidir.
Bir alt problem, rahatlatılmış optimumunda \(x_j = a\) kesirli olduğu için dallandırılsın. Eklenen kısıt ya \(x_j \le \lfloor a \rfloor\) ya da \(x_j \ge \lceil a \rceil\)’dir. \(0 \le a \le U_j\) olduğundan \[ 0 \le \lfloor a \rfloor \le \lfloor U_j \rfloor, \qquad 1 \le \lceil a \rceil \le \lfloor U_j \rfloor + 1 \] olur. Demek ki ağaçta eklenebilecek bütün kısıtlar \[ x_j \le t \ \ (0 \le t \le \lfloor U_j \rfloor), \qquad x_j \ge t \ \ (1 \le t \le \lfloor U_j \rfloor + 1) \] biçimindedir ve her \(j\) için bunların sayısı \(2(\lfloor U_j \rfloor + 1)\)’dir; hepsinin sayısı sonludur. Buna \(N\) diyelim.
Ağacın kökten başlayan herhangi bir yolu boyunca eklenen kısıtların hepsi farklıdır. Gerçekten, bir alt problemde eklenen yeni kısıt, o alt problemin rahatlatılmış optimumu tarafından sağlanmaz (Önerme 13.1); alt problemin kendi kısıtlarını ise bu optimum sağlar. Öyleyse yeni kısıt alt problemin kısıtları arasında yoktu. Bu yüzden bir yol üzerinde en fazla \(N\) dallanma olabilir, yani ağacın derinliği en fazla \(N\)’dir. Her alt problem en fazla iki yeni alt problem ürettiğinden ağaçta en fazla \(1 + 2 + 2^2 + \dots + 2^N\) alt problem bulunur. Bu sayı sonludur ve yöntem sonlu adımda durur. \(\blacksquare\)
Teorem 13.2 (Dal-Sınır Yönteminin Doğruluğu) Maksimum tipinde bir TP probleminin rahatlatılmış LP probleminin uygun bölgesi sınırlı olsun ve dal-sınır yöntemi bütün alt problemler budanınca dursun.
- Hiç aday çözüm bulunmamışsa TP probleminin uygun çözümü yoktur.
- Aday çözüm bulunmuşsa en büyük \(z\) değerli aday TP probleminin optimal çözümüdür.
İspat
Ağaçta dallandırılmamış, yani budanmış alt problemlere yaprak diyelim. \(\vec{x}\) TP probleminin herhangi bir uygun çözümü olsun.
\(\vec{x}\) bir yaprağın uygun çözümüdür. \(\vec{x}\), Alt Problem 1’in tam sayılı bir uygun çözümüdür. Tam sayılı uygun çözümü olduğu bir alt problem dallandırılmışsa Önerme 13.1 gereği \(\vec{x}\) yeni alt problemlerden birinin tam sayılı uygun çözümüdür. Kökten başlayıp her seferinde bu alt probleme inersek, ağaç sonlu olduğundan (Önerme 13.2) sonunda bir \(L\) yaprağına varırız ve \(\vec{x}\), \(L\)’nin uygun çözümüdür.
\(z(\vec{x})\), son A.S değerini aşmaz. \(L\)’nin rahatlatılmış optimal değeri \(z_L\) olsun. Teorem 13.1 gereği \(z(\vec{x}) \le z_L\)’dir. \(L\) üç durumdan biriyle budanmıştır:
- D2 olamaz, çünkü \(\vec{x}\), \(L\)’nin bir uygun çözümüdür.
- D3 ise \(L\)’nin optimumu bir adaydır; \(z_L\) bu adayın değeridir ve en iyi adayın değerini aşmaz.
- D1 ise budama anındaki A.S için \(z_L \le \text{A.S}\)’dir. A.S yalnız büyüyebildiği için bu, son A.S değerini de aşmaz. D1’in uygulanabilmesi için o anda A.S sonlu olmalıdır, yani bir aday bulunmuş olmalıdır.
Her durumda \(z(\vec{x}) \le z_L \le\) (en iyi adayın değeri) olur ve bir aday bulunmuştur.
Sonuç. Hiç aday bulunmamışsa yukarıdaki akıl yürütme bir çelişki verir; demek ki TP probleminin uygun çözümü yoktur. Aday bulunmuşsa en iyi aday TP probleminin uygun bir çözümüdür ve her uygun \(\vec{x}\) için \(z(\vec{x})\) onun değerini aşmaz; yani en iyi aday optimal çözümdür. \(\blacksquare\)
Minimum probleminde aynı ispat, eşitsizlikler ters çevrilerek ve A.S yerine Ü.S kullanılarak yapılır.
13.5 Dal-Sınır Yöntemi
Buraya kadar söylenenleri bir reçetede toplayalım ve iki örnekte uygulayalım.
- Tam sayı şartlarını kaldırıp Alt Problem 1’i, yani rahatlatılmış LP problemini çöz. Uygun çözümü yoksa TP probleminin de yoktur. Optimal \(z\) değeri Ü.S’dir; \(\text{A.S} = -\infty\) al.
- Optimal çözüm tam sayılıysa TP probleminin optimal çözümüdür; dur.
- Dallandırılacak bir alt problemde kesirli değer alan bir \(x_j = a\) seç ve \(x_j \le \lfloor a \rfloor\), \(x_j \ge \lceil a \rceil\) kısıtlarıyla iki yeni alt problem kur; sıradaki numaraları ver.
- Her yeni alt problemin rahatlatılmış problemini çöz ve karar ver: uygun değilse budanır (D2); çözüm tam sayılıysa adaydır, gerekirse A.S güncellenir ve budanır (D3); \(z \le \text{A.S}\) ise budanır (D1); hiçbiri değilse dallandırılmak üzere bekler.
- Bekleyen alt problem kaldıkça 3. ve 4. adımları tekrarla. Bekleyen bir alt problemi dallandırmadan önce, bu arada büyümüş olabilecek A.S ile yeniden karşılaştır.
- Bekleyen alt problem kalmayınca en iyi aday TP probleminin optimal çözümüdür; aday yoksa TP probleminin uygun çözümü yoktur.
Minimum probleminde Ü.S ile A.S yer değiştirir: Alt Problem 1’in değeri A.S olur, başlangıçta \(\text{Ü.S} = +\infty\) alınır, D1’de \(z \ge \text{Ü.S}\) olan alt problem budanır ve en küçük \(z\) değerli aday seçilir.
Örnek 13.6 (Dal-Sınır Yöntemiyle Bir Maksimum Problemi) \[ \begin{aligned} x_1 + x_2 &\le 6 \\ 9x_1 + 5x_2 &\le 45 \\ x_1, x_2 &\ge 0 \text{ ve tam sayı} \\ \max z &= 8x_1 + 5x_2 \end{aligned} \] problemini çözünüz.
Çözüm
İşaret koşulunda tam sayı olma şartı da bulunduğuna dikkat edelim: problem bir TP problemidir ve dal-sınır yöntemiyle çözülecektir. Alt problemlerin hepsi iki değişkenlidir; her birinin rahatlatılmış problemini grafik yöntemle, uygun bölgenin köşelerini tarayarak çözeceğiz.
Alt Problem 1. Rahatlatılmış problemin uygun bölgesi \((0, 0)\), \((5, 0)\), \((15/4, 9/4)\) ve \((0, 6)\) köşeli dörtgendir. \((15/4, 9/4)\) köşesi iki kısıt doğrusunun kesişimidir: \(9x_1 + 5x_2 = 45\) denkleminden \(5(x_1 + x_2) = 30\) denklemini çıkarırsak \(4x_1 = 15\), yani \(x_1 = 15/4\) ve \(x_2 = 6 - 15/4 = 9/4\) bulunur. Köşelerde \[ \begin{aligned} z(0, 0) &= 0, & z(5, 0) &= 40, \\[1mm] z\big(\tfrac{15}{4}, \tfrac94\big) &= 30 + \tfrac{45}{4} = \tfrac{165}{4}, & z(0, 6) &= 30 \end{aligned} \] olur. Alt Problem 1’in optimal çözümü \(x_1 = 15/4\), \(x_2 = 9/4\) ve \(z = 165/4 = 41{,}25\)’tir. Pür TP problemi için \(\text{Ü.S} = 165/4\)’tür; henüz aday olmadığından \(\text{A.S} = -\infty\)’dur.
Çözümde iki değişken de kesirlidir. Dallanan değişken keyfi seçilir; \(x_1\)’i seçelim. \(3 < x_1 = 15/4 < 4\) olduğundan \[ \begin{aligned} \text{Alt Problem 2} &= \text{Alt Problem 1} \cup \{x_1 \ge 4\}, \\[1mm] \text{Alt Problem 3} &= \text{Alt Problem 1} \cup \{x_1 \le 3\} \end{aligned} \] alt problemleri kurulur.
| Alt Problem 2 | Alt Problem 3 |
|---|---|
| \(x_1 + x_2 \le 6\) | \(x_1 + x_2 \le 6\) |
| \(9x_1 + 5x_2 \le 45\) | \(9x_1 + 5x_2 \le 45\) |
| \(x_1 \ge 4\) | \(x_1 \le 3\) |
| \(x_1, x_2 \ge 0\) ve tam sayı | \(x_1, x_2 \ge 0\) ve tam sayı |
| \(\max z = 8x_1 + 5x_2\) | \(\max z = 8x_1 + 5x_2\) |
| Rahatlatılmış optimum: \(x_1 = 4\), \(x_2 = \frac{9}{5}\), \(\max z = 41\) | Rahatlatılmış optimum: \(x_1 = 3\), \(x_2 = 3\), \(\max z = 39\) |
Alt Problem 3. \(x_1 \le 3\) kısıtı bölgenin sol parçasını alır; köşeler \((0, 0)\), \((3, 0)\), \((3, 3)\) ve \((0, 6)\)’dır. \((3, 3)\) noktası \(x_1 = 3\) ile \(x_1 + x_2 = 6\) doğrularının kesişimidir ve \(9 \cdot 3 + 5 \cdot 3 = 42 \le 45\) olduğundan uygundur. Köşelerde \(z\) değerleri sırasıyla \(0\), \(24\), \(39\) ve \(30\)’dur. Optimum \(x_1 = 3\), \(x_2 = 3\), \(z = 39\)’dur. Bütün karar değişkenleri tam sayı olduğundan bu bir uygun çözüm ve aday çözümdür: \(\text{A.S} = 39\) olur ve Alt Problem 3 budanır (D3).
Alt Problem 2. \(x_1 \ge 4\) kısıtı bölgenin sağındaki küçük üçgeni alır; köşeler \((4, 0)\), \((5, 0)\) ve \((4, 9/5)\)’tir. \((4, 9/5)\) noktası \(x_1 = 4\) ile \(9x_1 + 5x_2 = 45\) doğrularının kesişimidir (\(5x_2 = 9\)) ve \(4 + 9/5 = 29/5 \le 6\) olduğundan uygundur. Köşelerde \[ z(4, 0) = 32, \quad z(5, 0) = 40, \quad z\big(4, \tfrac95\big) = 32 + 9 = 41 \] olur. Optimum \(x_1 = 4\), \(x_2 = 9/5\), \(z = 41\)’dir. \(41 > 39 = \text{A.S}\) olduğundan D1 uygulanmaz; \(x_2\) kesirli olduğu için dallanmaya devam edilir.
\(1 < x_2 = 9/5 < 2\) olduğundan yeni alt problemler şunlardır: \[ \begin{aligned} \text{Alt Problem 4} &= \text{Alt Problem 2} \cup \{x_2 \ge 2\}, \\[1mm] \text{Alt Problem 5} &= \text{Alt Problem 2} \cup \{x_2 \le 1\}. \end{aligned} \]
| Alt Problem 4 | Alt Problem 5 |
|---|---|
| \(x_1 + x_2 \le 6\) | \(x_1 + x_2 \le 6\) |
| \(9x_1 + 5x_2 \le 45\) | \(9x_1 + 5x_2 \le 45\) |
| \(x_1 \ge 4\) | \(x_1 \ge 4\) |
| \(x_2 \ge 2\) | \(x_2 \le 1\) |
| \(x_1, x_2 \ge 0\) ve tam sayı | \(x_1, x_2 \ge 0\) ve tam sayı |
| \(\max z = 8x_1 + 5x_2\) | \(\max z = 8x_1 + 5x_2\) |
| Uygun çözüm yok | Rahatlatılmış optimum: \(x_1 = \frac{40}{9}\), \(x_2 = 1\), \(\max z = \frac{365}{9}\) |
Alt Problem 4. Alt Problem 2 için çizdiğimiz üçgenin en yüksek noktası \(x_2 = 9/5\)’tir; bu üçgen ile \(x_2 \ge 2\) yarı düzleminin arakesiti boştur. Cebirle de görülür: \(x_1 \ge 4\) ve \(x_2 \ge 2\) ise \(9x_1 + 5x_2 \ge 36 + 10 = 46 > 45\) olur. Alt Problem 4 uygun değildir, TP probleminin optimal çözümünü veremez ve bu yüzden budanır (D2).
Alt Problem 5. Alt Problem 2’nin üçgeni ile \(x_2 \le 1\) yarı düzleminin arakesiti \((4, 0)\), \((5, 0)\), \((40/9, 1)\) ve \((4, 1)\) köşeli dörtgendir. \((40/9, 1)\) noktası \(x_2 = 1\) ile \(9x_1 + 5x_2 = 45\) doğrularının kesişimidir: \(9x_1 = 40\). Ayrıca \(40/9 + 1 = 49/9 \le 6\)’dır. Köşelerde \[ \begin{aligned} z(4, 0) &= 32, & z(5, 0) &= 40, \\[1mm] z\big(\tfrac{40}{9}, 1\big) &= \tfrac{320}{9} + 5 = \tfrac{365}{9}, & z(4, 1) &= 37 \end{aligned} \] olur. Optimum \(x_1 = 40/9\), \(x_2 = 1\), \(z = 365/9 \approx 40{,}56\)’dır. \(365/9 > 39 = \text{A.S}\) olduğundan budanmaz; \(x_1\) için bulunan değer tam sayı olmadığından \(x_1\) seçilerek tekrar dallanma yapılır.
\(4 < x_1 = 40/9 < 5\) eşitsizliğinden yeni alt problemler oluşturulur: \[ \begin{aligned} \text{Alt Problem 6} &= \text{Alt Problem 5} \cup \{x_1 \ge 5\}, \\[1mm] \text{Alt Problem 7} &= \text{Alt Problem 5} \cup \{x_1 \le 4\}. \end{aligned} \]
| Alt Problem 6 | Alt Problem 7 |
|---|---|
| \(x_1 + x_2 \le 6\) | \(x_1 + x_2 \le 6\) |
| \(9x_1 + 5x_2 \le 45\) | \(9x_1 + 5x_2 \le 45\) |
| \(x_1 \ge 4\) | \(x_1 \ge 4\) |
| \(x_1 \ge 5\) | \(x_1 \le 4\) |
| \(x_2 \le 1\) | \(x_2 \le 1\) |
| \(x_1, x_2 \ge 0\) ve tam sayı | \(x_1, x_2 \ge 0\) ve tam sayı |
| \(\max z = 8x_1 + 5x_2\) | \(\max z = 8x_1 + 5x_2\) |
| Rahatlatılmış optimum: \(x_1 = 5\), \(x_2 = 0\), \(\max z = 40\) | Rahatlatılmış optimum: \(x_1 = 4\), \(x_2 = 1\), \(\max z = 37\) |
Alt Problem 7. \(x_1 \ge 4\) ve \(x_1 \le 4\) birlikte \(x_1 = 4\) demektir. O zaman \(9x_1 + 5x_2 \le 45\) kısıtı \(x_2 \le 9/5\), \(x_1 + x_2 \le 6\) kısıtı \(x_2 \le 2\) verir; bunlardan daha güçlüsü \(x_2 \le 1\)’dir. Uygun bölge \((4, 0)\) ile \((4, 1)\) arasındaki doğru parçasıdır. Uç noktalarda \(z(4, 0) = 32\) ve \(z(4, 1) = 37\)’dir; optimum \(x_1 = 4\), \(x_2 = 1\), \(z = 37\)’dir. \(x_1\) ve \(x_2\) tam sayı olduğundan bu bir uygun çözümdür, optimal çözüm için adaydır. Ama \(37 < 39 = \text{A.S}\) olduğundan elimizdeki adaydan kötüdür; A.S değişmez ve Alt Problem 7 budanır (D3).
Alt Problem 6. \(x_1 \ge 5\) ise \(9x_1 \ge 45\) olur; \(9x_1 + 5x_2 \le 45\) kısıtı ancak \(x_1 = 5\) ve \(x_2 = 0\) için sağlanır. Yani Alt Problem 5’in bölgesi ile \(x_1 \ge 5\) yarı düzleminin arakesiti yalnız \((5, 0)\) noktasıdır. Bu bölge için optimum \(x_1 = 5\), \(x_2 = 0\), \(z = 40\)’tır. Bütün karar değişkenleri tam sayı olduğundan bu da bir aday çözümdür. \(40 > 39\) olduğundan en iyi aday artık budur: \(\text{A.S} = 40\). Alt Problem 6 budanır (D3).
Sonuç. Bekleyen alt problem kalmadı. Üç aday çözüm bulundu: Alt Problem 3 (\(z = 39\)), Alt Problem 7 (\(z = 37\)) ve Alt Problem 6 (\(z = 40\)). En büyük değerli aday Alt Problem 6’dır ve Teorem 13.2 gereği TP probleminin optimal çözümüdür: \[ x_1 = 5, \quad x_2 = 0, \quad \max z = 40 . \] Bu değer, beklendiği gibi \(\text{Ü.S} = 165/4 = 41{,}25\) değerini geçmez. Bütün adımlar aşağıdaki ağaçta toplanmıştır.
Sağlama. Sonucu dal-sınır yönteminden bağımsız olarak da doğrulayalım. Tam sayılı noktalarda \(z = 8x_1 + 5x_2\) bir tam sayıdır ve Teorem 13.1 gereği \(z \le 165/4 = 41{,}25\)’tir; yani \(z \le 41\). \(z = 41\) olabilir mi? \(8x_1 = 41 - 5x_2\) eşitliğinde \(x_2 = 0, 1, \dots, 8\) denenirse sağ taraf \(41, 36, 31, 26, 21, 16, 11, 6, 1\) değerlerini alır; bunlardan yalnız \(16\) sayısı 8’e bölünür. Tek aday \(x_2 = 5\), \(x_1 = 2\) noktasıdır, o da \(2 + 5 = 7 > 6\) olduğundan uygun değildir. Demek ki tam sayılı uygun noktalarda \(z \le 40\)’tır ve \((5, 0)\) noktası bu değere ulaşır.
Son olarak yuvarlamanın burada da işe yaramadığına dikkat edelim: Alt Problem 1’in optimumu \((15/4, 9/4)\) en yakın tam sayılara yuvarlanırsa \((4, 2)\) elde edilir, ama \(9 \cdot 4 + 5 \cdot 2 = 46 > 45\) olduğundan bu nokta uygun değildir. \(\blacksquare\)
Bu örnekte D1 kuralı hiç kullanılmadı: her alt problem ya uygun değildi ya tam sayılı çözüm verdi ya da mevcut adaydan daha büyük bir sınır verdi. Aşağıdaki küçük örnekte üç budama kuralının üçü de işe karışıyor.
Örnek 13.7 (Üç Budama Kuralının Birlikte Kullanıldığı Bir Örnek) \[ \begin{aligned} 2x_1 + 3x_2 &\le 6 \\ 2x_1 + x_2 &\le 5 \\ x_1, x_2 &\ge 0 \text{ ve tam sayı} \\ \max z &= 3x_1 + 2x_2 \end{aligned} \] TP problemini dal-sınır yöntemiyle çözünüz. Kesirli değişkenlerden önce \(x_1\)’i seçiniz.
Çözüm
Alt problemleri numara sırasıyla çözeceğiz; her dallanmada önce \(\le\), sonra \(\ge\) dalına numara verelim.
Alt Problem 1. Rahatlatılmış problemin köşeleri \((0, 0)\), \((5/2, 0)\), \((9/4, 1/2)\) ve \((0, 2)\)’dir. \((9/4, 1/2)\) köşesi için \(2x_1 + 3x_2 = 6\) denkleminden \(2x_1 + x_2 = 5\) denklemini çıkarırsak \(2x_2 = 1\), yani \(x_2 = 1/2\) ve \(x_1 = 9/4\) bulunur. Köşelerde \[ \begin{aligned} z(0, 0) &= 0, & z\big(\tfrac52, 0\big) &= \tfrac{15}{2}, \\[1mm] z\big(\tfrac94, \tfrac12\big) &= \tfrac{27}{4} + 1 = \tfrac{31}{4}, & z(0, 2) &= 4 \end{aligned} \] olur. Optimum \(x_1 = 9/4\), \(x_2 = 1/2\), \(z = 31/4 = 7{,}75\)’tir: \(\text{Ü.S} = 31/4\), \(\text{A.S} = -\infty\). \(2 < 9/4 < 3\) olduğundan \[ \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öşeler \((0, 0)\), \((2, 0)\), \((2, 2/3)\) ve \((0, 2)\)’dir; \((2, 2/3)\) noktası \(x_1 = 2\) ile \(2x_1 + 3x_2 = 6\) doğrularının kesişimidir ve \(2 \cdot 2 + 2/3 = 14/3 \le 5\) olduğundan uygundur. \(z\) değerleri sırasıyla \(0\), \(6\), \(6 + 4/3 = 22/3\) ve \(4\)’tür. Optimum \(x_1 = 2\), \(x_2 = 2/3\), \(z = 22/3 \approx 7{,}33\)’tür. Henüz aday olmadığından dallanmaya devam edilir.
Alt Problem 3. \(2x_1 + x_2 \le 5\) ve \(x_2 \ge 0\) kısıtlarından \(x_1 \le 5/2 < 3\) çıkar; \(x_1 \ge 3\) ile çelişir. Uygun çözüm yoktur ve Alt Problem 3 budanır (D2).
Alt Problem 2’de \(0 < x_2 = 2/3 < 1\) olduğundan \(x_2\) değişkeninden dallanırız: \[ \begin{aligned} \text{Alt Problem 4} &= \text{Alt Problem 2} \cup \{x_2 \le 0\}, \\[1mm] \text{Alt Problem 5} &= \text{Alt Problem 2} \cup \{x_2 \ge 1\}. \end{aligned} \]
Alt Problem 4. \(x_2 \ge 0\) ve \(x_2 \le 0\) birlikte \(x_2 = 0\) demektir; kısıtlar \(2x_1 \le 6\), \(2x_1 \le 5\) ve \(x_1 \le 2\)’ye iner. Uygun bölge \((0, 0)\) ile \((2, 0)\) arasındaki doğru parçasıdır ve optimum \(x_1 = 2\), \(x_2 = 0\), \(z = 6\)’dır. Çözüm tam sayılıdır; bu bir aday çözümdür ve \(\text{A.S} = 6\) olur. Alt Problem 4 budanır (D3).
Alt Problem 5. Köşeler \((0, 1)\), \((3/2, 1)\) ve \((0, 2)\)’dir; \((3/2, 1)\) noktası \(x_2 = 1\) ile \(2x_1 + 3x_2 = 6\) doğrularının kesişimidir ve \(2 \cdot \tfrac32 + 1 = 4 \le 5\)’tir. \(z\) değerleri \(2\), \(9/2 + 2 = 13/2\) ve \(4\)’tür. Optimum \(x_1 = 3/2\), \(x_2 = 1\), \(z = 13/2 = 6{,}5\)’tir. \(13/2 > 6 = \text{A.S}\) olduğundan budanmaz; \(1 < 3/2 < 2\) olduğundan \(x_1\) değişkeninden dallanırız: \[ \begin{aligned} \text{Alt Problem 6} &= \text{Alt Problem 5} \cup \{x_1 \le 1\}, \\[1mm] \text{Alt Problem 7} &= \text{Alt Problem 5} \cup \{x_1 \ge 2\}. \end{aligned} \]
Alt Problem 6. Köşeler \((0, 1)\), \((1, 1)\), \((1, 4/3)\) ve \((0, 2)\)’dir; \((1, 4/3)\) noktası \(x_1 = 1\) ile \(2x_1 + 3x_2 = 6\) doğrularının kesişimidir. \(z\) değerleri \(2\), \(5\), \(3 + 8/3 = 17/3\) ve \(4\)’tür. Optimum \(x_1 = 1\), \(x_2 = 4/3\), \(z = 17/3 \approx 5{,}67\)’dir. Çözüm kesirlidir ama \(17/3 \le 6 = \text{A.S}\)’dir: bu alt problemin hiçbir tam sayılı çözümü elimizdeki adaydan iyi olamaz. Alt Problem 6 budanır (D1). Böylece örneğin \((1, 1)\) noktasına (\(z = 5\)) hiç bakmadan elemiş olduk.
Alt Problem 7. \(x_1 \ge 2\) ve \(x_2 \ge 1\) ise \(2x_1 + 3x_2 \ge 4 + 3 = 7 > 6\) olur. Uygun çözüm yoktur; Alt Problem 7 budanır (D2).
Sonuç. Bekleyen alt problem kalmadı. Tek aday Alt Problem 4’ün çözümüdür; TP probleminin optimal çözümü \[ x_1 = 2, \quad x_2 = 0, \quad \max z = 6 \] olur ve \(6 \le \text{Ü.S} = 31/4\)’tür.
Sağlama. Uygun tam sayılı noktaları tek tek sayalım. \(2x_1 + 3x_2 \le 6\) kısıtından \(x_2 \le 2\); \(x_2 = 0\) için \(x_1 \le 2\), \(x_2 = 1\) için \(x_1 \le 3/2\), \(x_2 = 2\) için \(x_1 = 0\) bulunur. Uygun noktalar \((0, 0)\), \((1, 0)\), \((2, 0)\), \((0, 1)\), \((1, 1)\) ve \((0, 2)\)’dir; \(z\) değerleri sırasıyla \(0\), \(3\), \(6\), \(2\), \(5\) ve \(4\)’tür. En büyüğü gerçekten \((2, 0)\) noktasındaki \(6\)’dır. \(\blacksquare\)
İki örnekte de alt problemler iki değişkenli olduğu için grafikle çözüldü. Değişken sayısı arttığında her alt problemin rahatlatılmış problemi simpleks yöntemle çözülür. Bunu her seferinde baştan yapmak gerekmez: yeni alt problem, dallandırılan alt problemin optimal tablosuna tek bir kısıt eklenerek elde edilir. Eklenen kısıt eski optimumu uygunsuz yapar ama \(z_j - c_j\) satırını bozmaz; tablo, Dual simpleks algoritması bölümündeki yöntemle birkaç iterasyonda yeniden optimal hâle getirilir.
Dallanan değişkenin ve alt problemlerin çözülme sırasının seçimi yalnız ağacın büyüklüğünü etkiler. Teorem 13.2 hangi seçim yapılırsa yapılsın yöntemin optimal değeri bulacağını garanti eder.
Bu bölümle kitabın konu anlatımı tamamlandı. Model kurmaktan başlayıp kanonik ve standart formlara, simpleks, büyük M ve iki faz yöntemlerine, duyarlılık analizine, dualiteye ve son olarak tam sayılı programlamaya uzanan bütün yöntemleri Alıştırmalar bölümündeki çözümlü problemlerle pekiştirebilirsiniz; orada bir dal-sınır problemi de bütün alt problemleri ve ağacıyla çözülüyor.