Ulaştırma ve Atama Modelleri Kaynak
Transkript
Ulaştırma ve Atama Modelleri Kaynak
Ulaştırma ve Atama Modelleri Konu 2 Ulaştırma Modeli 1. Farklı kaynaklardan temin edilen bir ürün, mümkün olan minimum maliyetle farklı istikametlere taşınmaktadır. taşınmaktadır. 2. Her kaynak noktası sabit sayıda ürün arz ederken, her istikamet noktası da sabit sayıda talepte bulunmaktadır. bulunmaktadır. Doç. Dr. Fazıl GÖKGÖZ 2 / 62 1 Örnek TALEP (TON) ARZ (TON) SAMSUN İSTANBUL 150 200 ERZURUM 175 100 İZMİR 275 300 GAZİANTEP ANTALYA Doç. Dr. Fazıl GÖKGÖZ 3 / 62 Arz--Talep Arz Tane Asansörü 1. Samsun 2. Erzurum 3. Gaziantep Toplam Arz 150 175 275 600 ton Değirmen A. İstanbul B. İzmir C. Antalya Toplam Talep 200 100 300 600 ton Doç. Dr. Fazıl GÖKGÖZ 4 / 62 2 Ulaşım Maliyetleri Ulaştırma Maliyetlerinin Durumu ($/ton) Tane Silosu 1. Samsun 2. Erzurum 3. Gaziantep Değirmen A. İstanbul B. İzmir C. Antalya $6 $8 $ 10 $7 $ 11 $ 11 $4 $5 $ 12 Doç. Dr. Fazıl GÖKGÖZ 5 / 62 Lineer Programlama Modeli Dengelenmiş Ulaştırma problemlerinde; kaynağın arz miktarı ile talep edilen tutarlar birbiriyle eşittir. Doç. Dr. Fazıl GÖKGÖZ 6 / 62 3 Ulaştırma Tablosu Doç. Dr. Fazıl GÖKGÖZ 7 / 62 Ulaştırma Problemlerinde Kullanılan Yöntemler Çözüm için kullanılan yöntemler SS – Atlama Taşı Yöntemi (Stepping Stone) MODI – Geliştirilmiş Dağıtım Yöntemi Olurlu başlangıç çözümü Kuzeybatı Köşe Yöntemi Minimum Maliyetli Hücre Yöntemi VAM--Vogel‘in Yaklaşımı Yöntemi VAM Doç. Dr. Fazıl GÖKGÖZ 8 / 62 4 Kuzeybatı Köşe Yöntemi Doç. Dr. Fazıl GÖKGÖZ 9 / 62 Kuzeybatı Köşe Yöntemi ile Bulunan Olurlu Başlangıç Çözümü Başlangıç Çözümü Z = $5,925 Doç. Dr. Fazıl GÖKGÖZ 10 / 62 5 Doç. Dr. Fazıl GÖKGÖZ 11 / 62 Minimum Maliyetli Hücre Yöntemi Başlangıçtaki Minimum Maliyetli Hücrenin Dağıtımı Doç. Dr. Fazıl GÖKGÖZ 12 / 62 6 İkinci minimum maliyetli hücrenin yerleştirilmesi Doç. Dr. Fazıl GÖKGÖZ 13 / 62 Minimum Maliyetli Hücre Yöntemi ile Bulunan Olurlu Başlangıç Çözümü Başlangıç Çözümü Z = $4,550 Doç. Dr. Fazıl GÖKGÖZ 14 / 62 7 Doç. Dr. Fazıl GÖKGÖZ 15 / 62 Vogel’in Yaklaşım Yöntemi Penaltı (Ceza) Maliyeti, her hangi bir sıra veya sütundaki en küçük ve ikinci en küçük maliyetin farkıdır. VAM tekniğinde en büyük ceza maliyetinin bulunduğu sıra veya sütundaki minimum maliyetli hücreye maksimum oranda yerleşim yapılır. Doç. Dr. Fazıl GÖKGÖZ 16 / 62 8 Doç. Dr. Fazıl GÖKGÖZ 17 / 62 Doç. Dr. Fazıl GÖKGÖZ 18 / 62 9 Doç. Dr. Fazıl GÖKGÖZ 19 / 62 Vogel’in Yaklaşım Yöntemiyle Bulunan Olurlu Başlangıç Çözümü Başlangıç Çözümü Z = $5,125 Doç. Dr. Fazıl GÖKGÖZ 20 / 62 10 Doç. Dr. Fazıl GÖKGÖZ 21 / 62 Atlama Taşı Yöntemi Doç. Dr. Fazıl GÖKGÖZ 22 / 62 11 Doç. Dr. Fazıl GÖKGÖZ 23 / 62 Doç. Dr. Fazıl GÖKGÖZ 24 / 62 12 1A →1B → 3B → 3A + 6 – 8 + 5 – 4 = –$1 BALANGIÇ ÇÖZÜMÜ OPTİMAL DEĞİLDİR Doç. Dr. Fazıl GÖKGÖZ 25 / 62 Doç. Dr. Fazıl GÖKGÖZ 26 / 62 13 - + + - Doç. Dr. Fazıl GÖKGÖZ 27 / 62 Doç. Dr. Fazıl GÖKGÖZ 28 / 62 14 Hücre 1A için Öngörülen Atlama Taşı Yolu Doç. Dr. Fazıl GÖKGÖZ 29 / 62 Atlama Taşı Yöntemindeki İkinci Döngü (İterasyon) Doç. Dr. Fazıl GÖKGÖZ 30 / 62 15 Doç. Dr. Fazıl GÖKGÖZ 31 / 62 Doç. Dr. Fazıl GÖKGÖZ 32 / 62 16 Doç. Dr. Fazıl GÖKGÖZ 33 / 62 Doç. Dr. Fazıl GÖKGÖZ 34 / 62 17 Doç. Dr. Fazıl GÖKGÖZ 35 / 62 Alternatif Optimal Çözüm Doç. Dr. Fazıl GÖKGÖZ 36 / 62 18 Doç. Dr. Fazıl GÖKGÖZ 37 / 62 Geliştirilmiş Dağıtım Yöntemi (Modi) Minimum Maliyetli Hücre Yöntemiyle Bulunan Başlangıç Çözümü Doç. Dr. Fazıl GÖKGÖZ 38 / 62 19 Dağıtıma Tabi Olan Hücreler DOLU HÜCRELER Doç. Dr. Fazıl GÖKGÖZ 39 / 62 Tüm ui ve uj Değerleriyle Bulunan Başlangıç Çözümü Doç. Dr. Fazıl GÖKGÖZ 40 / 62 20 Boş Hücreler Doç. Dr. Fazıl GÖKGÖZ 41 / 62 MODI Çözüm Yöntemindeki İkinci Döngü (İterasyon) Doç. Dr. Fazıl GÖKGÖZ 42 / 62 21 Doç. Dr. Fazıl GÖKGÖZ 43 / 62 İkinci İterasyon için Yeni ui ve uj Değerleri Doç. Dr. Fazıl GÖKGÖZ 44 / 62 22 Doç. Dr. Fazıl GÖKGÖZ 45 / 62 Doç. Dr. Fazıl GÖKGÖZ 46 / 62 23 Dengelenmemiş Ulaştırma Modeli (Talep > Arz) Doç. Dr. Fazıl GÖKGÖZ 47 / 62 Dengelenmemiş Ulaştırma Modeli (Talep < Arz) Doç. Dr. Fazıl GÖKGÖZ 48 / 62 24 Dejenerasyon Durumu m sıra + n sütun – 1 = Yerleşim yapılabilecek hücre sayısı Doç. Dr. Fazıl GÖKGÖZ 49 / 62 Minimum Maliyetli Hücre Yöntemiyle Bulunan Başlangıç Çözümü m sıra + n sütun – 1 ; 3 + 3 – 1 = 5 hücreye yerleşim yapılır. Doç. Dr. Fazıl GÖKGÖZ 50 / 62 25 Başlangıç Çözümü Doç. Dr. Fazıl GÖKGÖZ 51 / 62 Doç. Dr. Fazıl GÖKGÖZ 52 / 62 26 Atlama Taşı Yöntemi İkinci İterasyon Doç. Dr. Fazıl GÖKGÖZ 53 / 62 Atama Modeli Örneği Resmi Hakemlerin, Baketbol Maçlarının Yapılacağı Bölgelere Olan Seyahat Mesafesi Her satırdaki minimum değer; satırda yer alan tüm değerlerden çıkarılır. Doç. Dr. Fazıl GÖKGÖZ 54 / 62 27 Satır Azaltılması Sonucu Atama Tablosunun Son Durumu Her sütundaki minimum değer; sütunda yer alan tüm değerlerden çıkarılır. Doç. Dr. Fazıl GÖKGÖZ 55 / 62 Sütun Azaltılması Sonucu Atama Tablosunun Son Durumu Doç. Dr. Fazıl GÖKGÖZ 56 / 62 28 Çizgi Testi ile Fırsat Maliyeti Tablosunun Elde Edilmesi 35 Atamaların sayısı, satır veya sütunların sayısından düşük olduğu takdirde çizgi testi kullanılmalıdır. Sıfırların bulunduğu satır ve sütunlar kesiştirilir ve geriye kalan sayılardan minimum olan değer (15) diğer kesişmeyen değerlerden çıkarılır. Doç. Dr. Fazıl GÖKGÖZ 57 / 62 İkinci Aşamadaki İterasyon 35 Söz konusu minimum değer (15) sıfırların bulunduğu satır ve sütunların kesiştiği noktalara ilave edilir. Sonuçta fırsat maliyeti tablosunda sıfır değer alan noktalar seçim yapılabilecek değerler setini oluşturur. Doç. Dr. Fazıl GÖKGÖZ 58 / 62 29 Doç. Dr. Fazıl GÖKGÖZ 59 / 62 Doç. Dr. Fazıl GÖKGÖZ 60 / 62 30 Doç. Dr. Fazıl GÖKGÖZ 61 / 62 ÖDEV – 2 Ulaştırma Modeli (Teslim Tarihi : 08.03.2007) Üç farklı bölgede bulunan çelik üretimi gerçekleştiren fabrikaların üretim bilgileri aşağıdadır ; Bölge Haftalık Üretim (ton) A 150 B 210 C 320 Toplam 680 Söz konusu şirketlerin sağladığı çelik dört farklı şehirdeki üretici tesislere sevkedilmektedir. ehir Haftalık Talep (ton) I 130 II 70 III 180 IV 240 Toplam 620 Doç. Dr. Fazıl GÖKGÖZ 62 / 62 31 ÖDEV – 2 Ulaştırma Modeli (Teslim Tarihi : 08.03.2007) Çeliğin ton başına nakliye maliyetleri ise aşağıdaki gibidir ; Ulaştırma Birim Maliyetleri ($/ton) Çelik Fabrikası A Üretim Tesisleri I II III IV 14 9 16 18 B 11 8 7 16 C 16 12 10 22 Bu kapsamda, nakliye yapan firmaların grevde olması nedeniyle, “B” bölgesinden “III” nolu şehre ulaştırma yapılamamakta olduğu göz önüne alınarak; a) Ulaştırma tablosunu hazırlayınız ve başlangıç çözümü yapınız, b) Problemin başlangıç değerlerini MODI yöntemiyle çözünüz, c) Çoklu optimal sonuçlar var mıdır ? Açıklayınız ve varsa tanımlayınız, d) Problemi genel lineer programlama modeli olarak da formule ediniz. Doç. Dr. Fazıl GÖKGÖZ 63 / 62 ÖDEV – 2 Ulaştırma Modeli (Teslim Tarihi : 08.03.2007) Bir çimento şirketi, ürettiği çimentoyu 3 farklı tesisten 3 farklı inşaat bölgesine sevk etmektedir. Her üç tesise ilişkin kapasite verileri ve bu tesislerden istenilen miktarlar ve birim ulaştırma maliyetleri ($/ton) verilmektedir. Gerekli başlangıç ve çözüme yönelik Ulaştırma Modelini uygulayarak optimal maliyet değerlerini ve çözümü bulunuz. İnşaat Alanları (Ulaştırma Birim Maliyetleri ($/ton) Tesis A B C Arz (Ton) 1 8 5 6 120 2 15 10 12 80 3 3 9 10 80 Talep (Ton) 150 70 60 280 Doç. Dr. Fazıl GÖKGÖZ 64 / 62 32 ÖDEV – 1 Tamsayılı Programlama Ödevlerinin Değerlendirilmesi Çözümler X1 X2 DP gevşetilmiş 1.3 6.1 Tamsayılı prog. 1 5 Yuvarlanmış 1 6 • Amaç fonksiyonunun değiştirilmemesi ve sonuçların X1 ve X2’nin değerleri olduğu hususu (Zmax. = 1.3X1 + 6.08X2 değil Zmax. = 2X1 + 3X2) • Soruda yuvarlanmış çözümün olurlu alan içerisinde olması gerektiği yazılmamıştır. Bu nedenle, cevap (X1:1,X2:6) olup, söz konusu sonucun olurlu alan içerisinde bulunmadığının ifade edilmesi gereklidir. Doç. Dr. Fazıl GÖKGÖZ 65 / 62 33