YÖNEYLEM ARAŞTIRMASI I - Deneme Sınavı - 14

Özellikle son elli yıldır büyük ölçekli projelerde uygulanabilen Yöneylem Araştırması teknikleri konusunda, GANTT Diyagramı denen teknik en eskiler arasındadır. 1958’de Amerikan Deniz Kuvvetleri Özel Projeler Bölümü tarafından, PERT (Project Evaluation and Review Technique), hemen hemen aynı zamanlara rastlayan Kritik Yol Yöntemi ise (CPM-Critical Path Method), Dupont Kimyevi Madde Fabrikası’nda bakım onarım faaliyetlerine yardımcı olmak üzere geliştirilmiştir. Bu teknikler çoğunlukla zaman esaslı faaliyetlerin programlanması problemlerinde uygulanmaktadırlar. CPM-PERT’de bir projeye ait tüm faaliyetler tanımlanır, aralarındaki öncüllük-ardıllık ilişkileri belirlenir ve projeye ait bir şebeke çizilir.

Doğrusal programlama, belirli bir amaca ulaşmak için, bazı kısıtlayıcılar altında kıt kaynakların en verimli şekilde kullanılmasını sağlayan bir matematiksel yöntemdir. Bu şekilde varılmak istenen amaç, kâr maksimizasyonu (en büyükleme) veya maliyet minimizasyonu (en küçükleme) olarak belirlenebilir.
Doğrusal programlamada “doğrusal” sözcüğü, fonksiyonların doğrusallığını, “programlama” ise planlama işlemini ifade etmektedir.

Doğrusal programlamanın uygulama alanları :
• Ulaştırma ve lojistik problemleri,
• Endüstriyel üretim planlaması ve envanter (stok) kontrolü
• Personel programlaması
• Beslenme(diyet) problemleri
• Karışım problemleri
• Tarımsal planlama
• Finansal planlama
• Yatırım planlaması
• Sağlık sistemleri
• Askeri planlama
• Trafik planlaması
• Atama problemleri
• Reklam seçimi problemleri
• Karışım problemle

Doğrusallık (Oranlılık) Varsayımı: Modelin amaç fonksiyonu ve kısıtlayıcı fonksiyonları ile ilgilidir. Doğrusallık varsayımı, işletmenin girdileri ile çıktıları arasında doğrusal bir ilişkinin olduğunu gösterir. Üretim düzeyi artarken aynı oranda üretim girdileri de artar. Eğer, Xj’inci eylem için amacın oluşumu doğrusallık özelliği gösteriyorsa, Xj’nin her bir birim değerinin kara katkısı cj iken, Xj’nin çözüm değerinin amaca katkısı cjXj kadar olur. Bunun yanında karar
problemine esas olan bi’inci kaynaktan her bir birim Xj için gerekli kaynak miktarı aij olmak üzere Xj için kaynak gereksinimi aijXj kadar olur. Kısıtlar ve amaç fonksiyonu birinci dereceden fonksiyon olmalıdır.
Aksi takdirde, doğrusal olmayan programlama söz konusu olur. Bu varsayım, her bir karar değişkeninin; gerek amaç fonksiyonu, gerekse tük kısıtlayıcılara etkisinin söz konusu değişkenin (Xj ) değeriyle doğru orantılı olması gerektiğinin ifade eder.

Doğrusal programlama modelindeki tüm parametrelerin (amaç fonksiyonu katsayıları-cj, sağ taraf sabitleri-bi ve teknoloji katsayıları- aij) biliniyor olduğu varsayımıdır. Parametre değerlerini kesin olarak biliniyor olması varsayımı, modelin deterministtik model olduğunun göstergesidir

Model doğrusal programlama gibi standart bir matematiksel model halinde ifade edilebiliyorsa, bilinen algoritmalar yardımıyla çözüme ulaşılabilir. Bir problemin, doğrusal programlama modeli kurulurken önce karar değişkenleri tanımlanır, sonrada amaç fonksiyonu ve kısıtlayıcılar formüle edilir.

Herhangi bir doğrusal programlama probleminde karar verici, karar değişkenlerinin bazı fonksiyonunu maksimum veya minimum yapmak ister. Maksimum veya minimum yapılmak istenen fonksiyona, amaç fonksiyonu adı verilir. Doğrusal programlama modelinden beklenen sonucun alınabilmesi için, amacın açık olarak bilinmesi ve nicel olarak yazılımı gerekmektedir.

Kısıtlayıcıların sağ taraf sabitlerini oluşturan bi’ler  elverişli kaynak miktarını gösterir. Bu kaynak miktarları kısıtlayıcı fonksiyonuna göre her zaman sınırlı olmaz. Bazen karar değişkenlerinin istediğinden fazla veya tam eşitlikte olabilir. Bu nedenle kısıtlayıcı denklemler, “=” eşitlik şeklinde olabileceği gibi, eşitsizlik şeklinde de olabilir. Eşitsizlik durumu, yukarıda görüldüğü gibi “≤” (küçük eşit) şeklinde olabileceği gibi, “≥” (büyük eşit) şeklinde de olabilir.

