DİNAMİK PROGRAMLAMA

Dinamik programlama, yöneylem araştırmasında kullanılan optimizasyon yöntemlerinden birisidir. Optimizasyonda amaç, mevcut kısıtlayıcı koşullar altında, eldeki sorunla ilgili en iyi karara varmaktır.

Biri diğerini izleyen ve karşılıklı etkileri olan bir dizi kararın bütünüyle ele alındığı problemler için geliştirilen karar modelleri ve bunların çözümleri “Dinamik Programlama” başlığı altında incelenir. Öte yandan incelenen problemin biri diğeriyle ilişkili alt problemlere ayrılabilme özelliğini taşıması ya da bir problem için geliştirilen karar modelinin, birbirine bağlı karar modelleri haline dönüştürülmesi, dinamik programlama uygulaması için yeterli olmaktadır.

Bazı ekonomik değişme ve gelişmeler, gelecek dönem için önceden yapılan planları geçersiz kılabilir. Bu durumda yeni bir planlamaya gereksinim vardır ya da önceki plan güncelleştirilmelidir. Koşullar bir zaman sürecinde değişiyorsa ve bunların alınan kararlara etkisi önemli ise, dinamik programlama modellerine gereksinim vardır.

1.DİNAMİK PROGRAMLAMADA KULLANILAN KAVRAMLAR

Dinamik programlama terminolojisinde aşama, durum, geçiş fonksiyonları, karar ve optimal politika adı verilen beş önemli kavram vardır.

AŞAMA:

Çok aşamalı bir karar probleminde, karar verilmesi gereken noktalar olarak da tanımlanabilir. Karar probleminin bir parçası olan aşama, kararların verilmesinde ve verilen kararların düzenlenmesinde kullanılmaktadır. Aşama sayısı sürecin uzunluğuna bağlıdır. Aşama yapısını belirleyen önemli bir özellik, sürecin sürekli ya da kesikli olmasıdır.

DURUM:

Her bir aşamada sistemin veya dğişkenlerin alabileceği değerdir. Başka bir ifade ile durum, bir aşama ve onu izleyen aşamalara dağıtılan kaynaklardır. Durum kavramı mutlak bir kavram olmayıp, analizin özelliğine bağlıdır. Herhangi bir stok problemi için stok düzeyi, üretim problemi için üretim düzeyi vs. herhangi bir aşamanın durumunu gösterebilir.

KARAR:

Herhangi bir süreçte aşamaları tamamlama ile ilgili seçenekler arasından bir seçim yapılması işlemi karar olarak isimlendirilir. Belirli bir durum ve aşamada verilen bir karar, sürecin hem durumunu hem de aşamasını değiştirir. Dolayısıyla her karar, geçerli bir durumdan bir sonraki aşamaya bağlı olan duruma geçişi etkiler. Her aşamada karar verme süreci, o aşamanın seçeneklerinden birinin seçimi ile sonuçlanır. Buna aşama kararı denir.

OPTİMAL POLİTİKA:

Çok aşamalı bir karar sürecinin her karara bağlı, maliyet ve kar cinsinden bir getirisi vardır. Bu getiri sürecin aşama ve durumu ile birlikte değişir. Optimal politika, sürecin herbir aşaması için, verilen kararların bir sırasıdır: Çözüm bir aşamadan diğerine sıra önceliğine göre gidilerek elde edilir ve son aşamaya erişildikten sonra her parametre için değerler belirlenerek işlem tamamlanır. Böylece en uygun politika oluşturulmuş olunur.

GEÇİŞ FONKSİYONLARI:

Her aşamanın bulunabilecek durumlarında verilebilecek karara göre, bu aşamayı izleyen veya daha önceki aşamanın hangi durumuna gelineceğini belirleyen ilişkilere, geçiş fonksiyonları denir.

2. OPTİMALİTE (EN UYGUNLUK) KURAMI

Dinamik programlama modelinin temelini oluşturan kuram, Bellman tarafından ortaya atılan optimalite kuramıdır. Bu kurama göre;

“Bir optimal politikanın özelliği, başlangıç durumu ve başlangıç kararları ne olursa olsun geri kalan kararlar, ilk verilen kararların sonucuna göre optimal bir politika oluşturur”. Dolayısıyla izlenecek çözüm yntemi öyledir ki, önceki karar ne olursa olsun, sonraki aşamalarda yne optimal politika elde edilir.

Dinamik programlamada süreç için optimal politika, at optimal politikalardan meydana gelir. Geriye doğru gidilirken n-1 aşama süreçlerine n’inci aşama karar süreçlerinin yerleştirilmesini, ileriye doğru gidilirken de n aşama süreçlerine n-1’inci aşama karar süreçlerinin yerleştirilmesini sağlar. Örneğin, bir enbüyükleme probleminde, belirli bir (xn ) durumunda bulunan bir aşamadan (n), olası durumlara bağlı olarak br sonraki aşamaya geçmenin optimal getiri değerleri fi (xi ) biliniyorsa, n. aşamanın xn durumundaki getirisi ile (n-1). Aşamanın yeni durumundaki getirileri toplanarak en büyük değere sahip alternatifler seçilir.

3. ÇOK AŞAMALI KARAR SÜREÇLERİ

Çok aşamalı karar süreci; herhangi bir yöntem veya kritere göre sıralı adımlara ayrılabilen bir karar süreci ya da ardışık olarak bir araya getirilebilen aşamalar olarak tanımlanabilir.

Çok aşamalı bir süreç incelenirken sürecin uzunluğu ve sistemin durumu ele alınmalıdır. Çünkü çok aşamalı bir karar süreci sistemin ilk durumu ve sürecin uzunluğu ile belirlenebilir.

4. DİNAMİK PROGRAMLAMA TÜRLERİ

Dinamik programlama problemlerinin ortaya çıkışında, ekonomik süreçlerin incelenmesi önemli bir yer tutar. Bir ekonomik süreç belli ölçüde rassal bir özellik taşıyabildiği gibi, sürecin denetlenme süreci de sınırlıdır. Buna göre dnamik programlama problemleri, rassallığın bulunduğu durum ve blunmadığı durum olmak üzere iki türlü sınıflandırabilir.

Bir süreçte aşamalar ve durum değerleri sonlu ise çk aşamalı karar süreci de sonludur. Eğer bir süreç sonsuz uzunlukta ya da pratik olarak çok geniş ise bu durumda sürecin sonsuz olduğu söylenebilir.

Süreç hakkında hiç hiç bilgi edinilemiyor ya da çok az bilgi edinilebiliyorsa bu bilinmeyen bir süreçtir. Bu durumda konu ile ilgili dinamik programlama modelini formüle etmek olanaksızdır.

Herhangi bir deterministik ve stokastik dinamik programlama problemi sonlu ve sonsuz durumlarına göre, dört türlü sınıflandırılabilir. Bu durumlar aşağıdaki gibidir. Burada,

N: Aşama sayısını,

a,b: Sınır değerlerini göstermektedir.

a £ N £ b

A B

-¥ £ N £ b

A B

a £ N £ +¥

A B

-¥ £ N £ +¥

A B

 

Burada ekonomik yönden en önemli olan durum, sağ tarafı açık, sol tarafı kapalı durumdur. Çünkü ekonomik kararlar geleceğe dönüktür. Gelecek ile ilgili bilgiler ise belirsizlik taşırlar ve bunları önceden tam olarak bilmek çoğu zaman olanaksızdır.

DETERMİNİSTİK DİNAMİK PROGRAMLAMA PROBLEMLERİ

Çok aşamalı bir karar sürecinde, karara etki eden tüm dışsal etmenler (faktörler) tam olarak bilinirse süreç deterministiktir. Buna bağlı olarak dinamik programlamada deterministiktir.

Bir dinamik programlama probleminin çözümüne, uygun bir modelin kurulması ile başlanır. Dinamik programlama ile ilgili problemler biçimsel olarak ya da konuları açısından birbirlerinden oldukça büyük farklılıklar gösterebilmektedirler. Bu nedenle tüm dinamik programlama modellerini içeren ve bunların çözümünü belirleyen tek bir yöntem yoktur. Farklı türdeki modellerin çözümlerinde kullanılmaktadır.

Tablosal yöntemde herhangi bir süreçle ilgili tüm aşamalar için bütün durumlar göz önünde bulundurularak tüm seçenekler belirlenir. Her aşama ile ilgili seçenekler arasından en iyileri seçilerek bir tabloya yerleştirilir. Tablosal yöntem, elde edilen bu tablodan hareketle optimal politikanın belirlendiği yöntem olarak tanımlanabilir. Bu yöntemde seçenekler arasından seçim yapılırken, seçilen seçeneğin uygun çözüm sağlayıp sağlamadığı da çözüm sırasında göz önünde bulundurulur. Dolayısıyla, yöntemden elde edilen çözümler de uygun çözüm olmaktadır. Diğer bir deyişle tablosal yöntem, dinamik programlamanın sadece uygun seçeneklerini göz önüne alarak çözüm yapılmasına olanak sağlar.

Analitik yöntem; verilen dönüşüm denklemlerinin her bir aşamada türevleri alınarak bu aşamalar için optimal değerlerin bulunmaya çalışıldığı bir yöntemdir. Dönüşüm denklemi her bir aşamada tek bir değişkene bağlı olarak eniyilenmeye çalışılır.

Dinamik programlama problemlerinin çözümü, yukarıda anlatılan yöntemlerden birisi kullanılarak; baştan sona doğru yani ileriye doğru çözüm yolu (tümevarım) veya sondan başa doğru yani geriye doğru çözüm yolu (tümdengelim) izlenerek, aşama aşama elde edilir.

Çözümde tümdengelimin mi yoksa tümevarımın mı kullanılacağını belirleyen, poblemin yapısı ve araştırmacıların probleme yaklaşım biçimleri olmaktadır. Sonu belli olan bir problemde tümdengelim işlemi uygulanır. Devam etmekte olan bir faaliyetin bütün hesaplamalarını tekrarlamamak için de tümevarım işlemini uygulamak yerinde olur.

1.DÖNÜŞÜM DENKLEMLERİNİN OLUŞTURULMASI

Dinamik programlamanın temelindeki düşünce; problemin, geriye dönüş ilişkileri veya dönüşüm fonksiyonlarınca tanımlanmasıdır.

