Kapalı Sayımlama (Balas) Algoritması

11 questions

Aşağıdaki 0-1 tamsayılı programlama problemi Balas (Kapalı Sayımlama) algoritması ile çözülmektedir:

\text{Minimize } Z = 5x_1 + 3x_2 + 8x_3

Kısıtlar:

x_1 + x_2 + x_3 \geq 2

2x_1 - x_2 + 4x_3 \geq 5

x_1, x_2, x_3 \in \{0, 1\}

Algoritmanın belirli bir aşamasında mevcut en iyi çözüm değerinin (incumbent) $Z^* = 10$ olduğu ve $x_1 = 0$ kısmi atamasının yapıldığı düğüme (alt probleme) gelindiği varsayıldığında, bu düğüm için aşağıdakilerden hangisi söylenebilir?

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Düğümden elde edilebilecek potansiyel amaç fonksiyonu değeri

Z^* = 10

değerinden küçük olduğu için dallanmaya devam edilir.

Kısmi çözüm kısıtları zaten sağladığı için bu düğüm bir 'tam çözüm' olarak işaretlenir.

Düğüm, amaç fonksiyonu alt sınırı mevcut en iyi çözüm olan 10 değerini aştığı için budanır.

Düğüm, doğrusal programlama gevşetmesi tamsayılı sonuç verdiği için kapatılır.

Show answer & explanation

Answer: Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Answer

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Verilen

x_1 = 0

ataması altında ikinci kısıt

-x_2 + 4x_3 \geq 5

halini almaktadır. Bu kısıtta

x_2

x_3

değişkenleri 0 veya 1 değerlerini alabildiğinden, sol tarafın ulaşabileceği en büyük değer (en iyimser durum)

x_2=0

x_3=1

iken 4'tür.

4 \geq 5

ifadesi matematiksel olarak imkansız olduğu için bu düğümden hiçbir uygun çözüm elde edilemez ve Balas algoritması gereği düğüm kapatılır.

Step-by-Step Solution

Kısmi atama değerini kısıtlarda yerine koyun.

x_1 = 0

için ikinci kısıt:

2(0) - x_2 + 4x_3 \geq 5 \Rightarrow -x_2 + 4x_3 \geq 5

Düğümün olanaklılığını test etmek için sabitlenen değişkenlerin etkisini görmek gerekir.

Kısıtın sol tarafının alabileceği maksimum değeri hesaplayın.

-x_2 + 4x_3

ifadesi için

x_2=0

x_3=1

seçildiğinde maksimum değer

-0 + 4(1) = 4

olur.

Değişkenler 0 veya 1 değerini alabildiği için kısıtın en iyimser durumda bile sağlanıp sağlanamayacağı kontrol edilir.

Hesaplanan maksimum değeri kısıt sağ tarafı ile karşılaştırın.

4 < 5

olduğu için kısıt hiçbir

x_2, x_3 \in \{0, 1\}

kombinasyonu için sağlanamaz.

Maksimum değer bile sınırı aşamıyorsa bu dal üzerinde uygun bir çözüm bulunması imkansızdır.

Algoritma kararını belirleyin.

Düğüm 'uygunsuzluk' (infeasibility) nedeniyle budanır (kapatılır).

Balas algoritmasında kısıt sağlanamıyorsa o dalın taranmasına devam edilmez.

Key Concept

Balas Algoritmasında Budama (Fathoming) Kriterleri

Question 2Question →

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:

2x_1 + 3x_2 + 6x_3 \geq 7

Algoritmanın bir adımında $x_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?

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

Kısmi çözümdeki amaç fonksiyonu değerinin, mevcut en iyi tamsayılı çözümden (üst sınır) daha küçük olması.

Kısıtın mevcut değişken değerleriyle (

x_3=0, x_1=0, x_2=0

) halihazırda sağlanmış olması.

Kısmi çözümde tamsayılı olmayan bir sonucun elde edilmesi ve dallandırmanın sona ermesi.

Kısıttaki tüm katsayıların pozitif olması nedeniyle amaç fonksiyonunun sınırsız olması.

Show answer & explanation

Answer: 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).

Answer

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

x_3=0

olarak sabitlendiğinde, kısıtı en çok destekleyen

x_1=1

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

Step-by-Step Solution

Kısmi çözümdeki değişken değerini kısıt denklemine yerleştirin.

2x_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.

Kalan serbest değişkenler (

x_1, x_2

) için sol tarafın alabileceği maksimum değeri hesaplayın.

x_1=1

x_2=1

için

2(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.

Elde edilen maksimum değeri kısıtın sağ tarafındaki değerle (RHS) kıyaslayın.

5 < 7

Sol tarafın alabileceği en büyük değer bile kısıtı sağlamaya yetmemektedir.

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.

Key Concept

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

Practice More

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.

Estimated Time:1m 30s

Question 3Question →

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?

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.

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.

Mevcut kısmi çözümün amaç fonksiyonu değeri, halihazırda elde edilmiş olan en iyi uygun çözümün değerinden (

Z^*

) büyük veya ona eşitse dal budanır.

Algoritmanın 'toplanabilirlik' özelliğini koruması için amaç fonksiyonu katsayılarının negatif olması ve problemin her zaman maksimizasyon tipinde olması gerekir.

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.

Show answer & explanation

Answer: 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

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ı (

c_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

Algoritmanın standart formunu analiz et.

Balas algoritması

\min Z = \sum c_j x_j

formundaki modeller için geliştirilmiştir.

Toplanabilirlik (additive) özelliği,

c_j \geq 0

olduğunda değişkenlerin çözüme dahil edilmesinin amaç fonksiyonu değerini azaltmayacağını garanti eder.

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.

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

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

Question 4Question →

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: $x_1 = 1$ , $x_4 = 0$ ( $x_2$ ve $x_3$ değişkenleri serbesttir).
Kısıt: $2x_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?

Serbest değişkenlere atanabilecek en iyi değerlerle dahi kısıt sağlanamayacağı için bu düğüm uygunsuzluk nedeniyle budanır.

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.

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.

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.

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.

Show answer & explanation

Answer: 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

Serbest değişkenlerin alabileceği en büyük değerler (

x_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

x_1=1

x_4=0

değerleri kısıtta yerine yazıldığında, kısıtın sol tarafı

2

değerini alır. Kısıtın sağlanması için serbest olan

x_2

x_3

değişkenlerinin toplamda en az

6

birimlik bir katkı yapması gerekir. Ancak bu değişkenler

0

veya

1

değerini alabildiğinden, yapabilecekleri maksimum katkı

4(1) + 1(1) = 5

birimdir.

5 < 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

Kısmi çözümdeki sabit değerleri kısıt denkleminde yerine koyun.

2(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.

Kısıtın sağlanması için serbest değişkenlerden beklenen minimum katkıyı hesaplayın.

4x_2 + x_3 \geq 8 - 2 \Rightarrow 4x_2 + x_3 \geq 6

Serbest değişkenlerin karşılaması gereken farkı bulmak için.

Serbest değişkenlerin (

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) = 5

En iyimser durumda kısıtın sağlanıp sağlanamayacağını test etmek için.

Maksimum katkı ile gereken farkı karşılaştırın.

5 < 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

Önce bilinen

x_1

x_4

değerlerini kısıt eşitsizliğinde yerine yazarak sadeleştirme yapın.

Sadeleşmiş kısıtın (

4x_2 + x_3 \geq 6

) sağlanması için

x_2

x_3

değişkenlerine 0 veya 1 değerlerinden hangilerini vermeniz gerektiğini düşünün.

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

Question 5Question →

$0-1$ tamsayılı programlama problemlerinin çözümünde kullanılan Balas’ın Kapalı Sayımlama (Additive) algoritmasında, standart bir minimizasyon problemi ele alınmaktadır. Algoritmanın belirli bir adımında, bir kısmi çözümün (düğümün) dallandırılması incelenirken; mevcut serbest değişkenlerin tamamı kısıtları sağlamaya en fazla katkıda bulunacak şekilde ( $0$ veya $1$ ) değerlendirilse dahi kısıtlardan en az birinin sağlanamadığı tespit edilmiştir. Bu durum ortaya çıktığında algoritmanın işleyişine göre aşağıdakilerden hangisi uygulanmalıdır?

İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Serbest değişkenler arasından yeni bir dallandırma değişkeni seçilerek alt düğümlere geçilir.

Mevcut kısmi çözüm, o ana kadarki en iyi çözüm (üst sınır) olarak kaydedilir.

Kısıtın yönü tersine çevrilerek algoritma bir sonraki iterasyona aktarılır.

Algoritma tamamen sonlandırılır ve problemin uygun bir çözümü olmadığına karar verilir.

Show answer & explanation

Answer: İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Answer

İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Doğru cevap, Balas algoritmasındaki 'uygunsuzluk nedeniyle kapatma' kriterini ifade etmektedir. Algoritmanın minimizasyon standart formunda, kısıtlar

\geq

şeklindedir. Eğer eldeki serbest değişkenlerin kısıtı sağlamaya yönelik en büyük katkısı bile (pozitif katsayılar için değişkeni

1

, negatifler için

0

yaparak) mevcut yetersizliği gideremiyorsa, o daldan devam etmenin bir anlamı kalmaz ve dal budanır.

Step-by-Step Solution

Kısmi çözümdeki serbest değişkenlerin kısıtlar üzerindeki etkisi analiz edilir.

Serbest değişkenlerin kısıtı sağlamaya en çok yardım eden değerleri belirlenir.

Düğümün kapatılıp kapatılmayacağına karar vermek için 'en iyi durum' testi yapılmalıdır.

Kısıtın sağlanabilirliği (feasibility check) kontrol edilir.

En iyi durumda bile kısıt ihlalinin devam ettiği görülür.

Eğer en iyi olasılıkta bile kısıt sağlanamıyorsa, o daldan uygun çözüm çıkma şansı sıfırdır.

Kapalı sayımlama mantığı gereği 'budama' işlemi uygulanır.

Düğüm 'uygunsuzluk' nedeniyle kapatılır.

Algoritmanın gereksiz dalları eleyerek hızlanması sağlanır.

Key Concept

Balas algoritmasında uygunsuzluk (infeasibility) nedeniyle budama kriteri.

Practice More

Balas algoritmasında 'üst sınır (Z*) yardımıyla budama' kriterini de incelemek, konunun tam anlaşılmasını sağlar.

Estimated Time:1m 30s

Question 6Question →

Balas’ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon probleminde, o ana kadar elde edilen en iyi uygun çözümün amaç fonksiyonu değeri $Z^* = 15$ olarak kaydedilmiştir. Algoritmanın bir aşamasında incelenen bir düğümdeki (kısmi çözüm) atanmış değişkenlerin maliyet katsayıları toplamı $12$ ’dir. Bu düğümde serbest durumda bulunan üç değişkenin maliyet katsayıları ise sırasıyla $4, 5$ ve $7$ ’dir. Yapılan teknik incelemede, kısıtların tamamının sağlanabilmesi için bu serbest değişkenlerden en az birinin $1$ değerini almasının zorunlu olduğu saptanmıştır.

Buna göre, incelenen bu düğümün durumu ile ilgili aşağıdakilerden hangisi doğrudur?

Atanmış değişkenlerin maliyeti (

12

), mevcut en iyi çözümden (

15

) küçük olduğu için dallandırma işlemine mutlaka devam edilmelidir.

Kısmi çözüm henüz uygun bir çözüm üretmediği için bu düğüm sadece "uygunsuzluk" (infeasibility) kriteri gerçekleşirse budanabilir.

Kısıtları sağlamak için gereken en küçük ek maliyetle dahi toplam maliyet

16

(

12 + 4

) olacağı ve bu değer

Z^* = 15

’ten büyük olduğu için düğüm budanmalıdır.

Elde edilen

12

değeri

15

’ten küçük olduğundan, serbest değişkenlere uygun değerler atanarak

12

değerinden daha küçük bir amaç fonksiyonu sonucuna ulaşılabilir.

Algoritma kuralları gereği, serbest değişkenlerin tamamı

1

yapılarak kısıtların sağlanıp sağlanmadığı kontrol edilmeden budama kararı verilemez.

Show answer & explanation

Answer: Kısıtları sağlamak için gereken en küçük ek maliyetle dahi toplam maliyet $16$ ( $12 + 4$ ) olacağı ve bu değer $Z^* = 15$ ’ten büyük olduğu için düğüm budanmalıdır.

Answer

Kısıtları sağlamak için gereken en düşük maliyet eklendiğinde (

12 + 4 = 16

) elde edilen alt sınır mevcut en iyi çözümden (

15

) büyük olduğu için düğüm budanmalıdır.

Balas'ın Kapalı Sayımlama algoritmasında, bir düğümden (kısmi çözüm) elde edilebilecek en iyi sonuç bile mevcut en iyi çözümden (

Z^*

) daha kötüyse, o dalın daha fazla incelenmesine gerek kalmaz ve budama işlemi yapılır. Soruda kısıtların sağlanması için en az bir değişkenin seçilmesi gerektiği belirtilmiştir. En ucuz seçenek olan

4

birimlik maliyet eklendiğinde bile toplam maliyet

16

olmaktadır.

16 > 15

olduğu için bu dal kesinlikle elenmelidir.

Step-by-Step Solution

Mevcut durumun analizi

Z^* = 15

, mevcut maliyet

= 12

, serbest değişken katsayıları

= \{4, 5, 7\}

Algoritmanın budama kriterlerini değerlendirmek için mevcut sınırı ve kısmi çözümün yükünü belirlemek gerekir.

Kısıt gereksiniminin belirlenmesi

En az bir serbest değişken

1

olmalıdır.

Kısmi çözümün kısıtları henüz sağlamadığı ve kısıtları sağlamak için ek maliyetin zorunlu olduğu anlaşılmaktadır.

Alt sınırın (Z-sınırı) hesaplanması

Minimum maliyet

= 12 + \min(4, 5, 7) = 12 + 4 = 16

Bu daldan elde edilebilecek en iyimser (en düşük maliyetli) çözümün değerini bulmak için en küçük katsayılı serbest değişken seçilir.

Budama kriterinin uygulanması

16 > 15

olduğu için düğüm budanır (fathomed).

Hesaplanan alt sınır mevcut en iyi çözümden (üst sınır) daha kötü olduğu için bu dalda daha iyi bir çözüm bulma imkanı kalmamıştır.

Key Concept

Balas algoritmasında amaç fonksiyonu (Z-sınırı) kriterine göre budama işlemi.

Question 7Question →

Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon probleminde, tüm amaç fonksiyonu katsayılarının negatif olmadığı ( $c_j \geq 0$ ) bilinmektedir. Algoritmanın herhangi bir adımında, incelenen bir düğümdeki kısmi çözümün amaç fonksiyonu değeri ( $Z_{kısmi}$ ), o ana kadar elde edilmiş en iyi uygun çözümün değerine ( $Z^*$ ) eşit veya bu değerden büyükse ( $Z_{kısmi} \geq Z^*$ ), bu düğümün durumu hakkında aşağıdakilerden hangisi söylenebilir?

Düğüm kapalı sayımlanır (budanır) çünkü bu daldan daha iyi bir çözüm gelmesi mümkün değildir.

Düğümden dallandırmaya devam edilir çünkü henüz atanmamış serbest değişkenler amaç değerini küçültebilir.

Düğüm uygun bir çözüm olarak kabul edilir ve tüm algoritma o anda sonlandırılır.

Kısmi çözümün kısıtları sağlayıp sağlamadığına bakılmaksızın yeni bir

Z^*

değeri olarak atanır.

Düğümdeki serbest değişkenlerin tamamına 0 değeri verilerek kısıtların uygunluğu kontrol edilir.

Show answer & explanation

Answer: Düğüm kapalı sayımlanır (budanır) çünkü bu daldan daha iyi bir çözüm gelmesi mümkün değildir.

Answer

Mevcut kısmi çözümün amaç değeri halihazırdaki en iyi çözüm değerine eşit veya ondan büyükse, katsayıların pozitif olması nedeniyle bu daldan daha iyi bir sonuç elde edilemez ve düğüm kapalı sayımlanır (budanır).

Balas algoritmasında amaç fonksiyonu katsayıları negatif olmayacak şekilde düzenlenir. Bir minimizasyon probleminde, bir dalın (düğümün) o ana kadarki maliyeti halihazırda bulduğumuz en iyi çözümün maliyetini geçmişse, o daldan devam ederek daha küçük bir maliyet elde etmemiz matematiksel olarak imkansızdır. Bu duruma algoritma literatüründe 'kapalı sayımlama' veya 'budama' denir.

Step-by-Step Solution

Balas algoritmasının standart formunu hatırla.

Problem minimizasyon yapısındadır ve tüm

c_j \geq 0

katsayılarına sahiptir.

Algoritmanın temel işleyişi katsayıların negatif olmaması üzerine kuruludur.

Amaç fonksiyonu değerinin değişimini analiz et.

Yeni değişkenlerin çözüme dahil edilmesi (1 atanması), amaç değerini (

Z

) sadece artırabilir veya sabit bırakabilir.

Katsayılar

c_j \geq 0

olduğu için

Z

değeri azalmaz.

Sınır (Bound) kontrolü yap.

Eğer

Z_{kısmi} \geq Z^*

ise, bu daldan gelecek hiçbir çözüm mevcut en iyi çözümü (

Z^*

) iyileştiremez.

Daha iyi bir çözüm bulunma ihtimali kalmadığı için bu dalın incelenmesi durdurulur (kapalı sayımlama).

Key Concept

Balas Algoritmasında Budama (Fathoming) Kriteri

Question 8Question →

Balas'ın Kapalı Sayımlama (Additive) algoritması ile bir $0-1$ tamsayılı programlama problemi çözülürken, algoritmanın doğrudan uygulanabilmesi için problemin standart minimizasyon formundaki amaç fonksiyonu katsayıları ( $c_j$ ) ile ilgili temel gereklilik aşağıdakilerden hangisidir?

Tüm

c_j

katsayıları negatif olmayan (

c_j \geq 0

) değerler olmalıdır.

Tüm

c_j

katsayıları negatif (

c_j < 0

) değerler olmalıdır.

c_j

katsayıları sadece

0

veya

1

değerlerini almalıdır.

Katsayıların işaretleri kısıtların yönüne (

\leq

veya

\geq

) bağlı olarak değişmelidir.

En az bir

c_j

katsayısı negatif, diğerleri pozitif olmalıdır.

Show answer & explanation

Answer: Tüm $c_j$ katsayıları negatif olmayan ( $c_j \geq 0$ ) değerler olmalıdır.

Answer

Balas algoritmasının standart minimizasyon formunda tüm amaç fonksiyonu katsayıları negatif olmayan (

c_j \geq 0

) değerler olmalıdır.

Balas'ın Kapalı Sayımlama algoritmasında, minimizasyon hedeflenirken amaç fonksiyonu katsayılarının negatif olmaması (

c_j \geq 0

) istenir. Bu durum, 'toplamsal' (additive) yapının korunmasını ve kısmi çözümlerde alt sınırların kolayca hesaplanarak uygun olmayan dalların budanmasını sağlar. Eğer katsayılarda negatif değer varsa, değişken dönüşümü (

x_j = 1 - y_j

) yapılarak bu şart sağlanmalıdır.

Step-by-Step Solution

Algoritmanın temel yapısını analiz etme

Balas'ın Kapalı Sayımlama algoritması,

0-1

tamsayılı programlama problemlerini çözmek için kullanılan toplamsal (additive) bir algoritmadır.

Algoritmanın hangi model yapısı üzerinde çalıştığını anlamak için gereklidir.

Standart form gerekliliklerini belirleme

Algoritmanın doğrudan uygulanabilmesi için problemin minimizasyon formunda olması ve tüm amaç fonksiyonu katsayılarının (

c_j

) negatif olmaması şartı aranır.

Bu şart, değişkenlerin değerinin

0

'dan

1

'e çıkarılması durumunda amaç fonksiyonu değerinin (Z) asla azalmayacağını garanti eder.

Budama (Kapalı Sayımlama) mantığı ile ilişkilendirme

Eğer bir kısmi çözümde elde edilen Z değeri mevcut en iyi çözümden (

Z^*

) büyükse,

c_j \geq 0

olduğu sürece daha fazla değişkenin

1

yapılması Z'yi daha da artıracaktır; bu da o dalın budanabilmesini sağlar.

Katsayıların işareti, algoritmanın arama uzayını verimli bir şekilde daraltmasını sağlayan temel mekanizmadır.

Key Concept

Balas Algoritması Standart Formu

Practice More

Balas algoritmasında kısıtların uygunluğunu kontrol etmek için kullanılan 'kısıt açığı' (slack) kavramını inceleyebilirsiniz.

Estimated Time:45s

Question 9Question →

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritmasında, bir minimizasyon modeli ele alınmaktadır. Algoritma akışında bir düğümün (alt problemin) 'uygunsuzluk' (infeasibility) nedeniyle kapalı sayımlanmasına (budanmasına) karar verilebilmesi için aşağıdaki durumlardan hangisinin gerçekleşmesi gerekir?

Kısıtın sağlanması için gereken miktarın, serbest değişkenlerin o kısıta sağlayabileceği maksimum pozitif katkıdan daha büyük olması

Mevcut düğümde hesaplanan amaç fonksiyonu değerinin o ana kadar bulunan en iyi çözüm değerinden (Z*) daha yüksek olması

Henüz değer atanmamış tüm değişkenlerin 1 değerini alarak kısıtların tamamını sağlaması

Problemin amaç fonksiyonundaki tüm katsayıların negatif değerlerden oluşması

Değişkenlerden birinin çözüm sürecinde 0 veya 1 dışında bir tamsayı değeri alması

Show answer & explanation

Answer: Kısıtın sağlanması için gereken miktarın, serbest değişkenlerin o kısıta sağlayabileceği maksimum pozitif katkıdan daha büyük olması

Answer

Balas algoritmasında bir düğüm, kısıtın sağlanması için gereken miktarın (zayiat/açık), serbest değişkenlerin kısıta yapabileceği maksimum pozitif katkıdan daha büyük olması durumunda uygunsuzluk nedeniyle budanır.

Doğru yanıt olan seçenek, Balas algoritmasındaki uygunsuzluk testini tanımlar. Eğer bir kısıttaki negatif sapma (açık), o kısıtta yer alan ve henüz değer atanmamış değişkenlerin kısıta katabileceği en büyük değerden daha büyükse, bu düğümün alt dallarında uygun bir çözüm bulunması matematiksel olarak imkansızdır. Bu nedenle düğüm 'uygunsuzluk' nedeniyle kapalı sayımlanır (budanır).

Step-by-Step Solution

Düğümdeki kısıt açığını (slack) belirle

s_i < 0 ise kısıt henüz sağlanmamıştır.

Budama kriterini kontrol etmek için kısıtın ne kadar uzağında olduğumuzu bilmemiz gerekir.

Serbest değişkenlerin kısıta yapabileceği maksimum katkıyı hesapla

Pozitif katsayılı serbest değişkenlerin katsayıları toplanır.

En iyi ihtimalle (tüm serbest değişkenler 1 olduğunda) kısıtın ne kadar iyileşebileceğini bulmak için gereklidir.

İhtiyaç ile maksimum katkıyı karşılaştır

Açık miktarı > Maksimum katkı ise durum uygunsuzdur.

En iyi senaryoda bile kısıt sağlanamıyorsa, bu daldan devam etmenin bir anlamı yoktur.

Key Concept

Uygunsuzluk Nedeniyle Budama (Fathoming by Infeasibility)

Question 10Question →

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

min Z = 8x_1 + 5x_2 + 12x_3

Algoritmanın belirli bir adımında $x_2$ değişkenine $1$ değeri atanmış, $x_1$ ve $x_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?

Show answer & explanation

Answer: 5

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

x_2

değişkenine 1 değeri atandığı için

Z

değeri

5 \times 1 = 5

olarak bulunur.

Step-by-Step Solution

Modeldeki amaç fonksiyonunu ve değişken durumlarını belirle.

min Z = 8x_1 + 5x_2 + 12x_3

fonksiyonunda

x_2 = 1

olarak sabitlenmiş,

x_1

x_3

serbesttir.

Balas algoritmasında mevcut çözüm değeri, o ana kadar değer atanmış değişkenler üzerinden hesaplanır.

Serbest değişkenlere varsayılan değerleri ata.

x_1 = 0

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

Değerleri amaç fonksiyonunda yerine koyarak hesaplama yap.

Z = 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

Question 11Question →

Bir kamu kurumunun bütçe kısıtları altındaki yatırım projelerinin seçimi için oluşturulan ve Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon modelinde, çözüm ağacının belirli bir düğümünde 1. ve 5. projelere onay verilmiş ( $x_1 = 1$ ve $x_5 = 1$ ), 2., 3. ve 4. projelerin durumu ise henüz karara bağlanmamıştır ( $x_2, x_3, x_4$ serbest değişkendir).

Modelin kaynak kullanım kısıtlarından birinin matematiksel ifadesi şöyledir:

4x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

Buna göre, Balas algoritmasının bu kısıtı değerlendirmesi ve ilgili düğüm için vereceği algoritmik karar aşağıdakilerden hangisidir?

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Kısıtın sağlanabilmesi için katsayıları negatif olan

x_2

x_4

değişkenlerine zorunlu olarak

1

atanarak bu düğüm üzerinden dallanma işlemine devam edilir.

Mevcut atamalar sonucunda eşitsizliğin sol tarafı pozitif bir değer aldığı için, uygunluk testi bırakılarak doğrudan amaç fonksiyonu sınır (bound) testine geçilir.

Serbest değişkenlerden katsayısı en büyük ve pozitif olan

x_3

değişkenine öncelikle

0

değeri atanarak kısıt ihlali giderilmeye çalışılır ve alt dallara geçilir.

Mevcut atamalar eşitsizliği sağlamadığı için kısıt yönü tersine çevrilir ve düğüm budanmadan çözüm araştırmasına aynı daldan devam edilir.

Show answer & explanation

Answer: Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Answer

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Balas algoritmasında (Kapalı Sayımlama) bir düğümün uygun bir çözüm üretip üretemeyeceği, serbest değişkenlere eşitsizliği en elverişli hale getirecek değerler verilerek test edilir.

4x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

kısıtında

x_1 = 1

x_5 = 1

atandığında, eşitsizlik

-3x_2 + 5x_3 - 2x_4 \le -10

halini alır. Eşitsizlik yönü

\le

olduğu için sol tarafı en küçük yapmak hedeflenir. Negatif katsayılı olanlara

1

(

x_2=1, x_4=1

), pozitif katsayılı olana

0

(

x_3=0

) verdiğimizde sol tarafın alabileceği en küçük değer

-5

olur.

-5

değeri

-10

'dan küçük veya eşit olmadığı için, bu kısıt serbest değişkenlerin alacağı hiçbir değerle sağlanamaz. Kesin kısıt ihlali söz konusu olduğundan düğüm uygunsuzluk (infeasibility) gerekçesiyle algoritmada derhal budanır.

Step-by-Step Solution

Mevcut atamaları kısıt denkleminde yerine koyun.

4(1) - 3x_2 + 5x_3 - 2x_4 + 2(1) \le -4

işlemi yapılarak

6 - 3x_2 + 5x_3 - 2x_4 \le -4

elde edilir.

Serbest değişkenlerin sağlaması gereken kalan eşitsizliği bulmak için sabitlenmiş değerler denkleme yansıtılır.

Eşitsizliği sadeleştirin.

Sabit olan

6

karşı tarafa atıldığında

-3x_2 + 5x_3 - 2x_4 \le -10

eşitsizliğine ulaşılır.

Serbest değişkenlerin hedef eşik değerini tam olarak görmek için matematiksel sadeleştirme yapılır.

Sol tarafı minimize edecek en elverişli

0-1

atamalarını belirleyin.

Sol tarafın en küçük değeri alabilmesi için katsayısı negatif olan değişkenlere

1

(

x_2 = 1, x_4 = 1

), katsayısı pozitif olan değişkenlere

0

(

x_3 = 0

) atanır. Bu durumda sol taraf:

-3(1) + 5(0) - 2(1) = -5

olur.

Bir düğümün uygun bir çözüm üretme ihtimalini test etmek için, "küçük eşittir" (

\le

) kısıt yönüne göre sol taraf matematiksel olarak elde edilebilecek en küçük değere çekilir.

Elde edilen minimum değeri eşitsizliğin sağ tarafı ile karşılaştırın.

Bulunan en küçük değer olan

-5

, eşitsizliğin sağ tarafındaki

-10

değerinden küçük veya eşit değildir (

-5 \not\le -10

Serbest değişkenler kullanılarak kısıtı sağlamak adına yapılabilecek en iyi atama bile eşitsizliği sağlayamıyorsa, bu düğümden türetilecek hiçbir çözüm uygun (feasible) olamaz ve düğüm uygunsuzluktan dolayı budanır.

Key Concept

Balas Algoritmasında Uygunsuzluk (Infeasibility) Budama Kriteri

Kapalı Sayımlama (Balas) Algoritması

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes