Kontrak Perkuliahan: Dosen Pengampu

Kontrak Perkuliahan • Dosen Pengampu : • Maria Krisnawati, S.T., M.T. • Seto Sumargo, S.T., M.T.

• Komposisi Penilaian : (Sampai dengan UTS) • Tugas • Kuis • UTS

15% 10% 25%

Kontrak Perkuliahan • Semua pekerjaan yang dikumpulkan harus mencantumkan, Nama dan NIM apabila tidak ada akan diberi diskon nilai • Tugas dikumpulkan sebelum Kuliah dimulai, keterlambatan pengumpulan tugas akan diberikan diskon nilai 10% per hari keterlambatan • Tugas harus ditulis tangan (kecuali ditentukan lain) • Ada kuis singkat tanpa pemberitahunan sebelumnya, yang materinya meliputi topik – topik kuliah minggu sebelumnya. • Tidak ada kuis susulan dengan alasan apapun • Pada saat perkuliahan mhs wajib membawa materi kuliah (hard copy)

Referensi 1. Operations Research An Introduction Eighth Edition, Hamdy A. Taha

Materi 1. 2. 3. 4. 5. 6.

Deterministic Dynamic Programming Deterministic Inventory Models Decision Analysis and games Queuing Systems Simulation Modeling Markov Chain

DETERMINISTIC DYNAMIC PROGRAMMING MARIA KRISNAWATI, S.T., M.T. Jurusan Teknik Industri Universitas Jenderal Soedirman

Pendahuluan • Dynamic programming mendeterminasikan solusi optimum dari permasalahan multivariabel dengan membaginya (dekomposisi) menjadi beberapa tahap, tiap tahap menyelesaikan subproblems variabel tunggal. • Keuntungan dari dekomposisi adalah proses optimasi tiap tahap hanya menyelesaikan satu variabel , lebih sederhana daripada menyelesaikan banyak variabel secara simultan

• Model DP pada dasarnya recursive equation yang menghubungkan tiap tahap yang berbeda dari permasalahan dengan cara memastikan bahwa setiap tahap memiliki solusi optimal yang feasible dan feasible untuk permasalahan keseluruhan

Contoh aplikasi DP

Recursive Nature of Computations in DP • Dynamic programming problems adalah masalah multi tahap(multistage) dimana keputusan dibuat secara berurutan (in sequence) , sehingga solusi optimum dari suatu sub problem digunakan sebagai input untuk sub problem berikutnya. • Ketika sub problem terakhir diselesaikan, solusi optimum dari permasalahan keseluruhan juga ditemukan. • Contoh : Shortest-Route Problems (Network problem) • Taha

Recursive Nature of Computations in DP • Untuk menemukan shortest (longest) path yang menghubungkan dua titik dalam network • Joe tinggal di new York dan akan pergi ke LA. Dia berencana menginap di rumah temannya dalam perjalanan tersebut. Joe punya teman di Columbus, Nashville, Louisville, Kansas, Omaha, Dallas, San Antonio, dan Denver. Joe tahu setelah satu hari perjalanan dia akan mencapai Columbus, Nashville atau Louisville. Setelah perjalanan 2 hari akan mencapai Kansas, Omaha, atau Dallas. Setelah 3 hari perjalanan akan mencapai Denver atau San Antonio. Setelah 4 hari akan mencapai LA. Untuk meminimalkan jarak, kemana Joe harus menginap setiap malam dalam perjalanannya ?

network 68

Columbus 2

79

Kansas 5

105

55

90

Nashville 760 3

76

Omaha 540

Stage 1

Stage 2

LA 10

6 94

51 Louisville 4

103

54

66 77

Denver 8

79

58 New York 1

61

San Antonio 9

79 70 83

Dallas 7

Stage 3

135

27

Stage 4 Stage 5

The recursion Ide bekerja secara backward adalah kita mulai menyelesaikan masalah dari yang paling sederhana untuk menyelesaikan masalah yang kompleks. Jadi kita mulai dari kota yang hanya membutuhkan perjalanan satu hari ke LA yaitu kota Denver dan San Antonio (kota pada stage 4) Kemudian kita gunakan informasi dari stage 4 untuk menemukan jarak terpendek dari kota pada stage 3 ( yang membutuhkan 2 hari) ke LA Demikian seterusnya sampai kita menemukan shortest path dari kota New York ke LA