Dinamik programlamada doğrusal programlamada olduğu gibi problemin formüle edilmesi ve çözümü için standart bir yaklaşım yoktur. DP dönüşüm fonksiyonları, doğrusal programlamanın tersine biçimsel olarak birbirlerinden oldukça farklı olabilmektedir. Ancak dinamik programlamada her hangi bir aşama, kendisinden bir önceki ya da bir sonraki aşama ile ilgili dönüşüm fonksiyonu da buna uygun olarak formüle edilmek zorundadır.

1.1. İleriye Doğru Çözüm Yolu İçin Dönüşüm Foknsiyonlarının Oluşturulması

Bu yöntemde n-1’inci aşama ile ilgili bilgiler, n’inci aşamanın karar girdilerini oluştururlar. Çözüme, birinci aşamada başlanarak 2, 3, …………..,n-1, n’inci aşamaya doğru gidileceğinden dönüşüm fonksiyonuda buna uygun olarak formüle edilmelidir.

Örnek: Yün üretimi ile ilgilenen ÖZSE işletmesinin yapağılarını işleyen üç makinesi vardır. Makinelerin ton başına üretim maliyetleri aşağıda verilmiştir (1000TL).

Yapağı Miktarı (X)

1.makinenin

2. makinenin

3. Makinenin

(ton)

maliyeti C1(x1)

maliyeti C2(x2)

maliyeti C3(x3)

0

0

0

0

1

1

2

4

2

2

3

5

3

4

4

6

4

6

5

7

5

8

7

9

6

10

9

10

7

13

11

12

8

16

14

13

9

20

17

14

10

25

20

16

İşletmenin yöneticisi toplam maliyeti en küçükleyen en uygun üretim planının, yani her bir makinede üretilecek en uygun üretim miktarının belirlenmesini istemektedir. Şimdi, süreci sonlu ve kararların çıktı değerleri önceden bilinen problemin dönüşüm denklemini kuralım.

Problemde;

xi : i'inci makinada üretilecek üıün miktarını ,

X : Toplam üretim miktarını,

Ci(xi) :i'inci makinanın xi duıumundaki maliyetini göstersin.

Problemin dinaınik programlama çözümü için gerekli olan dönüşüm fonksiyonu kurulmadan önce, problemle ilgili durum ve aşamaların belirlenmesi gerekir.

Problemde, herbir makinada üretilebilecek ürün miktarları, durum kavramına karşılık gelmektedir. Buna bağlı olarak;

x1 : 1. durum

x2 : 2. durum

xn : n'inci durumu göstermektedir.

Problemde, xn= X'dir ve X'in değeri kesin olarak bilinmektedir. Bütün i değerleri

(i = 0, 1, 2, ....., n) için 0 £ i £ X olduğu varsayılmakta ve makinalara yapılabilecek tahsisler;

xi = 0 ise i'inci makinaya kadar herhangi bir tahsis yapılmadığını,

xi = X ise bütün üretimin i'inci makinaya kadar olan makinalarda yapıldığını (i'inci makina dahil),

0 £ xi £ X ise i'inci makinalara xi ‘nin, kalan makinalara ise (X-xi)'nin tahsis edilmiş olduğunu gösterir.

Problemde herbir makina, aşamalara karşılık gelmektedir. Buna göre;

1. makina 1. Aşamayı

2. makina 2. aşamayı

n. makina n. aşamayı göstermektedir.

Ayrıca;

fn(X): n'inci aşamada, optimal bir düzenlemenin kullanılması ile X durumundaki toplam getiriyi gösterir. Dolayısıyla bizim örneğimizde;

fn(X): X üretim miktarının n makinada üretilmesi ile ortaya çıkacak minimum toplam maliyeti göstermekte kullanılacaktır.

Bu simgeleri kullanarak problemle ilgili aşağıdaki fonksiyon yazılabilir.

fn(X) = min.Y(x1, x2,………….. xn)

Buradan,

n

MinY=S Ci(xi)= C1(x1)+ C2(x2)+……………+Cn(xn)

i=1

kısıtlayıcı denklem;

n

S xi = X

i=1

ve xi ³ 0 i = 1, 2, ...., n yazılabilir.

Görüldüğü gibi, fonksiyon üretim miktarı ve bunlara karşılık gelen maliyet değerlerine bağlıdır. Şimdi bu değerlerden hareketle dinamik programlama ile ilgili dönüşüm fonksiyonunu yazmaya çalışalım.

fn(X) = min. [Cn(xn)+fn-1(X-xn)]

Kısıtlayıcı koşul

0 £ xn £ X

Burada;

xn: n'inci aşamanın alabileceği türlü durum değerlerini (xn = 0, 1 , ...., X)

X : Sürecin o andaki durumunu

Cn(xn): n aşamanın türlü durum değerlerine karşılık gelen maliyet değerleri

fn-1(X-xn) = (X-xn) durumunda n-1 aşama sürecinin maliyet değerini göstermektedir.

Şimdi bu denklemin nasıl elde edildiğini açıklamaya çalışalım.

Birinci aşama için modeli formüle ederken x1'in değeri kesin olarak bilinmemektedir. Bu durumda 0 £ x1£ X olmak üzere, x1'in tüm uygun değerleri için optimal çözümler hesaplanır. Bulunan değerlerin her biri için optimum seçenek, bu aşamadaki seçenekler arasından seçilir. Problemde söz konusu olan seçenek; amacımız maliyet minimizasyonu olduğundan, birim başına en düşük maliyeti veren seçenektir.

