Integer Linear Programming Dengan Pendekatan Metode Cutting Plane dan Branch and Bound untuk Optimasi Produksi Tahu

Abstract

Integer Linear Programming (ILP) dapat menyelesaikan permasalahan Linear Programming (LP) dengan tambahan syarat bahwa nilai dari variabel keputusan harus berupa bilangan bulat (integer) baik sebagian maupun keseluruhannya. Penyelesaian ILP dapat menggunakan metode Cutting Plane dan Branch and Bound. Metode cutting plane merupakan metode yang digunakan untuk menyelesaikan ILP baik bilangan bulat murni maupun bilangan bulat campuran dengan menambahkan batasan baru yang disebut gamory. Batasan gamory diberikan jika nilai dari variabel keputusan belum integer. Batasan-batasan tersebut secara efektif akan menyingkirkan beberapa ruang solusi yang tidak berisi bilangan bulat yang layak, tetapi tidak pernah menyingkirkan satupun titik bilangan bulat yang layak. Sedangkan metode Branch and Bound dengan cara membuat cabang bagi masing-masing variabel keputusan yang bernilai tidak bulat agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru. Berdasarkan hasil penelitian yang telah dilakukan dapat diketahui bahwa solusi optimal yang dihasilkan oleh kedua metode tersebut adalah sama, yaitu: jumlah produksi tahu besar dan tahu kecil adalah sebanyak 339239 unit per bulan dan 4 unit per bulan dengan keuntungan maksimal Rp 77971299.6 per bulan.