POLINOMIAL KOMBINATORIK
DISERTASI
Oleh MARDININGSIH 098110007/Ilmu Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
POLINOMIAL KOMBINATORIK
DISERTASI
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Doktor dalam Program Studi Doktor Ilmu Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh MARDININGSIH 098110007/Ilmu Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
Judul Disertasi Nama Mahasiswa Nomor Pokok Program Studi
: : : :
POLINOMIAL KOMBINATORIK Mardiningsih 098110007 Doktor Ilmu Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Opim Salim S, M.Sc) Promotor
(Prof. Dr. Saib Suwilo, M.Sc) Co-Promotor
Ketua Program Studi
(Prof. Dr. Herman Mawengkang)
Tanggal lulus: 24 Juli 2013
(Prof. Dr. Tulus, M.Si) Co-Promotor
Dekan
(Dr. Sutarman, M.Sc)
Telah diuji pada Tanggal 24 Juli 2013
PANITIA PENGUJI DISERTASI Ketua Anggota
: Prof. Dr. Opim Salim S, M.Sc : 1. Prof. Dr. Saib Suwilo, M.Sc 2. Prof. Dr. Tulus, M.Si 3. Prof. Dr. Herman Mawengkang 4. Dr. Sutarman, M.Sc 5. Dr. Marwan Ramli, M.Si
PERNYATAAN
Saya menyatakan dengan sebenar-benarnya bahwa segala pernyataan dalam disertasi saya yang berjudul: POLINOMIAL KOMBINATORIK Merupakan gagasan atau hasil penelitian disertasi saya sendiri dengan pembimbingan para komisi pembimbing, kecuali yang dengan ditunjukkan rujukannya. Disertasi ini belum pernah diajukan untuk memperoleh gelar pada program sejenis di perguruan tinggi lainnya. Semua data dan informasi yang digunakan telah dinyatakan secara jelas dan dapat diperiksa kebenarannya. Medan, Juli 2013 Penulis,
Mardiningsih
i
ABSTRAK Polinomial kombinatorik merupakan masalah optimisasi yang berasal dari masalah kombinatorial yang berbentuk pemrograman polinomial dan integer. Penelitian ini menyajikan syarat agar suatu polinomial kombinatorik mempunyai penyelesaian. Syarat eksistensi (adanya) nilai optimum dapat diperoleh dengan memberikan batasan pada variabel keputusan dan menggunakan sifat-sifat himpunan penyelesaian (polihedra) dari model yang diberikan, dan menggunakan definisi kekonvekan fungsi pada bilangan bulat. Kata kunci: Polinomial kombinatorik, Polihedra, Nilai optimum
ii
ABSTRACT The combinatoric polynomial comes from optimization problem combinatorial in form the nonlinear and integer programming. This reasearch present a condition such that the combinatoric polynomial has solution. Existence of optimum value will be found by restriction of decision variable and properties of feasible solution set and definition convexity at integer. Through this condition, the optimum value could be known. Keywords: Combinatoric polynomial, Polihedra, Optimum value.
iii
KATA PENGANTAR Assalamualaikum Wr. Wb. Syukur Alhamdulilah, segala puji bagi Allah atas segala limpahan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan disertasi yang berjudul Polinomial Kombinatorik. Dalam meyelesaikan disertasi ini penulis telah banyak mendapat bantuan dan bimbingan, baik moril maupun material dari berbagai pihak. Pada kesempatan ini juga dengan segala kerendahan hati, penulis sampaikan ucapan terima kasih kepada:
1. Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, MSc(CTM). Sp.A(K) selaku Rektor Universitas Sumatera Utara, yang telah memberikan kesempatan dan bantuan dana kepada penulis untuk mengikuti Program Studi Doktor Ilmu Matematika, Fakultas MIPA, Universitas Sumatera Utara. 2. Bapak Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, dan komisi penguji yang telah memberikan kesempatan kepada penulis untuk menjadi peserta Program Doktor Ilmu Matematika angkatan 2009, dan telah memberikan masukan dan saran hingga selesainya disertasi ini. 3. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi S3 Ilmu Matematika, dan selaku komisi penguji. Atas keiklasan dan kesabaran serta ketulusan hati dalam memberi bimbingan dan dorongan dari awal hingga selesainya disertasi ini. iv
4. Bapak, Prof. Dr. Opim Salim Sitompul, M.Sc selaku Promotor, atas ketulusan hati dan keiklasan dalam membimbing dan mendukung dan mengarahkan penulis pada pembahasan isi dan penulisan hingga selesainya disertasi ini. 5. Bapak Prof. Dr. Tulus, M.Si selaku Co-Promotor dengan ketulusan hati dan memberi motivasi, mendukung dan mengarahkan penulis untuk masalah penulisan karya ilmiah serta membimbing penulis dalam menyelesaikan disertasi ini. 6. Bapak Prof. Dr. Saib Suwilo, M.Sc selaku Co-Promotor yang atas keiklasan dan ketulusan hati dalam memberi masukan dan arahan, mengenai isi disertasi ini. 7. Bapak Dr. Marwan Ramli, M.Si selaku komisi penguji yang atas keiklasan dan ketulusan hati dalam memberi masukan dan arahan, mengenai isi disertasi ini. 8. Seluruh Staf Pengajar Program Studi S3 Ilmu Matematika dan staf pengajar Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 9. Buat sahabat-sahabatku, dan seluruh teman-teman S-3 Ilmu Matematika yang tidak disebutkan satu persatu, yang memberi semangat dan dorongan dan doanya kepada penulis. 10. Saudari Misiani S.Si dan Staf Administrasi Program Doktor Ilmu Matemav
tika serta Staf Administrasi Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara.
Secara khusus penulis menyampaikan terimakasih kepada Alm. Ayahanda dan Almh. Ibunda tercinta, yang telah tak terhingga banyaknya mendidik tentang arti hidup dan mendoakan agar penulis berhasil dan manjadi orang yang bermanfaat. Penulis turut menyampaikan penghargaan dan terimakasih tak terhingga yang sangat mendalam kepada suamiku tercinta dan anak-anakku tersayang, juga buat semua kakak-kakak dan adik-adikku yang sangat menyayangiku yang telah memberikan support luar biasa demi keberhasilan pendidikan ini. Akhir kata penulis, semoga pendidikan yang saya peroleh ini bermanfaat untuk kebaikan umat manusia. Sekian maaf dan terimakasih.
Medan,
Juli 2013
Penulis,
Mardiningsih
vi
RIWAYAT HIDUP
Mardiningsih dilahirkan di Medan pada tanggal 5 april 1963, dari Ayah yang bernama Wiryamiharja (Alm) dan Ibu bernama Markonah (almh) sebagai anak bungsu dari delapan bersaudara. Pada tahun 1975 lulus SD Swasta Budisatrya Medan. Pada tahun 1978 lulus SMP Swasta PAB Sampali. Pada tahun 1981 Lulus SMA swasta Josua Medan. Pada tahun 1986 Lulus Sarjana Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Pada tahun 1999 memperoleh gelar Master Science pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung. Selanjutnya pada tahun 2009 penulis mengikuti pendidikan S3 program studi Ilmu Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Pada tahun 1988, penulis diterima sebagai staf pengajar di FMIPA USU, dan sampai saat ini penulis memperoleh pangkat Lektor Kepala golongan IV/c di Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Penulis menikah tanggal 1 Maret 1986, dan sampai saat ini telah dikaruniai Allah SWT dengan tiga orang putra.
vii
DAFTAR SINGKATAN DAN NOTASI a. R = Himpunan semua bilangan real b. Z = Himpunan bilangan bulat c. Z[x1, x2 , x3, . . . , xn ] = Z[x] adalah himpunan semua polinomial dengan n variabel x1 , . . . , xn dan koefisien bilangan bulat d. K[x1, x2, x3 , . . . , xn ] = K[x] adalah himpunan semua polinomial dengan n variabel x1 , . . . , xn dan koefisien field K e. Misalkan suatu field K dan bilangan bulat positif n, didefinisikan suatu ruang Eucledian atas K berdimensi n adalah himpunan K n = {(a1, . . . , an )|a1, . . . , an ∈ K} Zn = {(a1 , . . . , an )|a1, . . . , an ∈ Z} Rn = {(a1, . . . , an )|a1, . . . , an ∈ R} f. Z+ = himpunan bilangan real positif = {x ∈ R|x ≥ 0} g. Z+ = himpunan bilangan bulat positif = {x ∈ Z|x ≥ 0} h. Conv (K) = Konveks hull dari K memuat titik-titik interior bilangan bulat yang bukan elemen K i. Kn = Graph komplit dengan n verteks j. Himpunan tutup [a, b] = {x ∈ R|a ≥ x ≥ b} k. ∅ = Himpunan kosong l. ⊆ adalah himpunan bagian (subset) viii
DAFTAR ISI Halaman PERNYATAAN
i
ABSTRAK
ii
ABSTRACT
iii
KATA PENGANTAR
iv
RIWAYAT HIDUP
vii
DAFTAR SINGKATAN DAN NOTASI
viii
DAFTAR ISI
ix
DAFTAR TABEL
xi
DAFTAR GAMBAR
xii
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Tujuan penelitian
11
1.3 Manfaat Penelitian
11
1.4 Metodologi Penelitian
12
BAB 2 OPTIMISASI KOMBINATORIAL
14
2.1 Masalah Model Optimisasi Kombinatorial
14
2.2 Beberapa Masalah Optimisasi Kombinatorial
16
2.2.1 Himpunan stabil dan bilangan stabil
16
2.3 Hubungan Masalah Kombinatorial dengan Optimisasi Kombinatorial
18
2.4 Jaminan Nullstellensatz dan Optimisasi Kombinatorial
19
ix
2.5 Definisi dan Notasi
20
BAB 3 KRITERIA KEOPTIMALAN DARI MASALAH OPTIMISASI POLINOMIAL 22 3.1 Eksistensi Optimisasi Polinomial
22
3.2 Pengali Lagrange
25
3.3 Syarat Keoptimalan KARUSH-KUHN-TUCKER
25
3.4 Kekonvekan
27
3.5 Pendekatan Optimisasi Berkendala
28
3.5.1 Metode dasar
30
3.5.2 Variabel superbasic
32
3.5.3 Metode derivatif
34
3.5.4 Arah pencarian
37
3.5.5 Implementasi
39
3.5.6 Ringkasan prosedur
39
BAB 4 POLINOMIAL KOMBINATORIK
44
4.1 Definisi dan Notasi
44
4.2 Kekonvekan pada Bilangan Bulat
47
BAB 5 EKSISTENSI NILAI OPTIMUM POLINOMIAL KOMBINATORIK 52 5.1 Masalah Polinomial Kombinatorik
53
5.2 Himpunan Layak (Polihedra)
54
5.3 Eksistensi (keberadaan) Nilai Optimum
59
BAB 6 KESIMPULAN DAN PENELITIAN LANJUTAN
61
6.1 Kesimpulan
61
6.2 Penelitian Lanjutan
62
DAFTAR PUSTAKA
63 x
DAFTAR TABEL
Nomor
Judul
Halaman
1.1 Kompleksitas komputasi dengan dimensi fix
xi
10
DAFTAR GAMBAR
Nomor 3.1
Judul
Masalah partisi pada konstrain dan konsep variabel super basic
xii
Halaman 33
BAB 1 PENDAHULUAN
1.1 Latar Belakang Suatu persoalan optimisasi dimulai dengan himpunan variabel bebas atau parameter, dan acapkali mencakup kondisi atau pembatasan terhadap nilai terterima dari variabel. Pembatasan demikian diistilahkan kendala dari persoalan. Komponen penting lainnya dari persoalan optimisasi adalah yang disebut fungsi objektif atau fungsi tujuan, yang tergantung pada variabel-variabel persoalan. Penyelesaian dari persoalan optimisasi adalah himpunan dari nilai-nilai variabel yang memenuhi kendala, sedemikian hingga fungsi objektif mencapai nilai optimal. Bentuk baku secara matematika yang representatif dalam mengungkapkan persoalan optimisasi dan untuk menyelesaikan persoalan adalah,
Maksimum
f (X)
dengan Kendala gi (X) = 0,
i =, 2, · · · , m (1.1)
gi (X) 6 0,
i = m + 1, m + 2, · · · , n
X = (x1, x2 , · · · xd ) Fungsi objektif f dan fungsi kendala gi merupakan fungsi bernilai real, X adalah vektor berdimensi d, yakni xi bernilai real untuk setiap i.
1
2 Bentuk (1) diatas menyatakan : tentukan nilai demikian untuk larik variabel keputusan X, sehingga fungsi f (X) dimaksimumkan dan fungsi kendala dipenuhi. Bentuk (1) disebut sebagai model program matematika. Dari uraian terdahulu, jelas bahwa untuk menyelesaikan persoalan optimisasi, perlu dihasilkan suatu model. Seringkali dalam pemakaian, variabel keputusan X dipersyaratkan memiliki batas bawah l dan batas atas u dengan l > 0 dan u > 0 agar nilai variabel keputusan X diharapkan tidak mengambil nilai 0. Dengan adanya persyaratan tersebut, model (1) sekarang ditambah dalam kendala dengan l ≤ X ≤ u. Ada masalah optimisasi yang variabel keputusannya dibatasi oleh bilangan bulat (integer) atau biner, masalah optimisasi ini disebut optimisasi kombinatorial. Persoalan optimisasi kombinatorial ini berasal masalah kombinatorial. Masalah kombinatorial adalah suatu masalah yang berhubungan dengan menghitung (counting), sehingga penyelesaian masalah optimisasi kombinatorial adalah bilangan bulat. Dengan bertambahnya persyaratan tersebut, model program matematika dari optimisasi kombinatorial adalah model (1) ditambah syarat pada kendala, yakni X = (x1, x2 , · · · , xd ), xi bilangan bulat untuk setiap i. Masalah optimisasi kombinatorial dapat diformulasikan dalam bentuk graph dan dalam bentuk program matematika. Suatu masalah optimisasi kombinatorial dalam graph yang mempunyai banyak aplikasi dan telah banyak diteliti secara intensif adalah masalah pewarnaan graph ( Murty, 2003). Masalah pewar-
3 naan graph dari suatu graph G = (V, E), adalah persoalan mencari minimum banyaknya warna yang dapat diberikan pada setiap titik pada himpunan V dengan setiap titik diberi satu warna, dengan kendala untuk setiap edge (i, j) ∈ E, warna yang digunakan untuk verteks i dan verteks j harus berbeda, permasalahan ini merupakan masalah optimisasi kombinatorial. Suatu graph G adalah suatu network (V, E) dengan V adalah himpunan berhingga titik-titik (verteks ) dan E adalah himpunan garis (edge), setiap edge merupakan pasangan berbeda dari titik-ttik. Jika V mempunyai n titik maka biasanya setiap titik diberi label, 1, 2, · · · , n. Garis yang menghubungkan titik i dan j dinotasikan dengan (i, j). Titik i dan j disebut bertetangga (adjacent) pada graph jika ada garis yang menghubungkan titik i dan titik j. Optimisasi kombinatorial dari masalah pewarnaan graph dapat direpresentasikan sebagai program matematika. Pada suatu graph dengan n buah titik, masalah pencarian warna menggunakan variabel keputusan bilangan bulat antara 1 dan n dan tidak pernah lebih besar dari n. Masalah pewarnaan graph, banyak aplikasinya pada masalah sehari-hari nyata, misalnya:
1. Masalah pembuatan jadwal pertemuan, dengan masalah pencarian minimum banyaknya slots waktu yng diperlukan untk penjadwalan semua pertemuan tanpa terjadi konflik.
4 2. Masalah pemberian warna pada pembuatan peta dunia, dengan semua negara harus diberi warna tetapi negara yang bertetangga tidak diperbolehkan mempunyai warna sama. Masalahnya adalah berapa minimum banyaknya warna yang digunaka pada pembuatan sebuah peta.
Lovast (1994), merepresentasikan masalah optimisasi kombinatorial dari masalah pencarian minimal banyaknya warna pada suatu graph G(V, E) dengan n buah titik, dengan mendefinisikan suatu variabel keputusan xi untuk i = 1 sampai dengan n, xi = bilangan untuk warna yang digunakan pada titik i. diperoleh program matematika dengan fungsi objektif f adalah fungsi linear, fungsi kendala gi merupakan polinomial, dan k adalah bilangan bulat positif, sebagai berikut: Miminimumkan k Kendala xki − 1 = 0 untuk setiap vertex i ∈ V (G) xj + xk−1 = 0 untuk setiap edge {i, j} ∈ E (G) xki + xk−2 i j 16i6n Aplikasi lain dari masalah optimisasi kombinatorial graph, misalnya masalah pemilihan kerja (job assignment problem), dapat diformulasikan sebagai program matematika, dengan fungsi objektif f dan fungsi kendala gi merupakan fungsi linear berharga bilangan bulat (integer).
5 Misalkan T adalah variabel waktu ketika semua pekerjaan telah dilakukan, bentuk program matematika (2) nya adalah: minimumkan T Kendala
X
xij = ti,
(i ∈ {1, 2, . . . n})
j∈Si
(1.2)
xij > 0 X
xij = ti ,
(i ∈ {1, 2, . . . n} , j ∈ Si ) (j ∈ {1, 2, . . . m})
j∈Si
Bilangan ti dan himpunan Si diberikan, variabel xij dan T akan dicari. Untuk setiap pekerjaan i dan untuk pekerja j adalah verteks, dan jika pekerja j mendapat pekerjaan i diwakili oleh edge {i, j}. Pada pemakaiannya, masalah optimisasi kombinatorial yang telah diuraikan sebelumnya, diperoleh bahwa optimisasi kombinatorial dapat direpresentasikan dalam bentuk program matematika, dan mempunyai beberapa kemungkinan yang terjadi pada fungsi tujuan dan fungsi kendala, yakni:
1. Fungsi tujuan adalah linear dan kendala juga fungsi linear. 2. Fungsi tujuan adalah linear dan kendala polinomial. 3. Fungsi tujuan adalah polinomial dan kendala fungsi linear. 4. Fungsi tujuan adalah polinomial dan kendala juga polinomial,
dengan variabel keputusan yang diperbolehkan adalah diskrit, yakni bilangan bulat atau biner.
6 Pada penelitian ini, yang akan dikaji adalah masalah optimisasi kombinatorial yang program matematikanya khusus mempunyai fungsi tujuan dan kendala berbentuk polinomial, dan untuk selanjutnya disebut polinomial kombinatorik. Bentuk umum dari polinomial kombinatorik adalah: Maksimumkan
f (X)
gi (X) = 0,
i = 1, 2, · · · , m (1.3)
gi (X) 6 0,
i = m + 1, m + 2, · · · , n
l6X 6u dengan f, gi ∈ Z[x] dan X ∈ Z d dan Z d = {(a1, · · · , ad )|a1, · · · , ad ∈ Z} Z[x] adalah himpunan semua polinomial dengan koefisien integer. Lorea et. al., (2008) memperlihatkan penyelesaian masalah optimisasi kombinatorial suatu graph berdasarkan keberadaan penyelesaian dari polinomial kombinatoriknya. Telah dibuktikan bahwa masalah kombinatorial mempunyai penyelesaian jika dan hanya jika polinomial kombinatoriknya mempunyai penyelesaian. Dari uraian diatas, diperoleh bahwa betapa pentingnya perlu diketahui suatu polinomial kombinatorik mempunyai penyelesaian, tetapi sampai dengan saat ini belum ada yang menjamin bahwa suatu polinomial kombinatorik mempunyai penyelesaian. Tetapi untuk menentukan bahwa polinomial kombinatorik tidak mempunyai penyelesaian sudah ada jaminannya yang disebut jaminan Nullstelensatz (Alon,1999). Oleh karena ini perlu dikaji apa yang menjamin agar suatu polinomial kombinatorik mempunyai penyelesaian.
7 Sebelum dilakukan penelitian pencarian syarat keoptimalan (syarat yang harus diberikan agar suatu polinomial kombinatorik (3) mempunyai penyelesaian (terselesaikan). Perlu dikaji beberapa kasus yang sudah diteliti oleh penelitipeneliti sebelumnya. Suatu model (3) mempunyai penyelesaian (terselesaikan) adalah diperolehnya himpunan variabel keputusan (titik bilangan bulat) yang memenuhi semua kendala yang disebut himpunnan layak atau polihedra (P := {x ∈ Z n |gi (x) ≤ 0}) bukan merupakan himpunan kosong, sedemikian hingga fungsi tujuan f mencapai nilai optimum. Ada dua kemungkinan yang terjadi ketika masalah polinomial kombinatorik tidak mempunyai penyelesaian, yaitu misalnya ketika masalahnya infeasible atau polihedranya merupakan himpunan kosong P := {x ∈ Z n |gi (x) 6 0} = ∅) dan f tak terbatas (untuk semua α ∈ Z ada x ∈ P dengan f (x) < α). Polinomial kombinatorik melibatkan sistem pertidaksamaan polinomial dan sekumpulan bilangan bulat, maka perlu analisa lebih lanjut untuk mengidentifikasikan keberadaan titik optimum (penyelesaian). Dalam kasus ini diperlukan penelitian terdahulu tentang asumsi dan metode yang sudah digunakan, pertama pada program matematika dengan fungsi tujuan dan kendala berbentuk polinomial tetapi variable keputusan bilangan real. Untuk fungsi tujuan dan kendala berbentuk polinomial dengan variabel keputusan bilangan real sudah ditemukan syarat agar masalah optimisasi nya mempunyai penyelesaian (Bazarra et al 1993), berdasarkan pernyataan berikut:
8
Misalkan (X, kk) adalah ruang norm riil S ⊆ X tak kosong, fungsi f : S → Z. Jika S adalah himpunan kompak barisan lemah dan fungsi f semi kontinu bawah lemah, maka ada paling sedikit satu x∗ ∈ S dengan f (x∗ ) ≤ f (x), untuk semua x ∈ S, sehingga masalah optimisasi min f (x) mempunyai paling sedikit satu x x∈S
penyelesaian. Setelah ada jaminan bahwa masalah optimisasi mempunyai penyelesaian, maka penelitian selanjutnya mencari syarat perlu dan syarat cukup untuk mendapatkan nilai optimum. Syarat perlu bahwa f (x) mempunyai relative minimum di x = x∗ , adalah f (x) harus terdefinisi pada suatu interval [a, b] untuk a < x∗ < b dan jika turunan f (x) atau 5f (f multivariabel) ada pada x = x∗ , maka f (x∗ ) = 0 atau 5f (x∗ ) = 0
0. Syarat cukup untuk nilai minimum (lokal atau global) dari f (x) jika f (x) = 00
0, f (x) = 0, sampai dengan f (n−1) (x) = 0. dan f (n) (x) > 0, untuk n genap, atau matriks Hess pada x = x∗ adalah definit positif. Karena f adalah polinomial maka nilai maksimum f (x) (jika ada) pada polihedranya adalah tidak tunggal, yaitu ada yang merupakan maksimum lokal dan ada yang merupakan maksimum global (nilai optimal), sehingga harus ada yang menjamin bahwa nilai maksimum lokal merupakan nilai maksimum global, yaitu jika fungsi f : S → R pada S ⊆ X dengan asumsi S subset konveks dan f juga fungsi konveks maka maksimum lokal merupakan maksimum global.
9 Untuk masalah optimisasi dengan fungsi tujuan f : Zn → Z linear dan kendala linear maka nilai minimum nya dijamin ada, jika polihedranya adalah kompak dan konveks, selanjutnya untuk pencarian penyelesaian bilangan bulat, masalah pencarian nilai optimalnya menggunakan metode branch and bound, metode cutting plane dan relaksasi Lagrangian. Pada prosedur relaksasi membutuhkan pengulangan lebih dari n kali (n adalah banyaknya variable), sebelum penyelesaiannya diperoleh.( Lovasz dan Schrijver, 1991). Untuk fungsi tujuan berbentuk polinomial dan kendala berbentuk linear, Lorea, et al (2006) menyajikan kompleksitas dari beberapa masalah untuk pencarian penyelesaian bilangan bulat dari masalah polinomial kombinatorik multi variable dengan program matematikanya, Fungsi tujuan, memaksimumkan f ∈ Z[x1, ..., xd] Kendala Ax 6 b dengan polihedra P = {x|Ax 6 b}, adalah matriks berukuran n × d dengan n, d ∈ Z+ dan x vektor berukuran d × 1 sehingga b vektor berukuran n × d. Algoritma yang disajikan adalah membangun batas atas dan batas bawah untuk mendapatkan nilai optimum global bilangan bulat dari masalah. Memaksimumkan f ∈ Z[x1, ..., xd] pada (x1, ..., xd) ∈ P ∩ Zd Awalnya dilakukan untuk f polinomial berderajat empat dan semua kendala linear(polinomial berderajat satu dengan sepuluh variabel, ternyata tidak
10 diperoleh penyelesaiannya. Tetapi dengan dua variable diperoleh penyelesaiannya. Adapun hasil penelitiannya disajikan pada tabel kompleksitas dari masalah polinomial kombinatorik dengan beberapa kasus optimisasi pada table 1 berikut: Tabel 1.1
Kompleksitas komputasi dengan dimensi fix
Tipe kendala Linear Konveks semi aljabar Polinomial
Linear Polytime Polytime Undecidable
Tipe fungsi tujuan Polinomial konveks Polytime Polytime Undecidable
Polinomial NP-hard NP-hard Undecidable
Sumber : Jurnal Mathematics of Operations Research (2006)
Michael dan Weismantel, R (2010) telah membahas masalah daerah layak atau polihedra suatu polinomial kombinatorik, khusus dengan fungsi tujuan linear dan kendala sebarang polinomial dengan koefisien bilangan bulat. Beliau juga mendefinisikan masalah kekonvekan suatu fungsi pada bilangan bulat, sebagai perluasan dari definisi kekonvekan pada fungsi kontinu di R, juga mengkaji sifatsifat dari polihedra yang diperoleh. Dari uraian hasil penelitian para peneliti terdahulu, diperoleh suatu masalah yaitu setelah masalah optimisasi kombinatorial direpresentasikan sebagai program matematika yang berbentuk polinomial kombinatorik, dengan bentuk umum polinomial kombinatorik ( 3). Permasalahannya adalah : Syarat apakah yang harus diberikan agar polinomial kombinatorik (3) mempunyai penyelesaian ? .
1. Apakah dengan memberi batasan pada variabel keputusan dan syarat pada fungsi kendala agar diperoeh himpunan layak (polihedra)? . 2. Apakah syarat agar terdapat unsur bilangan bulat di polihedra yang menghasilkan nilai optimum fungsi objektif ?.
11 1.2 Tujuan penelitian Tujuan penelitian ini adalah menentukan syarat agar polinomial kombinatorik (·) mempunyai penyelesaian.
1.3
Manfaat Penelitian Karena ada masalah kombinatorial dalam kehidupan nyata yang model
matematikanya berbentuk polinomial kombinatorik, maka manfaat dari penelitian ini adalah :
1. Dapat digunakan untuk menentukan penyelesaian dari masalah kombinatorial yang diperoleh berdasarkan pada penyelesaian polinomial kombinatoriknya. 2. Penelitian ini dapat memberikan teori dan teorema baru tentang kondisi keoptimalan dari suatu pemrograman matematika yang disebut Polinomial Kombinatorik. 3. Dengan ditemukan syarat agar polinomial kombinatorik mempunyai penyelesaian (terselesaikan) maka dapat dilanjutkan untuk menentukan metode apa yang sesuai untuk pencarian penyelesaian nya. 4. Dapat diterapkan untuk menyelesaikan masalah hampiran (aproksimasi) atau menemukan algoritma yang efisien dalam mencari nilai optimal dari beberapa masalah kombinatorial yang modelnya berbentuk polinomial kombinatorik
12 1.4
Metodologi Penelitian Langkah-langkah yang dilakukan untuk menentukan syarat agar polinomial
kombinatorik mempunyai penyelesaian adalah sebagai berikut,
1. Mengkaji masalah polinomial kombinatorik yang mempunyai satu atau dua variabel, karena masalah ini masih dapat direpresentasikan dengan grafik. Mengkaji karakteristik atau situasi apa saja yang terjadi tentang kendala yang berbentuk polinomial, karena dengan kendala berbentuk polinomial akan mempengaruhi keberadaan nilai optimum dari fungsi tujuan yang juga polinomial. Karena fungsi tujuan polinomial mempunyai beberapa lintasan yang mungkin dilalui, yang disebut kountur, atau dapat mempunyai lebih dari satu titik ekstrim, sehingga keberadaan penyelesaiannya yang bergantung pada pengaruh kendala terhadap fungsi objektif perlu dianalisa. Dalam masalah ini diselidiki kemungkinan-kemungkinan yang terjadi tentang kountur dan titik ekstrim dari fungsi objektif himpunan layaknya (polihedra). 2. Melakukan pengkajian tentang polihedra masalah polinomial kombinatorik (·) dengan satu variabel dan dua variabel dan hubungan nya dengan fungsi tujuannya, yakni dengan mengkaji model, Fungsi Objektif Memaksimumkan f (X) kendala
gi (X) 6 0 i = 1, 2, ..., m (1.4) l 6 x 6 u, l, u > 0
l, u dan x ∈ Z
13 dengan f, g ∈ Z[x], selanjutnya membandingkan dengan jika f, g ∈ R[x]. 3. Mengkaji secara umum sifat-sifat polihedra masalah (1) di Zn 4. Pembuktian secara aljabar untuk memperlihatkan bahwa dengan pemberian beberapa syarat maka Polinomial Kombinatorik mempunyai penyelesaian (terselesaikan).
