INTEGER PROGRAMMING

Ada kalanya persoalan yang pemecahan optimalnya harus menghasilkan bilangan bulat (integer). Integer Programming dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan linier programming). Contohnya sebuah perusahaan yang memproduksi bola. Perusahaan ini tidak dapat memproduksi produknya dalam bentuk setengah jadi, maksudnya perusahaan tidak dapat memproduksi 2,7 bola, tetapi haruslah bilangan bulat. Siapa yang akan membeli 2,7 bola? Sehingga dengan metode pembulatan, kita bisa hasilkan misalnya 2 atau 3 bola per hari. Tetapi apakah metode pembulatan ini efisien? Kita lihat pada penjelasan selanjutnya. 

Model matematis dari integer programming sebenarnya sama dengan model linear programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat. Terdapat  3 macam permasalahan dalam Integer Programming (pemrograman bulat), yaitu Program Integer Murni (Pure Integer Programming), yaitu kasus dimana semua variabel keputusan harus berupa bilangan bulat. Kemudian Program Integer Campuran (Mixed Integer Programming), yaitu kasus dimana beberapa, tapi tidak semua, variabel keputusan harus berupa bilangan bulat. Integer programming dapat juga digunakan untuk memecahkan masalah dengan jawaban ya atau tidak (yes or no decision), untuk model ini variabel dibatasi menjadi dua, misal 1 dan 0, jadi keputusan ya atau tidak diwakili oleh variabel. Model ini seringkali disebut sebagai model pemrograman bulat biner (Zero One Integer Programming). 

Mari kita coba gunakan Integer Programming pada kasus berikut:

Suatu perusahaan keramik membuat dua macam guci,yaitu guci tipe elite dan guci tipe famili. Untuk membuat satu buah guci tipe elite, diperlukan bahan baku A sebanyak 10 kg, bahan baku B sebanyak 7 kg, dan bahan baku C sebanyak 6 kg. Untuk membuat guci tipe famili, diperlukan bahan baku A sebanyak 4 kg, bahan baku B sebanyak 5 kg, dan bahan baku C sebanyak 10 kg. Banyaknya bahan baku A yang tersedia sebanyak 40 kg, bahan baku B sebanyak 35 kg, dan bahan baku C sebanyak 60 kg. Sebuah guci tipe elite akan menghasilkan sumbangan terhadap laba Rp22.000 dan guci tipe famili Rp25.000. Kita akan mencari banyaknya setiapmacam guci yang dihasilkan agar dapat memaksimumkan sumbangan terhadap laba.

Masalah dapat kita rumuskan dalam persamaan-persamaan sebagai berikut (sumbangan terhadap laba dalam ribuan rupiah).

Kalau besarnya hasil produksi boleh berupa bilangan pecahan, ini dapat dikerjakan dengan metode linear programming. Kalau kita gunakan metode grafik, itu akan terlihat seperti berikut:

Dalam gambar itu, daerah feasible-nya adalah segi lima OABCD. Titik optimalnya di titik C karena nilainya maksimum sesuai dengan fungsi tujuan. Pada titik optimal ini, nilaiX 1 = 1,25, nilai X 2 = 5,25, dan nilai Z = 158,75. Artinya, perusahaan akan berproduksi dengan laba tertinggi kalau menghasilkan guci tipe elite sebanyak 1,25 buah dan menghasilkan guci tipe famili sebanyak 5,25, lalu menghasilkan sumbangan terhadap laba Rp158.750. Akan tetapi, jawaban itu didasarkan dengan solusi linear programming, nilai X1 dan X2 boleh pecahan. 

Kita harus sadari, yang dihasilkan oleh perusahaan itu guci dan satuannya harus utuh. Maka, seharusnya, kita kerjakan dengan integer programming. Pemecahan paling mudah dari problem diatas adalah dengan melakukan pembulatan (round off) dari solusi optimal kita lakukan pembulatan menjadi X1 = 2 dan X2 = 6, tetapi pembulatan tersebut diluar area kemungkinan produksi (lihat grafik), jadi tidak bisa dilakukan. Pembulatan berikutnya adalah ke dalam area kemungkinan produksi, yaitu X1 = 1 dan X2 = 5, produksi tersebut bisa dilakukan tetapi belum tentu merupakan solusi optimal.

Kalau kita lihat grafik berikut, tampak ada 22 titik yang dapat dipilih salah satu karena satuan X1 ataupun X2 bilangan utuh. Lalu, di antara ke-22 titik itu, kita pilih titik yang nilai Z-nya tertinggi karena tujuannya memaksimumkan.

Titik-titik alternatif yang feasible dan integer terlihat pada grafik. Diantara titik-titik itu, kita pilih yang paling besar (maksimum).

Dari tabel diatas dapat kita ketahui bahwa solusi optimal dari permasalahan produksi tersebut adalah di antara 22 titik yang feasible itu, alternatif sumbangan terhadap laba yang paling tinggi adalah alternatif ketujuh. Jawaban optimal adalah X1= 0, X2 = 6 dan Z = 150. Artinya, supaya menghasilkan sumbangan terhadap laba yang maksimal tidak menghasilkan guci tipe elite dan menghasilkan guci tipe famili sebanyak enam buah, sehingga menghasilkan sumbangan tehadap laba sebesar Rp150.000.

Perhatikan bahwa batasan integer ini menyebabkan keuntungan lebih rendah daripada solusi optimal dari linear programming. Hasil dari Integer Programming tidak akan pernah melebihi nilai keuntungan optimal dari solusi Linier Programming.

Sumber: EKMA4413