0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritmasında, bir minimizasyon modeli ele alınmaktadır. Algoritma akışında bir düğümün (alt problemin) 'uygunsuzluk' (infeasibility) nedeniyle kapalı sayımlanmasına (budanmasına) karar verilebilmesi için aşağıdaki durumlardan hangisinin gerçekleşmesi gerekir?
- Kısıtın sağlanması için gereken miktarın, serbest değişkenlerin o kısıta sağlayabileceği maksimum pozitif katkıdan daha büyük olmasıCevap
- BMevcut düğümde hesaplanan amaç fonksiyonu değerinin o ana kadar bulunan en iyi çözüm değerinden (Z*) daha yüksek olması
- CHenüz değer atanmamış tüm değişkenlerin 1 değerini alarak kısıtların tamamını sağlaması
- DProblemin amaç fonksiyonundaki tüm katsayıların negatif değerlerden oluşması
- EDeğişkenlerden birinin çözüm sürecinde 0 veya 1 dışında bir tamsayı değeri alması
Cevap
Balas algoritmasında bir düğüm, kısıtın sağlanması için gereken miktarın (zayiat/açık), serbest değişkenlerin kısıta yapabileceği maksimum pozitif katkıdan daha büyük olması durumunda uygunsuzluk nedeniyle budanır.
Doğru yanıt olan seçenek, Balas algoritmasındaki uygunsuzluk testini tanımlar. Eğer bir kısıttaki negatif sapma (açık), o kısıtta yer alan ve henüz değer atanmamış değişkenlerin kısıta katabileceği en büyük değerden daha büyükse, bu düğümün alt dallarında uygun bir çözüm bulunması matematiksel olarak imkansızdır. Bu nedenle düğüm 'uygunsuzluk' nedeniyle kapalı sayımlanır (budanır).
Adım Adım Çözüm
Anahtar Kavram
Uygunsuzluk Nedeniyle Budama (Fathoming by Infeasibility)