Dogrusal Programlama-Simplex Yönteminde Ozel Durumlar ve Dualite
Yayinlanma Zamani: 2011-02-09 19:27:00
Doğrusal Programlama - SIMPLEKS YÖNTEMİNDE ÖZEL DURUMLAR VE DUALİTE
SIMPLEKS YÖNTEMİNDE ÖZEL DURUMLAR
1. Alternatif Çözümler
2. Sınırsız DP
Alternatif Optimal Çözümler :
DP’nin birden fazla optimal çözümü olması durumudur.
Genellikle eşdeğer doğrusunun sınırlayıcı kısıtlardan birine ait doğru parçası ile kesişmesi sonucu meydana gelir.
Zmaks= 8X1+ 5X2
Simpleks tabloda alternatif çözüm durumu Cj-Zjsatırı ve temel sütun araştırılarak anlaşılabilir.Eğer çözümde olmayan bir değişkenin Cj-Zjdeğeri 0 ise, alternatif optimal çözümler vardır.
Zmaks= 8X1+ 5X2 + 0S1+0 S2
8/5X1+ X2 + S1 = 8
X1+ 5/4X2 + S2 = 6
X1, X2 ,S1, S2 ≥0
Başlangıç Simpleks Tablo
İkinci Simpleks Tablo ve Üçüncü Simpleks Tablo :
Sınırsız Çözüm Alanı
Kimi DP problemlerinde, amaç fonksiyonu maksimizasyon ise amaç fonksiyonu değerinin sonsuza dek arttırılması, minimizasyon problemi ise eksi sonsuza dek azaltılması mümkündür. Bu tip problemlerde uygun çözüm alanı da, amaç fonksiyonu değeri de sınırsızdır.
Sınırsız çözüm yalnız bir şeyi ifade eder: Model yanlış kurulmuştur. Bunun sebebi varsayımların doğru kurulmaması, kimi kısıtların eksikliği veya model parametrelerinin yanlış tahminlenmesi olabilir(Taha, 1997 pp.103-104).
Zmax= X1 + 2X2
X1 + X2 ≥1
Sınırsız çözüm simpleks tabloda, çözümden çıkacak değişken belirlenirken farkedilebilir.
İkinci Simpleks Tablo ve Üçüncü Simpleks Tablo:
Yukarıdaki tabloda görüleceği gibi, optimal çözüme ulaşılmamış olmasına rağmen, çözümden çıkacak değişkeni belirlemek mümkün değildir. Sağ taraf testinde tüm değerler tanımsız veya <0 olduğu için problem sınırsızdır.
DP problemlerinde çözümsüzlük uygun çözüm alanının bulunmaması sonucu oluşur.
Genellikle problemin doğru modellenmemesi sonucu meydana gelir.
Zmaks=3X1 + 2X2
2X1 + X2 ≤2
3X1 + 4X2 ≥12
X1 , X2 ≥0
Çözümsüzlüğün amaç fonksiyonu ile ilgisi yoktur ve simpleks tablo üzerinde temel değişkenler sütunu kontrol edilerek anlaşılabilir. Optimal simpleks tabloda eğer bir yapay değişkenin değeri sıfırdan farklı ise, problem çözümsüzdür.
Zmax= 3X1+ 2X2+ 0S1 +0E1 -MA1
2X1+ X2+ S1 =2
3X1+ 4X2 -E1 + A1 =12
X1, X2 ,E1, A1 , S1≥0
Çözümsüzlük durumu, genellikle birbiri ile çelişen kısıtların varlığında oluşur.
Simpleks çözüm tekniği uygulanırken optimal çözümde temelde yeraland eğişkenlerden en az birinin değerinin 0 olması sonucu ortaya çıkar.
Genellikle gereksiz bir kısıtın modelde bulunması sonucu meydana gelir.
Zmaks= 3X1+ 9X2
Simpleks yöntemi uygulanırken çözümden çıkacak değişkenin seçiminde minimum oran kuralında eşitlik olabilir. Birden fazla aynı minimum orana sahip değer varsa çıkan değişken, bu eşit oranlardan birinin rasgele seçilmesiyle belirlenir.
Problemde böyle bir durum gerçekleştiğinde bir sonraki iterasyonda bir yada birden fazla taban değişken sıfır değerini alarak tabloda kalacaktır. Bu yeni çözümede jenere çözüm adı verilmektedir. Modelin çözümünün bu şekilde çıkması çok önemli değildir. Kısıtlardan en az birinin fazla olduğu yorumu yapılabilir.
Bozulma hali bazan bir dalgalanma durumuna yol açtığından optimal çözüme ulaşılamaz ve tekrarlamalar olabilir
Zmaks= 3X1+ 9X2 + 0S1+0 S2
X1+ 4X2 + S1 = 8
Başlangıç Simpleks Tablo:
İkinci Simpleks Tablo:
Çözümde olan:x2=2, S2=0
Çözümde olmayan: x1=S1=0
Üçüncü Simpleks Tablo:
Çözümde olan:x2=2, x1=0
Çözümde olmayan: S2=S1=0Z=18
Herhangi bir DP ile ilişkisi olan bir diğer DP dual (eşters) olarak isimlendirilir. Dual bilgisi ekonomik ve duyarlılık analizi ile ilgili ilginç açıklamalar sağlar. Duali alınan DP primal olarak isimlendirilir. Primal model en büyükleme sorunu ise dual en küçükleme sorunu olur. Bu kuralın tam terside doğrudur.
Bir DP’nin Dualini Bulma
Normal en büyükleme probleminin duali normal en küçükleme problemidir.
Normal enbüyüklemeproblemi tümdeğişkenlerin0 veya0’danbüyükolduğuvetümkısıtların≤ olduğubirproblemdir.
Normal en küçükleme problemi tüm değişkenlerin 0 veya 0’dan büyük olduğuve tüm kısıtların ≥ olduğu bir problemdir.
Benzer şekilde, normal en küçükleme probleminin dualide normal en büyükleme problemidir
Normal En büyükleme Probleminin Dualini Bulma
Normal En küçükleme Probleminin Dualini Bulma
Normal Olmayan En büyükleme Probleminin Dualini Bulma :
Eğeri. primal kısıt> kısıtsa, ilgilidual değişkenyi< 0 şeklinde olmalıdır.
Eğeri. primal kısıt eşitlikse, ilgili dual değişken yi “serbest" (unrestricted in sign -urs) değişkendir.
Eğeri. primal değişken serbest ise, i. dual kısıt eşitliktir.
Eğeri. primal kısıt ≤ kısıtsa, ilgili dual değişken xi ≤ 0 şeklinde olmalıdır
Eğeri. primal kısıt eşitlikse, ilgili dual değişken xi “serbest" (urs) değişkendir.
Eğeri. primal değişken serbest ise, i. dual kısıt eşitliktir
Zmaks= 4x1+ 6x2
x1serbest, x2≥ 0
Zmin=2y1+ 5y2 + 8y3
y1 –y3≥ 4
2y1+ 4y3= 160
Primal ve dualin en iyi amaç fonksiyon değerleri eşittir.
Primal normal en büyükleme sorunu olduğunda, dual değişkenler karar vericiye sağlanabilecek kaynakların değeri ile ilgili olur. Bu yüzden dual değişkenlerden çoğu kez kaynak gölge fiyatları olarak söz edilir
30x1+ 20x2≤ 300 (Tahta kısıtı)
5x1+ 10x2≤ 110 (Montajkısıtı)
Wmin= 300y1+ 110y2
30y1+ 5y2≥ 6 (Sırakısıtı)
20y1+ 10y2≥ 8 (Masa kısıtı)
Yoneylem Arastirmasi - Lineer Programlama