Examkin

Soru

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

Aşağıdaki 0-1 tamsayılı programlama problemi Balas (Kapalı Sayımlama) algoritması ile çözülmektedir:

Minimize Z=5x1+3x2+8x3\text{Minimize } Z = 5x_1 + 3x_2 + 8x_3
Kısıtlar:
x1+x2+x3≥2x_1 + x_2 + x_3 \geq 2
2x1−x2+4x3≥52x_1 - x_2 + 4x_3 \geq 5
x1,x2,x3∈{0,1}x_1, x_2, x_3 \in \{0, 1\}

Algoritmanın belirli bir aşamasında mevcut en iyi çözüm değerinin (incumbent) Z∗=10Z^* = 10 olduğu ve x1=0x_1 = 0 kısmi atamasının yapıldığı düğüme (alt probleme) gelindiği varsayıldığında, bu düğüm için aşağıdakilerden hangisi söylenebilir?

  1. Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.Cevap
  2. B
    Düğümden elde edilebilecek potansiyel amaç fonksiyonu değeri Z∗=10Z^* = 10 değerinden küçük olduğu için dallanmaya devam edilir.
  3. C
    Kısmi çözüm kısıtları zaten sağladığı için bu düğüm bir 'tam çözüm' olarak işaretlenir.
  4. D
    Düğüm, amaç fonksiyonu alt sınırı mevcut en iyi çözüm olan 10 değerini aştığı için budanır.
  5. E
    Düğüm, doğrusal programlama gevşetmesi tamsayılı sonuç verdiği için kapatılır.

Cevap

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.
Verilen x1=0x_1 = 0 ataması altında ikinci kısıt −x2+4x3≥5-x_2 + 4x_3 \geq 5 halini almaktadır. Bu kısıtta x2x_2 ve x3x_3 değişkenleri 0 veya 1 değerlerini alabildiğinden, sol tarafın ulaşabileceği en büyük değer (en iyimser durum) x2=0x_2=0 ve x3=1x_3=1 iken 4'tür. 4≥54 \geq 5 ifadesi matematiksel olarak imkansız olduğu için bu düğümden hiçbir uygun çözüm elde edilemez ve Balas algoritması gereği düğüm kapatılır.

Adım Adım Çözüm

1
Kısmi atama değerini kısıtlarda yerine koyun.
x1=0x_1 = 0 için ikinci kısıt: 2(0)−x2+4x3≥5⇒−x2+4x3≥52(0) - x_2 + 4x_3 \geq 5 \Rightarrow -x_2 + 4x_3 \geq 5.
Düğümün olanaklılığını test etmek için sabitlenen değişkenlerin etkisini görmek gerekir.
2
Kısıtın sol tarafının alabileceği maksimum değeri hesaplayın.
−x2+4x3-x_2 + 4x_3 ifadesi için x2=0x_2=0 ve x3=1x_3=1 seçildiğinde maksimum değer −0+4(1)=4-0 + 4(1) = 4 olur.
Değişkenler 0 veya 1 değerini alabildiği için kısıtın en iyimser durumda bile sağlanıp sağlanamayacağı kontrol edilir.
3
Hesaplanan maksimum değeri kısıt sağ tarafı ile karşılaştırın.
4<54 < 5 olduğu için kısıt hiçbir x2,x3∈{0,1}x_2, x_3 \in \{0, 1\} kombinasyonu için sağlanamaz.
Maksimum değer bile sınırı aşamıyorsa bu dal üzerinde uygun bir çözüm bulunması imkansızdır.
4
Algoritma kararını belirleyin.
Düğüm 'uygunsuzluk' (infeasibility) nedeniyle budanır (kapatılır).
Balas algoritmasında kısıt sağlanamıyorsa o dalın taranmasına devam edilmez.

Anahtar Kavram

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

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru