Yöneylem Araştırması Dersi 6. Ünite Özet

Giriş

İkillik ya da Latince kökenli adıyla dualite kelimesi, farklı alanlarda değişik anlamlara sahip olsa da, genel olarak karşıtlık ve birbirini tamamlayıcılık özelliklerine işaret etmektedir. Sembolik ol arak (S:117, Şekil 6.1)’da görüldüğü gibi siyah-beyaz bir daireyle gösterilen, Uzakdoğu ve özellikle bir Çin felsefesi olarak tanınan Yin ve Yang, ikillik ilkesini çok iyi anlatır. Bu düşünceye göre, her şeyin birbirinden ayrılamaz iki karşıt kutbu vardır. Kutuplar az da olsa karşıtını mutlaka içerisinde barındırır ve karşıtlar birbirine dönüşebilen yapıdadır.

İkillik konusunun doğrusal programlama ile ilgisi, eniyi çözümü aranan her doğrusal karar probleminin gerçekte “asıl” ve “ikil” olarak adlandırılan, birbiriyle yakından ilişkili iki ayrı modeli içermesinden ileri gelir. Bu modeller, ikilliğin felsefi anlamına da ters düşmeyecek şekilde, birbirinin hem karşıtı sayılabilen hem de birbirine dönüşebilen yapıda olan modellerdir. Bir doğrusal programlama probleminin asıl ve ikil modellerinin çözümleri arasındaki ilişkilerin bilinmesi önemlidir. Asıl problem veya asıl model, eniyi çözümü aranan problemdir. Doğrusal programlama problemleri ile ilgili çözüm teknikleri, asıl modellerin çözümü üzerine yoğunlaşmıştır. İkil model ise, asıl modelin parametreleri kullanılarak oluşturulan ve karşıt yönde amaç fonksiyonuna sahip olan diğer modeldir.

Doğrusal programlamada ikilliğin önemli olmasının başlıca üç ana nedeni bulunmaktadır:

• İkil modelin değişkenlerinden hareketle, asıl problemle ilgili önemli ekonomik açıklamalarda bulunma ve yorum yapma imkanı sağlar.
• Modelin yapısındaki veya parametrelerindeki değişimleri inceleyen duyarlılık analizleri ile ilgili işlemlere katkıda bulunur.
• Bazı durumlarda ikillik, ilgilenilen asıl problemin çözümünü kolaylaştırır.

Doğrusal Karar Modelinin İkili

Verilen bir doğrusal karar modelinin ikil modelini yazma işlemi “ikilini alma” olarak ifade edilir. İkil modelin karar değişkenleri ise “ikil değişkenler” olarak adlandırılır. İkinci üniteden hatırlanacağı gibi, verilen bir doğrusal programlama modeli standart veya kanonik biçime dönüştürülebilmektedir. Kanonik biçimde yazılmış bir doğrusal karar modelinin ikilini almak daha kolaydır. Bu bölümde öncelikle kanonik modelin ikilinin yazılması üzerinde durulmakta, daha sonra kanonik olmayan bir modelin ikilinin nasıl alınacağı açıklanmaktadır.

Kanonik Modelin İkili : Kanonik biçimde, eğer problemin amacı enbüyükleme ise tüm kısıtlar ? tipinde, eğer enküçükleme ise tüm kısıtlar ? şeklinde olur. Ayrıca, karar değişkenlerinin tümünün sıfırdan büyük eşit olma (veya negatif değer almama) koşulunu taşıması gerekir.

İkil modelde y ₁ ,y ₂ ,…,y _m ile gösterilen değişkenler ikil değişkenlerdir.

Sayfa 119’da enküçükleme modelinin ikili örnek ile gösterilmiştir.

Kanonik biçimindeki her iki modelin de farklı yerlerde aynı parametreleri kullandığı görülür. Kanonik biçimli ve enbüyükleme amaçlı bir problemin ikilini yazarken ortaya çıkan durumlar aşağıdaki şekilde özetlenebilir:

