İŞL404U-SAYISAL KARAR VERME TEKNİKLERİ
Ünite 3: Dualite ve Duyarlılık Analizleri
Giriş
Doğrusal programlamanın en önemli iki konusu dualite ve duyarlılık analizidir. Dualite kavramının ortaya çıkarılması doğrusal programlamanın gelişiminde önemli bir buluş olmuştur. Buraya kadar incelenmiş olan doğrusal programlama problemleri ile ilgili çözüm teknikleri, sadece primal problemlere (yani problemin verilmiş hâli) optimum (en iyi) çözüm aramaktadır. En büyükleme (maksimizasyon) veya en küçükleme (minimizasyon) olarak verilmiş, herhangi bir problem “primal problem” olarak adlandırılır. Bir doğrusal programlama probleminin, primali dışındaki başka bir görünümü “dual problem” olarak adlandırılır. Dual problem ve primal problem arasındaki ilişkilerin birçok yönden yararlı olduğu kanıtlanmıştır. Bunlar; dual çözümün taşıdığı önemli ekonomik anlam (gölge fiyatlar) ile matematiksel özellikler açısından işlem kolaylığıdır. Dualite teorisinin anahtar kullanımlarından biri de “duyarlılık analizinin” yorumlanmasında yatar. Duyarlılık analizi hemen hemen her doğrusal programlama çalışmasının önemli bir kısmını oluşturur. Çünkü asıl modelde bazı parametre değerleri değiştiğinde, onların değişim aralığının ve optimal sonuca etkilerinin araştırılması ve yönetsel kararları temsil eden bazı parametre değerlerinin seçimi ile bunlar üzerindeki çalışmalar duyarlılık analizleri ile yapılabilmektedir.
Dual Problemin Tanımı
Doğrusal programlama teorisine göre formüle edilen her bir problem “primal problem” ve “dual problem” olarak iki biçimde ifade edilmektedir. Doğrusal programlamada maksimizasyon veya en küçükleme olarak karşımıza gelen herhangi bir problem “primal problem” olarak adlandırılmaktadır. Bir problemin primali dışında bir başka görünümü ise “dual problem” olarak adlandırılmaktadır. Formüle edilen bir doğrusal programlama probleminin verileri kullanılarak, dual adı verilen bir diğer doğrusal programlama problemi elde edilebilmektedir. Bu iki problemden hangisinin primal veya hangisinin dual olarak adlandırıldığının bir önemi yoktur. Duali alınan bir doğrusal programlama probleminin, dualinin alınması sonucu problemin primal hali elde edilmiş olur. Doğrusal programlamada dualitenin önemli olmasının üç ana nedeni vardır. Bunlar;
1. Dualite ile primal problemin çözümünü kolaylaşmıştır. 2. Dual modelin değişkenleri ile primal model ile ilgili gölge fiyat gibi önemli ekonomik açıklamalarda bulunma imkânı sağlanmıştır. 3. Ayrıca duyarlılık analizi işlemlerinde önemli katkıları olmuştur. Böylece dualite kavramı doğrusal programlamanın gelişiminde önemli bir buluş olmuştur.
Primal model olarak adlandırılan doğrusal programlama modellerinin değişik bir düzende oluşturulabilmesi ile elde edilen modele dual model adı verilmektedir.
Bir doğrusal programlama modelinde amaç fonksiyonu en büyükleme ve tüm kısıtlayıcılar “≤” yapısında veya amaç fonksiyonu en küçükleme ve tüm kısıtlayıcılar “≥” yapısında ise bu tür problemlere kanonik yapıda denir. Ayrıca karar değişkenlerinin tümünün negatif olmama koşulunu sağlaması gerekir.
Kâr amaçlı kanonik yapılı doğrusal programlama modelinin dualini alma
Kanonik yapıda en büyükleme (maksimizasyon) amaçlı problemin dualini yazarken ortaya çıkan ilişkiler şu şekilde özetlenebilir:
1. Primal modelde amaç en büyükleme olduğunda, onun dual modelinde amaç en küçükleme olur. 2. En büyükleme amaçlı primal modelde tüm kısıtlayıcıların yönü “≤” şeklinde iken dual modelde tüm kısıtlayıcıların yönü “≥” şeklindedir. 3. Primal modelin sağ taraf sabitleri(bi), dual modelin amaç fonksiyonu katsayılarıdır. 4. Primal modelin amaç fonksiyonu katsayıları(cj), dual model kısıtlayıcılarının sağ taraf sabitleridir. 5. Primal modelde “m” adet kısıt, “n” adet karar değişkeni (X1, X2, … Xn) varken dual modelde “n” adet kısıtlayıcı ve m adet dual değişken (y1, y2, … ym) vardır. Bir başka deyişle primal modelin kısıtlayıcı sayısı, dual değişken sayısına eşittir. Benzer şekilde dual modelin kısıtlayıcı sayısı, primal değişken sayısına eşittir. 6. Primal modelin her bir kısıtının sol tarafında yer alan satır katsayıları (ai1,ai2, … ain), dual modelin “yi” değişkenine ait sütun katsayılarını verir. Daha genel olarak primal modelin kısıtlayıcılarının teknik katsayıları, dönüşüme uğrayarak, dual modelin kısıtlayıcılarının teknik katsayılarını oluşturmaktadır. Primal modelin kısıtlayıcı katsayıları A matrisi ile gösterilirse;
Maliyet amaçlı kanonik yapılı doğrusal programlama modelinin dualini alma
Kanonik yapıda en küçükleme amaçlı problemin dualini yazarken ortaya çıkan ilişkiler şu şekilde özetlenebilir:
1. Primal modelde amaç en küçükleme olduğunda, onun dual modelinde amaç en büyükleme olur. 2. En küçükleme amaçlı primal modelde tüm kısıtlayıcıların yönü “≥” şeklinde iken, dual modelde tüm kısıtlayıcıların yönü “≤” şeklindedir. 3. Primal modelin sağ taraf sabitleri(bi), dual modelin amaç fonksiyonu katsayılarıdır. 4. Primal modelin amaç fonksiyonu katsayıları (cj), dual model kısıtlayıcılarının sağ taraf sabitleridir. 5. Primal modelde “m” adet kısıt, “n” adet karar değişkeni (X1, X2, … Xn) varken dual modelde “n” adet kısıtlayıcı ve m adet dual değişken (y1, y2, … ym) vardır. Bir başka deyişle primal modelin kısıtlayıcı sayısı, dual değişken sayısına
eşittir. Benzer şekilde dual modelin kısıtlayıcı sayısı, primal değişken sayısına eşittir. 6. Primal modelin her bir kısıtının sol tarafında yer alan satır katsayıları (ai1, ai2, … ain), dual modelin “yi” değişkenine ait sütun katsayılarını verir. Daha genel olarak primal modelin kısıtlayıcılarının teknik katsayıları, dönüşüme uğrayarak dual modelin kısıtlayıcılarının teknik katsayılarını oluşturmaktadır. 7. Primal ve dual modelde yer alan değişkenler için negatif olmama varsayımı geçerlidir.
Dual Simpleks Yöntemi ve Gölge Fiyat
Simpleks algoritması, doğrusal programlama problemlerinin çözümünde etkin olarak kullanılmaktadır. Bir primal modelin, duali alındıktan sonra dual simpleks yöntemi ile optimum çözümü araştırılır. Dual simpleks yönteminin esası, problemin dualine simpleks yönteminin uygulanmasıdır. İncelenen primal modelin öncelikle duali alınır. Daha sonra bu dual model standartlaştırılır. Standart bu modelin simpleks yöntemi ile çözümü araştırılır. Primal optimum çözüm tablosundan, dual problemin optimal çözüm değerleri bulunabileceği gibi, dual optimal simpleks tablosundan primal problemin optimal çözüm değerleri bulunabilir. Dual simpleks optimum çözüm tablosunda dual değişkenlerin Cj – Zj aldığı değerler, primal modelin aylak değişken değerlerini verir.
Duyarlılık Analizleri
Duyarlılık analizi, bir doğrusal programlama modelinin parametrelerindeki değişmelerin, optimal çözümü nasıl etkilediğini ortaya koymaktadır. Genellikle doğrusal programlama problemlerinin parametre değerleri tam olarak bilinmektedir. Elde edilen çözüm, problemin parametre değerleri sabit olduğu sürece geçerlidir. Ancak karar vericiler, parametre değerlerinde meydana gelen değişimin optimum çözümü nasıl etkilediğini bilmek isterler. Duyarlılık analizi, mevcut problemin optimum çözümüne ulaşıldıktan sonra uygulanmaktadır. Böylece mevcut çözüm değişmeden modelin katsayılarında değişiklik olması halinde optimum çözüme etkili bir şekilde nasıl ulaşılacağı belirlenmektedir.
Duyarlılık analizinde yapılan işlem; problemin optimum çözümü bulunduktan sonra, sağ taraf sabitlerinde (bi) değişme olduğunda, amaç fonksiyonu katsayılarında (cj) değişme olduğunda, modele yeni bir değişken eklenmesi durumunda, modelden bir değişken çıkarılması durumunda, modele yeni bir kısıtlayıcı eklenmesi durumunda ve modelden bir kısıtlayıcı çıkarılması durumunda, optimuma etkili bir şekilde nasıl ulaşılacağını belirlemektir.