YÖNEYLEM ARAŞTIRMASI
GİRİŞ
Doç. Dr. Dilay Çelebi

YÖNEYLEM ARAŞTIRMASI
1. Yöneylem Araştırması (ing. Operations Research) kısıtların olduğu bir durumda, belirli bir amaca yönelik en uygun çözümün bulunması için geliştirilmiş bir yöntemdir. 2. Yöneylem araştırması; bir organizasyon içinde operasyonların koordinasyonu ve yürütmesi ile ilgili dünyanın gerçek karmaşık sorunları için fikir üretmede matematiksel modelleme, istatistik ve algoritma gibi bilimsel yöntemleri kullanan disiplinlerarası bir bilimdir. 3. Yöneylem Araştırması ile Yönetim Bilimi (Management Science) modern bilim açısından aynı anlamdadır

YA karar verme problemlerini nicel modelleme yöntemlerini kullanarak ele alır.

YA’nın kısa tarihçesi




  


   

1600’ler Beklenen Değer (Blaise Pascal); Newton’un Minimum bulma metodu (Isaac Newton) • 1700’ler Bayes Kuralı (Thomas Bayes); En küçük kareler yöntemi (Carl F. Gauss) • 1826 Doğrusal Denklemlerin çözümü (Carl F. Gauss) • 1890 Bilimsel Yönetim (Frederick W. Taylor) • 1900 Gantt Çizelgesi (Henry Gantt, Frederick W. Taylor) • 1902 Eşitsizlik sistemlerinin çözümü(J. Farkas) • 1936 “Yöneylem Araştırması” teriminin ilk defa kullanılması • 1939 Kısıtlı problemlerler için optimallik koşulları (W. Karush) • 1941 Ulaştırma Problemi (F. L. Hitchcock) • 1942 BK & ABD’de kurulan YA grupları
Doç. Dr. Dilay Çelebi

YA’nın tarihçesi


II. Dünya Savaşı

Doç. Dr. Dilay Çelebi

YA’nın tarihçesi
• 1944 Fayda Teorisi (John von Neumann, Oskar Morgenstern) • 1947 Doğrusal programlama modeli (Simplex yöntemi) (George B. Dantzig) • 1947 Oyun teorisi (von Neumann & Morgenstern) • 1949 Monte Carlo benzetimi(S. M. Ulam, J. von Neumann) • 1950 En kısa yol problemi • 1951 Doğrusal olmayan Programlama (Kısıt sistemli problemler için optimallik koşulları) (H. Kuhn & A. Tucker) • 1960 Karar Ağaçları • 1960 Markov Süreçleri • 1961 Little Kanunu • 1974 Kuyruk Kuramı • 1984 Yapay Sinir ağları... http://www.lionhrtpub.com/orms/orms-10-02/historysb1.html
Doç. Dr. Dilay Çelebi

YA ne işe yarar?
Organizasyonlar Uygulamanın Özelliği Ulusal su yönetimi politikasını geliştirme Kimya fabrikasında minimum maliyetle üretim hedeflerini karşılamak için üretim işlevini optimum kılma Yayın Yılı 1985 1985 Hollanda Rijks Waterstatt Mosanto Şirketi Sağladığı Yıllık Tasarruf (milyon dolar) 15 2

Weyerhauser Şirketi
Eletrobras/CEPAL, Brezilya Birleşik Havayolları Citgo Petrol Şirketi

Elektrik Gücü Araştırma Enstitüsü
San Francisco Polis Departmanı Texaco, Şirketi IBM Yellow Freight Sistem Şirketi Amerikan Hava Yolları New Haven Sağlık Departmanı

Ağaç ürünlerinin getirisini maksimum kılmak için ağaçların kesimini planlama Ulusal elektrik üretim sisteminde hidro ve termal kaynakların optimal dağıtımı Minimum maliyetle müşteri ihtiyaçlarını karşılama ve rezervasyon bürolarında program değişikliği Rafineri işlemlerini, sunum ve dağıtımı ile ürünlerin pazarlanmasını optimum kılma Elektrik ihtiyacı için petrol ve kömür stoklarını, stok maliyetlerini ve tükenme riskini yönetme
Bilgi işlem sistemi ile polis karakollarının yayılımı ve optimal programlama Kalite ve satış gereksinimleri için optimal benzin karışımını elde etme Servis desteğini geliştirmek için yedek kısım envanterlerin ulusal entegrasyonu Ulusal yük taşıma ağının tasarımı ve yükleme yollarının optimali Geliri artırmak için uçuşların koordinasyonu ve seyahat düzeni sistemini tasarlama Etkili iğne değişimi programı ile maliyetlerde azalma

