Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk super dan top masing -masing 6 dan 3 Petani tersebut ingin mengetahui berapa sak masing- masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi Tentukan solusi optimum menggunakan metode Branch and Bound. __ 20 25 24 8

Berikut penyelesaian masalah optimasi pembelian pupuk petani menggunakan metode Branch and Bound. Karena metode Branch and Bound biasanya digunakan untuk masalah bilangan bulat, kita akan berasumsi bahwa petani hanya bisa membeli pupuk dalam satuan sak. Kita perlu informasi tambahan: berapa kg nitrogen dan fosfat yang terkandung dalam satu sak pupuk super dan satu sak pupuk top. Misalkan:

* x: jumlah sak pupuk super yang dibeli
* y: jumlah sak pupuk top yang dibeli
* N_super: kg nitrogen per sak pupuk super
* P_super: kg fosfat per sak pupuk super
* N_top: kg nitrogen per sak pupuk top
* P_top: kg fosfat per sak pupuk top

Maka, permasalahan dapat dirumuskan sebagai berikut:

Minimalkan: Z = 6x + 3y (Total biaya)

Terkendala oleh:

* N_superx + N_topy ≥ 16 (Kebutuhan Nitrogen)
* P_superx + P_topy ≥ 24 (Kebutuhan Fosfat)
* x ≥ 0, y ≥ 0, x dan y adalah bilangan bulat (Tidak boleh pecahan sak pupuk)


Metode Branch and Bound:

Karena kita tidak memiliki nilai N_super, P_super, N_top, dan P_top, kita tidak dapat menyelesaikan masalah ini secara numerik. Metode Branch and Bound akan bekerja sebagai berikut:

1. Menentukan Batas Atas (Upper Bound): Kita akan memulai dengan solusi yang memenuhi kendala, misalnya dengan mencoba beberapa kombinasi x dan y. Biaya dari kombinasi ini akan menjadi batas atas awal.

2. Membuat Pohon Branch and Bound: Kita akan membagi ruang solusi menjadi cabang-cabang berdasarkan nilai x dan y. Misalnya, kita bisa mulai dengan cabang x=0, x=1, x=2, dst. Untuk setiap nilai x, kita akan mencari nilai y minimum yang memenuhi kendala.

3. Menghitung Batas Bawah (Lower Bound): Untuk setiap cabang, kita akan menghitung batas bawah biaya. Ini bisa dilakukan dengan mengabaikan kendala bilangan bulat dan menyelesaikan masalah linear programming secara relaksasi (tanpa batasan x dan y harus bilangan bulat).

4. Pemangkasan Cabang: Jika batas bawah suatu cabang lebih besar dari batas atas terbaik yang sudah ditemukan, cabang tersebut dapat dipangkas karena tidak akan menghasilkan solusi yang lebih baik.

5. Iterasi: Proses ini diulang sampai semua cabang telah dieksplorasi atau dipangkas. Solusi dengan biaya minimum yang ditemukan adalah solusi optimum.


Kesimpulan:

Tanpa informasi tentang kandungan nitrogen dan fosfat dalam setiap sak pupuk, kita hanya dapat menjelaskan *proses* penyelesaian masalah menggunakan metode Branch and Bound. Untuk mendapatkan solusi numerik, kita perlu informasi tambahan tersebut. Setelah informasi tersebut tersedia, kita dapat menerapkan langkah-langkah di atas untuk menemukan jumlah sak pupuk super dan top yang harus dibeli petani agar biaya minimum tercapai dan kebutuhan pupuk terpenuhi.