Doğrusal Programlamada Dejenerasyon

"Dejenere" kelimesi, Latince "degenerare" (düşüşe geçmek, bozulmak) kelimesinden türetilmiştir. Latince "genus" (ırk, tür) kökünden gelir ve bozulma, kötüleşme anlamına gelir.

Doğrusal programlamada (LP) dejenerasyon, geçerli bölgenin belirli bir köşe noktasında (vertex) o noktayı benzersiz olarak tanımlamak için gerekli olandan fazla aktif kısıtlamanın olması durumudur. Bu durum, Simpleks yöntemi gibi algoritmalarla hesaplama zorluklarına yol açabilir ve duraklama veya döngüsel davranışa neden olabilir. Bu makalede, dejenerasyon kavramını detaylı olarak inceleyeceğiz, nedenlerini ve doğrusal programlama problemlerini çözme üzerindeki etkilerini ele alacağız.

Dejenerasyon Nedir?

Doğrusal programlamada dejenerasyon, bir temel uygun çözümde bir veya daha fazla temel değişkenin sıfır olması durumunda meydana gelir. Geometrik terimlerle, bu, geçerli bölgenin bir köşe noktasının gereğinden fazla kısıtlama ile tanımlandığı anlamına gelir. Bu fazla aktif kısıtlamalar, Simpleks yöntemindeki pivot seçim sürecinde belirsizlik yaratabilir.

Dejenerasyonun Geometrik Yorumu

Geometrik bir bakış açısından, dejenerasyon, bir n-boyutlu problemde n'den fazla kısıtlamanın bir köşe noktasında kesişmesiyle ortaya çıkar. İki boyutlu bir LP probleminde, geçerli bölge bir çokgendir ve genellikle her köşe iki kısıtlama ile tanımlanır. Üç veya daha fazla kısıtlama aynı noktada kesiştiğinde, o köşe dejenere olur. Bu durum, optimal çözümlerin varlığı veya benzersizliğini etkilemez, ancak onları bulma yolunu karmaşıklaştırabilir.

Dejenerasyonun Matematiksel Tanımı

Standart formda bir Doğrusal Programlama problemi düşünün:

    Minimize cTx
    Subject to:
    Ax = b
    x ≥ 0

Burada x ∈ ℝⁿ, A ∈ ℝᵐˣⁿ, b ∈ ℝᵐ, ve c ∈ ℝⁿ. Bir temel uygun çözüm dejenere olduğunda, bir veya daha fazla temel değişken sıfırdır. Eşdeğer olarak, dejenerasyon, aktif kısıtlama matrisinin sırasının, bir köşe noktasındaki aktif kısıtlama sayısından daha az olduğu durumdur.

Dejenerasyon Örneği

Bu iki değişkenli doğrusal programlama problemini düşünün:

    Max: z = x₁ + x₂
    Kısıtlayıcı Koşutlar:
    x₁ + x₂ ≤ 2
    x₁ ≥ 1
    x₂ ≥ 1
    2x₁ + 2x₂ = 4

Bu örnekte:

• Geçerli bölge bu kısıtlamalarla sınırlandırılmış ve bir çokgen oluşturmuştur.
• (1, 1) noktasında üç kısıtlama aynı anda aktiftir:
  • x₁ = 1 (x₁ ≥ 1'den)
  • x₂ = 1 (x₂ ≥ 1'den)
  • 2x₁ + 2x₂ = 4 (eşitlik kısıtlamasından)
• İki boyutta bir köşeyi tanımlamak için yalnızca iki kısıtlama gerekli olduğundan, ancak (1, 1) noktasında üç aktif kısıtlama olduğundan, bu nokta dejenere bir noktadır

Simpleks Yöntemine Etkisi

Dejenerasyon, Simpleks yöntemini birkaç şekilde etkiler:

• Sıfır Adımlar: Dejenerasyon meydana geldiğinde,Simpleks yöntemi, hedef değerinde iyileşme sağlamayan bir pivot yapabilir (dejenere pivot).
• Dönme: Nadiren algoritma hedef değerini iyileştirmeden dejenere köşe noktaları arasında dönebilir.
• Birden Fazla Optimal Çözüm: Dejenerasyon, birden fazla optimal çözümün varlığını gösterebilir, ancak bu her zaman geçerli değildir.

Dejenerasyonun Tespiti

Dejenerasyon, birkaç yöntemle tespit edilebilir:

• Temel Değişken Analizi: Mevcut temel uygun çözümde herhangi bir temel değişkenin sıfır olup olmadığını kontrol etme.
• Kısıtlama Analizi: Bir köşe noktasındaki bağlayıcı kısıtlamaların sayısını sayma - eğer bu sayı problemin boyutunu aşarsa, o köşe dejenere bir noktadır.
• Sıra Analizi: Aktif kısıtlama matrisinin sırasının, aktif kısıtlamaların sayısından az olup olmadığını kontrol etme.

Dönme Öncesi Stratejiler

Dejeneratif problemlerde döngüyü önlemek için birkaç strateji vardır:

• Bland Kuralı: Uygun olanlar arasında en küçük indekslere sahip olanları her zaman seçme.
• Bozulma Yöntemleri: Dejenerasyonu ortadan kaldırmak için sağdaki (b vektörü) değerleri hafifçe değiştirme.
• Leksikografik Yöntem: Pivot seçiminde bağlama çözümlemek için hedef fonksiyonların hiyerarşik bir sistemini kullanma.

Pratik Etkiler

Dejenerasyon pratikte yaygın olsa da, modern çözücüler onu etkili bir şekilde yönetir:

• Yüksek doğruluklu pivot seçim kuralları, dönme olasılığını azaltır.
• Birçok dönme öncesi strateji uygulanır.
• Yakın dejenere durumları yönetmek için gelişmiş sayısal yöntemler.
• Bazı dejenerasyon biçimlerini tespit ve ortadan kaldırmak için ön işleme teknikleri.

Sonuç

Dejenerasyon, doğrusal programlamada temel bir kavramdır ve birçok pratik uygulamada doğal olarak ortaya çıkar. Simpleks yöntemi çözüm sürecini karmaşıklaştırabilirken, modern algoritmalar ve yazılım uygulamaları çeşitli teorik ve pratik teknikler ile dejenerasyonu etkili bir şekilde yönetmektedir. Dejenerasyonu anlamak, optimizasyon problemleriyle çalışan uygulayıcılar için kritik öneme sahiptir çünkü sonuçları yorumlamada ve çözüm süreçlerinde sorunları giderme konusunda yardımcı olur.

Tüm Yazılar

Grafik Hesap Makinesi Nedir?  3 boyutlu çizim  Basit Hesap Makineleri Nedir Ve Nerelerde Kullanılır?  Bilimsel Hesap Makinesi Nedir ve Ne İçin Kullanılır?  Hesap Makinesi Tasarımları Ve Çeşitleri  Hesap Makinesinin Tarihten Günümüze Değişimi  İlk Mekanik Hesap Makinesi  Online Bilimsel Hesap Makinesi  Online Standart Basit Hesap Makinesi  Bilimsel Hesap Makinesi Nedir?  Birebir Fonksiyon  Fonksiyon nedir?  Öklid Kimdir?  Önemli Bir İşlemsel Aracımız  Trigonometri - Üçgen Matematiği/Geometrisi  Riemann - Hayatı, Çalışmaları ve Integral Meselesi  Dünyanın En Gelişmiş Hesap Makinesi  İntegral Nedir?  Programlanabilir Hesap Makineleri  Hesap Makinesi Yazılımı Nedir? Nerelerde Kullanılır?  George Dantzig: Doğrusal Programlamanın Babası  Doğrusal Programlamada Dejenerasyon  

id: iesgyzWzgy