METODE PERSAMAAN DIOPHANTINE LINEAR DALAM PENENTUAN SOLUSI PROGRAM LINEAR INTEGER

METODE PERSAMAAN DIOPHANTINE LINEAR DALAM PENENTUAN SOLUSI PROGRAM LINEAR INTEGER Asrul Syam Program Studi Teknik Informatika, STMIK Dipanegara, Makassar e-mail: [email protected]

Abstrak Masalah optimasi merupakan bagian yang penting dalam kehidupan manusia, bentuk optimasi tersebut dapat berupa meminimalkan biaya atau memaksimalkan keuntungan diantara beberapa kendala keterbatasan yang ada, serta diharapkan solusi yang diberikan berupa bilangan bulat. Penelitian ini bertujuan untuk menentukan solusi optimum dari suatu fungsi tujuan dalam program bilangan bulat dengan menggunakan metode persamaan Diophantine Linear. Metode penelitian dimulai dengan membahas persamaan linear, program bilangan bulat, teori bilangan, teorema Euclid, teorema sisa china, serta metode algoritma branch and bound dan metode cutting plane sebagai pembanding dari metode baru yang akan dibangun, yaitu metode persamaan Diophantine linear. Ketiga metode tersebut diaplikasikan pada beberapa contoh kasus dengan fungsi tujuan maksimum dan minimum untuk 2 dan 3 variabel, dan juga dapat diaplikasikan untuk kasus n variabel. Hasil penelitian menunjukkan bahwa dengan metode persamaan Diophantine linear, lebih mudah dan efisien dalam penentuan solusi optimum dari program bilangan bulat dibandingkan dengan metode branch and bound maupun metode cutting plane. Kata kunci: Solusi optimum, persamaan Diophantine linear Abstract Optimization problems is an important part of human life, such optimization can be a form of minimizing costs or maximizing profits among several obstacles existing limitations, as well as the expected solution given an integer. This study aims to determine the optimum solution of an objective function in the program integers using Linear Diophantine equation. The research method begins by discussing linear equations, program integers, number theory, Euclid's theorem, china remainder theorem, as well as branch and bound algorithm method and the method of cutting plane as a comparison of the new method to be constructed, the method of linear Diophantine equation. These three methods are applied in a few cases with maximum and minimum objective function for 2 and 3 variables, and can also be applied to the case of n variables. The results showed that the method of linear Diophantine equations, easier and more efficient in determining the optimum solution of the program integers instead of the branch and bound and cutting plane methods. Keywords: Optimum Solutions, linear Diophantine equation

1. PENDAHULUAN Permasalahan optimasi merupakan bagian yang tidak lepas dalam kehidupan manusia sehari-hari. Terkadang dalam usaha untuk memenuhi kebutuhannya, manusia membutuhkan proses optimasi dalam pekerjaannya. Bentuk optimasi tersebut, dapat berupa meminimalkan biaya yang dikeluarkan atau juga dapat berupa memaksimalkan pendapatan yang ingin diperoleh [10]. Namun 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 Received June1st,2012; Revised June25th, 2012; Accepted July 10th, 2012

itu, diperlukan proses optimasi dengan menggunakan metode integer programming untuk menyelesaikan masalah tersebut.[8] Adapun metode untuk mendapatkan solusi dari integer programming yang berupa bilangan bulat, yaitu dengan menggunakan algoritma Branch and Bound[1], algoritma Cutting Plane [5] dan metode persamaan Diophantine linear [6]. Untuk kasus optimasi yang cukup besar atau terdiri dari beberapa variabel, 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 [1]. Solusi Integer Programming dengan metode persamaan Diophantine linear, pertama kali dikaji oleh Risnawati ibnas [6], sehingga mampu memperoleh solusi bilangan bulat dengan cepat dan tepat, namun hanya terbatas pada masalah fungsi tujuan yang maksimal. Sehingga perlu untuk melanjutkan penelitian tersebut, yaitu menentukan solusi bilangan bulat dari Integer Programming dengan menggunakan metode Diophantine Linear yang mampu mencakup semua kasus optimasi, yaitu memaksimalkan atau meminimalkan fungsi tujuan.