Solusi • Tentukan Cij = jarak kota i ke kota j • Tentukan Ft(i) = panjang shortest path dari kota i ke kota LA dimana kota i adalah kota pada stage t • Tentukan shortest path ke LA dari setiap kota di setiap stage mulai dari stage akhir

Stage 4 computation Karena hanya ada satu path dari kota pada stage 4 ke LA maka kita dapat langsung menentukan Jarak terpendek dari kota Denver ke kota LA adalah F4(8) = 1030 Dari kota San Antonio ke LA adalah F4(9) = 1390

Stage 3 computation • Terdapat tiga kota pada stage 3 yaitu kota Kansas, Omaha dan Dallas • Dari kota Kansas terdapat 2 path menuju kota LA yaitu Path 1. Kansas – Denver – kemudian mengambil shortest path dari Denver ke LA Path 2. Kansas – San Antonio – kemudian mengambil shortest path dari San Antonio ke LA

Panjang Path 1 didapatkan dari C58 + F4(8) Panjang Path 2 didapatkan dari C59 + F4(9) Sehingga Jarak terpendek dari kota 5 ke kota 10 adalah

𝐹3 5 C58 + F4(8) = 610 + 1030 = 1640 ∗ = 𝑚𝑖𝑛 ቊ C59 + F4(9)= 790+1390=2180

Dengan cara yang sama, jarak terpendek dari kota Omaha(6) ke LA adalah

𝐹3 6 𝐶68 + 𝐹4 8 = 540 + 1030 = 1570 ∗ = 𝑚𝑖𝑛 ቊ 𝐶69 + 𝐹4 9 = 940 + 1390 = 2330 Jarak terpendek dari kota Dallas ke LA adalah

𝐹3 7 𝐶78 + 𝐹4 8 = 790 + 1030 = 1820 = 𝑚𝑖𝑛 ቊ 𝐶79 + 𝐹4 9 = 270 + 1390 = 1660 ∗

Stage 2 computation Pada stage 2 terdapat 3 kota yaitu Columbus, Nashville, dan Louisville Terdapat 3 path dari Coulumbus ke LA yaitu Path 1. Columbus – Kansas – kemudain mengambil shortest path dari Kansas Path 2. Columbus – Omaha – kemudian mengambil shortest path dari Omaha Path 3. Columbus – Dallas – kemudian mengambil shortest path dari Dallas

• Panjang Path 1. adalah C25+F3(5) • Panjang Path 2. adalah C26+F3(6) • Panjang Path 3. adalah C27+F3(7) Sehingga Jarak terpendek dari kota 2(Columbus ) ke LA adalah 𝐶25 + 𝐹3 5 = 680 + 1640 = 2320 ∗ 𝐹2 2 = 𝑚𝑖𝑛 ൞ 𝐶26 + 𝐹3 6 = 790 + 1570 = 2360 𝐶27 + 𝐹397) = 1050 + 1660 = 2710

• Dengan cara yang sama, jarak terpendek dari kota Nashville(3) ke LA adalah

𝐹2 3 𝐶35 + 𝐹3 5 = 580 + 1640 = 2220 ∗ = 𝑚𝑖𝑛 ൞ 𝐶36 + 𝐹3 6 = 760 + 1570 = 2330 𝐶37 + 𝐹3 7 = 660 + 1660 = 2320 Jarak terpendek dari kota Louisville(4) ke LA adalah 𝐹2 4

𝐶45 + 𝐹3 5 = 510 + 1640 = 2150 ∗ = 𝑚𝑖𝑛 ൞ 𝐶46 + 𝐹3 6 = 700 + 1570 = 2270 𝐶47 + 𝐹3 7 = 830 + 1660 = 2490

Stage 1 computation • Dari kota 1(New York) terdapat 3 Path ke kota LA yaitu Path 1. New York – Columbus – kemudian mengikuti shortest path dari Columbus Path 2. new York – Nashville – kemudian mengikuti shortest pat dari Nashville Path 3. New York – Louisville – kemudian mengikuti shortest path dari Louisville

Jarak terpendek dari kota New york (1) ke LA (10) adalah

𝐹1 1

𝐶12 + 𝐹2 2 = 550 + 2320 = 2870 ∗ = 𝑚𝑖𝑛 ൞ 𝐶13 + 𝐹2 3 = 900 + 2220 = 3120 𝐶14 + 𝐹2 4 = 770 + 2150 = 2920 Penentuan Path optimal Dari Stage 1 kota 1: 1 – 2 Dari Stage 2 kota 2 : 2 – 5 Dari Stage 3 kota 5 : 5 – 8 – 10 Jadi Path Optimal adalah 1 – 2 – 5 – 8 – 10 dengan jarak 2870

Karakteristikaplikasi Dynamic Programming • Karakteristik 1 • Problem dapat dibagi menjadi beberapa stage dan dibutuhkan sebuah keputusan pada setiap stage.

• Karakteristik 2 • Setiap stage memiliki beberapa state. • state, adalah informasi yang dibutuhkan pada setiap stage untuk membuat keputusan optimal.

• Karakteristik 3 • Keputusan yang dipilih pada setiap stage menggambarkan bagaimana state pada stage sekarang ditransformasi ke state pada stage berikutnya.

• Karakteristik 4 • Diberikan state sekarang, keputusan optimal untuk setiap stage yang tersisa harus tidak tergantung pada state yang dicapai sebelumnya atau keputusan yang diambil sebelumnya. • Ide ini dikenal sebagai the principle of optimality.

• Karakteristik 5 • Jika state untuk suatu problem telah diklasifikasikan ke T stage, harus terdapat rekursi yang menghubungkan biaya atau reward yang didapat selama stage t, t+1, …., T terhadap biaya atau reward yang didapat dari stages t+1, t+2, …. T.

Resource allocation Problem • Kementerian tenaga kerja memiliki dana sebesar 5 juta dollar untuk digunakan oleh kementerian – kementerian yang lain untuk menciptakan tenaga kerja • Terdapat 4 kementrian yang mengajukan permohonan dana untuk kepentingan penciptaan tenaga kerja. • Kementrian tenaga kerja ingin mengalokasikan dana untuk memaksimalkan banyaknya tenaga kerja yang 24 diciptakan

• Data

Estimasi pekerjaan baru yang tercipta Kementrian

Biaya $ juta pekrjaan yg diciptakan

Pendidikan

4

225

Keuangan

1

45

2

125

3

190

Perhubungan Pertanian

50 pekerjaan per biaya $1 juta 2

75

3

155

4

220

25

SOLUsi • Kementrian tenaga kerja ingin : • Memaksimumkan total banyaknya tenaga kerja baru • Biaya yang tersedia adalah $5 juta.

26

SOLUsi • Notasi Dj = jumlah dana yang dialokasikan ke kementrian j, di mana j adalah : 1 - Pendidikan, 2 - Keuangan, 3 – Perhubungan , 4 - Pertanian. Rj(Dj) = banyaknya pekerjaan baru yang tercipta jika Kementrian j dibiayai sebesar $Dj juta.

• Model Max R1(D1) + R2(D2) + R3(D3) + R4(D4) ST D1 + D2 + D3 + D4 <= 5 D1, D2, D3 , D4 >= 0

27

The Backward Dynamic Programming

• Definisikan Fj(Xj) adalah maksimum banyaknya pekerjaan baru yang diciptakan oleh kementrian (stage) j,j+1,…, 4, jika tersedia dana sebesar $Xj juta (state) untuk kementrian j sampai 4.

28

The Backward Dynamic Programming • Stage 4: Kementrian Pertanian,(KPt) • Mulailah dengan tahap terakhir j = 4 (Kementrian Pertanian, KPt). • Alokasikan dana yang memaksimalkan jumlah pekerjaan baru yang diciptakan untuk kementrian ini. • Jelas, solusi optimal untuk kementrian terakhir adalah menggunakan semua jumlah yang tersedia pada stage ini). • Solusi optimal untuk stage terakhir disebut “The boundary condition”

