Examkin

Question

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

Aşağıda bir tamsayılı programlama modeli verilmiştir:

Maksimum Z=10x1+15x2\text{Maksimum } Z = 10x_1 + 15x_2
Kısıtlar:\text{Kısıtlar:}
3x1+2x2≤103x_1 + 2x_2 \leq 10
x1+4x2≤11x_1 + 4x_2 \leq 11
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin Dal-Sınır (Branch and Bound) algoritması ile çözümünde, başlangıç düğümündeki doğrusal programlama gevşetmesi sonucunda optimal çözüm x1=1,8x_1 = 1,8 ve x2=2,3x_2 = 2,3 olarak bulunmuştur.

Eğer algoritma gereği ilk dallandırma işlemi x1x_1 değişkeni üzerinden yapılacaksa, bu düğümden türetilecek iki yeni alt problem için modele eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

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

Answer

Dallandırma işlemi için x1 değişkenine eklenmesi gereken kısıtlar x1 ≤ 1 ve x1 ≥ 2 şeklindedir.
Doğru cevap, x1 değişkeninin mevcut kesirli değeri olan 1,8'i kapsayan tamsayılar 1 ve 2 olduğu için, bu değeri dışarıda bırakacak şekilde x1 ≤ 1 ve x1 ≥ 2 kısıtlarının eklenmesidir. Bu sayede arama uzayı ikiye bölünür ve 1 ile 2 arasındaki tamsayı olmayan bölge elenmiş olur.

Step-by-Step Solution

1
Dallandırma değişkeninin mevcut değerini belirle.
x1=1,8x_1 = 1,8
Dallandırma kuralı, tamsayı olması gereken ancak kesirli çıkan değişken üzerinden uygulanır.
2
Değişkenin değerini kapsayan ardışık iki tamsayıyı (taban ve tavan değerleri) bul.
1 ve 2
1,8 değeri 1 ile 2 tamsayıları arasındadır (1<1,8<21 < 1,8 < 2).
3
Alt problemleri oluşturacak eşitsizlikleri formüle et.
x1≤1x_1 \leq 1 ve x1≥2x_1 \geq 2
Dal-Sınır algoritması, kesirli bölgeyi dışarıda bırakmak için değişkeni tamsayı sınırlarına zorlayan iki ayrı dal oluşturur.

Key Concept

Dal-Sınır algoritmasında dallandırma (branching) kuralı, kesirli değerin en yakın alt tamsayısından küçük-eşit ve en yakın üst tamsayısından büyük-eşit kısıtlarının eklenmesine dayanır.

Hints

1
Dallandırma yapılırken amaç, kesirli çıkan değişkenin değerini (1,8) içine alan tamsayı olmayan aralığı yok etmektir.
2
Değişkenin değerinden (1,8) küçük olan en büyük tamsayıyı ve büyük olan en küçük tamsayıyı belirleyin.
Estimated Time:1m 30s
Rate this question

Topics

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

More questions from this topic