INTEGER PROGRAMMING

Dalam masalah integer programming, jika model mengharapkan semua variabel basis bernilai integer (bulat positif atau nol), dinamakan pure all integer programming. Jima model hanya mengharapkan variabel tertentu bernilai integer, dinamakan mixed integer programming. Dan jika model hanya mengharapkan nilai nol atau satu untuk variabelnya, dinamakan zero one integer programming.
a. Pendekatan pembulatan
Suatu pendekatan yang sederhana dalam menyelesaikan masalah integer programming adalah dengan membulatkan nilai variabel keputusan yang diperoleh melalui LP. Pendekatan ini mudah dan praktis dalam usaha, waktu, dan biaya yang diperlukan untuk memperoleh solusi. Bahkan pendekatan pembulatan merupakan cara yang efektif untuk masalah integer programming. Yang besar dimana biaya perhitungan sangat tinggi atau untuk masalah dimana nilai-nilai solusi variabel keputusan besar.
b. metode grafik
masalah yang hanya melibatkan dua variable dapat diselesaikan secara grafik. Pendekatan ini identik dengan metode grafik linear programming kecuali solusi optimum harus memenuhi persyaratan bilangan bulat. Pendekatan yang termudah untuk menyelesaikan masalah integer programming dua dimensi adalah dengan menggunakan kertas grafik dan mengambarkan sekumpulan titik integer dalam ruang solusi layak.
c. metode gomory (cutting plane algorithm)
suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap pure integer programming pertama kali dikemukakan oleg R.E Gomory pada tahun 1958. Langkah-langkah prosedur gomory adalah:
• Sewlesaikan integer programming menggunakan metode simpleks jika masalahnya sederhana diselesaikan dengan pendekatan grafik sehingga pendekatan gomory kurang efisien.
• Periksa solusi optimum, jika variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi berakhir. Jika satu atau lebih variable basis memiliki nilai pecah terus ketahap selanjutnya.
• Buat suatu kendala gomory (suatu bidang pemotong atau cuttingplane) dan cari solusi optimum selalui prosedur dual simpeks.
d. metode branch & bound
metode ini diperkenalkan oleh and dan doig, dan dikembangkan lebih lanjut oleh little dan peneliti lainnya. Teknik ini dapat diterapkan untuk masalah pure maupun mixed integer programming. Langkah untuk metode maksimasi adalah:
• Selesaikan masalah linear programming dengan metode simpleks biasa tanpa pembatas bilangan bulat.
• Teliti solusi uptimumnya. Jika variabel basis yang diharapkan buat maka telah tercapai. Jika satu atau lebih variabel basis yang diharapkan bulat ternyata tidak bulat, lanjutkan langkah selanjutnya.
• Nilai solusi pecah yang layak dicabangkan kedalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinu yang tidak memenuhi persyaratan bulat dari masalah ini.
• Nilai solusi optimum kontinu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah. Sub-sub masalah memiliki batas atas kurang dari batas bawah yang suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap submasalah yang dicari.

Sumber;
Mulyono. Sri, S.E.,M.Sc. Riset Operasional. Fakultas Ekonomi Universitas Indonesia. 2002.