Doğrusal programlama

Doğrusal programlamanın tarihçesi

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 eliminasyon yö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çıkça 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 çözüm algoritmasının, maliyetleri ve getirileri planlama suretiyle harp masraflarının kısılmasına yol açtığı açıkça 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'te 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.

Kullanım alanları

Doğrusal programlama yönteminin çok olmasına rağmen matematik için çok önemli olan optimizasyon alanında çok büyük bir rol oynamasında çeşitli nedenler vardır. Yöneylem araştırması alanında birçok pratik problem doğrusal programlama problemi olarak tanımlanmaktadır. Doğrusal programlamanın bazı özel hallerinin, örneğin ağ şebekelerinde akışım veya çoklu mal akışımı problemlerinin, o kadar önemli oldukları anlaşılmıştır ki özel problem çözüm şekilleri ve algoritmaları ortaya çıkartmak için bu özel problem alanlarına büyük araştırma çabaları yöneltilmiştir.
Diğer tipte olan optimizasyon problemleri için ortaya çıkartılan algoritmaların çoğu özel alt problem olarak doğrusal programlama çözümlerini kapsamaktadır. Matematik optimizasyon kavram ve yöntemlerinin geliştirilmesi için yapılan çalışmaların geçmişine bakılırsa, bunların en önemli olanlarının çoğunun (örneğin dualite, koveksite, bölünebilirlik ve daha genelleştirmeler) ilk defa doğrusal programlama için ortaya atılıp geliştirildiği aşikar olarak görülmektedir.
Aynı şekilde pratik alanlar olan işletmecilik ve mikroiktisat alanlarında etkin mal ve hizmet üretimi ve arzı için gelirleri maksimum hale getirmek veya maliyet ve masrafları minimum hale getirmek için, doğrusal programlama çok büyük katkılarda bulunmaktadır. Doğrusal programlamanın bu pratik alanlardaki kullanıldığı problemler arasında yiyecek maddelerinin harmanlanması, envanter kontrolü, insan ve makine kaynaklarının en iyi şekilde tahsis edilmeleri, ilan kampanyalarının planlaması, elektrik ve diğer enerji için toptan fiyatlama ve tahsis planlaması vb. bulunmaktadır.

Tamamlayıcı gevşeklik

Eğer sadece birincil problem için en iyi optimal çözüm biliniyorsa, ikincil problem için bir en iyi optimal çözümün elde edilmesi tamamlayıcı gevşeklik teoremini kullanmak suretiyle mümkün olur. Bu teorem şunu önerir:
x = (x₁, x₂, . . ., xₙ) birincil problem için olanaklı bir çözüm ve y = (y₁, y₂, . . . , yₘ)  ise ikincil problem için olanaklı bir çözüm olduğu kabul edilsin. (w₁, w₂, . . ., wₘ) birincil problem icçin gevşeklik değişkenler ve (z₁, z₂, . . . , zₙ) du bunlara karşıt ikincil problem için gevşeklik değişkenleri olsunlar. Bu halde x ve y kendileri için yukarıda anılmış problemler için en iyi optimal sonuç olmalariı, ancak ve ancak 
xⱼzⱼ = 0, for j = 1, 2, . . . , n,
wᵢyᵢ = 0, for i = 1, 2, . . . , m.
şartları gerçekleşirse ortaya çıkar.
Bu nedenle, eğer birincil problemdeki i'inci gevşeklik değişkeni sıfıra eşit değilse, ikincil problemde i'inci değişken değeri sıfıra eşit olur. Benzer şekilde, eğer ikincil problemdeki j'inci gevşeklik değişken sıfıra eşit değillerse, birincil problemde j'inci değişken değeri sıfıra eşittir.

Kuram

