Yöneylem Arastirmasi Ders Notlari -1
29 05 2011

Yöneylem Arastirmasi Ders Notlari -1

 

YÖNEYLEM ARAŞTIRMASI (operations research)
İçerik:

1   Giriş
     Yöneylem araştırmasının doğuşu
     Yöneylem araştırmasının  gelişimi ve uygulama alanları

1. BÖLÜM    MATEMATİK  PROGRAMLAMA

2   Doğrusal programlama
        Formülasyon ve grafik çözüm
        Simplex yöntemi
        Simplex yönteminin  dejenere olması durumu
        Dualite
 3  Ulaşım Modelleri 
        Genel ulaşım problemi
        Ulaşım problemlerinin çözümü
        Ulaşım problemlerinin dejenere olması durumu
 4  Ağ modelleri
        En kısa yol problemi ve en kısa yol algoritması
        Maksimum akış problemi
 5   Tam sayılı programlama
 6   Dinamik programlama

2. BÖLÜM OLASILIKLI MODELLER

 7   Karar teorisi
 8   Oyun teorisi
        İki kişili sıfır toplamlı oyunlarda optimum çözüm
        Karma stratejiler
 9   Proje planlama teknikleri
        CPM ve PERT yöntemleri
        Aktivite sürelerinin tahmini
        Krıtik yolun bulunması
 10  Kuyruk modelleri
 11  Simülasyon

Kaynaklar:
Operations Research, Hamdy A.Taha,1992
Operations Research,F.S. Hillier,G.J.Lieberman,1967
Quantitative Approaches to Management,R.I.Levin,D.S.Rubin,J.P.Stinson,1986  




BÖLÜM 1

GİRİŞ

Yöneylem araştırmasının doğuşu

Sanayi devriminin gerçekleşmesinden sonra bu devrimi gerçekleştiren ülkelerdeki organizasyonların hacimlerinin büyüdüğü ve işlemlerin karmaşıklıklarının arttığı gözlenmiştir.Organizasyonların büyümesi ile birlikte yeni problemler ortaya çıkmış ve hala da çıkmaktadır.Büyümeyle artan karmaşıklık kaynakların organizasyonun yararına en etkin şekilde kullanımını güçleştirmiştir.Bu tür problemler ve bunlara çözüm arayışı yeni bilim dallarının doğuşunu hızlandırmıştır.Yöneylem araştırması da bunlardan biridir.II.Dünya savaşından önceki yıllarda özgün YA çalışmalarına rastlanılmasa da  YA nın ilk uygulamalarının  yönetimde bilimsel yaklaşımların kullanılması olarak gösterilmektedir.Hatta yönetim bilimi ve YA ile ilgili çalışmalar M.Ö. 212 yılına kadar uzanmaktadır.Sürekli karar verme durumunda olan yöneticilere(decision makers) seçenekler içinde en iyisini (optimum) bulma konusundaki bilimsel yaklaşımlar  II. Dünya savaşına kadar süregelmiştir.
İlk YA çalışmasının II.Dünya savaşı sırasında İngiltere’de (1939) bir ekip tarafından yapıldığı  tüm  yöneylem araştırmacılarınca kabul edilmektedir.İngiltereye yapılan hava akınları sırasında en iyi savunma şeklini  belirlemek için radarların en etkin kullanımını saptamak amacıyla biraraya gelen farklı mesleklerdeki uzmanlar bu ekip çalışması ile en iyi çözümü bulmuşlardır.Bu ilk YA çalışmasının başarılı olması sonucunda savunma sisteminin diğer bölümlerinde de benzer ekipler kurularak YA çalışmaları yaygınlaştırılmıştır.
1942 yılında İngilterede General Spaatz’ın isteği ile Hava Kuvvetleri Komutanlığında “operations analysis groups(Eighth Bomber Command)” kurulmuştur.Bunun bir benzeri de  A.B.D.   Deniz Kuvvetlerinde   MIT den   Philip  M. Morse    başkanlığında   “ operations  research teams “ adı altında organize edilmiştir.Savaştan sonra da özellikle A.B.D. de askeri alanda uygulamalar devam etmiştir.Kurulan Operations Research Office (daha sonra Research Analysis Corporation adını almıştır) çalışmalara devam etmiştir.Hava kuvvetlerinde Operations Analysis Division kurulmuş ve RAND corporation tarafından yönetilen RAND projesi çalışmalarına başlanmıştır.
Diğer yandan üretimin makinalaşmasi, organizasyonların sürekli büyümesi,insan-makine sistemlerindeki karmaşıklık YA çalışmalarına endüstride de ihtiyaç olduğunu ortaya çıkarmıştır. YA çalışmalarının gelişmesinde anahtar  rol oynayan iki faktör vardır.Bunlardan bir tanesi bilim adamlarının YA tekniklerini geliştirerek bu teknikleri gerçek hayata uygulamaya başlamalarıdır.Bu konuda özellikle 1947 yılında George B.Dantzig tarafından geliştirilen ve ilk formülasyonu Leontieff ‘e ait olan Doğrusal Programlama (Linear programming)    tekniğinin Simpleks  algoritması ile çözümü önemli bir aşamadır.Bu tekniğin benzer problemlere uygulanması hızla yayılmış ve süregelen bilgi birikimi ile diğer tekniklerin gelişmesi çabuklaşmıştır.İkinci faktör ise bilgisayarlardaki gelişmedir.Bilgisayar donanımı ve yazılımı alanındaki hızlı gelişmeler YA tekniklerinin gerçek hayat problemlerine uygulanışını kolaylaştırmış,elle çözümü çok uzun zaman alan ve hata oranının arttığı  problemlerin çözümü kolaylıkla gerçekleştirilmiştir.
1950 yılından sonra bilimsel bir nitelik kazanan YA nın bir çok tanımı yapılmıştır.Bu tanımlardan bir tanesi şöyledir:
“YA , bir sistemde ortaya çıkan problemlere ,sistemin denetlenebilir bileşenleri cinsinden bilimsel yöntem, teknik ve araçların uygulanması ile en iyi(optimum) çözümün bulunmasıdır.”

Kısaca YA nın konusu ,yaklaşımı ve amacı şu şekilde verilebilir ;

YA nın Konusu : İnsan - Makina sistemlerinin tasarım , kuruluş ve işletiminde karşılaşılan problemleri belirlemek ve karar  problemlerine optimum çözüm   aramaktır.

YA nın yaklaşımı : Sistemi bütünüyle ele alarak farklı disiplinlerden oluşan ekiple bilimsel yöntemi izlemektir.

YA  nın amacı : Yönetimin  politika  ve  uygulamalarını  bilmsel  olarak   belirlemesine
yardımcı olmak , böylece yönetimle ilgili kararların tutarlılık ve uygulanabilirliğini arttırmaktır.         

YA Model Yaklaşımı

Bir YA çalışmasında kullanılan aşamaları  aşağıdaki gibi verebiliriz:

1.  Problemin formüle edilmesi.
2.  Çalışılan sisteme ait matematik modelin kurulması.
3.  Modelin çözümünün yapılması.
4.  Modelin ve çıkarılan çözümün test edilmesi.
5.  Çözüm üzerinde kontrollerin yapılması.
6.  Çözümün gerçek hayata geçirilmesi.(uygulanması)

Karar problemleri her ne kadar matematiksel model oluşturulup çözülse de bu problemleri etkileyen başka faktörler mevcuttur. Bu faktörlerin başında insan unsuru gelir. Bazı görüşlere göre karar problemlerinin matematik modellerle çözülmesi pratik değildir. Buna en iyi örnek asansör problemidir.
Bir işyerinde asansörlerin yavaşlığından ötürü oluşan şikayetleri gidermek amacıyla bir bekleme hattı(kuyruk) modeli kurularak problem analiz edilmiş ve sonunda asansörün hızının arttırılmasına karar verilmiştir. Ancak şikayetler azalmadığı için insan faktörü ele alınarak, bekleyenlerin can sıkıntısından şikayetlerini arttırdıkları düşünülmüş ve asansör girişlerine ayna yerleştirilmiştir. Asansör bekleyenler ayna sayesinde kendileriyle ilgilendiklerinden şikayetler ortadan kalkmıştır.
YA tekniklerinin pek çoğunun yapısında iteratif(yinelemeli) algoritmalar yer alır. Bundan dolayı bu algoritmaları elle çözmek uzun hesaplamalar gerektirir. Bilgisayarların gelişimi ile bu tekniklerin çözümleri kolaylaşmıştır.
Gerçek problemlerin matematik modele uygulanmasındaki zorluklar, bazı modellerin matematik formüllerle gösterilmeyip simülasyon teknikleriyle çözülmesini gerektirir. Simülasyon, gerçek sistemi küçük birimler halinde inceler ve bu birimleri birlikte hareket ettirecek  mantıksal ilişkileri kullanarak, sistemin mevcut davranışını taklit eder. 

1.  Problemin formüle edilmesi

Burada yapılacak ilk iş ele alınan sistemi iyi tanımlayarak problemin  değişkenlerini saptamak ,bunların organizasyonun diğer birimleriyle olan ilişkilerini göz önüne alarak problemin çerçevesini oluşturmaktır.Yöneylem araştırmacısı (veya grubu) karar verici durumunda olan yöneticilere danışarak   probleme doğru cevap arayacaktır.Yönetimin tavsiyeleriyle ayrıntılı bir teknik analiz yapılıp,işletmenin amacı,politikası ,kaynakları araştırılarak bir rapor oluşturulacaktır.Yönetimin amacını(amaçlarını) kesin olarak tespit etmesi doğru cevabın bulunması açısından gereklidir.Örneğin kar etme amacı öncelikli olan bir kuruluş uzun dönem kar maksimizasyonunu yegane amacı olarak bemimseyebilir.Ancak yapılan araştırmalar birçok işletmenin diğer amaçları yanında güvenli kar hedefini benimsediğini göstermektedir.Bir çok işletme de tek amacın kar olmadığını, pazardaki payını yükseltmek, karın devamlılığı,çalışanların morallerinin yükseltilmesi, işletmenin prestijinin yükseltilmesi, sabit fiyatlar gibi tipik amacların da hedeflenebileceğini savunmaktadır.Dolayısıyla YA çalışmasının başlangıcında bu hedeflerin tespit edilip yönetim tarafından bildirilmesi gerekmektedir.
 

2. Çalışılan sisteme ait matematik modelin kurulması

Problemi formüle ettikten sonraki aşama matematiksel bağlantıları kurarak problemi matematik semboller ve ifadelerle sunmaktır.Matematiksel model, matematik ifadelerle ilişkilendirilmiş,çözümleri ele alınan sistemin durumunu açıklayan bir eşitlikler kümesidir. Matematik eşitlikler fizik kurallarını,kimyasal reaksiyonları en iyi şekilde açıklayabildikleri gibi sosyal bilimlerde de incelenen sistemin davranışlarını anlama, açıklama ve yorumlamada  bize yardımcı olmaktadırlar.Sistemin anlaşılması açısından diğer sistemlerden daha kullanışlı olmaları, ardışık irdeleme olanağının bulunması  ve model üzerinde denemeler yapılabilmesi  matematiksel modellerin avantajları olarak sayılabilir.Sosyal bilimlerde bilimsel yöntemlerin uygulanması matematik modellerin yardımıyla olmaktadır.

3.  Modelin çözümünün yapılması

Matematik modelin kurulmasından sonra bu modelin çözüm aşamasına geçilir.Bir YA çalışmasında bu aşamanın çalışmanın en önemli parçası olduğu düşünülürse de gerçekte bu adım araştırmacılar için en kolay adım olarak alınabilir..Çünkü burada geliştirilmiş olan algoritmalardan birisinin bilgisayar kullanılarak çözümü yapılmaktadır.YA nın bu aşamadaki rolü çözümün optimum yani en iyi çözüm olmasını sağlamaktır.Modeldeki amacın gerçekleşip gerçekleşmediği , kısıtlamaların amaç üzerindeki etkileri,değişkenlerin aldıkları değerlerin yorumu çözümden sonra değerlendirilecek hususlardır.Duyarlılık analizi(sensitivity analysis) yapılarak parametreler üzerinde yapılacak herhangi bbir değişikliğin modeli nasıl etkileyeceği görülür.
 
4.  Modelin ve çözümün test edilmesi 

Modelin çözümünden sonra dikkat edilmesi gereken nokta çözümün ne denli güvenilir olduğudur.Modeli kurarken yapılan bir hata çözümün tüm aşamalarına yansıyabilir.Çözüm bulunduktan sonra modelin tamamını değerlendirerek,sonucun modelin gerçek olarak uygulanabileceğini kanıtlaması gerekir.Probleme ait model yeniden gözden geçirilir ve bir hata olup olmadığı araştırılır. Bir diğer yararlı  test etme şekli de matematik ifadelerin kullanıldıkları birimlerdeki doğruluklarıdır.Modelin ve çözümünün başlangıç uygulamasından önce test edilmesi güvenli bir uygulama ve zaman içinde geçerlilik kazanması açısından gereklidir.

5.  Çözüm üzerinde kontrollerin yapılması

Eğer model devamlı kullanılacaksa ,bir sonraki adım modeli açıklayan çok iyi bir sistem dökümantasyonunun  hazırlanmasıdır. Bu sistemde model, çözüm prosedürü ve uygulama için kullanılan işlemler yer almalıdır.Kullanıcının değişmesi durumunda bile böyle bir prosedür hazırlanmışsa uygulama aksamayacaktır.Öte yandan gerçek hayatta sürekli koşullar değiştiği için bu değişikliklerin modele yansıtılması yani modelin güncelleştirilmesi söz konusudur.

6.  Çözümün gerçek hayata geçirilmesi(uygulanması)

YA çalışmasının son aşaması da çözümün karar verici tarafından benimsenip uygulanmasıdır.Çalışmanın başarısı şüphesiz üst kademe yöneticilerinin ve işlemleri yürütecek kişilerin vereceği  desteğe bağlıdır.YA çalışması yapan grup  yöneticilerle devamlı işbirliği ile bulunan çözümün güvenli bir şekilde uygulanabileceğini izlemelidir.  
      

Türkiye’de YA Çalışmaları

Türkiyede ilk YA çalışmaları 1960 yılında askeri   amaçlı   olarak  başlatılmıştır. 1965        
yılında Tübitak  da ilk YA grubu kurulmuştur.1964 yılından itibaren de üniversitelerde
YA  konularının  anlatımı  başlamış   ve dersler      konulmuştur.1975  yılında kurulan
YA derneği ulusal kongreler düzenlemekte ,çıkardığı yayınlarla da   YA  çalışmalarını 
desteklemektedir.

YA nın dünyadaki gelişimi

Çeşitli ülkelerde kurulan  dernekler YA ilgili periyodikler yayınlayarak bu konudaki gelişmeleri duyurmaktadırlar.1950 yılı başında A.B.D. da kurulan ORSA(Operations Research  Society of America) ile TIMS(The Institute of Management Sciences) bu kuruluşların en ünlüleridir.YA uygulamalarını ve yapılan araştırmaları aktaran dergilerin bazıları  aşağıda verilmektedir.

A.I.E.E. Transactions
C.O.R.S. Journal
Decision Sciences
Industrial Engineering
Journal of Industrial     Engineering
Management Science
Mathematical Programming
Mathematics of Operations Research
Naval Research Logistics Quarterly
Networks
Operations Research
Transportation Science

YA tekniklerinin uygulama alanları

Çok değişik uygulama  alanları olmasına karşın işletmeler dikkate alındığında değişik departmanlardaki uygulamalar şu şekilde verilebilir:
Muhasebe        : Nakit akış planı,Kredi politikası
Tasarım           : Proje kaynaklarının yaratılması, Proje planlama, Bina planlama,fabrika kapasite ve yerinin planlanması,Hastane planlaması,Bölgesel depoların seçimi,Uluslararası logistik sistemler
Finans             : Kar politikası, Yatırım analizi,Değerli kağıt analizi
Üretim       :Envanter kontrol, Üretim planlama, İnsan-gücü planlaması, Üretimi kolaylaştırma
Pazarlama       : Reklam yönetimi
Organizasyon  :Personel temini, Personel planlama
Satın alma       : Optimum satın alma,Malzeme yönetimi
Araştırma-geliştirme: AR-GE projelerinin kontrolu, Ürün geliştirme

Ayrıca ulusal planlama,enerji planlaması ve yönetimi,teknoloji planlaması,savunma,çevre sağlığı , haberleşme sistemleri gibi konularda da uygulamalar yapılmaktadır.

YA teknikleri

YA  teknikleri olarak kullanılan algoritmaları iki bölümde toplamak mümkündür.
1. Matematiksel programlama teknikleri
Doğrusal programlama(linear programming)
Networks
     Transportation problem
      PERT-CPM
      Dinamik programlama
Integer programming
     Goal programming
Game theory

2.  Olasılıklı modeller

Olasılık teorisi (probability)
Karar teorisi(decision making)
Envanter teorisi
Simulasyon
Kuyruk teorisi( wating lines)
Markov analizi


DOĞRUSAL PROGRAMLAMA


Yöneylem Araştırması modelleri, alternatifler, kısıtlar ve amaç fonksiyonu adı verilen temel elemanlardan oluşur. Karar problemlerinin alternatifleri genelde bilinmeyen değişkenler olarak ortaya çıkar. Bu değişkenler uygun bir matematik model oluşturmak üzere kısıtlar ve amaç fonksiyonu olarak düzenlenir.  Modelin çözümü ile tüm kısıtları sağlayan, aynı zamanda  da amaç  fonksiyonunu optimum (maksimum veya minimum) yapan karar değişkenlerinin değerleri bulunur.
DP, sınırlı kaynakların kullanımını optimum yapmak için geliştirilmiş bir matematiksel modelleme yöntemidir. Bir optimizasyon tekniği olarak belirli ortak özellikleri bulunan problemlere uygulanır. Problemden kaynaklanan bazı özel durumlar dışında tüm DP modelleri üç temel özellik taşır:

Doğrusal amaç fonksiyonu
Doğrusal kısıtlar
Pozitiflik koşulu




Dogrusal amaç fonksiyonu

Tüm organizasyonların varmak istediği bir veya birden çok  amaç vardır. Çoğu organizasyonlar kar maksimizasyonu ya da maliyet minimizasyonunu amaç olarak alırlar. DP modellerinde birçok değişkenin doğrusal fonksiyonundan oluşan bir “amaç fonksiyonu” bulunur.  Bu fonksiyonu Z , değişkenleri x1 , x2 , ………., xn  ve sabit katsayıları da c1 , c2 , ……… cn  ile göstermek üzere;

                             Z =  c1 * x1  + c2 * x2  + ......................... + cn * xn

Şeklinde yazılır. Problemin amacı Z ‘i maksimum veya minimum yapa x değerlerinin bulunmasıdır. Eğer kar maksimizasyonu amaçlanmışsa Z’i maksimum yapan, aksi durumda da maliyet minimizasyonu için Z’ i minimum yapan x değerleri  aranır.

Doğrusal kısıtlar

Bütün doğrusal fonksiyonlar pozitif sonsuzda maksimum, negatif sonsuzda minimum değerini alırlar. Dolayısıyla doğrusal amaç fonksiyonlarının aynı maksimum ve minimuma sahip olduklarını söyleyebiliriz. Matematiksel olarak anlamsız olan bu sonuçtan kaçınmak için değişkenler üzerinde bazı kısıtlamalar yapılmalıdır. Zaten organizasyonların kaynaklarının da sonsuz olmadığı düşünülürse bu kısıtlamaların modelde yer alması normaldir. DP modellerinde kısıtlar, doğrusal eşitsizliklerden meydana gelir.
                       a11 , a12 , ........................., amn
                        ve
                       b1 , b2 , ..........................., bm

sabit sayılar olmak üzere kısıtlar :

                       a11 *  x1   +  a12 * x2 + …………………………+   a1n * xn  <=  b1
                                 a21 *  x1     +  a22* x2  + …………………………+ a2n * xn   < = b2
                        ..............................................................
                        ..............................................................
                     
                       am1 *  x1   +  am2 * x2 + …………………………+   amn * xn  <=  bm

şeklinde gösterilir. Kısıtlar incelendiğinde şu özellikler göze çarpmaktadır:

Sistemin her satırı genellikle bir eşitsizliktir. Bazı durumlarda eşitlik de olabilir.
Eşitsizliklerin sol tarafları doğrusal fonksiyonlardır.
Kısıtların sayısı (m ) için bir sınırlama yoktur.

Kısıtları ifade eden eşitsizlikler , problemin çözümü olabilecek x değişkenlerinin içinde bulunduğu  «çözüm bölgesini» belirler. Sonuçta tüm kısıtları sağlayan optimum(en uygun) çözüm bulunur.



Pozitiflik koşulu

DP ‘ nin gerçek problemlere uygulanmasını kolaylaştırmak amacı ile çözümde karar değişkenlerinin negatif değer alamayacağı koşulu getirilmiştir. Matematik olarak problem çözüldüğünde  ;

             x1 , x2 , ………., xn   >= 0 olmalıdır. 




 DP modellerinin formülasyonu değişik şekillerde gösterilmektedir. En yaygın gösterim şekli aşağıda verildiği gibi matris notasyonu kullanılarak formüle etmektir.

Örnek Problem :  XX şirketi, H1 ve H2 hammaddelerinin karışımından iç ve dış duvar boyası üretmektedir. Aşağıdaki tabloda problemin temel verileri gösterilmektedir.


Şirketin yaptığı pazar araştırmasında, günlük iç boya talebinin en fazla 2 ton olduğu görülmüştür. Yine aynı araştırmada, günlük iç boya talebinin günlük dış boya talebinden fazla olduğu ve bu fazlalığın günde en çok 1 ton olduğu anlaşılmıştır. Sirket karını maksimum yapacak şekilde optimum üretim miktarını belirlemek istemektedir. Bu problem bir DP modeli olarak düşünüldüğünde 3 temel elemanı olacaktır:
1. karar değişkenleri
2. amaç fonksiyonu
3. kısıtlar
Modelin  karar değişkenleri iç ve dış boya miktarlarıdır.

x1     -->    dış boyanın günlük üretim miktarını( ton)
 x2   -->    iç boyanın günlük üretim miktarını( ton )    göstersin.

Şirket için en iyi amaç toplam karı maksimum yapmaktır. Z toplam karı göstermek üzere;

                               maksimum   Z = 5 * x1   +  4 * x2 
 
Şeklinde yazılabilir.  Modelin son elemanı hammadde ve taleple ilgili sınırlamalardır.
    
                            H1 hammaddesinin kullanımı:

                               6 * x1  + 4 * x2  ton

                           H2 hammaddesinin kullanımı da:

                               1* x1  + 2 *x2   tondur.  

Bu hammaddelerin günlük kullanımları sınırlı olduğu için kısıtları şu şekilde yazabiliriz:
                              
                            6 * x1  + 4 * x2   < = 24            H1  hammaddesi için

                            1* x1  + 2 *x2     <=   6             H2 hammaddesi için



Ayrıca  taleple ilgili sınırlamalar da vardır :
İç duvar boyası talebinin günde en çok 2 ton olması ;
                                 x2   < =  2
İç boyanın günlük üretiminin dış boyanın üretiminden en çok 1 ton fazla olması;
                                 x2    -    x1    < = 1
 Modelde yer alan  değişkenlerin negatif olmama (pozitiflik koşulu) sınırlamasını da ekleyerek matematik modeli aşağıdaki gibi yazabiliriz :
              amaç fonksiyonu :

                         maksimum   Z = 5 * x1   +  4 * x2 

               kısıtlar :
                             6 * x1  + 4 * x2   < = 24
                                   x1  + 2 *x2     <=   6
                                 -  x1    + x2             < =  1
                                            x2              < =  2
              pozitiflik koşulu :
                                            x1 , x2    > = 0

Bu kısıtların tümünü sağlayan herhangi bir çözüm uygun çözüm adını alır.

Grafik çözüm