29

SOLUsi • Stage 4: Tabel Kementrian Pertanian

States

Ingat: untuk Kementrian Pertanian Biaya 2 3 4

Pekerjaan 75 155 220

Dana Pendanaan OptimalMaximum Pkerjaan Tersedia untuk Stage 4 F4(X4) 0 0 0 1 0 0 2 2 75 3 3 155 4 4 220 5 5 220 30

SOLUsi • Stage 3: Kementrian Perhubungan, (KPh) • Pada stage ini kita mempertimbangkan pendanaan untuk Kementrian Perhubungan dan Kementrian Pertanian • Untuk jumlah dana tertentu yang tersedia untuk kedua kementrian ini, keputusan besarnya dana yang diberikan untuk kementrian KPh akan berpengaruh pada dana yang tersedia untuk KPt 31

SOLUTION Stage 3: Tabel Kementrian Perhubungan Dana yg Tersedia utk Stage 3,4 (X3) 0 1 2

3

Kemungkinan Dana yg Pendanaan Tersisa utk utk Stage 3 Stage 4 (D3) (X3-D3) 0 0 0 1 1 0 0 2 1 1 2 0 0 3 1 2 2 1 3 0

Max. Jobs baru Optimal F3(X3) Jk m'alokasikan D3 ke Stage 3 Optimal D3 R3(D3)+F4(X3-D3) 0+0 F3(0) = 0; D3(0) = 0 0+0 50+0 = 50 F3(1) = 50; D3 = 1 0+75 = 75 50+0 = 50 100+0 F3(3) = 100; D3 = 2 0+155 = 155 50+75 = 125 100+0 = 100 150+0 = 150 F3(3) = 155; D3 = 0

32

SOLUsi Stage 3: Tabel Kementrian Perhubungan Dana yg Tersedia utk Stage 3,4 (X3)

4

5

Kemungkinan Dana yg Pendanaan Tersisa utk utk Stage 3 Stage 4 (D3) (X3-D3)

0 1 2 3 4 0 1 2 3 4 5

4 3 2 1 0 5 4 3 2 1 0

Max. Jobs baru Optimal F3(X3) Jk m'alokasikan D3 ke Stage 3 Optimal D3 R3(D3)+F4(X3-D3)

0+220 = 220 50+155 = 205 100+75 = 175 150+ 0 = 150 200+ 0 = 220 F3(4) = 220; D3 = 0 0+220 = 220 50+220 = 270 100+155 = 255 150+75 = 225 200+0 = 200 250+0 = 250 F3(5) = 270; D3 = 1

33

SOLUsi • Stage 2: Kementrian Keuangan, (KKu) • Pada stage ini kita memikirkan pendanaan untukKementrian Keuangan dan dua Kementrian sebelumnya yaitu Kementrian Perhubngan dan Pertanian • Untuk state tertentu (jumlah dana yang tersedia untuk ketiga Kementrian ), keputusan mengalokasikan sejumlah dana untuk Kementrian Keuangan berpengaruh pada jumlah dana yang tersedia untuk Kementrian Perhubungan dan Pertanian (state pada stage j = 3).

34

SOLUsi Dana yg Tersedia utk Stage 2,3,4 (X2) 0 1 2 3

4

5

KemungkinanDana yg pendanaan Tersisa utk utk Stage 2 Stage 3,4 (D2) (X2-D2) 0 0 1 0 1 2 0 1 2 3 0 1 2 3 0 1 2 3

0 1 0 2 1 0 3 2 1 0 4 3 2 1 5 4 3 2

Max. Jobs baru Optimal F2(X2) Ji m'alokasikan D2 ke Stage 2 Optimal D2 R2(D2)+F3(X2-D2) 0+0 0+50 = 50 45+0 = 45 0+100 = 100 45+50 = 95 125+0 = 125 0+155 = 155 45+100 = 145 125+50 = 175 190+0 = 190 0+220 = 220 45+155 = 195 125+100 = 225 190+50 = 240 0+270 = 270 45+220 = 265 125+155 = 280 190+100 = 290

