Bu yazı dizisinin ilkinde biraz bilimsel çalışıp bölümüm İstatistikteki derslerden biri olan Doğrusal Programlamada kullanılan bazı fonksiyon ve algoritmaları kodlamaya dönüştürmeye çalışacağım. En basit matematiksel olarak açıklayacak olursak birden fazla fonksiyonun ortak çözüm yapılarak isteğe bağlı max yada min olmasını sağlayacak değişkenleri yani (X1,X2,X3) leri bulmaya çalışacağız. Matamatiksel ifadeleri düzgün yazamadığımdan kusura bakmayın.
Ne demek istiyorum. Örneğin
Enb(X0) = 15X1 + 25X2
bu fonskyonu en büyük yapacak X1 ve X2 ile ilgileniyorum fakat kısıtlarım var
kısıt 1: 3X1 + 2X2 <= 12
kısıt 2: X1 + 2X2 <= 6
X1,X2 >= 0
Bu koşullar altında ana fonksiyonu en büyük yapcak X1 ve X2 bulmamız gerekmekte. Bunuda Simpleks Algoritmalar adı verilen matris yöntemleri ile yapmak mümkün. Öncelikle matris işlemlerinden başlayıp Simpleks Algoritmalarla bir problem nasıl çözülür yapmaya çalışacağım. Peki bu yöntemle ne gibi problemlere cevaplar verilebilir. Örnek bir kaç tane soru yazayım:
1. Bir işletmede tükenmez ve dolma kalem üretilmektedir. Üretimde, plastik dökümle şekillendirme ve parlatma olmak üzere iki önemli işlem olup, Üretim miktarı kg ile ölçülmektedir. Türlere göre kg başına harcanan süreler ve günlük kullanılabilir kapasiteler aşağıdaki gibidir.
Döküm Parlatma
Tükenmez 3 1
D. Kalem 2 2
Kapasite(saat) 12 6
Yapılan araştırma sonucuna göre kg başına dolma kalem karının 25 birim TL. Tükenmez kalem karının ise 15 TL olduğu anlaşılmış, talep ve stokların karararı etkilemediği bildirilmiştir.
Hangi kalemden ne kalemden ne kadar üretmeli ki karı en yüksek olsun?
2. Amerika'ya lisansüstü çalışmalar yapmak üzere giden Mehmet, iki kız arkadaş edinmiştir.
Bunlar Mary ve Nancy'dir. Mehmet'e göre;
a-) Mary olgun bir kızdır ve klasiklerden zevk almaktadır. Böyle bir yerde onunla 3 saat
birlikte olmak 12 dolara mal olmaktadır. Diğer taraftan Nancy daha çok popüler
eğlenceleri yeğlemektedir. Onunla böyle bir yerde 3 saat birlikte olmanın maliyeti de 8
dolardır.
b-) Mehmet'in bütçesi gönül işlerine ancak ayda 48 dolar ayırmasına olanak vermektedir.
Ayrıca, derslerinin ve çalışma koşullarının ağır oluşunda n dolayı, kız arkadaslarına en
fazla ayda 18 saatlik süre ve 40.000 kalorilik enerji ayırabilmektedir
c-) Mary ile her buluşmasında 5.000 kalori enerji harcayan Mehmet, Nancy için bunun iki
katını harcamaktadır. Eğer Mehmet'in Mary ile buluşmaktan beklediği mutluluğu 6 birim
ve Nancy ile buluşmaktan beklediği mutluluğun da 5 birim olduğunu biliyorsak,
mutluluğunu maksimize etmek isteyen Mehmet'in sosyal yaşamını nasıl planlaması
gerekecektir?
Bunun gibi soruları Simplex Algoritmalar yöntemleri ile kolay bir şekilde yapabiliriz. İlk olarak Delphi 'de matris nasıl oluştururuz ona bakalım. İki boyutlu matris oluşturmanın iki yolu var Delphi 'de bunlardan biri iç içe for döngüleri kullanarak herhangi bir yere kayıt etmek, örneğin bir StringGride. Bende uygulamada StringGridi kullanacağım. İstenirse veritabanı ClientDataSet 'e atarakta yapılabilir. Diğer bir yolda aslında olması gereken işlem yapacağımız ortam Arraylerdir. İki boyutlu bir Array tanımlayarak matris işlemlerimizi çok kolay bir şekilde yapabiliriz.
Öncelikle for döngüleri ile StringGride bir matris oluşturmayı deneyelim. Bunun için iki for döngüsü yeterli demiştik.
procedure TForm4.Button1Click(Sender: TObject);
var
j,k: Integer;
begin
k := 1;
for i := 0 to 3 do
begin
for j := 0 to 3 do
begin
StringGrid1.Cells[j,i] := inttostr(k);
k := k+1;
end;
end;
end;
Görüldüğü üzere StringGride iki for döngüsü kullanarak çok kolay bir şekilde bir matris oluşturduk. Fakat yapacağımız işlemlerin kolaylığı için bu oluşturduğumuz değerleri bir Array 'in içine alalım. Bunun için global bir Array tanımlayalım.
var
Form1: TForm1;
veriseti : array[0..3] of extended;
üçe üçlük bir array tanımlamış olduk. Bu arrayin içine veriler oluşurken aynı zamanda yazalım. Bunun için bir satır kod eklememiz yeterli yukardaki koda:
veriseti[j,i] := k;
Böylece 1 den 9 ' a kadar sıralı bir matris oluşturup bunu Array' in içine almış olduk.
Şimdi' de istenilen bir satır içinde en küçük değeri ve en küçük değerin pozisyonunu bulmaya çalışalım. Buradaki mantık matrisin ilk elemanını en küçük olarak kabul et ve ondan sonra gelen matris elemanları ile karşılaştır. Eğer ondan sonra gelen matris elemanı bizim en küçük değerimizden küçükse artık en küçük olarak bu elemanı kullan. Yani yer değiştiriyoruz.
procedure TForm4.Button5Click(Sender: TObject);
var
enk : extended;
begin
enk := veriseti[0,1];
for i := 0 to 3 do
begin
if veriseti[i,1] < enk then enk := veriseti[i,1];
end;
edit1.Text := FloatToStr(enk);
end;
yukardaki kod 1. satır içindeki en küçük değeri bulmamızı sağlamaktadır. Bu arada Array' lerde önce sütun sonra satır belirtilir yani veriseti[i,j] dersek i = sütun , j = satır demek oluyor.
Şimdide bütün matriste en küçük değeri bulmaya çalışalım.
procedure TForm4.Button6Click(Sender: TObject);
var
enk : extended;
begin
enk := veriseti[0,0];
for i := 0 to 3 do begin
for j := 0 to 3 do begin
if enk > veriseti[i,j] then enk := veriseti[i,j];
end;
end;
edit1.Text := FloatToStr(enk);
end;
Şimdide bulduğumuz en küçük değerin matriste hangi sütunda bulunduğunu bulmamız gerekiyor. Sadece bunları bilerek Simplex Algoritmaları oluşturabiliriz. En küçük elemanın hangi sütunda olduğunu bulmak için sayac kullanacağım. Mantık bulduğum en küçük değere eşit olmaması koşulu ile sayacı hep bir arttırmak.
sütun:=0;
while enk <> veriseti[i,0] do inc(sütun);
Bu kodu da ekledikten sonra artık en küçük değerin hangi sütunda olduğunu da bulmuş olurum. Şimdi Simpleks Algoritmaların çözüm aşamasına geçelim. Simpleks Algoritmaların nasıl çözüldüğü ile ilgili bir sunum en aşağıda mevcuttur indirebilirsiniz.
İlk önce temele girecek ve temelden çıkacak değişkenlerin bulunması gerekmektedir. Temele girecek değişkenin bulunması için ilk önce amaç fonksiyonumuzda en küçük olan değeri bulmalıyız. Bu değer bizim temele girecek değişkenimiz olacaktır. Bunu da aşağıdaki kod bloku ile yapabiliriz. Bir sonraki yazıda temelden çıkacak değişkeni ve yeni Simpleks tablonun oluşturulmasını anlatacağım.
Amaç Fonksiyonu
Enb Z = 2X1 + 3X2 + X3
Kısıtlar
2X1 + X2 + 3X3 <= 15
X1 + 4X2 + 2X3 <= 12
X1 , X2 , X3 => 0
Oluşturduğum örnek uygulamanın ekran çıktısı:
Şu an için uygulama birinci Simpleks tabloyu oluşturuyor. Bu uygun temel çözümlerden birisi fakat en iyi çözüm olduğu anlamına gelmiyor.
Simlex Algoritmamın Temele girecek sütununu bulmak için oluşturduğum kodlama:
global tanımlamalar:
var
Form1: TForm1;
i,j,satır,sütun : integer;
enk : extended;
veriseti : array[0..100,0..100] of extended;
amacfonk : array[0..100] of extended ;
kısıt : array[0..100,0..100] of extended ;
sabitler : array[0..100] of extended ;
amac fonksiyonumun en küçük değerini bulup temele girecek değişkenin bulunması:
enk := amacfonk[0];
for sütun := 0 to StringGrid3.ColCount - 1 do
if enk > amacfonk[sütun] then enk := amacfonk[sütun];
sütun := 0;
while enk <> amacfonk[sütun] do inc(sütun);
Label1.Caption := 'Temele girecek := ' + floattostr(sütun+1)+ '. Sütun';
Okuduğunuz İçin Teşekkür Ederim
Hakan UÇAR
İstatistikçi ve Amatör Programcı
İçerikler Tamamen Ücretsiz Olup Özgün Anlatımdır Paylaşırken Kaynak Belirtiniz Lütfen.
Simpleks Algoritma Çözümünün Nasıl Yapıldığı İle İlgili PowerPoint Sunumu:
0 yorum:
Yorum Gönder