Analisis Penerapan Integer Linear Programming (ILP) dan Algoritma Branch and Bound untuk Memaksimumkan Laba Usaha (Studi Kasus UKM Gasela Mebel)

UKM Gasela mebel merupaka UKM yang bergerak di bidang kerajinan furniture, seperti lemari 3 pintu, lemari 2 pintu, meja rias, dan meja TV. Pada proses produksinya UKM ini menggunakan sistem make to order artinya hanya memproduksi saat ada pesanan dari konsumen. Dalam satu hari UKM Gasela mebel memproduksi 1 atau 2 unit produk saja sementara bahan baku untuk pembuatan furniture itu sendiri masih banyak yang tersisa, sehingga produksi barang ada UKM Gasela mebel tidak mendapat hasil optimal dan sulit untuk mendapatkan keuntungan yang maksimal. Dari permasalahan ini dilakukan ppenerapan metode Integer Linear Programming dan Algoritma Branch and Bound. Berdasarkan perhitungan menggunakan software POM-QM for Windows dan perhitungan manual maka didapatkan hasil produksi optimal dalam satu hari yaitu lemari 3 pintu (X1) = 3 unit, lemari 2 pintu (X2) = 1 unit, meja rias (X3) = 4 unit, dan meja TV (X4) = 4 unit, dengan keuntungan 2.495.000 diambil dengan gaji pegawai untuk 4 orang sebesar Rp. 600.000 dan biaya transportasi 50.000 maka total laba bersih pada UKM Gasela mebel adalah 1.845000 dalam satu hari jika semua produk dapat terjual habis.

Kata kunci : Algoritma branch and bound, integer linear programming, perencanaan produksi