Sebuah perusahaan memproduksi 2 jenis mesin pertanian , yaitu Mesin Pemanen Kentang (MPK)dan Mesin Pemanen Jagung (MPJ) . Masing - masing jenis produk melalui tahapan proses yaitu bagian kelistrikan dan perakitan. Waktu yang diperlukan untuk kelistrikan untuk Mesin Pemanen Kentang (MPK) 2 jam dan untuk Mesin Pemanen Jagung (MPJ) memerlukan waktu 1 jam. Sedangkan waktu yang diperlukan untuk perakitan untuk Mesin Pemanen Kentang (MPK) adalah 5 jam dan untuk Mesin Pemanen Jagung (MPJ) adalah 9 jam. Perusahaan tersebut hanya mempunyai waktu untuk bagian kelistrikan selama 13 jam dan waktu perakitan 41 jam per minggu. Mesin Pemanen Kentang (MPK) menghasilkan keuntungan $ 5 (dalam satuan ribuan) per unit sedangkan Mesin Pemanen Jagung (MPJ) menghasilkan keuntungan $ 7 (dalam satuan ribuan) per unit.
Pertanyaan
Rumuskan model pemrograman integer dari permasalahan di atas!
Berapa unit Mesin Pemanen Kentang (MPK) dan Mesin Pemanen Jagung (MPJ) yang harus diproduksi agar keuntungan maksimum? (Jelaskan langkah-langkah penyelesaian dengan menggunakan metode Branch-Bound )
Pertanyaan
Rumuskan model pemrograman integer dari permasalahan di atas!
Berapa unit Mesin Pemanen Kentang (MPK) dan Mesin Pemanen Jagung (MPJ) yang harus diproduksi agar keuntungan maksimum? (Jelaskan langkah-langkah penyelesaian dengan menggunakan metode Branch-Bound )
Jawaban:
Model pemrograman integer untuk permasalahan di atas dapat dirumuskan sebagai berikut:
Variabel:
Letakkan:
x = Jumlah unit Mesin Pemanen Kentang (MPK) yang diproduksi
y = Jumlah unit Mesin Pemanen Jagung (MPJ) yang diproduksi
Fungsi Tujuan:
Maksimalkan Keuntungan = 5x + 7y
Kendala:
1. Waktu yang tersedia untuk bagian kelistrikan: 2x + y ≤ 13
2. Waktu yang tersedia untuk perakitan: 5x + 9y ≤ 41
3. Jumlah unit yang diproduksi harus non-negatif: x ≥ 0, y ≥ 0
Berikut adalah langkah-langkah penyelesaian menggunakan metode Branch-Bound:
1. Hitung batas bawah (lower bound) awal dengan menghitung keuntungan maksimum jika semua mesin yang diproduksi adalah jenis MPK atau MPJ dengan asumsi tidak ada batasan waktu. Misalnya, jika hanya memproduksi MPK: x = 41/5 = 8 (dibulatkan ke bawah), maka keuntungan maksimum = 5 * 8 = 40 ribu dolar. Jika hanya memproduksi MPJ: y = 41/9 = 4 (dibulatkan ke bawah), maka keuntungan maksimum = 7 * 4 = 28 ribu dolar. Pilih batas bawah yang lebih tinggi, yaitu 40 ribu dolar.
2. Buat simpul awal dengan semua variabel bernilai 0 dan keuntungan sementara = 0.
3. Mulai proses Branch-Bound:
a. Periksa setiap simpul:
- Jika simpul tidak memenuhi semua kendala, lewati simpul tersebut.
- Jika simpul memenuhi semua kendala, periksa apakah keuntungan sementara lebih besar dari batas bawah saat ini. Jika tidak, lewati simpul tersebut.
- Jika simpul memenuhi semua kendala dan keuntungan sementara lebih besar dari batas bawah saat ini, perbarui batas bawah saat ini dan catat solusi sementara.
b. Bagi simpul yang memenuhi semua kendala menjadi dua simpul anak, dengan masing-masing simpul anak menambahkan satu unit dari salah satu jenis mesin (MPK atau MPJ) ke simpul induk.
c. Ulangi langkah (a) dan (b) untuk semua simpul anak yang dihasilkan.
4. Terus ulangi langkah (3) sampai semua simpul telah diperiksa.
5. Setelah semua simpul telah diperiksa, solusi optimal akan ditemukan dengan keuntungan maksimum yang tercatat.
Dalam implementasi sebenarnya, langkah-langkah ini akan dijalankan secara terkomputerisasi dengan menggunakan algoritma Branch-Bound untuk mencari solusi optimal dengan keuntungan maksimum.