» 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
3. Çözümsüzlük
4. Dejenerasyon

 

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
8/5X1+ X2≤8
X1+ 5/4X2≤6
X1, X2≥0
 

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
X2 ≤4
X1, X2 ≥0

Sınırsız çözüm simpleks tabloda, çözümden çıkacak değişken belirlenirken farkedilebilir.
Başlangıç Simpleks Tablo

İ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.

Çözümsüzlük

  • 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
Başlangıç Simpleks:

İkinci tablo:

Çözümsüzlük durumu, genellikle birbiri ile çelişen kısıtların varlığında oluşur.

Dejenerasyon (Bozulma)

  • 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
X1+ 4X2≤8
X1+ 2X2≤4
X1, X2≥0

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

 

Standart form:
Zmaks= 3X1+ 9X2 + 0S1+0 S2
X1+ 4X2 + S1 = 8
X1 + 2X2 + S2 = 4
X1, X2 ,S1, S2 ≥0

Başlangıç Simpleks Tablo:

İkinci Simpleks Tablo:

Çözümde olan:x2=2, S2=0
Çözümde olmayan: x1=S1=0
Z=18

Üçüncü Simpleks Tablo:

Çözümde olan:x2=2, x1=0
Çözümde olmayan: S2=S1=0Z=18

DUALİTE

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.

 

Normal En küçükleme Probleminin Dualini Bulma

  • 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

Örnek

  • Zmaks= 4x1+ 6x2

2x1+ 4x2=100
4x1–x2≥ 120
3x1+x2≤300
x1serbest, x2≥ 0

  • Zmin=2y1+ 5y2 + 8y3

y1+2y2+y3≥ 8
y1 –y3≥ 4
2y1+ 4y3= 160
2y1+y2≤ 40

Ekonomik Yorum

  • 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

Örnek
Zmaks= 6x1+8x2
30x1+ 20x2≤ 300 (Tahta kısıtı)
5x1+ 10x2≤ 110 (Montajkısıtı)
x1,x2≥ 0
Wmin= 300y1+ 110y2
30y1+ 5y2≥ 6 (Sırakısıtı)
20y1+ 10y2≥ 8 (Masa kısıtı)
y1,y2≥ 0

Çözüm

Sonraki Konu

Yoneylem Arastirmasi - Lineer Programlama

 


Duyuru

Facebook sayfamiza üye olun


Duyuru
Sitemizde güncelleme çalismalari devam etmektedir.
Görüs ve önerilerinizi bizimle paylasabilirsiniz ! mail adresimiz : endustrimuhendisligi@hotmail.com