Contoh Soal dan Jawaban Metode Branch and Bound (Grafik)
"Contoh soal dan jawaban metode branch and bound metode grafik, z = 5x1 + 8x2, x1 + x2 = 5 , 4x1 + 7x2 = 28 langkah pertama..."
2 min read
Contoh soal dan jawaban metode Branch and Bound - Apa itu metode Branch and Bound? Metode ini dikenal sebagai algoritma pemecahan masalah dalam mencari solusi optimal soal-soal linear programming dengan menggunakan dengan langkah-langkah percabangan dan pembatasan. |
| Contoh Soal dan Jawaban Metode Branch and Bound (Grafik) |
Metode Branch and Bound adalah salah satu metode pendekatan yang dapat digunakan untuk menyelesaikan masalah program linear. Algoritma Branch and Bound juga digunakan dalam programming integer. Dalam teknik optimasi, setelah materi Branch and Bound akan dilanjutkan dengan pengenalan Knapsack problem algoritma Greddy.
Metode Branch and Bound bertujuan untuk memperkecil search tree. Branch adalah percabangan sedangkan Bound adalah pembatasan.
Jadi, secara sederhana, algoritma Branch and Bound digunakan untuk menyelesaikan masalah dan mencari solusi maksimal suatu soal programming linear dengan percabangan yang memiliki syarat batasan berupa fungsi kendala.
Langkah-langkah algoritma Branch and Bound
- Branch, yaitu membangun semua cabang tree yang mungkin untuk menuju solusi
- Bound, yaitu menghitung node aktif (E-node) dan dead node (D-node) dengan menggunakan syarat batas constraint (kendala)
Cara menyelesaikan masalah program linear dengan metode Branch and Bound
- Buat persamaan Matematika dari soal cerita
- Selesaikan dengan menggunakan linear programming metode simplex atau grafik.
- Cari nilai optimal pada variabel. Nilai optimal harus bulat (Integer programming).
- Solusi dipecah menjadi cabang-cabang ke dalam sub-sub masalah dengan tujuan menghilangkan solusi yang belum memenuhi syarat.
- Fungsi tujuan pada sub masalah ditetapkan sebagai batas atas sedangkan solusi bulat terbaik ditetapkan menjadi batas bawah.
- Proses pencarian solusi optimal dengan pencabangan dihentikan (fathoming) jika solusi pada sub masalah terjadi:
- Infeasible, yaitu tidak memiliki daerah layak
- Semua variabel sudah bernilai bulat atau integer
- Pada contoh soal maksimisasi, penghentian pencabangan dilakukan ketika batas atas sub masalah lebih kecil atau sama dengan batas bawah.
- Pada contoh soal minimisasi, pencabangan dihentikan ketika sub masalah batas bawah lebih besar atau sama dengan batas atas.
Soal dan jawaban metode Branch and Bound
Untuk lebih mudahnya, kita langsung melihat contoh soal dan jawaban mencari solusi optimal metode Branch and Bound dari suatu masalah linear programming. Di contoh ini, kita menggunakan metode grafik. Kamu bisa menyelesaikan linear programming dengan metode simplex jika mau.
Silahkan nonton video Youtube ini. Kreatif dan keren. Menjelaskan tentang Branch and Bound dan terdapat contoh soal penyelesaian solusi optimal menggunakan metode grafik Branch and Bound.
Latihan soal metode Branch and Bound menggunakan metode grafik
Fungsi maksimum:
z = 5x1 + 8x2
Fungsi kendala:
x1 + x2 = 5
4x1 + 7x2 = 28
x1, x2 >= 0
Langkah pertama, selesaikan dengan linier programming menggunakan metode grafik. Gunakan metode eliminasi dan subtitusi untuk mencari nilai x1, x2 dan z baru. Setelah itu, gambarkan grafiknya dan carilah solusi optimal sampai semua syarat Branch and Bound terpenuhi.
Kalau belum paham tentang linear programming, maka latihan soal Branch and Bound harus disepelehkkan dulu dan kembali ke metode grafik dan simplex linear programming.
Lihat juga Contoh Soal Linier Programming Riset Operasi
Demikianlah Contoh Soal dan Jawaban Metode Branch and Bound. Semoga bermanfaat!