1986
1986 1986 1987

15
43 6 70

1989
1989 1990 1990 1992 1992 1993

59
11 30 20 + 250 milyon az envanter 17.3 500 > %33

Doç. Dr. Dilay Çelebi

MATEMATİKSEL MODELLEME

Model, gerçekliğin seçilmiş bir soyutlamasıdır* Model bir durumun temsilidir**

Matematiksel model bir problemin soyut matematiksel temsilidir.
Matematiksel programlama, matematiksel modellerin karar verme problemlerinin çözümü için kullanılmasıdır.
*Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, 1993. **Quantitative Analysis for Management, 9th Edition, Barry Render, Ralph M. Stair, M. Hanna, 2006.

Matematiksel Modeller

• Bir sistemin bileşenlerinin simgeler ile tanımlanıp bunlar arasındaki ilişkilerin fonksiyonlar ile gösterimine “matematiksel model” adı verilir. • Veri sayısallaştırılabilir olmalıdır!



İki kardeşten küçük olanı 2km ötedeki istasyona gitmek üzere yaya olarak yola çıkıyor. Büyük kardeş de aynı yoldan istasyona gitmek için 10 dakika sonra bisikleti ile yola çıkıyor. Küçük kardeşin yürüme hızı 80 m/dakika, büyük kardeşin hızı ise 240 m/dakika olduğuna göre, büyük kardeşin küçük kardeşi yakalaması ne kadar sürer?

Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, 1993.

Matematiksel Modeller
• Bir sistemin bileşenlerinin simgeler ile tanımlanıp bunlar arasındaki ilişkilerin fonksiyonlar ile gösterimine “matematiksel model” adı verilir. • Veri sayısallaştırılabilir olmalıdır!

Modeller genellikle varsayımlar kullanarak gerçekliği basitleştirir.
Bir model; 1. Gereksinimlerinize cevap verecek, 2. Sürece ayırabileceğiniz kadar bir zamanda çözülebilecek Kadar detay barındırmalıdır.

Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, 1993.

Varsayımlar
Gerçek Dünya Varsayılan Dünya Model

Doç. Dr. Dilay Çelebi

Sayısal Model


İki kardeşten küçük olanı 2km ötedeki istasyona gitmek üzere yaya olarak yola çıkıyor. Büyük kardeş de aynı yoldan istasyona gitmek için 10 dakika sonra bisikleti ile yola çıkıyor. Küçük kardeşin yürüme hızı 80 m/dakika, büyük kardeşin hızı ise 240 m/dakika olduğuna göre, büyük kardeşin küçük kardeşi yakalaması ne kadar sürer?

Doç. Dr. Dilay Çelebi

Varsayımlar


Bu problemin çözümü gerçek hayatta geçerli midir?
 Sabit

hız  Trafik ışıkları  Yükselti  Yorgunluk  Trafik sıkışıklığı

Doç. Dr. Dilay Çelebi

Varsayımlar...


4 arkadaş bir binanın 5. katındaki bir arkadaşlarının evine ziyarete gidiyor. Dördü okey oynamaya başlıyor. Bu esnada kalan biri balkona çıkıyor ve aşağıya düşüyor. Aşağıdan tesadüfen geçmekte olan polisler durumu görüp, soruşturma yapıyorlar. Düşen kişi “Beni Mustafa itti” diyor. Polisler yukarı çıkıp kim olduğunu sormadan Mustafa’yı tutukluyor. Nasıl?

Doç. Dr. Dilay Çelebi

