tamsayılı programlama problemlerinin çözümünde kullanılan Balas’ın Kapalı Sayımlama (Additive) algoritmasında, standart bir minimizasyon problemi ele alınmaktadır. Algoritmanın belirli bir adımında, bir kısmi çözümün (düğümün) dallandırılması incelenirken; mevcut serbest değişkenlerin tamamı kısıtları sağlamaya en fazla katkıda bulunacak şekilde ( veya ) değerlendirilse dahi kısıtlardan en az birinin sağlanamadığı tespit edilmiştir. Bu durum ortaya çıktığında algoritmanın işleyişine göre aşağıdakilerden hangisi uygulanmalıdır?
- İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.Answer
- BSerbest değişkenler arasından yeni bir dallandırma değişkeni seçilerek alt düğümlere geçilir.
- CMevcut kısmi çözüm, o ana kadarki en iyi çözüm (üst sınır) olarak kaydedilir.
- DKısıtın yönü tersine çevrilerek algoritma bir sonraki iterasyona aktarılır.
- EAlgoritma tamamen sonlandırılır ve problemin uygun bir çözümü olmadığına karar verilir.
Answer
İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.
Doğru cevap, Balas algoritmasındaki 'uygunsuzluk nedeniyle kapatma' kriterini ifade etmektedir. Algoritmanın minimizasyon standart formunda, kısıtlar şeklindedir. Eğer eldeki serbest değişkenlerin kısıtı sağlamaya yönelik en büyük katkısı bile (pozitif katsayılar için değişkeni , negatifler için yaparak) mevcut yetersizliği gideremiyorsa, o daldan devam etmenin bir anlamı kalmaz ve dal budanır.
Step-by-Step Solution
Key Concept
Balas algoritmasında uygunsuzluk (infeasibility) nedeniyle budama kriteri.
Practice More
Balas algoritmasında 'üst sınır (Z*) yardımıyla budama' kriterini de incelemek, konunun tam anlaşılmasını sağlar.
Estimated Time:1m 30s