Examkin

Soru

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

Bir kamu kurumunun bütçe kısıtları altındaki yatırım projelerinin seçimi için oluşturulan ve Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir 0−10-1 tamsayılı minimizasyon modelinde, çözüm ağacının belirli bir düğümünde 1. ve 5. projelere onay verilmiş (x1=1x_1 = 1 ve x5=1x_5 = 1), 2., 3. ve 4. projelerin durumu ise henüz karara bağlanmamıştır (x2,x3,x4x_2, x_3, x_4 serbest değişkendir).

Modelin kaynak kullanım kısıtlarından birinin matematiksel ifadesi şöyledir:
4x1−3x2+5x3−2x4+2x5≤−44x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

Buna göre, Balas algoritmasının bu kısıtı değerlendirmesi ve ilgili düğüm için vereceği algoritmik karar aşağıdakilerden hangisidir?

  1. Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.Cevap
  2. B
    Kısıtın sağlanabilmesi için katsayıları negatif olan x2x_2 ve x4x_4 değişkenlerine zorunlu olarak 11 atanarak bu düğüm üzerinden dallanma işlemine devam edilir.
  3. C
    Mevcut atamalar sonucunda eşitsizliğin sol tarafı pozitif bir değer aldığı için, uygunluk testi bırakılarak doğrudan amaç fonksiyonu sınır (bound) testine geçilir.
  4. D
    Serbest değişkenlerden katsayısı en büyük ve pozitif olan x3x_3 değişkenine öncelikle 00 değeri atanarak kısıt ihlali giderilmeye çalışılır ve alt dallara geçilir.
  5. E
    Mevcut atamalar eşitsizliği sağlamadığı için kısıt yönü tersine çevrilir ve düğüm budanmadan çözüm araştırmasına aynı daldan devam edilir.

Cevap

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.
Balas algoritmasında (Kapalı Sayımlama) bir düğümün uygun bir çözüm üretip üretemeyeceği, serbest değişkenlere eşitsizliği en elverişli hale getirecek değerler verilerek test edilir. 4x1−3x2+5x3−2x4+2x5≤−44x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4 kısıtında x1=1x_1 = 1 ve x5=1x_5 = 1 atandığında, eşitsizlik −3x2+5x3−2x4≤−10-3x_2 + 5x_3 - 2x_4 \le -10 halini alır. Eşitsizlik yönü ≤\le olduğu için sol tarafı en küçük yapmak hedeflenir. Negatif katsayılı olanlara 11 (x2=1,x4=1x_2=1, x_4=1), pozitif katsayılı olana 00 (x3=0x_3=0) verdiğimizde sol tarafın alabileceği en küçük değer −5-5 olur. −5-5 değeri −10-10'dan küçük veya eşit olmadığı için, bu kısıt serbest değişkenlerin alacağı hiçbir değerle sağlanamaz. Kesin kısıt ihlali söz konusu olduğundan düğüm uygunsuzluk (infeasibility) gerekçesiyle algoritmada derhal budanır.

Adım Adım Çözüm

1
Mevcut atamaları kısıt denkleminde yerine koyun.
4(1)−3x2+5x3−2x4+2(1)≤−44(1) - 3x_2 + 5x_3 - 2x_4 + 2(1) \le -4 işlemi yapılarak 6−3x2+5x3−2x4≤−46 - 3x_2 + 5x_3 - 2x_4 \le -4 elde edilir.
Serbest değişkenlerin sağlaması gereken kalan eşitsizliği bulmak için sabitlenmiş değerler denkleme yansıtılır.
2
Eşitsizliği sadeleştirin.
Sabit olan 66 karşı tarafa atıldığında −3x2+5x3−2x4≤−10-3x_2 + 5x_3 - 2x_4 \le -10 eşitsizliğine ulaşılır.
Serbest değişkenlerin hedef eşik değerini tam olarak görmek için matematiksel sadeleştirme yapılır.
3
Sol tarafı minimize edecek en elverişli 0−10-1 atamalarını belirleyin.
Sol tarafın en küçük değeri alabilmesi için katsayısı negatif olan değişkenlere 11 (x2=1,x4=1x_2 = 1, x_4 = 1), katsayısı pozitif olan değişkenlere 00 (x3=0x_3 = 0) atanır. Bu durumda sol taraf: −3(1)+5(0)−2(1)=−5-3(1) + 5(0) - 2(1) = -5 olur.
Bir düğümün uygun bir çözüm üretme ihtimalini test etmek için, "küçük eşittir" (≤\le) kısıt yönüne göre sol taraf matematiksel olarak elde edilebilecek en küçük değere çekilir.
4
Elde edilen minimum değeri eşitsizliğin sağ tarafı ile karşılaştırın.
Bulunan en küçük değer olan −5-5, eşitsizliğin sağ tarafındaki −10-10 değerinden küçük veya eşit değildir (−5≰−10-5 \not\le -10).
Serbest değişkenler kullanılarak kısıtı sağlamak adına yapılabilecek en iyi atama bile eşitsizliği sağlayamıyorsa, bu düğümden türetilecek hiçbir çözüm uygun (feasible) olamaz ve düğüm uygunsuzluktan dolayı budanır.

Anahtar Kavram

Balas Algoritmasında Uygunsuzluk (Infeasibility) Budama Kriteri
Bu soruyu puanla

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru