Examkin

Soru

Zorluk: OrtaDal-Sınır (Branch and Bound) Algoritması

Bir tamsayılı programlama modeli aşağıda verilmiştir:

Maksimum Z=8x1+5x2\text{Maksimum } Z = 8x_1 + 5x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤4,5x_1 + x_2 \leq 4,5
x1≤3,2x_1 \leq 3,2
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin doğrusal programlama gevşetmesi (LP relaxation) çözüldüğünde optimal sonuçlar x1=3,2x_1 = 3,2, x2=1,3x_2 = 1,3 ve Z=32,1Z = 32,1 olarak bulunmuştur. Dal-Sınır (Branch and Bound) algoritması uygulanarak x1x_1 değişkeni üzerinden dallandırma yapıldığında, x1≤3x_1 \leq 3 kısıtının eklendiği alt problemin doğrusal programlama gevşetmesine göre optimal amaç fonksiyonu değeri (ZZ) aşağıdakilerden hangisidir?

  1. 31,5Cevap
  2. B
    32,1
  3. C
    24,0
  4. D
    31,0
  5. E
    Uygun çözüm yoktur

Cevap

Yeni kısıt altında hesaplanan optimal amaç fonksiyonu değeri 31,5'tir.
Dallandırma işlemi sonucunda x1≤3x_1 \leq 3 kısıtı modele eklenir. Bu durumda x1x_1 değişkeninin alabileceği en büyük değer 3 olur. x1=3x_1 = 3 değeri ilk kısıtta (x1+x2≤4,5x_1 + x_2 \leq 4,5) yerine yazıldığında x2≤1,5x_2 \leq 1,5 elde edilir. Amaç fonksiyonu 8(3)+5(1,5)8(3) + 5(1,5) işleminden 31,5 olarak hesaplanır.

Adım Adım Çözüm

1
Alt problemin kısıtlarını belirleme
x1+x2≤4,5x_1 + x_2 \leq 4,5, x1≤3,2x_1 \leq 3,2 ve x1≤3x_1 \leq 3
Dallandırma işlemi seçilen değişkenin tamsayı olmayan değerini içine almayan iki yeni kısıt kümesi oluşturur.
2
Kısıtları sadeleştirme
x1+x2≤4,5x_1 + x_2 \leq 4,5 ve x1≤3x_1 \leq 3
x1≤3x_1 \leq 3 kısıtı, x1≤3,2x_1 \leq 3,2 kısıtını kapsadığı için daha dar bir bölge tanımlar ve üsttekini gereksiz kılar.
3
Yeni uygun çözüm bölgesinde Z değerini maksimize etme
x1=3x_1 = 3 için x2=4,5−3=1,5x_2 = 4,5 - 3 = 1,5 bulunur.
x1x_1 katsayısı daha yüksek olduğu için sınır değerine (3) eşitlenerek x2x_2 değeri kısıt üzerinden hesaplanır.
4
Amaç fonksiyonunu hesaplama
Z=8(3)+5(1,5)=24+7,5=31,5Z = 8(3) + 5(1,5) = 24 + 7,5 = 31,5
Bulunan değişken değerleri amaç fonksiyonunda yerine konur.

Anahtar Kavram

Dal-Sınır algoritmasında bir düğümün gevşetilmiş çözümü, eklenen tamsayı kısıtları altında yeniden hesaplanır.

Daha Fazla Pratik

x1 >= 4 kısıtının neden uygun çözüm içermediğini (infeasible) kısıt doğruları üzerinden inceleyiniz.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Dal-Sınır (Branch and Bound) Algoritması

Bu konudan daha fazla soru