Examkin

Soru

Zorluk: ZorÖzel Durumlar (Sınırsızlık, Çoklu Çözüm, Uygunsuzluk, Dejenerelik)

Bir kamu kurumunun lojistik ağındaki dağıtım maliyetlerini en küçükleme (minimizasyon) amacıyla kurduğu doğrusal programlama modelinin Simpleks algoritması ile çözümünde nihai (optimal) tabloya ulaşılmıştır.

Tabloda incelenen değerlere göre şu iki durum tespit edilmiştir:
I. Temel dışı (non-basic) bir karar değişkeninin net değerlendirme satırındaki (Zj−CjZ_j - C_j) değeri tam olarak sıfırdır.
II. İlgili temel dışı değişkenin sütununda yer alan tüm yer değiştirme (teknolojik) katsayıları sıfır veya negatiftir (≤0\leq 0).

Buna göre, modellenen problem ve elde edilen çözüm durumu hakkında aşağıdakilerden hangisi kesinlikle doğrudur?

  1. Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.Cevap
  2. B
    Problemde amaç fonksiyonunu eksi sonsuza götüren bir sınırsızlık durumu vardır ve problemin herhangi bir optimal çözümü bulunamaz.
  3. C
    Simpleks algoritmasının önceki adımlarında en küçük oran testinde eşitlik çıkmış olup, çözüm dejenereliğe (bozulmaya) uğradığı için iterasyonlar tıkanmıştır.
  4. D
    Kurulan modeldeki kısıtlar birbiriyle çelişmektedir, bu nedenle problemin uygun çözüm alanı boştur ve yapay değişkenler temelden çıkmamıştır.
  5. E
    Uygun çözüm alanı her yönden kapalı (sınırlı) bir dışbükey çokgendir ve problemin yalnızca tek bir köşede gerçekleşen benzersiz (unique) bir optimal çözümü vardır.

Cevap

Problemin uygun çözüm alanı sınırsızdır, ancak amaç fonksiyonu değeri sınırlıdır ve birbirine eşit amaç fonksiyonu değeri veren sonsuz sayıda alternatif optimal çözüm bulunur.
Verilen iki durumun birleşimi, yöneylem araştırmasında özel ve ileri düzey bir senaryoyu tanımlar. Optimal bir tabloda temel dışı bir karar değişkeninin net değerlendirme (fırsat maliyeti) değerinin sıfır olması, bu problemin çoklu (alternatif) optimal çözüme sahip olduğunu kanıtlar. Bu değişken temele sokulmak istendiğinde, sütunundaki tüm teknolojik katsayıların sıfır veya negatif olması ise oran testi yapılamayacağını, dolayısıyla o eksen boyunca çözüm alanının sınırsız (açık) olduğunu gösterir. Ancak değişken temele girse bile amaç fonksiyonuna net katkısı sıfır olduğundan, çözüm alanı sonsuza gitmesine rağmen amaç fonksiyonu değeri bozulmaz ve sabit kalır. Matematiksel ve grafiksel olarak bu durum; sınırsız bir uygun çözüm bölgesi üzerinde, amaç fonksiyonu doğrusuna paralel olan ve sonsuza uzanan bir optimal çözümler ışını (ray) elde edildiğini kesin olarak doğrular.

Adım Adım Çözüm

1
Birinci öncülün (Temel dışı değişken için Zj−Cj=0Z_j - C_j = 0) analiz edilmesi.
Problemin alternatif (çoklu) optimal çözümü olduğu tespit edilir.
Optimal bir tabloda temel dışı bir değişkenin amaca katkısının sıfır olması, bu değişkenin temele girmesi halinde amaç fonksiyonu değerinin değişmeyeceğini (mevcut optimal değerin korunacağını) gösterir.
2
İkinci öncülün (Sütundaki katsayıların ≤0\leq 0 olması) analiz edilmesi.
Uygun çözüm alanının o değişken yönünde sınırsız olduğu tespit edilir.
Temele girecek değişkenin sütununda hiç pozitif katsayı olmaması, Simpleks oran testinin yapılamayacağı ve değişkenin mevcut kısıtları ihlal etmeden sonsuza kadar artırılabileceği anlamına gelir.
3
İki bilginin sentezlenerek çözümün genel yorumunun yapılması.
Uygun çözüm alanının sınırsız olduğu, ancak bu yönde ilerlerken amaç fonksiyonu değerinin değişmemesi sebebiyle amaç fonksiyonunun sınırlı kaldığı sonucuna varılır.
Değişken sonsuza giderken amaç fonksiyonuna katkısı sıfır olduğundan, amaç değeri sonsuza gitmez. Bu durum, sınırsız bir uygun çözüm alanı içinde, amaç fonksiyonu ile çakışan ve sonsuza uzanan bir 'alternatif optimal çözümler ışını' (ray) oluşturur.

Anahtar Kavram

Özel Durumlarda Çoklu Çözüm ve Sınırsız Alan İlişkisi
Bu soruyu puanla

Konular

Özel Durumlar (Sınırsızlık, Çoklu Çözüm, Uygunsuzluk, Dejenerelik)

Bu konudan daha fazla soru