Knowing: Penelitian Operasional 2

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
Pegawai	Bekasi	Depok	Jakarta	Bogor	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 lima pegawainya terhadap daerah potensial agar mendapatkan hasil yang maksimum dalam hal pendapatan dan kepuasan pelanggan. Solusi persoalan penugasan dengan menggunakan algoritma branch and bound.

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 – Jakarta, Budi – Bogor, Pandu- Tangerang. Urutan feasible

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 – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan feasible

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 – Jakarta, Sutarno – Bogor, Pandu – Tangerang. Urutan infeasible

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 – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan infeasible.

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 – Jakarta, Budi – Bogor, Budi – Tangerang. Urutan infeasible

Penugasan Daerah Depok

Penugasan pada daerah Bekasi yang diberikan kepada Saputro dengan nilai tertinggi , kemudian yang lainnya dicabangkan ke kota Depok.

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 – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan feasible

2. Node 2 Budi ke Depok

Didapat nilai : 30+29+30+26+20 = 135

Dengan urutan penugasan : Saputro – Bekasi, Budi – Depok, Riyanto – Jakarta, Pandu – Bogor, Pandu – Tangerang. Urutan infeasible

3. Node 3 Sutarno ke Depok

Didapat nilai : 30+31+30+28+20 = 139

Dengan urutan penugasa : Saputro – Bekasi, Sutarno – Depok, Riyanto – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan feasible

4. Node 4 Pandu ke Tangerang

Didapat nilai : 30+30+30+28+19 = 137

Dengan urutan Penugasan : Saputro – Bekasi, Pandu – Depok, Riyanto – Jakarta, Budi – Bogor, Budi – Tangerang. Urutan infeasible

Penugasan Daerah Jakarta

Penugasan pada daerah Depok yang diberikan kepada Sutarno dengan nilai tertinggi 139 kemudian yang lainnya dicabangkan ke kota Jakarta

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 Jakarta

Didapat nilai : 30+31+30+28+20 = 139

Dengan urutan penugasan : Saputro – Bekasi , Sutarno – Depok, Riyanto – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan feasible

2. Node 2 Budi ke Jakarta

Didapat nilai : 30+31+19+26+20 = 126

Dengan urutan penugasan : Saputro – Bekasi, Sutarno – Depok, Budi – Jakarta, Pandu – Bogor, Pandu – Tangerang. Urutan infeasible

3. Node 3 Pandu ke Jakarta

Didapat nilai : 30+31+15+28+19 = 123

Dengan urutan penugasa : Saputro – Bekasi, Sutarno – Depok, Pandu – Jakarta, Budi – Bogor, Budi – Tangerang. Urutan infeasible

Penugasan Daerah Bogor

Penugasan pada daerah Jakarta yang diberikan kepada Riyanto dengan nilai tertinggi 136 kemudian yang lainnya dicabangkan ke kota Bogor

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 Bogor

Didapat nilai : 30+31+30+28+20 = 139

Dengan urutan penugasan : Saputro – Bekasi , Sutarno – Depok, Riyanto – Jakarta, Budi – Bogor, Pandu – Tangerang. Urutan feasible

2. Node 2 Pandu ke Bogor

Didapat nilai : 30+31+30+26+19 = 136

Dengan urutan penugasan : Saputro – Bekasi, Sutarno – Depok, Riyanto – Jakarta, Pandu – Bogor, Budi – Tangerang. Urutan feasible

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