Examkin

Soru

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

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?

  1. x1x_1 değişkeni; x1≤3x_1 \leq 3 ve x1≥4x_1 \geq 4Cevap
  2. B
    x2x_2 değişkeni; x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2
  3. C
    x1x_1 değişkeni; x1<3x_1 < 3 ve x1>4x_1 > 4
  4. D
    x1x_1 değişkeni; x1≥3x_1 \geq 3 ve x1≤4x_1 \leq 4
  5. E
    x1x_1 değişkeni; x1≤3,8x_1 \leq 3,8 ve x1≥3,8x_1 \geq 3,8

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

Konular

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

Bu konudan daha fazla soru