DOĞRUSAL PROGRAMLAMA

Doğrusal programlama tekniği kısıtlı kaynaklarla en uygun sonucun alınmasında kullanılan bir karar verme aracı olarak tanımlanabilir. Doğrusal programlama tekniğinin iki temel dayanağı söz konusudur. Bunlar doğrusallık ve sınırlılıktır. Bir problemin doğrusal programlama problemi olabilmesi bu iki özelliğine bağlıdır. Kaynakların sınırsız olduğu koşullarda optimizasyon (eniyileme) anlamsızdır. Diğer taraftan doğrusal programlama problemlerinin tanımlanmasında üç unsurdan bahsedilebilir. Birincisi amaç fonksiyon, ikincisi karar değişkenleri, üçüncüsü ise kısıtlardır. Bir problemin doğrusal programlama problemi olarak tanımlanabilmesi bu unsurların doğrusal fonksiyon olarak tanımlanabilmesi ve yazılabilmesine bağlıdır. Doğrusal modellerin çözümü ile ilgili ilk çalışmalar 19. yüzyılın başlarında gerçekleştirilmiştir.

Ancak doğrusal programlamanın uygulamaları açısından esas gelişim gösterdiği dönem İkinci Dünya Savaşı yıllarıdır. Savaş döneminde özellikle İngiltere’deki komuta merkezinin başta lojistik ve savunma olmak üzere, birçok optimizasyon probleminin çözümü için doğrusal modelleri geliştirme çabası sadece doğrusal programlamanın değil, aynı zamanda o yıllarda "Harekat Araştırması" olarak adlandırılan günümüzde ise "Yöneylem Araştırması" disiplininin temellendirilmesinde de büyük bir rol oynamıştır.

Doğrusal programlama askeri, endüstriyel, ekonomik ve sosyal faaliyetler başta olmak üzere pekçok hayati süreçte kendisine uygulama alanı bulmuştur. Zaman içerisinde doğrusal programlama önceleri savaş döneminde Atlantik'te seyreden gemilerin seyir biçiminin, Londra hava savunması için uçaksavar bataryalarının yerleşim düzeyinin eniyilenmesi problemlerine çözüm ararken, günümüzde mal ve hizmetlerin üretiminde girdilerin enazlanıp, gelir ve faydanın ençoklanması gibi temel iktisadi sorunlara ışık tutar olmuştur. Doğrusal programlama, birçok problemin çözümünü araştırırken gelişmiş ve sorunların niteliğine göre birçok şekilde farklı yaklaşım ve türev modellerinde ortaya çıkmasını sağlamış ve böylelikle, günümüzde yöneylem araştırmasının belli başlı çalışma sahalarından biri haline gelmiştir.

Bu bağlamda tamsayılı doğrusal programlama, karmaşık tamsayılı programlama, hedef programlama, ulaştırma ve atama modelleri, şebeke modelleri, karar ağaçları, veri zarflama analizi gibi pekçok model ve yaklaşımın geliştirilmesinde ve uygulanmasında temel teşkil etmiştir. Tüm bunlar gözönüne alındığında günümüzdeki pekçok yönetimsel problemlerin anlaşılmasında doğrusal programlama modelinin anlaşılması büyük bir önem arzetmektedir.

Doğrusal programlama modelinin temel gösterimi, yazının girişinde de belirtildiği gibi, bir amaç fonksiyonu (temel doğrusal programlama için sadece bir adet amaç fonksiyonu), n adet kısıt fonksiyonu ve negatif olmama koşuluna sahip karar değişkenleri olmak üzere üç unsurdan oluşmaktadır. Bir doğrusal programlama modeli;

Amaç Fonksiyonu (Maksimum veya minimum olmak üzere 1 adet) :

Kısıt fonksiyonları (n adet) :

Karar değişkenleri (negatif olmama koşulu altında) :                          

                                                               ,    , ....., 

şeklinde ifade edilebilir.

Doğrusal programlama modelini bir örnek üzerinde uygulamaya çalışalım. Bir kimya işletmesi bir X ürünü üretmektedir. Üretmekte olduğu bu ürüne ait üretim sürecindeki parametreler aşağıdaki gibidir.                       

İşletmenin ürünü, litresi sırası ile 16 TL., 20 TL. ve 25 TL. olan A, B ve C ara mallarından elde edilebilmektedir. Bu üç ara malın özellikleri aşağıdaki gibidir:

Üretici, yukarıdaki koşullara uygun olarak ürününü en düşük maliyetle üretmek istemektedir. Bu veriler ışığında model şu şekilde olacaktır.

Karar Değişkenleri

x₁ = Üründeki A oranı

x₂ = Üründeki B oranı

x₃ = Üründeki C oranı

Doğrusal programlama modelinin çözümü için günümüzde iki tane geçerli yöntem bulunmaktadır. Bunların ilki, grafik çözümüdür. Analitik düzlemde geometik yöntemi kullanarak uygun çözümü bulmaya çalışan yöntemdir. Ancak, temelde iki karar değişkeni ile sınırlıdır. Diğeri ise daha genel geçer ve jenerik bir çözüm yöntemi olan Simpleks (Simplex) algoritmasıdır. 1947 yılında Amerikalı matematikçi George Dantzig tarafından geliştirilmiştir. Grafik yöntemin gelişkin modelleri kapsamaması dolayısıyla grafik çözüm yöntemine burada değinilmeyecektir. Simpleks yöntemi, özellikle günümüzün yüksek hesap kapasitesi ve araçlarını kullanılmasına uygunluğu açısından burada temel özellikleriyle verilecektir.

Yöntem cebirsel iterasyon işlemine dayanır. Yöntemde önce başlangıç simpleks tablosu düzenlenir sonra tekrarlayıcı işlemler ile belirli bir hesap yöntemi içinde gelişen çözümlere doğru ilerleyerek optimal çözüme ulaşıncaya kadar işlemler sürdürülür. Başlangıç tablosunun standard formda ifade edilbilmesi için, modelde şu üç hususa dikkat edilmelidir.

1. Tüm kısıt fonksiyonlarını teşkil eden eşitsizlikler eşitlik haline getirilmelidir.

2. Amaç fonksiyonu sadece maksimum veya sadece mininum yönlü olmak üzere düzenlenir.

3. Bütün karar değişkenleri 0'dan büyük pozitif olmalıdır.           

Amaç Fonksiyonu

Kısıt Fonksiyonu 1 :

Kısıt Fonksiyonu 2 :

Kısıt Fonksiyonu 3:

Kısıt Fonksiyonu 4:

Kısıt Fonksiyonu 5:

Simplex Çözüm Değerleri:

Barış Tamer AKYILMAZ