simplex metodu

endüstri mühendisliğinde modelleme ve optimizasyon dersi altında görmüş olduğumuz metot. doğrusal bir modelin çözümü için geliştirilmiş metottur. amaç fonksiyonu ve kısıtlardan oluşan bir doğrusal modelde kullanılabilir. daha öncesinden model nasıl kurulur ? anlatılmaktadır. ben bunu burda anlatmayacağım. direkt olarak örnekle anlatacak olursam;

en küçük Z=2x1-3x2
x1+x2<=4
x1-x2<=6

1- ilk adımımız verileri standart forma dönüştürmek olacaktır. burda kısıtlara bakılır.

>= var ise -e+a eklenir. e fazla değeri, a(artificial) problemi çözmemiz için gereken fiziksel olarak var olmayan, yapay değişkeni gösterir.

<= var ise +s(slack) eklenir.

= var ise +a eklenir.

kısıtlarımız;

x1+x2+s1=4
x1-x2+s2=6

olur.

2- tablo oluşturulur. tablo oluşturulurken zj-cj satırımız yani en çok veya en az denklememizin yazıldığı satır genelde (-) çarpılarak yazılır. genelde diyorum çünkü (-) ile çarpılmadanda yapılabiliyor.

*******x1**x2**s1**s2**S.D.***O.T
zj-cj***-2**+3**0***0
s1*****1***1***1***0***4****4/1
s2*****1***-1***0***1***6****6/-1

s.d.=sağ taraf değişkenleri
o.t.=oran testi

3- zj-cj satırında en küçük problemlerinde en büyük pozitif sayı, en çok problemlerinde en küçük negatif sayının olduğu sütun seçilir.
burda en küçük problemini incelediğimiz için en büyük pozitif sayı olan 3'ün bulunduğu sütun seçiliyor.

4- sağ taraf değişkeni seçilen sütuna bölünerek oran testi yapılıyor. oran testinde sıfır, negatif ve sonsuz dışında pozifit olan en küçük sayının olduğu satır seçiliyor. ve kesiştikleri yer bize pivot elemanı veriyor.
burda 4'ün bulunduğu s1 satırı seçiliyor ve kesişimindeki 1 pivot elemanımız oluyor.

pivot eleman ise, çözüme girecek x2 sütunu ile, çözümden çıkacak s1 satırının kesiştiği 1 değeri belirlenecektir.
yeni tablo değerlerini bulmak için ise, öncelikli olarak pivot satırında bulunan sayılar, pivot eleman bölünerek, yeni oluşan değerler tablo 2 pivot satırına yerleştirilir.

çözüme giren değişken birim matrisin bir elemanı olacağından dolayı, x2 birim matris olacak şekilde satırlar arasında aritmetik işlemlere devam edilir, yeni tablodaki zj-cj satırı elemanlarını bulmak için tablo 1 deki pivot satırı (-3) çarpılır ve tablo 1 deki zj-cj satırı elemanları ile toplanır.

*******x1**x2**s1**s2**s.d.***z
zj-cj***-5***0**-3***0****bi***-12
0******1***1***1***0****4****x2=4
0******2***0***1***1****10***s2=10

simplex metot ile bir adım ilerleme tamamlanmış ve sıra bulunan çözümüm en iyi çözüm olup/olmadığının test edilmesine gelmiştir. test için, zj-cj satırı değerlerine bakılır amaç fonksiyonumuz en küçük olduğu için, adımları tamamlamak için değerlerin tamamının sıfır veya negatif olması gerekecektir.
tablo 2 deki zj-cj satırının elamanları arasında pozitif değer olmadığı için en iyi çözüme ulaşılmış ve çözüm tamamlanmış olduğuna karar veririz. modelin çözümünde tablo 2 de görüldüğü gibi

çözüme giren x2 =4 ve s2=10
çözüme girmeyen x1=s1=0

ve amaç fonksiyonunun değeri de -12 olarak bulunur.
eğer, ilk satırda bütün çözümde olan değişkenlerin katsayısı pozitif ise, optimal sonuç bulunmuştur. eğer pozitif değer var ise, en büyük pozitif değer seçilir ve çözüme girer.

not=sözlüğün boşlukları yok etmesinden dolayı tablo berbat olmuştur. uğraşıp bir ara resmini koyarım şimdi çalışmam gerekiyor.

not2= boşluk problemini yıldız koyarak çözmeye çalıştım.

(bkz: burda alın teri var)