Examkin

Soru

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

Doğrusal programlama problemlerinin Simpleks algoritması ile çözümü sürecinde, bir iterasyondan diğerine geçişte anahtar satırın belirlenmesi amacıyla yapılan oran testi (min{bi/aij∣aij>0}min \{ b_i / a_{ij} \mid a_{ij} > 0 \}) sonucunda, en küçük oran değerinin birden fazla kısıt satırı için aynı olduğu saptanmıştır. Bu durum, bir sonraki iterasyonda elde edilecek temel uygun çözüm ile ilgili aşağıdakilerden hangisine neden olur?

  1. A
    Problemin uygun bir çözümünün bulunmamasına (Uygunsuzluk)
  2. Temel değişkenlerden en az birinin değerinin sıfıra eşit olmasına (Dejenerelik)Cevap
  3. C
    Amaç fonksiyonu değerinin sonsuza gitmesine (Sınırsızlık)
  4. D
    Problemin birden fazla alternatif optimal çözüme sahip olmasına
  5. E
    Algoritmanın çözüm sürecinin sonlanarak optimal tabloya ulaşılmasına

Cevap

Oran testindeki eşitlik durumu, bir sonraki çözümde en az bir temel değişkenin değerinin sıfır olmasına (dejenerelik) neden olur.
Simpleks yönteminde anahtar satır seçimi için yapılan oran testinde birden fazla satırın aynı minimum değeri vermesi, bir sonraki iterasyonda temel değişkenlerden en az birinin sıfır değerini alacağını gösterir. Bu durum literatürde 'dejenerelik' veya 'bozulma' (degeneracy) olarak adlandırılır.

Adım Adım Çözüm

1
Oran testinin amacını değerlendir
Oran testi, çözüm kümesinin (uygun bölge) sınırları dışına çıkmadan temelden ayrılacak olan değişkeni (anahtar satır) belirler.
Anahtar satır, uygun çözüm bölgesinin sınırlarını belirleyen kısıtları temsil eder.
2
Eşitlik (tie) durumunun etkisini incele
Birden fazla satırda aynı minimum oran çıktığında, giren değişken tabana girdiğinde bu satırlardaki tüm değişkenler aynı anda sıfıra ulaşır.
Değişkenlerin değişim hızları (katsayıları) ve mevcut değerleri arasındaki oran aynı olduğu için aynı anda sınır değerine ulaşırlar.
3
Sonuç aşamasını belirle
Yalnızca bir değişken temelden çıkabilirken, sıfıra düşen diğer değişkenler temel değişken olarak kalmaya devam eder (dejenerelik oluşur).
Temel çözümde sıfır değerli bir değişkenin bulunması, problemin dejenereliğe (bozulmaya) uğradığını tanımlar.

Anahtar Kavram

Simpleks Oran Testi ve Dejenerelik (Bozulma)
Tahmini Süre:45s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru