Examkin

Question

Difficulty: MediumKapalı Sayımlama (Balas) Algoritması

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas’ın Kapalı Sayımlama (Additive) algoritmasında, bir minimizasyon modeli için belirli bir çözüm aşamasında aşağıdaki kısıt ve kısmi çözüm elde edilmiştir:

Kısmi Çözüm: x1=1x_1 = 1, x4=0x_4 = 0 (x2x_2 ve x3x_3 değişkenleri serbesttir).
Kısıt: 2x1+4x2+x3+5x4≥82x_1 + 4x_2 + x_3 + 5x_4 \geq 8

Buna göre, bu düğümün (kısmi çözümün) algoritmadaki durumu ile ilgili aşağıdakilerden hangisi söylenebilir?

  1. Serbest değişkenlere atanabilecek en iyi değerlerle dahi kısıt sağlanamayacağı için bu düğüm uygunsuzluk nedeniyle budanır.Answer
  2. B
    Kısmi çözümdeki mevcut değerler kısıtı sağladığı için bir uygun çözüm bulunmuştur ve dal kapatılır.
  3. C
    Kısıt henüz sağlanmamıştır ancak serbest değişkenlerden birine 1 değeri verilerek kısıt sağlanabileceği için dallandırmaya devam edilir.
  4. D
    Amaç fonksiyonu katsayıları pozitif olduğu sürece bu kısıtın sağlanıp sağlanmadığına bakılmaksızın dallandırma yapılır.
  5. E
    Serbest değişken sayısı kısıt katsayılarından az olduğu için bu dalda çözüm aranamaz ve algoritma durur.

Answer

Serbest değişkenlerin alabileceği en büyük değerler (x2=1,x3=1x_2=1, x_3=1) dikkate alındığında bile kısıtın sağlanması mümkün olmadığından, bu düğüm uygunsuzluk (infeasibility) nedeniyle budanır.
Kısmi çözümdeki x1=1x_1=1 ve x4=0x_4=0 değerleri kısıtta yerine yazıldığında, kısıtın sol tarafı 22 değerini alır. Kısıtın sağlanması için serbest olan x2x_2 ve x3x_3 değişkenlerinin toplamda en az 66 birimlik bir katkı yapması gerekir. Ancak bu değişkenler 00 veya 11 değerini alabildiğinden, yapabilecekleri maksimum katkı 4(1)+1(1)=54(1) + 1(1) = 5 birimdir. 5<65 < 6 olduğu için bu dal üzerinden hiçbir şekilde uygun bir çözüme ulaşılamaz ve düğüm budanır.

Step-by-Step Solution

1
Kısmi çözümdeki sabit değerleri kısıt denkleminde yerine koyun.
2(1)+4x2+x3+5(0)≥8⇒2+4x2+x3≥82(1) + 4x_2 + x_3 + 5(0) \geq 8 \Rightarrow 2 + 4x_2 + x_3 \geq 8
Mevcut çözümün kısıt üzerindeki etkisini belirlemek için.
2
Kısıtın sağlanması için serbest değişkenlerden beklenen minimum katkıyı hesaplayın.
4x2+x3≥8−2⇒4x2+x3≥64x_2 + x_3 \geq 8 - 2 \Rightarrow 4x_2 + x_3 \geq 6
Serbest değişkenlerin karşılaması gereken farkı bulmak için.
3
Serbest değişkenlerin (x2,x3∈{0,1}x_2, x_3 \in \{0, 1\}) kısıtın sol tarafına yapabileceği maksimum katkıyı belirleyin.
Maksimum katkı: 4(1)+1(1)=54(1) + 1(1) = 5
En iyimser durumda kısıtın sağlanıp sağlanamayacağını test etmek için.
4
Maksimum katkı ile gereken farkı karşılaştırın.
5<65 < 6 olduğu için kısıt asla sağlanamaz.
Balas algoritması budama kriterini (uygunsuzluk) uygulamak için.

Key Concept

Balas (Kapalı Sayımlama) Algoritmasında Uygunsuzluk Testi

Hints

1
Önce bilinen x1x_1 ve x4x_4 değerlerini kısıt eşitsizliğinde yerine yazarak sadeleştirme yapın.
2
Sadeleşmiş kısıtın (4x2+x3≥64x_2 + x_3 \geq 6) sağlanması için x2x_2 ve x3x_3 değişkenlerine 0 veya 1 değerlerinden hangilerini vermeniz gerektiğini düşünün.
3
Eğer serbest değişkenlere en büyük değerlerini (1) verdiğinizde bile kısıt sağlanmıyorsa, bu dalda uygun çözüm aramanın bir anlamı kalmaz.

Practice More

Balas algoritmasında 'uygunluk' (feasibility) nedeniyle budama yapılabilmesi için kısmi çözümdeki değişkenlerin kısıtları sağlaması ve geri kalan serbest değişkenlerin amaç fonksiyonuna katkısının 0 olması (minimizasyon için) gerektiğini hatırlayınız.
Estimated Time:1m 30s
Rate this question

Topics

Kapalı Sayımlama (Balas) Algoritması

More questions from this topic