Doğrusal Programlama

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonun doğrusal eşitlikler ve eşitsizlikler kısıtlamaları ile optimizasyon 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 programlamaya 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. Doğrusal programlama birçok pratik alanda kullanım sahası bulmaktadır. Özellikle birçok işletme ve ekonomi sorunlarina özel veya kamu sektörunde 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 kullanamaktadı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 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. 1920lerde Sovyet Rusyada 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 Kantoriviç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. İkinci Dünya Savaşı sırasında Birleşik Amerikada 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 1947ye kadar devlet sırı olarak saklı kalmıştır.

1947de John von Neumann, özellikle oyunlar teorisi ile de ilgileniyorken, dualite teorisini geliştirmiştir. Bu zaman kadar doğrusal programlamaya yaptıkları katkılar nedeni ile Kantroviç, Dantzing ve von Neumanna 1975de Nobel Ekonomi ödülü verilmiştir. 1947den 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. 1979da 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 1984te 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 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 çözum ş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. Standart şekil Bir doğrusal programlama probleminin tanımlanması için en uygun ve alışılmış olan şekline standart şekil adı verilmektedir.

Bu standart şekilde bir doğrusal programlama problemi üç özel parçadan oluşmaktadır. Her doğrusal program problemi bir genel standart doğrusal program problemine (yani kanonik şekile) dönüştürülebilir. Matematiksel olarak bir genel standart doğrusal program problemi basitçe bir şekilde şöyle ifade edilir.