Examkin

Soru

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

Bir üretim planlaması için oluşturulan iki değişkenli saf tamsayılı maksimizasyon problemi aşağıda verilmiştir:

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

Bu problem Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünde tamsayı kısıtları gevşetilerek çözülen doğrusal programlama modelinin optimal çözümü x1=2,25x_1 = 2,25, x2=1,5x_2 = 1,5 ve amaç fonksiyonu değeri Z=12,75Z = 12,75 olarak bulunmuştur.
Algoritmanın standart işleyişine göre, tamsayı olmayan değişkenler arasından en büyük kesirli kısma sahip olan değişken seçilerek ilk dallanma yapılacaktır.

Buna göre, kök düğümden yapılan bu dallanma işlemi sonucunda elde edilecek iki yeni alt düğümün gevşetilmiş (relaxed) amaç fonksiyonu (ZZ) değerleri aşağıdakilerden hangisinde doğru olarak verilmiştir?

  1. A
    x2≤1x_2 \leq 1 dalı için Z=10,75Z = 10,75 ve x2≥2x_2 \geq 2 dalı için Z=14,75Z = 14,75
  2. B
    x1≤2x_1 \leq 2 dalı için Z=12,67Z = 12,67 ve x1≥3x_1 \geq 3 dalı için Z=9,0Z = 9,0
  3. x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5Cevap
  4. D
    x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥1x_2 \geq 1 dalı için Z=12,75Z = 12,75
  5. E
    x2≤1x_2 \leq 1 dalı için Z=10,0Z = 10,0 ve x2≥2x_2 \geq 2 dalı için Z=11,0Z = 11,0

Cevap

Doğru değerler x2≤1x_2 \leq 1 dalı için Z=11,5Z = 11,5 ve x2≥2x_2 \geq 2 dalı için Z=12,5Z = 12,5'tir.
Doğru dallanma kuralı uygulanarak en büyük kesirli kısma sahip olan x2x_2 değişkeni seçilmiş ve x2≤1x_2 \leq 1 ile x2≥2x_2 \geq 2 dalları oluşturulmuştur. Her iki dal için doğrusal programlama modeli yeni kısıtlarla yeniden çözüldüğünde sırasıyla Z=11,5Z=11,5 ve Z=12,5Z=12,5 değerlerine ulaşılır.

Adım Adım Çözüm

1
Dallanma değişkenini belirleme
x1x_1'in kesirli kısmı 0,250,25 ve x2x_2'nin kesirli kısmı 0,500,50'dir.
Algoritma kuralı gereği en büyük kesirli kısma sahip olan değişken (x2x_2) üzerinden dallanma yapılır.
2
Dallanma kısıtlarını oluşturma
İki yeni alt düğüm için x2≤1x_2 \leq 1 ve x2≥2x_2 \geq 2 kısıtları elde edilir.
x2=1,5x_2=1,5 tamsayı olmadığı için bir alt tamsayıya yuvarlanarak sol dal, bir üst tamsayıya yuvarlanarak sağ dal oluşturulur.
3
x2≤1x_2 \leq 1 dalı için problemi çözme
Mevcut kısıtlarda x2=1x_2=1 alındığında dar kısıt 2x1+1≤6⇒x1≤2,52x_1 + 1 \leq 6 \Rightarrow x_1 \leq 2,5 olur. Bu dal için Z=3(2,5)+4(1)=11,5Z = 3(2,5) + 4(1) = 11,5 bulunur.
Amaç fonksiyonunu maksimize etmek için kısıtların izin verdiği en büyük değerler olan x1=2,5x_1=2,5 ve x2=1x_2=1 seçilir.
4
x2≥2x_2 \geq 2 dalı için problemi çözme
Mevcut kısıtlarda x2=2x_2=2 alındığında dar kısıt 2x1+6≤9⇒x1≤1,52x_1 + 6 \leq 9 \Rightarrow x_1 \leq 1,5 olur. Bu dal için Z=3(1,5)+4(2)=12,5Z = 3(1,5) + 4(2) = 12,5 bulunur.
Tüm kısıtları aynı anda sağlayan en uygun değerler olan x1=1,5x_1=1,5 ve x2=2x_2=2 belirlenir.

Anahtar Kavram

Dal-Sınır Algoritmasında Düğüm Değerlendirme
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru