Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Dinamik Programlama

Yöneylem Araştırması 18. Sunum
by

Mehmet Ali Anil

on 23 May 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Dinamik Programlama

Yöneylem Araştırması Dinamik Programlama çok zor
problem kolay alt
problemler Mehmet Ali Anıl
Davut Polat
Gökhan Çelik alt problemler
çözülür çözümler
birleştirilir Ürün Ağırlık Kazanç A B C 1 2 3 6 8 7 14 17 16 Problem: Taşıma kapasitesi 20 ton olan bir kamyonla 3 çeşit mal taşınmak istenmektedir.
Malların birim ağırlık (ton) ve sağladıkları kazançlar tabloda gösterilmiştir.
Amaç: Kamyonun 20 tonluk taşıma kapasitesinin A, B ve C arasında toplam kazancı en
büyük yapacak şekilde paylaştırılmasıdır. Problemin Çözüm Aşamaları : Kamyona A'dan, B'den ve C'den kaçar adet yükleneceği belirleneceginden;
A,B, ve C'nin herbiri bir aşama teşkil eder. Bu sebeple problem 3 aşamalıdır. Durum Değişkenleri : Herhangi bir aşamada alınacak kararı etkileyen kamyonun incelenen
ve gelecekteki aşamaları için kalan taşıma kapasitesidir. Geçiş Fonksiyonu : Geçiş fonksiyonu n. aşamanın durum değişkeni ile (n+1). aşamanın durum
değişkenini ilişkilendirmelidir. Geçiş fonksiyonu aşağıdaki gibidir. Kazanç Fonksiyonu : Kazanç fonksiyonu her aşamada, o aşamada verilen karar sonrası gerçekleşen
toplam kazancı yansıtmalıdır. , n nolu üründen sağlanan kazanç değeri olmak
üzere, n. aşamanın kazanç fonksiyonu: Buna göre, yük taşıma probleminin dinamik programlama yineleme denklemi: Ürün C : Sıra C'ye geldiğinde A ve B'den kaçar adet taşındığına bağlı olarak kamyonda 0 ile 20
ton arasında değişen kapasite bulunur. C'nin 7 ton ağırlığında olduğu göz önünde
bulundurulduğunda durum değişkeninin 0,1,2,...,19,20 gibi tek tek değerlerle değil
değer aralıklarıyla açıklanması uygun olur. Buna göre üçüncü aşama karar tablosu : 0 16 32 0 1 2 olarak tanımlanmıştır. Ürün A : 2. adımdaki gibi, sıra A'ya geldiğinde 0 ile 20 arasında değişen taşıma kapasitesi kalmış olabilir. A'dan taşınmazsa; = 0, tüm kapasite A'ya ayrılırsa, = 3 olur. 'in olası değerleri 0,1,2 ve 3 olarak belirlenir. Buna göre 1. aşama karar tablosu : olarak belirlenir 0 1 2 3 0+34=34 14+32=46 28+17=45 42+0=42 46 1 20 Çözüm : Birinci aşama karar tablosu düzenlendiğinden en iyi çözüm bulunmuştur. Bu tablodan başlayarak en iyi çözümü belirleyecek olursak; sutununda = 1' dir. Yani A'dan bir adet taşınmıştır. Böylece 20 tonluk kapasitenin 6 tonu A için kullanılacaktır. Geriye 20-6 = 14 tonluk kapasite kalmıştır. İkinci aşamadaki = 14 başlıklı satırından = 0 olduğu yani B'den taşınmayacağı belirlenir. Üçüncü aşama tablosunda ise 14 ton kapasitelik yani = 14 satırından = 2 olduğu yani C'den 2 adet taşınacağı belirlenir. Sonuçta en iyi çözüm ile 1 adet A ve 2 adet C taşınarak en büyük kazanç olan 46 elde edilmiştir. Yük Taşıma Problemi Stok Kontrol Problemi Stok düzeyinin kontrol edileceği zaman uzunluğu N eşit parçaya bölünür.
Dönemlere istem bilinmektedir.
Üretim kapasitesi sınırlıdır. Her dönem başında üretim miktarı belirlenmelidir.
Stok tükenmesi yoktur. Müşteri istemi stoktan veya cari üretimden anında karşılanır.
Toplam üretim maliyeti= üretim sabit maliyet + değişken maliyet

Problemin Özellikleri Problemin Özellikleri(devam) İşletmenin depo kapasitesi sınırlıdır.
Bulundurma maliyeti belirlidir. Elde kalan ürün miktarı ile çarpımına eşittir.
Stok durumu her ayın başında kontrol edilmektedir.


Planlama dönemindeki toplam istemin en düşük maliyetle karşılanması. Amaç: Stok kontrol Problemi- Örnek Tişört satan bir mağaza ürün satışının 5 ay sürdüğünü bilmektedir.
Araştırmalara göre gelecek yılın ilgili 5 ayındaki tahmini istemler: Ay İstem Nisan Mayıs Haziran Temmuz Ağustos 20
20 50 40 30 Stok kontrol Problemi- Örnek(devam) Üretici firma 10’dan az 50’den fazla sipariş kabul etmiyor.
Siparişler 10,20,30,40 ve 50’lik partiler halinde olmalı.
Stokta ne fazla 50 tişört olmalı. Siparis Miktari Satis Fiyati(Birim) 10 20 30 40 50 9.5 8.5 8.2 8.0
9.0 Extra harcama= Sipariş Hazırlıkları(2 TL) +Ulaştırma maliyeti(8 TL)= 10TL
Bir tişörtün bir ay stok maliyeti 0.5 TL’dir.
Mevsim sonunda elde ürün kalmaması (stok miktarının sıfır olması) istenmektedir


