Examkin

Soru

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

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritması, standart bir minimizasyon modelini esas alır. Bir problemin çözümü sırasında aşağıdaki kısıtın sağlanması gerekmektedir:

2x1+3x2+6x3≥72x_1 + 3x_2 + 6x_3 \geq 7

Algoritmanın bir adımında x3=0x_3 = 0 olarak sabitlendiği bir kısmi çözüm (düğüm) incelenmektedir. Buna göre, bu düğümün algoritma tarafından 'kapalı' (fathomed) olarak işaretlenmesinin temel gerekçesi aşağıdakilerden hangisidir?

  1. Kalan serbest değişkenlere en uygun değerler (1) verilse dahi kısıtın sağlanmasının mümkün olmaması (Uygunsuzluk).Cevap
  2. B
    Kısmi çözümdeki amaç fonksiyonu değerinin, mevcut en iyi tamsayılı çözümden (üst sınır) daha küçük olması.
  3. C
    Kısıtın mevcut değişken değerleriyle (x3=0,x1=0,x2=0x_3=0, x_1=0, x_2=0) halihazırda sağlanmış olması.
  4. D
    Kısmi çözümde tamsayılı olmayan bir sonucun elde edilmesi ve dallandırmanın sona ermesi.
  5. E
    Kısıttaki tüm katsayıların pozitif olması nedeniyle amaç fonksiyonunun sınırsız olması.

Cevap

Düğümün kapatılma gerekçesi, kalan serbest değişkenlerin kısıtı en çok destekleyen değerleri alması durumunda bile kısıtın sağlanamamasıdır.
Balas algoritmasında bir dalın kapatılması için üç temel kriter vardır: Uygun bir çözümün bulunması, dalın mevcut en iyi çözümden daha kötü sonuç vereceğinin kanıtlanması veya dalın kısıtları sağlamasının matematiksel olarak imkansız olması. Soruda x3=0x_3=0 olarak sabitlendiğinde, kısıtı en çok destekleyen x1=1x_1=1 ve x2=1x_2=1 atamaları bile sol tarafı ancak 5 yapabilmektedir. 5 değeri kısıtın gerektirdiği 7 değerinden küçük olduğu için bu dalda hiçbir uygun çözüm bulunamaz ve dal kapatılır.

Adım Adım Çözüm

1
Kısmi çözümdeki değişken değerini kısıt denklemine yerleştirin.
2x1+3x2+6(0)≥7⇒2x1+3x2≥72x_1 + 3x_2 + 6(0) \geq 7 \Rightarrow 2x_1 + 3x_2 \geq 7
Düğümün uygunluğunu test etmek için sabitlenen değerlerin etkisini görmek gerekir.
2
Kalan serbest değişkenler (x1,x2x_1, x_2) için sol tarafın alabileceği maksimum değeri hesaplayın.
x1=1x_1=1 ve x2=1x_2=1 için 2(1)+3(1)=52(1) + 3(1) = 5
0-1 programlamada bir kısıtın sağlanma şansı, katsayısı pozitif olan değişkenlere 1 verilerek kontrol edilir.
3
Elde edilen maksimum değeri kısıtın sağ tarafındaki değerle (RHS) kıyaslayın.
5<75 < 7
Sol tarafın alabileceği en büyük değer bile kısıtı sağlamaya yetmemektedir.
4
Algoritma kuralına göre kararı belirleyin.
Düğüm 'Uygunsuzluk' (Infeasibility) nedeniyle kapatılır (fathomed).
Bu daldan gidilerek elde edilecek hiçbir çözüm kısıtı sağlayamayacağı için dallandırma durdurulur.

Anahtar Kavram

Balas (Kapalı Sayımlama) algoritmasında uygunsuzluk testi (Fathoming by infeasibility)

Daha Fazla Pratik

Benzer bir problemi kısıt yönünü değiştirerek (küçük eşittir) çözmeyi deneyin ve bu sefer serbest değişkenlere 0 verilerek kısıtın en iyi şekilde nasıl desteklendiğini analiz edin.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru