METODE PENCABANGAN DAN PENYIMPULAN
(BRANCH AND BAOUND METHODS)
STUDI KASUS
Pengusaha air minum isi ulang mempunyai 5 orang pegawai yang bertugas untuk mendistribusikan pengisian air minum untuk 5 daerah. Berikut ini data dari area distribusi air minum.
| Pegawai | Daerah Distribusi | ||||
| Bekasi | Depok | | | Tangerang | |
| Saputro | 30 | 27 | 27 | 17 | 14 |
| Riyanto | 15 | 24 | 30 | 18 | 17 |
| Budi | 23 | 29 | 19 | 28 | 19 |
| Sutarno | 22 | 31 | 14 | 25 | 15 |
| Pandu | 23 | 30 | 15 | 26 | 20 |
Pengusaha tersebut menginginkan penugasan yang sesuai untuk
Pengolahan Data
Langkah penyelesaian pertama, yaitu penugasan tiap pegawai antar ke daerah potensial Bekasi. Berikut ini adalah percabangan dengan nilai Upper Bound
Penugasan Daerah Bekasi
Branching
Gambar Branching Daerah Bekasi
Bounding
1. Node 1, yaitu penugasan Saputro ke Bekasi didapat nilai dari tabel diatas dengan cara menghilangkan baris1 dan kolom 1, kemudian cari nilai terbesar dari tiap-tiap kolom yang masih tersisa dan jumlahkan dengan nilai tempat bertugas.
30+31+30+28+20) = 139. UB = 139 dari nilai ini didapat penugasan :
Saputro – Bekasi, Sutarno – Depok, Riyanto –
2. Node 2, yaitu penugasan Riyanto ke Bekasi didapat nilai dari tabel dengan cara menghilangkan baris 2 kolom 1, kemudian cari nilai terbesar dari tiap-tiap yang masih tersisa dan jumlahkan denga nilai tempat bertugas.
15+31+27+28+20 = 121. UB = 121 dari nilai ini didapat penugasan :
Riyanto – Bekasi, Sutarno – Depok, Saputro –
3. Node 3, yaitu penugasan Budi ke Bekasi didapat nilai dari tabel dengan cara menghilangkan baris 3 kolom 1, kemudian cari nilai terbesar dari tiap-tiap yang masih tersisa dan jumlahkan denga nilai tempat bertugas.
23+31+30+26+20 = 130. UB = 130 dari nilai ini didapat penugasan :
Budi – Bekasi, Sutarno – Depok, Riyanto –
4. Node 4, yaitu penugasan Sutarno ke Bekasi didapat nilai dari tabel dengan cara menghilangkan baris 4 kolom 1, kemudian cari nilai terbesar dari tiap-tiap yang masih tersisa dan jumlahkan denga nilai tempat bertugas.
22+30+30+28+20 = 130. UB = 130 dari nilai ini didapat penugasan :
Sutarno – Bekasi, Pandu – Depok, Riyanto –
5. Node 5, yaitu penugasan Pandu ke Bekasi didapat nilai dari tabel dengan cara menghilangkan baris 5 kolom 1, kemudian cari nilai terbesar dari tiap-tiap yang masih tersisa dan jumlahkan denga nilai tempat bertugas.
23+31+30+28+19 = 131. UB = 131 dari nilai ini didapat penugasan :
Pandu – Bekasi, Sutarno – Depok, Riyanto –
Penugasan Daerah Depok
Penugasan pada daerah Bekasi yang diberikan kepada Saputro dengan nilai tertinggi , kemudian yang lainnya dicabangkan ke
Branching
Gambar Branching Daerah Depok
Masih ada empat subset yang belum di Fathomed ( node Riyanto, Budi, Sutarno, Pandu) selanjutnya pilih salah satu dari percabangan ( branching ). Pilih yang memiliki UB tertinggi, yakni node Saputro, ditugaskan pada daerah Bekasi. Sehingga tinggal Riyanto, Budi, Sutarno dan Pandu yang ditugaskan pada daerah selanjutnya Depok
Bounding
Gambar diatas menunjukan branching dari node Saputro dan kemudian menghitung nilai UB tiap-tiap node. Didapatkan nilai-nilai sebagai berikut:
1. Node 1 Riyanto ke Depok
Didapat nilai : 30+24+27+28+20 = 129
Dengan urutan penugasan : Saputro – Bekasi , Riyanto – Depok, Saputro –
2. Node 2 Budi ke Depok
Didapat nilai : 30+29+30+26+20 = 135
Dengan urutan penugasan : Saputro – Bekasi, Budi – Depok, Riyanto –
3. Node 3 Sutarno ke Depok
Didapat nilai : 30+31+30+28+20 = 139
Dengan urutan penugasa : Saputro – Bekasi, Sutarno – Depok, Riyanto –
4. Node 4 Pandu ke Tangerang
Didapat nilai : 30+30+30+28+19 = 137
Dengan urutan Penugasan : Saputro – Bekasi, Pandu – Depok, Riyanto –
Penugasan Daerah Jakarta
Penugasan pada daerah Depok yang diberikan kepada Sutarno dengan nilai tertinggi 139 kemudian yang lainnya dicabangkan ke
Branching
Gambar Branching Daerah Jakarta
Bounding
Gambar diatas menunjukan branching dari node Sutarno dan kemudian menghitung nilai UB tiap-tiap node. Didapatkan nilai-nilai sebagai berikut:
1. Node 1 Riyanto ke
Didapat nilai : 30+31+30+28+20 = 139
Dengan urutan penugasan : Saputro – Bekasi , Sutarno – Depok, Riyanto –
2. Node 2 Budi ke
Didapat nilai : 30+31+19+26+20 = 126
Dengan urutan penugasan : Saputro – Bekasi, Sutarno – Depok, Budi –
3. Node 3 Pandu ke
Didapat nilai : 30+31+15+28+19 = 123
Dengan urutan penugasa : Saputro – Bekasi, Sutarno – Depok, Pandu –
Penugasan Daerah Bogor
Penugasan pada daerah
Gambar Branching Daerah Bekasi
Bounding
Gambar diatas menunjukan branching dari node Saputro dan kemudian menghitung nilai UB tiap-tiap node. Didapatkan nilai-nilai sebagai berikut:
1. Node 1 Budi ke
Didapat nilai : 30+31+30+28+20 = 139
Dengan urutan penugasan : Saputro – Bekasi , Sutarno – Depok, Riyanto –
2. Node 2 Pandu ke
Didapat nilai : 30+31+30+26+19 = 136
Dengan urutan penugasan : Saputro – Bekasi, Sutarno – Depok, Riyanto –
Fathoming
Feasible solution = 139
Fathomed semua tiap node lain karena mereka memiliki UB value kurang dari 139
Stop
Karena tidak ada lagi tiap node yang un fathomed maka prosedur Branch and Bound dihentikan disini.
Solusi Optimal adalah calon sembarang (current incumbent) :
Saputro – Bekasi , Sutarno – Depok, Riyanto – Jakarta, Budi – Bogor, Pandu – Tangerang dengan nilai 139
MARKOV CHAIN
1. PENDAHULUAN
Konsep dasar Markov Chain baru diperkenalkan sekitas tahun 1907, oleh seorang Matematis Rusia Andrei A Markov (1856-1922). Model ini berhubungan dengan suatu rangkaian proses dimana kejadian akibat suatu eksperimen hanya tergantung pada kejadian yang langsung mendahuluinya dan tidak tergantung pada rangkaian kejadian sebelum-sebelumnya yang lain.
Markov Chain bias diterapkan diberbagai bidang antara lain ekonomi, politik, kependudukan, industri, pertanian dan lain-lain. Dalam studi kasus ini akan membahas tentang sebuah perusahaan sepatu dengan mencari steady state probabilitasnya.
2. STUDI KASUS
Seorang pengusaha sepatu ingin mengetahui keadaan steady state dari salah seorang pegawainya jika probabilitas transisinya adalah sebagai beriku:
- Probabilitas pegawai jika hari ini dan besok memproduksi adalah 0,70
- Probabilitas pegawai jika hari ini memproduksi dan besok tidak adalah 0.25
- Probabilitas pegawai jika hari ini tidak memproduksi dan besok memproduksi adalah 0.42
- Probabilitas pegawai jika hari ini dan besok tidak memproduksi adalah 0.52
Tentukan steady state probabilitasnya !
Penyelesian :
Tabel Produksi
| Hari ini | Hari Esok | |
| Produksi | Tidak Produksi | |
| Produksi | 0,70 | 0,25 |
| Tidak Produksi | 0,42 | 0,52 |
Probabilitasnya adalah :
Maka,
Jadi hasil yang didapat yaitu 0,584 untuk steady state 1 dan 0,416 untuk steady state 2
