Examkin

Soru

Zorluk: Çok zorYapay Değişkenli Yöntemler (Büyük-M ve İki Evreli)

Doğrusal programlama problemlerinin çözümünde kullanılan İki Evreli (Two-Phase) simpleks yönteminin 1. Evre (Phase-I) adımında, yapay değişkenlerin toplamından oluşan amaç fonksiyonu (WW) minimize edilmektedir.

Bir problemin 1. Evre optimum tablosuna ulaşıldığında amaç fonksiyonu değerinin W=0W = 0 olduğu, ancak yapay değişkenlerden biri olan R1R_1'in temel değişkenler arasında ve çözüm değerinin sıfır (00) olarak kaldığı görülmüştür. Bu optimum tablonun R1R_1'e ait satırında, temel olmayan asıl karar ve aylak/artık değişkenlerin katsayıları a1j∗a_{1j}^* ile gösterilmektedir.

Bu durumun teorik yorumu ve 2. Evre'ye (Phase-II) geçiş süreci ile ilgili aşağıdakilerden hangisi kesinlikle doğrudur?

  1. Eğer tüm a1j∗=0a_{1j}^* = 0 ise, bu satır modeldeki kısıtlardan birinin diğerlerine doğrusal bağımlı olduğunu gösterir ve satır tablodan silinerek 2. Evre'ye geçilir; sıfırdan farklı bir a1j∗a_{1j}^* varsa R1R_1 pivot işlemiyle temelden çıkarılır.Cevap
  2. B
    Eğer tüm a1j∗≤0a_{1j}^* \leq 0 ise, problemin uygun çözüm alanı sınırsızdır ve 2. Evre'ye geçilmeden simpleks algoritması sonlandırılarak çözümün sınırsız olduğu rapor edilir.
  3. C
    W=0W = 0 koşulu sağlansa bile R1R_1'in temelde kalması, başlangıç matematiksel modelinde ≥\geq veya == yönlü kısıtların yanlış kurgulandığını gösterir ve modelin düzeltilmesi gerekir.
  4. D
    R1R_1 değişkeni 2. Evre boyunca temel değişken olarak tablodaki yerini korumak zorundadır; ancak asıl amaç fonksiyonuna eklenirken Büyük-M (Big-M) yöntemi kuralları gereği −M-M katsayısı ile cezalandırılmalıdır.
  5. E
    Eğer herhangi bir a1j∗>0a_{1j}^* > 0 ise, problemde uygun çözüm yoktur (infeasible) kararı verilir, çünkü yapay değişkenin temelden çıkabilmesi için tüm katsayıların sıfır olması şarttır.

Cevap

Eğer tüm a1j∗=0a_{1j}^* = 0 ise, satır tablodan silinir (doğrusal bağımlılık); sıfırdan farklı katsayı varsa pivot işlemiyle R1R_1 temelden çıkarılır.
İki Evreli (Two-Phase) yöntemin 1. Evre'si sonunda W=0W=0 değerine ulaşılması, uygun çözümün varlığını kanıtlar. Ancak bir yapay değişken sıfır değeriyle temelde kalmışsa, bu durum incelenmelidir. Eğer bu satırdaki tüm karar ve artık değişken katsayıları sıfırsa (a1j∗=0a_{1j}^*=0), elde edilen denklem 0x1+0x2+...+1R1=00x_1 + 0x_2 + ... + 1R_1 = 0 şeklindedir. Bu denklem 0=00=0 mantığına dönüştüğünden, kısıtın diğer kısıtların doğrusal bir birleşimi (redundant/gereksiz) olduğu anlaşılır ve satır tablodan tamamen silinir. Eğer sıfırdan farklı bir katsayı var ise, basit bir pivot işlemi yapılarak asıl değişken temele sokulur, yapay değişken temelden uzaklaştırılır ve 2. Evre'ye öyle geçilir. Doğru ifade bu durumu eksiksiz açıklamaktadır.

Adım Adım Çözüm

1
1. Evre (Phase-1) sonunda amaç fonksiyonu değeri W = 0 olduğunda temel uygun çözümün varlığını değerlendirmek.
W = 0 olması, yapay değişkenlerin değerlerinin toplamının sıfırlandığını ve orijinal problemin uygun bir çözüm alanına (feasible region) sahip olduğunu kesin olarak kanıtlar.
Yapay değişkenler çözüm alanında olmayan noktaları yapay olarak var etmişti; toplamın sıfırlanması hedefe ulaşıldığını gösterir.
2
Yapay değişkenin (R1R_1) temelde kalması ve değerinin 0 olması durumunun (dejenerelik) analiz edilmesi.
Bu durum, kısıtlardan birinin doğrusal bağımlı (gereksiz) olabileceğine veya o anki köşede yoz (degenerate) bir temel çözümde bulunulduğuna işaret eder.
2. Evre'ye geçerken algoritmanın tıkanmaması için sıfır değerli yapay değişkenlerin temelden tamamen uzaklaştırılması veya zararsız hale getirilmesi gerekir.
3
İlgili satırdaki temel olmayan değişken katsayılarının (a1j∗a_{1j}^*) kontrol edilmesi.
Tüm katsayılar sıfır ise 0=00 = 0 şeklinde etkisiz bir denklem elde edilir; bu kısıt gereksizdir ve satır silinir. Eğer sıfırdan farklı bir katsayı varsa, o değişken anahtar sütun seçilerek normal bir pivot işlemiyle R1R_1 temelden çıkarılır.
Yapay değişkenler asıl problemde varlık göstermediğinden 2. Evre'deki hesaplamaları bozmamaları için bu temizlik matematiksel bir zorunluluktur.

Anahtar Kavram

İki Evreli Yöntemde 1. Evre Sonunda Dejenerelik ve Doğrusal Bağımlılık (Redundancy) Analizi
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Yapay Değişkenli Yöntemler (Büyük-M ve İki Evreli)

Bu konudan daha fazla soru