Doğrusal programlamanın tarihçesi

[iGrand]

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 eşitsizlikler sistemi şeklindeki bir problemin incelenmesi ta Fourierin çalışmalarına kadar dayanmaktadır ve bu tanınmış matematikçi anısına Fourier-Motzkin eliminasyonyöntemi şeklinde isimlendirilmiştir.
1920'lerde Sovyet Rusya'da tüm ekonomi planlaması konuları pratikte ön plana geçmişken teorik olarak tüm ekonominin nasıl planlanabileceğini göstermek için yapılan teorik çalışmalar arasında Leonid Kantoroviç'in katkısı ilk defa bir doğrusal programlama probleminin açıkca ortaya çıkarılmasına yol açmıştır. Ne yazık ki teorinin pratik planlamaya uygulanmasının imkânsızlığı ve ideolojik nedenler dolayısıyla Kantroviç'in bu çalışmasının önemi ancak II. Dünya Savaşından sonra anlaşılabilmiştir.
II. Dünya Savaşı sırasında Birleşik Amerika'da ortaya çıkan lojistik tahsis sorunlarını incelemek için kurulan bir araştırma grubu, grup başkanı olan George Dantzig etrafında, bu türlü sorunların çözülmesi için doğrusal programlama probleminin tanımlanması gereğini ortaya çıkartmışlar ve bu türlü doğrusal programlama problemlerinin çözümü için simpleks algoritması adını verdikleri bir çözüm sistemi ortaya atmışlardır. Özelikle bu matematik modelin ve çözum algoritmasının, maliyetleri ve getirileri planlama suretiyle harp masraflarının kısılmasına yol açtığı açıkca görüldüğü için bu teorik ve pratik gelişmeler 1947'ye kadar devlet sırı olarak saklı kalmıştır. 1947'de John von Neumann, özellikle oyunlar teorisi ile de ilgileniyorken, ikincillik teorisini geliştirmiştir.
Bu zaman kadar doğrusal programlamaya yaptıkları katkılar nedeni ile Kantoroviç, Dantzing ve von Neumann'a 1975'de Nobel Ekonomi ödülü verilmiştir.
1947'den sonra özellikle geliştirilen bilgisayar uygulamaları ile birlikte özellikle büyük özel sanayi birimleri ve büyük devlet projeleri için birçok doğrusal programlama problem tanımlanmış ve simpleks algoritması ile çözülüp pratikte kullanılmaya başlanmıştır. Örneğin petrol rafine şirketlerinin günlük üretim planlamaları ve çok girdili ve çok çıktılı üretim karışımı planlamaları için doğrusal programlama çözümlerini devamlı olarak kullanmaya başlamışlardır.
1979'da Leonid Haciyan doğrusal programlama probleminin polinom zaman içinde çözülebileceğini ilk defa ispat etmiştir. Fakat bu alanda çok daha önemli teorik ve pratik gelişmeler 1984'te Narendra Karmarkar'ın doğrusal programlama problemlerin çözülmesi için (simpleks algoritması yerine) içsel nokta yöntemi ortaya atması ile başlamıştır.
Doğrusal programlamanın pratik yararlılığı bu yöntemin ilk kullanılma problemlerinden biri olan ve Dantzig tarafından ortaya atılan 70 kişinin 70 göreve, karar verici kuruma en iyi sonuç çıkaracak şekilde, tahsis edilmesi örneğinin biraz daha ayrıntılarına bakmak suretiyle anlaşılabilir. Eğer çözüm için her mümkün tahsisi teker teker elden geçirip her biri için amaca yaptığı katkıyı bulmak deneyimine girişilirse, bu kadar çok büyük sayıda permutasyonun elden geçirilmesinin imkânsız olduğu hemen açığa çıkar; çünkü gerekli permütasyon sayısı bütün yakın evrende bulunan parçacıkların sayısına yaklaşır. Eğer bu problem doğrusal programlama şeklinde belirtilip en iyi çözümü bulma kararı verirsek, en zor ve zaman alıcı çabanın probleminin çözümünde değil problemin programa girdisinin hazırlanmasında olduğu anlaşılır. Bu problemin bilgisayarla simpleks algoritması kullanılarak çözülmesi göz kırpma zamanı bile almaz. Doğrusal programlama kuramı arkasında bulunan teori, kontrol edilmesi gereken mümkün en iyi çözüm sayısını çok etkili şekilde azaltmaktadır.