Examkin

Soru

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

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?

  1. x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2Cevap
  2. B
    x2<1x_2 < 1 ve x2>2x_2 > 2
  3. C
    x2≤1x_2 \leq 1 ve x2≥1x_2 \geq 1
  4. D
    x2=1x_2 = 1 ve x2=2x_2 = 2
  5. E
    x2≤2x_2 \leq 2 ve x2≥3x_2 \geq 3

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

Konular

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

Bu konudan daha fazla soru