• Asıl modelde amaç fonksiyonunun enbüyük değeri aranıyor iken, ikil modelde bunun karşıtı olan enküçük değer araştırılmaktadır.
• Asıl modelde tüm kısıtların yönü ? iken, ikil modelde tüm kısıtların yönü bunun karşıtı olan ? şeklindedir.
• Asıl modelde m adet kısıt varken, ikil modelde m adet karar değişkeni (y ₁ ,y ₂ ,…,y _m ) bulunmaktadır. Bir başka deyişle asılın her kısıtı için bir ikil değişken tanımlanmaktadır.
• Asıl modelde n adet karar değişkeni bulunurken, ikilinde n adet kısıt yer almaktadır. Bir diğer deyişle asılın her değişkeni ikilin bir kısıtına karşı gelmektedir.
• Asıl model kısıtlarının sağ taraf sabitleri (b _i ), ikilin amaç fonksiyonu katsayılarıdır.
• Asıl modelin amaç fonksiyonu katsayıları (c _j ), ikil model kısıtlarının sağ taraf sabitleridir.
• Asıl modelde i. kısıtın sol tarafındaki satır katsayıları (a _i1 , a _i2 , …, a _in ,), ikil modelin yi değişkenine ait sütun katsayıları olmaktadır.
• Hem asıl hem de ikil modelin değişkenleri sıfırdan büyük eşit olarak tanımlanmıştır.

Eğer asıl model kanonik biçimli ve enküçükleme amaçlı ise, bunun ikil modeli, yukarıda sıralanan durumların ilk ikisi dışında kalan özelliklerin tamamını sağlamak zorundadır. Farklı olarak ikil modelin maç fonksiyonu enbüyükleme yönünde ve tüm kısıtları ? biçiminde olmalıdır.

Kanonik biçimdeki doğrusal karar modelinin ikilini kolaylıkla oluşturabilmek için (S:120, Şekil: 6.1 ve 6.2)’den yararlanılabilir.

Genel Modelin İkili, En iyi değerini aradığımız doğrusal karar modeli, her zaman kanonik biçimde olmayabilir. Modelin kısıtları, kullanılan kaynak miktarlarına göre “ ?” , “?” veya “=” tipinde verilebilir. Karar değişkenlerinin bazılarının sıfırdan küçük eşit olması istenirken, bazılarının serbest işaretli olması (-, 0, + işaretli değer alabilen) istenebilir. Kanonik biçimde olmayan bir doğrusal karar modelinin, izleyen iki yoldan birini kullanarak ikilini oluşturmak mümkündür:

1. Uygun işlemlerle karar modelini kanonik biçime dönüştürmek ve ikil modelini yazmak.
2. Dönüştürme işlemini yapmadan, genel kuralları uygulayarak doğrudan ikil modeli yazmak.

Genel bir doğrusal karar modelinin ikilinin yazılmasında gözönüne alınacak ilişkiler (S:122, Tablo 6.5)’te gösterilmektedir. Tablodaki bağıntıları dikkatle incelersek aşağıdaki genel sonuçlara ulaşabiliriz:

• Asıl ve ikil modellerin amaçları karşıt yöndedir. Bir model enbüyükleme amaçlı ise diğeri enküçükleme amaçlıdır.
• Bir modeldeki i. kısıt, diğer modeldeki i. karar değişkenine karşı gelir.
• Bir modeldeki i. kısıtın yönü, diğer modelde bu kısıta karşı gelen i. karar değişkeninin işaretini belirler.
• Eğer bir modelde i. kısıt eşitlik olarak ifade edilmişse, diğer modelin i. karar değişkeni serbest işaretli olur.
• Bir modeldeki kısıtın yönü eğer kanonik biçimde öngörülenin tersi yönündeyse, diğer modelde buna karşı gelen karar değişkeni “ ? 0” olarak tanımlanır.

İkil Değişkenlerin Ekonomik Anlamı

Giriş kısmında, ikil değişkenlerden yararlanarak, asıl problemle ilgili önemli ekonomik yorumlar yapılabileceği ifade edilmişti. Verilen bir doğrusal programlama modelinin ikilinin nasıl elde edileceği örneklerle açıklanarak gösterildi. Artık oluşturulan ikil modelden yararlanarak, asıl problemin ekonomik açıdan nasıl yorumlanabileceği konusunu ele alabiliriz. Konunun daha iyi anlaşılması için, izleyen örnek problem üzerinden gidilecektir. Doğrusal programlama modelleri, genellikle sınırlı kaynak kullanımı kısıtları altında gelir ya da karın enbüyüklenmesi amacına yönelik olarak geliştirilen, bir kaynak dağıtım modeli gibi düşünülebilir. Örnek problemde de, karı enbüyükleyen üretim miktarlarının bulunması istenmektedir (S:124 , Örnek 6.4).

Asıl ve İkil Modellerin Çözümleri Arasındaki İlişkiler

