Matlab Soru Çözümleri-Kuzey Batı Yöntemi Algoritması

Herkese merhabalar. Bu yazımda Yöneylem Araştırmasında (Operation Research) görmüş olduğumuz problemlerden olan Taşıma Problemi (Transportation Problem) ‘nde başlangıç ataması yapabilmek için kullanmış olduğumuz yöntemlerden biri olan Kuzey Batı Yöntemi ‘nin algoritmasını anlatacağım. 

Kuzey Batı Yöntemi

Kuzey yarım küredeki bir haritada kuzey yönü yukarı, batı yönü de sol taraftadır. Kuzey-batı köşesi de sol üst köşedir. Bir taşıma problemini sunan tabloda sol üst köşeden başlayarak sağa ve aşağı doğru adım adım inen çözüme “kuzey-batı köşe çözümü” denir. Kuzey-batı hücresinden başladıktan sonra herhangi bir satır veya sütun dolduysa bir sonraki hücreye geçecektir. Şimdi öncelikle el ile çözümüne bakalım. Maliyet tablosu ile üretim ve talep kısıtları aşağıdaki tablolarda verilmiştir. Kuzey-Batı yönteminde maliyet tablosu en son toplam maliyeti hesaplarken işimize yarayacaktır.

Çözümü ilk olarak el ile yapalım. Karşımıza böyle bir sonuç çıkacaktır.

Kodlarımızı inceleyelim.

Öncelikle yukarıda ki gibi değişkenlerimizi tanımlıyoruz. Dışarıdan aldığımız veya el ile yazdığımız sorunun bilgilerini değişkenlere yazıyoruz. Sonrasında bizim işlem yapabilmemiz için talep ve üretim miktarlarını kullanmamız gerekmektedir. Bu yüzden geçici talep ve geçici üretim değişkenlerini ekliyoruz.

Şimdi asıl olaya gelelim. Kuzey-Batı yönteminde talep veya üretim için olabildiğince fazla atama yapılması gerekmektedir. Ve bu yapılan atamalar 3 farklı koşul oluşturmaktadır.

  • Talep Miktarı, Üretimden fazladır
  • Üretim Miktarı, Talepten azdır
  • Talep Miktarı ile Üretim miktarı eşittir

Talep miktarı üretimden fazlaysa ; sağ tarafta gördüğünüz üzere P2 nin ilk hücresinin ilk değerini talebin ilk değerinden üretimin ilk değerini çıkarttığımız takdirde elde ederiz. Yani P21=Talep1-Üretim(P1) şeklinde olacaktır.

 

 

 

Talep miktarı Üretimden az ise; sol tarafta gördüğünüz gibi bu seferde yukarıdaki işlemin tam tersini yapıyoruz. Yani P22=Üretim(2)-P21 şeklinde olmalıdır. Ancak 2.Talep 20 olduğundan en fazla 20 atama yapabiliriz. Programlama kısmında da bunu düzeltiyoruz.

 

 

 

Şimdi programlama kısmına tekrar bakalım. For döngüsü sayesinde hem talebi hem de üretim vektörlerini tek tek dolaşacaktır. Bu vektörler 0 ‘dan büyükse üretim(i) ve talep(j) koordinatlarını alarak hesaplamalara devam edecektir. Yukarıda anlatılan koşullar ise for döngüsünden sonra karar yapıları olan if-else ‘te karşımıza gelecektir. i ve j olarak aldığımız koordinatları sonuç matrisimiz olan x’e atama yapıyoruz. En son da maliyet matrisi ile sonuç matrisini (x) karşılıklı olarak çarpıp topluyoruz ve toplam maliyeti buluyoruz.

Programımızı çalıştıralım.

Kaynakça:

  • Yöneylem Araştırması-Hamdy A.-Taha
  • Operations Research Applications and Algorithms Fourth Edition-Wayne L.Winston