YÖNEYLEM ARAŞTIRMASI I

Amaç fonksiyonu satırında 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 temele girecek değişkenin olup olmadığı değerlendirilir. Buna göre Simpleks Algoritmasının herhangi bir çözümü için x0 satırında, temel ve temel dışı değişkenlerin amaç fonksiyonunda karşı gelen katsayıları kontrol edilir. En küçükleme probleminde temele girecek değişken varsa, xo'da en büyük negatif katkı sağlayacak pozitif değere karşı gelen değişkendir. Buna göre 5, 1, 7 değerlerinden en büyük negatif katkıyı sağlayacak olan pozitif 7 değerine karşı gelen değişken 5. değişken temele girecektir.

Amaç fonksiyonu satırında 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 temele girecek değişkenin olup olmadığı değerlendirilir. Buna göre Simpleks Algoritmasının herhangi bir çözümü için x0 satırında, temel ve temel dışı değişkenlerin amaç fonksiyonunda karşı gelen katsayıları kontrol edilir. En büyükleme probleminde temele girecek değişken varsa, xo'da en büyük pozitif katkı sağlayacak negatif değere karşı gelen değişkendir. Buna göre -3, -1 ve -8 değerlerinden en büyük pozitif katkıyı sağlayacak olan -8 değerine karşı gelen değişken 3. değişken temele girecektir.

Bir temel çözümde, tüm değişkenler
>=0
olmakla birlikte, temelde olduğu halde sıfır değerini alan bir değişken var ise, elde edilen çözüme dejenere (bozulmuş) çözüm denir. temelde olan x2 ve x4 değişkenlerinden x4 pozitif değer almışken ,x2 sıfır değerini aldığın çözüm dejeneredir.

Bir doğrusal karar probleminin çözümünde çeşitli yöntemler kullanılabilir. Problemin uygun çözüm alanı (eğer boş küme değilse) içerisindeki uç noktalarını belirleyip içlerinden eniyi çözüm veya çözümleri bulmaya dönüktür. İki değişken olduğu durumda yaygın kullanılan yöntem grafik yöntemdir. Daha fazla sayıda değişken olduğunda ise analitik yöntem  Simpleks Algoritması’dır.

Doğrusal Proğramlama modeli bağımsız vektörlerden oluşur, m denklem ve n değişkenin olduğu (mxn’lik ve m<n) bir sistemin çözümünde ele alınılır.

Örnek olarak iki denklem ve beş değişkenin olduğu bir sistemde, her seferinde üç değişkene sıfır değerini vererek, iki değişken için çözüm bulunabilir. Burada, sıfır değeri verilen değişkenlere temel dışı değişken denir

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

Temel değişkenlerin analitik çözümü sonucunda bazen negatif değer bulunabilir. Bu gibi durumlarda analitik yöntem küçük bir problem için bile iş yükü getirmektedir ve uç nokta olmadığı halde bazı noktaların da zorunlu olarak hesaplanmasını gerektirmektedir.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 eniyisinin bulunması ile sonuçlanır

her probleme karşı gelen matematiksel model, kısıtları eşitlik haline getirildiğinde katsayılarından oluşan matris elde edilir.Bu katsayılar matrisinin çözünü için kare matrik olmak zorundadır. Bu gibi durumlarda denklem sistemine başlangıç çözüme karşı gelmek üzere, birim matrisi oluşturacak şekilde, gerektiği sayıda yeni değişken eklenir.

Bir temel çözümde, tüm değişkenler sıfıra eşit yada sıfırdan büyük olmakla birlikte, temelde olduğu halde sıfır değerini alan bir değişken var ise, elde edilen çözüme dejenere (bozulmuş) çözüm denir.

Simpleks Algoritması’na, en iyileme de, çözüm sürecini kolaylaştıran paket programlarLINDO, LINGO, GAMS gibi, örnekleri verilebilecek bu tür yazılımların yanında, hemen her bilgisayarda hali hazırda bulunan çalışma tablosu programı Microsoft Excel’in çözücü (solver) modülü ile bile belirli büyüklükteki matematiksel modellere çözüm bulunabilmektedir.

Bir çö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.

Simpleks Algoritması’nı uygulayabilmek için verilen denklem sisteminin kısıtlarının eştlik haline getirilmesi gerekir.

eşdeğerleri

Doğrusal bağımsız vektörlerden oluşan, m denklem ve n değişkenin olduğu (mxn’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

3 tane denklem kadar

4-3=1 tane

s1 ve s2 değişkenlerine sırasıyla artık ve aylak değişken denir.