Matematiksel Modeller
1. Bu cümlelerden sadece 1 tanesi yanlıştır. 2. Bu cümlelerden sadece 2 tanesi yanlıştır. 3. Bu cümlelerden sadece 3 tanesi yanlıştır. 4. Bu cümlelerden sadece 4 tanesi yanlıştır. 5. Bu cümlelerden sadece 5 tanesi yanlıştır. 6. Bu cümlelerden sadece 6 tanesi yanlıştır. 7. Bu cümlelerden sadece 7 tanesi yanlıştır. 8. Bu cümlelerden sadece 8 tanesi yanlıştır. 9. Bu cümlelerden sadece 9 tanesi yanlıştır. 10. Bu cümlelerden sadece 10 tanesi yanlıştır. Bu cümlelerden hangisi doğrudur?

Doç. Dr. Dilay Çelebi

Karar Modelleri
Sistemin yöneticisinin kontrolü altında olup, karar değişkeni olarak isimlendirilen değişkenlere hangi değerlerin verilmesi gerektiğini belirlemek amacıyla kullanılan matematiksel modellere “karar modeli” adı verilir. Karar Değişkenleri

2 km A B

V=?
Kısıtlar Amaç En kısa zamanda B Aracın hızı noktasına varmak Yol şartları

Hız, seçilen araç, yol

Karar Modelleri  Ortamı seçici olarak temsil eder  Karar değişkenleri belirlenir  Amaç belirlenir  Kısıtlar tarafından sınırlanır
Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, 1993.

Karar Modelleri








Çeşitli yaşlardan 4 arkadaş, bir gece vakti bir köprüden geçecekler. 1.10 dakikada geçer 2. 5 dakikada geçer 3. 2 dakikada geçer 4. 1 dakikada geçer Ellerinde sadece bir fener var ve köprüden aynı anda en fazla 2 kişi geçebilir. Bu arkadaşları köprüden geçirin ancak sadece 17 dakikada....
Doç. Dr. Dilay Çelebi

Optimizasyon Modelleri

Optimizasyon “en iyi çözümü bulma” faaliyetidir. Türkçe karşılığı “Eniyileme” olarak tanımlanmıştır. Optimizasyon modelleme, bir problemin en iyi çözümünün bulunması ile ilgilenen bir matematiksel modelleme türüdür.

Optimizasyon modelinin amacı karar değişkenlerine bağlı bir fonksiyonun değerinin en az ya da en çok yapılmasıdır.*
ÖRNEKLER Kar Ençoklama Maliyet Enazlama Bekleme sürelerinin enazlanması Kapasitenin en yüksek oranda kullanılması Çalışma saatlerinin en az yapılması

*Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, 1993.

Optimizasyon modelleri


27 000 km yolu araba ile gidecek olan bir kimse, arabasının lastiklerini yeniliyor ve yola çıkıyor. 12 000 km'de kullanılmaz olan lastiklerden, en az kaç tane yedek daha almalıdır?

Doç. Dr. Dilay Çelebi

Nicel Analiz
Karar Süreci
Problem Tanımı

Nicel Analiz
Problem Tanımı

Alternatiflerin Araştırılması

Gözlem

Değerlendirme

Model Kurulumu Sonuçların Analizi

Çözüm

Doğrulama

Seçim

Doç. Dr. Dilay Çelebi

YA Yöntemleri
YA
Deterministik Modeller Doğrusal Programlama Tam sayılı Programlama Doğrusal olmayan Programlama Ulaştırma Modelleri Çok amaçlı Karar Verme
Doç. Dr. Dilay Çelebi

Stokastik Modeller Markov Zincirleri Kuyruk Teorisi Dinamik Programlama

Buluşsal Yaklaşımlar

Doğrusal Programlama
Tanım: a ve b reel sayılar, a≠0 olmak üzere f(x) = ax + b denklemi ile tanımlanan fonksiyona bir doğrusal fonksiyon (linear function) denir.
Doğrusal Fonksiyonlar:

y  ax  b

Doğrusal olmayan fonksiyonlar:

2x 1 y x  2 y  10 3a  369b  432 c

2x2 1 y xy  10 a  3c  432 b c

Doğrusal Programlama
Bir doğrusal programlama problemi (DPP) üç bölümden oluşur:
1. Bir DP problemi, karar değişkenlerinin (x1, x2, ....,xn) doğrusal bir fonksiyonu olan amaç fonksiyonunu içerir. Amaç fonksiyonu maksimizasyon ya da minimizasyon amaçlı olabilir.

