Examkin

Question

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

İki karar değişkenli (x1,x2≥0x_1, x_2 \geq 0) bir saf tamsayılı maksimizasyon problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Kök düğümde (P0) doğrusal programlama gevşetmesinin optimum çözümü x1=4,5x_1 = 4,5, x2=5,5x_2 = 5,5 ve amaç fonksiyonu değeri Z=144,5Z = 144,5 olarak hesaplanmıştır.

Algoritmanın ilerleyen adımlarında sırasıyla aşağıdaki düğümler ve çözümler elde edilmiştir:

- P1 Düğümü (P0'dan x1≤4x_1 \leq 4 dalı): x1=4x_1 = 4, x2=5,8x_2 = 5,8 ve Z=142,8Z = 142,8
- P2 Düğümü (P0'dan x1≥5x_1 \geq 5 dalı): x1=5x_1 = 5, x2=4x_2 = 4 ve Z=140Z = 140
- P3 Düğümü (P1'den x2≤5x_2 \leq 5 dalı): x1=3,5x_1 = 3,5, x2=5x_2 = 5 ve Z=138,5Z = 138,5
- P4 Düğümü (P1'den x2≥6x_2 \geq 6 dalı): Uygun çözüm alanına sahip değildir.

Bu bilgilere göre, algoritmanın güncel durumu ve P3 düğümü için verilecek karar aşağıdakilerden hangisinde doğru olarak ifade edilmiştir?

  1. A
    P2 düğümünde ilk tamsayılı çözüm elde edildiği için algoritma anında sonlandırılır ve diğer düğümlerin durumuna bakılmaksızın Z=140Z=140 değeri optimum kabul edilir.
  2. P3 düğümünün amaç fonksiyonu değeri (Z=138,5Z=138,5), mevcut en iyi tamsayılı çözümden (Z=140Z=140) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından Z=140Z=140 kesin optimum olur.Answer
  3. C
    P3 düğümü tamsayılı çözüm vermediğinden algoritma devam etmeli ve x1=3,5x_1 = 3,5 değeri için kısıtlar x1<3x_1 < 3 ve x1>4x_1 > 4 şeklinde tanımlanarak yeni dallandırma yapılmalıdır.
  4. D
    P2 düğümündeki çözüm, kök düğümün gevşetilmiş üst sınır değerine (Z=144,5Z=144,5) ulaşamadığı için budanır ve P3 düğümünden standart dallandırma işlemlerine devam edilir.
  5. E
    Kök düğümde (P0) elde edilen gevşetilmiş çözüm değerlerinin en yakın tamsayıya yuvarlanmasıyla elde edilecek sonuç optimum kabul edileceği için, algoritma dallandırma yapmadan P0 üzerinden sonlanır.

Answer

P3 düğümünün amaç fonksiyonu değeri (Z=138,5Z=138,5), mevcut en iyi tamsayılı çözümden (Z=140Z=140) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından Z=140Z=140 kesin optimum olur.
Maksimizasyon problemlerinde Dal-Sınır algoritması, bulduğu her tamsayılı çözümü (P2 düğümündeki Z=140Z=140) bir alt sınır olarak kabul eder. Aktif düğümlerden elde edilen gevşetilmiş Z değeri bu alt sınırdan küçük veya eşitse (P3 düğümündeki 138,5<140138,5 < 140), o dalın daha iyi bir çözüm üretme ihtimali kalmadığı için dallandırma durdurulur ve budanır. Tüm açık dallar kapandığında (P4 uygunsuz, P3 bound yedi, P2 zaten tamsayı), algoritma iterasyonu tamamlar ve elimizdeki en iyi tamsayılı çözüm (Z=140Z=140) global optimum olur.

Step-by-Step Solution

1
Algoritmadaki mevcut en iyi tamsayılı çözümü (alt sınırı) belirle.
P2 düğümünde x1=5,x2=4x_1=5, x_2=4 tamsayı değerleri elde edilmiştir ve Z=140Z=140 olmuştur. Maksimizasyon probleminde ilk tamsayılı çözüm bir alt sınır (Lower Bound) oluşturur: LB = 140.
Mevcut en iyi tamsayılı çözüm, diğer düğümlerin dallandırılıp dallandırılmayacağına karar vermek için bir eşik değeri görevi görür.
2
P4 düğümünün durumunu değerlendir.
P4 düğümünde uygun çözüm olmadığı (infeasible) belirtilmiştir. Bu nedenle bu dal tamamen kapatılır (budanır).
Uygun çözüm alanı olmayan bir düğümden tamsayılı çözüm elde edilemez.
3
P3 düğümünün durumunu sınırlandırma (bound) kuralı ile değerlendir.
P3 düğümünde Z=138,5Z = 138,5'tir. Maksimizasyon probleminde bu daldan elde edilebilecek maksimum tamsayılı çözüm en fazla 138,5 (hatta ondan küçük) olabilir. Ancak elimizde zaten Z=140Z=140 veren bir çözüm vardır. 138,5<140138,5 < 140 olduğundan P3 düğümü dallandırılmaz ve budanır.
Bir düğümün amacı, mevcut en iyi tamsayılı çözümden daha iyi bir sonuç potansiyeli taşımaması durumunda sınırlandırma (fathoming by bound) kuralıyla elenmesidir.
4
Algoritmanın genel durumunu kontrol et.
P0'ın dalları olan P1 ve P2 incelenmiştir. P2 tamsayılıdır. P1'in dalları olan P3 (sınır nedeniyle) ve P4 (uygunsuzluk nedeniyle) budanmıştır. Açıkta (aktif) dallandırılacak hiçbir düğüm kalmamıştır.
Tüm aktif düğümler budandığında veya tamsayılı optimum çözüme ulaştığında algoritma sonlanır.

Key Concept

Dal-Sınır (Branch and Bound) Algoritmasında Budama Kuralları ve Optimum Çözüm Koşulu
Estimated Time:3m 0s
Rate this question

Topics

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

More questions from this topic