Examkin

Soru

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

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?

  1. x1≤2x_1 \leq 2 ve x1≥3x_1 \geq 3Cevap
  2. B
    x1<2x_1 < 2 ve x1>3x_1 > 3
  3. C
    x1≥2x_1 \geq 2 ve x1≤3x_1 \leq 3
  4. D
    x1≤2,4x_1 \leq 2,4 ve x1≥2,4x_1 \geq 2,4
  5. E
    x1≤3x_1 \leq 3 ve x1≥4x_1 \geq 4

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

Konular

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

Bu konudan daha fazla soru