- Katılım
- 29 Eyl 2012
- Konular
- 6,428
- Mesajlar
- 13,741
- Reaksiyon Skoru
- 502
- Altın Konu
- 0
- TM Yaşı
- 13 Yıl 8 Ay 16 Gün
- Başarım Puanı
- 340
- Yaş
- 29
- MmoLira
- -382
- DevLira
- 0
ROHAN2 WORLD 1-120 TR TİPİ OFFICIAL YOHARA, BALATHOR VE AMON! 80. GÜNÜNDE! +10.000 ONLİNE! HİLE VE BOT %100 ENGELLİ HEMEN TIKLA!
Doğrusal programlama problemlerinin pratik olarak çözümlenmesi için ilk kullanışlı algoritma George Dantzig ve Rand Corp. özel araştırma ekibinin ortaya attığı simpleks algoritmasıdır. Bu algoritma kısıtlamalardan ortaya çıkan düzeyleri birçok değişirli polihedron (iki değişkenli problemde "uygunluk alanı") olarak görmekte ve bu polihedronda kesişme noktalarını yani polihedron köşelerini (iki değişkenli problemde kısıtlama çizgilerinin kesişme noktalarını) birer mümkün çözüm olarak görmektedir. Bundan sonra bir köşeden başlayıp bu köşeyi tayin eden kenarlar takip edilerek amaç fonksiyonun iyileşmesini sağlayan kenarlar teşhis edilmekte; bunlardan amaç fonksiyonuna en iyi sonuç çıkaracak kenar takip edilip bir diğer polihedron köşesi bulunmaktadır. Bu yeni bulunan polihedron köşesi de aynı usul kullanılarak daha iyi bir başka köşeye gidebilme imkânı aranmaktadır. Eğer elde bulunan bir polihedron köşesinden daha iyi amaç sonuç sağlayan bir köşeye gitme imkânı yoksa, bu son köşe optimum çözum olarak kabul edilmektedir.
Genel olarak çok büyük sayıda değişkenli ve çok büyük sayıda kısıtlamalı pratik doğrusal programlama problemlerinde bu polihedron üzerinde köşeden köşeye gidiş yönteminin, eğer köşeden köşeye gidişlerin "dalgalanma"larını önlemek için özel itina gösterilirse, etkin ve global bir optimum sonuç cikartmakta olduğu eldeki kullanma tecrübelerinden bilinmektedir. Ama matematikçiler bilmektedirler ki bu çeşit yinelemeli (itiratif) çözüm çok büyük sayıda (hatta , üssel olarak artan sayıda) kose incelemesi gerektirebilmektedir. Önceleri kompüter kullanarak bu çeşit yinelemeli çözüm problemlerinin sonlu bir zaman döneminde çözümlenemiyeceği (yani bu problemin P-karmaşıklık sınıfına dahil olduğu) şüphesi ortaya çıkmıştı.
Fakat bu soruna yanit, 1979da "Leonid Khachiyan" adli bir Sovyet Rus matematikcisi tarafindan gelistirilen ve lineer proglamlama icin ilk en-fena-halde-polinom-zaman algoritmasi olan elipsoid yontemi'nin ortaya atilmasi ile acikliga kavusturulmustur. Buna gore, n tane degiskeni olan ve L girdi "bit"leri ile enkodlanabilen bir problemin cozumlenmasi icin, bu Khachiyan algoritmasi icin O(L) sayisal rakamli O(n4L) aritmetik operasyon yapilmasi gerekmektedir. Bu cozumleme algoritmasi ("Arkadi Namirovski" tarafindan onerilen "konveks optimazasyon" bulunmasi icin kullanilan elipsoid tekniginin), "Naum Shor" ve "D.Yudin" tarafindan gelistirilmis sekli ile uygulanmaktadir. Khachiyan'in algoritmasi ve Shor-Yudin gelistirmeleri, ve bunlarla dogrusal programlama problemlerin cozumlenme isbatlari matematik teorisi bakimindan cok onemli merhaleler oldugu suphesizdir. Fakat pratikte bu yeni algoritma, ozel olarak suni olarak gelistirilen dogrusal programlama problem gruplarini cozme haricinde, pratik dogrusal programlama problemleri cozumu icin daha onceki "simpleks algoritmasi" 'nin yerini almamistir.
Fakat bu yeni algoritma dogrusal programlama uzerinde yeni matematiksel arastirmalara ilham kaynagi olmus ve matematikciler polihedronun sinirlarinda disindan kose kose arastirmaya dayanan "dissal cozum"ler arama yerine polihedronun icinden gidisle en iyi dis koseyi bulmaya dayanan "icsel nokta yontemleri"ne dayanan algoritmalarla pratik cozum usulleri gelistirmislerdir. 1984de "N.Karmarkar" bir "icsel nokta yontemi" olarak dogrusal programlama problemlerinin cozumu icin Karmarkar algoritmasi'ni ortaya atmistir. Bu algoritma ile Khachiyan'in teoretik en-kotu-hal-polinom siniri
ifadesine dusurulmustur. Boylece simpleks algoritmasina nazaran cok dramatik sekilde pratik cozum perfomansinda gelismeler ve kolayliklari ortaya cikartmistir. Daha sonra bicok diger "icsel nokta yontemi" ortaya atilmistir. Bunlkaradn cogu "afin iskalasi kurulmasi" teorisine dayanmaktadir. Son zamanlarda ise "baraj fonksiyonu" veya "patika takipciligi" teorilerine dayanan "icsel nokta yontemi" algoritmalari onerilmistir.
Uygulamali matematikcilerin en son dusuncelerine gore, pratik endustriyel sorunlar icin dogrusal programlama kullanilmasinda, duzgun kullanma icin gelistirilmis simpleks algortmasi ile icsel-nokta yontemi kullanan algoritmalar arasinda pek gercek fark bulunmamaktadir.
Genel olarak çok büyük sayıda değişkenli ve çok büyük sayıda kısıtlamalı pratik doğrusal programlama problemlerinde bu polihedron üzerinde köşeden köşeye gidiş yönteminin, eğer köşeden köşeye gidişlerin "dalgalanma"larını önlemek için özel itina gösterilirse, etkin ve global bir optimum sonuç cikartmakta olduğu eldeki kullanma tecrübelerinden bilinmektedir. Ama matematikçiler bilmektedirler ki bu çeşit yinelemeli (itiratif) çözüm çok büyük sayıda (hatta , üssel olarak artan sayıda) kose incelemesi gerektirebilmektedir. Önceleri kompüter kullanarak bu çeşit yinelemeli çözüm problemlerinin sonlu bir zaman döneminde çözümlenemiyeceği (yani bu problemin P-karmaşıklık sınıfına dahil olduğu) şüphesi ortaya çıkmıştı.
Fakat bu soruna yanit, 1979da "Leonid Khachiyan" adli bir Sovyet Rus matematikcisi tarafindan gelistirilen ve lineer proglamlama icin ilk en-fena-halde-polinom-zaman algoritmasi olan elipsoid yontemi'nin ortaya atilmasi ile acikliga kavusturulmustur. Buna gore, n tane degiskeni olan ve L girdi "bit"leri ile enkodlanabilen bir problemin cozumlenmasi icin, bu Khachiyan algoritmasi icin O(L) sayisal rakamli O(n4L) aritmetik operasyon yapilmasi gerekmektedir. Bu cozumleme algoritmasi ("Arkadi Namirovski" tarafindan onerilen "konveks optimazasyon" bulunmasi icin kullanilan elipsoid tekniginin), "Naum Shor" ve "D.Yudin" tarafindan gelistirilmis sekli ile uygulanmaktadir. Khachiyan'in algoritmasi ve Shor-Yudin gelistirmeleri, ve bunlarla dogrusal programlama problemlerin cozumlenme isbatlari matematik teorisi bakimindan cok onemli merhaleler oldugu suphesizdir. Fakat pratikte bu yeni algoritma, ozel olarak suni olarak gelistirilen dogrusal programlama problem gruplarini cozme haricinde, pratik dogrusal programlama problemleri cozumu icin daha onceki "simpleks algoritmasi" 'nin yerini almamistir.
Fakat bu yeni algoritma dogrusal programlama uzerinde yeni matematiksel arastirmalara ilham kaynagi olmus ve matematikciler polihedronun sinirlarinda disindan kose kose arastirmaya dayanan "dissal cozum"ler arama yerine polihedronun icinden gidisle en iyi dis koseyi bulmaya dayanan "icsel nokta yontemleri"ne dayanan algoritmalarla pratik cozum usulleri gelistirmislerdir. 1984de "N.Karmarkar" bir "icsel nokta yontemi" olarak dogrusal programlama problemlerinin cozumu icin Karmarkar algoritmasi'ni ortaya atmistir. Bu algoritma ile Khachiyan'in teoretik en-kotu-hal-polinom siniri
Uygulamali matematikcilerin en son dusuncelerine gore, pratik endustriyel sorunlar icin dogrusal programlama kullanilmasinda, duzgun kullanma icin gelistirilmis simpleks algortmasi ile icsel-nokta yontemi kullanan algoritmalar arasinda pek gercek fark bulunmamaktadir.
