Examkin

Question

Difficulty: MediumDal-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. 27Answer
  5. E
    27,67

Answer

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.

Step-by-Step Solution

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.

Key Concept

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.

Practice More

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

Alternative Method

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.
Estimated Time:2m 30s
Rate this question

Topics

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

More questions from this topic