Examkin

Soru

Zorluk: OrtaKapalı Sayımlama (Balas) Algoritması

Balas’ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir 0−10-1 tamsayılı minimizasyon probleminde, o ana kadar elde edilen en iyi uygun çözümün amaç fonksiyonu değeri Z∗=15Z^* = 15 olarak kaydedilmiştir. Algoritmanın bir aşamasında incelenen bir düğümdeki (kısmi çözüm) atanmış değişkenlerin maliyet katsayıları toplamı 1212’dir. Bu düğümde serbest durumda bulunan üç değişkenin maliyet katsayıları ise sırasıyla 4,54, 5 ve 77’dir. Yapılan teknik incelemede, kısıtların tamamının sağlanabilmesi için bu serbest değişkenlerden en az birinin 11 değerini almasının zorunlu olduğu saptanmıştır.

Buna göre, incelenen bu düğümün durumu ile ilgili aşağıdakilerden hangisi doğrudur?

  1. A
    Atanmış değişkenlerin maliyeti (1212), mevcut en iyi çözümden (1515) küçük olduğu için dallandırma işlemine mutlaka devam edilmelidir.
  2. B
    Kısmi çözüm henüz uygun bir çözüm üretmediği için bu düğüm sadece "uygunsuzluk" (infeasibility) kriteri gerçekleşirse budanabilir.
  3. Kısıtları sağlamak için gereken en küçük ek maliyetle dahi toplam maliyet 1616 (12+412 + 4) olacağı ve bu değer Z∗=15Z^* = 15’ten büyük olduğu için düğüm budanmalıdır.Cevap
  4. D
    Elde edilen 1212 değeri 1515’ten küçük olduğundan, serbest değişkenlere uygun değerler atanarak 1212 değerinden daha küçük bir amaç fonksiyonu sonucuna ulaşılabilir.
  5. E
    Algoritma kuralları gereği, serbest değişkenlerin tamamı 11 yapılarak kısıtların sağlanıp sağlanmadığı kontrol edilmeden budama kararı verilemez.

Cevap

Kısıtları sağlamak için gereken en düşük maliyet eklendiğinde (12+4=1612 + 4 = 16) elde edilen alt sınır mevcut en iyi çözümden (1515) büyük olduğu için düğüm budanmalıdır.
Balas'ın Kapalı Sayımlama algoritmasında, bir düğümden (kısmi çözüm) elde edilebilecek en iyi sonuç bile mevcut en iyi çözümden (Z∗Z^*) daha kötüyse, o dalın daha fazla incelenmesine gerek kalmaz ve budama işlemi yapılır. Soruda kısıtların sağlanması için en az bir değişkenin seçilmesi gerektiği belirtilmiştir. En ucuz seçenek olan 44 birimlik maliyet eklendiğinde bile toplam maliyet 1616 olmaktadır. 16>1516 > 15 olduğu için bu dal kesinlikle elenmelidir.

Adım Adım Çözüm

1
Mevcut durumun analizi
Z∗=15Z^* = 15, mevcut maliyet =12= 12, serbest değişken katsayıları ={4,5,7}= \{4, 5, 7\}
Algoritmanın budama kriterlerini değerlendirmek için mevcut sınırı ve kısmi çözümün yükünü belirlemek gerekir.
2
Kısıt gereksiniminin belirlenmesi
En az bir serbest değişken 11 olmalıdır.
Kısmi çözümün kısıtları henüz sağlamadığı ve kısıtları sağlamak için ek maliyetin zorunlu olduğu anlaşılmaktadır.
3
Alt sınırın (Z-sınırı) hesaplanması
Minimum maliyet =12+min⁡(4,5,7)=12+4=16= 12 + \min(4, 5, 7) = 12 + 4 = 16
Bu daldan elde edilebilecek en iyimser (en düşük maliyetli) çözümün değerini bulmak için en küçük katsayılı serbest değişken seçilir.
4
Budama kriterinin uygulanması
16>1516 > 15 olduğu için düğüm budanır (fathomed).
Hesaplanan alt sınır mevcut en iyi çözümden (üst sınır) daha kötü olduğu için bu dalda daha iyi bir çözüm bulma imkanı kalmamıştır.

Anahtar Kavram

Balas algoritmasında amaç fonksiyonu (Z-sınırı) kriterine göre budama işlemi.
Bu soruyu puanla

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru