Langsung ke konten utama

ALGORITMA BRANCH AND BOUND

 

ALGORITMA BRANCH AND BOUND

Algoritma Branch and Bound adalah metode algoritma umum untuk mencari solusi optimal dari dari berbagai permasalahan optimasi, terutama untuk optimasi diskrit dan kombinatorial. Sebagaimana pada algoritma runut-balik, algoritma Branch and Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam pohon ruang status. Yang membedakan keduanya adalah bila pada algoritma runut-balik, ruang solusi dibangun secara dinamis berdasarkan skema DFS (Depth First Search), maka pada algoritma Branch and Bound ruang solusi dibangun dengan skema BFS (Breadth First Search). Pada algoritma ini, permasalahan dibagi bagi menjadi subregion subregion yang mungkin mengarah ke solusi. Inilah yang disebut dengan branching, mengingat prosedur ini akan dilakukan berulang ulang secara rekursif untuk setiap subregion dan setiap subregion yang dihasilkan akan membentuk sebuah struktur pohon yang disebut sebagai pohon pencarian atau pohon branch-and- bound di mana simpul simpulnya membangun subregion subregion. Selain branching, lgoritma ini juga melakukan apa yang disebut dengan bounding yang merupakan cara cepat untuk mencari batas atas dan bawah untuk solusi optimal pada subregion yang mengarah ke solusi. Algoritma Branch and Bound banyak digunakan untuk memecahkan berbagai macam permasalahan antara lain : persoalan Knapsack 0/1, Travelling Salesman Problem (TSP), The N-Queens Problem (Persoalan N-Ratu), Graph Colouring (Pewarnaan Graf), Sirkuit Hamilton, Integer Programming, Nonlinear Programming, Quadratic Assignment Problem (QAP), Maximum Satisfiability Problem (MAX-SAT), dan lain sebagainya.

Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah. Algoritma ini memiliki 2 prinsip, yaitu:

·   Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching

·       Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik

APLIKASI ALGORITMA BRANCH AND BOUND DALAM PENYELESAIAN INTEGER PROGRAMMING

Telah dijelaskan sebelumnya bahwa algoritma Branch and Bound dapat digunakan untuk menyelesaikan Integer Programming. Gambar 1 adalah flowchart aplikasi algoritma Branch and Bound dalam menyelesaikan Integer Programming dengan optimasi minimum. Gambar 2 adalah flowchart aplikasi algoritma Branch and Bound dalam menyelesaikan Integer Programming dengan optimasi maksimum. Berikut ini adalah contoh aplikasi algoritma Branch and Bound untuk menyelesaikan Integer Programming :

Persoalan :

Maksimum Z = 9x1 + 5x2 + 6x3 + 4x4

Dengan batasan :

1. 6x1 + 3x2 + 5x3 + 2x4 <= 10

2. x3 + x4 <= 1

3. x1 + x3 <= 0

4. x2 + x4 <= 0

5. xi <= 1, xi >= 0, xi integer

Langkah 1 : Inisialisasi Pohon

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum :

Pohon :


Langkah 2 :

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum :

Pohon :


Langkah 3 :

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum : ~

Keterangan : Iterasi anak kiri aras 1

Pohon :

                          


Langkah 4 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kanan aras 1

Pohon :


Langkah 5 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan: Iterasi anak kanan aras 1 dan anak kiri aras 2

Pohon :


Langkah 6 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kiri aras 2 dengan solusi terbaik

Pohon :

 

Langkah 7 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Perluasan anak kiri aras 2

Pohon :


Langkah 8 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kiri aras 3

Pohon :


               

Langkah 9 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Bunuh anak kiri aras 3 karena tidak mungkin mengarah ke solusi (melanggar batasan ke 2 dan 4

Pohon :


Langkah 10 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kanan aras 3

Pohon :


Langkah 11 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Perluasan anak kanan aras 3 dan iterasi anak kiri aras 4

Pohon :


Langkah 12 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Bunuh anak kanan aras 4 karena tidak mungkin mengarah ke solusi (melanggar batasan ke 1)

Pohon :


Langkah 13 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Bunuh anak kanan aras 2 karena jika anak kanan aras 4 dibunuh, aras 2 tidak mungkin mengarah ke solusi

Pohon :


Setelah menjalani berbagai langkah, diperoleh solusi optimal dari permasalahan di atas.

Solusi : {1,1,0,0}

Nilai Z maksimum : 14


Refrensi :

https://piptools.net/algoritma-bb-branch-and-bound/

 

Nama            : Yohanes Bosco Christo Setya Atmaka

NPM             : 19316049

Kelas             : TK 19 C

Fakultas         : http://ftik.teknokrat.ac.id/

Universitas    : https://teknokrat.ac.id/

Komentar

Posting Komentar

Postingan populer dari blog ini

Sketsa Konseptual Automatic Teller Machine (ATM)

U niversitas Teknokrat Indonesia Website UTI :    https://teknokrat.ac.id/   Website FTIK :   https://ftik.teknokrat.ac.id/ Nama     :  Yohanes Bosco Christo Setya Atmaka NPM       :  19316049 Kelas      :  TK 20 A      Disini saya akan menjelaskan tentang sketsa konseptual dari sebuah Automatic Teller Machine (ATM). Automatic Teller Machine (ATM)        A TM adalah singkatan dari Anjungan Tunai Mandiri atau Automatic Teller Machine adalah sebuah alat elektronik yang mengijinkan nasabah bank untuk mengambil uang dan mengecek rekening tabungan mereka tanpa perlu dilayani oleh seorang "teller" manusia.      Mesin ini sering dikunjungi untuk melakukan transaksi perbankan secara mandiri, mulai dari transfer hingga tarik tunai.      ATM hadir sebagai fasilitas yang disediakan bank untuk memudahkan transaksi setiap nasabah karena tidak perlu selalu datang ke bank untuk melakukan transaksi tertentu. Fungsi ATM      Berikut ini beberapa fungsi ATM, yaitu : Menarik uang tunai 24 j
Posting Komentar
Baca selengkapnya

Review Artikel "Perancangan Teknik Kriptografi Block Cipher Berbasis Pola Permainan Tradisional Rangku Alu"

  REVIEW ARTIKEL Judul                     : "Perancangan Teknik Kriptografi Block Cipher Berbasis Pola Permainan Tradisional Rangku Alu " Jurnal                    : Jurnal Teknik Informatika dan Sistem Informasi Volume  & Hal     : Vol. 5 No. 2, Hal 189-200  Tahun                     : 2019 Penulis                    :  Perdana Bagas Tirta Kumbara, Magdalena A. Ineke Pakereng Link Artikel          :  https://journal.maranatha.edu/index.php/jutisi/article/view/1714 Reviewer : Nama : Yohanes Bosco Christo Setya Atmaka NPM : 19316049 Mata Kuliah : Kriptografi 1. Permasalahan Pada artikel ini menurut penulis pengaruh teknologi informasi kini berperan hampir di setiap aspek kehidupan baik dalam pemerintahan, pendidikan, kesehatan, perbankan, bahkan dalam bidang militer sekalipun. Oleh karena itu dikembangkan sebuah cabang ilmu yang mempelajari tentang keamanan informasi atau data yang disebut dengan Kriptografi. Namun dengan diterapkannya algoritma Kriptografi Block Cipher,
Posting Komentar
Baca selengkapnya

LAPORAN KEGIATAN JALAN SEHAT UTI

LAPORAN KEGIATAN JALAN SEHAT UNIVERSITAS TEKNOKRAT INDONESIA           “SEMANGAT SEHAT”           UNIVERSITAS TEKNOKRAT INDONESIA BANDAR LAMPUNG LAMPUNG 2021   LAPORAN KEGIATAN JALAN SEHAT UNIVERSITAS TEKNOKRAT INDONESIA   A.   LATAR BELAKANG Kesehatan merupakan sesuatu yang sangat berharga dan mahal harganya. Tiada insan yang rela apabila kesehatannya dibeli oleh orang lain. Hidup sehat membuat siapapun dapat mempermudah aktivitas yang dilakukannya. Ada banyak hal yang dapat dilakukan agar hidup sehat tanpa harus mengeluarkan keringat yang banyak, salah satunya dengan mengikuti jalan sehat. Jalan sehat merupakan  salah satu  olahraga yang murah dan terjangkau  serta  memberikan banyak manfaat, terutama kesehatan. Kemasan kegiatan  yang  membawa nuansa sederhana  dengan  ramai peserta  membuat kegiatan ini semakin meriah. Dan juga dapat digunakan sebagai ajang silaturahmi menjelang datangnya bulan suci ramadhan . Banyaknya kesibukan
Posting Komentar
Baca selengkapnya