Birinci aşamada x1 ile belirlenen optimum seçeneği f1(X) ile gösterirsek, dinamik programlama problemi bu f1(X) ifadesini minimize eden x1 değerinin bulunması olacaktır. Birinci aşamada optimal çözüm, f1(X), yalnız x1'in bir fonksiyonudur.

f1 (X) = c1 (x1) kısıtlayıcı koşul

0 £ x1£ X

İkinci aşamada, x2, varsayım gereği yine 0, 1, 2, ...., X değerlerini alabilir. Verilen bir X (x = 0, 1, 2, ...., X) değeri için ikinci aşamada optimal seçenek x2 £ X koşulunu sağlayan tüm i seçenekleri arasından, aşağıdaki durumlar gerçekleşecek şekilde seçilir.

İkinci aşamada i seçeneğinin maliyeti c2(x2)

x1=X – x2 durumunda birinci aşamada elde edilen maliyet c1(x1) olmak üzere, bu iki aşama ile ilgili maliyetler toplanır ve en düşük maliyet toplamını veren seçenek seçilir. Söylenenleri simgelerle ifade edersek;

f1(X) = c1(x1)

f1(X-x2) = f1(X) olmak üzere

f2(X) = min. [c2(x2) + f1(X-x2)] yazılabilir.

Denklem için kısıtlayıcı koşul

0 £ x2£ X

Görüldüğü gibi f2(X) değeri birinci ve ikinci aşama maliyetlerinin toplamıdır ve yalnız X2 nin bir fonksiyonudur.

Modelde x2= X ise x1 = 0'dır. Bu durum birinci aşamada üretim yapılmayacak anlamına gelir. Eğer (X-x2) = x1 ³ 0 ise, birinci aşamada x1'in alacağı değer kadar üretim yapılacak demektir.

Yukarıda ikinci aşama için yapılan işlemler, 3, 4, ....., n-1 ve n’inci aşamalar için de yapılınca dinamik programlama probleminin çözümü için gerekli olan dönüşüm fonksiyonları oluşturulmuş olacaktır. Bu yapılan işlemler "yineleme ilişkileri" olarak da bilinir ve dayanağı Bellman'ın optimalite ilkesidir. Bu ilkeye göre herhangi bir aşamada alınmış bir kararın, daha önceki aşamalarda verilmiş olan kararlara etkisini geriye doğru izlemeye gerek yoktur. Geri kalan aşamalar için kararlar, daha önceki aşamalarda belirlenmiş olan politikayı gözönüne almadan saptanacaktır. Bunların toplamı da optimal politikayı verecektir. Bu durum D.P.'nin temel özelliğidir.

İleriye doğru çözüm yolunun kullanıldığı durumlarda türlü aşamalar için oluşturulan dönüşüm fonksiyonları aşağıda özet olarak verilmiştir. Kısıtlayıcı koşullar dönüşüm fonksiyonlarının altında gösterilmektedir.

Birinci aşama için,

f1(X)=min. [c1(x1)]

0 £ x1£ X

İkinci aşama için,

f2(X) = min. [c2(x2) + f1(X-x2)]

0£ x2£ X

n-1'inci aşama için,

fn-1(X) = min. [cn-1(xn-1) + fn-2(X-xn-1))

0£ xn-1£ X

n'inci aşama için,

