Examkin

Soru

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

Bir kamu kurumunun lojistik planlamasında kullanılmak üzere aşağıdaki tamsayılı programlama modeli oluşturulmuştur:

Maksimum Z=5x1+6x2\text{Maksimum } Z = 5x_1 + 6x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤5x_1 + x_2 \leq 5
4x1+7x2≤284x_1 + 7x_2 \leq 28
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problem Dal-Sınır (Branch and Bound) algoritması ile çözüldüğünde, elde edilecek en iyi tamsayılı çözümün amaç fonksiyonu değeri (ZZ) kaçtır?

  1. A
    24
  2. B
    25
  3. C
    26,75
  4. 27Cevap
  5. E
    27,67

Cevap

En iyi tamsayılı çözümün amaç fonksiyonu değeri 27'dir.
Problemin DP gevşetmesi çözüldüğünde Z=27,67Z=27,67 bulunur. En büyük kesirsel kısma sahip olan x2x_2 (2,67) üzerinden dallandırma yapıldığında, x2≤2x_2 \leq 2 kolunda (3,2)(3,2) tamsayılı çözümü ve Z=27Z=27 değeri elde edilir. Diğer kol olan x2≥3x_2 \geq 3 incelendiğinde ise en iyi değerin Z=26,75Z=26,75 olduğu görülür. 27 değeri 26,75'ten büyük olduğu için en iyi tamsayılı çözüm 27'dir.

Adım Adım Çözüm

1
Doğrusal Programlama (DP) gevşetmesini çözün.
x1=2,33x_1 = 2,33 (7/3), x2=2,67x_2 = 2,67 (8/3) ve Z=27,67Z = 27,67 (83/3)
Algoritmanın başlangıç noktasını (kök düğüm) belirlemek için tamsayı kısıtları kaldırılır.
2
En büyük kesirsel kısma sahip değişken üzerinden dallandırma yapın.
x2x_2 değişkeni üzerinden x2≤2x_2 \leq 2 ve x2≥3x_2 \geq 3 dalları oluşturulur.
Değişkenlerin tamsayı olmasını sağlamak için kesirsel değerler sınırlandırılır.
3
x2≤2x_2 \leq 2 dalını (Düğüm 1) çözün.
x1=3,x2=2x_1 = 3, x_2 = 2 ve Z=27Z = 27 (Tamsayılı çözüm)
Bu dalda ulaşılan en iyi çözüm tüm değişkenleri tamsayı olan uygun bir noktadır.
4
x2≥3x_2 \geq 3 dalını (Düğüm 2) çözün.
x1=1,75,x2=3x_1 = 1,75, x_2 = 3 ve Z=26,75Z = 26,75
Bu daldaki en iyi çözümün ZZ değeri (26,75), halihazırda bulunan tamsayılı çözümden (27) küçük olduğu için bu dal budanır.
5
Sonuçları karşılaştırarak optimumu belirleyin.
Z=27Z = 27
Elde edilen en büyük tamsayılı amaç fonksiyonu değeri çözüm olarak kabul edilir.

Anahtar Kavram

Dal-Sınır algoritmasında, bir düğümün üst sınırı (maksimizasyon için) mevcut en iyi tamsayılı çözümden küçükse, o dal daha iyi bir sonuç üretemeyeceği için budanır.

Daha Fazla Pratik

Karışık tamsayılı (mixed-integer) programlama modellerinde sadece tamsayı olması istenen değişkenler üzerinden dallandırma yapıldığını unutmayın.

Alternatif Yöntem

Grafik yöntemiyle tamsayılı noktalar (lattice points) belirlenerek amaç fonksiyonu her biri için hesaplanabilir. (0,4), (1,3), (2,2), (3,2), (4,1) ve (5,0) noktaları uygun bölgededir. Bunlar arasında Z değerini en büyük yapan (3,2) noktasıdır.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru