program dinamik dynamic programming · pendahuluan (2) pemrograman dinamik merupakan teknik...

Program Dinamik

(Dynamic Programming)

Riset Operasi

TIP – FTP – UB

Program Dinamik :

Pendahuluan (1)

Program dinamik merupakan suatu pendekatan solusi bukan suatu teknik

Tidak terbatas pada golongan masalah tertentu

Pendekatan solusi adalah merinci suatu masalah menjadi masalah-masalah yang lebih kecil tahapan (stages)

Penyelesaian tahapan secara berurutan

Hasil dari suatu keputusan (solusi) pada suatu tahap akan mempengaruhi keputusan tahap berikutnya

Program Dinamik :

Pendahuluan (2)

Pemrograman dinamik merupakan teknik matematis yang dapat berguna untuk membuat suatu urutan keputusan yang saling berkaitan

Pemrograman dinamis tidak mempunyai rumusan yang baku

Tiap permasalahan memerlukan perumusan tertentu

Teknik pemrograman dinamis dikenal juga dengan multistage programming

Klasifikasi Program Dinamis

Status Diskret Status Kontinyu

Tunggal Majemuk Tunggal Majemuk

Deterministik

Probabilistik

Prosedur Pemecahan Masalah

Prosedur pemecahan

Rekursi maju (forward recursion)

Rekursi mundur (backward recursion)

Perbedaan prosedur

Cara mendefinisikan status dalam sistem.

Prosedur rekursi mundur secara umum lebih

efisien

Langkah-langkah Pemecahan

Tentukan prosedur pemecahan (maju atau mundur).

Tentukan tahap (stage).

Definisikan variabel status (state) pada tiap tahap.

Definisikan variabel keputusan pada tiap tahap.

Definisikan fungsi pengembalian pada tiap tahap.

Definisikan fungsi transisi.

Definisikan fungsi rekursif.

Perhitungan.

Tentukan solusi optimal dengan backtracking.

Permasalahan

Sebuah perusahaan membagi wilayah

pemasarannya menjadi tiga: utara, timur,

selatan. Perusahaan tersebut memilliki 3

tenaga penjual yang akan dialokasikan ke

tiga wilayah tersebut tanpa membatasi

jumlah tenaga penjual di setiap wilayah sdrs

hasil penjualan maksimum.

Contoh Program Dinamik (1)

Permasalahan

Alternatif Keputusan

Salesman/Daerah

Tingkat Pengembalian/Daerah

Utara Timur Selatan

0 0 0 2

1 7 9 6

2 12 15 10

3 20 18 16


Model Matatematika Masalah

Maksimum R1+R2+R3

Ditujukan

D1+D2+D3 ≤ 3

Dimana

R1, R2, R3 = pengembalian dari tiap 3 daerah

D1, D2, D3 = keputusan penempatan

salesman ke tiap 3 daerah


Tahap 1 : Alokasi ke Daerah Selatan Keadaan 1 (S1):

Salesman Tersedia

Keputusan 1 (D1):

Alokasi Salesman

Pengembalian 1(R1):

Jumlah Penjualan

0 0 2

1 0 2

1 6

2 0 2

1 6

2 10

3 0 2

1 6

2 10

3 16


Tahap 1 : Alokasi ke Daerah Selatan (Opt) Keadaan 1 (S1):

Salesman Tersedia

Keputusan 1 (D1):

Alokasi Salesman

Pengembalian 1(R1):

Jumlah Penjualan

0 0 2

1 0 2

1 6

2 0 2

1 6

2 10

3 0 2

1 6

2 10

3 16


Tahap 2 : Alokasi ke Daerah Timur Keadaan 2

(S2):

Salesman

Tersedia

Keputusa 2

(D2):

Alokasi

Salesman

Pengembali

an 2 (R2):

Jumlah

Penjualan

Keadaan 1

(S1):

Salesman

Tersedia

Pengembali

an 1(R1):

Jumlah

Penjualan

Total

Pengembali

an (R1+R2)

0 0 0 0 2 2

1 0 0 1 6 6

1 9 0 2 11

