Konsep Dasar Integer Programming Pada Riset Operasional

Konsep Integer Programming

Konsep Integer Programming secara sederhana adalah metode optimisasi dalam analisis matematika digunakan untuk menyelesaikan masalah keputusan di mana variabel keputusannya harus berupa bilangan bulat (integer).

Riset Operasional STIE Indocakti 

Contoh umum Integer Programming

Perusahaan perlu memutuskan jumlah produk yang akan diproduksi atau berapa banyak karyawan yang akan dipekerjakan. Keputusan ini harus berupa angka bulat, tidak bisa memproduksi setengah produk atau mempekerjakan seperempat orang.

Tujuan utama Integer Programming

Memaksimalkan atau meminimalkan fungsi (seperti keuntungan, biaya, atau waktu) dengan mematuhi sejumlah kendala yang ada. Kendala ini bisa berupa batasan sumber daya, waktu, anggaran, atau kapasitas

Contoh Lain Integer Programming

Perusahaan otomotif menggunakan Integer Programming untuk menentukan jumlah mobil setiap model yang diproduksi, mempertimbangkan kapasitas produksi, permintaan pasar, dan ketersediaan komponen.

Perencanaan produksi: 

Menentukan jumlah produk yang akan diproduksi.

Distribusi: 

Menentukan rute pengiriman yang paling efisien.

Pengambilan keputusan investasi: 

Memilih proyek investasi yang optimal.

Peranan Integer Programming

1. Menentukan jumlah maksimal produk yang diproduksi dengan mempertimbangkan kapasitas produksi, permintaan pasar, dan biaya produksi.
2. Merancang rute pengiriman yang paling efisien untuk meminimalkan biaya transportasi.
3. Memilih investasi yang memberikan keuntungan maksimum dengan mempertimbangkan keterbatasan anggaran.

Formulasi Masalah Metode Branch and Bound

Metode Branch and Bound adalah salah satu teknik pemecahan masalah dalam Integer Programming.

Hubungan antara Branch and Bound dengan Integer Programming

Membantu menemukan solusi optimal masalah nilai integer pada variabel keputusan. Integer programming melibatkan kombinasi variabel dan kendala yang kompleks, yang tidak sbisa diselesaikan dengan metode linear programming biasa.

Tujuan Metode Branch and Bound

1. Menemukan Solusi Optimal dengan Kendala Integer
2. Mengurangi Jumlah Perhitungan dengan Pemangkasan (Pruning)
3. Memastikan Efisiensi dalam Pemecahan Masalah Besar
4. Menghasilkan Solusi Optimal Secara Sistematis
5. Memastikan Keputusan yang Berdasarkan Nilai Optimal (Global Optimality)

Cara kerja Metode Branch and Bound dalam Integer Programming

1. Membagi (branching) masalah menjadi submasalah yang lebih kecil.
2. Memperkirakan Batas (bounding) untuk setiap submasalah guna menilai apakah submasalah itu masih mungkin memberikan solusi optimal.

Keuntungan Menggunakan Branch and Bound untuk Integer Programming

1. Menyederhanakan dan mempercepat pencarian solusi optimal
2. Dapat memaksimalkan atau meminimalkan fungsi tujuan dalam batasan integer yang diinginkan.

Kelebihan: Metode Branch and Bound dalam Integer Programming

1. Fleksibel: Dapat digunakan untuk berbagai jenis masalah Integer Programming.
2. Efisien: Dapat menemukan solusi optimal dengan cepat masalah berukuran sedang.

Kekurangan: Metode Branch and Bound dalam Integer Programming

Kompleksitas: Untuk masalah yang sangat besar, metode ini dapat menjadi sangat kompleks dan membutuhkan waktu komputasi yang lama.

Contoh Umum Penerapan Metode Branch and Bound

Mencari Kamar Hotel

Bayangkan ingin memesan kamar hotel untuk konferensi. Setiap kamar memiliki kapasitas tertentu, dan Anda memiliki sejumlah peserta konferensi yang harus diakomodasi. Tujuan Anda adalah memilih kamar yang tepat sehingga semua peserta terakomodasi dengan biaya seminimal mungkin.

Integer Programming:

Variabel keputusan adalah jumlah kamar yang akan dipesan untuk setiap tipe kamar. Batasannya adalah jumlah total kapasitas kamar harus mencukupi untuk semua peserta, dan anggaran Anda terbatas.

Metode Branch and Bound:

Metode ini dapat dianalogikan sebagai proses mencari kamar hotel secara sistematis.

Inisialisasi:

Mulai dengan mencari solusi awal, misalnya dengan mengisi semua peserta ke kamar terbesar terlebih dahulu, tanpa memperhatikan batasan jumlah kamar. Ini memberikan batas atas untuk biaya total.

Branching:

Kemudian membagi masalah menjadi dua cabang:

1. Cabang 1: Anda memutuskan untuk tidak memesan kamar tipe terbesar lagi.
2. Cabang 2: Anda memutuskan untuk memesan setidaknya satu kamar tipe terbesar.

Bounding:

Untuk setiap cabang, Anda menghitung batas bawah biaya total. Misalnya, jika Anda tidak memesan kamar tipe terbesar lagi, Anda dapat menghitung biaya minimum yang mungkin dengan mengisi semua peserta ke kamar tipe terkecil.

Prune: (mempersempit pencarian Solusi)

Jika batas bawah suatu cabang lebih tinggi dari batas atas cabang lain, maka cabang tersebut dapat diabaikan karena tidak mungkin memberikan solusi yang lebih baik. Anda melanjutkan proses ini untuk setiap cabang baru sampai menemukan kombinasi kamar yang memenuhi semua batasan dengan biaya terendah.