Genelleştirilmiş Problemler

En genel haliyle, bir doğrusal programlama problemi belli sayıda aktivitelerin hangisinden ne kadar yapılacağı sorusuna yanıt arar.

Aktivitelerin (daha iyi bir terim olmadığına göre) "miktarları" problemin değişkenleridir. Problemin oluşturulmasında ilk adım aktivitelerin ve onlara bağlı değişkenlerin tanımlanması ve adlandırılmasıdır. Bir kaç örnek sunacak olursak,

• Bir üretim tesisi için

  • üretim aktivitelerine bakarsınız;

  • değişkenler farklı ürünlerin üretim adet, lot veya ton sayıları, veya üretimlerine harcanan makine/işçilik saatleridir.

• Bir satış mağazası için

  • satış aktivitelerine bakarsınız;

  • değişkenler farklı ürünlerin satış adet, paket, kilo tutarlarıdır, hatta belki de ürünlere ayrılan raf alanlarıdır.

• Taşeron işçi çalıştıran bir işletme için

  • işçi atama aktivitelerine bakarsınız;

  • değişkenler işçilerin farklı işlerdeki günlük/haftalık çalışma saatleri veya farklı işlere atanan işçi sayıları olabilir.

• Kirlilik ölçümleri yapan bir sanayi tesisi için

  • kirliliğe katkısı olan imalat aktivitelere bakarsınız;

  • değişkenler bu imalat aktivitelerinin miktar veya saatleridir.

Bu ve benzeri örneklerde aktivitelerin (her ne şekilde ölçüyorsanız) miktarlarını

x₁, x₂, x₃, ... , x_j

gibi sembollerle ifade edersiniz.

Bir doğrusal programlama probleminde bir de "performans fonksiyonu" ya da "hedef fonksiyon" vardır. Bu fonksiyon "iyileştirmeye" çalıştığınız bir hedef değişkeni aktivitelerle ilgili değişkenlere doğrusal olarak bağlamalıdır. Bağlantı doğrusal değilse zaten problem bir doğrusal programlama problemi değildir.

Genelde Z sembolüyle temsil edilen hedef değişkenin neye karşılık geldiği problemin kaynağına bağlıdır. Yukarıdaki örneklere devam edecek olursak,

• Bir üretim tesisi için hedef değişken

  • toplam satış geliri,

  • toplam üretim maliyeti,

  • üretimden kaynaklanan toplam kirlilik, vb. olabilir.

• Bir satış mağazası için hedef değişken

  • toplam satış kârı,

  • kullanılan toplam raf alanı,

  • toplam satış elemanı sayısı, vb. olabilir.

• Taşeron işçi çalıştıran bir işletme için hedef değişken

  • işlere atanan toplam işçi sayısı,

  • işverenlerden alınan toplam komisyon,

  • gönderilen işçilerin toplam başarısı (nasıl ölçerlerse artık) vb. olabilir.

• Kirlilik ölçümleri yapan bir sanayi tesisi için hedef değişken

  • toplam çevre kirliği olabileceği gibi,

  • resmi denetleme kurumlarının tesbit edip belirlediği toplam ceza tutarı olabilir. (Amaç yapmamak değil de yakalanmamak ise)

Hedef değişkeni aktivite değişkenlerine bağlayan (doğrusal) performans fonksiyonunun genel ifadesi aşağıdaki gibi olacaktır:

Z = c1 x1 + c2 x2 + … + cnxn

Bu fonksiyondaki c_i aktivite katsayıları aktivitelerin hedef değişkene, yani performansa katkılarını ifade ederler.

• Hedef değişken olarak toplam üretim maliyetini seçen bir üretim tesisi için aktivite katsayıları farklı ürünlerin adet/lot/ton başına üretim maliyetleridir.

• Hedef değişken olarak toplam kârı seçen bir satış mağazası için aktivite katsayıları farklı ürünlerin adet/paket/kilo başına net kârlarıdır.

• Hedef değişken olarak işveren komisyonu seçen bir taşeron işçi firması için aktivite katsayıları farklı işverenlerden işçi başına veya işçilik saati başına alınan komisyon tutarıdır.

• Hedef değişken olarak çevreye yayılan toplam kirliliği seçen bir sanayi tesisi için aktivite katsayıları üretim saati veya tonu başına ortaya çıkan kirletici madde miktarıdır.

Bir doğrusal programlama probleminin amacı performans fonksiyonunundan elde edilebilecek "en iyi" hedef değişken değerini belirlemektir. En iyi değer duruma göre en yüksek (maksimum) ya da en düşük (minimum) değer olabilir. Maliyeti düşürme amacıyla çözülen bir problemde hedef değişken maliyettir ve en düşük değer hedeflenmiştir. Yüksek kâr amacıyla çözülen bir problemde hedef değişken toplam kârdır ve en yüksek değer hedeflenmiştir. Kirliliği azaltma amacıyla çözülen bir problemde hedef değişken toplam kirliliktir ve en düşük değer hedeflenmiştir. vs. vs.

Tabi, problemin amacı aslında mümkün olan en yüksek veya en düşük değeri belirlemektir. Bunun için de problemin sunumunda belirtilen sınırlamaları ifade eden kısıtların formülleri oluşturulmalıdır. Sınırlamalar aktivitelerde kullanılan (makine saati, tesis alanı, işçi sayısı, vb.) kaynakların kullanılabilirlik sınırlarıdır. Kaynak kullanımları da aktiviteleirn miktarlarına doğrusal fonksiyonlarla bağlı olmalıdır (yoksa problem zaten bir doğrusal programlama problemi değildir).

Kaynakların kullanım sınırlamalarını b₁, b₂, b₃, ... b_i sembolleriyle temsil edersek,

kısıtları da bu sınırlamanın altında ya da üstünde kalması gereken şöyle doğrusal eşitsizliklerle ifade ederiz:

a11 x1 + a12 x2 + … + a1nxn ≤ b1

a21 x1 + a22 x2 + … + a2nxn ≥ b2

…

am1 x1 + am2 x2 + … + amnxn ≤ bm

En genel haliyle, bir doğrusal programlama probleminin amacı hedef değişkenin maksimizasyonu (en yüksek değerinin belirlenmesi) değil de minimizasyonu (en düşük değerinin belirlenmesi) olabileceği gibi, performans ve kısıt ifadelerindeki katsayılar ve izin verilen değişken değerleri vb. de negatif olabilir. Ne var ki o tür farklılaşmalarda çözüm yöntemleri de farklılaşabilir. Biz, en azından elle çözüm örneklerinde, çoğunlukla pozitif değişken değerleriyle deneyeceğimiz maksimizasyon problemlerine odaklanacağız.