Kısıtlayıcılardaki karar değişkenlerinin katsayıları (aij), farklı ürünlerin üretiminde kullanılan teknolojiyi yansıttığı için, teknolojik katsayılar adı verilir.

Üretim Planlaması : Doğrusal programlamanın en yaygın kullanıldığı alanlardan birisi, üretim işletmelerin de maksimum karlı veya minimum maliyetli üretim bileşenlerini belirlemede kullanılmasıdır.

Herhangi bir doğrusal programlama probleminde karar verici, karar değişkenlerinin bazı fonksiyonunu maksimum veya minimum yapmak ister.  minimum yapılmak istenen fonksiyon genellikle maiyet fonksiyonudur. Doğrusal programlama modelinin amacı en az maliyetle en fazla kar elde etmektir.

Uygun Çözüm Alanı dışbükey(konveks) bir alandır. Dışbükey alanın temel özelliği, bu alan içinde iki nokta ele alınıp bir doğru parçasıyla birleştirildiğinde, birleştiren doğru parçasının tamamının alan
kalmasıdır. Bir anlamda Uygun Çözüm Alanı kümesindeki herhangi iki nokta çiftini birleştiren doğru parçası, tamamen Uygun Çözüm Alanı kümesinde ise, uygun çözüm alanı dışbükey (konveks ) kümedir.

Uç(köşe) Nokta Teoremi: Grafik üzerinde Uygun Çözüm Alanının (UÇA) farklı iki noktasının dışbükey birleşimi olarak yazılamayan noktası varsa, buna uç nokta veya köşe nokta denir. Düzlemde bir üçgenin, bir karenin köşeleri uç (köşe) noktadır. Şu halde, amaç fonksiyonu maksimizasyon (en büyükleme) veya minimizasyon (en küçükleme) yönünde olan bir doğrusal programlama modelinin:
i. Eğer modelin optimum (en iyi) çözümü varsa, bu çözüm Uygun Çözüm Alanının bir köşe noktasındadır.
ii. Amaç fonksiyonu optimum (en iyi) değerini birden çok köşe noktasında alıyorsa, bu noktaların her dışbükey birleşimi de optimum(en iyi) çözümdür

Modelin iki karar değişkeni olduğunda, kısıtların her biri düzlemde bir doğru oluşturur. Bu doğrunun ikiye ayırdığı düzlemin bir bölgesi, ilgili kısıttı sağlayan (X1, X2)‘i değerlerini verir. Modelin tüm kısıtlayıcı fonksiyonları aynı koordinat sisteminde çizilerek, her bir kısıttın sağlanan bölgeleri taranırsa, kısıtları birlikte gerçekleştiren (X1, X2) ikilileri, yani “Uygun Çözüm Alanı(UÇA)” taranmış bölge olarak ortaya çıkar.

X1, ve X2 değişkenlerinin çözüm değerlerinin anlamlı olabilmesi için, negatif olmayan değer almaları gerekir. Olası çözüm değerleri Ürün I ve Ürün II’den üretilecek miktarları gösterecekti.Bunun yanında X1≥ 0, yatay eksenin(apsis) üst tarafını, X2≥ 0 dikey eksenin (ordinat) sağ tarafını işaret eder ki, bu da koordinat ekseninin I.Bölgesidir

Bir doğrusal programlama modelinin tüm kısıtlarını sağlayan her X vektörüne,
X=[X1,X2, … Xj, … Xn]
uygun çözüm denir. Uygun çözümlerin oluşturduğu kümeye, Uygun Çözüm Alanı (UÇA) denir. Uygun Çözün Alanı = {X | AX≤b, X≥0 }
Burada, A- matris ve b- sütun vektörüdür.

Doğrusal karar modelinin optimum çözümünü bulmak için öncelikle Uygun Çözüm Alanının(UÇA) belirlenmesi gerekmektedir. İlk adımda modelin kısıtlayıcıları olan doğrusal eşitsizliklerin grafiğini çizmek gerekir. Bütün doğrusal programlama modellerinde negatif olmama kısıtlayıcıları (X1, X2≥ 0) bulunduğundan, öncelikle bu kısıtların doyurulması ile başlamak gerekir. Koordinatlar ekseninde uygun çözüm alanının hangi bölümde yer aldığı belirlenir. Örnek modeldeki X1(Ürün I’den üretilecek miktar) genellikle apsis (yatay) ekseninde, X2(Ürün II’den üretilecek miktar),ordinat (düşey) ekseninde gösterilir.

Doğrusal programlamada optimum çözüm her zaman, Uygun Çözüm Alanının köşe noktalarındadır. Amaç fonksiyonunun  en büyük değer aldığı belirlenerek, optimum çözüme ulaşılır. Bunun için köşe noktalarının her birinin, (X1, X2) değerleri amaç fonksiyonunda yerine konur. Hangi uç noktada amaç fonksiyonunu en yüksek değer yapıyorsa uygun çözüm o dur.

Uygun Çözüm Alanında minimizasyon amacına en uygun köşe olarak orijine en yakın köşe olacaktır.

Karar modelinin kısıtlarının grafiği çizildiğinde, uygun çözüm alanı oluşmuyor (boş) ise, problemin çözümü yoktur denir.