Examkin

Dal-Sınır (Branch and Bound) Algoritması

12 soru

Soru 1Soru →

Aşağıda bir tamsayılı programlama modeli verilmiştir:

Maksimum Z=5x1+4x2\text{Maksimum } Z = 5x_1 + 4x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤5,2x_1 + x_2 \leq 5,2
2x1+x2≤92x_1 + x_2 \leq 9
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin doğrusal programlama gevşetmesi (LP relaxation) çözüldüğünde optimal çözüm x1=3,8x_1 = 3,8 ve x2=1,4x_2 = 1,4 olarak bulunmuştur. Dal-Sınır (Branch and Bound) algoritmasında "en büyük kesirsel kısım" (most fractional part) kuralı uygulandığında, ilk dallandırma adımı hangi değişken üzerinden ve hangi kısıtlarla gerçekleştirilmelidir?

Cevabı ve açıklamayı göster

Cevap: x1x_1 değişkeni; x1≤3x_1 \leq 3 ve x1≥4x_1 \geq 4

Cevap

Dallandırma, kesirsel kısmı en büyük olan x1x_1 değişkeni üzerinden x1≤3x_1 \leq 3 ve x1≥4x_1 \geq 4 kısıtları eklenerek yapılmalıdır.
Verilen gevşetilmiş çözümde x1=3,8x_1 = 3,8 değerinin kesirsel kısmı (0,80,8), x2=1,4x_2 = 1,4 değerinin kesirsel kısmından (0,40,4) daha büyüktür. Bu durumda en büyük kesirsel kısım kuralına göre x1x_1 değişkeni seçilir. Değişkenin tamsayı olması gerektiğinden, 3,83,8 değerini dışarıda bırakacak şekilde x1≤3x_1 \leq 3 ve x1≥4x_1 \geq 4 kısıtları ile iki yeni alt problem (dal) oluşturulur.

Adım Adım Çözüm

1
Gevşetilmiş çözümdeki değişkenlerin kesirsel kısımlarını belirleme
x1=3,8x_1 = 3,8 için kesirsel kısım 0,80,8; x2=1,4x_2 = 1,4 için kesirsel kısım 0,40,4 bulunmuştur.
Dallandırma kuralını uygulamak için her değişkenin tamsayıdan ne kadar uzak olduğu hesaplanmalıdır.
2
En büyük kesirsel kısma sahip değişkeni seçme
0,8>0,40,8 > 0,4 olduğu için x1x_1 değişkeni seçilmiştir.
"En büyük kesirsel kısım" kuralı, tamsayı çözümden en uzak olan veya dallandığında çözüm alanını en çok etkilemesi beklenen değişkeni seçmeyi hedefler.
3
Dallandırma kısıtlarını oluşturma
x1≤⌊3,8⌋⇒x1≤3x_1 \leq \lfloor 3,8 \rfloor \Rightarrow x_1 \leq 3 ve x1≥⌈3,8⌉⇒x1≥4x_1 \geq \lceil 3,8 \rceil \Rightarrow x_1 \geq 4 kısıtları elde edilmiştir.
Tamsayı olmayan bölgeyi (3<x1<43 < x_1 < 4) çözüm kümesinden çıkarmak için değişkenin alt ve üst tamsayı değerleri yeni kısıtlar olarak atanır.

Anahtar Kavram

Dal-Sınır Algoritmasında Dallandırma Kuralı

Daha Fazla Pratik

Elde edilen bu dallardan hangisinin daha önce inceleneceğini belirlemek için 'en iyi sınır' (best bound) kuralını inceleyebilirsiniz.
Tahmini Süre:1m 30s
Soru 2Soru →

Aşağıda bir tamsayılı programlama modeli verilmiştir:

Maksimum Z=10x1+15x2\text{Maksimum } Z = 10x_1 + 15x_2
Kısıtlar:\text{Kısıtlar:}
3x1+2x2≤103x_1 + 2x_2 \leq 10
x1+4x2≤11x_1 + 4x_2 \leq 11
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin Dal-Sınır (Branch and Bound) algoritması ile çözümünde, başlangıç düğümündeki doğrusal programlama gevşetmesi sonucunda optimal çözüm x1=1,8x_1 = 1,8 ve x2=2,3x_2 = 2,3 olarak bulunmuştur.

Eğer algoritma gereği ilk dallandırma işlemi x1x_1 değişkeni üzerinden yapılacaksa, bu düğümden türetilecek iki yeni alt problem için modele eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x1≤1x_1 \leq 1 ve x1≥2x_1 \geq 2

Cevap

Dallandırma işlemi için x1 değişkenine eklenmesi gereken kısıtlar x1 ≤ 1 ve x1 ≥ 2 şeklindedir.
Doğru cevap, x1 değişkeninin mevcut kesirli değeri olan 1,8'i kapsayan tamsayılar 1 ve 2 olduğu için, bu değeri dışarıda bırakacak şekilde x1 ≤ 1 ve x1 ≥ 2 kısıtlarının eklenmesidir. Bu sayede arama uzayı ikiye bölünür ve 1 ile 2 arasındaki tamsayı olmayan bölge elenmiş olur.

Adım Adım Çözüm

1
Dallandırma değişkeninin mevcut değerini belirle.
x1=1,8x_1 = 1,8
Dallandırma kuralı, tamsayı olması gereken ancak kesirli çıkan değişken üzerinden uygulanır.
2
Değişkenin değerini kapsayan ardışık iki tamsayıyı (taban ve tavan değerleri) bul.
1 ve 2
1,8 değeri 1 ile 2 tamsayıları arasındadır (1<1,8<21 < 1,8 < 2).
3
Alt problemleri oluşturacak eşitsizlikleri formüle et.
x1≤1x_1 \leq 1 ve x1≥2x_1 \geq 2
Dal-Sınır algoritması, kesirli bölgeyi dışarıda bırakmak için değişkeni tamsayı sınırlarına zorlayan iki ayrı dal oluşturur.

Anahtar Kavram

Dal-Sınır algoritmasında dallandırma (branching) kuralı, kesirli değerin en yakın alt tamsayısından küçük-eşit ve en yakın üst tamsayısından büyük-eşit kısıtlarının eklenmesine dayanır.

İpuçları

1
Dallandırma yapılırken amaç, kesirli çıkan değişkenin değerini (1,8) içine alan tamsayı olmayan aralığı yok etmektir.
2
Değişkenin değerinden (1,8) küçük olan en büyük tamsayıyı ve büyük olan en küçük tamsayıyı belirleyin.
Tahmini Süre:1m 30s
Soru 3Soru →

Bir tamsayılı programlama modeli aşağıda verilmiştir:

Maksimum Z=8x1+5x2\text{Maksimum } Z = 8x_1 + 5x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤4,5x_1 + x_2 \leq 4,5
x1≤3,2x_1 \leq 3,2
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin doğrusal programlama gevşetmesi (LP relaxation) çözüldüğünde optimal sonuçlar x1=3,2x_1 = 3,2, x2=1,3x_2 = 1,3 ve Z=32,1Z = 32,1 olarak bulunmuştur. Dal-Sınır (Branch and Bound) algoritması uygulanarak x1x_1 değişkeni üzerinden dallandırma yapıldığında, x1≤3x_1 \leq 3 kısıtının eklendiği alt problemin doğrusal programlama gevşetmesine göre optimal amaç fonksiyonu değeri (ZZ) aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: 31,5

Cevap

Yeni kısıt altında hesaplanan optimal amaç fonksiyonu değeri 31,5'tir.
Dallandırma işlemi sonucunda x1≤3x_1 \leq 3 kısıtı modele eklenir. Bu durumda x1x_1 değişkeninin alabileceği en büyük değer 3 olur. x1=3x_1 = 3 değeri ilk kısıtta (x1+x2≤4,5x_1 + x_2 \leq 4,5) yerine yazıldığında x2≤1,5x_2 \leq 1,5 elde edilir. Amaç fonksiyonu 8(3)+5(1,5)8(3) + 5(1,5) işleminden 31,5 olarak hesaplanır.

Adım Adım Çözüm

1
Alt problemin kısıtlarını belirleme
x1+x2≤4,5x_1 + x_2 \leq 4,5, x1≤3,2x_1 \leq 3,2 ve x1≤3x_1 \leq 3
Dallandırma işlemi seçilen değişkenin tamsayı olmayan değerini içine almayan iki yeni kısıt kümesi oluşturur.
2
Kısıtları sadeleştirme
x1+x2≤4,5x_1 + x_2 \leq 4,5 ve x1≤3x_1 \leq 3
x1≤3x_1 \leq 3 kısıtı, x1≤3,2x_1 \leq 3,2 kısıtını kapsadığı için daha dar bir bölge tanımlar ve üsttekini gereksiz kılar.
3
Yeni uygun çözüm bölgesinde Z değerini maksimize etme
x1=3x_1 = 3 için x2=4,5−3=1,5x_2 = 4,5 - 3 = 1,5 bulunur.
x1x_1 katsayısı daha yüksek olduğu için sınır değerine (3) eşitlenerek x2x_2 değeri kısıt üzerinden hesaplanır.
4
Amaç fonksiyonunu hesaplama
Z=8(3)+5(1,5)=24+7,5=31,5Z = 8(3) + 5(1,5) = 24 + 7,5 = 31,5
Bulunan değişken değerleri amaç fonksiyonunda yerine konur.

Anahtar Kavram

Dal-Sınır algoritmasında bir düğümün gevşetilmiş çözümü, eklenen tamsayı kısıtları altında yeniden hesaplanır.

Daha Fazla Pratik

x1 >= 4 kısıtının neden uygun çözüm içermediğini (infeasible) kısıt doğruları üzerinden inceleyiniz.
Tahmini Süre:1m 30s
Soru 4Soru →

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin modeli şu şekildedir:

Maksimum Z=8x1+5x2\text{Maksimum } Z = 8x_1 + 5x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤6x_1 + x_2 \leq 6
9x1+5x2≤459x_1 + 5x_2 \leq 45
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Algoritmanın ilk adımında doğrusal programlama gevşetmesi çözülmüş ve başlangıç çözümü x1=3,75x_1 = 3,75 ve x2=2,25x_2 = 2,25 (Z=41,25Z = 41,25) olarak bulunmuştur. Algoritmanın standart kuralları gereği x1x_1 değişkeni üzerinden dallandırma (branching) yapılmasına karar verilmiştir.

Buna göre, x1≥4x_1 \geq 4 kısıtının eklendiği yeni alt problemin (düğümün) optimum amaç fonksiyonu değeri (ZZ) kaçtır?

Cevabı ve açıklamayı göster

Cevap: 41,00

Cevap

Eklenen kısıt altında bu alt problemin optimum amaç fonksiyonu değeri 41,00'dir.
Dallandırma kuralına göre x1≥4x_1 \geq 4 kısıtı modele eklendiğinde, x1x_1 değişkeni amaç fonksiyonu katsayısı daha büyük olduğu için sınır değerinde (44) sabitlenir. Bu durumda kısıtlar altında x2x_2 değişkeni en fazla 1,81,8 değerini alabilir. 8(4)+5(1,8)8(4) + 5(1,8) işlemi sonucunda bu düğüme ait amaç fonksiyonu değeri 41 olarak bulunur.

Adım Adım Çözüm

