YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 1: Yöneylem Araştırmasına Giriş
Yöneylem Araştırmasının Kısa Tarihçesi
Yöneylem Araştırmasının (YA), bir bilim dalı olarak ilk defa İkinci Dünya Savaşı yıllarında sistemli bir şekilde uygulandığı fikri kesinlik kazanmıştır. Savaş esnasında, sınırlı kaynakların çeşitli askerî operasyonlarda etkin bir şekilde kullanılması probleminin çözülmesi için önce İngiliz, daha sonra ABD yönetimi tarafından çok sayıda bilim insanı bir araya getirilmiştir. Bu bilim insanlarının oluşturduğu ekip tarafından, üzerinde çalışılan askerî operasyonlar için matematiksel modeller geliştirilerek en iyi çözümlerin hesaplanması için bilimsel yöntemler uygulanmıştır.
YA, bir bilim dalı olarak sistemli bir şekilde İkinci Dünya Savaşı’ndan sonra gelişmeye başlasa da daha önce de bazı problemlerin çözümlenmesi için sade sayılabilecek matematiksel modeller önerilmişti. 1937 yılında Von Neyman, 1939 yılında ise Kantoroviç tarafından, ekonomi problemlerinin çözümlenmesi için doğrusal matematiksel modeller önerilmiştir.
1947 yılında George Dantzig, YA dalında çok önemli bulgu olan, doğrusal programlama problemlerinin çözümü için “simpleks yöntemi” geliştirdi. SCOOP (Scientific Computation of Optimal Programs – Optimal Programların Bilimsel Yöntemlerle Hesaplanması) Projesi, bir Pentagon-temelli (Amerika Birleşik Devletleri) projedir. Hava Kuvvetleri Araştırma Grubu, 1947 yılında oluşturuldu. Bu program planlaması, aslında kaynak kısıtlamalarını aşmadan amaçları en iyi şekilde karşılayan bir programın belirlenmesi için bir biri ile rekabet eden ve bir biri ile bağlantılı aktivitelerin seçilmesi problemi idi.
Programlama problemleri, hedeflenen amaçların karşılanabilmesi için sınırlı kaynakların etkin bir şekilde kullanımı ile alakalıdır. Bu tip problemlerin tipik örnekleri olarak ham petrolden çeşitli yakıt türlerinin elde edilmesi için yapılması gereken rafineri işlemlerini, tedarikçilerden fabrikalara malzeme sevkiyatı problemini, taleplerin karşı- lanacağı şekilde bir üretim planlama problemini gösterebiliriz:
• Ax ≤ b, x ≥ 0 kısıtları altında Enbüyükle (veya Enküçükle)
1950’li yıllardan itibaren teorik ve uygulamalı matematiksel programlama bilim dalında sağlanan önemli gelişmeler, sanayide ve ekonomide karşılaşılan büyük boyutlu problemlerin matematiksel modellerinin geliştirilmeye başlanması, bu problemlerin en iyi çözümlerinin karakterizasyonu alanında elde edilen önemli teorik bulgular ve çözümlerin hesaplanması için geliştirilen yöntemler, yöneylem araştırmasının önemini ve rolünü daha da artırdı.
Tarihçeden de görüleceği üzere, Yöneylem Araştırması teori ve yöntemleri hayatımızın her alanında kullanılan ve uygulanan bir bilim dalıdır. Bu tarihçeden edindiğimiz belki de en önemli sonuç, günümüzde ister ekonomide olsun ister askeriyede, ister bankacılıkta olsun ister
sanayide, sağlık sektöründe veya sosyolojide, hiçbir fikrin veya teorinin matematiksel modeli kurulmadan ve en iyi veya en iyiye yakın çözümü bulunmadan, inandırıcılığının kabul edilmediğidir. Hayatımızın hangi alanında olursa olsun, kıt kaynakların amaçlarımız doğrultusunda en etkin bir şekilde kullanılması her zaman önemlidir, zira kaynaklar hangi alanda olursa olsun her zaman sınırlıdır.
Yöneylem Araştırması, Matematiksel Programlama ve Doğrusal Programlama Problemleri
Matematiksel Programlama teriminde yer alan “programlama” kelimesi, Bilgisayar Programlamada kullanılan “bilgisayar programı” veya “bilgisayar kodu” kelimesi ile karıştırılmamalıdır. Her ne kadar anlam itibarıyla bu terimler birbirine yakın olsalar da Matematiksel Programlamada kullanılan “programlama” kelimesi, belli bir hedefe ulaşmak veya belli bir amacı veya amaçları en iyilemek için, genellikle bizim kontrolümüz altında olmayan kısıtları da gözeterek gerekli adımların veya eylemlerin belirlenmesi, bir başka deyimle programlanması anlamında kullanılmaktadır. Bu adımlar programlanırken, elimizdeki mevcut uygun çözümden daha iyi bir çözüm ele etmek için, hangi yönde hangi eylemin gerçekleştirileceğine karar verilmesinin araştırılması da bir bilim dalı olarak uygu-lamalı matematiksel programlamanın veya yöneylem araştırmasının temel prensibini oluşturmaktadır. Dolayısıyla Yöneylem Araştırması, elimizdeki kısıtlı kaynakların, var olan kıstaslar gözetilerek belirlenen amaçlara ulaşılması ve/veya verimliliğin olabildiğince artırılması için gerekli bilimsel eylemlerin araştırılması ve uygulanması bilimidir.
Bir problem öncelikle sözel olarak ifade edilir. Örneğin, bir fabrikada çok sayıda ürün üretilmekte ve bu ürünler siparişçilere ulaştırılmaktadır. Fakat bu süreçte bazı siparişler gecikmekte, bazı siparişler ise çok pahalıya mal olmaktadır. Bu süreci optimize etmek için öncelikle fabrikadaki üretim sürecini, daha sonra sipariş planlarını, üretilmiş ürünlerin depolanacağı depo imkânlarını, siparişlerin ulaştırılabilmesi için gereken araç filosunu iyice araştırmamız gerekmektedir. Daha sonra ise süreci optimize etmek için, yani siparişleri “gecikmeden” ve “en ucuz maliyetle” ulaştırmak için neler yapılması gerektiğinin belirlenmesi gerekir. Bu sorular bizi, öncelikle hangi ürünün hangi sırada ve ne kadar üretilmesi gerektiği sorusunu belirlemeye doğru itmektedir. Bunu yaparken, üretilecek ürünlerin depoda ne kadar zaman bekleyeceği bilgisinin de hesaplanması gerekiyor. Buradan da, özellikle depo alanımız sınırlı olduğundan ürünlerin “sıra ile” ve “gerektiği miktarda” üretilmesi ve depoda fazla bekletilmeden siparişçilere ulaştırılması gerektiği sonucuna varıyoruz. Nihayet bütün bunları programlarken de taşınacak ürünlerin mümkün olan “en az sayıda araçla” ve “en ucuz yolla” taşınmasını da programlamamız gerekecek. Dolayısıyla bütün bunları, problemin matematiksel modeli kurulmadan yapama-
yacağımız sonucuna varıyoruz. Bunun için ise, öncelikle bütün imkânlarımızı (üretim imkânları, ham madde, depo alanı, araç filosu) parametre veri tabloları şeklinde oluşturmamız, bulmamız gereken aktiviteleri karar değişkenleri şeklinde belirlememiz, amacımızı ve üretim ve hammadde kısıtlarımızı net bir şekilde ifade etmemiz gerekmektedir.
Doğrusal Programlama Problemleri İçin Matematiksel Model ve Çözüm Kavramları
Yöneylem Araştırmasının bir bilim dalı olarak hayatımıza girdiği ve sistemli bir şekilde geliştirilmeye başlandığı 20. yüzyılın ortalarından itibaren, bütün dünyada yaygın olarak kullanılan bir fikir, hiçbir hipotezin, matematiksel modeli oluşturularak çözümü bulunmadan, inandırıcı ve ikna edici olamayacağı fikridir. Yöneylem Araştırmasını bir bilim dalı olarak itibarlı kılan en önemli faktörlerden biri de bu olsa gerek. Çünkü Yöneylem Araştırması çatısı altında öğrenilen problemler için de benimsenmiş olan araştırma yöntemi, öncelikle bu problemlerin, mümkünse problemi birebir yansıtan bir matematiksel modelinin oluşturulması ve daha sonra bu modelin mümkün olan en iyi çözümünün bulunmaya çalışılması. Bu mümkün olmadığında sadeleştirilmiş, ama gerçeğe yakın bir matematiksel model oluşturularak bu modelin en iyi çözümünün veya yaklaşık en iyi çözümünün bulunmaya çalışılmasıdır.
Yöneylem Araştırması, bilim dalı kapsamında öğrenilen en iyileşme problemleri, bu problemlerin doğası itibarıyla doğrusal veya doğrusal olmayan, tek amaçlı veya çok amaçlı, kesikli (örneğin tam sayılı) veya sürekli karar değişkenlerine sahip, kısıtlı veya kısıtsız problemler olarak tasnif edilebilmektedirler. Bu matematiksel modelin amaç fonksiyonu ve kısıtları doğrusal ifadelerle tarif edildiğinden, bu bir doğrusal programlama problemidir.
Matematiksel Programlama, belli bir hedefe ulaşmak veya belli bir amacı veya amaçları en iyilemek için, genellikle bizim kontrolümüz altında olmayan kısıtları da gözeterek gerekli adımların veya eylemlerin belirlenmesi hakkında bir bilim dalıdır. Bu adımlar programlanırken, elimizdeki mevcut uygun çözümden daha iyi bir çözüm elde etmek için, hangi yönde hangi eylemin gerçekleştirileceğine karar verilmesinin araştırılması da bir bilim dalı olarak uygulamalı matematiksel programlamanın veya yöneylem araştırmasının temel prensibini oluşturmaktadır. Dolayısıyla Yöneylem Araştırması, elimizdeki kısıtlı kaynakların, belirlenen amaçlara ulaşılması ve/veya verimliliğin olabildiğince artırılması için gerekli eylemlerin araştırılması ve uygulanması bilimidir. Bu eylemlerin başında, eğer mümkünse problemin matematiksel modelinin kurulması ve en iyi çözümünün bulunması gelmektedir. Doğrusal programlama ise bütün amaçların ve kısıtların doğrusal ifade, denklem veya eşitsizliklerle ifade edildiği bir matematiksel programlama dalıdır.
Ulaştırma, Atama, En Kısa Yol, En Küçük Kapsayan Ağaç, Tam Sayılı Programlama, Çok Amaçlı En İyileme Problemleri ve Hedef Programlama Problemleri
Yöneylem Araştırması, en önemli problemlerinden, Atama problemini, ağ problemleri olarak En Kısa Yol problemi ile En Küçük Kapsayan Ağaç problemlerini ve bu problemlerin en iyi çözümlerinin bulunmasını kapsamaktadır. En kısa yol problemi, bir yerden bir başka yere gidilebilecek çok sayıda yol seçeneği içinden en kısasının nasıl seçilmesi gerektiği ile ilgili bir problemdir. Bu problemler, şehirlerarası taşımacılıkta, üretilmiş ürünlerin tedarikçilere ulaştırılması için en iyi rotanın (en kısa veya en ucuz veya en hızlı ) seçilmesi probleminde ve benzeri durumlarda karşılaşılan en önemli problem sınıfında yer almaktadır. En küçük kapsayan ağaç problemi ise örneğin; doğalgaz, su, internet veya telefon şebekelerinin en kapsayıcı şekilde ve en düşük masrafla yapılabilmesi problemlerinde karşılaşılmaktadır. Atama problemleri ise bir planlama periyodunda yapılması planlanan işleri, farklı fiyat veya verimlilik göstergesi ile yapabilecek farklı kişilere veya şirketlere, toplam ve- rimliliği en büyükleyecek (veya toplam yapılma maliyetini en küçükleyecek) atamanın gerçekleştirilmesi problemi olarak tanımlanmaktadır. Ulaştırma problemlerinde tedarikçilerin toplam üretim kapasitesinin, siparişçilerin toplam talep miktarına eşit olmalıdır.
Günümüz Yöneylem Araştırması biliminde, problem türlerine özel çözüm yöntemleri geliştirilmiştir. Örneğin bir ulaştırma problemi, genel olarak doğrusal programlama problemleri sınıfında yer aldığından elbette ki doğrusal programlama problemlerinin çözümü için geliştirilmiş olan simpleks yöntem uygulanarak çözülebilir. Ancak, bir ulaştırma problemi, doğrusal bir karar modeli olmasının yanı sıra sırf ulaştırma problemine özel koşul ve kıstaslara sahip olduğundan, bu tür bir problemin en iyi çözümünün bulunabilmesi için simpleks yöntemin genel şekli yerine bu algoritmanın, problemin özelliklerini maharetle kullanan daha sade bir şekli geliştirilmiştir. Bu nedenle, bir karar probleminin hangi türe ait olduğunun belirlenmesi, bu problemin en iyi çözümünün daha hızlı bulunabilmesi için uygun algoritmanın seçilebilmesi açısından önem arz etmektedir.
Bir örnek ile konu daha iyi anlaşılabilir:
Örnek: Çiftçimizin A ve B köylerinde birer tane mandırasının olduğunu ve bu mandıralarda tereyağı ve peynir üretebildiğini varsayalım. A köyündeki mandırada üretilen 1 kg tereyağının maliyeti 18 TL, 1 kg peynirinki ise 13 TL’dir. B köyündeki mandırada ise 1 kg tereyağının üretim maliyeti 20 TL, 1 kg peynirinki ise 12 TL’dir. Çift- çimizin her iki köydeki mandıraları kullanmak istediğini ve her iki ürünü de üretmek istediğini göz önünde bulundurarak, hangi ürünün hangi köyde üretilmesi gerektiğine karar vermesi gerekiyor.
ÇÖZÜM: Basit bir kıyaslamayla tereyağının A köyünde, peynirin ise B köyündeki mandıraya atanmasının, maliyetin en küçüklenmesi açısından en iyi çözüm olacağı görülmektedir.
Atama problemlerinde her bir işin yapılmış ol-ması ve işi yapabilen her bir birime de atama yapılmasının gerekliliği unutulmamalıdır. Doğası itibarıyla tam sayılı program- lama problemleri modellenmesinde kullanılan karar değişkenleri sadece tam sayı değerleri alabilmektedir. Bu durum hem problemlerin matematiksel modellerinin oluşturulmasını hem de en iyi çözümlerinin bulunmasını zorlaştırmaktadır. Örneğin, yukarıdaki mandıracı örneğinde herhangi bir sebepten (örneğin aniden oluşan olumsuz üretim koşulları yüzünden) sadece bir ürünün üretilmesi gerektiği şeklinde bir kısıtlama olması durumunda aşağıdaki şekilde karar değişkenleri kullanılabilirdi. Örneğin, x değişkeni tereyağının y de peynirin üretilip üretilmeyeceği ile ilgili değişkenler olsaydı, bu değişkenler sadece 0 veya 1 değerleri alabilecekti, yani x = 0, tereyağının üretilmemesi, x = 1 ise üretilmesi gerektiği durumlarını gösterecekti. Bu durumda iki üründen sadece bir tanesinin üretilmesi gerektiği şeklindeki kısıtlama da x + y = 1 denklemi ile modellenebilir.