Examkin

Soru

Zorluk: ZorSaf Tamsayılı Programlama Modelleri

Amaç fonksiyonu katsayılarının tamamı tamsayı olan maksimizasyon yönlü saf tamsayılı bir doğrusal programlama problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Sadece tek bir optimum çözümün bulunmasının hedeflendiği bu problemde, algoritmanın belirli bir aşamasında mevcut en iyi tamsayılı çözümün (alt sınır) amaç fonksiyonu değeri Z=125Z = 125 olarak belirlenmiştir.

Aynı aşamada, henüz dallandırılmamış olan üç farklı aktif düğümün (X, Y ve Z) doğrusal programlama gevşetmesi (LP relaxation) çözülmüş ve aşağıdaki amaç fonksiyonu değerleri elde edilmiştir:

• Düğüm X: ZX=127.4Z_X = 127.4 (En az bir değişken kesirli)
• Düğüm Y: ZY=125.8Z_Y = 125.8 (En az bir değişken kesirli)
• Düğüm Z: ZZ=124.6Z_Z = 124.6 (En az bir değişken kesirli)

Buna göre, algoritmanın karar kuralları işletildiğinde düğümlerin durumu ile ilgili aşağıdaki ifadelerden hangisi kesinlikle doğrudur?

  1. A
    Düğüm Y'nin amaç fonksiyonu değeri (125.8125.8), mevcut alt sınırdan (125125) büyük olduğu için daha iyi bir tamsayılı çözüm bulma ihtimaline karşı Düğüm Y dallandırılmaya devam edilmelidir.
  2. B
    Düğüm X'in amaç fonksiyonu değeri en yüksek olduğu için, bu düğümdeki kesirli değişkenler doğrudan en yakın tamsayıya yuvarlanarak yeni alt sınır 127127 olarak güncellenmelidir.
  3. Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.Cevap
  4. D
    Düğüm Z'nin amaç fonksiyonu değeri mevcut alt sınırdan küçük olsa da, dallandırma kısıtları eklendikçe amaç fonksiyonu değeri artabileceği için Düğüm Z aktif tutulmalıdır.
  5. E
    Düğümlerin tamamında en az bir değişken kesirli çıktığı için problemin uygun bir saf tamsayılı çözümü olmadığı kararına varılarak algoritma derhal sonlandırılmalıdır.

Cevap

Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.
Maksimizasyon yönlü ve katsayıları tamsayı olan bir saf tamsayılı programlama probleminde, herhangi bir tamsayılı çözümün ZZ değeri de mutlaka tamsayı olmak zorundadır. Doğrusal programlama gevşetmesi, o düğümden elde edilebilecek tüm çözümler için aşılmaz bir üst sınır (upper bound) verir. Düğüm Y için bu üst sınır 125.8125.8'dir. Değişkenler tamsayıya zorlandığında, bu daldan elde edilebilecek en büyük ZZ değeri aşağı yuvarlanarak en fazla 125125 olabilir. Algoritma zaten Z=125Z = 125 değerini veren geçerli bir tamsayılı çözüme (mevcut alt sınır) sahiptir. Problemde tek bir optimum çözüm arandığı için, Düğüm Y'den daha iyi bir sonuç (Z≥126Z \ge 126) elde etme olasılığı sıfırdır. Bu yüzden Düğüm Y budanarak (kapatılarak) elenir.

Adım Adım Çözüm

1
Maksimizasyon probleminde Dal-Sınır algoritmasının temel budama (fathoming) kurallarını belirleme.
Bir düğümün budanması için doğrusal programlama gevşetmesi (üst sınır) değerinin, mevcut en iyi tamsayılı çözümden (alt sınır) daha kötü veya ona eşit olması gerekir.
Algoritmanın amacı, yalnızca elimizdeki mevcut en iyi çözümden daha üstün (daha iyi) çözümler aramaktır.
2
Saf tamsayılı modelde amaç fonksiyonu katsayılarının tamsayı olmasının matematiksel etkisini analiz etme.
Hem karar değişkenleri hem de amaç fonksiyonu katsayıları tamsayı olduğundan, amaç fonksiyonu ZZ yalnızca tamsayı değerler alabilir.
Tamsayıların doğrusal kombinasyonu her zaman bir tamsayıdır.
3
Düğüm Y'nin üretebileceği maksimum tamsayı değerini hesaplama.
ZY=125.8Z_Y = 125.8 olduğuna göre, değişkenler tamsayı olmaya zorlandığında bu daldan elde edilebilecek en yüksek ZZ değeri ⌊125.8⌋=125\lfloor 125.8 \rfloor = 125'tir.
Doğrusal programlama gevşetmesi, ilgili daldaki tüm olası tamsayılı çözümler için kesin bir üst sınır (upper bound) sağlar.
4
Elde edilen bu üst sınırı mevcut alt sınır ile karşılaştırma.
Düğüm Y'nin üretebileceği maksimum değer (125125), halihazırda elimizde bulunan mevcut en iyi çözüme (Z=125Z = 125) eşittir. Tek bir optimum çözüm arandığı için daha iyi bir çözüm çıkma ihtimali yoktur.
Bu nedenle Düğüm Y dallandırılmadan budanır (kapatılır). Düğüm Z (124.6<125124.6 < 125) zaten budanır. Sadece Düğüm X (⌊127.4⌋=127>125\lfloor 127.4 \rfloor = 127 > 125) dallandırılmaya devam edilir.

Anahtar Kavram

Saf Tamsayılı Programlamada Dal-Sınır Algoritması ve Budama Kuralları
Bu soruyu puanla

Konular

Saf Tamsayılı Programlama Modelleri

Bu konudan daha fazla soru