1
x1≥4x_1 \geq 4 kısıtını modele ekleyerek alt problemi tanımlayın.
Yeni kısıtlar: x1≥4x_1 \geq 4, x1+x2≤6x_1 + x_2 \leq 6 ve 9x1+5x2≤459x_1 + 5x_2 \leq 45.
Dallandırma işlemi, gevşetilmiş çözümdeki tamsayı olmayan değişkenin alt ve üst tam sayı sınırlarını kısıt olarak eklemektir.
2
Eklenen kısıtlar altında x2x_2 değişkeninin alabileceği en büyük değeri belirleyin.
x1=4x_1 = 4 için: 4+x2≤6⇒x2≤24 + x_2 \leq 6 \Rightarrow x_2 \leq 2 ve 9(4)+5x2≤45⇒5x2≤9⇒x2≤1,89(4) + 5x_2 \leq 45 \Rightarrow 5x_2 \leq 9 \Rightarrow x_2 \leq 1,8.
Maksimizasyon probleminde, ZZ fonksiyonunun katsayıları pozitif olduğundan x1x_1 ve x2x_2 değişkenlerinin mümkün olan en büyük değerleri alması gerekir. x2x_2 için en dar kısıt 1,81,8 değeridir.
3
Bulunan (x1,x2)(x_1, x_2) değerlerini amaç fonksiyonunda yerine koyun.
Z=8(4)+5(1,8)=32+9=41Z = 8(4) + 5(1,8) = 32 + 9 = 41.
Alt problemin (düğümün) sınır değerini (upper bound) bulmak için optimum nokta hesaplanır.

Anahtar Kavram

Dal-Sınır algoritmasında her bir dallandırma işlemi, tamsayı olmayan bölgeyi dışarıda bırakacak şekilde arama uzayını daraltan yeni kısıtlar ekleyerek alt problemler oluşturur.

Daha Fazla Pratik

Bu düğümden sonra x2=1,8x_2 = 1,8 değeri üzerinden yapılacak dallandırmanın sonuçlarını inceleyerek tamsayı çözüme ulaşmaya çalışın.
Tahmini Süre:1m 30s
Soru 5Soru →

Bir kamu kurumunun lojistik planlamasında kullanılmak üzere aşağıdaki tamsayılı programlama modeli oluşturulmuştur:

Maksimum Z=5x1+6x2\text{Maksimum } Z = 5x_1 + 6x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤5x_1 + x_2 \leq 5
4x1+7x2≤284x_1 + 7x_2 \leq 28
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problem Dal-Sınır (Branch and Bound) algoritması ile çözüldüğünde, elde edilecek en iyi tamsayılı çözümün amaç fonksiyonu değeri (ZZ) kaçtır?

Cevabı ve açıklamayı göster

Cevap: 27

Cevap

En iyi tamsayılı çözümün amaç fonksiyonu değeri 27'dir.
Problemin DP gevşetmesi çözüldüğünde Z=27,67Z=27,67 bulunur. En büyük kesirsel kısma sahip olan x2x_2 (2,67) üzerinden dallandırma yapıldığında, x2≤2x_2 \leq 2 kolunda (3,2)(3,2) tamsayılı çözümü ve Z=27Z=27 değeri elde edilir. Diğer kol olan x2≥3x_2 \geq 3 incelendiğinde ise en iyi değerin Z=26,75Z=26,75 olduğu görülür. 27 değeri 26,75'ten büyük olduğu için en iyi tamsayılı çözüm 27'dir.

Adım Adım Çözüm

1
Doğrusal Programlama (DP) gevşetmesini çözün.
x1=2,33x_1 = 2,33 (7/3), x2=2,67x_2 = 2,67 (8/3) ve Z=27,67Z = 27,67 (83/3)
Algoritmanın başlangıç noktasını (kök düğüm) belirlemek için tamsayı kısıtları kaldırılır.
2
En büyük kesirsel kısma sahip değişken üzerinden dallandırma yapın.
x2x_2 değişkeni üzerinden x2≤2x_2 \leq 2 ve x2≥3x_2 \geq 3 dalları oluşturulur.
Değişkenlerin tamsayı olmasını sağlamak için kesirsel değerler sınırlandırılır.
3
x2≤2x_2 \leq 2 dalını (Düğüm 1) çözün.
x1=3,x2=2x_1 = 3, x_2 = 2 ve Z=27Z = 27 (Tamsayılı çözüm)
Bu dalda ulaşılan en iyi çözüm tüm değişkenleri tamsayı olan uygun bir noktadır.
4
x2≥3x_2 \geq 3 dalını (Düğüm 2) çözün.
x1=1,75,x2=3x_1 = 1,75, x_2 = 3 ve Z=26,75Z = 26,75
Bu daldaki en iyi çözümün ZZ değeri (26,75), halihazırda bulunan tamsayılı çözümden (27) küçük olduğu için bu dal budanır.
5
Sonuçları karşılaştırarak optimumu belirleyin.
Z=27Z = 27
Elde edilen en büyük tamsayılı amaç fonksiyonu değeri çözüm olarak kabul edilir.

Anahtar Kavram

Dal-Sınır algoritmasında, bir düğümün üst sınırı (maksimizasyon için) mevcut en iyi tamsayılı çözümden küçükse, o dal daha iyi bir sonuç üretemeyeceği için budanır.

Daha Fazla Pratik

Karışık tamsayılı (mixed-integer) programlama modellerinde sadece tamsayı olması istenen değişkenler üzerinden dallandırma yapıldığını unutmayın.

Alternatif Yöntem

Grafik yöntemiyle tamsayılı noktalar (lattice points) belirlenerek amaç fonksiyonu her biri için hesaplanabilir. (0,4), (1,3), (2,2), (3,2), (4,1) ve (5,0) noktaları uygun bölgededir. Bunlar arasında Z değerini en büyük yapan (3,2) noktasıdır.
Tahmini Süre:2m 30s
Soru 6Soru →

Aşağıda verilen saf tamsayılı programlama modeli Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir:

