Examkin

Question

Difficulty: MediumDal-Sınır (Branch and Bound) Algoritması

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin modeli şu şekildedir:

Maksimum Z=8x1+5x2\text{Maksimum } Z = 8x_1 + 5x_2
Kısıtlar:\text{Kısıtlar:}
x1+x2≤6x_1 + x_2 \leq 6
9x1+5x2≤459x_1 + 5x_2 \leq 45
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Algoritmanın ilk adımında doğrusal programlama gevşetmesi çözülmüş ve başlangıç çözümü x1=3,75x_1 = 3,75 ve x2=2,25x_2 = 2,25 (Z=41,25Z = 41,25) olarak bulunmuştur. Algoritmanın standart kuralları gereği x1x_1 değişkeni üzerinden dallandırma (branching) yapılmasına karar verilmiştir.

Buna göre, x1≥4x_1 \geq 4 kısıtının eklendiği yeni alt problemin (düğümün) optimum amaç fonksiyonu değeri (ZZ) kaçtır?

  1. 41,00Answer
  2. B
    41,25
  3. C
    39,00
  4. D
    32,00
  5. E
    45,00

Answer

Eklenen kısıt altında bu alt problemin optimum amaç fonksiyonu değeri 41,00'dir.
Dallandırma kuralına göre x1≥4x_1 \geq 4 kısıtı modele eklendiğinde, x1x_1 değişkeni amaç fonksiyonu katsayısı daha büyük olduğu için sınır değerinde (44) sabitlenir. Bu durumda kısıtlar altında x2x_2 değişkeni en fazla 1,81,8 değerini alabilir. 8(4)+5(1,8)8(4) + 5(1,8) işlemi sonucunda bu düğüme ait amaç fonksiyonu değeri 41 olarak bulunur.

Step-by-Step Solution

1
x1≥4x_1 \geq 4 kısıtını modele ekleyerek alt problemi tanımlayın.
Yeni kısıtlar: x1≥4x_1 \geq 4, x1+x2≤6x_1 + x_2 \leq 6 ve 9x1+5x2≤459x_1 + 5x_2 \leq 45.
Dallandırma işlemi, gevşetilmiş çözümdeki tamsayı olmayan değişkenin alt ve üst tam sayı sınırlarını kısıt olarak eklemektir.
2
Eklenen kısıtlar altında x2x_2 değişkeninin alabileceği en büyük değeri belirleyin.
x1=4x_1 = 4 için: 4+x2≤6⇒x2≤24 + x_2 \leq 6 \Rightarrow x_2 \leq 2 ve 9(4)+5x2≤45⇒5x2≤9⇒x2≤1,89(4) + 5x_2 \leq 45 \Rightarrow 5x_2 \leq 9 \Rightarrow x_2 \leq 1,8.
Maksimizasyon probleminde, ZZ fonksiyonunun katsayıları pozitif olduğundan x1x_1 ve x2x_2 değişkenlerinin mümkün olan en büyük değerleri alması gerekir. x2x_2 için en dar kısıt 1,81,8 değeridir.
3
Bulunan (x1,x2)(x_1, x_2) değerlerini amaç fonksiyonunda yerine koyun.
Z=8(4)+5(1,8)=32+9=41Z = 8(4) + 5(1,8) = 32 + 9 = 41.
Alt problemin (düğümün) sınır değerini (upper bound) bulmak için optimum nokta hesaplanır.

Key Concept

Dal-Sınır algoritmasında her bir dallandırma işlemi, tamsayı olmayan bölgeyi dışarıda bırakacak şekilde arama uzayını daraltan yeni kısıtlar ekleyerek alt problemler oluşturur.

Practice More

Bu düğümden sonra x2=1,8x_2 = 1,8 değeri üzerinden yapılacak dallandırmanın sonuçlarını inceleyerek tamsayı çözüme ulaşmaya çalışın.
Estimated Time:1m 30s
Rate this question

Topics

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

More questions from this topic