BAB 1PENDAHULUANA. Latar BelakangPermasalahan optimasi merupakan bagian yang tidak asing lagi dalam kehidupan sehari-hari. Terkadang dalam usaha untuk memenuhi kebutuhannya, manusia membutuhkan proses optimasi dalam pekerjaannya. Bentuk optimasi tersebut, dapat berupa meminimumkan biaya yang dikeluarkan atau juga dapat berupa memaksimumkan pendapatan yang ingin diperoleh. Namun sering terdapat kendala yang diperoleh ketika hasil (nilai variabel keputusan) yang didapatkan dari proses optimasi tersebut berupa bilangan pecahan, padahal hasil yang diharapkan tidak memungkinkan jika menggunakan bilangan pecahan. Oleh karena itu, diperlukan proses optimasi dengan menggunakan metode integer programming untuk menyelesaikan masalah tersebut. (Kurniawati, R, dkk. 2008 ) Integer Programming atau biasa juga disebut program bilangan bulat adalah model program linear dengan penambahan persyaratan bahwa semua atau sebagian nilai variabelnya berupa bilangan bulat. Jika semua nilai variabelnya berupa bilangan bulat, maka dinamakan pure integer programming, sedangkan jika sebagian variabel-variabelnya berupa bilangan pecahan dan variabel-variabel tertentu berupa bilangan bulat, maka dinamakan mixed integer programming. Ada beberapa cara untuk menyelesaikan program bilangan bulat tersebut, diantaranya dengan menggunakan metode grafik untuk persamaan linear yang terdiri dari 2 variabel dan metode simpleks untuk persamaan linear yang lebih dari 2 variabel. Namun kedua metode ini biasanya menghasilkan variabel keputusan yang tidak bulat. Adapun metode untuk mendapatkan solusi dari integer programming yang berupa bilangan bulat, yaitu dengan menggunakan algoritma branch and bound (Aprilia, S. 2005), algoritma cutting plane (John E Michel, 1998) dan metode persamaan Diophantine linear (Risnawati Ibnas, 2012). Untuk kasus optimasi yang cukup besar, Algoritma Branch and Bound dan algoritma Cutting Plane tidak efektif diterapkan, karena kedua metode tersebut membutuhkan proses yang panjang dalam hal iterasi, sehingga membutuhkan waktu yang lama dalam pemprosesan hasilnya. (Aprilia, S. 2005)Solusi Integer Programming dengan metode persamaan Diophantine linear, telah dikaji oleh Risnawati Ibnas (2012) sehingga mampu memperoleh solusi bilangan bulat dengan cepat dan tepat, namun hanya terbatas pada masalah fungsi tujuan yang maksimum. Sehingga penulis bermaksud untuk melanjutkan penelitian tersebut, yaitu menentukan solusi bilangan bulat dari Integer Programming dengan menggunakan metode Diophantine Linear yang mampu mencakup semua kasus optimasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan.B. Rumusan MasalahDiberikan masalah program linear sebagai berikut:Fungsi tujuan:Maksimumkan atau Minimumkan

Fungsi kendala:

Dengan

Bagaimana menyelesaikan persamaan di atas yang variabel keputusannya bernilai bilangan bulat dan terdiri atas dua atau lebih variabel dengan metode persamaan Diophantine linear.C. Tujuan PenelitianPenelitian ini bertujuan untuk menentukan nilai optimum dari suatu fungsi tujuan dalam program linear dengan variabel keputusan bernilai bilangan bulat menggunakan persamaan Diophantine linear.D. Manfaat PenelitianManfaat penelitian ini adalah memberikan sumbangsih pengetahuan mengenai cara menyelesaikan masalah Integer Programming dengan metode Diophantine linear dengan fungsi tujuan maksimum atau minimum, serta fungsi kendala berupa pertidaksamaan untuk menghasilkan solusi optimum dengan variabel bilangan bulat dalam waktu yang lebih efisien.E. Ruang LingkupPenulisan tesis ini membahas persamaan Diophantine linear dengan variabel keputusan bernilai bilangan bulat sampai dengan n variabel dengan menerapkan pada contoh kasus dua sampai tiga variabel.

BAB II

TINJAUAN PUSTAKA

A. Program Linear

Program Linear atau Linear Programmingatau disingkat PL merupakan metode matematika dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan atau meminimumkan biaya.PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier. Fungsi tujuan linear adalah fungsi yang menggambarkan tujuan atas sasaran dalam masalah program linear yang berkaitan dengan pengaturan secara optimal sumber daya untuk memperoleh keuntungan maksimum, sedangkan fungsi kendala linear merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia. (Siringoringo, 2005).Bentuk umum program linear:Fungsi tujuan:Maksimumkan atau Minimumkan

Fungsi kendala:

dengan

Asumsi-asumsi program linear.a. ProporsionalitasAsumsi ini berarti bahwa naik turunnya nailai z dan penggunaan sumber atau fasilitas yang tersedia akan berubah sebanding degan perubahan tingkat kegiatan.b. Linearitas dan AdditivitasFungsi tujuan dan semua kendala harus linear. Denga kata lain, jika suatu kendala melibatkan dua variabel keputusan, dalam diagram dimensi dua, akan berupa garis lurus. Begitu juga, suatu kendala yang melibatkan tiga variabel akan menghasilkan suatu bidang datar dan kendala yang melibatkan n variabel akan menghasilkan hyperplane dalam ruang berdimensi n.c. Divisibilitas.Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan dapat berupa bilangan pecahan.d. Deterministic.Asumsi ini menyatakan bahwa semua parameter terdapat dalam model program linear, dapat diperkirakan dengan pasti meskipun jarang tepat. (Risnawati Ibnas, 2012)

Solusi optimal dari model program linear dapat diperoleh dengan menggunakan metode grafik, namun metode ini hanya terbatas untuk dua variabel keputusan dan metode simpleks yang dapat digunakan untuk dua atau lebih variabel keputusan. (Taha, H. 1993,2005)B. Program Bilangan BulatProgram bilangan bulat atau Integer Programming atau disingkat IP merupakan bentuk khusus dari program linear, dimana asumsi divisibilitas melemah atau hilang sama sekali. Ketika asumsi divisibilitas melemah, maka sebagian dari nilai variabel keputusan berupa bilangan bulat dan sebagian lainnya berupa bilangan pecahan. Model program bilangan bulat dimana hanya sebagian dari nilai variabelnya berupa bilangan bulat dan sebagian lainnya berupa bilangan pecahan disebut program bilangan bulat campuran, tetapi jika seluruh variabel keputusan dari suatu persoalan program linear harus bernilai bilangan bulat (asumsi divisibilitas hilang), maka persoalan tersebut disebut sebagai persoalan bilangan bulat murni.