Examkin

Soru

Zorluk: ZorDal-Sınır (Branch and Bound) Algoritması

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?

  1. A
    Kesirli bir çözüm bulunur ve dallanmaya devam edilir, Z=1283Z = \frac{128}{3}
  2. Tamsayılı bir çözüm bulunur ve bu dal budanır (fathomed), Z=41Z = 41Cevap
  3. C
    Kısıtları sağlayan uygun bir çözüm alanı yoktur (İnfeasible), dal budanır
  4. D
    Tamsayılı bir çözüm bulunur ve bu dal budanır, Z=46Z = 46
  5. E
    Kesirli bir çözüm bulunur ve dallanmaya devam edilir, Z=42.5Z = 42.5

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
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru