Branch and Bound Method

Tam sayılı programlama problemleri, değişkenlerin sadece tam sayı değerler alabildiği optimizasyon problemleridir. Bu tür problemlerin çözümü, doğrusal programlama (Linear Programming - LP) yöntemleriyle tam olarak yapılamaz çünkü LP çözümleri sürekli (kesirli) değerler üretir. İşte bu noktada, Branch and Bound yöntemi devreye girer ve bize optimal tam sayılı çözümleri bulmamızda yardımcı olur.

Genel Bakış: Doğrusal ve Tam Sayılı Programlama

Gerçek hayat problemlerini matematiksel modellerle ifade ederken, önce LP modellerini öğrendik. LP modelleri, değişkenlerin sürekli değerler alabildiği ve amaç fonksiyonunun doğrusal olduğu problemlerdir. Bu modelleri çözerken:

Grafiksel Yöntem: İki değişkenli problemlerde, kısıtları grafik üzerinde göstererek feasible region'ı (uygun bölge) belirledik ve köşe noktalarını inceledik.
Simplex Yöntemi: Daha yüksek boyutlu LP problemlerini çözmek için Simplex ve varyasyonları olan Two-Phase Simplex, Big M, Dual Simplex ve Revised Simplex yöntemlerini kullandık.

Ancak, bazı durumlarda değişkenlerin tam sayı değerler alması gerekir. Bu durumda Tam Sayılı Programlama (Integer Programming - IP) kullanılır. IP, LP'ye benzer ancak ek bir kısıt olarak değişkenlerin tam sayı olması şartını içerir.

Tam Sayılı Programlama ve Sorunları

Tam sayılı programlamada, LP yöntemlerini doğrudan kullanmak yeterli olmaz çünkü LP çözümleri genellikle kesirli değerler verir. Kesirli değerleri en yakın tam sayıya yuvarlamak ise çoğu zaman optimal olmayan veya kısıtları ihlal eden çözümler üretir.

Örnek Sorunlar:

Yuvarlama Problemi: Kesirli bir LP çözümünü yuvarlayarak elde edilen tam sayılı değerler, orijinal kısıtları sağlamayabilir.
Optimal Olmayan Çözümler: Yuvarlama ile elde edilen tam sayılı çözümler, gerçek optimal çözümden uzak olabilir.

Branch and Bound Yönteminin Tanıtımı

Branch and Bound yöntemi, tam sayılı programlama problemlerini çözmek için kullanılan bir böl ve fethet metodudur. Bu yöntemle, çözüm uzayını sistematik olarak bölerek ve bazı alt problemleri elimine ederek optimal tam sayılı çözümü buluruz.

Branch and Bound'un Temel Adımları

LP Relaxation Çözümü: İlk olarak, tam sayı kısıtlarını göz ardı ederek LP problemini çözeriz. Bu, bize problemin üst sınırını (upper bound) verir.
Dallanma (Branching): Eğer LP çözümü tam sayı değilse, kesirli değer alan bir değişken seçilir ve bu değişken üzerinde dallanma yapılır. Örneğin, $x_i$ değişkeni için $x_i \leq k$ ve $x_i \geq k+1$ şeklinde iki yeni alt problem oluşturulur, burada $k$ tam sayıdır.
Sınırlandırma (Bounding): Her alt problem için LP problemi çözülür. Eğer bir alt problemin çözümü mevcut en iyi tam sayılı çözümden daha kötü ise veya problem feasible değilse, o dalı keseriz.
Tekrarlama: Bu adımları, tüm alt problemler için tekrarlayarak optimal tam sayılı çözümü bulmaya çalışırız.

Örnek Problem

Amaç Fonksiyonu:

\text{Maksimize et} \quad Z = 5x_1 + 6x_2

Kısıtlar:

\begin{align*} 2x_1 + x_2 &\leq 12 \\ x_1 + x_2 &\leq 8 \\ x_1, x_2 &\geq 0 \\ x_1, x_2 &\in \mathbb{Z} \end{align*}

Adım 1: LP Relaxation Çözümü

Tam sayı kısıtlarını yok sayarak LP problemini çözelim.

Kısıtların Grafik Üzerinde Gösterimi:

Kısıt 1: $2x_1 + x_2 \leq 12$
Kısıt 2: $x_1 + x_2 \leq 8$
Kısıt 3: $x_1 \geq 0$ , $x_2 \geq 0$

Bu kısıtları grafik üzerinde çizerek feasible region'ı belirleriz. Kısıtların kesişim noktalarını bularak köşe noktalarını elde ederiz.

Köşe Noktaları ve Amaç Fonksiyonu Değerleri:

