YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 3: Doğrusal Programlama (DP) Problemleri için Çözüm Yöntemi Simpleks Yöntem
Giriş
Bu bölümde, keyfi sayıda kısıt ve karar değişkeni ile modellenen doğrusal programlama problemlerinin en iyi çözümlerini bulmak için, 1947 yılında G. Dantzig tarafından geliştirilen ve “Simpleks Yöntem” olarak adlandırılan yöntemi öğreneceğiz.
Simpleks Yöntemin Cebirsel Yorumu
İlk olarak bir DP probleminin, en iyi çözümünün kolaylıkla bulunmasına olanak sağlayan kanonik şekli ile başlayalım.
Doğrusal Programlama Probleminin Kanonik Şekli ve Cebirsel Eniyilik Kriteri
Şimdi aşağıdaki örneği ele alalım:
ÖRNEK 3.2. Aşağıdaki problemin neden kanonik şekilde olduğunu, temel değişkenlerini, temel dışı değişkenlerini açıklayınız ve bu değişkenlerin aldıkları değerleri bularak bunların bir temel uygun çözüm oluşturduğunu gösteriniz. Bulduğunuz temel uygun çözümün optimallik kriterini sağlayıp sağlamadığını araştırınız.
x1 - 2x2 + x4 = 5,
-x2 + x3 + x4 = 3,
xj ≥ 0, j = 1,2,3,4
kısıtları altında
Enb z = 0x1 - 2x2 + 0x3 - 3x4.
Çözüm: Bir DP probleminin kanonik şekilde olabilmesinin koşullarını hatırlayacak olursak, bu problemde tüm karar değişkenleri negatif olamayacak şekilde kısıtlandığını; iki fonksiyonel kısıdın da eşitlik şeklinde formüle edildiğini; sağ taraf sabitlerinin ikisinin de negatif olmadığını; birinci ve ikinci fonksiyonel kısıtlarda +1 katsayıya sahip x1 ve x3 karar değişkenlerinin diğer kısıtlarda ve amaç fonksiyonundaki katsayılarının sıfıra eşit olduğunu kolayca saptayabiliriz. Burada şöyle bir analiz de yapabiliriz: aslında x4 karar değişkeninin de her bir fonksiyonel kısıttaki katsayısı +1’e eşittir, fakat bu değişkenin amaç fonksiyonundaki katsayısı sıfır olmadığından, temel değişkenlerimiz kesinlikle x1 ve x3 olup, diğer değişkenler x2 ve x4 temel dışı değişkenlerdir. Kurala göre temel değişkenlerin değerleri sağ taraf sabitlerine, temel dışı değişkenler ise sıfıra eşitlenerek temel uygun çözüm bulunabilir: x1 = 5, x2 = 0, x3 = 3, x4 = 0. Optimallik kriterine göre bir temel uygun çözümün en iyi çözüm olabilmesi için;
“Kanonik şekilde tanımlanmış bir en büyükleme probleminin temel dışı değişkenlerinin tamamının amaç fonksiyonundaki katsayılarının işaretlerinin negatif olması durumunda, bu problemin temel uygun çözümü, uygun çözüm alanında amaç fonksiyonuna en büyük değeri sağlayan uygun çözüm, dolayısıyla de bu problemin en iyi çözümüdür.”
Bizim problemin temel dışı değişkenleri olan x2 ve x4 değişkenlerinin amaç fonksiyonundaki katsayıları negatif
işarete sahip olduğundan, en iyilik kriteri sağlanıyor, dolayısıyla bulmuş olduğumuz temel uygun çözümün, bu problemin en iyi çözümü olduğunu kesinlikle söyleyebiliriz.
Pivot ve En Küçük Oran Kriteri: Eğer kanonik şekildeki bir problemde bir xt değişkeninin temele alınması ile mevcut uygun çözümün iyileştirilmesi mümkün ise, xt değişkeninin pozitif katsayıya sahip bütün kısıtlarda, sağ taraf sabitini bu değişkenin katsayısına bölmekle elde edilen oranların en küçük olduğu kısıt pivot kısıt olarak ilan edilir ve bu kısıttaki temel değişken de temelden çıkacak değişken olarak belirlenir. Eğer amaç fonksiyonunda birden fazla sayıda temel dışı değişken pozitif katsayıya sahip ise, bu katsayılardan en büyük olana karşı gelen değişken seçilerek temele girecek değişken olarak ilan edilir. Sebebi ise çok açık: (her zaman böyle olmasa da birçok durumlarda) en büyük katsayılı değişkenin temele girmesi amaç fonksiyonuna daha büyük katkı sağlayacaktır.
Alternatif Çözüm Kriteri: Eğer kanonik şekildeki bir problemde temel dışı değişkenlerden pozitif katsayıya sahip bir değişken bulunmazken, bir xt temel dışı değişkenin katsayısı sıfır ise bu durum, mevcut temel uygun çözümün en iyi çözüm olduğu anlamına gelecektir. Fakat katsayısı sıfır olan temel dışı değişkenin fonksiyonel kısıtlardan bir veya birkaç tanesinde pozitif katsayıya sahipse, bu aşamada bu değişkenin temele alınması ile yeni bir temel uygun çözümün türetilebilmesi mümkündür. Bu değişkenin katsayılarının pozitif olduğu kısıtlara en küçük oran yöntemi uygulanarak pivot satır ve temelden çıkacak değişken bulunmak suretiyle pivot işlemi yapılır ve yeni bir temel uygun çözüm türetilebilir. Temele girmesine karar verilen değişkenin amaç fonksiyonu satırındaki katsayısı sıfır olduğundan, amaç fonksiyonu denklemine pivot işlemi yapılmayacak ve bu satır değişmediğinden yeni temel uygun çözüm için amaç fonksiyonunun değeri de değişmeyecektir. Böylece yeni bir optimal çözüm türetilmiş olacaktır. Bu yüzden, bu şekilde ortaya çıkan çözümlere alternatif çözümler denir. İki alternatif çözüm noktasını birleştiren doğru parçası üzerindeki bütün noktalar benzer özelliğe sahip olduklarından (amaç fonksiyonuna aynı değeri sağladıklarından) bu doğru parçası üzerindeki bütün noktalar en iyi çözümler olma özelliğine sahiptir.
Şimdi kanonik şekilde verilmiş bir DP problemi için simpleks yöntemin cebirsel algoritmasını ana hatlarıyla özetleyebiliriz:
Başlangıç adım: Kanonik şekilde verilmiş problemin temel uygun çözümünü bul.
En İyilik Testi: Eldeki çözüme (cebirsel) en iyilik kriterini uygula.
Ana adım: Eldeki çözüm en iyilik kriterini sağlıyorsa DUR: problemin en iyi çözümü bulunmuştur.
En iyilik kriteri sağlanmıyorsa, çözümün iyileştirilmesi için pivot işlemini uygula, yeni bir temel uygun çözüm bul ve eldeki çözümü güncelleyerek En İyilik Testi Adımına Git.
Simpleks Yöntemin Geometrik Yorumu
Önceki bölümlerde, DP problemlerinin en iyi çözümler hakkında edindiğimiz en önemli bilgilerden biri de bu çözümlerin her zaman uç-nokta uygun (UNU) çözümler arasında olabileceği bilgisidir, yani bir DP probleminin en iyi çözümünü bulmak istersek, aslında tüm UNU çözümleri dolaşarak bunu yapabiliriz. Ancak, karar değişkenleri ve fonksiyonel kısıtların sayısı arttıkça bunun yapılabilmesi pek kolay hatta mümkün olmayabilir. Bu durumda herhangi bir UNU çözüm noktasını bulduğumuz zaman kolay test edebileceğimiz bir kriterin olması çok işimize gelecektir. Bir önceki alt bölümde, temel ve temel dışı değişkenlerle amaç fonksiyonu birlikte incelenerek elimizdeki temel uygun çözümün optimal olup olmadığını test etmek için bir kriter öğrenmiştik. Şimdi UNU çözümler üzerinden bir kriter daha belirleyeceğiz.
Geometrik En İyilik Kriteri: İncelediğimiz DP probleminin en iyi çözüme sahip bir problem olduğunu var-sayalım. Eğer elimizdeki bir uç-nokta uygun çözüm, bu uygun çözüme komşu uç-nokta uygun çözümler arasında amaç fonksiyonuna en iyi değer sağlayan nokta ise, problemin de en iyi çözümüdür.
Simpleks Yöntemin Cebirsel ve Geometrik Yorumlarının İlişkilendirilmesi ve Simpleks Algoritma
Problemimizin kanonik şekli aşağıdaki gibi olduğunda:
−x1 + x2 + x3 = 3,
3x1 + x2 + x4 = 9,
x1 + x2 + x5 = 5,
xj ≥ 0, j = 1,2,3,4,5,
kısıtları altında
Enb z=2x1 + x2.
Dikkatle bakıldığında x3, x4, x5 değişkenlerinin temel değişkenler, x1, x2 değişkenlerinin ise temel dışı değişkenler oldukları açıkça görülmektedir. Bu yorumu kullanarak orijinal problemin UNU çözümleri ile genişletilmiş problemin temel uygun çözümleri arasındaki ilişkiyi açıklayalım.
Başlangıç Adım: x1=0, x2=0 noktasını problemin başlangıç UNU çözüm olarak seç. Bu nokta, kanonik problem için x1=0, x2=0, x3=3, x4=9, x5=5 temel uygun çözüme karşılık gelmektedir.
İterasyon 1.
En iyilik testi: x1=0, x2=0 noktasına geometrik en iyilik kriterini uygula: Komşu uç-nokta uygun çözümlerle kıyaslayalım: z(0,0)=0, z(3,0)=6, z(0,3)=3. Bu yüzden, yeni (ve daha iyi) uç-nokta uygun çözüm x1=3, x2=0
olarak güncelleştiriliyor. Karşı gelen amaç fonksiyonunun yeni değeri z=6.
İterasyon 2.
Geometrik en iyilik testi: x1=3, x2=0 uç-nokta uygun çözüme komşu uç-nokta uygun çözümler x1=2, x2=3 ve x1=0, x2=0 noktalarıdır. x1=0, x2=0 noktası daha önce kontrol edildiğinden, eldeki çözümü sadece x1=2, x2=3 UNU çözümü ile kıyaslamak yeterlidir:
z(2,3) = 7 > z(3,0) = 6.
Bu yüzden, geometrik en iyilik kriterine göre, güncelleşmiş yeni uç nokta uygun çözüm olarak x1=2, x2=3 belirleniyor.
Algoritmayı sonlandır: x1=2, x2=3, x3=2, x4=0, x5=0 temel uygun çözümü cebirsel en iyilik kriterini, karşı gelen x1=2, x2=3 UNU çözümü de geometrik en iyilik kriterini sağladığından, problemin en iyi çözümüdür. Bu noktada, amaç fonksiyonunun en iyi değeri −z=−7 veya z=7 olarak bulunmuştur.
Simpleks Yöntemin Tablo Şekli
Simpleks yöntemin tablo şekli, cebirsel algoritmanın kullandığı sadece önemli bilgileri içermektedir: değişkenlerin katsayıları, sağ taraf sabitleri ve eniyilik ve/veya mevcut uygun çözümün iyileştirilmesi kriterinin uygulanması için temelden çıkacak ve temele girecek değişkenler.
Simpleks algoritmayı kısaca özetleyelim:
• Algoritma yalnızca uygun uç noktalara odaklıdır. • Belli adımlar serisinin tekrarından oluşan (iteratif) bir algoritmadır. • Genelde başlangıç uç nokta olarak (0,0) noktasını seçer. • Komşu uç noktaları belirler. • Amaç fonksiyonunun her bir kenar üzerinde iyileşme derecesini hesaplar. • Bulunmuş uç-nokta uygun çözümden daha iyi komşu uç-nokta uygun çözüm yoksa, bu noktayı optimal çözüm noktası olarak belirler.