Yöneylem Araştırması Dersi 8. Ünite Özet
Ulaştırma Ve Atama Modelleri
Açıköğretim ders notları öğrenciler tarafından ders çalışma esnasında hazırlanmakta olup diğer ders çalışacak öğrenciler için paylaşılmaktadır. Sizlerde hazırladığınız ders notlarını paylaşmak istiyorsanız bizlere iletebilirsiniz.
Açıköğretim derslerinden Yöneylem Araştırması Dersi 8. Ünite Özet için hazırlanan ders çalışma dokümanına (ders özeti / sorularla öğrenelim) aşağıdan erişebilirsiniz. AÖF Ders Notları ile sınavlara çok daha etkili bir şekilde çalışabilirsiniz. Sınavlarınızda başarılar dileriz.
Ulaştırma Ve Atama Modelleri
Giriş
Bu ünitede, doğrusal programlamanın özel bir türü olan ulaştırma ve atama modelleri yer almaktadır. Genel olarak ürünlerin birden fazla üretim noktasından, birden fazla tüketim noktasına dağıtımı ile ilgilin problemler, ulaştırma veya atama problemleri (transportation or assignment problems) olarak adlandırılır.
Atama modelinde amaç, bir etkinliği eniyilemek için kaynak kullanımının bire bir dağıtımını sağlamaktır. Ulaştırma probleminin özel bir hali olan atama problemleri ile genellikle işlerin makinelere dağıtımı, kişilerin işlere tayini, personelin satış bölgelerine dağıtımına benzer durumlarda karşılaşılmaktadır.
Ulaştırma Modeli
Ulaştırma problemlerinde cevap aranan soru, hangi üretim merkezinden, hangi tüketim merkezine ne kadar ürün taşınacağıdır. Bu soru aynı zamanda karar değişkenlerini tanımlamakta olup, sorunun cevabı ürün dağıtım planını verecektir. Eğer bir ulaştırma modelinin toplam sunum miktarı toplam talep miktarına eşit ise, “dengelenmiş ulaştırma modeli”, eşit değilse “dengelenmemiş ulaştırma modeli” olarak adlandırılır.
Ulaştırma Tablosu
Ulaştırma tablosu, üretim merkezleri satırlarda, tüketim merkezleri sütunlarda olmak üzere m×n sayıda hücresi olan bir tablodur. Üretim ve tüketim merkezlerinin kesiştiği her bir hücre, bir karar değişkenine karşı gelir. Her hücrenin sağ veya sol üst köşesine birim taşıma maliyetleri yazılır. Üretim merkezlerinin kapasiteleri, satırların en sağında; tüketim merkezlerinin talepleri de sütunların altında yer alır.
Ulaştırma Modelinde Başlangıç Çözüm Bulma
Ulaştırma modelinde talep ve sunum kısıtlarını sağlayan herhangi bir çözüm, sıfırdan büyük eşit olma koşuluna da uyuyorsa problem için uygun bir çözümdür. Bununla birlikte, en iyi çözüm olup olmadığını sınayabilmek ve ulaştırma tablosu üzerinde işlemleri yürütebilmek için, bu çözümün “temel uygun çözüm” olması gerekir.
Bu bölümde, dengelenmiş ulaştırma modeline bir başlangıç temel uygun çözüm bulmak için en çok kullanılan üç yöntem tanıtılmaktadır. Bu yöntemler,
- Kuzeybatı köşe yöntemi (Northwest corner method)
- Enküçük maliyet yöntemi (Minimum cost method)
- VAM yöntemi (Vogel’s approximation method)
olarak sıralanabilir.
Kuzeybatı Köşe Yöntemi İle Başlangıç Çözüm Bulma
Başlangıç temel uygun çözümü oluşturmak için en basit ve hızlı olan yöntemdir. Bu yöntemde, taşıma maliyetleri göz önüne alınmaz. Ulaştırma tablosunun kuzeybatı (en sol üst) köşesinden güneydoğu köşesine doğru hücrelere değer atanır. Her adımda tablodaki bir satır veya sütun işlem dışı bırakılarak, tablo daraltılır.
Başlangıç temel uygun çözüm bulma yöntemlerini kullanırken, her adımda daraltılmış tabloları ayrı ayrı düzenlemeye gerek yoktur. Tüm işlemler aynı tablo üzerinde rahatlıkla yapılabilir.
En Küçük Maliyet Yöntemi İle Başlangıç Çözüm Bulma
Birim taşıma maliyetlerini esas alan bu yöntemde, her seferinde daraltılmış tabloda en düşük maliyetli olan hücreye atama yapılır. Atama yapılacak hücrenin seçimi haricinde, hücrelere atanacak değerin belirlenmesi, sunum ve talep miktarlarının güncellenmesi ve işlem dışı bırakma adımları kuzeybatı köşe yönteminde olduğu gibidir. Enküçük maliyet yönteminin adımları aşağıdaki şekilde sıralanabilir:
- Tablo genelinde en düşük maliyete sahip olan ve sayısal bir değer atanmamış (i, j) hücresi seçilir. En düşük maliyetli birden fazla hücre varsa, herhangi biri ele alınabilir.
- Bu hücreye, i. satırdaki sunum ve j. Sütundaki talep değerleri göz önüne alınarak, mümkün olan en büyük değer atanır.
- Atanan miktar, i. satırın sunum ve j. sütunun talep değerlerinden çıkarılarak, S i ve d j değerleri güncellenir.
- Sıfır değerine karşı gelen satır veya sütundan sadece birisi işlem dışı bırakılarak tablo daraltılır.
- İşlem dışı bırakılmamış sadece bir satır veya sütun kaldığında algoritma sonlanır. Kalan miktarlar son satır veya sütundaki uygun yerlere atanır. Aksi halde birinci adıma dönülür.
VAM Yöntemi İle Başlangıç Çözüm Bulma
VAM yöntemi, en düşük maliyet yönteminin geliştirilmiş hali olarak düşünülebilir. Tablo genelinde, birinci öncelikli hücre yerine ikinci öncelikli hücreye dağıtım yapılması halinde birim başına kaçırılacak fırsatları bulup, en büyük fırsatın kaçırılmaması esasına dayanır. Araştırma sonuçları, VAM ile bulunan bir başlangıç temel uygun çözümün, diğer yöntemlere göre daha az ardıştırma ile eniyi çözüme ulaştığını ileri sürmektedir.
Ulaştırma Modelinde Eniyilik Sınaması
Ulaştırma probleminin çözümündeki ikinci adım eniyilik sınamasıdır. Eniyilik koşulları sağlanmadığı zaman, temelde olmayan en az bir değişken için amaç fonksiyonunda istenen yönde iyileştirme yapılabilir demektir.
Ulaştırma tablosu üzerinde yer alan bir temel uygun çözümün, en iyi çözüm olup olmadığını sınamak için farklı yöntemler geliştirilmiştir. Bu bölümde önce döngü kavramından bahsedilmekte, daha sonra eniyilik sınaması için geliştirilmiş atlama taşı (stepping stone) ve MODI (Modified distribution method) yöntemleri tanıtılmaktadır.
Döngü Kavramı
Ulaştırma tablosu üzerindeki bir hücreden başlayarak, yine aynı hücrede sona eren, köşelerinde en az dört farklı hücrenin sıralandığı kapalı güzergaha döngü, çevrim veya yörünge denmektedir. Bir güzergahın döngü oluşturması için izleyen şartların sağlanması gerekir:
- İki ardışık hücre, aynı satırda ya da aynı sütunda yer almalıdır.
- Dizideki son hücre, ilk hücreyle ortak bir satır ya da sütuna sahip olmalıdır.
- Üç ardışık hücre aynı satır ya da sütunda bulunmamalıdır.
Eniyilik sınaması yaparken, ulaştırma tablosunda mutlaka (m+n-1) adet temel değişkenin yer alması gerektiği unutulmamalıdır. Eğer bozulmuş temel uygun çözüm varsa, bu değişkenlerden en az biri sıfır değeri almıştır.
Atlama Taşı Yöntemi ile Eniyilik Sınaması
Bu yöntem, mevcut çözümdeki temel dışı değişkenlerin temele alınması halinde, amaç fonksiyonunda ne kadar artış ya da azalma olacağının hesaplanmasına dayanır. Temeldışı değişkenler, ulaştırma tablosu üzerinde bir değer atanmamış boş hücrelerdir.
MODI Yöntemi ile Eniyilik Sınaması
Atlama taşı yönteminin bir dezavantajı, tüm boş hücreler için döngü bulma ve değişim değeri hesaplama zorunluluğudur. Bu bölümde, iyileşme yapılacak hücreyi tek tek denemeden bulduğu için atlama taşına göre daha hızlı olan bir yöntem tanıtılmaktadır. Başlangıç temel uygun çözümün bulunmasında sunulan üç yöntemden istediğinizi kullanabildiğiniz gibi, mevcut çözümün eniyi olup olmadığını belirlemek için de atlama taşı veya MODI yöntemlerinden herhangi birisini kullanabilirsiniz.
Ulaştırma Modelinde Yeni temel Uygun Çözüm
Ulaştırma modelinin çözümünde eniyilik sınamasından sonraki adım, eğer en iyi çözüme erişilmemişse izleyen temel uygun çözümün bulunmasıdır. Atlama taşı veya MODI yöntemlerden birisi ile eniyilik sınaması yapıldığında, eğer en iyi çözüm elde edilmemişse, daha düşük maliyetli çözüm için hangi değişkenin temelde yer alması gerektiği de belirlenmektedir.
Çözüm algoritmasının başlıca üç adımı bulunduğunu unutmayalım:
Bir başlangıç temel uygun çözümün bulunması, eniyilik sınamasının yapılması ve en iyi çözüme erişilmemişse izleyen temel uygun çözümün bulunarak ikinci adıma dönülmesi.
Atama Modeli
Verilen n adet işin, n adet işlem noktasına dağıtımına yönelik problemler için geliştirilen atama modelleri, ulaştırma modelleri gibi kendisine özel çözüm algoritmasına sahip doğrusal programlama modellerindendir.
Atama modelinde amaç, genellikle toplam maliyeti enküçüklemek için kaynak kullanımının bire bir dağıtımının yapılmasıdır. İşçilerin işlere atanması ya da işe en uygun kişi seçimi, atama modeliyle çözülebilecek bir konudur.
Problemin oluştuğu sistemin özel yapısının gerektirdiği kısıtlar dışında, problemin iki temel kısıtı vardır:
- Her iş yalnız bir işlem noktasına atanabilir.
- Her işlem noktasına yalnız bir iş atanabilir.
Atama modeli, normal bir ulaştırma problemi gibi çözülebilir. Bununla birlikte, sunum ve talep miktarının bire eşit olması Macar Algoritması olarak adlandırılan basit bir çözüm algoritmasının geliştirilmesine yol açmıştır.
Atama Modelinin Macar Algoritması İle Çözümü
Problemin kendine has yapısı sebebiyle, atama modelinin çözümü için özel algoritmalar geliştirilmiştir. Bunlardan en yaygın kullanılanı Macar Algoritmasıdır. Bu algoritma, mümkün olan her alternatifi değerlendirmeden etkin bir şekilde eniyi çözümü bulmayı sağlar.
Macar algoritması ile atama problemini çözebilmek için, aşağıdaki koşulların sağlanması gerekir:
- Problemin amacı bir etkinliğin enküçüklenmesidir.
- İşlem noktası ile iş sayısı birbirine eşittir (= n.)
- Her atama gideri c ij ? 0 koşuluna uymaktadır (c ij : i. işlem noktasını j. işe atamanın maliyeti)
Yukarıdaki koşulların sağlandığı bir atama modelinin Macar algoritması ile çözüm adımları aşağıdaki gibidir:
- Her satırdaki en küçük cij seçilip, diğer atama giderlerinden bu değer çıkartılarak, satırlara göre indirgenmiş tablo bulunur.
- İndirgenmiş tablonun her sütunundaki en küçük c ij seçilip, diğer ögelerden bu değer çıkartılarak, tablo bir kez daha indirgenir.
- Tablo üzerinde sıfır değerini alan tüm ögelerden geçen en az sayıda dikey ya da yatay doğrular çizilir. Eğer bulunan doğru sayısı = n ise, eniyi çözüme ulaşılmış olup adım beşe, değilse izleyen adıma geçilir.
- Üzerinden doğru geçmeyen satır veya sütundaki en küçük öge seçilerek, doğrular dışında kalmış diğer ögelerden bunun değeri çıkartılır, doğruların kesim noktalarındaki ögelere eklenir. üçüncü adıma dönülür.
- Her doğru üzerinde sıfır değerli hücreler esas alınarak her i için yalnız bir j olmak üzere, eniyi çözüme karşı gelen x ij değerleri yazılıp, eniyi çözüm bulunur.
Giriş
Bu ünitede, doğrusal programlamanın özel bir türü olan ulaştırma ve atama modelleri yer almaktadır. Genel olarak ürünlerin birden fazla üretim noktasından, birden fazla tüketim noktasına dağıtımı ile ilgilin problemler, ulaştırma veya atama problemleri (transportation or assignment problems) olarak adlandırılır.
Atama modelinde amaç, bir etkinliği eniyilemek için kaynak kullanımının bire bir dağıtımını sağlamaktır. Ulaştırma probleminin özel bir hali olan atama problemleri ile genellikle işlerin makinelere dağıtımı, kişilerin işlere tayini, personelin satış bölgelerine dağıtımına benzer durumlarda karşılaşılmaktadır.
Ulaştırma Modeli
Ulaştırma problemlerinde cevap aranan soru, hangi üretim merkezinden, hangi tüketim merkezine ne kadar ürün taşınacağıdır. Bu soru aynı zamanda karar değişkenlerini tanımlamakta olup, sorunun cevabı ürün dağıtım planını verecektir. Eğer bir ulaştırma modelinin toplam sunum miktarı toplam talep miktarına eşit ise, “dengelenmiş ulaştırma modeli”, eşit değilse “dengelenmemiş ulaştırma modeli” olarak adlandırılır.
Ulaştırma Tablosu
Ulaştırma tablosu, üretim merkezleri satırlarda, tüketim merkezleri sütunlarda olmak üzere m×n sayıda hücresi olan bir tablodur. Üretim ve tüketim merkezlerinin kesiştiği her bir hücre, bir karar değişkenine karşı gelir. Her hücrenin sağ veya sol üst köşesine birim taşıma maliyetleri yazılır. Üretim merkezlerinin kapasiteleri, satırların en sağında; tüketim merkezlerinin talepleri de sütunların altında yer alır.
Ulaştırma Modelinde Başlangıç Çözüm Bulma
Ulaştırma modelinde talep ve sunum kısıtlarını sağlayan herhangi bir çözüm, sıfırdan büyük eşit olma koşuluna da uyuyorsa problem için uygun bir çözümdür. Bununla birlikte, en iyi çözüm olup olmadığını sınayabilmek ve ulaştırma tablosu üzerinde işlemleri yürütebilmek için, bu çözümün “temel uygun çözüm” olması gerekir.
Bu bölümde, dengelenmiş ulaştırma modeline bir başlangıç temel uygun çözüm bulmak için en çok kullanılan üç yöntem tanıtılmaktadır. Bu yöntemler,
- Kuzeybatı köşe yöntemi (Northwest corner method)
- Enküçük maliyet yöntemi (Minimum cost method)
- VAM yöntemi (Vogel’s approximation method)
olarak sıralanabilir.
Kuzeybatı Köşe Yöntemi İle Başlangıç Çözüm Bulma
Başlangıç temel uygun çözümü oluşturmak için en basit ve hızlı olan yöntemdir. Bu yöntemde, taşıma maliyetleri göz önüne alınmaz. Ulaştırma tablosunun kuzeybatı (en sol üst) köşesinden güneydoğu köşesine doğru hücrelere değer atanır. Her adımda tablodaki bir satır veya sütun işlem dışı bırakılarak, tablo daraltılır.
Başlangıç temel uygun çözüm bulma yöntemlerini kullanırken, her adımda daraltılmış tabloları ayrı ayrı düzenlemeye gerek yoktur. Tüm işlemler aynı tablo üzerinde rahatlıkla yapılabilir.
En Küçük Maliyet Yöntemi İle Başlangıç Çözüm Bulma
Birim taşıma maliyetlerini esas alan bu yöntemde, her seferinde daraltılmış tabloda en düşük maliyetli olan hücreye atama yapılır. Atama yapılacak hücrenin seçimi haricinde, hücrelere atanacak değerin belirlenmesi, sunum ve talep miktarlarının güncellenmesi ve işlem dışı bırakma adımları kuzeybatı köşe yönteminde olduğu gibidir. Enküçük maliyet yönteminin adımları aşağıdaki şekilde sıralanabilir:
- Tablo genelinde en düşük maliyete sahip olan ve sayısal bir değer atanmamış (i, j) hücresi seçilir. En düşük maliyetli birden fazla hücre varsa, herhangi biri ele alınabilir.
- Bu hücreye, i. satırdaki sunum ve j. Sütundaki talep değerleri göz önüne alınarak, mümkün olan en büyük değer atanır.
- Atanan miktar, i. satırın sunum ve j. sütunun talep değerlerinden çıkarılarak, S i ve d j değerleri güncellenir.
- Sıfır değerine karşı gelen satır veya sütundan sadece birisi işlem dışı bırakılarak tablo daraltılır.
- İşlem dışı bırakılmamış sadece bir satır veya sütun kaldığında algoritma sonlanır. Kalan miktarlar son satır veya sütundaki uygun yerlere atanır. Aksi halde birinci adıma dönülür.
VAM Yöntemi İle Başlangıç Çözüm Bulma
VAM yöntemi, en düşük maliyet yönteminin geliştirilmiş hali olarak düşünülebilir. Tablo genelinde, birinci öncelikli hücre yerine ikinci öncelikli hücreye dağıtım yapılması halinde birim başına kaçırılacak fırsatları bulup, en büyük fırsatın kaçırılmaması esasına dayanır. Araştırma sonuçları, VAM ile bulunan bir başlangıç temel uygun çözümün, diğer yöntemlere göre daha az ardıştırma ile eniyi çözüme ulaştığını ileri sürmektedir.
Ulaştırma Modelinde Eniyilik Sınaması
Ulaştırma probleminin çözümündeki ikinci adım eniyilik sınamasıdır. Eniyilik koşulları sağlanmadığı zaman, temelde olmayan en az bir değişken için amaç fonksiyonunda istenen yönde iyileştirme yapılabilir demektir.
Ulaştırma tablosu üzerinde yer alan bir temel uygun çözümün, en iyi çözüm olup olmadığını sınamak için farklı yöntemler geliştirilmiştir. Bu bölümde önce döngü kavramından bahsedilmekte, daha sonra eniyilik sınaması için geliştirilmiş atlama taşı (stepping stone) ve MODI (Modified distribution method) yöntemleri tanıtılmaktadır.
Döngü Kavramı
Ulaştırma tablosu üzerindeki bir hücreden başlayarak, yine aynı hücrede sona eren, köşelerinde en az dört farklı hücrenin sıralandığı kapalı güzergaha döngü, çevrim veya yörünge denmektedir. Bir güzergahın döngü oluşturması için izleyen şartların sağlanması gerekir:
- İki ardışık hücre, aynı satırda ya da aynı sütunda yer almalıdır.
- Dizideki son hücre, ilk hücreyle ortak bir satır ya da sütuna sahip olmalıdır.
- Üç ardışık hücre aynı satır ya da sütunda bulunmamalıdır.
Eniyilik sınaması yaparken, ulaştırma tablosunda mutlaka (m+n-1) adet temel değişkenin yer alması gerektiği unutulmamalıdır. Eğer bozulmuş temel uygun çözüm varsa, bu değişkenlerden en az biri sıfır değeri almıştır.
Atlama Taşı Yöntemi ile Eniyilik Sınaması
Bu yöntem, mevcut çözümdeki temel dışı değişkenlerin temele alınması halinde, amaç fonksiyonunda ne kadar artış ya da azalma olacağının hesaplanmasına dayanır. Temeldışı değişkenler, ulaştırma tablosu üzerinde bir değer atanmamış boş hücrelerdir.
MODI Yöntemi ile Eniyilik Sınaması
Atlama taşı yönteminin bir dezavantajı, tüm boş hücreler için döngü bulma ve değişim değeri hesaplama zorunluluğudur. Bu bölümde, iyileşme yapılacak hücreyi tek tek denemeden bulduğu için atlama taşına göre daha hızlı olan bir yöntem tanıtılmaktadır. Başlangıç temel uygun çözümün bulunmasında sunulan üç yöntemden istediğinizi kullanabildiğiniz gibi, mevcut çözümün eniyi olup olmadığını belirlemek için de atlama taşı veya MODI yöntemlerinden herhangi birisini kullanabilirsiniz.
Ulaştırma Modelinde Yeni temel Uygun Çözüm
Ulaştırma modelinin çözümünde eniyilik sınamasından sonraki adım, eğer en iyi çözüme erişilmemişse izleyen temel uygun çözümün bulunmasıdır. Atlama taşı veya MODI yöntemlerden birisi ile eniyilik sınaması yapıldığında, eğer en iyi çözüm elde edilmemişse, daha düşük maliyetli çözüm için hangi değişkenin temelde yer alması gerektiği de belirlenmektedir.
Çözüm algoritmasının başlıca üç adımı bulunduğunu unutmayalım:
Bir başlangıç temel uygun çözümün bulunması, eniyilik sınamasının yapılması ve en iyi çözüme erişilmemişse izleyen temel uygun çözümün bulunarak ikinci adıma dönülmesi.
Atama Modeli
Verilen n adet işin, n adet işlem noktasına dağıtımına yönelik problemler için geliştirilen atama modelleri, ulaştırma modelleri gibi kendisine özel çözüm algoritmasına sahip doğrusal programlama modellerindendir.
Atama modelinde amaç, genellikle toplam maliyeti enküçüklemek için kaynak kullanımının bire bir dağıtımının yapılmasıdır. İşçilerin işlere atanması ya da işe en uygun kişi seçimi, atama modeliyle çözülebilecek bir konudur.
Problemin oluştuğu sistemin özel yapısının gerektirdiği kısıtlar dışında, problemin iki temel kısıtı vardır:
- Her iş yalnız bir işlem noktasına atanabilir.
- Her işlem noktasına yalnız bir iş atanabilir.
Atama modeli, normal bir ulaştırma problemi gibi çözülebilir. Bununla birlikte, sunum ve talep miktarının bire eşit olması Macar Algoritması olarak adlandırılan basit bir çözüm algoritmasının geliştirilmesine yol açmıştır.
Atama Modelinin Macar Algoritması İle Çözümü
Problemin kendine has yapısı sebebiyle, atama modelinin çözümü için özel algoritmalar geliştirilmiştir. Bunlardan en yaygın kullanılanı Macar Algoritmasıdır. Bu algoritma, mümkün olan her alternatifi değerlendirmeden etkin bir şekilde eniyi çözümü bulmayı sağlar.
Macar algoritması ile atama problemini çözebilmek için, aşağıdaki koşulların sağlanması gerekir:
- Problemin amacı bir etkinliğin enküçüklenmesidir.
- İşlem noktası ile iş sayısı birbirine eşittir (= n.)
- Her atama gideri c ij ? 0 koşuluna uymaktadır (c ij : i. işlem noktasını j. işe atamanın maliyeti)
Yukarıdaki koşulların sağlandığı bir atama modelinin Macar algoritması ile çözüm adımları aşağıdaki gibidir:
- Her satırdaki en küçük cij seçilip, diğer atama giderlerinden bu değer çıkartılarak, satırlara göre indirgenmiş tablo bulunur.
- İndirgenmiş tablonun her sütunundaki en küçük c ij seçilip, diğer ögelerden bu değer çıkartılarak, tablo bir kez daha indirgenir.
- Tablo üzerinde sıfır değerini alan tüm ögelerden geçen en az sayıda dikey ya da yatay doğrular çizilir. Eğer bulunan doğru sayısı = n ise, eniyi çözüme ulaşılmış olup adım beşe, değilse izleyen adıma geçilir.
- Üzerinden doğru geçmeyen satır veya sütundaki en küçük öge seçilerek, doğrular dışında kalmış diğer ögelerden bunun değeri çıkartılır, doğruların kesim noktalarındaki ögelere eklenir. üçüncü adıma dönülür.
- Her doğru üzerinde sıfır değerli hücreler esas alınarak her i için yalnız bir j olmak üzere, eniyi çözüme karşı gelen x ij değerleri yazılıp, eniyi çözüm bulunur.