Yazan : Şadi Evren ŞEKER

Bu yazının amacı, daha önceden anlatılan doğrusal programlama (linear programming) konusunu, gerçek hayatta yaşanabilecek problemler ve bu problemlerin nasıl doğrusal denklemlerle modellendiğini örneklerle anlatmaktır.

Doğrusal programlama daha önce de bahsedildiği üzere birden fazla doğrusal denklem için en verimli, en iyi noktayı bulmayı hedefler.

Öncelikle bir problemin nasıl doğrusal denklemlerle ifade edildiğini bir örnek üzerinden görelim. Daha sonra farklı örneklerle konuyu anlamaya çalışacağız.

Örneğimizde bir üretici, 2 farklı üründen üretebiliyor olsun.

A1 ürünü için R1 kaynağından 1 birim ve R2 kaynağından 3 birim gerekiyor ve

A2 ürünü için R1 kaynağından 1 birim ve R2 kaynağından 2 birim gerekiyor olsun.

Ayrıca A1 ürününün satış değeri, 6 lira ve A2 ürününün 5 lira olsun.

Örneğin 5 birim R1 ve 12 birim R2 kaynağı bulunan bir üretici için, hangi üründen ne kadar üretmesi en fazla kâr elde edilmesini sağlar?

Bu soruyu çözmek için öncelikle problemi matematiksel olarak modellememiz gerekir.

Aşağıdaki gibi bir tablo yaparsak soruyu daha net görebiliriz:

Yukarıdaki tabloda hangi ürünün, hangi kaynaktan ne kadar gerektirdiği yazılmış ve son satırda, elimizde bulunan kaynak miktarı yazılmıştır.

Bu tabloyu hazırladıktan sonra, aşağıdaki denklemleri üretebiliriz.

X, A1 ürününden üretilen mal sayısı ve Y, A2 ürününden üretilen mal sayısı olmak üzere:

X + Y <= 5 olmalıdır. Çünkü iki üründe birer adet R1 gerektirmekte, dolayısıyla elimizdeki R1′den fazla üretemeyeceğimiz için en fazla 5 birim üretim yapabilmekteyiz.

Aynı şekilde 3X + 2Y <=12 olmalıdır.

Yazabileceğimiz diğer bir denklem ise X+Y>=0 olmasıdır. Bunun sebebi, üreticinin eksi miktarda mal üretememesidir.

Ayrıca kazancımızı, Z ile gösterecek olursak:

Z = 6X + 5Y şeklinde yazılabilir. Çünkü X ürünü 6 lira ve Y ürünü 5 liraya satılmaktadır.

Yukarıdaki denklemleri aşağıdaki şekilde listeleyebiliriz:

• X+Y<=5

• X+Y>=0
• 3X+2Y <= 12
• Z= 6X + 5Y

Görüldüğü üzere yukarıdaki denklemlerin tamamı y=ax + b şeklinde yazılabilecek doğrusal denklemlerdir. Konunun ismi olan doğrusal programlamanın da (linear programming) bir probleme uygulanabilmesi için bu yapıda bir problemle karşılaşılması gerekir.

Burada biraz terminolojiden bahsedecek olursak. Klasik bir OR (operations research, yöneylem) probleminde, ilk adım, problemin matematiksel olarak modellenmesidir. Bu modelleme sonucunda çıkarılacak iki önemli denklem grubu bulunur:

• Problemin kısıtları (Restriction)
• Problemin hedef fonksiyonu (objective function)

Yukarıdaki denklemlerden ilk 3 tanesi, problemin kısıtlarıdır. Yani X ve Y değerlerinin alabilecekleri limitleri belirlemektedir. Örneğin X>=0 veya Y>=0 olması gibi.

Son denklem ise hedef fonksiyonumuzdur. Bu fonksiyon bizim sonuçta azami değeri almasını istediğimiz hedefimizdir.

Yukarıdaki modellemeden görüldüğü üzere bir problemi doğrusal denklemlerle ifade edebiliyoruz. Şimdi farklı bir örnek üzerinden doğrusal programlamanın nasıl çalıştığını anlayalım.

Bir firmanın önümüzdeki 4 aylık satış beklentileri sırasıyla 1000, 800, 1200, 900 olarak beklenmektedir.

Firmanın normal üretim kapasitesi 800 birim iken aşırı üretim kapasitesi 200 birimdir. Normal üretimindeki birim maliyet 20 lira iken aşırı üretime girmesi durumunda, her aşırı üretim ürünü için 25 birim ödenmektedir.

Ayrıca her ürünün bir aylık depolama maliyeti 3 liradır.

Yukarıdaki problemi doğrusal olarak modellemeye çalışalım.

Öncelikle hedef fonksiyonumuzu (objective functions) yazarak başlıyalım:

X: normal üretim miktarı

Y: aşırı üretim miktarı

I: depolanan ürün miktarı olmak şartıyla

20X + 25Y + 3I değeri bize aylık olarak maliyetleri vermektedir. Dolayısıyla bizim beklentimiz, ön görülen üretimi karşılarken bir yandan bu maliyetleri asgari düzeye indirmektir. Dolayısıyla hedef fonksiyonumuz 20X+25Y+3I değerini minimize etmektir.

Bu problemdeki kısıtları yazacak olursak:

1. Ay için

X+Y = 1000 olmalıdır (ilk ay depolanan ürün olmadığını kabul ediyoruz)

Ayrıca diğer aylar için olan stok miktarları aşağıdaki şekilde formüllenebilir:

I1 = (X1 + Y1) – 1000

I2 = (X2 + Y2 + I1) – 800

I3 = (X3 + Y3 + I2) – 1200

I4 = ( X4 + Y4 + I3) – 900

Yukarıdaki denklemleri hedef fonksiyonumuz ile birleştirerek bir maliyet fonksiyonunu aşağıdaki şekilde yazabiliriz:

Görüldüğü üzere denklemimizde ilk fonksiyonumuzda olduğu üzere 3 değişken ve bu değişkenlerin aylık toplamları bulunmaktadır. Amacımız bu değerleri minimize etmektir.

Ayrıca aşağıdaki koşullarda yazılabilir:

0 ≤ X ≤ 800

0 ≤ Y ≤ 200

Bu koşullar da her ay için üretilen normal ve aşırı üretim miktarlarını belirlemektedir.

Şimdi yukarıdaki denklemleri açarak doğrusal programlamada uğraşılan denklemlerin yapılarını tanımaya çalışalım. Yapacağımız işlem, her denklemde, bir önceki denklemde bulunan değeri yazmak. Örneğin

I2 = (X2 + Y2 + I1) – 800

Denklemindeki I1 değeri daha önceden belirlenmiş bir değerdir. Bu değeri yerine yazarak başlayabiliriz:

I2 = (X2 + Y2 + (X1 + Y1) – 1000 ) – 800

I3 = (X3 + Y3 + (X2 + Y2 + (X1 + Y1) – 1000 ) – 800 ) – 1200

I4 = ( X4 + Y4 + (X3 + Y3 + (X2 + Y2 + (X1 + Y1) – 1000 ) – 800 ) – 1200 ) – 900

Her adımdaki denklemde bulunan I değeri, bir önceki denklemde bulunan değer ile değiştirilmiştir.

Dolayısıyla aslında minimize etmek istediğimiz değeri aşağıdaki şekilde yazabiliriz:

1,178 views