Doğrusal programlama

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonunun doğrusal eşitlik ve/veya eşitsizlik kısıtlamalarını sağlayacak şekilde optimizasyon (yani amaç fonksiyonu değerinin en küçüklenmesi veya en büyüklenmesinin) yapılmasıdır. Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinin ağırlıklı toplamlarından oluşmalıdır.

Doğrusal (lineer) programlamadaki doğrusal (lineer) sözcüğü, modeldeki tüm matematiksel fonksiyonların doğrusal (lineer) olması gerektiğini belirtir. Programlama kelimesi ise bilgisayar programlama'ya işaret etmez; daha çok planlama ile eş anlamlıdır. Dolayısıyla doğrusal (lineer) programlama, birçok uygun alternatif arasından belirlenmiş bir hedefe uyan optimal çözümü bulacak aktivitelerin planlanmasını içerir.

Fazla matematiksel olmayan terimler ile, bir seri doğrusal eşitlik veya eşitsizlik şeklinde ifade edilmiş koşullara bağlı olarak (en küçük maliyet veya en büyük kâr gibi) en iyi sonuca varılmasıdır.

Genel olarak bir doğrusal programlama probleminde , ve matrislerinde sayısal değerler halinde problem başlangıcında verilir ve vektörü için sayısal değişken değerleri sonuç olarak, problem çözülmekle, bulunur.

Doğrusal programlama birçok pratik alanda kullanım sahası bulmaktadır. Özellikle birçok işletme ve ekonomi sorunlarına özel veya kamu sektöründe devamlı kullanılmaktadır. Nakliyat, enerji üretimi ve dağıtımı, telekomunikasyon, sınai üretim gibi teknik işletmecilik gerektiren alanlarında bulunan birçok firmalar doğrusal programlamayı çok kullanmaktadırlar. Doğrusal programlama işletmecilik alanlarında çok kapsamlı ve çok çeşitli sorunların çözülebilmesini sağlamaktadır. Bunlar sorunlar arasında planlama, yol gösterme, zaman programlaması, iş ve işçi tahsis edilmesi gibi önemli sorunlar doğrusal programlama kullanılarak modellenebilmektedir.

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.

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.

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.

Doğrusal programlama diğer şekiller de alabilir. Bunlardan birkaç örnek verelim: minimizasyon problemleri; değişik şekillerde ( veya = halinde) verilen kısıtlamalar; negatif değişken kapsayan problem vb. Bütün bu değişik şekiller uygun dönüşümler kullanılarak standart forma dönüştürülebilirler.

Bir doğrusal programlama problemi sınırsız veya uygunsuz bulunarak çözümsüz olabilir. İkincillik teoremine göre, eğer asılsal sınırsız ise, o halde zayıf ikincillik teoremine göre, ikincil problem uygunsuzdur. Aynı şekilde, eğer ikincil problem sınırsız ise, asılsal problem uygunsuz olacaktır. Ancak hem asılsal ve hem de ikincil problemlerinin uygunsuz olmaları da mümkündür.

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.

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.

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(n4L) 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 "dış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 çö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.

Dogrusal programlama pratik hayatta orta dönem veya uzun dönem optimizasyon problemlerinin (yani yoneylem araştırması terimlerini kullanırsak özel sektor veya devlet sektörü kurumlarının taktik ve stratejik problemlerinin) çözülmesi için uygulanmaktadır. Doğrusal programlamanın uygulanma alanı çok geniştir; girdi planlaması, üretim planlaması ve idaresi, insan kaynakları planlaması, dağıtım ve lojistik planlaması ve idaresi, pazarlama planlaması, finansman idaresi ve kontrolü alanlarında özellikle etkin sonuçlar ortaya çıkarırlar. Özellikle büyük tarım üretimi, ormancılık, sanayi sektörü; fabrika üretimi; petrol, gaz, elektrik, nükleer gibi enerji üretimi ve dağıtımı; kara nakliyat vasıtaları, demiryolu ve hava nakliyatı, telekomünikasyon, finansman sağlama vb kesimlerde kullanılmaktadır.