Asıl ve ikil modellerin çözümleri arasındaki İlişkiler :Asıl ve ikil problemlerin çözümleri arasındaki ilişkiler üç ana özelliğe bağlı olarak açıklanabilir. Bunlar, her iki problemin uygun çözümleri arasındaki ilişkiyi tanımlayan “zayıf ikillik özelliği”, her iki modelin de eniyi değerlerinin eşit olduğunu belirten “güçlü ikillik özelliği” ve eniyi çözümleri ilişkilendiren “aylaklığın tamamlayanı özelliği” olarak adlandırılmaktadır.

Zayıf ikillik özelliğine göre, asıl ve ikil problemlerin her ikisi de uygun çözümlü olduğunda, bu modellerin herhangi uygun çözümlerine karşı gelen amaç fonksiyonu değerleri arasında daima,

ilişkisi sağlanır.

Bir doğrusal programlama problemi için geliştirilen asıl ve ikil modellerden birisi enbüyükleme amaçlı ise diğeri enküçükleme amaçlı olacaktır. Bu ilişki için, hangisinin asıl hangisinin ikil problem olduğu değil, eniyilemenin yönü önemlidir. Zayıf ikillik özelliğinden yararlanarak, asıl veya ikil problemlerden birisinin uygun bir çözümüne karşı gelen amaç fonksiyonu değerini, diğer problemin eniyi değeri için alt veya üst sınır olarak kullanabiliriz.

Güçlü ikillik özelliğine göre, asıl veya ikil problemden herhangi birisi sınırlı değerde bir eniyi çözüme sahipse, diğerinin de mutlaka bir eniyi çözümü vardır ve her iki problemin eniyi değerleri birbirine eşittir. Bir başka deyişle, asıl ve ikil problemlerin bir eniyi değeri varsa, bu değerler arasında daima,

ilişkisi sağlanır. Bu özellikten yararlanarak, asıl veya ikil modellerden herhangi birinin eniyi değerini biliyorsak diğer modelin eniyi değerinin de buna eşit olacağını söyleyebiliriz. Zayıf ve güçlü ikillik özellikleri ile ifade edilen ilişkiler (S:128, Şekil 6.2)’de gösterilmektedir.

İkillik teoremi: Zayıf ve güçlü ikillik özelliklerinden hareketle, bir doğrusal programlama problemi için geliştirilen asıl ve ikil modellerin çözümleri ile ilgili, aşağıdaki durumlardan sadece birisi söz konusu olur:

1. Asıl ve ikil modellerden her ikisinin sınırlı değerde eniyi çözümü vardır ve eniyi değerler birbirine eşittir.
2. Asıl modelin uygun bir çözümü olup amaç fonksiyonu değeri sınırsız olduğunda, ikil modelin uygun çözümü yoktur.
3. İkil modelin uygun bir çözümü olup amaç fonksiyonu değeri sınırsız olduğunda, asıl modelin uygun çözümü yoktur.
4. Hem asıl hem de ikil modelin uygun bir çözümü yoktur.

Karşılaştırabilir durumlar S:128, Tablo 6.8’de özetlenmektedir.

Aylaklığın tamamlayanı (complementary slackness), ikillik üzerine geliştirilen kavram ve teknikleri bütünleştirerek, asıl ve ikil problemlerin eniyi çözümlerini ilişkilendiren önemli bir özelliktir. Bir kısıta ait “boşluk değişkeni” ve “sıkı kısıt” terimlerinin tanımlanması, bu özelliğin daha kolay anlaşılmasını sağlayacaktır. Boşluk değişkeni, eniyi çözümde kısıtın eşitsizliğin sol tarafındaki değeri ile sağ taraf sabiti arasındaki farkı veren değişkendir. Eğer kısıt “?” türünde ise boşluk değişkeni “aylak değişken”, kısıt “?” türünde ise boşluk değişkeni “artık değişken “ olarak adlandırılır. Eğer eniyi çözümde, bir kısıta ait boşluk değişkeni sıfıra eşitse, o kısıt tam eşitlik halinde gerçekleştiği için o kısıtın “sıkı kısıt” olduğu söylenir.

İkil Problemin Çözümünün Asıl Simpleks Tablosundan Elde Edilmesi

Asıl modelin son simpleks tablosu veya eniyi çözümünü gösteren simpleks tablosu verilmişse, ikil değişkenlerin değerini bu tablodan okumak mümkündür. Son simpleks tablosunda, başlangıç temel uygun çözüme karşı gelen değişkenlerin indirgenmiş maliyetlerinden, ikil değişkenlerin değeri bulunabilir. İndirgenmiş maliyetler, simpleks tablosunun amaç fonksiyonu (z) satırı veya sıfır satırı olarak adlandırılan satırında yer alan sayısal değerlerdir.

Başlangıç simpleks tablosunun ve genel olarak bir ardıştırmadaki simpleks tablosunun şematik gösterimi S:131, Tablo 6.10 ve S:132, Tablo 6.11’ de görülmektedir. Başlangıç tabloda, başlangıç temel değişkenlerin z satırındaki katsayıları sıfıra eşit olup, temel değişkenlere karşı gelen sütunlardaki katsayıları birim matris oluşturmaktadır. İzleyen ardıştırmalarda ise, başlangıç temel değişkenlerin z satırındaki katsayıları sıfırdan küçük, sıfır veya sıfırdan büyük değer alabilir.

Asıl modelin, son simpleks tablosunun z satırından, başlangıç temel değişkenlere karşı gelen indirgenmiş maliyetler bulunur ve izleyen eşitlik kullanılarak ikil değişkenlerin eniyi değeri hesaplanır:

Eniyi y _i = [i. asıl kısıttaki başlangıç temel değişkene karşı gelen indirgenmiş maliyet] + [ Başlangıç temel değişkenin orijinal modeldeki amaç fonksiyonu katsayısı]

Eğer asıl modelin kısıtlarına eklenen aylak ve artık değişkenleri biliyorsak, son simpleks tablosundan ikil değişkenleri bulmak için, izleyen yöntemi de kullanabiliriz. Aylak ve artık değişkenlerin amaç fonksiyonu katsayıları sıfır olduğundan, asıl modelin,

• i.kısıtında aylak değişken varsa, y _i = aylak değişkenin son tablodaki indirgenmiş maliyeti
• k. kısıtında artık değişken varsa, y _k = - (artık değişkenin son tablodaki indirgenmiş maliyeti) olarak elde edilir.

İkil Problemi Kullanarak Asıl Problemin Çözülmesi

Bazı durumlarda bir doğrusal programlama probleminin asıl modelini çözmek yerine ikil modelini çözmek, işlem yükü açısından daha kolay olabilir. Eğer problemin asıl modelini çözmek için simpleks ardıştırmalarını uygulamak gerekirken, ikil modelin çözümünü grafik yöntemle bulabileceksek, hesaplama kolaylığı açısından ikil modelin çözümü ile uğraşmak bize zaman kazandıracaktır. Daha sonra asıl - ikil modellerin çözümleri arasındaki ilişkileri veren ikillik teoremi ve aylaklığın tamamlayanı özelliklerini kullanarak asıl modelin çözümünü bulabiliriz. Grafik yöntemle çözüm S:134, Şekil 6.3’te görülmektedir.

Gölge Fiyatlar

Doğrusal programlama modellerinde, kaynaklardaki değişimlerin problemin eniyi değerinde ne kadar bir farklılığa sebep olacağının belirlenmesi, yöneticiler için önemlidir. Fayda - maliyet analizi yapmakta kullanılan gölge fiyatlar, herhangi bir üretim kaynağının miktarının bir birim arttırılması veya azaltılması durumunda amaç fonksiyonu değerinde meydana gelecek artış veya azalış olarak tanımlanır.

İkil değişkenlerin, asıl modelin kısıtlarına karşı geldiğini ve kaynakların birim değerlerini gösterdiğini biliyoruz. Asılın i. kısıtına karşı gelen ikil değişkeni y _i olarak adlandırdığımızda, y _i , i. kısıtla ifade edilen kaynağın 1 biriminin değerini ya da fiyatını vermektedir.

Gölge fiyat amaç fonksiyonundaki değişimi veriyorsa, bir asıl problemin i. kısıtının sağ taraf sabitindeki ? _i kadar değişimi, asıl modelin amaç fonksiyonunda yapacağı farklılığı gölge fiyatlar yardımıyla,

Yeni z değeri=Eski z değeri+? _i (i. kısıtın gölge fiyatı)

eşitliği ile tanımlanabilir. ? _i ,i. kısıtın yeni değeri ile eski değeri arasındaki farktır. Eğer mevcut miktardan artış olursa ? _i < 0, eğer mevcut miktardan artış olursa ? _i > 0 olacaktır.