Examkin

Question

Difficulty: EasyKapalı 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. 5Answer
  3. C
    8
  4. D
    12
  5. E
    25

Answer

İ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.

Step-by-Step Solution

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.

Key Concept

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.

Practice More

Eğer amaç fonksiyonunda katsayılar negatif olsaydı, Balas algoritmasını uygulamadan önce yapılacak dönüşümleri inceleyebilirsiniz.
Estimated Time:45s
Rate this question

Topics

Kapalı Sayımlama (Balas) Algoritması

More questions from this topic