Integer Linear Programing

INTEGER LINEAR PROGRAMMING

Linear Programming (LP) merupakan teknik riset operasional (operation research technique) yang telah dipergunakan secara luas dalam berbagai jenis masalah manajemen (Gaspersz, 2004). Pemrograman linier memakai suatu model matematis untuk menggambarkan masalah yang dihadapi. Kata sifat ‘linier’ berarti bahwa semua fungsi matematis dalam model ini harus merupakan fungsi – fungsi linier. Kata ‘pemrograman’ di sini merupakan sinonim untuk kata ‘perencanaan’. Maka, membuat pemrograman linier adalah membuat rencana kegiatan – kegiatan untuk memperoleh hasil yang optimal, ialah suatu hasil yang mencapai tujuan yang ditentukan dengan cara yang paling baik (sesuai model matematis) di antara semua alternatif yang mungkin.

Komponen Model Integer Linear Programming

Integer linear programming memiliki tiga komponen utama, yaitu

1. Fungsi Tujuan (Objective Function)

Fungsi tujuan adalah fungsi yang menggambarkan tujuan/sasaran dari dalam permasalahan integer linear programming yang berkaitan dengan pengaturan secara optimal sumber daya-sumber daya untuk mencapai hasil yang optimal.

2. Fungsi Pembatas (Constraint Function)

Fungsi pembatas merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.

3. Variabel Keputusan (Decision Variables)

Variabel keputusan merupakan aspek dalam model yang dapat dikendalikan. Nilai variabel keputusan merupakan alternatif yang mungkin dari fungsi linier.

Bentuk Baku Model Pemrograman Linier

Secara matematis, model umum dari integer linear programming yang terdiri dari sekumpulan variabel keputusan X1, X2, …, Xn, dirumuskan sebagai berikut  :

Fungsi tujuan :  Maksimasi (atau Minimasi)

Asumsi – Asumsi Pemrograman Linier

1. Proporsionalitas, Naik turunnya nilai fungsi tujuan (Z) dan penggunaan sumber daya berubah sebanding (proporsional) dengan perubahan tingkat aktivitas.

2. Additivitas, Aktivitas (variabel keputusan) tidak saling mempengaruhi dalam menentukan nilai fungsi tujuan sehingga nilai fungsi tujuan merupakan penjumlahan kontribusi setiap variabel keputusan atau dengan kata lain kenaikan fungsi tujuan yang diakibatkan oleh suatu aktivitas dapat ditambahkan tanpa mempengaruhi bagian nilai fungsi tujuan yang diperoleh dari aktivitas lain.

3. Deterministik, Semua parameter yang terdapat dalam model matematis (Aij, Cj, bi) dapat ditentukan dengan pasti, meskipun jarang dapat ditentukan dengan tepat.

4. Accountability, Sumber-sumber yang tersedia harus dapat dihitung sehingga dapat dipastikan berapa bagian yang terpakai dan berapa bagian yang masih tersisa.

5. Linearity of Objectives, Fungsi tujuan dan kendala-kendala harus dapat dinyatakan sebagai suatu fungsi linear.

Solusi Model Integer Linear Programming

• Solusi model integer linear programming adalah jawaban akhir dari suatu pemecahan masalah. Pada suatu model matematis, solusi dikatakan layak (feasible solution) jika penyelesaiannya tidak melanggar batasan-batasan yang ada. Namun jika penyelesaiannya tidak memungkinkan pada alternatif-alternatif yang layak (feasible), maka solusi itu dikatakan tidak layak (no feasible solution). Integer Linear Programming (ILP) dapat diselesaikan dengan banyak cara, antara lain menggunakan grafik, metode eliminasi dan substitusi maupun menggunakan perangkat lunak. Perangkat lunak yang digunakan untuk memperoleh solusi model integer linear programming, antara lain Excel Solver, TORA, LINDO, AMPL dan LINGO.