Examkin

Soru

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

Saf tamsayılı bir doğrusal programlama problemi Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir. Bir çözüm adımında, gevşetilmiş (relaxed) çözümden elde edilen sonuçlarda x1=4,6x_1 = 4,6 değeri bulunmuştur. Algoritma gereği bu değişken üzerinden yapılacak olan ilk dallandırma (branching) işleminde modele eklenecek yeni kısıtlar aşağıdakilerden hangisidir?

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

Cevap

Dallandırma kuralına göre eklenecek kısıtlar x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5 şeklinde olmalıdır.
Dal-Sınır algoritmasında, bir değişken vv gibi kesirli bir değer aldığında, mevcut çözüm bölgesini tamsayı olmayan kısmı (⌊v⌋<x<⌈v⌉ \lfloor v \rfloor < x < \lceil v \rceil ) dışarıda bırakacak şekilde ikiye bölmemiz gerekir. x1=4,6x_1 = 4,6 için alt tamsayı sınırı 4, üst tamsayı sınırı ise 5'tir. Bu nedenle x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5 kısıtları eklenerek iki yeni alt problem oluşturulur.

Adım Adım Çözüm

1
Tamsayılı olması gereken ancak kesirli sonuç veren değişkenin belirlenmesi
x1=4,6x_1 = 4,6
Dal-Sınır algoritmasında dallandırma, tamsayı kısıtını sağlamayan değişkenler üzerinden yapılır.
2
Değişken değerini çevreleyen ardışık tamsayıların bulunması
⌊4,6⌋=4\lfloor 4,6 \rfloor = 4 ve ⌈4,6⌉=5\lceil 4,6 \rceil = 5
Değişkenin alabileceği olası tamsayı değerleri kesirli kısmın hemen altındaki ve üstündeki değerlerdir.
3
Kesirli bölgeyi dışarıda bırakacak eşitsizliklerin yazılması
x1≤4x_1 \leq 4 ve x1≥5x_1 \geq 5
Bu iki kısıt, 4<x1<54 < x_1 < 5 aralığındaki uygun olmayan tüm kesirli değerleri (4,6 dahil) çözüm kümesinden çıkarırken tamsayı noktaları korur.

Anahtar Kavram

Dal-Sınır Algoritmasında Dallandırma Kuralı
Tahmini Süre:45s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru