Examkin

Kapalı Sayımlama (Balas) Algoritması

11 soru

Soru 1Soru →

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

Minimize Z=5x1+3x2+8x3\text{Minimize } Z = 5x_1 + 3x_2 + 8x_3
Kısıtlar:
x1+x2+x3≥2x_1 + x_2 + x_3 \geq 2
2x1−x2+4x3≥52x_1 - x_2 + 4x_3 \geq 5
x1,x2,x3∈{0,1}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∗=10Z^* = 10 olduğu ve x1=0x_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?

Cevabı ve açıklamayı göster

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

Cevap

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.
Verilen x1=0x_1 = 0 ataması altında ikinci kısıt −x2+4x3≥5-x_2 + 4x_3 \geq 5 halini almaktadır. Bu kısıtta x2x_2 ve x3x_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) x2=0x_2=0 ve x3=1x_3=1 iken 4'tür. 4≥54 \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.

Adım Adım Çözüm

1
Kısmi atama değerini kısıtlarda yerine koyun.
x1=0x_1 = 0 için ikinci kısıt: 2(0)−x2+4x3≥5⇒−x2+4x3≥52(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.
2
Kısıtın sol tarafının alabileceği maksimum değeri hesaplayın.
−x2+4x3-x_2 + 4x_3 ifadesi için x2=0x_2=0 ve x3=1x_3=1 seçildiğinde maksimum değer −0+4(1)=4-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.
3
Hesaplanan maksimum değeri kısıt sağ tarafı ile karşılaştırın.
4<54 < 5 olduğu için kısıt hiçbir x2,x3∈{0,1}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.
4
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.

Anahtar Kavram

Balas Algoritmasında Budama (Fathoming) Kriterleri
Soru 2Soru →

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:

2x1+3x2+6x3≥72x_1 + 3x_2 + 6x_3 \geq 7

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

Cevabı ve açıklamayı göster

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

Cevap

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 x3=0x_3=0 olarak sabitlendiğinde, kısıtı en çok destekleyen x1=1x_1=1 ve x2=1x_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.

Adım Adım Çözüm

1
Kısmi çözümdeki değişken değerini kısıt denklemine yerleştirin.
2x1+3x2+6(0)≥7⇒2x1+3x2≥72x_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.
2
Kalan serbest değişkenler (x1,x2x_1, x_2) için sol tarafın alabileceği maksimum değeri hesaplayın.
x1=1x_1=1 ve x2=1x_2=1 için 2(1)+3(1)=52(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.
3
Elde edilen maksimum değeri kısıtın sağ tarafındaki değerle (RHS) kıyaslayın.
5<75 < 7
Sol tarafın alabileceği en büyük değer bile kısıtı sağlamaya yetmemektedir.
4
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.

Anahtar Kavram

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

Daha Fazla Pratik

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.
Tahmini Süre:1m 30s
Soru 3Soru →

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?

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

Balas algoritmasında standart form (minimizasyon ve pozitif katsayılar) budama (fathoming) mantığının temelini oluşturur.
Soru 4Soru →

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?

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

İpuçları

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.

Daha Fazla Pratik

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.
Tahmini Süre:1m 30s
Soru 5Soru →

0−10-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 (00 veya 11) 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?

Cevabı ve açıklamayı göster

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

Cevap

İ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 11, negatifler için 00 yaparak) mevcut yetersizliği gideremiyorsa, o daldan devam etmenin bir anlamı kalmaz ve dal budanır.

Adım Adım Çözüm

1
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.
2
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.
3
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.

Anahtar Kavram

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

Daha Fazla Pratik

Balas algoritmasında 'üst sınır (Z*) yardımıyla budama' kriterini de incelemek, konunun tam anlaşılmasını sağlar.
Tahmini Süre:1m 30s
Soru 6Soru →

Balas’ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir 0−10-1 tamsayılı minimizasyon probleminde, o ana kadar elde edilen en iyi uygun çözümün amaç fonksiyonu değeri Z∗=15Z^* = 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ı 1212’dir. Bu düğümde serbest durumda bulunan üç değişkenin maliyet katsayıları ise sırasıyla 4,54, 5 ve 77’dir. Yapılan teknik incelemede, kısıtların tamamının sağlanabilmesi için bu serbest değişkenlerden en az birinin 11 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?

Cevabı ve açıklamayı göster

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

Cevap

Kısıtları sağlamak için gereken en düşük maliyet eklendiğinde (12+4=1612 + 4 = 16) elde edilen alt sınır mevcut en iyi çözümden (1515) 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∗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 44 birimlik maliyet eklendiğinde bile toplam maliyet 1616 olmaktadır. 16>1516 > 15 olduğu için bu dal kesinlikle elenmelidir.

Adım Adım Çözüm

1
Mevcut durumun analizi
Z∗=15Z^* = 15, mevcut maliyet =12= 12, serbest değişken katsayıları ={4,5,7}= \{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.
2
Kısıt gereksiniminin belirlenmesi
En az bir serbest değişken 11 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.
3
Alt sınırın (Z-sınırı) hesaplanması
Minimum maliyet =12+min⁡(4,5,7)=12+4=16= 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.
4
Budama kriterinin uygulanması
16>1516 > 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.

Anahtar Kavram

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

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

1
Balas algoritmasının standart formunu hatırla.
Problem minimizasyon yapısındadır ve tüm cj≥0c_j \geq 0 katsayılarına sahiptir.
Algoritmanın temel işleyişi katsayıların negatif olmaması üzerine kuruludur.
2
Amaç fonksiyonu değerinin değişimini analiz et.
Yeni değişkenlerin çözüme dahil edilmesi (1 atanması), amaç değerini (ZZ) sadece artırabilir veya sabit bırakabilir.
Katsayılar cj≥0c_j \geq 0 olduğu için ZZ değeri azalmaz.
3
Sınır (Bound) kontrolü yap.
Eğer Zkısmi≥Z∗Z_{kısmi} \geq Z^* ise, bu daldan gelecek hiçbir çözüm mevcut en iyi çözümü (Z∗Z^*) iyileştiremez.
Daha iyi bir çözüm bulunma ihtimali kalmadığı için bu dalın incelenmesi durdurulur (kapalı sayımlama).

Anahtar Kavram

Balas Algoritmasında Budama (Fathoming) Kriteri
Soru 8Soru →

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

Cevabı ve açıklamayı göster

Cevap: Tüm cjc_j katsayıları negatif olmayan (cj≥0c_j \geq 0) değerler olmalıdır.

Cevap

Balas algoritmasının standart minimizasyon formunda tüm amaç fonksiyonu katsayıları negatif olmayan (cj≥0c_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ı (cj≥0c_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ü (xj=1−yjx_j = 1 - y_j) yapılarak bu şart sağlanmalıdır.

Adım Adım Çözüm

1
Algoritmanın temel yapısını analiz etme
Balas'ın Kapalı Sayımlama algoritması, 0−10-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.
2
Standart form gerekliliklerini belirleme
Algoritmanın doğrudan uygulanabilmesi için problemin minimizasyon formunda olması ve tüm amaç fonksiyonu katsayılarının (cjc_j) negatif olmaması şartı aranır.
Bu şart, değişkenlerin değerinin 00'dan 11'e çıkarılması durumunda amaç fonksiyonu değerinin (Z) asla azalmayacağını garanti eder.
3
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∗Z^*) büyükse, cj≥0c_j \geq 0 olduğu sürece daha fazla değişkenin 11 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.

Anahtar Kavram

Balas Algoritması Standart Formu

Daha Fazla Pratik

Balas algoritmasında kısıtların uygunluğunu kontrol etmek için kullanılan 'kısıt açığı' (slack) kavramını inceleyebilirsiniz.
Tahmini Süre:45s
Soru 9Soru →

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?

Cevabı ve açıklamayı göster

Cevap: 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ı

Cevap

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

Adım Adım Çözüm

1
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.
2
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.
3
İ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.

Anahtar Kavram

Uygunsuzluk Nedeniyle Budama (Fathoming by Infeasibility)
Soru 10Soru →

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?

Cevabı ve açıklamayı göster

Cevap: 5

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
Soru 11Soru →

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−10-1 tamsayılı minimizasyon modelinde, çözüm ağacının belirli bir düğümünde 1. ve 5. projelere onay verilmiş (x1=1x_1 = 1 ve x5=1x_5 = 1), 2., 3. ve 4. projelerin durumu ise henüz karara bağlanmamıştır (x2,x3,x4x_2, x_3, x_4 serbest değişkendir).

Modelin kaynak kullanım kısıtlarından birinin matematiksel ifadesi şöyledir:
4x1−3x2+5x3−2x4+2x5≤−44x_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?

Cevabı ve açıklamayı göster

Cevap: 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.

Cevap

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. 4x1−3x2+5x3−2x4+2x5≤−44x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4 kısıtında x1=1x_1 = 1 ve x5=1x_5 = 1 atandığında, eşitsizlik −3x2+5x3−2x4≤−10-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 11 (x2=1,x4=1x_2=1, x_4=1), pozitif katsayılı olana 00 (x3=0x_3=0) verdiğimizde sol tarafın alabileceği en küçük değer −5-5 olur. −5-5 değeri −10-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.

Adım Adım Çözüm

1
Mevcut atamaları kısıt denkleminde yerine koyun.
4(1)−3x2+5x3−2x4+2(1)≤−44(1) - 3x_2 + 5x_3 - 2x_4 + 2(1) \le -4 işlemi yapılarak 6−3x2+5x3−2x4≤−46 - 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.
2
Eşitsizliği sadeleştirin.
Sabit olan 66 karşı tarafa atıldığında −3x2+5x3−2x4≤−10-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.
3
Sol tarafı minimize edecek en elverişli 0−10-1 atamalarını belirleyin.
Sol tarafın en küçük değeri alabilmesi için katsayısı negatif olan değişkenlere 11 (x2=1,x4=1x_2 = 1, x_4 = 1), katsayısı pozitif olan değişkenlere 00 (x3=0x_3 = 0) atanır. Bu durumda sol taraf: −3(1)+5(0)−2(1)=−5-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.
4
Elde edilen minimum değeri eşitsizliğin sağ tarafı ile karşılaştırın.
Bulunan en küçük değer olan −5-5, eşitsizliğin sağ tarafındaki −10-10 değerinden küçük veya eşit değildir (−5≰−10-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.

Anahtar Kavram

Balas Algoritmasında Uygunsuzluk (Infeasibility) Budama Kriteri