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ıyla ilgili olarak, bir düğümün (kısmi çözümün) 'budanması' veya 'kapatılması' süreci hakkında aşağıda verilen ifadelerden hangisi yanlıştır?

  1. A
    Kısmi çözümde yer alan tüm serbest değişkenlere 0 değeri atandığında kısıtların tamamı sağlanıyorsa, bu dal üzerinden daha iyi bir sonuç elde edilemeyeceği için budama yapılır.
  2. B
    Serbest değişkenlerin kısıtları sağlamaya en yardımcı olacak değerleri (genellikle 1) atanmasına rağmen en az bir kısıt hala ihlal ediliyorsa, bu daldan uygun çözüm gelmeyeceği için kapatılır.
  3. C
    Mevcut kısmi çözümün amaç fonksiyonu değeri, halihazırda elde edilmiş olan en iyi uygun çözümün değerinden (Z∗Z^*) büyük veya ona eşitse dal budanır.
  4. Algoritmanın 'toplanabilirlik' özelliğini koruması için amaç fonksiyonu katsayılarının negatif olması ve problemin her zaman maksimizasyon tipinde olması gerekir.Answer
  5. E
    Budama işlemi; bir düğümden elde edilebilecek potansiyel en iyi çözümün, mevcut en iyi çözümden daha iyi olamayacağının kesinleştiği durumlarda uygulanır.

Answer

Balas algoritması standart olarak minimizasyon problemlerine uygulanır ve amaç fonksiyonu katsayılarının negatif olmaması (sıfırdan büyük veya eşit olması) şartı aranır.
Balas'ın Kapalı Sayımlama (Additive) algoritması, 0-1 tamsayılı programlama problemlerini çözmek için tasarlanmış bir algoritmadır. Bu algoritmanın en temel gereksinimi, problemin minimizasyon formunda olması ve amaç fonksiyonundaki tüm katsayıların (c_j) negatif olmaması (cj≥0c_j \geq 0) şartıdır. Bu şart sağlandığında, bir değişkenin çözüme 1 olarak dahil edilmesi amaç fonksiyonu değerini asla azaltmaz (sadece artırır veya sabit bırakır), bu da 'toplanabilirlik' özelliğini ve etkili budama yapılmasını sağlar. Dolayısıyla katsayıların negatif olması gerektiği yönündeki ifade yanlıştır.

Step-by-Step Solution

1
Algoritmanın standart formunu analiz et.
Balas algoritması min⁡Z=∑cjxj\min Z = \sum c_j x_j formundaki modeller için geliştirilmiştir.
Toplanabilirlik (additive) özelliği, cj≥0c_j \geq 0 olduğunda değişkenlerin çözüme dahil edilmesinin amaç fonksiyonu değerini azaltmayacağını garanti eder.
2
Budama (fathoming) kriterlerini gözden geçir.
Düğüm şu 3 durumda kapatılır: 1. Uygun bir çözümün bulunması (tüm serbest değişkenler 0 iken kısıtların sağlanması), 2. Uygunsuzluğun saptanması (fizibilite testi), 3. Mevcut en iyi çözümden daha iyi sonuç alınamayacağının anlaşılması (sınır testi).
Bu kriterler arama ağacında gereksiz dalların incelenmesini engeller.
3
Yanlış olan seçeneği belirle.
Amaç fonksiyonu katsayılarının negatif olması gerektiği ve problemin maksimizasyon olması gerektiği ifadesi algoritmanın temel varsayımıyla çelişir.
Negatif katsayılar varsa xj=1−yjx_j = 1 - y_j dönüşümü yapılarak katsayılar pozitif hale getirilmelidir.

Key Concept

Balas algoritmasında standart form (minimizasyon ve pozitif katsayılar) budama (fathoming) mantığının temelini oluşturur.
Rate this question

Topics

Kapalı Sayımlama (Balas) Algoritması

More questions from this topic