Bir f fonksiyonu , x1, x2, …….xn değişkenlerinin bir doğrusal fonksiyonu olabilmesi için c1, c2, …..cn sabitleri için, f (x1, x2,…..xn) = c1x1 + c2x2 + c3x3+……..cnxn formunu alması gereklidir.

Doğrusal Programlama
2. Bir DP problemi, karar değişkenlerinin alacağı değerleri sınırlayan kısıt denklemlerini içerir. Her bir kısıt denklemi doğrusal eşitlik ya da eşitsizlik şeklinde ifade edilmelidir.
Bir doğrusal f (x1, x2, …….xn) fonksiyonu ve b sabit sayısı için, f (x1, x2, …….xn)  b ve f (x1, x2, …….xn) )  b doğrusal eşitsizliklerdir.

Doğrusal Programlama
3. Her bir değişken için işaret kısıtlaması vardır.

Her hangi bir xj (j=1,.....,n) değişkeninin işaretinin belirlenmesi gerekir. Bu durum değişkenlerin negatif olmama (xj  0, j=1,.....,n) ya da sınırlandırılmamış (xj –serbest) olması şeklinde belirtilmelidir.

Doğrusal Programlamanın Unsurları


Değişkenler: Bir problemin modeli kurulduktan sonra değeri hesaplanacak olan bilinmeyen simgelerdir. Karar Değişkenleri: Bir karar modelinin çözümlenmesi sürecinde değeri hesaplanacak olan karar unsurlarıdır. Sapma Değişkenleri: Kullanılan faktör ve onun kapasitesi arasındaki dengeyi kurmaya çalışırlar.






Gölge Değişkenler: Atıl kapasiteyi temsil ederler. “” şeklindeki bir kısıt denklemini (=) şeklinde ifade etmek amacıyla kullanılırlar.
  

Örnek:

X1 + X2  5
X1 + X2 +S1 = 5



Artık Değişkenler: Fazla kapasiteyi temsil ederler. “” şeklindeki bir kısıt denklemini (=) şeklinde ifade etmek amacıyla kullanılırlar.


Örnek:




X 1 + X2  5
X1 + X2 - E1 = 5

Doğrusal Programlamanın Unsurları










Parametreler: DP modelinin davranışını etkileyen sabit sayılardır. DP modelindeki cj, bi ve aij (i=1 ........m; j=1 ......... n) sayıları parametreler olarak adlandırılırlar. Amaç Fonksiyonu: Karar değişkenlerinden ve bu değişkenlerin parametrelerinden (cj), oluşan en iyi çözümün (maksimum ya da minimum) elde edilmesini sağlayan doğrusal bir fonksiyondur. Kısıt denklemi: Bir modeldeki karar değişkenleri ile parametreler arasındaki zorunlu ilişkilerin kurulduğu doğrusal fonksiyonların her birine “kısıt denklemi” adı verilir. Teknolojik Katsayılar: Her faaliyet için gerekli olan kaynak miktarıdır. aij (i=1 ........m; j=1 ......... n) Sağ Taraf Değerleri: Mevcut kaynak miktarlarını gösteren, problemdeki kısıt denklemlerinin sağ taraflarında yer alan parametrelerdir. bi (i=1 ........m)

Doç. Dr. Dilay Çelebi

DP Problemlerinin Genel Yapısı Karar Değişkenleri
Z maks,min  c1 x1  c2 x2  c3 x3  ....  cn xn a11x1  a12 x2  a13 x3  ....a1n xn , ,  b1 a21x1  a22 x2  a23 x3  ....a2 n xn , ,  b2  am1 x1  am 2 x2  am 3 x3  ....amn xn , ,  bm x1 , x2 ,...xn  0, serbest
Kısıtlar Amaç Fonksiyonu

DP Problemlerinin Genel Yapısı
Z maks,min   c j x j j 1 n

a x j 1 ij

n

j

, , bi

x j  0, serbest

Doğrusal Programlamanın Adımları

1. 2.

Değişkenlerin ve karar değişkenlerinin seçilmesi, Amaç fonksiyonun oluşturulması, a) Her değişkenin amaç fonksiyonuna katkısının hesaplanması, b) Doğrusal amaç fonksiyonunun elde edilmesi, c) Amaç fonksiyonunun enazlanacağının mı yoksa ençoklanacağının mı belirlenmesi.

