Doğrusal Programlama (DP) Problemleri İçin Çözüm Yöntemi Simpleks Yöntem

1. Bütün karar değişkenleri negatif olmayacak şekilde kısıtlanmıştır.
2. Bütün fonksiyonel kısıtlar eşitlik şeklinde formüle
edilmiştir.
3. Fonksiyonel kısıtların sağ taraflarındaki sabitlerin 
hiç birisi negatif değildir.
4. Her bir fonksiyonel kısıtta sadece bir karar değişkeni +1 katsayıya sahiptir. 

Genel olarak, kanonik şekilde verilmiş herhangi bir DP probleminin temel uygun çözümü, her bir kısıtta temel değişken olarak adlandırılan izole değişkenin değerinin sağ taraf sabitine, bu kısıttaki temel dışı değişkenler olarak adlandırılan temel değişken haricindeki bütün değişkenlerin ise sıfıra eşitlenmesi ile elde edilir

Kanonik şekilde tanımlanmış bir en büyükleme probleminin temel dışı değişkenlerinin tamamının amaç fonksiyonundaki işaretlerinin negatif olduğunu varsayalım. Bu durumda, 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.

Kanonik şekilde verilmiş bir en büyükleme probleminin temel dışı değişkenlerinin
bir (veya bir kaç) tanesinin amaç fonksiyonundaki katsayısının pozitif işarete sahip
olduğunu varsayalım. Eğer bu değişkenin (veya değişkenlerin) bütün fonksiyonel kısıtlardaki
katsayıları sıfır veya negatif sayı ise, bu problemin amaç fonksiyonu uygun çözüm alanında üstten sınırsızdır.

Yeni temel değişkenin oluşturulması işlemine pivot işlemi denir.

Kanonik şekilde verilmiş bir en büyükleme probleminin temel dışı değişkenlerinin bir (veya birkaç) tanesinin amaç fonksiyonundaki katsayısının pozitif işarete sahip olduğunu varsayalım. Eğer bu değişkenin her hangi bir fonksiyonel kısıttaki katsayısı pozitif ise, daha iyi bir temel uygun çözüm pivot işlemi kullanılarak elde edilebilir.

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.

Eğer pivot satırdaki sağ taraf sabiti sıfır ise, bu satıra karşı gelen temel değişkenin
değerinin sıfır olması anlamına gelmektedir. Bu durumda pivot işlemi yapılacak,
fakat “yeni” temel değişkenin değeri yine de sıfır olacaktır. Yani temele “yeni” bir
değişken girse de değeri sıfır olacağından ve temelden çıkan değişkenin de hem
önceki hem de yeni değeri sıfır olduğundan aslında yeni bir çözüm üretilmemiş
olacak ve amaç fonksiyonunun değeri doğal olarak değişmeyecektir. Bu tip çözümlere
dejenere çözümler denir.

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.

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.

Kısıtların eşitlik haline getirilmesiyle elde edilen denklemlerin kesişim (uygun çözüm alanında kalan) noktasına uç nokta uygun çözüm denir.

Uygun çözüm alanı dışında kalan diğer kesişim noktaları ise uç nokta uygun olmayan çözümler olarak adlandırılır.

n tane karar değişkenine sahip bir doğrusal programlama probleminde eğer iki uç nokta, n - 1 adet sınır doğrusunu ortak olarak sağlıyorsa, o zaman bu iki uç noktaya komşu uç noktalar denir.

İki komşu uç noktayı her zaman birbirine bağlayan bir doğru parçası vardır. Bu doğru parçasına uygun
çözüm alanının bir kenarı denir.

İncelediğimiz DP probleminin en iyi çözüme sahip bir problem olduğunu varsayalı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.

Geometrik En İyilik kriterinin bize sağladığı çok önemli özellik de bir UNU çözümün en iyi
çözüm olduğunu kontrol etmek için onu tüm UNU (iç nokta uygun)  çözümlerle değil, sadece komşu UNU
çözümlerle kıyaslamanın yeterli olacağıdır. Bu özellik, simpleks yöntemin en önemli kazanımlarından
biri olarak sayılmaktadır.

Başlangıç Adım: O(0,0) noktasını başlangıç UNU çözüm olarak seç (bu noktanın seçilmesi genellikle
hiçbir hesaplama gerektirmediğinden kolaylıkla seçilebilir).
En iyilik testi: O(0,0) noktasına en iyilik kriterini
uygula: Sağlamıyor. Komşu uç-nokta uygun
çözümlerle kıyasla.

Ana Adım: Bulunan noktada amaç fonksiyonu
daha iyi değere sahip olduğundan, eldeki çözümü
güncelle: UNU çözüm  , ve En iyilik
testinin yapıldığı adıma git ve testi bu UNU çözüme
uygula.

Mevcut uygun çözüm optimal olup olmadığı için tablodaki  temel dışı değişkenlerin iamaç 
fonksiyonundaki katsayıları negatif olmalıdır.

• 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.

Sayfa 73'deki  akış şemasını inceleyiniz.