programa dinamis
Post on 22-Feb-2016
90 Views
Preview:
DESCRIPTION
TRANSCRIPT
Programa Dinamis STMIK MERCUSUARJl. Raya Jatiwaringin No. 144 Pondok Gede Bekasi 17411
Pendahuluan Persoalan bersifat dinamis diarahkan kepada pemecahan secara
bertahap yang masing-masingnya merupakan satu kesatuan. Ada 3 hal yang penting diketahui tentang programa dinamis,
yaitu: o Stage (tahapan) dari persoalan yang dihadapi dan ingin dicari
solusinya. o State (kondisi) yang menjadi faktor penentu keputusan dari
tiap tahapan. o Decision (keputusan) yang harus diambil dari tiap tahap untuk
sampai kepada solusi keseluruhan.
........................... Pendahuluan
• Keputusan tahap N sangat ditentukan oleh keputusan pada tahap-tahap sebelumnya. Model formulasi tujuan yang diharapkan akan berbeda, tergantung pada jenis persoalan yang dihadapi.
• Selanjutnya akan ditunjukkan 3 jenis persoalan yang mengarah pada model programa dinamis.
Contoh 1: Stage Coach Memilih rute angkutan barang/orang 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 antarkota yang dilewati sebagai berikut.
............................................. Contoh 1: Stage Coach
Tahap 1 → Pilihan rute AB atau AC. Tahap 2 → Pilihan rute antara BD, BE, BF, atau BG, serta antara
CD, CE, CF, atau CG, Tahap 3 dan 4 → Dapat dibaca lanjut seperti di atas. Penjelasannya dari persoalan tersebut:
o Tahapan diperlukan sebagai penentu rute yang akan dipilih. o Secara keseluruhan, tujuan utama dari persoalan tersebut
adalah minimasi waktu tempuh dari kota asal (A) ke kota tujuan akhir (K),
o Penyelesaian dapat dilakukan dengan cara mundur (backward) atau maju (forward), walau pada umumnya banyak dipilih cara mundur.
............................................. Contoh 1: Stage Coach
Secara tradisional, persoalan tersebut dapat diselesaikan dengan menghitung setiap altematif rute yang mungkin (2 x 4 x 3 x 1 = 24 altematif), kemudian pilih waktu tempuh terkecil.
Cara programa dinamis lebih sistematis dan mudah dikerjakan.
............................................. Contoh 1: Stage Coach
Misalkan, waktu tempuh antarkota (dalam hari) seperti pada gambar didepan.
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 -7 dikenal sebagai cara mundur (backward).
State (kondisi penentu keputusan) adalah minimasi waktu tempuh dari route yang dipertimbangkan.
Dari/Ke K f4(x4) x4*
H 15 15 HK
I 13 13 IK
J 10 10 JK
Tahap 4 hanya dicantumkan waktu tempuh dari (H, I, atau J) -ke (K)
f4(x4) adalah nilai perolehan pada tahap 4 x4 * adalah rote terbaik pada tahap 4
Hasil tahap 4: • Dari H terus ke K dengan waktu 15 hari• Dari I terus ke K dengan waktu 13 hari• Dari J terus ke K dengan waktu 10 hari
Tahap 4: min { f4(X4) }............................................. Contoh 1: Stage Coach
........................... Pendahuluan
Dari/Ke H I J f3(x3) x3*D 27 27 26 26 DJ
E 30 28 23 23 EJ
F 30 31 30 30 FH/FJ
G 30 26 27 26 GH
• Tujuan di tahap 3 adalah minimasi waktu tempuh tahap 3 ditambah yang terbaik dari tahap 4. Misalnya, 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.
TAHAP 3: min {f3(x3) +f4*(x4)}
........................... Pendahuluan
HASIL TAHAP 3: Dari D, yang terbaik adalah terus ke J hingga ke K dengan total
waktu tempuh = 16 + 10 = 26 hari . Dari E, yang terbaik adalah terus ke J hingga ke K dengan total
waktu tempuh = 13 + 10 = 23 hari . Dari F, ada 2 jalur yang terbaik, yaitu: a) terus ke H hingga ke K
dengan total waktu tempuh = 15 + 15 = 30 hari dan b) terus ke J hingga ke K dengan total waktu tempuh = 20 + 10 = 30 hari .
Dari G, yang terbaik adalah terus ke I hingga ke K dengan total waktu tempuh = 13 + 13 = 26 hari.
Dari/Ke D(26)
E(23)
F(30)
G(26) f2(x2) x2*
B 46 40 48 43 40 BE
C 44 58 50 46 44 CD
Tujuan tahap 2 adalah minimasi waktu tempuh tahap 2 ditambah yang terbaik dari tahap 3. Misalnya, untuk BE = 17 + 23 = 40 (dihitung mulai dari B hingga K), demikian pula 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, tampak bahwa tujuan berikutnya adalah ke D
(bila dari C) atau E (bila dari B).
Tahap 2: min f2(x2) +f3*(x3) ............................................. Contoh 1: Stage Coach
HASIL TAHAP 2: Dari B, yang terbaik adalah terus ke E, lanjut ke J, hingga ke K
dengan total waktu tempuh = 17 + 13 + 10 = 40 hari . Dari C yang terbaik adalah terus ke D, lanjut ke J, hingga ke K
dengan total waktu tempuh = 18 + 16 + 10 = 44 hari.
............................................. Contoh 1: Stage Coach
Dari/Ke B/40/
C/44/ f1(x1) x1*
A 15+40=55 12+44=56 55 AB
TAHAP 1: min {f1(x1) +f2*(x2)}
Tujuan tahap 1 adalah minimasi waktu tempuh tahap 1 ditambah yang terbaik dari tahap 2.
Y ang 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
............................................. Contoh 1: Stage Coach
Dapat ditunjukkan hasil akhir rute terbaik dengan programa dinamis sebagai berikut (diberi wama merah).
Rute terbaik → dari A ke B ke E ke J ke K dengan waktu tempuh 55 hari
............................................. Contoh 1: Stage Coach
CONTOH 2: CARGO LOADING
Jenis Barang Berat (ton) Biaya (juta/ton)A 2 66
B 5 155
C 3 96
Misalkan, sebuah perusahaan angkutan mendapat order mengirimkan barang dari satu tempat ke tempat lainnya dengan menggunakan satu truk besar yang berkapasitas 15 ton. Jenis barang yang diangkut, berat, dan biayanya adalah sebagai berikut.
Barang yang diangkut harus utuh (tidak boleh setengah atau seperempat-nya (kalau mengangkut 1 barang B berarti kapasitasnya 5 ton, bila 2 barang B berarti 10 ton, dan seterusnya).
...................... Contoh 2: Cargo Loading
Jawab: Stage dalam persoalan ini adalah jumlah barang yang harus diangkut dengan syarat tanpa melampaui kapasitas serta dapat memaksimumkan pendapatan. → Ada 3 jenis barang, berarti ada 3 tahapan (stage). 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 = ° (tanpa barang C), C=1, C=2, C=3, C=4, dan C=5
• Perhatikan kapasitasnya, cantumkan rupiah yang diperoleh .
...................... Contoh 2: Cargo Loading
Kapasitas C=0 C=1 C=2 C=3 C=4 C=5 f3(x3) x3*
0 0 0 0
3 0 96 96 1
6 0 96 192 192 2
9 0 96 192 288 288 3
12 0 96 192 288 384 384 4
15 0 96 192 288 384 480 480 5
• Pada C= 1, berarti rupiahnya = 1 x 96 = 96 juta . • Pada C= 2, berarti rupiahnya = 2 x 96 = 192 juta . • Pada C= 3, berarti rupiahnya = 3 x 96 = 288 juta . • Pada C= 4, berarti rupiahnya = 4 x 96 = 384 juta . • Pada C= 5, berarti rupiahnya = 5 x 96 = 480 juta.
Hasil tahap 3: Pada kapasitas ° ton, tidak ada yang diangkut sehingga tidak ada
rupiah yang diperoleh. Pada kapasitas 3 ton, yang diangkut hanya 1 barang C dengan
berat 3 ton sehingga diperoleh 96 juta. Pada kapasitas 6 ton, yang diangkut 2 barang C dengan berat 2 x 3
ton sehingga diperoleh 2 x 96 juta = 192 juta. Pada kapasitas 9 ton, yang diangkut 3 barang C dengan berat 3 x 3
ton sehingga diperoleh 3 x 96 juta = 288 juta. Pada kapasitas 12 ton, yang diangkut 4 barang C dengan berat 4 x
3 ton sehingga diperoleh 4 x 96 juta = 384 juta. Pada kapasitas 15 ton, yang diangkut 5 barang C dengan berat 5 x
3 ton sehingga diperoleh 5 x 96 juta = 480 juta.
...................... Contoh 2: Cargo Loading
...................... Contoh 2: Cargo Loading
TAHAP 2: max { f2x2 + f3 * (kapasitas - x3) } Karena barang B (disebut X2) = 5 ton maka maksimum jumlah
barang B yang dapat diangkut adalah 3 buah. Siapkan B=O , 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.
...................... Contoh 2: Cargo Loading
Catatan perhitungan pada tahap 2: Pada kolom f2*X2 tercantum nilai rupiah terbaiknya. Kolom X2* menunjukkan jumlah barang B yang harus diangkut
pada tahap 2. Jumlah barang B yang dapat diangkut dapat 0, 1, atau 2 -
tergantung pada kapasitasnya.
...................... Contoh 2: Cargo Loading Kapasitas B=0 B=1 B=2 B=3 f2(x2) x2*
0 0 0 0
1 0 0 0
2 0 0 0
3 96 96 0
4 96 96 0
5 96 155 155 1
6 192 155 192 0
7 192 155 192 0
8 192 251 251 1
9 288 251 288 0
10 288 251 310 310 2
11 288 347 310 347 1
12 384 347 310 384 0
13 384 347 406 406 2
14 384 443 406 406 1
15 480 443 406 465 480 0
HASIL TAHAP 2: Pada kapasitas 0 hingga 2 ton, tidak ada barang B yang dibawa
(B=O) sehingga tidak ada rupiah yang diperoleh . Pada kapasitas 3 hingga 4 ton, yang terbaik adalah bawa 1 barang
C (C=l) tanpa barang B (B=O) dengan perolehan 96 juta . Pada kapasitas 5 ton, yang terbaik adalah bawa 1 barang B (B=I)
tanpa barang C (C=O) dengan perolehan 155 juta . Pada kapasitas 6 hingga 7 ton, yang terbaik adalah bawa 2 barang
C (C=2) tanpa barang B (B=O) dengan perolehan 2 x 96 = 192 juta. Pada kapasitas 8 ton, yang terbaik adalah bawa 1 barang B (B= 1)
dan 1 barang C (C=I) dengan perolehan 155 + 96 = 251 juta .
...................... Contoh 2: Cargo Loading
HASIL TAHAP 2: Pada kapasitas 0 hingga 2 ton, tidak ada barang B yang dibawa
(B=O) sehingga tidak ada rupiah yang diperoleh . Pada kapasitas 3 hingga 4 ton, yang terbaik adalah bawa 1 barang
C (C=l) tanpa barang B (B=O) dengan perolehan 96 juta . Pada kapasitas 5 ton, yang terbaik adalah bawa 1 barang B (B=I)
tanpa barang C (C=O) dengan perolehan 155 juta . Pada kapasitas 6 hingga 7 ton, yang terbaik adalah bawa 2 barang
C (C=2) tanpa barang B (B=O) dengan perolehan 2 x 96 = 192 juta. Pada kapasitas 8 ton, yang terbaik adalah bawa 1 barang B (B= 1)
dan 1 barang C (C=I) dengan perolehan 155 + 96 = 251 juta .
...................... Contoh 2: Cargo Loading
Pada kapasitas 9 ton, yang terbaik adalah bawa 3 barang C (C=3) tanpa barang B (B=O) dengan perolehan 3 x 96 = 288 juta .
Pada kapasitas 10 ton, yang terbaik adalah bawa 2 barang B (B=2) tanpa barang C (C=O) dengan perolehan 2 x 155 = 310 juta .
Pada kapasitas 11 ton, yang terbaik adalah bawa 1 barang B (B=1) dan 2 barang C (C=2) dengan perolehan 155 + (2 x 96) = 347 juta.
Pada kapasitas 12 ton, yang terbaik adalah bawa 4 barang C (C=4) tanpa barang B (B=O) dcngan perolehan 4 x 96 = 384 juta .
Pada kapasitas 13 ton, yang terbaik adalah bawa 2 barang B (B=2) dan 1 barang C (C=l) dengan perolehan (2 x 155) + 96 = 406 juta .
...................... Contoh 2: Cargo Loading
Pada kapasitas 14 ton, yang terbaik adalah bawa 1 barang B (B=I) dan 3 barang C (C=3) dengan perolehan 155 + (3 x 96) = 443 juta .
Pada kapasitas 15 ton, yang terbaik adalah bawa 5 barang C (C=5) tanpa barang B (B=O) dengan pcrolehan 5 x 96 = 480 juta.
Tahap 1: max { f1x1 + f2* (kapasitas – x1) } Pada tahap akhir, cukup dicantumkan kapasitas maksimum (15 ton). Karena berat barang A (disebut x.) = 2 ton maka maksimum jumlah
barang yang dapat diangkut adalah 7 buah barang A dengan sisa 1 ton.
Nilai rupiah terbaik dihitung dari jumlah barang A yang diangkut dengan ditambah rupiah terbaik dari si sa kapasitas di tahap 2
...................... Contoh 2: Cargo Loading
...................... Contoh 2: Cargo Loading
Kapasitas A=0 A=1 A=2 A=3 A=4 A=5 A=6 A=7 f1(x1) x1*
15
0+
480=
480
66+
406=
472
132+
347=
479
198+
288=
486
264+
192=
456
330+
155=
485
396+96=
492
462+0=
462
492 6
Hasil terbaik dari tahap 1 dan secara kesuluruhan adalah 492 juta Bawa 6 buah barang A (6 x 66 juta = 396 juta) . Dari tahap 2, tambahan 96 juta dari kolom B = 0 (berarti tidak ada
barang B yang diangkut) . Ke tahap 3, nilai 96 tersebut dari kolom C = 1 (berarti bawa 1
barang C).
Siapkan kolom A=O, A=I, A=2, A=3, A=4, A=5, A=6, A=7
Ringkasan
...................... Contoh 2: Cargo Loading
Tahap 1 2 3 Total
Jumlah Barang A=6 B=0 C=1
Tonase 12 0 3 15 ton
Rupiah 396 0 96 492 juta
Bawa 6 barang A, tidak perlu bawa barang B, dan bawa 1 barang C. Total perolehan = 492 juta
CONTOH 3: RELIABILITY Suatu peralatan elektronik terdiri atas 3 komponen utama yang
disusun secara seri. Agar keandalan (reliability) sistem tersebut lebih baik lagi maka dimungkinkan untuk menambah unit-unit paralel pada ketiga komponen utama dengan kendala biaya, serta dengan tujuan mendapat- kan keandalan yang lebih tinggi.
Tabulasi untuk tambahan unit paralel dengan kondisi biaya (ci) dan probabilitas sistem dapat berfungsi (Ri) adalah sebagai berikut:
Jumlah Komponen 1 Komponen 2 Komponen 3Unit Paralel R1 c1 R2 c2 R3 c3
1 0,6 1 0,7 3 0,5 22 0,8 2 0,8 5 0,7 43 0,9 3 0,9 6 0,9 5
............... Contoh 3: Reliability
Pada tiap komponen utama minimal harus dipasang 1 unit paralel.
Tahapan adalah untuk komponen utama (ada 3 tahapan). Tujuan perhitungan adalah mendapatkan probabilitas berfungsi-
nya sistem yang tinggi (maksimasi reliabilitas). Kendalanya adalah biaya, misalnya total dana $ 10 juta (satuan c,
dalam juta $).
→ Penyelesaian dengan metode backward (ada 3 tahap).
............... Contoh 3: Reliability
Dana x3=1 x3=2 x3=3 f3*(x3) x3*2 0,5 0,5 1
3 0,5 0,5 1
4 0,5 0,7 0,7 2
5 0,5 0,7 0,9 0,9 3
6 0,5 0,7 0,9 0,9 3
Tahap 3; max {f3 x3}
Pada tahap ini, cukup dicantumkan nilai R, dari data asal dengan total dana yang disiapkan adalah $ 6 juta.
Dana yang sudah pasti dipakai minimal $ 2 juta (untuk memasang 1 unit paralel di komponen utama Ill).
............... Contoh 3: Reliability
H asil Tahap 3: Dengan dana $ 2 juta hingga $ 3 juta, dipasang 1 unit paralel (1 x
$ 2 juta) dengan reliabilitas 0,5 . Dengan dana $ 4 juta, dipasang 2 unit paralel (2 x $ 2 juta)
dengan reliabilitas 0,7 . Dengan dana $ 5 juta hingga $ 6 juta, dipasang 3 unit paralel (3 x
$ 2 juta) dengan reliabilitas 0,9. Hasil terbaik di tahap 3 akan digunakan untuk mencari yang terbaik di tahap 2 nantinya. Untuk ke tahap 2, minimal dana yang terpakai adalah $ 5 juta ($ 2 juta + $ 3 juta) untuk pemasangan minimal 1 unit paralel pada komponen utama II dan Ill). Dana maksimal yang dipakai adalah $ 9 juta (karena harus disiapkan minimal 1 unit paralel pada komponen utama I yang berharga $ 1 juta).
............... Contoh 3: Reliability
Dana x2=1 x2=2 x2=3 f2*(x2) x2*5 0,7x0,5=0,35 0,35 1
6 0,7x0,5=0,35 0,35 1
7 0,7x0,7=0,49 0,8x0,5=0,40 0,49 1
8 0,7x0,9=0,63 0,8x0,5=0,40 0,9x0,5=0,45 0,63 1
9 0,7x0,9=0,63 0,8x0,7=0,56 0,9x0,5=0,45 0,63 1
Tahap 2: max {f2x2, f3*(dana-x3)}
Probabilitas sistem yang disusun seri adalah hasil perkalian antara probabilitas tiap komponennya. Dana yang disiapkan adalah $ 9 juta.
Hasil tahap 2 menunjukkan bahwa se1alu hanya memasang 1 unit parale1 saja (dari nilai X2* = 1).
Lanjut ke tahap 1 yang cukup ditampilkan dengan total dananya (10 juta).
............... Contoh 3: Reliability
Hasil tahap 2: Dengan dana $ 5 juta hingga $ 6 juta, yang terbaik adalah
dipasang 1 unit paralel di komponen utama II (1 x $ 3 juta) dan 1 unit parale1 di komponen utama III (1 x $ 2 juta) dengan reliabilitas 0,7 x 0,5 = 0,35 .
Dengan dana $ 7 juta, yang terbaik adalah dipasang 1 unit parale1 di komponen utama II (1 x $ 3 juta) dan 2 unit parale1 di komponen utama III (2 x $ 2 juta) dengan reliabilitas 0,7 x 0,7 = 0,49
Dengan dana $ 8 juta hingga $ 9 juta, yang terbaik adalah dipasang 1 unit parale1 di komponen utama II (1 x $ 3 juta) dan 3 unit parale1 di komponen utama III (3 x $ 2 juta) dengan re1iabilitas 0,7 x 0,9 = 0,63.
Tahap 1: max {f1x1, f2*(dana-x2)}
............... Contoh 3: Reliability
Dana x1=1 x1=2 x1=3 f1*(x1) x1*
10 0,63x0,63=0,378 0,8x0,63=0,504 0,9x0,49=0,441 0,540 2
• Reliabilitas tertinggi adalah 0,504. Solusi terbaiknya adalah dengan memasang 2 unit paralel di komponen utama I, 1 unit paralel di komponen utama Il, dan 3 unit paralel di komponen utama Ill.
Komponen Utama I
KomponenUtama II
Komponen tama III
Jumlah Unit Paralel yang dipasang 2 1 3
Biaya yang dibutuhkan 2 x $ 1juta 1x $ 3juta 3 x $ 2juta
Realibilitas 0,8 0,7 0,9
............... Contoh 3: Reliability
Solusi (ringkasan) terbaiknya
Total biaya = $10 juta. Total reliabilitas = 0,8 X 0,7 X 0,9 = 0,504
............... Contoh 3: Reliability
............... Contoh 3: Reliability
............... Contoh 3: Reliability
............................................. Contoh 1: Stage Coach
............................................. Contoh 1: Stage Coach
top related