YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 2: Doğrusal Programlama Modelleri: Grafik Çözüm
En İyileme Problemleri İçin Çözüm, Uygun Çözüm, En İyi Çözüm Kavramları
Bir karar probleminin çözüm süreci, çeşitli uygun çözüm alternatifleri içinden amacımıza veya amaçlarımıza en çok uyan uygun çözümün seçilmek istendiği durumda ortaya çıkar. Birden fazla alternatif uygun çözümlerin var olduğu bir durumda, eğer uygun çözümlerin hepsini, amacımız doğrultusunda, tek tek kıyaslayabilme şansına sahipsek, kıstaslarımıza en çok uyan uygun çözümü, bütün uygun çözümleri ikişer ikişer kıyaslayarak, kolayca seçebiliriz.
Eğer incelemekte olduğumuz problemin kıstaslarını sağlayan uygun çözüm yoksa bu problemin çözümü yoktur demektir. Eğer problemin kıstaslarını sağlayan tek bir uygun çözüm dışında başka alternatif uygun çözümler yoksa bir karar problemi de yoktur demektir: Tek seçenek- tek çözüm. Bu durumlarda uygun çözümleri, problemde hedeflenen amaç doğrultusunda kıyaslayarak en iyi çözümü bulabiliyoruz. Fakat maalesef gerçek hayatta, bütün problemlerde uygun çözümler, sayılabilecek kadar sonlu sayıda olmayabilir.
Bir matematiksel programlama probleminin tüm kısıtlarını sağlayan seçeneklere uygun çözümler denir. Uygun çözümler içerisinde amaç fonksiyonunun en iyi değere ulaştığı seçeneğe problemin çözümü veya en iyi çözümü denir. Sözel olarak tarif edilen bir problemde, problemin koşullarını sağlayan uygun çözümler, sayılamayacak kadar çok sayıda olduğu bir durumda, bu problemin en iyi çözümünün bulunabilmesi için problemin matematiksel modelinin kurulması büyük önem arz etmektedir.
Doğrusal Programlama Problemlerinin Varsayımları
Bir doğrusal programlama probleminin sağlaması gereken varsayımları vardır. Problemlerde bazı özellikler doğrusal bir bağlantı şeklinde matematiksel olarak ifade edilebilirken, bazı özellikler doğrusal bir bağlantı ile ifade edilemez. Bu özellikler, orantılılık, toplanabilirlik, bölü- nebilirlik ve belirlilik olarak sıralanabilir.
• Orantılılık: Bir karar problemi incelendiği zaman, öncelikle bu problemin ortaya çıktığı işletme veya sistem kapsamlı bir şekilde, yöneylem araştırması ekibi tarafından analiz edilir. Bu aşamada, yani sistem analizi aşa- masında öncelikle bu problemi oluşturan çeşitli parametrelerin değerleri belirlenir. Bu aşamada neyin yapılmak istendiği, hangi hedefin veya amacın tutturulmak istendiği ve bunun için sistemin sahip olduğu imkânlar, kapasite ve ham madde bilgileri, birim üründen elde edilecek kâr miktarı ve benzeri bulgular analiz edilerek ortaya çıkartılır. Bu bulguları hesaplamak ve karar problemini matematiksel olarak formüle edebilmek için genellikle karar değişkenleri olarak adlandırılan değişkenlerin tanımlanması
matematiksel modelin oluşturulması açısından büyük önem arz eder. • Toplanabilirlik: Örneğin işletme iki ürünün satışından elde edeceği toplam kârı en büyüklemek istemekte ve bunun için her bir üründen ne kadar üretilmesi gerektiğine karar vermek istemektedir. Bunlardan birincisinin üretileceği toplam miktar diğerininki ise olsun. Varsayalım ki, işletmede yapılan sistem analizi sonucu ortaya çıkan parametre değerlerine göre, birinci ürünün birim miktarından elde edilen kâr miktarı, ikinci ürünün birim miktarından elde edilen kâr miktarı ise olsun. Bu durumda orantılılık özelliğine göre birinci ürünün tamamından elde edilecek kâr miktarı, ikinci ürünün tamamından elde edilecek kâr miktarı ise olacaktır. Belli bir sürece ürünlerin toplam katkısı, bu ürünlerin bireysel katkılarının toplamından oluşmaktadır. • Bölünebilirlik: Karar değişkenleri, problemin kısıtlarını sağlayan tam sayı ve tam olmayan sayılar dâhil her türlü reel sayı değerini alabilir olmalıdır. Yani, bir doğrusal karar modelinde, bir karar değişkeninin her türlü tam ve küsuratlı değeri alabilmesi karşısında bir engel bulunmamalıdır. • Belirlilik: Bir doğrusal karar probleminin tanımlanması sırasında belirlenen tüm parametrelerin değerleri bilinen sabitlerden ibaret olmalıdır. Yukarıdaki örnekte kullanılan, “birinci ürünün birim miktarından elde edilen kâr miktarı olsun” şeklindeki bilgi, problemde ortaya çıkan tüm parametreler için benzer şekilde belirlenmiş olmalıdır.
Matematiksel Model
Bir problemi araştırmak ve çözüme kavuşturabilmek için, problemin sözel tarifini çok iyi incelememiz, söz konusu problemin içinde bulunduğu sistemi çok iyi analiz etmemiz gerekiyor. Böyle bir analiz, öncelikle problemin olmazsa olmaz koşullarını, hedeflerini, amaçlarını ve bu problem kapsamındaki tüm veriyi, bir başka deyimle, problemin tüm parametrelerinin titizlikle belirlenmesinden başlar.
Problemle ilgili tüm parametreler belirlendikten sonra bu problemde neyin bulunmak istendiği sorusunu cevaplamamız gerekiyor. Yöneylem Araştırması ile en önemli olan bilgileri seçip ayırabilmek ve problemde en iyi karara ulaşmak için neyin yapılmak istendiği, hangi bulguların ortaya çıkarılması gerektiğini hesaplanmalıdır. Bu araştırma bizi karar değişkenlerine götürecektir. Bir karar probleminin en önemli bileşenlerinden biri de karar değişkenleridir.
Karar değişkenleri belirlendikten sonra, problem kapsamında tarif edilen kıstasların, bu karar değişkenleri ve problemin parametreleri kullanılarak formüle edilmesi gerekiyor. Bu kısıtlamalar, problemin incelendiği sistemde
kullanılabilecek makine, enerji, ham madde miktarları, mevcut iş gücü, üretim ve depo alanı ve benzeri koşullardan oluşabilir. Problem kapsamında tarif edilen bu gibi özel koşulların, problemin karar değişkenleri ve parametreleri kullanılarak matematiksel eşitlik ve/veya eşitsizlikler şeklindeki ifadelerine problemin kısıtları denir.
Bir karar probleminin en önemli bileşenlerinden biri de problemin amaç fonksiyonudur. Bir problem kapsamında tarif edilen ve tutturulması veya en iyilenmesi istenen hedef, amaç ve ya amaçların, problemin karar değişkenleri ve parametreleri kullanılarak oluşturulan matematiksel ifadesine, bu problemin amaç fonksiyonu denir.
Bir karar probleminin bir diğer bileşeni de problemin uygun çözümleridir. Bir karar probleminin bütün kısıtlarını sağlayan karar değişkeni değerine veya karar değişkenlerinin değerlerinden oluşan bir vektöre (dizine) bu problemin uygun çözümü denir. Bir karar probleminin en iyi çözümünün veya çözümlerinin incelenmesinin veya bulunmasının yolu, uygun çözümlerin kıyaslanmasından geçer.
Uygun çözümlerin hangisinin daha iyi olduğu sorusunun cevabı, aslında hangisinin, problemin amaç fonksiyonuna daha iyi değer sağladığının araştırılmasından geçer. Amaç fonksiyonuna sağladığı değere göre daha iyi olduğuna karar verdiğimiz çözüm, bir sonraki aşamada diğer çözümlerle kıyaslanır, diğeri ise elenir. Amaç fonksiyonuna en iyi (en büyük veya en küçük) değeri sağlayan uygun çözüme problemin en iyi çözümü denir.
Bir karar probleminin tüm verileri ve parametreleri kullanılarak, problemin kıstas ve koşullarının ve amaç ve hedeflerinin matematiksel semboller, eşitlikler ve eşitsizlikler kullanılarak ifade edilişine bu problemin matematiksel modeli denir. Modelleme, işi rakamlara dökmeden önce problemi “hissetme” ile başlar. Herhangi bir işletmede oluşan bir problemin en iyi çözümünün bulunabilmesi için, önce problemi yöneticileri tarafından dinlemek, onların hassas oldukları noktaları belirlemek, problemin tüm detaylarını, verilerini, parametrelerini ve ne istendiğini araştırmak ve tespit etmek gerekmektedir. Bu analiz sonucunda ortaya çıkan parametreler, girdi ve çıktı bilgileri, karar değişkenleri, kısıtlar ve amaç veya amaçlar, matematiksel modelin oluşturulmasında bize yardımcı olacaktır.
Grafik Çözüm Yöntemi
Grafik yöntem, problemin uygun çözümler kümesinin ve amaç fonksiyonunun grafiksel olarak gösterilmesi ve amaç fonksiyonunun en büyüklenmesi veya en küçüklenmesine bağlı olarak uygun çözümlerin geometrik yorumlarla araştırılmasına dayanıyor. Önceki bölümlerde incelediğimiz örneklerin bazılarında en iyi çözümü direkt kıyaslama yöntemi ile bulabilmiştik. Aslında bu tür kıyaslamanın, uygun çözümlerin tamamını kıyaslayarak elemenin mümkün olmadığı durumlarda bile genel bir çözüm yöntemi hakkında ipuçları içermektedir.
Grafik yöntemi, bir problemin matematiksel modelinin geometrik olarak nasıl resimlenebileceği, problemi tanımlayan amaç fonksiyonu ve fonksiyonel ve küme kısıtlarının grafiklerinin kullanılarak uygun çözüm alanının ve bu alanda en iyi çözümün bulunması olarak ta tanımlanabilir.
Grafik yöntemini bir örnek ile açıklamak yararlı olacaktır.
Örnek: Bir işletme sosis, salam ve kavurma üretimi yapmaktadır. Bu ürünlerin üretimi için ana ham madde olarak et kullanılmaktadır. İşletme, et alımını iki farklı tedarikçiden temin etmekte ve ürettiği ürünleri satarak faaliyetini sürdürmektedir. İşletmede üretim ve pazarlama birimleri ile birlikte bir araştırma yapan YA ekibi, farklı tedarikçilerden alınan etler arasında kalite farkı bulunduğunu tespit ediyor (içerdikleri yağlılık oranı, kemik oranı vb.) ve aşağıdaki birim üretim bilgilerini hesaplıyor:
1. tedarikçiden alınan 1 ton etten 0.2 ton sosis, 0.2 ton salam, 0.4 ton kavurma üretilmekte ve geri kalan 0.2 ton et (sinir ve kemikler) fire olarak değerlendirilmektedir.
2. tedarikçiden alınan 1 ton etten 0.3 ton sosis, 0.1 ton salam, 0.4 ton kavurma üretilmekte ve geri kalan 0.2 ton et fire olarak değerlendirilmektedir.
• Problemin çözümünde öncelikle kârın en büyüklenmesi için her bir tedarikçiden ne kadar et alınması gerektiği şeklinde formüle edilen problemin matematiksel modeli çıkartılır. • Matematiksel modeller için tek tek geometrik gösterimler grafik yöntemi ile yapılır. Ve her grafikteki alanlar hesaplanır. • Daha sonra bu grafikler tek bir grafikte birleştirilir. Bu grafikte artık kısıtlar belirlenir. • Amaç fonksiyonunda karar değişkenlerinin katsayıları değişkenler için olabildiğince büyük sayıların seçilerek, amaç fonksiyonunun da değeri büyültülür. Bu uygun çözüm için fonksiyonumuzun değeri hesaplanır.
Amaç fonksiyonu Enb z = ax + by şeklinde, uygun çözüm alanı da bir K kümesi şek-linde tarif edilen bir doğrusal programlama probleminin en iyi çözümünü bulmak için, (0,0) noktası ile (a,b) noktasından geçen vektöre dik doğruyu, K kümesinde (a,b) vektörü yönünde kaydırarak, K kümesini en son terk ettiği noktayı bulmak yeterlidir. Eğer böyle bir nokta varsa, bu nokta problemin en iyi çözümüdür. Eğer doğru sınırsızca kaydırıldığında uygun çözüm alanını terk etmiyorsa, amaç fonksiyonu üstten sınırsızdır ve problemin en iyi çözümü yok-tur demektir. En küçükleme probleminin en iyi çözümünü bulmak için (0,0) noktası ile (a,b) noktasından geçen vektöre dik doğruyu, K kümesinde (a,b) vektörünün tersi yönünde kaydırarak, K kümesini en son terk ettiği noktayı bulmak gerekiyor.