F2(0) = 0; D2 = 0 F2(1) = 50; D2 = 0 F2(2) = 125; D2 = 2

F2(3) = 190; D2 = 3

F2(4) = 240; D2 = 3

F2(5) = 290; D2 = 3

35

SOLUsi • Stage 1: Kementrian Pendidikan (KPd) • Pada stage ini kita memikirkan pendanaan untuk Kementrian Pendidikan dan semua kementrian sebelumnya. • Perhatikan bahwa pada stage 1 masih terdapat $5 juta untuk dialokasikan (X1 = 5).

36

SOLUsi • Stage 1: Kementrian Pendidikan hanya mengusulkan satu proposal yaitu sebesar $4 juta, sehingga (D1 = 0, 4). Tidak didanai

Dana yg Kemungkinan Tersedia Pendanaan utk Stage 1,2,3,4 utk Stage 1 (X1) (D1) 5

0 4

Proposal didanai

Dana yg Tersisa utk Stage 2,3,4 (X1-D1) 5 1

Max. Jobs Baru Optimal F1(X1) Jk m'alokasikan D3 ke Stage 3 Optimal D1 R1(D1)+F2(X1-D1) 0+290 = 290 225+50 = 275

F1(5) = 290; D1 = 0

37

SOLUsi Stage 1 2 3 4

0

1

D2 = 0 D3 = 0 D4 = 0

D2 = 0 D3 = 1 D4 = 1

State 2

3

4

D2 = 2 D3 = 2 D4 = 2

D2 = 3 D3 = 0 D4 = 3

D2 = 3 D3 = 0 D4 = 4

5 D1 = 0 D2 = 3 D3 = 1 D4 = 5

Alokasi pendanaan optimal untuk memaksimalkan banyaknya pekerjaan yang diciptakan adalah : Pendidikan = $0 Keuangan = $3 million Perhubungan = $2 million Pertanian = $0 Maximum banyaknya pekerjaan yang diciptakan= 290

38

komponenDynamic Programming

Variabel Stage Variabel State

Notasi j Xj

Variabel Keputusan

Dj

Nilai Stage Return

Rj(Dj)

Nilai Optimal

Fj(Xj)

Boundary Condition

F(XN)

Nilai Solusi Optimal

F1(T)

Deskripsi Contoh Titik Keputusan Keempat Kementrian Jumlah Resource Dana yang tersisa utk dialokasikan tersisa untuk dialokasikan ke Kementrian - kementrian Keputusan yg mungkin Dana yang diberikan untuk pada stage j kementrian ke j stage return karena Banyaknya pekerjaan pada membuat keputusan Dj kementrian j jika didanai Dj Return kumulatif terbaik Maximum banyaknya pekerjaan baru untuk stages j dan yang diciptakan kementrian j,…,4. stages sisanya pada state Xj. sekumpulan nilai optimal Banyaknya pekerjaan baru yang diciptak untuk stage terakhir (N) mendanai kementrian 4 dg $X4 juta. Kumulatif return terbaik Maximum total banyaknya pekerjaan 39bar dengan dana tersedia T utk dialokasikan ke semua kementrian

Dynamic Recursive Relationship • Dynamic programming adalah proses rekursif • Recursive relationship berikut menggambarkan proses untuk resource allocation • Definisikan Fj(Xj) sebagai maksimum banyaknya pekerjaan baru yang diciptakan oleh kementrian (stage j, j+1, …, 4, jika tersedia $Xj juta untuk pendanaan kementrian (stage) j sampai 4.

Fj(Xj) = Max {(Rj(Xj) + Fj+1(Xj - Dj)}

40 Untuk semua Xj yang feasible

Dynamic Recursive Relationship

Bentuk dari recursion relation berbeda beda dari satu problem ke problem yang lain, tapi secara umum idenya sama : Lakukan yang terbaik untuk stage yang tersisa dengan resource sisa yang tersedia.

41