EN KISA YOL - Endüstri Mühendisliği Bölümü

Anadolu Üniversitesi
Endüstri Mühendisliği Bölümü
İST328 Yöneylem Araştırması 2 Dersi
2010-2011 Bahar Dönemi
Hazırlayan: Doç. Dr. Nil ARAS
AÇIKLAMA
• Bu sunu izleyen kaynaklardaki örnek ve
bilgilerden faydalanarak hazırlanmıştır.
• Wayne L. Winston, OPERATIONS RESEARCH
Applications and Algorithms “Chapter 7,
Transportation, Assignment, and
Transshipment Problems”, 4th edition, 2004,
Brooks/Cole-Thomson Learning.
Rastlayabileceğiniz hataların sorumluluğu
tarafıma ait olup, beni haberdar etmenizden
memnun olacağımı ifade ederim.
Doç. Dr. Nil ARAS
2
En kısa güzergah problemi
• Ayrıtları, iki düğüm arasındaki uzaklığı gösteren bir
serimde, başlangıç düğümden (kaynak düğüm),
verilen bir bitiş düğümüne (varış düğümü) toplam
ayrıt uzunluğu enküçük olan güzergahı bulma
problemidir.
Başlangıç düğüm: initial node
Bitiş düğümü: terminal node
En kısa yol : shortest path (path of minimum length)
3
Örnek: Powerco…
• Powerco örneğini hatırlayalım. Birinci santralden
birinci şehre olan gönderimin aktarma istasyonları
vasıtasıyla gerçekleştiğini ve santral ile birinci şehir
arasında 4 adet aktarma istasyonu olduğunu
farzedelim. Santral ve şehir arasındaki enkısa yolu
bulmak için serim modellerinden faydalanabiliriz.
• Santralden gönderilecek elektrik maliyetinin uzaklıkla
doğru orantılı değişmesi halinde, hangi güzergahın
izleneceği problemi.
• Ayrıtlardaki yönler,hangi düğümden hangisine geçişin
mümkün olduğunu, her bir ayrıtın üzerindeki sayılar
ise, karşı gelen iki düğüm arasındaki uzaklığı
göstermektedir.
4
Kaynak santral +4 aktarma noktası +varış noktası =6
düğüm
3
2
4
4
2
2
6
1
3
2
3
3
5
5
Dijkstra Algoritması
• Bütün ayrıt uzunluklarının negatif olmadığı
(nonnegative) varsayımıyla,
• Bir düğümden (örneğin birinci düğüm) diğer tüm
düğümlere olan en kısa güzergahları bulur.
• Başlangıçtan bitişe en kısa güzergahı belirlerken,
yanısıra da, her düğümün başlangıca göre enkısa
güzergahını da vermekte böylece, başlangıçtan tüm
düğümlere enkısa güzergahlar bulunmuş olmaktadır.
6
Dijkstra Algoritmasının Adımları
1. Başlangıç düğüm geçerli (permanent) küme öğesi olarak
ele alınıp, komşu erişilebilir düğümler kümesi belirlenir.
2. Geçerli düğümler kümesi içinden erişilebilir düğümler
kümesine enkısa olan bağlantı (ayrıt) bulunup, saklanır
(Xij=1). Bu düğüm son düğümse durulur, değilse 3. adıma
geçilir.
3. Yapılan bağlantıya karşı gelen erişilebilir küme düğümü,
geçerli kümeye aktarılır.
4. Eldeki geçerli düğümler kümesinin erişilebilir düğümler
kümesi bulunup 2. adıma geri dönülür.
7
Örnek: Powerco…
Geçerli
Erişilebilir
Saklanan
Toplam
düğümler
düğümler
ayrıt
uzaklık
kümesi
kümesi
1
2 ,3
(1,3)
3
1,3
2,5
(1,2)
4
1,3,2
4,5
(3,5)
6
1,3,2,5
4,6
(2,4)
7
6
(5,6)
8
1,3,2,5,4
8
Geçerli düğümler kümesi ={1}
3
2
4
4
2
2
6
1
3
2
3
3
5
9
Erişilebilir düğümler kümesi ={2,3}
3
2
4
4
2
2
6
1
3
2
3
3
5
10
Saklanan ayrıt=(1,3)
3
2
4
4
2
2
6
1
3
2
3
3
5
11
Geçerli düğümler kümesi={1,3}
Erişilebilir düğümler kümesi ={2,5}
3
2
4
4
2
2
6
1
3
2
3
3
5
12
Saklanan ayrıt =(1,2)
3
2
4
4
2
2
6
1
3
2
3
3
5
13
Geçerli düğümler kümesi={1,2,3}
Erişilebilir düğümler kümesi ={4,5}
3
2
4
4
2
2
6
1
3
2
3
3
5
14
Saklanan ayrıt =(3,5), (2,5)
3
2
4
4
2
2
6
1
3
2
3
3
5
15
Geçerli düğümler kümesi={1,2,3,5}
Erişilebilir düğümler kümesi ={4,6}
3
4
2
4
2
2
6
1
3
2
3
3
5
16
Saklanan ayrıt =(2,4)
3
2
4
4
2
2
6
1
3
2
3
3
5
17
Geçerli düğümler kümesi={1,2,3,4,5}
Erişilebilir düğümler kümesi ={6}
3
2
4
4
2
2
6
1
3
2
3
3
5
18
Saklanan ayrıt =(5,6)
3
2
4
4
2
2
6
1
3
2
3
3
5
19
EN KISA YOL (1): 1 3 5 6
EN KISA YOL (2): 1 2 5 6
3
2
4
4
2
2
6
1
3
2
3
3
5
20
DONANIM YENİLEME PROBLEMİNİN
EN KISA YOL PROBLEMİNE
DÖNÜŞTÜRÜLMESİ
Anadolu Üniversitesi, IST328 Yöneylem Araştırması 2, 2011 Bahar, Doç. Dr. Nil Aras
21
(Winston, sayfa 415)
• Yeni satın alınan bir otomobilin fiyatı 12,000 $ dır
(t=0 zamanında). Bir otomobilin bir yıllık bakım
maliyeti, yıl başlangıcındaki yaşına bağlıdır. Otomobil
eskidikçe, artan yüksek bakım maliyetlerini
kabullenmek yerine, eski arabayı takas yapıp yine
12,000 $ a yeni bir araba satın alınabilir. Her yılın
başında arabanın yenileneceği veya kullanılacağı
kararı verilecektir.
• Hedef, izleyen 5 yıl boyunca ortaya çıkacak net
maliyeti enküçükleyecek bir stratejinin belirlenmesidir.
(Yeni araba satın alma fiyatının 5 yıl boyunca
değişmeyeceği varsayılmaktadır.)
22
Arabanın
yaşı (yıl)
Yıllık bakım
masrafı
Arabanın
yaşı (yıl)
Takas fiyatı
0
$2,000
1
$7,000
1
$4,000
2
$6,000
2
$5,000
3
$2,000
3
$9,000
4
$1,000
4
$12,000
5
$0
23
Problemin serim modeli
C16
C15
C14
C13
1
C12 2
C23
C26
C25
C24
3
C34 4
C45
C35
•
•
•
•
5
C56
6
C46
C36
Serim 6 düğümden oluşur. i, j: yıllar olmak üzere;
(i,j) ayrıtı : i. yıl başlangıcında yeni bir araba satın alma ve
i. yıl bitimi j. yıl başlangıcına kadar onu kullanma
(i,j) ayrıtının uzunluğu: toplam net maliyet (cij)
cij= [i. yılın başlangıcında yeni araba satın alma maliyeti] +
[i, i+1, …, j-1 yılları boyunca oluşan bakım masrafı] – [j.
yılın başlangıcında takas değeri]
Anadolu Üniversitesi, IST328 Yöneylem Araştırması 2, 2011 Bahar, Doç. Dr. Nil Aras
24
3 yılın başında yeni araba satın alma maliyeti
+ 3 yıllık bakım masrafı
- 3 yıl sonunda takas fiyatı
Yıl
(Arabanın yaşı)
Toplam
Bakım
masrafı
Yıl sonu
itibarıyla
Takas fiyatı
1
2
7
(2+12-7)=7
2
6
6
(6+12-6)=12
3
11
2
(11+12-2) =21
4
20
1
(20+12-1)=31
5
32
0
(32+12-0)=44
Net maliyet
(1000$)
25
c12=2+12-7=7
c13=2+4+12-6=12
c14=2+4+5+12-2=21
c15=2+4+5+9+12-1=31
c26=2+4+5+9+12-1=31
c34=2+12-7=7
c35=2+4+12-6=12
c36=2+4+5+12-2=21
c16=2+4+5+9+12+12-0=44
c23=2+12-7=7
c24=2+4+12-6=12
c25=2+4+5+12-2=21
c45=2+12-7=7
c46=2+4+12-6=12
c56=2+12-7=7
26
44
31
21
12
1
7
2
31
21
12
7
3
7
4
7
12
5
7
6
12
21
Problem, artık 1. düğümden 6. düğüme olan en kısa
yolun bulunması problemine dönüştüğünden,
Dijkstra algoritması ile çözüm bulunur.
27