Geometrik olarak, doğrusal kısıtlayıcılar olanaklı yöre adı verilen bir içbükey polihedron belirtirler. Hedef fonksiyonu da doğrusal olduğu, yani bir konveks fonksiyon olduğu, için her yöresel en iyi optimum noktası, otomatik olarak, global en iyi optimal noktası olur. Bu öneri Karush-Kuhn-Tucker teoremininin uygulanmasına göre gerçekleşir. Hedef fonksiyonunun doğrusal olması en iyi optimal çözümlerin sonlu noktalar setinin bir konveks kabuğudur ve çok defa tek bir noktadan oluşur.
En iyi optimal çözüm noktasının bulunamadığı iki özel hal bulunmaktadır. Birinci özel halde, kısıtlamalar birbirleri ile tamamiyle çelişme halindedirler (Tam çelişme halindeki iki doğrusal kısıtlamaya örnegin x ≥ 2 ve x ≤ 1 olabilir). Bu halde olanaklı yöre boştur ve hiçbir çözüm bulunmadığı için en iyi optimal sonuç da yoktur. Bu halde, doğrusal programlama problemine olanaksız problem adı verilir.

Algoritmalar

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 çözüm 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ç çıkartmakta olduğu eldeki kullanma tecrübelerinden bilinmektedir. Fakat matematikçiler bilmektedirler ki bu çeşit yinelemeli (itiratif) çözüm çok büyük sayıda (hatta, üssel olarak artan sayıda) köşe incelemesi gerektirebilmektedir. Önceleri bilgisayar kullanarak bu çeşit yinelemeli çözüm problemlerinin sonlu bir zaman döneminde çözümlenemeyeceği (yani bu problemin P-karmaşıklık sınıfına dahil olduğu) şüphesi ortaya çıkmıştı. Fakat bu soruna yanıt, 1979'da "Leonid Khachiyan" adlı bir Sovyet Rus matematikçisi tarafından geliştirilen ve lineer programlama için ilk en-fena-halde-polinom-zaman algoritması olan elipsoid yöntemi'nin ortaya atılması ile açıklığa kavuşturulmuştur. Buna göre, n tane değişkeni olan ve L girdi "bit"leri ile enkodlanabilen bir problemin çözümlenmesi için, bu Khachiyan algoritması için  O(L) sayısal rakamlı O(n⁴L) aritmetik operasyon yapılması gerekmektedir. Bu çözümleme algoritması ("Arkadi Namirovski" tarafından önerilen "konveks optimizasyon" bulunması için  kullanılan elipsoid tekniğinin), "Naum Shor"  ve "D. Yudin" tarafından geliştirilmiş şekli ile uygulanmaktadır.
Fakat bu yeni algoritma doğrusal programlama üzerinde yeni matematiksel araştırmalara ilham kaynağı olmuş ve matematikçiler polihedronun sınırlarında dışından köşe köşe araştırmaya dayanan "dişsal çözüm"ler arama yerine polihedronun içinden gidişle en iyi dış koşeyi bulmaya dayanan "içsel nokta yöntemleri"ne dayanan algoritmalarla pratik cözüm usulleri geliştirmişlerdir. 1984'te "N.Karmarkar" bir "içsel nokta yöntemi"  olarak doğrusal programlama problemlerinin çözümü için Karmarkar Algoritması'nı ortaya atmıştır. Bu algoritma ile Khachiyan'ın teorik en-kötü-hal-polinom sınırı   ifadesine düşürülmüştür. Böylece simpleks algoritmasına nazaran pratik çözüm performansında gelişmeler ortaya çıkmıştır.
Uy

Uygulama Alanları

Dogrusal programlama pratik gercekte orta donem veya uzun donem optimizasyon problemlerinin (yani yoneylem arastirmasi terimlerini kullanirsak ozel sektor veya devlet sektoru kurumlarinin taktik ve strategi problemlerinin) cozulmesi icin uygulanmaktadir. Bu tip problemlerin bulunup uygulanma alanlari cok genistir ve girdi planlamasi, uretim planlanmasi ve idaresi, insan kaynaklari planlanamsi,  dagilim planlamasi ve idaresi, pazarlama planlamasi , finansman idaresi ve kontrolü  alanlarinda ozellikle etkin sonuclar ortaya cikarirlar. Ozellikle buyuk tarim uretimi, ormancilik, sanayi sektoru; fabrika uretimi; petrol, gaz, elektrik, nukleeer gibi enerji uretimi ve dagilimi; kara nakliyat vasitalari, demiryolu ve hava nakliyati, telekomunukasyon, finansman saglama vb kesimlerde kullanilmaktadir.