2. BAHAN &METODE PENELITIAN Metode penelitian ini berbentuk kajian pustaka (studi literatur). Secara umum desain penelitian yang dilakukan adalah, identifikasi masalah, studi literatur mengenai program linear, menentukan solusi lain dari satu solusi yang diketahui dari persamaan diophantine linear untuk 2 variabel dan n variabel, membangun langkah penyelesaian program bilangan bulat dengan menggunakan metode persamaan Diophantine linear, serta mengaplikasikan dalam beberapa contoh kasus yang memuat 2 dan 3 variabel untuk fungsi tujuan yang maksimum maupun untuk fungsi tujuan yang minimum. Adapun alat bantu komputasi yang digunakan pada penelitian ini adalah POM for Windows 3 dan Geogebra. 3. HASIL DAN PEMBAHASAN Metode Persamaan Diophantine Linear pada Program Linear Integer 2 Variabel Diberikan masalah program linear integer 2 variabel dengan beberapa kendala sebagai berikut Maks/Min: 𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 Kendala 𝑎11 𝑥1 + 𝑎12 𝑥2 ≤ 𝑏1 atau ≥ 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 ≤ 𝑏1 atau ≥ 𝑏2 (1) ⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 ≤ 𝑏𝑚 atau ≥ 𝑏𝑚 Dengan 𝑥𝑖 ≥ 0 Berikut ini langkah-langkah aplikasi persamaan Diophantine linear 2 variabel dalam penentuan solusi Program linear integer 2 variabel (1)untuk fungsi tujuan yang maksimal. Langkah pertama, terlebih dahulu mencari solusi program bilangan bulat dengan menggunakan metode grafik atau metode simplex dari persamaan (1) sehingga diperoleh 𝑧𝑜𝑝𝑡 dengan 𝑥1 = 𝑥1∗ dan 𝑥2 = 𝑥2∗ . Jika 𝑥1∗ dan 𝑥2∗ bilangan bulat maka langkah selesai, namun jika tidak bulat, maka lanjut ke langkah selanjutnya. ∗ Langkah kedua, yaitu mengubah nilai 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan ∗ bilangan bulat terbesar yang kurang dari 𝑧𝑜𝑝𝑡 , sehingga fungsi tujuan dari (1) dapat dituliskan menjadi 𝑐1 𝑥1 + 𝑐2 𝑥2 = 𝑧1 (2) Title of manuscript is short and clear, implies research results (First Author)

