Simplex yöntemi denklemlerin tabloya yerleştirilip iterasyonların tablo üzerinden yapılmasına dayanan bir algoritmadır. Bu yöntem sınırlı optimizasyon problemlerinin ve mxn’lik kazanç matrisi ile ifade edilebilen oyun teorisi temelli problemlerin çözümünde kullanılır. Simplex algoritmasının uygulanması sonucunda oyun değeri ve strateji değerleri hesaplanabilir. Sınırlı optimizasyon problemlerinde ise istenilen maksimum kazanç ya da minimum zarar değerleri tablodan okunabilir. Bu algoritmanın çalıştırılabilmesi için öncelikle problemde verilen eşitsizlik denklemleri eşitlikler haline getirilmelidir. Bunun için denklemlere yapay değişkenler eklenir. Yapay değişkenlerin eklenmesinde denklemlerin eşitsizlik durumları önemlidir. Eğer problem için tanımlanan denklemlerin hepsi “<=” ya da “>=” ile ifade ediliyor ise problem tek katlı bir problemdir. Eğer problem denklemlerinde eşitsizliklerin ifadesinde “<=” ve “>=” kullanılmış ise bu problem çift katlıdır. Örneğin bir problem için tanımlanan aşağıdaki denklem grupları;
2x+4y <= 1500
2y-z <= 900
4a+3b-c >= 300
-a+2b >= 467
3c >= 125
tek katlı problemler ifade ederler,
2x-y >= 12
2x >= 8
3x+4y <= 58
ise çift katlı bir problem ifade eder. Buna göre yapay değişkenlerin eklenmesi ise aşağıdaki şekilde gerçekleştirilir.
2x+4y <= 1500 2x+4y+k = 1500
2y-z <= 900 2y-z+l = 900
4a+3b-c >= 300 4a+3b-c-x = 300
-a+2b >= 467 -a+2b-y = 467
3c >= 125 3c-z = 125
2x-y >= 12 2x-y-a+b = 12
2x >= 8 2x-c+d = 8
3x+4y <= 58 3x+4y+e = 58
Burada kırmızı renkte olanlar yapay değişkenlerdir. Mavi renkte olanlar ise ikinci yapay değişken ya da artık değişken olarak adlandırılır ve yalnızca çift katlı problemlerde eklenir. Problem denklemlerinde eşitsizliklerden kurtulduktan sonra problemin amaç fonksiyonuna bakılmalıdır. Verilen amaç fonksiyonunun maksimum veya minimum olması işlemlerin başlangıç şeklini değiştirmektedir. İşlemlere başlamadan önce değerlerin simplex tablosuna yerleştirilmesi gerekir. Maksimum problemlerinde amaç fonksiyonunun katsayıları tabloya negatif eklenir. Minimum problemlerinde ise amaç fonksiyonunun katsayıları tabloya pozitif olarak eklenir. Yukarıda verilen ilk denklem grubu örneği için amaç fonksiyonunu
x+y -> max
şeklinde belirlersek simplex tablosu aşağıdaki şekilde olacaktır.
| x | y | z | k | l | Çözüm | oranlar | |
| amaç fonksiyonu | -1 | -1 | 0 | 0 | 0 | 0 | |
| k | 2 | 4 | 0 | 1 | 0 | 1500 | |
| l | 0 | 2 | -1 | 0 | 1 | 900 |
Burada değerler değişkenlerin denklemlerdeki katsayılarıdır. Çözüm sütununa ise eşitliklerin sağ tarafında verilen değerler girilir. Çift katlı problemlerde ise bu tabloya ikinci bir amaç fonksiyonu sütunu eklenir ve burada sadece artık değişkenin değeri “1” olarak girilir. Yukarıda verilen çift katlı problem ifade eden örnek için amaç fonksiyonunu
x+3y -> min
şeklinde belirlersek simplex tablosu aşağıdaki şekilde olacaktır.
| x | y | a | b | c | d | e | çözüm | oranlar | |
| amaç Fonk. | 1 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | |
| yapay amaç fonk. | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | |
| b | 2 | -1 | -1 | 1 | 0 | 0 | 0 | 12 | |
| d | 2 | 0 | 0 | 0 | -1 | 1 | 0 | 8 | |
| e | 3 | 4 | 0 | 0 | 0 | 0 | 1 | 58 |
Burada satırlara, çift yapay değişken eklenen denklemler için yapay değişkenlerden pozitif olanı yazılmıştır. Simplex tablosu oluşturulduktan sonra algoritma adımları aşağıdaki şekildedir.
Maksimum problemi için ;
- Amaç fonksiyonu satırından asıl değişkenler içerisinde minimum değere sahip olanı seçilir.
- Seçilen değerin bulunduğu sütundaki pozitif değerlerin çözüm sütununda aynı satırda bulunan değere oranları hesaplanır.
- Hesaplanan oranlarda minimum olan seçilerek bu satır ile seçilen sütunun kesişimindeki değer “1” yapılır. Belirlenen satıra seçili olan sütunun adı verilir.
- Seçilen sütunda bulunan diğer elemanlar Gauss Eleminasyonu işlemleri ile “0” yapılır.
- Amaç fonksiyonu satırındaki asıl değişken değerleri pozitif olana kadar bu işlemler tekrar eder ve eğer bu satırda yapay değişken değerlerinden negatif olanları var ise aynı işlemler minimum olanı seçilerek onlar için de tekrar eder. Anlaşıldığı üzere işlemler öncelikle asıl değişkenler için yapılır.
Minimum problemi için ;
- Amaç fonksiyonu satırından asıl değişkenler içerisinde maksimum değere sahip olanı seçilir.
- Seçilen değerin bulunduğu sütundaki pozitif değerlerin çözüm sütununda aynı satırda bulunan değere oranları hesaplanır.
- Hesaplanan oranlarda minimum olan seçilerek bu satır ile seçilen sütunun kesişimindeki değer “1” yapılır. Belirlenen satıra seçili olan sütunun adı verilir.
- Seçilen sütunda bulunan diğer elemanlar Gauss Eleminasyonu işlemleri ile “0” yapılır.
- Amaç fonksiyonu satırındaki asıl değişken değerleri “0” olana kadar bu işlemler tekrar eder ve eğer bu satırda yapay değişken değerlerinden negatif olanları var ise aynı işlemler minimum olanı seçilerek onlar için de tekrar eder. Anlaşıldığı üzere işlemler öncelikle asıl değişkenler için yapılır.
Çift katlı problemlerde öncelikle yapay amaç fonksiyonu satırındaki “1” olan değerler yani artık değişken sütunları ile kesişimindeki değerler Gauss Eleminasyonu ile 0 yapılır. Bu işlemden sonra problemin türüne göre yukarıda verilen adımlar öncelikle yapay amaç fonksiyonu için gerçekleştirilir. Adımların durdurulması için gerekli koşullar yapay amaç fonksiyonu için sağlandığında yapay amaç fonksiyonu satırı ve artık değişkenlerin sütunları tablodan çıkarılır. Geriye kalan tabloda tek katlı problem gibi devam edilerek simplex adımları uygulanır. İterasyonlar tamamlandığında sonuç tablosunda amaç satırının çözüm sütunundaki değer bize amaç fonksiyonunda istenilen değeri verir. Diğer satırlardaki değişkenlerin çözüm sütunu değerleri ise bu değişkenlerin istenilen sonuca varılması için olması gereken değerlerini verir.
Adımları daha iyi anlamak için bu uygulamayı kullanabilirsiniz -> İndirmek için tıklayınız.
Bir yanıt yazın