fn(X) = min. [cn(xn) + fn-1(X-xn)

0£ xn£ X

Modelden görüldüğü gibi herhangi bir aşama kendinden bir önceki aşama ile ilgilidir. Örneğin f2(X)'in belirlenmesinde f1(X), fn(X)'in belirlenmesinde fn-1(X) kullanılmaktadır.

Şimdi de geriye doğru çözüm yolu için dönüşüm denkleminin oluşturulmasını görelim.

1.2. Geriye Doğru Çözüm Yolu İçin Dönüşüm Fonksiyonunun Oluşturulması

İleriye doğru çözüm yolu için anlatılanlar ve ileri sürülen varsayımlar bu çözüm yolu içinde aynen geçerlidir. Bu nedenle dönüşüm fonksiyonunun oluşturulmasının yeniden anlatılması gereksiz sayılabilir. Ancak bu yolla dönüşüm fonksiyonu formüle edileceği zaman işleme n'inci aşamadan başlanarak, n-1, n-2, ....., 3, 2, 1 aşamalara gelinecek şekilde model kurulmalıdır. Yani n-1 aşama süreçlerine, n. aşama karar değerleri fn(X) yerleştirilecek-

tir. n. kademe için,

fn(X)= min [cn(xn)]

0£ xn£ X

n-1. kademe için,

fn-1(X)=min [cn-1(xn-1) + fn(X- xn-1 )

0£ xn-1£ X

1. kademe için,

f1(X) = min [c1(x1) + f2(X- x1 )

0£ x1£ X

Dönüşüm fonksiyonlarının oluşturulmasından sonra problemin dinamik programlama çözümlemesine geçilebilir.

2.TABLOSAL YÖNTEM

Tablosal yöntemin ne olduğu konusuna değinmiştik. Şimdi bu yöntemi bir örnek üzerinde daha geniş olarak ele alacağız. Problemi önce ileriye doğru çözüm yolunu kullanarak çözmeye çalışalım.

2.l. İleriye Doğru Çözüm Yolu

Problem, dönüşüm fonksiyonu yardımıyla birinci kademeden başlanarak çözümlenecektir. Çözüm için önce problemin dinamik programlama modelinin kurulması gerekir.

Birinci aşamada optimum kararın verilebilmesi için f1(X) değerleri belirlenmelidir. 0£ x1£ X koşulu altında.

f1(X) = C1(x1 ) 'dir.

Birinci makinada ürün üretilmediğinde f1(X)değeri sıfır olacaktır. Bütün ürün bu makinada üretilirse f1(X) değeri C1(x1 ) 'in alacağı değere eşit olacaktır.

Şimdi x1'in alabileceği türlü değerler için f1(X)'i belirleyelim.

X

x1

C1(x1)

f1(X)

0

0

0

0

1

1

1

1

2

2

2

2

3

3

4

4

4

4

6

6

5

5

8

8

6

6

10

10

7

7

13

13

8

8

16

16

9

9

20

20

10

10

25

25

 

Böylece x1'in aldığı türlü değerler için f1(X)'in değerleri belirlenmiş oldu. Bu sonuçlar Tablo 1'in üçüncü sütununda topluca gösterilmiştir.

İkinci aşamada optimum kararların belirlenebilmesi için f2(X)'in değerlerinin bulunması gerekir. f2(X) değerlerinin bulunmasında, C2(x2) ve f1(X- x2) değerleri kullanılacaktır. Bunu sözlü olarak ifade edecek olursak, ikinci aşamanın maliyet fonksiyonunun değerleri, kısıtlayıcıları doyurmak koşuluyla, her durum için birinci aşamanın maliyet değerleri ile ikinci aşamanın maliyet değerleri birlikte işlem gördürülerek elde edilecektir. Buradan hareketle ikinci aşama için dönüşüm fonksiyonu,

f2(X) = min [c2(x2) + f1(X- x2)]

O£ x2£ X

yazılabilir.

Şimdi ikinci aşama için çözüm işleminin uygulanmasına geçelim. X = 1 durumu için (bir birim ürün üretilmesi duıumu);

f2(1) = min [c2(x2)+f1(1- x2 )]

O£ x2£ 1

Buradan

C2 (1)+f1 (0) = 2+0=2

f2(1) = min

C2 (0)+f1 (1) =0+1=1

O£ x2£ 1 elde edilir.

Görüldüğü üzere bir birimlik çıktı birinci makinada veya ikinci makinada üretilebilir. Ürün birinci makinada üretilirse bunun maliyeti 1 TL., ikinci makinada üretilirse 2 TL.'dir. Küçük maliyet "1" olduğu için x1=1, x2=0 olacaktır. Bu da bize sadece bir birim üıün üretilmesi durumunda üretimin birinci makinada yapılması gerektiğini gösterir. Modelimizde, seçenekler aynı zamanda O£ x2£ 1 koşulunu da sağlamaktadır.

X = 2 (iki birim ürün üretilmesi) durumu için;

f2(2) = min [c2(x2)+f1(2- x2 )]

O£ x2£ 2

 

 

C2 (0)+f3 (2) = 3+0=3

f2(2) = min C2 (1)+f3 (1) =2+4=6

C2 (2)+f3 (0) =0+5=5

O£ x2£ 2

Diğer durumlar için de aynı yol izlenerek, ikinci aşama için (O£ x2£ X) olmak üzere, tüm durumlara karşılık gelen maliyet fonksiyonunun değerleri elde edilir.Geri kalan durumlarla ilgili getiri değerleri aşağıdaki gibidir.

 

 

 

C2 (2)+f1 (0) = 3+0=3

f2(2) = min C2 (1)+f1 (1) =2+1=3

C2 (0)+f1 (2) =0+2=2

O£ x2£ 2

Burada en küçük maliyet değeri 2 olduğundan, buna karşılık gelen x2= 0, x1 =2 duıumunda f2(2) = 2'dir. X = 3 duıumunda;

f2(3) = min [c2(x2)+f1(3- x2 )]

O£ x2£ 3

 

 

 

 

 

 

C2 (3)+f1 (0) = 4+0=4

C2 (2)+f1 (1) =3+1=4

f2(3) = min

C2 (1)+f1 (2) =2+2=4

C2 (0)+f1 (3) =0+4=4

O£ x2£ 3

Görüldüğü gibi f2(3) için bütün seçeneklerin değerleri eşit çıkmaktadır. Yalnız üç birim ürün üretilme durumunda bu dört seçenekten hangisi seçilirse seçilsin, üretimin maliyeti 4 birim olacaktır. Bu durum seçenekli çözüm olduğunu göstermektedir.

Problemin çözümünde dinamik programlama tekniği kullanıldığında, bu dört seçenekten herhangi birisi rastgele seçilebilir. Herhangi bir fırma yöneticisi bu seçeneklerden hangisinin seçileceğine, içinde bulunulan diğer sınırlayıcı koşulları da gözönünde bulundurarak karar verecektir. Biz burada dördüncü seçeneği kullanarak bu simgelerin ne anlama geldiğini açıklayalım. Bu durumda x1= 3 ve x2= 0 için f2(3)= 4'tür. Bu, eğer 3 birim ürün üretilmesi gerekiyor ise, bunun hepsinin birinci makinada üretilmesi gerektigini göstermektedir.

X = 4 durumunda,

f2(4)= min [c2 (x2)+f1 (4- x2)]

O£ x2£ 4

 

 

 

 

C2 (4)+f1 (0) = 5+0=5

C2 (3)+f1 (1) =4+1=5

C2 (2)+f1 (2) =3+2=5

f2(4) = min

C2 (1)+f1 (3) =2+4=6

C2 (0)+f1 (4) =0+6=6

O£ x2£ 4

Burada; birinci, ikinci ve üçüncü seçenekler için f2(4) = 5'dir. Bu duıumda yine yorum yapmak için birinci seçeneği ele alalım. Seçenek i8çin durum değerleri x1 = 0 ve x2 = 4'dür. Bu değerler de bize; 4 birim üıün üretildiğinde, bunun hepsinin ikinci makinada üretilmesi gerektiğini gösterir.

Geri kalan durumlar için yukarıdaki işlemler tekrarlandığında, aşağıdaki değerler elde edilir.

X = 5 durumunda,

min f2(5)= 6 elde edilir.

X = 6 duıumunda,

x2= 4, x1= 2 için

min f2(6)= 7 bulunur.

X = 7 durumunda ,

min f2(7)= 9 elde edilir.

X = 8 duıumu için,

min f2(8)= 11 elde edilir

X = 9 için de,

min f2(9) = 13'dür.

Seçeneklerimiz ise aşağıda görülmektedir.

X=10 durumu için

minf2 (10)= 15’tir.

 

Seçeneklerimiz yine aşağıda görülmektedir.

Yapılan hesaplamaların sonucu elde edilen bu değerlere Tablo 1'in beşinci sütununda yer verilmiştir.

Üçüncü aşama ile ilgili türlü üretim miktarlarına karşılık gelen maliyet değerlerini yani f3(X)'ü belirlemek için, f2(X)'de olduğu gibi, tekrar aynı yineleme ilişkileri kullanılacaktır. Başka bir deyişle ikinci aşamada uygulanan süreç aynen izlenecektir. Bu söylediklerimiz, problemde daha başka aşamalarda (4, 5, .:..., n-1, n gibi) olsaydı, onlar için de geçerli olacaktı.

f3(X) = min [c3(x3)+f2(X- x3 )]

O£ x3£ X

X=1 durumu için,

f3(1) = min [c3(x3)+f2(1- x3 )]

O£ x3£ 1


C3 (0)+f2 (1) = 0+1=1

f3(1) = min

C3 (1)+f2 (0) =4+0=4

O£ x3£ 1 elde edilir.

x3= 0, (1- x3)= 1 durumunda f3(1)= 1'dir. (1- x3)= 1’ den anlaşılacağı üzere, x1 veya x2 ‘den herhangi birinin değeri bire eşittir. Bu değerin hangisine ait olduğu Tablo 1'den elde edilebilir.

X= 2 durumu için,

f3(2) = min [c3(x3)+f2(2 - x3 )]

O£ x3£ 2

C3 (2)+f2 (0) = 5+0=5

f3(2) = min C3 (1)+f2 (1) =4+1=5

C3 (0)+f2 (2) =0+2=2

O£ x3£ 2

x3= 0, (2- x3)= 2 durumunda f3(2)= 2'dir. (2- x3)= 2 durumunda ise önceki aşamalar için (x1= 2, x2= 0), (x2= 2, x1= 0) ya da (x1= 1, x2= 1) olabilir.

Geriye kalan durumlar için yukarıdaki benzer işlemler tekrarlandığında, aşağıdaki değerler elde edilir.

X = 3 durumu için,

min f3(3) = 4

Bu değere karşılık gelen durum değerleri,

x3= 0, X-x3= 3'dür.

X = 4 durumu için,

min f3(4) = 5

Bu maliyete karşılık gelen durum değerleri

x3= 0, X-x3= 4'dür

X = 5 için,

x3= 0, X-x3= 5 durumunda

min f3(5) = 6 elde edilir.

X=6 için,

min f3(6) = 7

Bu değere karşılık gelen durum değleri ise x3= 0, X- x3= 6'dır.

X = 7 durumu için,

x3= 0, X- x3= 7 durumunda

min f3(7) = 9 bulunur.

X = 8 durumunda,

min f3(8) = 11

x3= 0, X- x3= 8’dir.

X = 9 durumunda,

min f3(9) = 13 bulunur.

Bu değere karşılık gelen durum değerleri ile ilgili seçenekler de aşağıda verilmiştir.

X = 10 için,

min f3(10) = 14

bu değere karşılık gelen durum değerleri

x3= 4, X- x3= 6 olarak elde edilir.

Şimdi buraya kadar, üç makina için elde ettiğimiz durum ve getiri değerlerini Tablo 1'de toplu olarak görebiliriz.

Tablodaki sonuçlaıa göre, 10 tonluk üıün üıetebilmek için minimum üretim maliyeti 14 olarak belirlenmiştir. Bu değere karşılık gelen 4 ton yapağı üçüncü makinada işlenecektir. Dolayısı ile geri kalan 6 ton yapağı ise birinci ve ikinci makinada işlenecektir.

Tablo 1

Problemin İleriye Doğru Çözüm Yolu İzlenerek Elde Edilen Dinamik Programlama Çözümü

 

Üretim

1.makine

2. Makine

3. Makine

Miktarı

(ton)

x1

f1(X)

x2

f2(X)

x3

f3(X)

0

0

0

0

0

0

0

1

1

1

0

1

0

1

2

2

2

0

2

0

2

3

3

4

0,1,2,3

4

0

4

4

4

6

2,3,4

5

0

5

5

5

8

3,4

6

0

6

6

6

10

4

7

0

7

7

7

13

4,5

9

0

9

8

8

16

4,5,6

11

0

11

9

9

20

4,5,6,7

13

0,3,4

13

10

10

25

4,5,6,7

15

4

14

Dört ton yapağının üçüncü makinada üretilmesi ile ortaya çıkan maliyet 7'dir. Bu değer, örnek problemde herbir makinanın türlü üretim değerleri için neden olacağı maliyetlerden bulunur. 10 ton üretim için gerekli üretim maliyeti 14 birim olduğundan, geri kalan 6 ton'luk üretim için de (14-7) = 7 birimlik bir maliyet söz konusu olacaktır. Bu maliyet Tablo 1'in beşinci sütununda göıülmektedir. Bu maliyete karşılık gelen üretim miktarı ise x2 için 4 birimdir. İkinci makinada 4 ton yapağı işlemenin maliyeti 5 birimdir. Dolayısı ile geriye kalan 2 birimlik bir maliyet ve bu maliyetle üretilmesi gereken 2 ton yapağı birinci makinada işlenecektir.

Makinalarla ilgili optimal üretim miktarları Tablo 1'de koyu olarak gösterilmiştir. Sonuç olarak optimal üretim planı aşağıdaki gibi yazılabilir.

x1= 2 için C1(x1) = 2

x2 =4 için C2 (x2 )= 5

x3 =4 için C3 (x3 )= 7

Toplam Maliyet TM= f3 (10 )=14

2.2. Geriye Doğru Çözüm Yolu

Bu kesimde daha önce ele alınan örnek problem, sondan başa doğru gelinerek yani tümdengelim yolu ile çözülmeye çalışılacaktır.

İleriye doğru çözüm yolunda olduğu gibi, birinci makina yine birinci aşamaya, ikinci makina ikinci aşamaya, üçüncü makina da üçüncü aşamaya karşılık gelmektedir. Ancak; sondan başa doğru gelinerek çözüm yapılacağından, işleme üçüncü aşamadan başlanması gerekecektir.

Üçüncü aşama için sistemin maliyet değerleri, bu aşamanın herbir durumu için söz konusu olan maliyet katsayılarına eşittir. Yani; .

f3 (X )= c3 (x3 ) olmaktadır.

Burada x3 'ün alabileceği türlü değerler için f3 (X)'in değerleri aşağıdaki gibi olacaktır.

 

 

 

 

 

X

x3

C3(x3)

f3(X)

0

0

0

0

1

1

4

4

2

2

5

5

3

3

6

6

4

4

7

7

5

5

9

9

6

6

10

10

7

7

12

12

8

8

13

13

9

9

14

14

10

10

16

16

Üçüncü aşama için yapılması gereken başka bir işlem kalmadığından, şimdi sıra ikinci aşama için gerekli işlemlerin yapılmasına gelmiştir.

Sürecin ikinci aşamadaki maliyet değerlerinin, üçüncü aşamanın maliyet değerleri6 ile ikinci aşamanın maliyet değerlerinin birlikte ele alınmaktadır. Buna göre ikinci aşama için dönüşüm fonksiyonu

f2(X) = min [c2(x2) + f3(X-x3)]

0£ x2£ X yazılabilir.

Şimdi, ikinci aşama için sayısal çözümlerin yapılmasına

geçilebilir,

X = 1 durumu için,

f2(1) = min [c2(x2) + f3(1-x2)]

0£ x2£ 1

C2 (1)+f3 (0) = 2+0=2

f2(1) = min

C2 (0)+f3 (1) =0+4=4

O£ x2£ 1

X = 2 durumu için,

f2(2) = min [c2(x2) + f3(2-x2)]

0£ x2£ 2

X = 3 durumunda,

min f2(3) = 4

Buna karşılık gelen durum değerleri ise

x2 = 3, x3 = 0 olmaktadır.

X = 4 durumu için de bu değerler

x2 = 4, x3 = 0

min f2(4) = 5’tir.

X= 5 durumunda ise

x2 =5, x3 = 0 için

min f2(5) = 7’dir.

X= 6 durumu için

x2 =6, x3 = 0 ve

min f2(6) = 9

X=7 durumu için seçenekli çözüm ortaya çıkmaktadır.

durum değerleri için

min f2(7) = 11 bulunmaktadır.

X=8 durumu için

x2 =4, x3 =4

min f2(8) = 12 elde edilir.

X=9 durumunda dört seçenek söz konusudur.

min f2(9) = 14 bulunur.

X=10 durumu için

x2 =4, x3 =6

min f2(10) = 15 elde edilir.

Böylece ikinci aşama içinde sayısal değerler elde edilmiş oldu. Şimdi elimizde çözüm değerleri hesaplanması gereken yalnız birinci aşama kaldı.

İkinci aşamada izlenen yöntemin aynısı birinci aşama içinde izlenerek çözüm değerleri bulunabilir.

Birinci aşama için dönüşüm fonksiyonu;

f1(X) = min [c1(x1) + f2 (X-x1)]

0£ x1£ X yazılabilir.

Şimdi X’in alacağı türlü değerler için bu fonksiyonun değerlerini belirleyelim.

X=1 durumu için

f1(1) = min [c1(x1) + f2 (1-x1)]

0£ x1£ 1

C1(0)+f2 (1) = 0+2=2

f1(1) = min

C1 (1)+f2 (0) =1+0=1

O£ x1£ 1

X=2, yani 2 birim ürün üretileceği durumda,

f1(2) = min [c1(x1) + f2 (2-x1)]

O£ x1£ 2

C1(0)+f2 (2) = 0+3=3

f1(2) = min C1 (1)+f2 (1) =1+2=3

C1 (2)+f2(0) =2+0=2

O£ x1£ 2

Bu süreç takip edilerek diğer durumlar için elde edilen çözümler aşağıdadır.

X=3 durumunda seçenekli çözüm ortaya çıkmaktadır. Seçenekler sırasıyla şöyledir.

f1(3)=4’tür

X=4 durumu için seçenekler

f1(4)=5’tir.

X=5 olduğunda, seçenekler

f1(5)=6’dır.

X=6 durumunda

f1(6)=7 bulunur.

X=7 durumunda

f1(7)=9 bulunur.

X=8 durumu için çözüm yapıldığında;

f1(8)=11

X=9 durumu için de maliyet fonksiyonunun değerini en küçükleyen, beş seçenek ortaya çıkmaktadır. Bu seçenekler;

Bu seçeneklere karşılık gelen maliyet değeri

f1(9)=13 olmaktadır.

X=10 durumunda ise;

x1=2, 10- x1=8

f1(10)=14 elde edlimektedir.

Böylece birinci aşama için de çözüm değerlerini hesaplamış olduk.

Her üç aşamada elde edilen durum ve maliyet değerleri kullanılarak Tablo 2 düzenlenmiştir. Bu tablo, her makinanın işlemesi gereken en uygun üretim miktarlarının ve bunlarla ilgili maliyet değerlerinin belirlenmesinde kullanılacaktır.

Tablo 2'den görüleceği üzere, on tonluk üretim, en az 14 birimlik bir toplam maliyete yol açmaktadır. Bu durumda x1= 2'dir. Bu da bize toplam 14 birimlik maliyetle üretimin yapılabilmesi için, 2 ton malın birinci makinada üretilmesi gerektiğini göstermektedir. Söz konusu iki ton malın birinci makinadaki üretim maliyeti "2" birimdir. Bu değeri toplam maliyet değerinden çıkardığımızda, geriye 12 birimlik bir maliyet kalmaktadır. Bu maliyet değeri de geri kalan 8 ton malın üretim maliyetine karşılık gelmektedir.

Tablo 2 Problemin Geriye Doğru Gelinerek Elde Edilen Dinamik Programlama Çözümü

Üretim

3.makine

2. Makine

1. Makine

Miktarı

(ton)

x3

f3(X)

x2

F2(X)

X1

F1(X)

0

0

0

0

0

0

0

1

1

4

1

2

1

1

2

2

5

2

3

2

2

3

3

6

3

4

3,2,1,0

4

4

4

7

4

5

0,1,2

5

5

5

9

5

7

1,2

6

6

6

10

6

9

2

7

7

7

12

7

11

2,3

9

8

8

13

4

12

2,3,4

11

9

9

14

5,4,3,0

14

1,2,3,4,5

13

10

10

16

4

15

2

14

Tablodan görüleceği üzere on tonluk üretimin en küçük toplam maliyet değeri 14 tondur. Bu durumda x1= 2 yani üretimin 2 birimi birinci makinada üretilecek demektir. Söz konusu iki ton ürünün, birinci makinadaki üretim maliyeti iki birimdir. Bu değeri toplam maliyetten çıkardığımızda geriye 12 birimlik bir maliyet kalmaktadır.

12 birimlik maliyete karşılık gelen ikinci makinanın optimal üretim miktarı (tablodan görüldüğü üzere) 4 tondur. 4 tonluk üretim ikinci makinada 5 birimlik bir maliyeti gerektirmektedir. İkinci ve üçüncü makinanın toplam üretim maliyeti olan 12 birimden bu 5 birimlik maliyet çıkarıldığında üçüncü makinanın 4 birimlik ürün üretebilmek için gereksinim duyduğu 7 birimlik maliyet değeri elde edilir. Geriye kalan 4 tonluk üretim de üçüncü makinada yapılacaktır. Sonuç olarak optimal üretim planı aşağıdaki gibi yazılabilir. Herbir makinanın işlemesi gereken yapağı miktarı;

x1=2 ton C1(x1)= 2 birim

x2=4 ton C2(x2)= 5 birim

x3=4 ton C3(x3)=7 birim

toplam maliyet f(X) = 14 birim

Elde edilen sonuçlardan görüldüğü gibi, problemin çözümünde kullanılan her iki yol da (tümevarım, tümdengelim) aynı sonucu vermektedir.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

YARARLANILAN KAYNAKLAR