3. 4.

Kısıtların belirlenmesi, İşaret kısıtlarının konulması.

Üretim Problemi
Bir terzi ceket ve pantalon üretimi yapmaktadır. Üretimde kullanılmak üzere 150 m2 kumaş ve 200 saatlik işgücü bulunmaktadır. Her ceket 3 m2 kumaş ve 10 saatlik işgücü, her pantalon ise 5 m2 kumaş ve 4 saatlik işgücü kullanmaktadır. Bir ceketten 50 TL, bir pantalondan ise 40 TL kâr edilmektedir. Toplam kârını maksimum yapmak için bu terzi kaç adet pantalon, kaç adet ceket üretmelidir?
Doç. Dr. Dilay Çelebi

Üretim Problemi


Bir oyuncak üreticisi plastik ve montaj departmanlarından oluşan atölyesinde A ve B tipinde iki farklı oyuncak üretmektedir. Her iki departmanda ikişer işçi çalışmaktadır. Her işçi günde 7.5 saat çalışmaktadır. Bir adet A tipi oyuncağın plastik departmanında işlenmesi için gerekli süre 4 dakika, montaj departmanında işlenmesi için gerekli süre 2 dakikadır. Benzer bir şekilde bir adet B tipi oyuncağın plastik departmanında işlenmesi için gerekli süre 1 dakika, montaj departmanında işlenmesi için gerekli süre 3 dakikadır. Oyuncakların birim katkıları sırasıyla 0.8 pb ve 1.2 pb’dir. Üretici yukarıdaki koşullara uygun olarak üründen en yüksek katkıyı sağlamayı amaçlamaktadır. Yukarıdaki verilere bağlı olarak oyuncak üreticisinin karar probleminin doğrusal programlama (DP) modelini kurunuz.

Üretim Problemi


Bezz Tekstil kumaş ve boya hammaddelerini kullarak üç çeşit giysi üretmektedir. Bu ürünlerden birer tane üretmek için gerekli hammadde miktarları ve gelecek hafta itibariyle bu hammaddelerin mevcut miktarları aşağıdaki gibidir: Kot Pantalon Kumaş Boya 4m 2 kg Elbise 3m 4 kg Gömlek 3m 5 kg Miktar 60 m 50 kg

•

Ürünler ile ilgili parasal bilgiler şu şekildedir:
Kot Pantalon
Satış Fiyatı Değişken Üretim Maliyeti 1300 490

Elbise
1000 400

Gömlek
950 430

•

İşletmenin sabit maliyetleri 1200 TL’dir ve üretilen her ürünün satılabildiği varsayılmaktadır. Buna göre işletme karını maksimum yapacak DP modelini kurunuz.

DP’nin Varsayımları

DP'nin gerçek hayatta karşılaşılan problemleri modellemekte kullanılabilmesi için temel varsayımlarının bilinmesi önemlidir:
1.
1. 2.

Doğrusallık (Linearity)
Toplanabilirlik (Additivity) Orantısallık (Proportionality)

2. 3.

Bölünebilirlik (Divisibility) Belirlilik (Certainity)

Kaynaklar


Operations Research: Applications and Algorithms , Fourth Edition,

WINSTON, W. L. (2004), Thomson Learning Inc: Canada.








Introduction to Management Science, 9th Edition, Taylor B.W., Prentice Hall, New Jersey, 2007. ISBN: 0-13-1966133-0, ITU Library Number: T56.T39.1990/T56.T39 1986. Quantitative Analysis for Management, 9th Edition, Barry Render, Ralph M. Stair, M. Hanna, Prentice Hall, New Jersey, 2006. ISBN: 0-13-153688-5, ITU Library Number: T56.R46 2006. Fundamentals of Management Science, Efraim Turban, Jack R. Meredith, Plano, Tex. : Business Publications, 1981. ISBN: 025602393X, ITU Library Number: HD30.23.T87 1981 Introductory Management Science, F.J. Gould, G.D. Eppen, C.P. Schmidt, Englewood Cliffs, N.J. : Prentice Hall, c1993. ISBN:0134864409, ITU Library Number: HD30.25.G68 1993.