İŞL404U-SAYISAL KARAR VERME TEKNİKLERİ
Ünite 2: Simpleks Yöntemi
Grafik Çözüm Üzerinden Simpleks Yönetiminin Açıklanması
Doğrusal programlama kavramı ve simpleks adıyla bilinen çözüm yöntemi George Dantzig tarafından bulunmuştur. Bilgi-işlem teknolojilerindeki gelişmelerin katkısıyla, Dantzig’in A.B.D. Hava Kuvvetleri için geliştirdiği planlama yöntemi, karmaşık yapıdaki karar problemlerinin çözümünde taşıdığı potansiyel nedeniyle büyük etki yaratmıştır. Dantzig’in geliştirdiği bu yapı, kendine ait bir ifadeyle kısaca şöyle açıklanabilir:
“Doğrusal programlama, uygulamanın yüksek düzeyde karmaşa içeren durumlarıyla karşılaşıldığında insanlığa kapsayıcı hedefler belirleme ve bu hedeflerde en iyiye ulaşmak için ayrıntılı kararlar alacak yolu belirleme kabiliyeti veren büyük devrimsel gelişmenin bir parçası olarak görülebilir. Bunu gerçekleştirmede kullandığımız araçlar, gerçek hayata dair problemlerin ayrıntılı matematiksel terimlerle açık ve net bir biçimde ortaya konması (modeller), bu modellerin çözümünde kullanılan yöntemler (çözüm yolları), ve çözüm yollarına ait aşamaların yürütülmesinde kullanılan makinelerdir (bilgisayarlar ve yazılımlar).”
Bir doğrusal programlama modelinde en iyi çözüm, uygun çözüm alanına ait köşelerden birindedir. Çözüme ilişkin tüm yöntemler bu geometrik yaklaşımı dikkate alır.
Grafik üzerinde çözüm yönteminde olduğu gibi, simpleks yönteminin ilk adımı probleme ait doğrusal modelin bir denklemler sistemine çevrilmesidir. Bu denklemler sisteminde problemin kısıtlayıcıları, fonksiyonlardan dönüştürülmüş denklemler olarak yer almaktadır. Buna göre uygun çözüm uzayı, m sayıda doğrusal eşitlik ve n sayıda değişken vasıtasıyla ifade edilmektedir. Eğer ele alınan sistemin değişkenleri ve doğrusal eşitlikleri sayı olarak birbirine eşit ise, sistemin yalnızca bir çözümü vardır. Fakat çoğu doğrusal programda değişken sayısı denklem sayısından fazladır (n > m). Bu durum, bir çözüm uzayı ile ifade edilen sonsuz sayıda çözümün olmasına yol açar. Bir temel çözüm, burada belirtilen çözüm uzayına ait köşelerden birinde yer alır. Bir temel çözümün, model kısıtlarına uygun olup olmaması çözüm uzayına ait bir köşede yer almasını engellemez. Bir denklemler sistemine ait köşe noktaları, n - m sayıda değişkene sıfır değeri verilerek, geri kalan m sayıdaki değişken için denklemlerin çözülmesiyle elde edilir.
Cebirsel çözüm yönteminden anlaşılacağı üzere, denklem sayısı m ve değişken sayısı n arttıkça cebirsel işlem ihtiyacı katlanarak artmaktadır. Simpleks yöntemi, daha iyi amaç fonksiyonu değerlerine ulaşacak şekilde uç noktaların izini süren bir yordam kullanarak, cebirsel yöntemle harcanacak çabayı azaltır. Bu yöntemde, amaç fonksiyonu değerini artıran yönde olmayan temel çözümlerin hesaplamasına gerek duyulmamaktadır. Simpleks yöntemi bir uç nokta çözümünde başlatılır. Sonrasında uç noktaya ait çözümün en iyi çözüm olup olmadığı sınanır. Eğer en iyi çözüm değilse, başlangıç uç
noktasının komşuluğunda olan daha iyi bir uç nokta çözümüne geçilir ve tekrardan, geçilen noktanın en iyi çözüm olup olmadığı sınanır. Yöntemin bu ardışık (veya yinelemeli) yapısını gösteren süreç şeması sayfa 34’te Şekil 2.2’de verilmiştir.
Ardıştırma, bir önceki işlemin çıktısının sonraki adımda yeniden işleme sokulduğu tekrarlı bir matematiksel işlemdir. Ardışık bir yordam, sonuca ulaşmak için her yinelemede hedefe daha yakın bir değer elde etmeyi amaçlar.
Grafik çözümler ile cebirsel çözümü karşılaştırdığımızda aşağıdaki özellikleri sıralayabiliriz.
Grafik Çözüm Yöntemi
• Kısıtlayıcılar çizilir ve uygun çözüm alanı belirlenir. • Uygun çözüm alanının köşe noktaları, yani uç noktalar belirlenir. Bunlardan birinin en iyi çözümü vermesi beklenmektedir. • Amaç fonksiyonundan faydalanarak Eş-kâr (veya Eş-maliyet) doğruları çizilerek en iyi amaç fonksiyonu değerine sahip uç nokta en iyi çözümü verir.
Cebirsel Çözüm Yöntemi
• Problem, m sayıda denklem ve n sayıda negatif olmayan değişken ile oluşturulmuş bir denklemler sistemiyle ifade edilir. • Temel ve temel dışı değişken kombinasyonları, denklemler sistemi üzerinden çözülür. Bunlardan birinin en iyi çözüm olması beklenmektedir. • Elde edilen temel ve temel dışı değişkenlerin amaç fonksiyonu değerleri hesaplanır. En iyi değere sahip çözüm en iyi çözümdür.
En iyi uç nokta çözümünün izine sürme mantığı Model 1.1 için sayfa 34’te verilen Tablo 2.3 ve sayfa 35’te verilen Şekil 2.3 yardımıyla örneklendirilmiştir. Bu örnekteki anlatım yalnızca uç noktaları değil, aynı zamanda bunlarla aynı hizada olan bir takım diğer noktaları da ele aldığı için, yalnızca simpleks yönteminin grafik üzerinden bir açıklaması değildir. Örnekte dikkat çekilmek istenenler, uç noktaların hesaplanmasının yeterli olduğu ve simpleks yönteminin, cebirsel yöntemdeki gibi her bir uç noktayı hesaplamaya gerek duymadığıdır.
Orijinde yer alan A uç noktasından başlayarak, diğer bir uç noktası olan D’ye giden yol üzerindeki noktalara ait Z değerleri artmakta, sınır çizgisi üzerindeki D noktasında ise en yüksek düzeye ulaşmaktadır.
Benzer durum uç noktası D’den, diğer bir uç noktası I ‘ya giden doğru üzerindeki noktalar için de geçerlidir. Aynısı uç noktası I’dan uç noktası N’ye giden noktalar için de gözlenmektedir. Buradan, yalnızca uç noktalara ait Z değerlerini hesaplamanın yeterli olacağı çıkarımı yapılabilir. Cebirsel yöntem A’dan başlayarak diğer uç noktalar olan D, I ve N’yi de hesaplar. Simpleks yöntemi
ise, A noktasından başladığında, N noktasında işlemi sonlandırır.
Simpleks yönetiminin cebirsel işlemlerine geçmeden önce, bu yöntemin çözümündeki anahtar kavramlar aşağıda özetlenmiştir:
• Yöntem yalnızca uç nokta çözümlere yani bu noktalara karşılık gelen temel uygun çözümlere odaklanır. • Kullanılan yordam ardışıktır ve kitabın 34. sayfasında bulunan Şekil 2.2.’deki ardıştırmayı içerir. • Başlangıç için tercih edilecek çözüm, tüm karar değişkenlerinin sıfır değerini aldığı ve dolayısıyla orijinde bulunan uç noktasına karşılık gelen temel uygun çözümdür. • En iyilik sınamasında bir temel uygun çözümden, onun komşuluğunda olan diğer bir temel uygun çözüme geçilecektir. • Komşu temel uygun çözümler arasındaki seçimde, Z değerindeki iyileşme temel alınır. • Eğer komşu temel uygun çözümler arasından hiçbiri Z’yi iyileştirmiyorsa, eldeki temel uygun çözüm en iyi çözümü vermektedir.
Burada açıklanan çözüme ilişkin anahtar kavramlara ve sayfa 34’te verilen Şekil 2.2’deki süreç şemasına göre, yukarıda verilen örneğin simpleks yöntemi ile çözümü şu şekildedir:
Başlangıç adımı: İlk temel uygun çözüm olarak uç noktası A (0, 0) seçilir.
En iyilik sınaması: A noktasından her iki komşu uç noktaya doğru gidildiğinde Z değeri iyileştiği için, A noktası en iyi çözümü vermemektedir. Hatırlanacağı üzere, modelde amaç fonksiyonun en büyüklenmesi istenmektedir. Bu sebeple, Z değerinin iyileşmesiyle kastedilen Z değerinin artmasıdır.
Ardıştırma: A noktasından N noktasına geçmek, D noktasına geçmeye kıyasla Z’yi daha çok iyileştirir. Diğer bir ifadeyle, x2’nin değerini sıfırda sabit tutmak ve x1 değerini artırmak, x1’in değerini sıfırda sabit tutmak ve x1 değerini artırmak seçeneğine kıyasla Z değerini daha çok iyileştirir. Bunun sebebi, en büyüklenmesi istenen amaç fonksiyonunda x1’in x2’den daha büyük bir katsayıya sahip olmasıdır. Sonuç olarak, en iyilik sınamasına girecek olan, uç noktası N’ye karşılık gelen temel uygun çözümdür.
En iyilik sınaması: Uç noktası N’nin komşuluğundaki uç noktalara (A ve I) karşılık gelen temel uygun çözümlerin hiçbiri Z değerini daha iyileştirmemektedir.
Dur: Uç noktası N’ye karşılık gelen temel uygun çözüm Model 1.1 için en iyi çözümü vermektedir.
Çözüme ilişkin bu açıklamadan sonra kitabın 35. sayfasında Şekil 2.3’ten tekrar gözden geçirilir ise uç
noktaların tümünü hesaplamaktansa simpleks yönteminin daha pratik olduğu görülecektir.
Simpleks Yönetiminin Cebirsel Çözümü
Bu başlık altında, simpleks yönteminin en iyi çözüme cebirsel olarak nasıl ulaştığı açıklanacaktır. Buradan itibaren, temel uygun çözümler, kitabın 34. sayfasında verilen Tablo 2.4’ün üçüncü sütununda sunulduğu şekliyle, tüm değişkenleri içerecek şekilde gösterilmektedir. Tabloyu incelerken temel dışı değişkenlere en baştan sıfır değerinin atandığını hatırlayınız.
İki temel uygun çözümün komşuluk koşulu, sahip oldukları değişkenler arasından yalnızca bir tanesinin aynı olmasıdır. Temel değişkenler ile temel dışı değişkenlerin birbiriyle yer değiştirmek dışında bir değişme imkânı olmadığı için, iki komşu temel uygun çözüme ait temel dışı değişkenler, biri hariç birbiriyle aynıdır. Aynı sebeple, bu iki temel uygun çözümün temel değişkenleri de, biri hariç biriyle aynı olacaktır.
Simpleks Yönetiminin Tablo Çözümü
Önceki başlıkta simpleks yöntemi ardındaki mantığın cebirsel işlemlerle gösterimine odaklanılmıştır. Yöntem bir kez kavrandığında tek yapılması gereken, ardışık çözüm işlemlerinin gerçekleştirilmesidir.
Fakat her ardıştırmada, denklemler sistemini olduğu gibi yeniden yazarak hesaplamak oldukça uğraştırıcıdır. Yazma uğraşını azaltmak için, denklemler sistemi, yalnızca özü içerecek bir tabloya dönüştürülerek çözülür.
Simpleks Tablolarında Alternatif Çözüm Yöntemleri
Simpleks yönteminin çeşitli çözümleri esas olarak aynı mantıksal temelde işlemektedir. Mantıksal işleyişin aynılığı şimdiye kadar açıklanan cebirsel çözüm ve tablo çözümü örneklerinde açıkça görülebilir. Bunun yanında, simpleks yöntemini uygulayan alternatif tablo çözüm yolları da kullanılmaktadır. Bahsedilen türde alternatif bir çözüm yolu tablo, sunumu ve tablo işlemleri açısından farklılaşabilmektedir.