Simpleks Yöntem
Simpleks yöntem çok değişkenli karar değişkenleri ve kısıtlayıcılardan oluşan doğrusal programlama problemlerinde optimum çözümü bulmak için 1947 yılında George Dantizg tarafından geliştirilmiştir. Bir doğrusal programlama problemini simpleks yöntem ile çözmek için standart formda ifade etmemiz gerekir. Bu sebeple ilk önce standart biçimden bahsedelim.
Standart Biçim
Zenk/enb = c1 . x1 + c2 . x2 + … + cn . xn
a11 . x1 + a12 . x2 + a13 . x3 + … + a1n . xn = b1
a21 . x1 + a22 . x2 + a23 . x3 + … + a2n . xn = b2
a31 . x1 + a32 . x2 + a33 . x3 + … + a3n . xn = b3
…..
am1 . x1 + am2 . x2 + am3 . x3 + … + amn . xn = bn
x1, x2, x3, … xn ≥ 0
olarak ifade edilen doğrusal programlama modeli aşağıdaki koşulları sağlarsa standart biçimdedir.
- Amaç fonksiyonu en büyükleme ya da en küçükleme olabilir.
- Kısıtlayıcı fonksiyonların sağ taraf sabitleri negatif olmamalıdır.
- Tüm kısıtlayıcı fonksiyonlar eşitlik halinde olmalıdır.
- Tüm karar değişkenleri negatif olmamalıdır.
Elimizdeki doğrusal programlama modelinde bazı dönüştürmeler yapmaya ihtiyaç duyabiliriz. Bir doğrusal programlama modeli üzerinde dönüşümlere kısaca göz atalım.
- Bir doğrusal programlama modelinin amaç fonksiyonunun anlamını değiştirmek için fonksiyonu (-1) ile çarpabiliriz. Bu durumda en büyükleme olan amaç fonksiyonu en küçükleme olacaktır.
Zenb = 2x1 + x2 + x3
Zenk = -2x1 – x2 – x3
- Bir doğrusal programlama modelinin kısıtlarındaki eşitsizliklerin yönünü değiştirmek için kısıtı (-1) ile çarpabiliriz.
3x1 + 4x2 ≥ 6
-3x1 – 4x2 ≤ -6
- Eşitsizlik durumundaki bir kısıtı eşitliğe çevirmemiz gerekebilir. Bu çevirme işlemi kısıtın yönüne göre değişmektedir. Eğer a1 . x1 + a2 . x2 + a3 . x3 ≥ b1 gibi bir kısıtı eşitlik haline dönüştürmek istiyorsak, eşitsizliğin sol tarafından negatif olmayan bir değişken çıkarmamız gerekir. Bu değişkene, artık değişken denir. Eğer a1 . x1 + a2 . x2 + a3 . x3 ≤ b1 gibi bir kısıtı eşitlik haline dönüştürmemiz gerekiyorsa, eşitsizliğin sol tarafına negatif olmayan bir aylak değişken eklememiz gerekir. Böylece elimizdeki bir doğrusal programlama modelini standart biçime dönüştürerek simpleks yöntem ile çözebiliriz. Son olarak kısıtlayıcı değişkenler eşitlik durumunda ise, eşitliğin sol tarafına “A” ile gösterilen bir yapay değişken eklenmelidir. Simpleks yöntemi daha iyi anlayabilmek için örnek üzerinde inceleyelim.
Örnek
Zenb = 2x1 + 3x2
6x1 + 4x2 ≤ 20
3x1 + x2 ≤ 30
x1 + x2 ≤ 40
x1, x2 ≥ 0
Simpleks yöntem ile çözünüz.
İlk adım olarak doğrusal problemi standart biçime çevirelim.
Standart Biçim
6x1 + 4x2 + x3 = 20
3x1 + 2x2 + x4 = 30
x1 + x2 + x5 = 40
x1, x2, x3, x4, x5 ≥ 0
Burada x3, x4 ve x5 aylak değişkendir. Aylak değişkenler amaç fonksiyonuna eklenirken katsayısı 0 (sıfır) olarak eklenir. Bu durumda amaç fonksiyonumuz aşağıdaki gibi olur.
Zenb = 2x1 + 3x2 + 0 x3 + 0 x4 + 0 x5
Şimdi ise bu problemi çözebilmek için tablo yapmamız gerekir. Bu tablonun üst kısmında değişkenler, sol kısmında temel değişken vektörü altında aylak ve yapay değişkenler yer almalıdır. Ancak burada artık değişkenler (varsa) yer alamazlar. Çünkü temel çözüm uygun olmaz.
| AFK | TDV | x1 | x2 | x3 | x4 | x5 | ÇV |
| 0 | x3 | ||||||
| 0 | x4 | ||||||
| 0 | x5 | ||||||
| – | Zj | ||||||
| – | Zj – Cj |
AFK = Temeldeki değişkenlerin (TDV altında) amaç fonksiyonundaki katsayıları
TDV = Temel değişken vektörü
ÇV = Çözüm vektörü
Kısıtları tabloya yerleştirirken sıralamaya dikkat etmemiz gerekir. İlk kısıtımızda x3 aylak değişkeni olduğu için, ilk sıraya x3 aylak değişkenini yazıp, x3 aylak değişkeninin bulunduğu satıra ise kısıtın katsayılarını sırasıyla yerleştirmemiz gerekir. Bu işlemi diğer kısıtlar içinde yapmamız gereklidir. Ardından temeldeki değişkenlerin amaç fonksiyonundaki katsayılarını yanlarına (AFK) yazmamız bizim için faydalı olacaktır. Çünkü Zj satırını elde etmek için bu katsayıları kullanacağız. Her bir Zj değeri o sütundaki elemanlar ile temeldeki değişkenlerin amaç fonksiyonlarındaki katsayıları çarpılıp toplanmasıyla elde edilir. Böylece
Z1 = 0.6 + 0.3 +0.1 = 0
Z2 = 0.4 + 0.1 +0.1 = 0
Z3 = 0.1 + 0.0 +0.0 = 0
Z4 = 0.0 + 0.1 +0.0 = 0
Z5 = 0.0 + 0.0 +0.1 = 0
Ç.V = 0.20 + 0.3 0+0.40 = 0 olarak elde edilir.
Sırada ise Zj – Cj satırını elde etmek var. Bu satırı elde etmek için her bir Zj değerinden karşılık gelen değişkenin amaç fonksiyonu katsayısının çıkarılması gerekir. Bu durumda
Z1 – C1 = 0 – 2 = -2 ——>C1 , x1 ‘in katsayısı
Z2 – C2 = 0 – 3 = -3 ——>C2 , x2 ‘nin katsayısı
Z3 – C3 = 0 – 0 = 0 ——>C3 , x3 ‘ün katsayısı
Z4 – C4 = 0 – 0 = 0 ——>C4 , x4 ‘ün katsayısı
Z5 – C5 = 0 – 0 = 0 ——>C5 , x5 ‘in katsayısı
Bu değerler tabloda ilgili yerlere yazılmalıdır.
Simpleks Başlangıç Çözüm Tablosu
| AFK | TDV | x1 | x2 | x3 | x4 | x5 | ÇV |
| 0 | x3 | 6 | 4 | 1 | 0 | 0 | 20 |
| 0 | x4 | 3 | 1 | 0 | 1 | 0 | 30 |
| 0 | x5 | 1 | 1 | 0 | 0 | 1 | 40 |
| – | Zj | 0 | 0 | 0 | 0 | 0 | 0 |
| – | Zj – Cj | -2 | -3 | 0 | 0 | 0 |
Buraya kadar yaptıklarımızla tabloyu doldurduk. Buradan sonra yapmamız gereken anahtar sütun, anahtar satır ve anahtar sayı değerlerini bulmaktır. Anahtar sütun, temele girecek olan değişkeni belirler. Anahtar satır, temelden çıkacak olan değişkeni belirler. Anahtar sayı ise temele yeni giren değişkenin tablodaki değerlerini belirlemek için kullanılır. Anahtar sütun, amaç fonksiyonuna göre iki şekilde belirlenir. Eğer amaç fonksiyonu en büyükleme ise, Zj – Cj satırındaki mutlak değerce en büyük olan negatif sayının bulunduğu sütun anahtar sütundur. Amaç fonksiyonu en küçükleme ise, Zj – Cj satırındaki en büyük sayının bulunduğu sütun anahtar sütun olur. Bu şekilde anahtar sütunu belirleyip hangi değişkenin temele gireceğini bulabiliriz. Bir değişken temele girerken, temeldeki hangi değişkenin çıkacağına karar vermek için anahtar satırı bulmamız gerekir. Anahtar satırı bulmak için çözüm vektörü kısmındaki değerleri karşılık gelen anahtar sütun elemanlarına bölerek oran sütununu elde etmemiz gerekir. Oran sütununda hangi değer daha küçük ise o değerin bulunduğu satır, anahtar satır olarak adlandırılır ve temelden çıkarılır. Anahtar sayı ise anahtar sütun ile anahtar satırın kesiştiği değerdir. Şimdi bizim tablomuzdaki değerlere göre anahtar sütun, anahtar satır ve anahtar sayıyı bulalım.
Anahtar Sütun
| X1 | X2 | X3 | X4 | X5 | |
| Zj – Cj | -2 | -3 | 0 | 0 | 0 |
Buradan da görüldüğü gibi mutlak değerce en büyük olan negatif sayının bulunduğu sütun x2 sütunudur. Böylece x2 sütunu anahtar sütundur ve temele girmelidir.
Anahtar Satır
| Anahtar sütun(X2) | Çözüm Vektörü(ÇV) | Oran | |
| x3 | 4 | 5 | 5/4 |
| x4 | 1 | 30 | 30 |
| x5 | 1 | 40 | 40 |
Böylece x3 ‘ün temelden çıkarılması gerekir. Anahtar sütun(x2) ve anahtar satır’ın(x3) kesiştiği değerin 4 olduğu görülür. Böylece anahtar sayı 4’tür. Bu değerleri elde ettikten sonra simpleks birinci çözüm tablosunu oluşturarak çözüme devam edelim. Burada x2 satırının yeni değerleri x3 satırının değerlerinin anahtar sayıya bölünmesiyle elde edilir.
Simpleks Birinci Çözüm Tablosu
| AFK | TDV | x1 | x2 | x3 | x4 | x5 | ÇV |
| 3 | x2 | 3/2 | 1 | 1/4 | 0 | 0 | 5 |
| 0 | x4 | 3/2 | 0 | -1/4 | 1 | 0 | 25 |
| 0 | x5 | -1/2 | 0 | -1/4 | 0 | 1 | 35 |
| – | Zj | 9/2 | 3 | 3/4 | 0 | 0 | 15 |
| – | Zj – Cj | 5/2 | 0 | 3/4 | 0 | 0 | – |
Burada tablonun son halini yazdık ama tablonun içerisindeki değerler yeniden hesaplanmalıdır. Bu değerlerin hesaplanmasına geçilmeden önce şunu belirtmemiz gerekir temeldeki değişkenler tabloda birim matris oluştururlar. Biz tablonun yeni değerlerini bulurken bu değişkenlerin oluşturacağı birim matrisi korumamız gerekir. Simpleks başlangıç çözüm tablosuna baktığımızda temeldeki x3, x4 ve x5 değişkenlerinin tabloda birim matris oluşturduğu görülür. Simpleks birinci çözüm tablosunda ise x2, x4 ve x5 birim matris oluşturmalıdır. Temeldeki değişkenlerin bulundukları satırların değerleri bulunurken bu birim matris gözedilerek bulunacaktır. x2 satırının değerlerinin nasıl bulunduğu söylemiştik. Şimdi x4 ve x5 satırlarındaki değerleri bulalım. İlk önce x4 satırının değerlerini hesaplayalım. Bunun için x4 satırının simpleks başlangıç çözümündeki yani eski değerleri ve yeni x2 ’nin değerlerini kullanacağız. Bu değerleri kullanarak ve birim matrisi koruyarak x4 ’ün yeni değerlerini bulacağız.
| x1 | x2 | x3 | x4 | x5 | ÇV | |
| Eski x4 | 3 | 1 | 0 | 1 | 0 | 30 |
| Yeni x2 | 3/2 | 1 | 1/4 | 0 | 0 | 5 |
| Yeni x4 | 3/2 | 0 | -1/4 | 1 | 0 | 25 |
Burada birim matrisin korunması için yeni x4 ’ün x2 sütunundaki değeri 0, x4 satırındaki değeri 1 ve x5 sütunundaki değeri 0 olmalıdır. Bunun için yeni x2 satırı (-1) ile çarpılıp toplanmalıdır. Bulunan yeni x4 satırının değerleri tabloya yazılır.
Şimdi x5 satırının değerlerini bulalım. Bunun için ise simpleks başlangıç çözüm tablosundaki yani eski x5 değerlerini ve yeni x2 değerlerini kullanacağız.
| x1 | x2 | x3 | x4 | x5 | ÇV | |
| Eski x5 | 1 | 1 | 0 | 0 | 1 | 40 |
| Yeni x2 | 3/2 | 1 | 1/4 | 0 | 0 | 5 |
| Yeni x5 | -1/2 | 0 | -1/4 | 0 | 1 | 35 |
Yeni x5 değerleri bulunurken birim matrisi korumak için yeni x5‘in x2 sütunundaki değeri 0, x4 sütunundaki değeri 0 ve x5 sütunundaki değeri 1 olmalıdır. Bu sebeple yeni x2 satırı (-1) ile çarpılıp toplanmalıdır. Böylece yeni x5 satırının değerleri hesaplanmış olur. Bu değerlerde tabloya eklendiğinde hesaplamamız gereken Zj ve Zj – Cj satırı kalır. Zj satırındaki değerleri temeldeki değişkenlerin amaç fonksiyonu katsayıları ile tablodaki değerlerin çarpılıp toplanmasıyla elde ediliyordu. O zaman Zj satırındaki değerler aşağıdaki gibi hesaplanır.
Z1 = 3.(3/2) + 0.(3/2) + 0.(-1/2) = 9/2
Z2 = 3.1 + 0.0 + 0.0 = 3
Z3 = 3.(1/4) + 0.(-1/4) + 0.(-1/4) = 3/4
Z4 = 3.0 + 0.1 + 0.0 = 0
Z5 = 3.0 + 0.0 + 0.1 = 0
Ç.V = 3.5 + 0. 25+ 0.35 = 15
Bu değerler tabloya yazılmalıdır. Ardından her bir Zj değeri bulunduğu sütundaki değişkenin amaç fonksiyonundaki katsayısı olan Cj ’den çıkarılarak Zj – Cj değerleri hesaplanır.
Z1 – C1 = (9/2)– 2 = 5/2 ——>C1 , x1 ‘in katsayısı
Z2 – C2 = 3 – 3 = -0 ——>C2 , x2 ‘nin katsayısı
Z3 – C3 = 3/4 – 0 = 3/4 ——>C3 , x3 ‘ün katsayısı
Z4 – C4 = 0 – 0 = 0 ——>C4 , x4 ‘ün katsayısı
Z5 – C5 = 0 – 0 = 0 ——>C5 , x5 ‘in katsayısı
Amaç fonksiyonumuz en büyükleme olduğu için Zj – Cj satırındaki tüm değerlerin sıfır veya pozitif olması gerekir. Eğer amaç fonksiyonumuz en küçükleme olsaydı Zj – Cj satırındaki tüm değerlerin negatif veya sıfır olması gerekecekti. Yukarıdada görüldüğü gibi Zj – Cj satırındaki tüm değerler sıfır veya pozitif olduğundan en iyi çözüme ulaşmış oluruz. Böylece
Zenb = 15 , x2 = 5 , x3 = 0 , x4 = 25 , x1 = 0 , x5 = 35 olarak elde edilir.
Eğer bizim problemimizde Zj – Cj
satırındaki herhangi bir değer negatif olsaydı çözüm en iyi olmayacaktı. Bu durumda ise tekrar anahtar sütun, anahtar satır ve anahtar sayi değerlerini bulacaktık. Ardından tabloyu tekrar oluşturup buradaki gibi değerleri yeniden hesaplayıp çözümün en iyi olup olmadığını kontrol etmemiz gerekirdi. Çözüm en iyi olana kadar bu işlemleri yapmaya devam edecektik.
