PROGRAMA DINAMIS
10/31/2012
1
Programa Dinamis berbeda dengan programa linier yang sudah kita kenal. Persoalan bersifat dinamis apabila diarahkan kepada pemecahan secara bertahap yang masingmasingnya merupakan satu kesatuan.
10/31/2012
Ada 3 hal yang penting diketahui tentang programa dinamis, yaitu: • STAGE (tahapan) dari persoalan yang dihadapi dan ingin dicari solusinya • STATE (kondisi) yang menjadi faktor penentu keputusan dari tiap tahapan • DECISION (keputusan) yang harus diambil dari tiap tahap untuk sampai kepada solusi keseluruhan.
2
Keputusan tahap N sangat ditentukan oleh keputusan pada tahap-tahap sebelumnya. Decision 1
Stage 1
State 1
Decision 2
Decision N
Stage 2
Stage N
State 2
State N
Tergantung pada jenis persoalan yang dihadapi, model/formulasi tujuan yang diharapkan pun akan berbeda. 10/31/2012
3
Contoh 1 : STAGE COACH Misalkan soal memilih rute angkutan barang dengan kereta kuda (stage coach) dari kota asal (A) ke kota tujuan (K). Persoalan lebih disederhanakan dengan memilah tahapan yang dapat ditempuh dengan lama waktu tempuh antar kota yang dilewati, sebagai berikut: 10/31/2012
4
• Tahap 1 adalah pilihan rute AB atau AC • Tahap 2 adalah pilihan rute antara BD, BE, BF, atau BG serta antara CD, CE, CF, atau CG • Tahap 3 dan 4 bisa dibaca lanjut seperti di atas ...
• Tahapan diperlukan sebagai penentu rute yang akan dipilih • Secara keseluruhan, tujuan utama dari persoalan tersebut adalah minimasi waktu tempuh dari kota asal (A) ke kota tujuan akhir (T) 10/31/2012
•
•
•
Penyelesaian dapat dilakukan denga cara mundur (backward) atau maju (forward), walau pada umumnya banyak dipilih cara mundur Secara tradisional persoalan tersebut dapat diselesaikan dengan menghitung setiap alternatif rute yang mungkin (2 x 4 x 3 x 1 = 24 alternatif), kemudian pilih waktu tempuh terkecil. Cara programa dinamis lebih sistematis dan mudah dikerjakan 5
Misalkan waktu tempuh antar kota (dalam hari) adalah sebagai berikut: Dari \ Ke
B
C
D
E
F
G
H
I
J
A
15
12
B
20
17
18
17
C
18
25
20
20
D
12
14
16
E
15
15
13
F
15
18
20
G
15
13
17
K
H
15
I
13
J
10
10/31/2012
6
• •
•
Komponen waktu tempuh dapat langsung dicantumkan pada garis panah dari dari/ke kota Penyelesaian cara programa dinamis adalah dengan membuat matriks setiap tahap, dimulai dari tahap 4, ke tahap 3, ke tahap 2, dan terakhir ke tahap 1 State (kondisi penentu keputusan) adalah minimasi waktu tempuh dari rute yang dipertimbangkan.
10/31/2012
7
Tahap 4 : min { f4(x4) } Dari \ Ke H I J
• • • •
K 15 13 10
f4(x4) 15 13 10
x4* HK IK JK
Tahap 4 hanya mencantumkan waktu tempuh dari ~ ke f4(x4) adalah nilai perolehan pada tahap 4 x4* adalah rute terbaik pada tahap 4 teruskan ke tahap 3
10/31/2012
8
Tahap 3 : min { f3(x3) + f4*(x4) } Dari \ Ke D E F G • • • • • •
•
H (15) 27 32 30 30
I (13) 27 32 31 26
J (10) 26 23 30 25
f3(x3)
x3*
26 23 30 25
DJ EJ FH , FJ GJ
Tujuan tahap 3 adalah minimasi waktu tempuh tahap 3 ditambah yang terbaik dari tahap 4 Misal untuk DH = 12 + 15 = 27 (dihitung mulai dari D hingga K), demikian yang lainnya f4*(x4) adalah perolehan terbaik dari tahap 4 (pakai tanda *) f3(x3) adalah nilai perolehan pada tahap 3 x3* adalah rute terbaik pada tahap 3 Dari tahap 3 ini terlihat bahwa tujuan berikutnya adalah ke J (kecuali dari F bisa juga ke H) teruskan ke tahap 2 10/31/2012
9
Tahap 2 : min { f2(x2) + f3*(x3) } Dari \ Ke B C •
D (26) 46 44
E (23) 40 58
F (30) 48 50
G (25) 42 45
f2(x2)
x2*
40 44
BE CD
Tujuan tahap 2 adalah minimasi waktu tempuh tahap 2 ditambah yang terbaik dari tahap 3 • Misal untuk BE = 17 + 23 = 40 (dihitung mulai dari B hingga K), demikian yang lainnya • f3*(x3) adalah perolehan terbaik dari tahap 3 (pakai tanda *) • f2(x2) adalah nilai perolehan pada tahap 2 • x2* adalah rute terbaik pada tahap 2 • Dari tahap 2 ini terlihat bahwa tujuan berikutnya adalah ke D (bila dari C) atau E (bila dari B) •10/31/2012 teruskan ke tahap 1 10
Tahap 1 : min { f1(x1) + f2*(x2) } Dari \ Ke A
• •
B (40) 55
C (44) 56
f1(x1)
x1*
55
AB
Yang terbaik pada tahap 1 adalah rute AB Bila diteruskan dapat diperoleh rute terbaik (waktu tempuh 55 hari), yaitu dari A ke B ke E ke J dan berakhir di K
10/31/2012
11
Contoh 2 : Cargo Loading Misalkan, sebuah perusahaan angkutan mendapat order mengirimkan barang dari satu tempat ke tempat lainnya dengan menggunakan satu truk besar dengan kapasitas 15 ton. Jenis barang yang diangkut, berat, dan biayanya adalah sebagai berikut: Jenis Barang A B C
Berat (ton) 2 5 3
Biaya (juta/item) 66 155 96
Barang yang harus diangkut harus utuh (tidak boleh setengah atau seperempatnya, berarti kalau mengangkut 1 barang B ~ kapasitasnya 5 ton, bila 2 barang B berarti 10 ton, dan seterusnya). 10/31/2012
12
JAWAB Stage dalam persoalan ini adalah jumlah barang yang harus diangkut, tanpa melampaui kapasitas, dan dapat memaksimumkan pendapatan. Ada 3 jenis barang ~ berarti ada 3 tahapan (stage).
10/31/2012
13
Tahap 3 : Max { f3(x3) } •
• •
Karena berat barang C (sebagai x3) = 3 ton ~ berarti jumlah maksimum barang C yang dapat diangkut adalah 5 buah) Siapkan kolom untuk C = 0 (tanpa barang C), C = 1 , C = 2 , C = 3 , C = 4 , dan C = 5 Perhatikan kapasitasnya ~ cantumkan rupiah yang diperoleh
10/31/2012
• •
•
•
Pada C=2 ~ berarti rupiahnya = 2 x 96 = 192 juta, dan seterusnya Baris kapasitas cukup diringkas untuk 0, 3, 6, 9, 12, dan 15 saja (kelipatan dari berat barang C = 3 ton) Tanda panah ke bawah berarti rupiahnya sama dengan yang di atasnya Nilai f3* (x3) berarti jawab terbaik pada tahap 3 pada kapasitas yang terpakainya
14
Tahap 2 ; Max { f2x2 + f3* (kapasitas - x3) } • • • •
•
Karena barang B (disebut x2) = 5 ton ~ maksimum jumlah barang B yang bisa diangkut adalah 3 buah Siapkan B=0 , B=1 , B=2, dan B=3 Perhatikan kapasitasnya Formula di atas berarti: rupiah yang diharapkan adalah dari barang B ditambah dengan sisa kapasitas yang tersedia untuk tahap 3 (tanda *) yang terbaik. Hasil terbaik pada tahap 2 ini sudah mencakup hasil terbaik pada tahap 3
10/31/2012
15
Perhatikan cara perhitungan tabulasinya sebagai berikut:
Pada kolom f2*x2 tercantum nilai rupiah terbaiknya Kolom x2* menunjukkan jumlah barang B yang harus diangkut pada tahap 2 10/31/2012 16 Jumlah B yang dapat diangkut bisa 0, 1, atau 2 tergantung pada kapasitasnya
Tahap 1 : Max { f1x1 + f2* (kapasitas - x1) } Pada tahap akhir cukup dicantumkan kapasitas maksimum (15 ton) Karena berat barang A (disebut x1) = 2 ton ~ maksimum jumlah barang yang bisa diangkut adalah 7 buah dengan sisa 1 ton Nilai rupiah terbaik dihitung dari jumlah barang A yang diangkut yang ditambah rupiah terbaik dari sisa kapasitas di tahap 2 Siapkan kolom A=0 ; A=1 ; A=2 ; A=3 ; A=4 ; A=5 ; A=6 ; A=7
10/31/2012
• Hasil terbaik dari tahap 1 secara kesuluruhan adalah 492 juta • Bawa 6 buah barang A (6 x 96 juta = 396 juta) • Dari tahap 2 ~ tambahan 96 juta dari kolom B = 0 (beraarti tidak ada barang B yang diangkut) • Ke tahap 3 ~ nilai 96 tersebut dari kolom C = 1 (berarti bawa 1 barang C)
17
Ringkasan : Tahap Bawa barang Tonase Rupiah 10/31/2012
1 A=6 12 396
2 B=0 0 0
3 C=1 3 96
total = 15 ton total = 492 juta 18
