Examkin

Question

Difficulty: Very hardDal-Sınır (Branch and Bound) Algoritması

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?

  1. 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.Answer
  2. B
    x2x_2 değişkeni üzerinden dallanma yapılarak modele x2<4x_2 < 4 ve x2>3x_2 > 3 kısıtları eklenir; her iki düğümde de henüz tamsayılı çözüm elde edilemediği için problemin alt sınırı (lower bound) başlangıçtaki −∞-\infty değerinde kalır.
  3. C
    Dallanma, amaç fonksiyonuna katkısı olan ancak daha küçük değere sahip olan x1x_1 değişkeni üzerinden yapılarak modele x1≤2x_1 \leq 2 ve x1≥3x_1 \geq 3 kısıtları eklenir; kök düğümdeki 41.2541.25 değeri tüm algoritma için kesin alt sınır (lower bound) olarak kabul edilir.
  4. D
    Algoritma kuralı gereği x2x_2 değişkeni seçilir ancak maksimizasyon problemi olduğu için modele sadece kısıt yönünü daraltan x2≤3x_2 \leq 3 kısıtı eklenir, x2≥4x_2 \geq 4 kısıtı uygun çözüm alanını büyüteceği gerekçesiyle dikkate alınmaz.
  5. E
    Gevşetilmiş çözümdeki değerler en yakın tamsayılara yuvarlanarak doğrudan x1=2x_1=2 ve x2=4x_2=4 noktası optimum kabul edilir ve algoritma sonlandırılarak amaç fonksiyonu değeri Z=42Z=42 olarak belirlenir.

Answer

İ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.

Step-by-Step Solution

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.

Key Concept

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.
Rate this question

Topics

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

More questions from this topic