Dimana persamaan (2) merupakan persamaan Diophantine Linear dengan 2 variabel. Persamaan (2) hanya memiliki solusi bulat jika 𝑑|𝑧1 dengan 𝑑 = 𝑔𝑐𝑑(𝑐1 , 𝑐2 . Anggap solusi bulat awal yang diperoleh dari (2) adalah (𝑥1 ,𝑥2 ), maka solusi bulat yang lain yang memenuhi (2) dan fungsi kendala pada (1) dapat diperoleh dari persamaan 𝑏 𝑎 𝑥1′ = 𝑥1 + (𝑑) . 𝑡 dan 𝑥2′ = 𝑥2 − (𝑑) . 𝑡 (3) Jika diperoleh solusi bulat pada persamaan (3), maka langkah selesai tetapi jika tidak diperoleh solusi bulat, maka lanjut ke langkah selanjutnya, yaitu mengubah nilai 𝑧1 menjadi 𝑧2 dengan 𝑧2 = 𝑧1 − 1 , kemudian mengulangi langkah kedua hingga langkah terakhir sampai diperoleh solusi bulat yang memenuhi fungsi kendala dari suatu fungsi tujuan (1). Berikut ini langkah-langkah aplikasi persamaan Diophantine linear 2 variabel dalam penentuan solusi Program linear integer 2 variabel (1) untuk fungsi tujuan yang minimal. Langkah pertama, terlebih dahulu mencari solusi program bilangan bulat dengan menggunakan metode grafik atau metode simplex dari persamaan (1) sehingga diperoleh 𝑧𝑜𝑝𝑡 dengan 𝑥1 = 𝑥1∗ dan 𝑥2 = 𝑥2∗ . Jika 𝑥1∗ dan 𝑥2∗ bilangan bulat maka langkah selesai, namun jika tidak bulat, maka lanjut ke langkah selanjutnya. ∗ Langkah kedua, yaitu mengubah nilai 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan ∗ ∗ bilangan bulat terbesar yang kurang dari 𝑧𝑜𝑝𝑡 jika 𝑧𝑜𝑝𝑡 bernilai negatif, dan mengubah nilai ∗ ∗ ∗ 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan bilangan bulat terkecil yang lebih dari 𝑧𝑜𝑝𝑡 jika 𝑧𝑜𝑝𝑡 bernilai positif, sehingga fungsi tujuan dari (1) dapat dituliskan menjadi 𝑐1 𝑥1 + 𝑐2 𝑥2 = 𝑧1 (4) Dimana persamaan (4) merupakan persamaan Diophantine Linear dengan 2 variabel. Persamaan (4) hanya memiliki solusi bulat jika 𝑑|𝑧1 dengan 𝑑 = 𝑔𝑐𝑑(𝑐1 , 𝑐2 ). Anggap solusi bulat awal yang diperoleh dari (4) adalah (𝑥1 ,𝑥2 ), maka solusi bulat yang lain yang memenuhi (1.4) dan fungsi kendala pada (1) dapat diperoleh dari persamaan 𝑏 𝑎 𝑥1′ = 𝑥1 + ( ) . 𝑡 dan 𝑥2′ = 𝑥2 − ( ) . 𝑡 (5) 𝑑 𝑑 Jika diperoleh solusi bulat pada persamaan (5), maka langkah selesai tetapi jika tidak diperoleh solusi bulat, maka lanjut ke langkah selanjutnya, yaitu mengubah nilai 𝑧1 menjadi 𝑧2 dengan 𝑧2 = 𝑧1 + 1 , kemudian mengulangi langkah kedua hingga langkah terakhir sampai diperoleh solusi bulat yang memenuhi fungsi kendala dari suatu fungsi tujuan (1). Metode Persamaan Diophantine Linear pada Program Linear Integer n variabel Diberikan masalah program linear integern variabel sebagai berikut Maks/Min 𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 Kendala: 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 atau ≥ 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2 atau ≥ 𝑏2

(6)

⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚 atau ≥ 𝑏𝑚 Dengan 𝑥𝑖 ≥ 0; 𝑖 = 1,2, … , 𝑛 Berikut ini langkah-langkah aplikasi persamaan Diophantine linear n variabel dalam penentuan solusi Program linear integer n variabel (6 ) untuk fungsi tujuan yang maksimal. Langkah pertama, terlebih dahulu mencari solusi program bilangan bulat dengan menggunakan metode grafik atau metode simplex dari persamaan (6) sehingga diperoleh 𝑧𝑜𝑝𝑡 dengan 𝑥1 = 𝑥1∗ ;𝑥2 = 𝑥2∗ ⋯ 𝑥𝑛 = 𝑥𝑛∗ .. Jika 𝑥1∗ ;𝑥2∗ ⋯ 𝑥𝑛∗ bilangan bulat maka langkah selesai, namun jika tidak bulat, maka lanjut ke langkah selanjutnya. ∗ Langkah kedua, yaitu mengubah nilai 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan ∗ bilangan bulat terbesar yang kurang dari 𝑧𝑜𝑝𝑡 , sehingga fungsi tujuan dari (6) dapat dituliskan menjadi Title of manuscript is short and clear, implies research results (First Author)

𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 = 𝑧1 (7) Dimana persamaan (7) merupakan persamaan Diophantine Linear dengan n variabel. Persamaan (7) hanya memiliki solusi bulat jika 𝑑|𝑧1 dengan 𝑑 = 𝑔𝑐𝑑(𝑐1 , 𝑐2 , … , 𝑐𝑛 ). Anggap solusi bulat awal yang diperoleh dari (2) adalah (𝑥1 ,𝑥2 , … 𝑥𝑛 ), maka solusi bulat yang lain yang memenuhi (2) dan fungsi kendala pada (1) dapat diperoleh dari persamaan 𝑏 𝑐 𝑎 𝑥1′ = 𝑥1 + (𝑑) . 𝑡 ; 𝑥2′ = 𝑥2 − (𝑑) . 𝑡 ; ⋯; 𝑥𝑛′ = 𝑥𝑛 + (𝑑) . 𝑡. (8) Jika diperoleh solusi bulat pada persamaan (8), maka langkah selesai tetapi jika tidak diperoleh solusi bulat, maka lanjut ke langkah selanjutnya, yaitu mengubah nilai 𝑧1 menjadi 𝑧2 dengan 𝑧2 = 𝑧1 − 1 , kemudian mengulangi langkah kedua hingga langkah terakhir sampai diperoleh solusi bulat yang memenuhi fungsi kendala dari suatu fungsi tujuan (6). Berikut ini langkah-langkah aplikasi persamaan Diophantine linear n variabel dalam penentuan solusi Program linear integer n variabel (6) untuk fungsi tujuan yang minimal. Langkah pertama, terlebih dahulu mencari solusi program bilangan bulat dengan menggunakan metode grafik atau metode simplex dari persamaan (6) sehingga diperoleh 𝑧𝑜𝑝𝑡 dengan 𝑥1 = 𝑥1∗ ;𝑥2 = 𝑥2∗ ⋯ 𝑥𝑛 = 𝑥𝑛∗ .. Jika 𝑥1∗ ;𝑥2∗ ⋯ 𝑥𝑛∗ bilangan bulat maka langkah selesai, namun jika tidak bulat, maka lanjut ke langkah selanjutnya. ∗ Langkah kedua, yaitu mengubah nilai 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan ∗ ∗ bilangan bulat terbesar yang kurang dari 𝑧𝑜𝑝𝑡 jika 𝑧𝑜𝑝𝑡 bernilai negatif, dan mengubah nilai ∗ ∗ ∗ 𝑧𝑜𝑝𝑡 menjadi 𝑧1 dimana nilai 𝑧1 merupakan bilangan bulat terkecil yang lebih dari 𝑧𝑜𝑝𝑡 jika 𝑧𝑜𝑝𝑡 bernilai positif, sehingga fungsi tujuan dari (1) dapat dituliskan menjadi 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 = 𝑧1 (9) Dimana persamaan (9) merupakan persamaan Diophantine Linear dengan n variabel. Persamaan (9) hanya memiliki solusi bulat jika 𝑑|𝑧1 dengan 𝑑 = 𝑔𝑐𝑑(𝑐1 , 𝑐2 , … , 𝑐𝑛 ). Anggap solusi bulat awal yang diperoleh dari (9) adalah (𝑥1 ,𝑥2 , … , 𝑥𝑛 ), maka solusi bulat yang lain yang memenuhi (9) dan fungsi kendala pada (1) dapat diperoleh dari persamaan 𝑏 𝑐 𝑎 𝑥1′ = 𝑥1 + (𝑑) . 𝑡 ; 𝑥2′ = 𝑥2 − (𝑑) . 𝑡 ; ⋯; 𝑥𝑛′ = 𝑥𝑛 + (𝑑) . 𝑡 (10) Jika diperoleh solusi bulat pada persamaan (10), maka langkah selesai tetapi jika tidak diperoleh solusi bulat, maka lanjut ke langkah selanjutnya, yaitu mengubah nilai 𝑧1 menjadi 𝑧2 dengan 𝑧2 = 𝑧1 + 1 , kemudian mengulangi langkah kedua hingga langkah terakhir sampai diperoleh solusi bulat yang memenuhi fungsi kendala dan fungsi tujuan (6). Penelitian ini menunjukkan bahwa, dengan menggunakan metode persamaan Diophantine Linear, solusi dari program bilangan bulat dengan fungsi tujuan yang maksimum ataupun fungsi tujuan minimum, dapat diperoleh dengan langkah yang lebih efektif dibandingkan dengan metode branch and bound dan metode cutting plane. Metode branch and bound sendiri hanya mampu menyelesaikan persoalan bilangan bulat yang terdiri dari 2 variabel, dan metode cutting plane mampu menyelesaikan persoalan bilangan bulat yang lebih dari 2 variabel, namun terkendala pada langkah yang lebih rumit dan panjang dalam hal iterasi, sehingga membutuhkan waktu yang lama dalam pemrosesan hasilnya [4]. Adapun untuk fungsi tujuan yang minimum, dipaparkan langkah-langkah penyelesaiannya seperti pada bab hasil di atas. Terdapat sedikit perbedaan pada langkah ke-3 ∗ yaitu, untuk nilai 𝑧𝑜𝑝𝑡 yang bernilai positif, maka dilakukan pembulatan ke atas, sedangkan ∗ untuk nilai 𝑧𝑜𝑝𝑡 yang bernilai negatif, maka dilakukan pembulatan ke bawah. Hal ini mungkin saja dapat terjadi dalam beberapa kasus optimasi yang fungsi tujuannya minimal, bahwa tidak semua fungsi tujuan yang minimal akan memberikan nilai negatif, tetapi juga bisa memberikan nilai positif [3]. Secara garis besar, persamaan Diophantine dibagi atas 2, yaitu persamaan Diophantine linear dan persamaan Diophantine non linear yang bisa terdiri dari n variabel. Pada tulisan ini, persamaan Diophantine yang dibahas dibatasi hanya pada persamaan Diophantinelinear dengan 2 atau lebih variabel. Adapun bentuk paling sederhana dari persamaan Diophantine linear yaitu memuat 2 variabel, yang berbentuk : Title of manuscript is short and clear, implies research results (First Author)

𝑎𝑥 + 𝑏𝑦 = 𝑐 (11) dengan 𝑎, 𝑏, 𝑐 ∈ 𝑍. Solusi persamaan Diophantine (11) di atas adalah semua pasangan bilangan bulat (𝑥, 𝑦) yang memenuhi persamaan (11) [5]. Teorema 1 Misalkan𝑎, 𝑏, 𝑐 ∈ 𝑍, dengan𝑎dan𝑏tidak keduanya nol dan𝑑 = gcd(𝑎, 𝑏). Maka persamaan Diophantine𝑎𝑥 + 𝑏𝑦 = 𝑐mempunyai solusi jika dan hanya jika𝑑|𝑐; dalam kasus ini terdapat tak berhingga banyak solusi. Solusi yang lain dapat ditentukan dengan persamaan berikut yaitu : 𝑏 𝑎 𝑥 = 𝑥0 + 𝑑 𝑡 , dan𝑦 = 𝑦0 − 𝑑 𝑡, untuk𝑡 ∈ 𝑍, dengan (𝑥0 , 𝑦0 )adalah solusi awal. [2] Teorema 2 Jika a dan b bilangan bulat positif, maka terdapat bilangan bulat s dan t sehingga 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏. Teorema 2 menjamin bahwa dari 2 buah bilangan bulat, maka selalu terdapat sebuah bilangan bulat yang selanjutnya disebut gcd (great common divisor) [2] Lemma 1 Jika 𝑎, 𝑏, dan 𝑐 bilangan bulat positif sehingga𝑔𝑐𝑑(𝑎, 𝑏) = 1dan𝑎|𝑏𝑐, maka 𝑎|𝑐. Lemma 1 menunjukkan bahwa bilangan a da b disebut relatif prim [2] Teorema 3: Teorema Euclid Jika 𝑎 = 𝑏𝑞 + 𝑟, dengan 𝑎, 𝑏, 𝑞, dan 𝑟 ∈ 𝑍. Maka 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑔𝑐𝑑(𝑏, 𝑟). Berdasarkan teorema Euclid diatas, maka nilai gcd atau FPB dari dua buah bilangan bulat dapat ditentukan. Teorema ini juga dapat diperluas untuk beberapa bilangan bulat [9] Algoritma Euclid yang Diperluas Dengan algoritma Euclid dapat dihitung 𝑔𝑐𝑑 dari 𝑎 dan 𝑏. Sesuai teorema 3, terdapat bilangan 𝑥 dan 𝑦 dengan 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑎𝑥 + 𝑏𝑦. Selanjutnya algoritma Euclid dapat diperluas sedemikian sehingga dapat digunakan untuk menghitung nilai 𝑥 dan 𝑦tersebut. Pada pembahasan algoritma Euclid bahwa diperoleh barisan sisa yaitu 𝑟0 , 𝑟1 , 𝑟2 , ⋯ , 𝑟𝑛 dan barisan hasil bagi 𝑞1 , 𝑞2 , ⋯ , 𝑞𝑛 . Selanjutnya, dicari barisan (𝑥𝑘 ) dan (𝑦𝑘 ) yang diperoleh dari barisan sisa dan hasil bagi sedemikian hingga pada iterasi terakhir diperoleh 𝑥 = (−1)𝑛 . 𝑥𝑛 dan 𝑦 = (−1)𝑛 . Pertama, ditentukan nilai awal 𝑥0 = 1, 𝑥1 = 0 , 𝑦0 = 0, 𝑦1 = 1. Selanjutnya, diberikan persamaan 𝑥𝑘+1 = 𝑞𝑘 . 𝑥𝑘 + 𝑥𝑘−1 dan 𝑦𝑘+1 = 𝑞𝑘 . 𝑦𝑘 + 𝑦𝑘−1, 0 ≤ 𝑘 < 𝑛. [6] Teorema 4: Teorema Sisa Cina (Chines Remainder Theorem) Jika 𝑚1 , 𝑚2 , ⋯ , 𝑚𝑛 adalah bilangan bulat positif sedemikian sehingga 𝑔𝑐𝑑(𝑚𝑖 , 𝑚𝑗 ) = 1 untuk 𝑖 ≠ 𝑗. Sistem : 𝑥 ≡ 𝑎1 (𝑚𝑜𝑑𝑚1 ), 𝑥 ≡ a2 (𝑚𝑜𝑑𝑚2 ), ⋮ 𝑥 ≡ 𝑎𝑛 (𝑚𝑜𝑑𝑚𝑛 ), mempunyai sebuah solusi modulo 𝑚 = 𝑚1 𝑚2 ⋯ 𝑚𝑛 (dengan 0 ≤ 𝑥 < 𝑚, dan semua solusi kongruen dengan modulo m) [7].

4. KESIMPULAN Dari hasil penelitian ini dapat disimpulkan bahwa metode Persamaan Diophantine linear dapat menentukan solusi dari program bilangan bulat secara akurat dan tepat dengan jumlah iterasi yang tidak panjang. Namun yang menjadi kendala dengan metode persamaan

Title of manuscript is short and clear, implies research results (First Author)

Diophantine linear terutama untuk jumlah variabel yang cukup banyak, yaitu sulitnya menentukan nilai awal dari program bilangan bulat yang harus memenuhi semua kendala program bilangan bulat yang ada 5. SARAN Diharapkan pada penelitian berikutnya, langkah-langkah yang dibangun dapat lebih disederhanakan dan pengaplikasian metode persamaan Diophantine linear tidak hanya terbatas pada program integer, tetapi juga dapat di aplikasikan pada program integer campuran.

UCAPAN TERIMA KASIH Penulismengucapkanterimakasihkepada Prof. Dr. Syamsuddiin Toaha, M.Sc dan Dr. Jeffry Kusuma atas bimbingannya selama dalam proses penyusuna artikel ilmiah ini.

DAFTAR PUSTAKA [1]

Aprilia S. (2005). Aplikasi Algoritma Branch and Bound untuk menyelesaikan Integer Programming. Lab Ilmu dan Rekayasa Komputer, Departemen Teknik Informatika ITB. [2] Bruce I. (2008). Linear Diophantine Equation. Diakses 13 Oktober 2014. Available from: http://www.groups.dcs.st-and.ac.uk/martin/teaching/1003/linier Diophantine.pdf [3] Davis T. (2006). Introduction to Diophantine Equation. Diakses 04 September 2014. Available from: http://www.geometer.org/mathcircles [4] Enty N. (2006). Aplikasi Algoritma Branch And Bound Untuk menyelesaikan Integer Programming. Fakultas Teknik. Universitas Stikubank. Semarang [5] Ginan G. (2008). Teori Bilangan dalam Persamaan Diophantine. Journal. Teknik elektro dan Informatika, Institut Teknologi, Bandung. [6] Ibnas R. (2012). Solusi Optimum Program Bilangan Bulat Dengan Metode Linier Diopantine. Tesis tidak diterbitkan. Makassar: Program Pascasarjana Universitas Hasanuddin. [7] Jong J.S. (2010). Riset Operasi dalam Pendekatan Algoritmis. Penerbit Andi: Yogyakarta. [8] Kurniawati R. & Soelaiman R. (2009). Penerapan Metode Barvinok Rational Functions pada Optimasi Integer Programming, Jurusan Teknik Informatika, Institut Teknologi Sepuluh November, Surabaya. [9] Munir R. (2004). Diktat Kuliah IF5054 Teori Bilangan (Number Theory). Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi: Bandung. [10] Siringoringo. (2005). Seri Teknik Riset Operasional Pemrograman Linear. Penerbit Graha Ilmu: Yogyakarta.

Title of manuscript is short and clear, implies research results (First Author)