Nokta A: $(x_1, x_2) = (0, 0)$
$Z = 5(0) + 6(0) = 0$
Nokta B: $(x_1, x_2) = (0, 8)$
$Z = 5(0) + 6(8) = 48$
Nokta C: $(x_1, x_2) = (5, 0)$
$Z = 5(5) + 6(0) = 25$
Kesişim Noktası: Kısıtların kesişim noktasını bulmak için denklemleri çözelim.
$\begin{align*} 2x_1 + x_2 &= 12 \\ x_1 + x_2 &= 8 \\ \end{align*}$
Bu denklemleri çözdüğümüzde:
$\begin{align*} x_1 &= \frac{4}{1} = 4 \\ x_2 &= 4 \end{align*}$
Amaç fonksiyonu:
$Z = 5(4) + 6(4) = 20 + 24 = 44$

LP relaxation'ın optimal çözümü $(x_1, x_2) = (4, 4)$ ve $Z = 44$ .

Ancak $x_1$ ve $x_2$ tam sayı olsa da diğer mümkün çözümleri de incelememiz gerekiyor.

Adım 2: Dallanma ve Sınırlandırma

LP çözümü tam sayı olsa da, diğer dalları inceleyelim.

Dallanma Noktası Seçimi

Eğer LP çözümü kesirli olsaydı, kesirli değer alan değişkenlerden biri üzerinde dallanma yapacaktık. Ancak bu örnekte LP çözümü tam sayı değerler veriyor. Bu durumda, diğer integer çözümleri bulmak ve en iyi çözümü seçmek için tüm mümkün tam sayılı çözümleri inceleyebiliriz.

Mümkün Tam Sayılı Çözümler ve Amaç Fonksiyonu Değerleri

$(x_1, x_2) = (4, 4)$ , $Z = 44$
$(x_1, x_2) = (5, 3)$ , $Z = 5(5) + 6(3) = 25 + 18 = 43$
$(x_1, x_2) = (6, 2)$ , $Z = 5(6) + 6(2) = 30 + 12 = 42$
$(x_1, x_2) = (3, 5)$ , $Z = 5(3) + 6(5) = 15 + 30 = 45$

Görüyoruz ki $(x_1, x_2) = (3, 5)$ için $Z = 45$ elde ediyoruz, bu da daha yüksek bir değer.

Ancak bu çözüm kısıtları sağlar mı? Kontrol edelim:

Kısıt 1: $2(3) + 5 = 6 + 5 = 11 \leq 12$
Kısıt 2: $3 + 5 = 8 \leq 8$

Kısıtları sağlıyor. Dolayısıyla optimal tam sayılı çözümümüz $(x_1, x_2) = (3, 5)$ ve $Z = 45$ 'tir.

Adım 3: Sonuç

Optimal tam sayılı çözüm:

\begin{align*} x_1 &= 3 \\ x_2 &= 5 \\ Z &= 45 \end{align*}

Branch and Bound'un Önemli Noktaları

Dallanma (Branching): Kesirli çözümlerde, kesirli değer alan değişkenler üzerinde dallanarak çözüm uzayını böleriz.
Sınırlandırma (Bounding): Her alt problem için bulunan amaç fonksiyonu değerleri, mevcut en iyi tam sayılı çözümden daha düşükse, o dalı keseriz.
Feasible ve Infeasible Durumlar: Bir dalın çözümü kısıtları sağlamıyorsa (infeasible) veya artık daha iyi bir çözüm üretme potansiyeli yoksa, o dalı daha fazla incelemeyiz.
Optimal Çözüme Ulaşma: Bu yöntemle, tüm mümkün tam sayılı çözümleri sistematik olarak inceleyerek optimal çözüme ulaşırız.

Sonuç

Branch and Bound yöntemi, tam sayılı programlama problemlerini çözmek için etkili ve sistematik bir yaklaşımdır. Değişkenlerin tam sayı olması gerektiği durumlarda, LP yöntemleri yetersiz kalır ve optimal çözümü bulmak için özel teknikler gerekir. Branch and Bound ile, çözüm uzayını dallara ayırarak ve hesaplamaları sınırlandırarak, hem doğru hem de verimli bir şekilde optimal tam sayılı çözümleri elde ederiz.

Bu yöntem, çeşitli optimizasyon problemlerinde uygulanabilir ve matematiksel modelleme yeteneklerimizi geliştirir. Temel prensipleri anladıktan sonra, daha karmaşık problemlere bu yöntemi uygulayabilir ve gerçek hayattaki tam sayılı karar problemlerini çözebiliriz.