Tişört satış mevsimi için toplam maliyetin en küçük olmasını sağlayan sipariş yöntemi Stok kontrol Problemi- Örnek(devam) AMAÇ: Stok Kontrol Problemi - Cozum
Dinamik programlamada belirli zaman dilimleri aşama olarak değerlendirilirler.
Burada 5 aylık planlama dönemindeki her bir ay bir oluşturur. AŞAMALAR: aşama Stok Kontrol Problemi - Cozum
Burada aylara göre en iyi sipariş miktarı belirlenmek istendiği için karar değişkenleri sipariş miktarı olarak belirlenmektedir.
KARAR DEĞİŞKENLERİ: Problemin Karar değişkenleri:
Burada durum değişkeni önceki aydan devreden stok miktarı olarak tanımlanmaktadır. DURUM DEĞİŞKENLERİ: Problemin Durum Değişkenleri:
S(n+1)= Sn+Xn-Dn n=1,2,3,4,5
S0=S1 -> Başlangıç stok düzey = 0 olmalı
S6 -> Dönem sonu stok düzeyi= 0 olmalı
Sn -> n. Aşamanın durum değişkeni (stoktan)
Xn -> n. Aşamanın karar değişkeni (sipariş)
Dn -> n. Aşamanın istemi GEÇİŞ FONKSİYONU: Stok Kontrol Problemi - Cozum
Verilen karar sonucu ortaya çıkan maliyeti yansıtır.
n. Aşamanın kazanç fonksiyonu
rn(Sn,Xn)=f(Xn)+ hn *(Sn +Xn-Dn) n=1,2,3,4,5
f(Xn) -> n. Aşamada Xn adet ürün sipariş verme maliyeti = sabit sipariş maliyeti + sipariş miktarına bağlı satın alma maliyeti
hn -> bir ay stok maliyeti= 0.5

Yineleme Fonksiyonu: KAZANÇ FONKSİYONU: B1 C1 D1 D2 C2 B2 A2 C2 A2 B2 A1 Rota Belirleme 13 7 6 10 16 10 13 10 6 8 3 6 5 10 15 7 10 8 16 9 9 6 3 14 8 13 6 6 B1 13 A1 10 B3 10 C3 10 9 C2 6 10 B2 S 3 5 8 D2 A3 16 14 13 13 3 8 7 6 10 9 16 D1 6 A2 C1 8 6 7 15 T S T Stok Kontrol Problemi - Cozum Stok Kontrol Problemi - Cozum
S6=0 olacağı için Temmuz ayından en az 0, en fazla 30 devir olabilir.
Buna göre: Ağustos Ayı: Ürün B : Sıra B'ye geldiğinde 0 ile 20 arasında değişen taşıma kapasitesi kalmış olabilir. B'nin 8 ton, C'nin 7 ton ağırlığında olduklarını göz önünde bulundurarak
için tıpkı 'de olduğu gibi uygun aralıklar belirlenmesi kolaylık sağlar. Buna göre 2. aşama karar tablosu: olarak tanımlanmıştır 14 15 0 1 2 0+16=16 0+16=16 0+32=32 0+32=32 0+32=32 17+16=33 17+16=33 0+17=17 0+17=17 - - - - - 34+0=34 16 17 32 33 34 0 0 1 1 2 Stok Kontrol Problemi - Cozum
Haziran ayından devreden stok
0,10,20,30,40,50 olabilir.
Buna göre: Temmuz Ayı: Stok Kontrol Problemi - Cozum
Mayis ayından devreden stok
0,10,20,30,40,50 olabilir.
Buna göre: Haziran Ayı: Stok Kontrol Problemi - Cozum Mayis Ayı:
Nisan ayından devreden stok
0,10,20,30,40,50 olabilir.
Buna göre: Stok Kontrol Problemi - Cozum Nisan Ayı:
S1=0 olacağı için en az 20 tişort sipariş etmelidir.
Buna göre X1=0,10,20,30,40,50 olabilir.

Buna gore:
x1: 40 S1: 0 x2: 0 S2: 20 x3: 50 S3:0 x4: 40 S4:0 x5:30 S5:0 Stok Kontrol Problemi- Planlama
T C3 13 6 A3 8 B3 C3 C3 6 B3 13 8 C3 A3 A3 8 10 9 16 6 7 3 A2 D2 C2 14 B2 9 A2 6 8 A3 C3 13 A3 B3 C3 A3 B3 B3 A3 A2 13 7 A3 8 B3 10 A2 A2 A2 A2 15 8 16 C3 A3 6 B2 A3 C3 8 B2 16 13 C2 B3 A3 C3 6 9 A3 9 C3 6 8 B3 C2 C2 12 B3 6 C3 3 13 D2 B3 C3 14 D2 16 C2 D2 A2 B2 15 16 12 16 10 16 15 13 6 3 A1 5 D1 6 10 10 8 B1 C1 16 B2 15 12 D2 16 C2 A2 26 21 18 C1 B1 A1 21 D1 19 26 13 6 7 10 S 19 18 39 25 25 37 8 16 C1 A3 T 5 6 14 C2 10 7 3 B3 9 16 C3 10 8 6 13 8 B2 6 6 D1 A1 10 13 D2 6 7 S 3 10 9 A2 13 10 B1 15
Full transcript