Maksimum Z=4x1+5x2\text{Maksimum } Z = 4x_1 + 5x_2
Kısıtlar:\text{Kısıtlar:}
2x1+3x2≤122x_1 + 3x_2 \leq 12
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Algoritmanın başlangıç adımında (kök düğüm) elde edilen doğrusal gevşetme çözümü x1=2,4x_1 = 2,4 ve x2=2,4x_2 = 2,4 olarak bulunmuştur. x1x_1 değişkeni üzerinden dallanma (branching) yapılmasına karar verilmiştir.

Buna göre, bu dallanma sonucunda oluşturulacak iki yeni alt problemin kısıtları aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x1≤2x_1 \leq 2 ve x1≥3x_1 \geq 3

Cevap

Dallanma kısıtları, değişkenin mevcut kesirli değerini dışarıda bırakacak şekilde en yakın tamsayı sınırları olan küçük-eşit 2 ve büyük-eşit 3 şeklinde belirlenmelidir.
Dal-Sınır algoritmasında, tamsayı olması gereken bir değişkenin doğrusal gevşetme çözümündeki değeri vv ise, bu düğümden dallanma yapılırken değişkenin bu kesirli değerini içine alan [⌊v⌋,⌈v⌉][\lfloor v \rfloor, \lceil v \rceil] aralığı çözüm kümesinden atılır. Bu durumda x1=2,4x_1 = 2,4 için taban değer 2, tavan değer 3'tür. Dolayısıyla yeni kısıtlar x1≤2x_1 \leq 2 ve x1≥3x_1 \geq 3 olarak belirlenir.

Adım Adım Çözüm

1
Dallanma yapılacak değişkenin değerini belirleme
x1=2,4x_1 = 2,4
Soruda dallanmanın x1x_1 değişkeni üzerinden yapılacağı belirtilmiştir.
2
Değişken değerinin tamsayı sınırlarını hesaplama
Alt sınır: ⌊2,4⌋=2\lfloor 2,4 \rfloor = 2, Üst sınır: ⌈2,4⌉=3\lceil 2,4 \rceil = 3
Dal-Sınır algoritması kuralı gereği değişkenin bulunduğu aralıktaki tamsayı komşuları bulunur.
3
Yeni kısıtları oluşturma
x1≤2x_1 \leq 2 ve x1≥3x_1 \geq 3
Sürekli olan uygun bölgeyi, kesirli kısmı dışarıda bırakacak şekilde iki ayrık alt bölgeye bölmek için bu kısıtlar eklenir.

Anahtar Kavram

Dal-Sınır Algoritması Dallanma Kuralı

Daha Fazla Pratik

Karma tamsayılı programlama modellerinde sadece tamsayı olması gereken değişkenler üzerinden dallanma yapıldığını unutmayınız.
Tahmini Süre:45s
Soru 7Soru →

Saf tamsayılı bir doğrusal programlama problemi Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir. Bir çözüm adımında, gevşetilmiş (relaxed) çözümden elde edilen sonuçlarda x1=4,6x_1 = 4,6 değeri bulunmuştur. Algoritma gereği bu değişken üzerinden yapılacak olan ilk dallandırma (branching) işleminde modele eklenecek yeni kısıtlar aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5

Cevap

Dallandırma kuralına göre eklenecek kısıtlar x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5 şeklinde olmalıdır.
Dal-Sınır algoritmasında, bir değişken vv gibi kesirli bir değer aldığında, mevcut çözüm bölgesini tamsayı olmayan kısmı (⌊v⌋<x<⌈v⌉ \lfloor v \rfloor < x < \lceil v \rceil ) dışarıda bırakacak şekilde ikiye bölmemiz gerekir. x1=4,6x_1 = 4,6 için alt tamsayı sınırı 4, üst tamsayı sınırı ise 5'tir. Bu nedenle x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5 kısıtları eklenerek iki yeni alt problem oluşturulur.

Adım Adım Çözüm

1
Tamsayılı olması gereken ancak kesirli sonuç veren değişkenin belirlenmesi
x1=4,6x_1 = 4,6
Dal-Sınır algoritmasında dallandırma, tamsayı kısıtını sağlamayan değişkenler üzerinden yapılır.
2
Değişken değerini çevreleyen ardışık tamsayıların bulunması
⌊4,6⌋=4\lfloor 4,6 \rfloor = 4 ve ⌈4,6⌉=5\lceil 4,6 \rceil = 5
Değişkenin alabileceği olası tamsayı değerleri kesirli kısmın hemen altındaki ve üstündeki değerlerdir.
3
Kesirli bölgeyi dışarıda bırakacak eşitsizliklerin yazılması
x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5
Bu iki kısıt, 4<x1<54 < x_1 < 5 aralığındaki uygun olmayan tüm kesirli değerleri (4,6 dahil) çözüm kümesinden çıkarırken tamsayı noktaları korur.

Anahtar Kavram

Dal-Sınır Algoritmasında Dallandırma Kuralı
Tahmini Süre:45s
Soru 8Soru →

İki karar değişkenli (x1,x2≥0x_1, x_2 \geq 0) bir saf tamsayılı maksimizasyon problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Kök düğümde (P0) doğrusal programlama gevşetmesinin optimum çözümü x1=4,5x_1 = 4,5, x2=5,5x_2 = 5,5 ve amaç fonksiyonu değeri Z=144,5Z = 144,5 olarak hesaplanmıştır.

Algoritmanın ilerleyen adımlarında sırasıyla aşağıdaki düğümler ve çözümler elde edilmiştir:

