Examkin

Soru

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

Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir 0−10-1 tamsayılı minimizasyon probleminde, tüm amaç fonksiyonu katsayılarının negatif olmadığı (cj≥0c_j \geq 0) bilinmektedir. Algoritmanın herhangi bir adımında, incelenen bir düğümdeki kısmi çözümün amaç fonksiyonu değeri (ZkısmiZ_{kısmi}), o ana kadar elde edilmiş en iyi uygun çözümün değerine (Z∗Z^*) eşit veya bu değerden büyükse (Zkısmi≥Z∗Z_{kısmi} \geq Z^*), bu düğümün durumu hakkında aşağıdakilerden hangisi söylenebilir?

  1. Düğüm kapalı sayımlanır (budanır) çünkü bu daldan daha iyi bir çözüm gelmesi mümkün değildir.Cevap
  2. B
    Düğümden dallandırmaya devam edilir çünkü henüz atanmamış serbest değişkenler amaç değerini küçültebilir.
  3. C
    Düğüm uygun bir çözüm olarak kabul edilir ve tüm algoritma o anda sonlandırılır.
  4. D
    Kısmi çözümün kısıtları sağlayıp sağlamadığına bakılmaksızın yeni bir Z∗Z^* değeri olarak atanır.
  5. E
    Düğümdeki serbest değişkenlerin tamamına 0 değeri verilerek kısıtların uygunluğu kontrol edilir.

Cevap

Mevcut kısmi çözümün amaç değeri halihazırdaki en iyi çözüm değerine eşit veya ondan büyükse, katsayıların pozitif olması nedeniyle bu daldan daha iyi bir sonuç elde edilemez ve düğüm kapalı sayımlanır (budanır).
Balas algoritmasında amaç fonksiyonu katsayıları negatif olmayacak şekilde düzenlenir. Bir minimizasyon probleminde, bir dalın (düğümün) o ana kadarki maliyeti halihazırda bulduğumuz en iyi çözümün maliyetini geçmişse, o daldan devam ederek daha küçük bir maliyet elde etmemiz matematiksel olarak imkansızdır. Bu duruma algoritma literatüründe 'kapalı sayımlama' veya 'budama' denir.

Adım Adım Çözüm

1
Balas algoritmasının standart formunu hatırla.
Problem minimizasyon yapısındadır ve tüm cj≥0c_j \geq 0 katsayılarına sahiptir.
Algoritmanın temel işleyişi katsayıların negatif olmaması üzerine kuruludur.
2
Amaç fonksiyonu değerinin değişimini analiz et.
Yeni değişkenlerin çözüme dahil edilmesi (1 atanması), amaç değerini (ZZ) sadece artırabilir veya sabit bırakabilir.
Katsayılar cj≥0c_j \geq 0 olduğu için ZZ değeri azalmaz.
3
Sınır (Bound) kontrolü yap.
Eğer Zkısmi≥Z∗Z_{kısmi} \geq Z^* ise, bu daldan gelecek hiçbir çözüm mevcut en iyi çözümü (Z∗Z^*) iyileştiremez.
Daha iyi bir çözüm bulunma ihtimali kalmadığı için bu dalın incelenmesi durdurulur (kapalı sayımlama).

Anahtar Kavram

Balas Algoritmasında Budama (Fathoming) Kriteri
Bu soruyu puanla

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru