Ünite 4: Simpleks Algoritması

Giriş

Doğrusal bağımsız vektörlerden oluşan, m denklem ve n değişkenin olduğu (m x n’lik ve m < n) bir sistemin çözümünde, diğer (n - m) tane değişken sıfır değerini almak üzere, ancak denklem sayısı (m) kadar değişkene değer bulunabilir. Burada, sıfır değeri verilen değişkenlere temel dışı, değer alması için çözüme alınan değişkenlere ise temel değişken denir. Temel dışı değişkenler sıfır iken temel değişkenler için bulunan çözüme temel çözüm denir. Bir temel çözümde tüm temel değişkenler sıfır veya sıfırdan büyük değer aldıysa bu çözüme bir temel uygun çözüm denir ve bir temel uygun çözüm aynı zamanda bir uç nokta demektir.

Analitik yöntem, basitçe yukarıdaki gibi uygulanmakta ve kısıtları eşitlik haline getirilmiş bir denklem sisteminin belirtilen şekilde tüm çözümlerini elde ederek içlerinden temel uygun çözüm (uç nokta) olanlarını bulmaktadır. Temel uygun çözüm olma özelliği sağlayanlar arasından amaç fonksiyonu değerini eniyileyen, problemin en iyi çözümünü verecektir.

Simpleks Algoritması, grafik ve analitik yöntemlerin uygulamadaki güçlüklerini taşımayan, ardışık sayısal çözüm tekniği sınıfında bir yöntemdir. Basitçe izlediği yol, bir uç noktadan başlayarak amaca göre daha iyi çözüm verecek başka bir uç noktaya geçmek (eğer varsa) ve istenen yönde iyileşmenin olmadığı durumda da durmaktır. Simpleks Algoritması ile problemin denklem sistemini çözen, uç nokta olsun olmasın tüm noktalarını bulmak gerekmediği gibi, sadece uç noktaların bile tümünün sınanmasına gerek kalmayabilmektedir. Algoritma, her adımda, uygun çözüm alanının bir uç noktasını bulup irdelemekte ve bu noktanın en iyi çözüm olup olamayacağını sınamaktadır. Nokta en iyi çözüm değilse, amaca göre daha iyi bir çözüm verecek izleyen uç noktayı bulur. Bazı durumlarda da problemin uygun çözüm alanı boş kümedir yani tüm kısıtları sağlayan tek bir çözüm bile yok demektir. Benzer şekilde özel durumlardan birisi de problemin sınırsız veya birden fazla uç noktada en iyi çözümünün olmasıdır.

Temel Uygun Çözüm, Uç Nokta, Analitik Yöntem

AX = b şeklindeki, doğrusal bağımsız vektörlerden oluşan, m denklem ve n değişkenin olduğu (m x n’lik ve m < n) bir sistemin çözümünde, diğer (n - m) tane değişken sıfır değerini almak üzere, ancak denklem sayısı (m) kadar değişkene değer bulunabilir.

Verilen denklem sisteminin diğer temel çözümleri de benzer şekilde her seferinde farklı iki diğer değişken temelde, geriye kalanlar temel dışında alınarak bulunabilir. Bunların arasından uç nokta olanlar tüm değişkenleri ? 0 koşulunu sağlayanlardır.

Analitik yöntem, verilen denklem sisteminin tüm temel çözümleri bulunduktan sonra, içlerinden uç nokta olanlarının bir amaç fonksiyonunda değerlendirilip en iyisinin bulunması ile sonuçlanır.

Simpleks Algoritması’na Olan İhtiyaç ve Bir Örnek Üzerinde Temel Adımları

Simpleks Algoritması analitik yöntemin temellerini esas alan, temel ve temel olmayan değişkenlerin belirlenmesinden sonra amaç fonksiyonu değeri iyileşecekse, bir uç noktadan diğerine geçen ardışık bir çözümleme tekniği olarak tanımlanır.

Simpleks Algoritması’nın temel adımları kitabınızın 72. Sayfasında yer alan Örnek 4.3’e göre açıklanmıştır.

1. Temel değişkenler, temel olmayan değişkenler cinsinden ifade edilir (kısıtlar yardımıyla temel değişkenler çözülür).
2. (3) ve (5)’de elde edilen, temel değişkenlerin (x ₁ ve s ₁ ) değerleri amaç fonksiyonunda yerine konursa, (6) elde edilir. Verilen bir problemde tüm değişkenler amaç fonksiyonunda yer almayabilir. s1 aylak değişken olduğu için, belirtildiği gibi amaç fonksiyonundaki katsayısı sıfırdır. x ₂ ise temelde olmadığı için ve (6) nolu denklem de zaten amaç fonksiyonunun temel dışı değişkenler cinsinden ifadesi olduğundan yine x ₂ olarak ilgili denklemde yer almıştır. Böylece kısıtlar ve amaç fonksiyonu sırasıyla (3), (5) ve (6) ile temel olmayan değişkenler (x ₂ ve s ₂ ) cinsinden ifade edilmiş olurlar. Amaç fonksiyonunun şu anki değeri 120’dir. Temel olmayan değişkenlerin değeri ise 0’dır.
3. Temel olmayan değişkenler cinsinden elde edilmiş olan amaç fonksiyonu (6) yardımıyla, temele alınabilecek ve amaç fonksiyonu değerini daha da iyileştirebilecek bir değişken olup olmadığına bakılır. Mevcut durumda değerleri sıfır olduğu halde temelde olmayan x ₂ ve s ₂ ’nin amaç fonksiyonunda korunmasının sebebi, değer almaları halinde x ₀ ’ ı daha iyiye götürecek bir katsayılarının olup olmadığını görebilmek içindir. m kısıtlı bir sistemin herhangi bir temel uygun çözümünde m tane temel değişken olmalıdır. Bu durumda x ₁ ve s ₁ ’in temelde olduğu, yukarıdaki gibi bir çözümde iki temel değişken olması gerekmekte olup x ₂ değişkeninin de temele alınması halinde, x ₁ ve s ₁ değişkenlerinin birisinin temelden çıkması gerekmektedir. (3) ve (5)’e göre, x ₂ değer aldıkça x ₁ ve s ₁ ’ in değerleri azalır.
4. Simpleks Algoritması’nda temelden çıkan değişken sıfır değerine ulaşırken, temelde kalmaya devam eden değişkenler ise pozitif değer almalıdırlar.

Simpleks Algoritması bir başlangıç temel uygun çözüm ile başlar. Bu başlangıç uç nokta, s.73’de verilen (x ₁ , x ₂ , s ₁ , s ₂ ) = (30, 0, 10, 0) gibi kısıtları sağlayan herhangi bir uç nokta olabileceği gibi, pratik olarak başlangıç modelde A katsayılar matrisinde yer alan mxm boyutundaki birim matrise (kendiliğinden varsa veya kısıtlar eşitlik haline getirildiğinde oluşmuşsa) karşı gelen değişkenler başlangıç temel uygun çözümü oluşturmak üzere alınırlar.

Verilen modelin kısıtları eşitlik haline getirildikten sona A katsayılar matrisinde denklem sayısı boyutundaki birim matrise karşı gelen değerler (örnek 4.3’de 2x2’lik birim matris) başlangıç temel değişkenler olarak alınırlar. Simpleks Algoritması mantığı tablolar yardımıyla, denklemleri tümüyle yazmadan sadece katsayılar temelinde de yürütülebilir. Buna göre, s ₁ ve s ₂ ’nin başlangıç temel değişkenler olduğu duruma karşı gelen çözüm ve izleyen işlemler, tablo yardımıyla izleyen bölümde açıklandığı gibi gerçekleşir.

Simpleks Algoritması’nı uygulayabilmek için verilen denklem sisteminin kısıtlarının eşitlik haline getirilmesi gerekir. Bu durumda m denklem ve n değişkenli AX = B sisteminde mxm’lik bir birim matris varsa, karşı gelen değişkenler başlangıç temel değişkenler olarak alınırlar. Bu ünitede yalnızca bu durumun sağlandığı örneklere yer verilip standart Simpleks Algoritması anlatılmaktadır. Öte yandan birim matrisin denklem sistemi eşitlik haline getirildiğinde kendiliğinden elde edilmediği durumlarda, sisteme, gerektiği kadar yeni değişken eklentisiyle bu eksiklik giderilmektedir. Bu tür değişkenlere yapay değişken denip, bu durumda bilinen Simpleks Algoritması’nın özel bir hali uygulanır.

Simpleks Tablo

x ₀ – 4x1 – 3x2 = 0 şeklinde tanımlanan ve belirtilen temel değişken takımı (s ₁ ve s ₂ ) başlangıç çözüm alınarak aşağıdaki tabloya yerleştirilir. Bu tablo oluşturulurken x0 ile gösterilen satır amaç fonksiyonuna diğer izleyen satırlar ise problemin verilen kısıtlarına karşı gelir.

Amaç fonksiyonu satırı x ₀ + C.X = 0 formatında alınır. Temel değişkenler yerine, temel olmayan değişkenler cinsinden, kısıtların çözümü ile bulunan eşdeğerleri yazıldığından, temel değişkenlere karşı gelen katsayılar sıfır olup, bu satır, amaç fonksiyonunun temel olmayan değişkenler cinsinden ifadesidir. Temelde olmayan değişkenlerin katsayılarına göre de, bilindiği gibi, temele girecek değişkenin olup olmadığı değerlendirilir.

x ₀ satırı amaç fonksiyonunun temel olmayan değişkenler cinsinden ifadesi olup, burada x ₁ değişkeni temele girecek değişken olarak belirlenir. Amaç fonksiyonundaki katsayısının -4 olması, X ₀ = C.X fonksiyonunda bu değişkenin katsayısının pozitif (+) olması demek olup, x1‘in temele alınması durumunda amaç fonksiyonu değerinin büyüyeceğini göstermektedir.

Sayfa 76, 77, 78’deki tabloları sırasıyla inceleyiniz.

Matris Gösterimi, Enbüyükleme ve Enküçükleme İçin Örnekler

Matematiksel modele karşı gelen denklem sistemi,

A : Tüm değişkenlere karşı gelen katsayılar matrisi, X değişken vektörü, b kaynak (sağ taraf sabitleri) vektörü iken,

olmak üzere AX = b şeklinde yazılabilir. Karşı gelen matris çarpımları,

gerçekleştirildiğinde,

x ₁ + x ₂ + s ₁ = 40

2x ₁ + x ₂ +s ₂ = 60

denklem sistemi yeniden elde edilir. Amaç fonksiyonu da benzer şekilde,

X ₀ = CX şeklinde tanımlanarak, C = (4 3 0 0)

olarak alınıp

olarak elde edilir. Böylece doğrusal karar modelinin

AX = b, X ? 0 , Enb X ₀ = CX

şeklinde de ifade edilebileceği gösterilmiş olur.

Simpleks Algoritması’nda değişkenler, önceki örnekte de görüldüğü gibi temel ve temel olmayan olmak üzere iki gruba ayrılırlar. Bu durumda,

X _B : Temel değişkenler vektörü

X _R : Temel olmayan değişkenler vektörü

olmak üzere X vektörü aşağıdaki gibi iki parçalı olarak

aşağıdaki gibi gösterilebilir.

Benzer şekilde, AX = b modelindeki A matrisi ile

Enb X ₀ = CX fonksiyonundaki C vektörü de şu şekilde parçalanabilir;

B: Temel değişkenlere A katsayılar matrisinde karşı gelen matris

R: Temel olmayan değişkenlere A katsayılar matrisinde karşı gelen matris

C _B : Temel değişkenlere C’de karşı gelen katkı vektörü

C _R : Temel olmayan değişkenlere C’de karşı gelen katkı vektörü iken

C = (C _B , C _R ), A = (B,R) şeklinde gösterilebilir.

Amaç fonksiyonunu enküçüklenmesi

Sayfa 79,80’deki enbüyükleme problemini gözönüne alalım Enbüyüklemede incelenen bu örnekte temelde yer almayan x ₁ değişkeninin amaç fonksiyonu satırındaki değeri olan -4, bu değişkenin temele alınması gerektiğini belirtir. Benzer şekilde devam edildiğinde temel olmayan değerler arasında katsıyısı negatif olan bir değişkenin kalmaması enbüyükleme için eniyilik koşulunun sağlandığını gösterir.

Verilen problem enküçükleme olursa yine benzer yaklaşım geçerlidir. Fakat bu durumda yer almayan değişkenler içerisinde amaç fonksiyonu satırındaki katsayısı negatif değil pozitif olan değişken amaç fonksiyonu değerini azaltacağından bu değişkenler temele alınmalıdır. Benzer şekilde katsıyısı pozitif olan bir değişkenin kalmaması enküçükleme için eniyilik koşulunun sağlandığını gösterir.