İki değişkenli bir DP modeli grafik olarak çözülebilir. Grafik yöntemin iki önemli adımı vardır:
Modelin tüm kısıtlarının sağlandığı uygun çözümleri içeren bir çözüm uzayının belirlenmesi,
Çözüm uzayındaki tüm noktalar arasından  optimum çözümün  bulunması.

Yukarıda verilen örneğin  grafik çözümünü yapalım. Kısıtları bir koordinat sisteminde göstermenin en kolay yolu, eşitsizlikleri eşitlik şeklinde düşünerek bunlara ait doğruların çizilmesidir. Daha sonra eşitsizliğin işaretine göre doğrunun altında ya da üstünde kalan bölge çözüm bölgesi olarak seçilir. Birinci kısıtı ele alırsak;

          6 * x1  + 4 * x2   < = 24   eşitsizliğini
          6 * x1  + 4 * x2    = 24     şeklinde eşitlik olarak yazalım.

 Bu doğruyu çizebilmek için iki nokta gerekir.   x1  = 0  için  x2 ‘yi,  x2= 0  için de x1  ‘ i hesaplayabiliriz.  x1  = 0  için    x2= 6 ,  x2  = 0  için    x1 = 4 bulunur. (0,6) ve (4,0) noktalarından geçen doğru aranılan doğrudur. Eşitsizliğin yönü (<= ) şeklinde olduğu için bu doğrunun altında kalan alan bu kısıtı sağlayan alandır.   Tüm kısıtlara ait doğrular çizildikten sonra, çözüm uzayı belirlenir. Aslıda uygun çözüm bölgesi sonsuz sayıda  uygun nokta içerdiği için , bunların arasından optimum noktayı bulmamız gerekir. 
 

 

 

 

Optimum çözümün belirlenmesi için kar fonksiyonunun artış yönünün bilinmesi gerekir.  Bu da Z’e  keyfi değerler atayarak yapılabilir. Z’ e önce 10 sonra 15 değerleri verilerek;

           5 * x1   +  4 * x2     = 10    ve
            5 * x1   +  4 * x2        = 15  doğruları çizilir.

Amaç fonksiyonunun daha artırılması durumunda ABCDEF uygun çözüm uzayının dışına çıkılacaktır. Şekilden çözüm uzayının dışına C noktasından çıkıldığı görülmektedir. Dolayısıyla uygun çözümü içeren nokta C noktasıdır. C noktası 1 ve 2 numaralı kısıtların kesişim noktası olduğu için buradan  x1  = 3 ve  x2= 1.5 bulunur.  Günlük üretimde 3 ton dış boya, 1.5 ton iç boya üretildiğinde günlük kar Z= 21000$ olacaktır.  Optimum çözümün çözüm uzayının komşu köşe noktalarından birinde bulunması raslantı değildir. Amaç fonksiyonunun eğimi değiştirilse bile, yeni çözüm yine köşe noktalarından birinde olacaktır.

 

 

Örnek problem: Bir çiftlikte günde en az 800 kg özel bir karışımla yapılan  yem kullanılmaktadır.  Bu karışım, aşağıdaki tabloda verilen maddelerin belirtilen miktarları kullanılarak elde edilmektedir.

 

 


Bu ürünün bileşiminde en az %30 protein ve en çok da % 5 lif bulunması zorunludur. Firma minimum maliyetle günlük yem karışımını belirlemek istemektedir. Önce probleme ait matematik modeli kuralım:

Karar değişkenleri:
                                            x1   --->    karışımdaki mısır miktarı (kg)
                                                                    x2    --->    karışımdaki soya unu miktarı(kg)

           Amaç fonksiyonu:
                                       Minimize  Z = 0.3* x1   + 0.9 * x2   

Kısıtlar:

                                     x1   +   x2  > =  800 ( günlük üretim)  
                                  
                      0.09* x1  + 0.60* x2    > = 0.3 ( x1 +  x2  )   (protein miktarı)

                      0.02 * x1  + 0.06 * x2  < = 0.05(x1 + x2 )    ( lif miktarı)

