Examkin

Soru

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

Balas’ın Kapalı Sayımlama (Additive) algoritması ile bir 0−10-1 tamsayılı programlama problemi çözülmektedir. Problemin amaç fonksiyonu aşağıda verilmiştir:

minZ=8x1+5x2+12x3min Z = 8x_1 + 5x_2 + 12x_3

Algoritmanın belirli bir adımında x2x_2 değişkenine 11 değeri atanmış, x1x_1 ve x3x_3 değişkenleri ise henüz atanmamış (serbest) durumdadır.

Buna göre, bu aşamada ilgili düğüm (node) için hesaplanan mevcut amaç fonksiyonu değeri kaçtır?

  1. A
    0
  2. 5Cevap
  3. C
    8
  4. D
    12
  5. E
    25

Cevap

İlgili düğümde hesaplanan amaç fonksiyonu değeri 5'tir.
Balas'ın Kapalı Sayımlama algoritmasında, bir düğümdeki amaç fonksiyonu değeri hesaplanırken, o düğümde 1 değeri alan (atanmış) değişkenlerin katsayıları toplanır. Henüz atanmamış (serbest) değişkenler ise 0 kabul edilir. Soruda sadece x2x_2 değişkenine 1 değeri atandığı için ZZ değeri 5×1=55 \times 1 = 5 olarak bulunur.

Adım Adım Çözüm

1
Modeldeki amaç fonksiyonunu ve değişken durumlarını belirle.
minZ=8x1+5x2+12x3min Z = 8x_1 + 5x_2 + 12x_3 fonksiyonunda x2=1x_2 = 1 olarak sabitlenmiş, x1x_1 ve x3x_3 serbesttir.
Balas algoritmasında mevcut çözüm değeri, o ana kadar değer atanmış değişkenler üzerinden hesaplanır.
2
Serbest değişkenlere varsayılan değerleri ata.
x1=0x_1 = 0 ve x3=0x_3 = 0 olarak alınır.
Balas algoritmasında bir düğümdeki alt sınır (veya mevcut değer), serbest değişkenlerin en küçük değeri olan 0 kabul edilmesiyle bulunur.
3
Değerleri amaç fonksiyonunda yerine koyarak hesaplama yap.
Z=8(0)+5(1)+12(0)=5Z = 8(0) + 5(1) + 12(0) = 5
Düğümün maliyetini belirlemek için sabitlenen değişkenin katkısı hesaplanır.

Anahtar Kavram

Balas algoritmasında bir kısmi çözümün amaç fonksiyonu değeri, atanan değişkenlerin katsayıları ile değerlerinin çarpım toplamıdır.

Daha Fazla Pratik

Eğer amaç fonksiyonunda katsayılar negatif olsaydı, Balas algoritmasını uygulamadan önce yapılacak dönüşümleri inceleyebilirsiniz.
Tahmini Süre:45s
Bu soruyu puanla

Konular

Kapalı Sayımlama (Balas) Algoritması

Bu konudan daha fazla soru