2 0 0 2 10 10

1 9 1 6 15

2 15 0 2 17

3 0 0 3 16 16

1 9 2 10 19

2 15 1 6 21

3 18 0 2 20


Tahap 2 : Alokasi ke Daerah Timur (Opt) Keadaan 2

(S2):

Salesman

Tersedia

Keputusa 2

(D2):

Alokasi

Salesman

Pengembali

an 2 (R2):

Jumlah

Penjualan

Keadaan 1

(S1):

Salesman

Tersedia

Pengembali

an 1(R1):

Jumlah

Penjualan

Total

Pengembali

an (R1+R2)

0 0 0 0 2 2

1 0 0 1 6 6

1 9 0 2 11

2 0 0 2 10 10

1 9 1 6 15

2 15 0 2 17

3 0 0 3 16 16

1 9 2 10 19

2 15 1 6 21

3 18 0 2 20


Tahap 3 : Alokasi ke Daerah Utara

Keadaan 3

(S3):

Salesman

Tersedia

Keputusa

3 (D3):

Alokasi

Salesman

Pengemba

lian 3

(R3):

Jumlah

Penjualan

Keadaan 2

(S2):

Salesman

Tersedia

Pengemba

lian 2(R2):

Jumlah

Penjualan

Total

Pengemba

lian

(R1+R2+R

3)

3 0 0 3 21 21

1 7 2 17 24

2 12 1 11 23

3 20 0 2 22


Tahap 3 : Alokasi ke Daerah Utara (Opt)

Keadaan 3

(S3):

Salesman

Tersedia

Keputusa

3 (D3):

Alokasi

Salesman

Pengemba

lian 3

(R3):

Jumlah

Penjualan

Keadaan 2

(S2):

Salesman

Tersedia

Pengemba

lian 2(R2):

Jumlah

Penjualan

Total

Pengemba

lian

(R1+R2+R

3)

3 0 0 3 21 21

1 7 2 17 24

2 12 1 11 23

3 20 0 2 22


Urutan Keputusan Optimal

Keadaan

(daerah)

Alokasi

Salesman Pengembalian

1. Selatan 0 2

2. Timur 2 15

3. Utara 1 7

Total 3 24

Problem Knapsack

Permasalahan mengenai berapa jumlah tiap

jenis barang yang berbeda dapat dimasukkan

ke dalam sebuah ransel guna

memaksimumkan pengembalian dari barang-

barang tersebut. Ransel punya kapasitas

tertentu (5 ruang)

Contoh Problem Knapsack (1)

Permasalahan

Alternatif Barang

yang Dibawa

Berat Laba

X 2 90

Y 3 150

Z 1 30


Model Matatematika Masalah

Maksimum R1D1+R2D2+R3D3

Ditujukan

W1D1+W2D2+W3D3 ≤ 5

Dimana

R1, R2, R3 = pengembalian dari tiap barang

D1, D2, D3 = keputusan jumlah barang yang dibawa

W1, W2, W3 = berat barang yang dibawa


Tahap 1 : Keputusan X

Keadaan 1 (S1):

Ruang Tersedia

Keputusan 1

(D1): Jumlah

Barang

Kebutuhan

Ruang

Pengembalian

1(R1)

5 2 4 180

4 2 4 180

3 1 2 90

2 1 2 90

1 0 0 0

0 0 0 0


Tahap 1 : Keputusan X (Opt)

Keadaan 1 (S1):

Ruang Tersedia

Keputusan 1

(D1): Jumlah

Barang

Kebutuhan

Ruang

Pengembalian

1(R1)

5 2 4 180

4 2 4 180

3 1 2 90

2 1 2 90

1 0 0 0

0 0 0 0


Tahap 2 : Keputusan Y

Keadaa

n 2 (S2)

Keput

usan

2

(D2)

Kebutu

han

Ruang

Penge

mbalia

n 2(R2)

Keada

an 1

(S1)

Keputu

san 1

(D1)

Penge

mbalia

n 1

(R1)

Penge

mbalia

n Total

(R)

5 1 3 150 2 1 90 240