Kısıtları ve amaç fonksiyonunu yeniden yazalım:

                                       Minimize  Z = 0.3* x1   + 0.9 * x2   
                                    x1   +   x2  > =  800                                       
                      0.21* x1  - 0.30* x2    < = 0
                      0.03* x1  - 0.01 * x2   >=  0
                                            x1 , x2    > = 0   
 

 

 

optimum noktada değişkenlerin değerleri:

x1    = 470.59 kg
x2   = 329.42 kg  
Amaç fonksiyonu: Z = 437.65 $

SİMPLEKS YÖNTEMİ

Bir doğrusal programlama modelini çözmek üzere geliştirilmiş , optimum çözümü iterasyon (ardışık yaklaşım) yoluyla bulan matematiksel bir yöntemdir. Probleme ait matematik model kurulduktan sonra, ilk  adım modeli standart DP modeli şekline getirmektir. Standart bir DP modelinde eşitsizlikler eşitlik şekline dönüştürülmelidir.

Eşitsizliklerin eşitlik haline getirilmesi

Bir DP modelinde <= yönündeki bir kısıtı eşitlik haline getirmek için eşitsizliğin sol tarafına bir artık (slack) değişken eklenir.
                            x1   + 3* x2    <= 4
eşitsizliği,
                             x1   + 3* x2  + S1  = 4
eşitliği ile aynı anlamdadır.  S1  >= 0 olup, artık değişken adını alır.
Eşitsizliğin yönü >= yönünde ise  artık değişken eklemek yerine çıkarmak gerekir. Ancak bu durumda da değişkenin negatif olmasından ötürü başlangıç çözümünde yer alamaz. Bunun için bu tür  kısıtlarda bir de yapay(artificial) değişken eklenir.
                            x1   + 2* x2    >= 6
eşitsizliği,
                            x1   + 2* x2  - S1  + A1    = 6
şeklinde eşitlik haline getirilir. Bazı modellerde  de sadece = şeklinde kısıtlar da yer alabilir. Bu durumda da eşitsizliğin sol tarafına bir yapay değişken eklenir.
           
                             2*x1    + 3* x2    = 10
eşitsizliği,
                             2* x1   + 3* x2   + A1    = 10
eşitlik haline getirilir.

Bir eşitliğin sağ tarafı mutlaka negatif olmama koşuluna uygun olmalıdır. Gerekirse bu koşulu sağlamak için eşitsizliğin her iki tarafı  –1 ile çarpılır ve eşitsizliğin yönü de değiştirilir.

Simpleks algoritması 

Simpleks algoritması uygun bir temel çözümle başlar ve daha sonra amaç fonksiyonunun daha da iyileştirildiği başka uygun çözümlerle devam eder. İlk uygun çözüm için probleme eklenen artık ve yapay değişkenlerden yararlanılır. Problemin karar değişkenleri (x1 , x2 , ………., xn  )   başlangıçta sıfır değerini alırken , artık (S ) ve yapay (A ) değişkenler sağ taraf değerlerine eşitlenir. Şimdi bir örnek problem ele alarak algoritmayı adım adım uygulayalım.

Örnek problem: Yüksek kaliteli cam ürünleri üreten bir firmanın üretimini gerçekleştirdiği 3 atölyesi mevcuttur.1. atölyede aliminyum çerçeve ve bağlantıları,2. atölyede ağaç çerçeve , 3. atölyede de cam üretilerek, kapı ve pencere    ürünleri yapılmaktadır. Kazançlarındaki azalmadan dolayı üst kademe yönetimi üretim hattını yenilemek istemektedir. Kar getirmeyen bazı ürünler üretilmeyecek, buna karşılık talebi olan bir veya 2 yeni ürün, üretim kapasitesinin izin verdiği ölçüde üretilecektir.Yeni ürün olarak aliminyum çerçeveli kapı ve çift camlı ağaç çerçeveli pencere üretilmesi kararlaştırılıyor. Pazarlama departmanı elde mevcut kapasite ile üretilecek bu ürünlerin satılacağını garanti etmektedir. Atölyelerden elde edilen bilgiler aşağıdaki tabloda verilmektedir:

1145
0
0
Yorum Yaz