- P1 Düğümü (P0'dan x1≤4x_1 \leq 4 dalı): x1=4x_1 = 4, x2=5,8x_2 = 5,8 ve Z=142,8Z = 142,8
- P2 Düğümü (P0'dan x1≥5x_1 \geq 5 dalı): x1=5x_1 = 5, x2=4x_2 = 4 ve Z=140Z = 140
- P3 Düğümü (P1'den x2≤5x_2 \leq 5 dalı): x1=3,5x_1 = 3,5, x2=5x_2 = 5 ve Z=138,5Z = 138,5
- P4 Düğümü (P1'den x2≥6x_2 \geq 6 dalı): Uygun çözüm alanına sahip değildir.

Bu bilgilere göre, algoritmanın güncel durumu ve P3 düğümü için verilecek karar aşağıdakilerden hangisinde doğru olarak ifade edilmiştir?

Cevabı ve açıklamayı göster

Cevap: P3 düğümünün amaç fonksiyonu değeri (Z=138,5Z=138,5), mevcut en iyi tamsayılı çözümden (Z=140Z=140) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından Z=140Z=140 kesin optimum olur.

Cevap

P3 düğümünün amaç fonksiyonu değeri (Z=138,5Z=138,5), mevcut en iyi tamsayılı çözümden (Z=140Z=140) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından Z=140Z=140 kesin optimum olur.
Maksimizasyon problemlerinde Dal-Sınır algoritması, bulduğu her tamsayılı çözümü (P2 düğümündeki Z=140Z=140) bir alt sınır olarak kabul eder. Aktif düğümlerden elde edilen gevşetilmiş Z değeri bu alt sınırdan küçük veya eşitse (P3 düğümündeki 138,5<140138,5 < 140), o dalın daha iyi bir çözüm üretme ihtimali kalmadığı için dallandırma durdurulur ve budanır. Tüm açık dallar kapandığında (P4 uygunsuz, P3 bound yedi, P2 zaten tamsayı), algoritma iterasyonu tamamlar ve elimizdeki en iyi tamsayılı çözüm (Z=140Z=140) global optimum olur.

Adım Adım Çözüm

1
Algoritmadaki mevcut en iyi tamsayılı çözümü (alt sınırı) belirle.
P2 düğümünde x1=5,x2=4x_1=5, x_2=4 tamsayı değerleri elde edilmiştir ve Z=140Z=140 olmuştur. Maksimizasyon probleminde ilk tamsayılı çözüm bir alt sınır (Lower Bound) oluşturur: LB = 140.
Mevcut en iyi tamsayılı çözüm, diğer düğümlerin dallandırılıp dallandırılmayacağına karar vermek için bir eşik değeri görevi görür.
2
P4 düğümünün durumunu değerlendir.
P4 düğümünde uygun çözüm olmadığı (infeasible) belirtilmiştir. Bu nedenle bu dal tamamen kapatılır (budanır).
Uygun çözüm alanı olmayan bir düğümden tamsayılı çözüm elde edilemez.
3
P3 düğümünün durumunu sınırlandırma (bound) kuralı ile değerlendir.
P3 düğümünde Z=138,5Z = 138,5'tir. Maksimizasyon probleminde bu daldan elde edilebilecek maksimum tamsayılı çözüm en fazla 138,5 (hatta ondan küçük) olabilir. Ancak elimizde zaten Z=140Z=140 veren bir çözüm vardır. 138,5<140138,5 < 140 olduğundan P3 düğümü dallandırılmaz ve budanır.
Bir düğümün amacı, mevcut en iyi tamsayılı çözümden daha iyi bir sonuç potansiyeli taşımaması durumunda sınırlandırma (fathoming by bound) kuralıyla elenmesidir.
4
Algoritmanın genel durumunu kontrol et.
P0'ın dalları olan P1 ve P2 incelenmiştir. P2 tamsayılıdır. P1'in dalları olan P3 (sınır nedeniyle) ve P4 (uygunsuzluk nedeniyle) budanmıştır. Açıkta (aktif) dallandırılacak hiçbir düğüm kalmamıştır.
Tüm aktif düğümler budandığında veya tamsayılı optimum çözüme ulaştığında algoritma sonlanır.

Anahtar Kavram

Dal-Sınır (Branch and Bound) Algoritmasında Budama Kuralları ve Optimum Çözüm Koşulu
Tahmini Süre:3m 0s
Soru 9Soru →

Bir kamu kurumunun tedarik zinciri ağında kullanılacak depo sayısını ve kapasitesini belirlemek amacıyla aşağıdaki saf tamsayılı maksimizasyon doğrusal programlama modeli kurulmuştur:

Maksimum Z=5x1+8x2\text{Maksimum } Z = 5x_1 + 8x_2
Kısıtlar:
x1+x2≤6x_1 + x_2 \leq 6
5x1+9x2≤455x_1 + 9x_2 \leq 45
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu model Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünün doğrusal programlama gevşetmesi çözüldüğünde optimum çözüm x1=2.25x_1 = 2.25, x2=3.75x_2 = 3.75 ve amaç fonksiyonu değeri Z=41.25Z = 41.25 olarak bulunmuştur. Algoritmanın kuralı gereği, ilk dallanma işlemi kesirsel kısmı en büyük olan değişken üzerinden yapılacaktır.

İlk dallanma işlemi sonucunda elde edilen alt problemlerin (düğümlerin) çözülmesiyle birlikte, algoritmanın güncel durumu ve sınır (bound) değerleri hakkında aşağıdakilerden hangisi doğrudur?

Cevabı ve açıklamayı göster

Cevap: x2x_2 değişkeni üzerinden x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 kısıtları ile iki alt düğüm oluşturulur; x2≤3x_2 \leq 3 kısıtlı düğümde Z=39Z=39 değerli tamsayılı çözüm bulunarak alt sınır (lower bound) 3939 olarak güncellenir, x2≥4x_2 \geq 4 kısıtlı düğüm ise Z=41Z=41 değerini verdiğinden incelenmeye devam edilir.

Cevap

İlk dallanma x2x_2 değişkeni üzerinden yapılarak x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 alt problemleri oluşturulur. x2≤3x_2 \leq 3 düğümünde tamsayılı Z=39Z=39 çözümü bulunarak alt sınır (lower bound) güncellenir. x2≥4x_2 \geq 4 düğümü ise Z=41Z=41 (ve kesirli x1x_1) değerini verdiği için incelenmeye devam edilir.
Doğru yaklaşımda algoritma kesirsel değeri en yüksek olan değişkeni seçer (x2=3.75x_2=3.75). x2≤3x_2 \leq 3 ve x2≥4x_2 \geq 4 dalları oluşturulur. x2≤3x_2 \leq 3 eklendiğinde sistem çözülürse x1=3x_1=3 bulunur ve tamsayılı (3,3)(3,3) noktasında amaç fonksiyonu Z=39Z=39 çıkar. Bu maksimizasyon problemi için referans alt sınırı (LB) oluşturur. x2≥4x_2 \geq 4 dalı çözüldüğünde ise x1=1.8x_1=1.8 ile Z=41Z=41 üst sınır değeri (UB) üretilir. Çıkan 4141 değeri, tamsayılı en iyi çözümümüz olan 3939'dan büyük olduğu için algoritma bu dalın budanamayacağına (kapatılamayacağına) hükmeder ve incelemeye devam eder.

Adım Adım Çözüm

1
Dallanma yapılacak değişkenin seçilmesi.
x1x_1'in kesirsel kısmı 0.250.25, x2x_2'nin kesirsel kısmı 0.750.75'tir. Kural gereği x2x_2 değişkeni seçilir.
Dal-Sınır algoritmasında daha hızlı yakınsama sağlamak için genellikle kesirsel kısmı 0.5'e en yakın veya en büyük olan değişken dallanma için seçilir.
2
Birinci alt problemin (x2≤3x_2 \leq 3) oluşturulması ve çözülmesi.
5x1+9(3)≤45⇒5x1≤18⇒x1≤3.65x_1 + 9(3) \leq 45 \Rightarrow 5x_1 \leq 18 \Rightarrow x_1 \leq 3.6 ve x1+3≤6⇒x1≤3x_1 + 3 \leq 6 \Rightarrow x_1 \leq 3. Maksimum x1x_1 değeri 33 olur. (3,3)(3, 3) noktasında Z=5(3)+8(3)=39Z = 5(3) + 8(3) = 39 bulunur.
Dallanan kısıt doğrusal programlama modeline eklenir ve maksimizasyon yönünde optimum köşe noktası hesaplanır.
3
Tamsayılı çözümün değerlendirilmesi.
(3,3)(3, 3) noktası tümüyle tamsayılıdır. Maksimizasyon probleminde geçerli bir tamsayılı çözüm bulunduğunda, bu değer mevcut alt sınır (Lower Bound) olarak kabul edilir. Yeni alt sınır: LB=39LB = 39.
Optimum tamsayılı çözüm en kötü ihtimalle bu değerde olacaktır.
4
İkinci alt problemin (x2≥4x_2 \geq 4) oluşturulması ve çözülmesi.
5x1+9(4)≤45⇒5x1≤9⇒x1≤1.85x_1 + 9(4) \leq 45 \Rightarrow 5x_1 \leq 9 \Rightarrow x_1 \leq 1.8. (1.8,4)(1.8, 4) noktasında Z=5(1.8)+8(4)=41Z = 5(1.8) + 8(4) = 41 bulunur.
Diğer dal incelenmeden optimum çözüm kesinleştirilemez.
5
Düğümlerin budanma (fathoming) durumunun kontrol edilmesi.
İkinci alt problemin amaç fonksiyonu değeri (Z=41Z=41), mevcut alt sınırdan (LB=39LB=39) daha büyük olduğu için budanamaz ve x1x_1 değişkeni kesirli (1.81.8) olduğu için dallanmaya bu düğümden devam edilir.
Eğer bir düğümün üst sınırı, mevcut en iyi tamsayılı çözümden küçük veya ona eşit olsaydı budanırdı. Ancak burada potansiyel olarak daha iyi bir çözüm barındırdığı için inceleme sürdürülmelidir.

Anahtar Kavram

Dal-Sınır algoritmasında maksimizasyon problemleri için düğüm oluşturma, doğrusal gevşetme çözümleriyle tamsayılı alt sınır (lower bound) bulma ve budama (fathoming) şartlarının analizi.
Soru 10Soru →

Bir üretim planlaması için oluşturulan iki değişkenli saf tamsayılı maksimizasyon problemi aşağıda verilmiştir:

Maksimum Z=3x1+4x2\text{Maksimum } Z = 3x_1 + 4x_2
Kısıtlar:\text{Kısıtlar:}
2x1+x2≤62x_1 + x_2 \leq 6
2x1+3x2≤92x_1 + 3x_2 \leq 9
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problem Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünde tamsayı kısıtları gevşetilerek çözülen doğrusal programlama modelinin optimal çözümü x1=2,25x_1 = 2,25, x2=1,5x_2 = 1,5 ve amaç fonksiyonu değeri Z=12,75Z = 12,75 olarak bulunmuştur.
Algoritmanın standart işleyişine göre, tamsayı olmayan değişkenler arasından en büyük kesirli kısma sahip olan değişken seçilerek ilk dallanma yapılacaktır.

Buna göre, kök düğümden yapılan bu dallanma işlemi sonucunda elde edilecek iki yeni alt düğümün gevşetilmiş (relaxed) amaç fonksiyonu (ZZ) değerleri aşağıdakilerden hangisinde doğru olarak verilmiştir?

Cevabı ve açıklamayı göster

Cevap: x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5

Cevap

Doğru değerler x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5'tir.
Doğru dallanma kuralı uygulanarak en büyük kesirli kısma sahip olan x2x_2 değişkeni seçilmiş ve x2≤1x_2 \leq 1 ile x2≥2x_2 \geq 2 dalları oluşturulmuştur. Her iki dal için doğrusal programlama modeli yeni kısıtlarla yeniden çözüldüğünde sırasıyla Z=11,5Z=11,5 ve Z=12,5Z=12,5 değerlerine ulaşılır.

Adım Adım Çözüm

1
Dallanma değişkenini belirleme
x1x_1'in kesirli kısmı 0,250,25 ve x2x_2'nin kesirli kısmı 0,500,50'dir.
Algoritma kuralı gereği en büyük kesirli kısma sahip olan değişken (x2x_2) üzerinden dallanma yapılır.
2
Dallanma kısıtlarını oluşturma
İki yeni alt düğüm için x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 kısıtları elde edilir.
x2=1,5x_2=1,5 tamsayı olmadığı için bir alt tamsayıya yuvarlanarak sol dal, bir üst tamsayıya yuvarlanarak sağ dal oluşturulur.
3
x2≤1x_2 \leq 1 dalı için problemi çözme
Mevcut kısıtlarda x2=1x_2=1 alındığında dar kısıt 2x1+1≤6⇒x1≤2,52x_1 + 1 \leq 6 \Rightarrow x_1 \leq 2,5 olur. Bu dal için Z=3(2,5)+4(1)=11,5Z = 3(2,5) + 4(1) = 11,5 bulunur.
Amaç fonksiyonunu maksimize etmek için kısıtların izin verdiği en büyük değerler olan x1=2,5x_1=2,5 ve x2=1x_2=1 seçilir.
4
x2≥2x_2 \geq 2 dalı için problemi çözme
Mevcut kısıtlarda x2=2x_2=2 alındığında dar kısıt 2x1+6≤9⇒x1≤1,52x_1 + 6 \leq 9 \Rightarrow x_1 \leq 1,5 olur. Bu dal için Z=3(1,5)+4(2)=12,5Z = 3(1,5) + 4(2) = 12,5 bulunur.
Tüm kısıtları aynı anda sağlayan en uygun değerler olan x1=1,5x_1=1,5 ve x2=2x_2=2 belirlenir.

Anahtar Kavram

Dal-Sınır Algoritmasında Düğüm Değerlendirme
Soru 11Soru →

Afet yönetimi alanında faaliyet gösteren bir STK, kısıtlı kaynaklarını en verimli şekilde değerlendirebilmek amacıyla karar değişkenleri x1x_1 (arama-kurtarma ekibi) ve x2x_2 (sağlık destek aracı) olan bir saf tamsayılı doğrusal programlama modeli tasarlamıştır.

Kurulan modelin amaç fonksiyonu Maksimum Z=7x1+5x2\text{Maksimum } Z = 7x_1 + 5x_2 şeklindedir ve kısıtlar şöyledir:
4x1+3x2≤254x_1 + 3x_2 \leq 25
2x1+x2≤102x_1 + x_2 \leq 10
x1,x2≥0x_1, x_2 \geq 0 ve tamsayı.

Modelin tamsayı kısıtları gevşetildiğinde kök düğümün (root node) optimum çözümü x1=2.5x_1 = 2.5, x2=5x_2 = 5 ve Z=42.5Z = 42.5 olarak bulunmuştur.
Bu problemi Dal-Sınır (Branch and Bound) algoritmasıyla çözerken, algoritmanın ilk aşamasında modele x1≥3x_1 \geq 3 kısıtı eklenerek yeni bir alt düğüm oluşturulmuştur.

Buna göre, oluşturulan bu yeni alt düğümün doğrusal programlama problemi çözüldüğünde elde edilecek çözümün durumu ve amaç fonksiyonu (ZZ) değeri aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: Tamsayılı bir çözüm bulunur ve bu dal budanır (fathomed), Z=41Z = 41

Cevap

Eklenen x1≥3x_1 \geq 3 kısıtı altında model çözüldüğünde en iyi tamsayılı çözüm olan (3,4)(3, 4) noktası elde edilir ve dal budanır, Z=41Z = 41 olur.
Düğümün modeli çözülürken x1≥3x_1 \geq 3 bölgesi incelendiğinde, maksimizasyon problemi olduğundan x1x_1'in 33 sınırında x2x_2'nin alabileceği maksimum değer aranır. 2x1+x2≤102x_1 + x_2 \leq 10 kısıtı x2≤4x_2 \leq 4 sınırını, 4x1+3x2≤254x_1 + 3x_2 \leq 25 kısıtı ise x2≤13/3x_2 \leq 13/3 sınırını getirir. En kısıtlayıcı sınır x2≤4x_2 \leq 4 olduğundan optimum nokta x1=3x_1=3, x2=4x_2=4 olur. Bu değerlerin ikisi de tamsayı olduğundan algoritma bu dalı 'tamsayılı çözüm bulundu' diyerek budar ve Z=41 adayı kaydedilir.

Adım Adım Çözüm

1
Oluşturulan yeni alt düğümün (node) modelini tanımla.
Maksimum Z=7x1+5x2Z = 7x_1 + 5x_2
Kısıtlar: 4x1+3x2≤254x_1 + 3x_2 \leq 25, 2x1+x2≤102x_1 + x_2 \leq 10, ve eklenen yeni kısıt x1≥3x_1 \geq 3.
Dal-Sınır algoritmasında her yeni düğüm, bir önceki düğümün kısıtlarına dallanma kısıtının eklenmesiyle oluşur.
2
Amaç fonksiyonunu maksimize etmek için x1x_1'in alabileceği en küçük sınır değeri olan x1=3x_1 = 3 değerini mevcut kısıtlarda yerine koyarak x2x_2 için üst sınırları hesapla.
1. Kısıt için: 4(3)+3x2≤25⇒12+3x2≤25⇒3x2≤13⇒x2≤4.334(3) + 3x_2 \leq 25 \Rightarrow 12 + 3x_2 \leq 25 \Rightarrow 3x_2 \leq 13 \Rightarrow x_2 \leq 4.33
2. Kısıt için: 2(3)+x2≤10⇒6+x2≤10⇒x2≤42(3) + x_2 \leq 10 \Rightarrow 6 + x_2 \leq 10 \Rightarrow x_2 \leq 4
x1x_1 artarken x2x_2'nin kapasite kısıtları nedeniyle alabileceği maksimum değeri bulmak gereklidir.
3
Elde edilen x2x_2 sınırlarından en kısıtlayıcı olanı seçerek düğümün optimum noktasını belirle.
x2≤4x_2 \leq 4 eşitsizliği daha kısıtlayıcıdır. Maksimum Z için x1=3x_1 = 3 ve x2=4x_2 = 4 seçilir.
Tüm kısıtların aynı anda sağlanması (uygun çözüm bölgesi) için en dar sınırın (minimum üst sınırın) geçerli olması gerekir.
4
Bulunan (3,4)(3, 4) noktasında amaç fonksiyonu değerini hesapla ve düğümün durumunu (tamsayılılık kontrolü) değerlendir.
Z=7(3)+5(4)=21+20=41Z = 7(3) + 5(4) = 21 + 20 = 41. Hem x1x_1 hem de x2x_2 tamsayı olduğu için dal 'tamsayılılık' gerekçesiyle budanır (fathomed).
Dal-sınır yönteminde, çözümü tamsayı çıkan düğümler dallandırılmaya devam edilmez; bunlar olası optimum çözüm (incumbent) adayı olarak kaydedilir.

Anahtar Kavram

Dal-Sınır Algoritmasında Alt Düğüm (Node) Değerlendirmesi ve Budama

Alternatif Yöntem

Grafik çözüm yöntemi kullanılarak da bu sonuca ulaşılabilir. Koordinat sisteminde kısıtlar çizilip x1=3x_1 = 3 doğrusunun sağında kalan uygun çözüm bölgesinin köşeleri incelendiğinde, (3,4)(3,4) noktasının bölgedeki en iyi tamsayılı köşe olduğu kolayca görülebilir.
Tahmini Süre:2m 0s
Soru 12Soru →

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin doğrusal programlama gevşetmesi (LP Relaxation) sonucunda elde edilen ilk çözümde x1=2,25x_1 = 2,25 ve x2=1,60x_2 = 1,60 değerleri bulunmuştur. Algoritma gereği x2x_2 değişkeni üzerinden dallandırma yapılmasına karar verilmiştir.

Buna göre, bu çözüm düğümünden (P0P_0) türetilecek olan iki yeni alt probleme eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

Cevabı ve açıklamayı göster

Cevap: x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2

Cevap

Dallandırma kısıtları, tamsayı olmayan değişken değerini kapsayan ardışık iki tamsayı kullanılarak x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 şeklinde oluşturulmalıdır.
Dal-Sınır algoritmasında, tamsayı olması gereken bir değişkenin gevşetilmiş çözümdeki değeri vv ise, dallandırma işlemi bu değeri dışarıda bırakacak şekilde x≤⌊v⌋x \leq \lfloor v \rfloor ve x≥⌈v⌉x \geq \lceil v \rceil kısıtlarının eklenmesiyle gerçekleştirilir. x2=1,60x_2 = 1,60 için bu sınırlar 11 ve 22 olduğundan, doğru kısıtlar x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 olur.

Adım Adım Çözüm

1
Dallandırma yapılacak değişkenin gevşetilmiş değerini belirleme
x2=1,60x_2 = 1,60
Soruda dallandırmanın x2x_2 değişkeni üzerinden yapılacağı belirtilmiştir.
2
Değerin alt ve üst tamsayı sınırlarını hesaplama
Alt tamsayı: ⌊1,60⌋=1\lfloor 1,60 \rfloor = 1; Üst tamsayı: ⌈1,60⌉=2\lceil 1,60 \rceil = 2
Dal-Sınır algoritması, tamsayı olmayan bölgeyi çözüm dışı bırakmak için değişkenin değerini çevreleyen tamsayıları kullanır.
3
Yeni kısıtları formüle etme
x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2
Mevcut uygun çözüm bölgesini ikiye bölerek tamsayı olmayan 1,601,60 değerini ortadan kaldırmak için bu iki kısıt alt problemlere eklenir.

Anahtar Kavram

Dal-Sınır (Branch and Bound) Algoritmasında Dallandırma Kuralı

İpuçları

1
Dallandırma işlemi, değişkenin tamsayı olmayan değerini içine alan tamsayı aralığını (1<1,60<21 < 1,60 < 2) bölmeyi hedefler.
2
Değişkenin değerini (1,601,60) bir altındaki tamsayıya yuvarlayarak üst sınırı, bir üstündeki tamsayıya yuvarlayarak alt sınırı oluşturmalısınız.
3
Elde edilen 1,601,60 değeri için eklenmesi gereken kısıtlar x2≤As¸ag˘ı Yuvarla(1,60)x_2 \leq \text{Aşağı Yuvarla}(1,60) ve x2≥Yukarı Yuvarla(1,60)x_2 \geq \text{Yukarı Yuvarla}(1,60) şeklindedir.

Daha Fazla Pratik

Dallandırma yapıldıktan sonra alt problemlerde elde edilen ZZ değerlerinin, ana problemin ZZ değerinden daha büyük olamayacağını (maksimizasyon için) hatırlayınız.
Tahmini Süre:1m 30s
Dal-Sınır (Branch and Bound) Algoritması Alıştırma Soruları — KPSS İstatistik | Examkin