0 0 0 5 2 180 180

4 1 3 150 1 0 0 150

0 0 0 4 2 180 180

3 1 3 150 0 0 0 150

0 0 0 3 1 90 90

2 0 0 0 2 1 90 90

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


Tahap 2 : Keputusan Y (Opt)

Keadaa

n 2 (S2)

Keput

usan

2

(D2)

Kebutu

han

Ruang

Penge

mbalia

n 2(R2)

Keada

an 1

(S1)

Keputu

san 1

(D1)

Penge

mbalia

n 1

(R1)

Penge

mbalia

n Total

(R)

5 1 3 150 2 1 90 240

0 0 0 5 2 180 180

4 1 3 150 1 0 0 150

0 0 0 4 2 180 180

3 1 3 150 0 0 0 150

0 0 0 3 1 90 90

2 0 0 0 2 1 90 90

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


Tahap 3 : Keputusan Z

Keadaa

n 3 (S3)

Keput

usan

3

(D3)

Kebutu

han

Ruang

Penge

mbalia

n 3(R3)

Keada

an 2

(S2)

Keputu

san 2

(D2)

Penge

mbalia

n 2

(R2)

Penge

mbalia

n Total

(R)

5 5 5 150 0 0 0 150

4 4 120 1 0 0 120

3 3 90 2 0 90 180

2 2 60 3 1 150 210

1 1 30 4 0 180 210

0 0 0 5 1 240 240


Keputusan Optimal

Keadaan

(Barang)

Jumlah

Barang

Kebutuhan

Ruang

Pengem

balian

X 1 2 90

Y 1 3 150

Z 0 0 0

Total 5 240

Problema Stagecoach

Suatu jaringan pengarahan perjalanan

dimana seorang pengarah jalan (abad 19)

ingin menentukan rute terpendek antara dua

kota (1 dan 7) berdasarakan rute alternatif

yang tersedia.

Problema Stagecoach (1)

Tahap 1

Keadaan 1 (S1):

Lokasi Truk

Keputusan 1

(D1): Rute

Pengembalian 1

(R1): Waktu

Tempuh

5 5 7 8

6 6 7 14


Tahap 1 (Opt)

Keadaan 1 (S1):

Lokasi Truk

Keputusan 1

(D1): Rute

Pengembalian 1

(R1): Waktu

Tempuh

5 5 7 8

6 6 7 14


Tahap 2

Keadaa

n 2 (S2)

Keputus

an 2

(D2)

Penge

mbalian

2 (R2)

Keadaa

n 1 (S1)

Pengem

balian 1

(R1)

Pengem

balian

Total (R)

2 25 25 5 8 33

26 17 6 14 31

3 35 14 5 8 22

36 17 6 14 31

4 45 26 5 8 34

46 22 6 14 36


Tahap 2 (Opt)

Keadaa

n 2 (S2)

Keputus

an 2

(D2)

Penge

mbalian

2 (R2)

Keadaa

n 1 (S1)

Pengem

balian 1

(R1)

Pengem

balian

Total (R)

2 25 25 5 8 33

26 17 6 14 31

3 35 14 5 8 22

36 17 6 14 31

4 45 26 5 8 34

46 22 6 14 36


Tahap 3

Keadaa

n 3 (S3)

Keputus

an 3

(D3)

Penge

mbalian

3 (R3)

Keadaa

n 2 (S2)

Pengem

balian 2

(R2)

Pengem

balian

Total (R)

1 12 16 2 31 47

13 35 3 22 57

14 9 5 34 43


Tahap 3 (Opt)

Keadaa

n 3 (S3)

Keputus

an 3

(D3)

Penge

mbalian

3 (R3)

Keadaa

n 2 (S2)

Pengem

balian 2

(R2)

Pengem

balian

Total (R)

1 12 16 2 31 47

13 35 3 22 57

14 9 5 34 43


Keputusan Optimal

Rute yang diambil 1 4 5 7 dengan

jarak tempuh 43.

Terima kasih

program dinamik dynamic programming · pendahuluan (2) pemrograman dinamik merupakan teknik...

Documents