1
I PENDAHULUAN 1.1 Latar Belakang Sepak bola merupakan olahraga yang populer di seluruh dunia termasuk di Indonesia. Sepak bola sebenarnya memiliki perangkat-perangkat penting yang harus ada dalam penyelenggaraannya, salah satunya adalah jadwal pertandingan. Penyusunan jadwal pertandingan harus dilakukan dengan hati-hati dan penuh pertimbangan agar pertandingan sepak bola dapat berjalan lancar. Permasalahan ini harus segera diatasi, tentunya ada banyak cara yang bisa dilakukan. Salah satunya adalah dengan memodelkan masalah penjadwalan pertandingan sepak bola sebagai suatu masalah Integer Linear Programming (ILP). ILP adalah masalah optimisasi dengan fungsi objektif dan kendala
yang linear serta variabel integer (bilangan bulat). Pada karya ilmiah yang menjadi literatur utama tulisan ini, yaitu ”Scheduling a Major College Basketball Conference” yang ditulis oleh George L. Nemhauser dan Michael A. Trick, dibahas pemodelan masalah penjadwalan pertandingan dengan ILP dan menggunakan bantuan software CPLEX 4.0 untuk menyelesaikannya. 1.2 Tujuan Tulisan ini bertujuan memodelkan dan menyelesaikan masalah penjadwalan pertandingan melalui ILP. Sebagai studi kasus diselesaikan masalah penjadwalan pertandingan sepak bola babak kualifikasi Piala Eropa 2008 Grup B.
II LANDASAN TEORI 2.1 Pemrograman Linear Definisi 1 (Fungsi Linear) f ( x1 , x 2 ,..., x n ) menyatakan Misalkan suatu fungsi dalam variabel-variabel x1 , x 2 ,..., x n . f ( x1 , x 2 ,..., x n ) adalah suatu fungsi linear jika dan hanya jika untuk himpunan konstanta c1 , c 2 ,..., c n , f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . [Winston, 1995] Sebagai gambaran, f ( x1 , x 2 ) = 2 x1 + x 2 merupakan fungsi linear, sementara f ( x1 , x 2 ) = x12 x 2 bukan fungsi linear. Suatu persamaan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear, apabila f fungsi linear. Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b, pertidaksamaan f ( x1 , x 2 ,..., x n ) ≤ b dan f ( x1 , x 2 ,..., x n ) ≥ b dikatakan pertidaksamaan linear. [Winston, 1995] Menurut Winston (1995), Pemrograman Linear (PL) adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan sebagai berikut.
a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi linear yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Variabel keputusan harus taknegatif ( xi ≥ 0) atau tidak dibatasi tandanya. Suatu PL dikatakan memiliki bentuk standar seperti yang didefinisikan sebagai berikut: Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar: minimumkan z = cT x terhadap Ax = b x≥0 ...(1) dengan x dan c merupakan vektor berukuran n, vektor b berukuran m, sedangkan A merupakan matriks berukuran m x n. Matriks A disebut matriks kendala. [Nash & Sofer, 1996] Definisi 4 (Solusi Optimum) Solusi optimum (terbaik) adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terkecil (dalam masalah minimisasi). Untuk masalah maksimisasi,
2
solusi optimum suatu PL adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terbesar. [Winston, 1995] 2.1.1 Solusi PL Untuk menyelesaikan suatu masalah PL, metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig pada tahun 1947. Dalam perkembangannya, metode ini adalah metode yang umum digunakan untuk menyelesaikan masalah PL, yaitu berupa metode iteratif (proses mencari solusi yang dilakukan berulang-ulang hingga didapatkan hasil yang diinginkan) untuk menyelesaikan masalah PL berbentuk standar. Pada PL (1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi dari PL (1). Misalkan matriks A dapat dinyatakan sebagai A = ( B N ) , dengan B merupakan matriks berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk PL (1). Misalkan x dapat dinyatakan sebagai ⎛x ⎞ vektor x = ⎜ B ⎟ dengan xB adalah vektor ⎝ xN ⎠ variabel basis dan x N adalah vektor variabel nonbasis, maka Ax = b ⎛x ⎞ Ax = ( B N ) ⎜ B ⎟ ⎝ xN ⎠ = Bx B + Nx N = b …(2) Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai xB = B -1b - B -1 Nx N …(3)
Definisi 5 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika: i. solusi tersebut memenuhi kendala PL; ii. kolom-kolom dari matriks koefisien yang berpadanan dengan komponen taknol adalah bebas linear. [Nash & Sofer, 1996] Definisi 6 (Solusi Fisibel Basis) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan x ≥ 0. [Nash & Sofer, 1996]
Ilustrasi solusi basis dan solusi fisibel basis dapat dilihat dalam contoh berikut:
Contoh 1 Misalkan diberikan pemrograman linear berikut: minimumkan z = −2 x1 − 3 x2 terhadap: −2 x1 + x2 + x3 = 4 − x1 + 2 x2 + x4 = 11 x1 + x5 = 5 x1 , x2 , x3 , x4 , x5 ≥ 0 …(4) Dari PL tersebut didapatkan: ⎛ −2 1 1 0 0 ⎞ ⎛4⎞ ⎜ ⎟ ⎜ ⎟ A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜11⎟ ⎜ 1 0 0 0 1⎟ ⎜5⎟ ⎝ ⎠ ⎝ ⎠ Misalkan dipilih xB
=
( x3
x4
x5 ) dan x N T
=
( x1
x2 )
T
maka matriks basisnya adalah ⎛1 0 0⎞ B = ⎜⎜ 0 1 0 ⎟⎟ ⎜0 0 1⎟ ⎝ ⎠ Dengan menggunakan matriks basis tersebut, diperoleh xN = ( 0 0)
T
xB = B -1b = ( 4 11 5 )
T
…(5)
Solusi (5) merupakan solusi basis, karena memenuhi kendala pada PL (4) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol.
2.2 Integer Linear Programming Model Integer Linear Programming (ILP) atau disebut juga Integer Programming (IP), adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa bilangan bulat, maka masalah tersebut disebut pure integer programming. Jika hanya sebagian yang harus berupa bilangan bulat, maka disebut mixed integer programming. Jika model tersebut hanya mengharuskan nilai nol atau satu untuk variabelnya, dinamakan zero-one integer programming. [Garfinkel & Nemhauser, 1972]
3
Definisi 7 (Pemrograman Linear Relaksasi) PL-Relaksasi merupakan pemrograman linear yang diperoleh dari suatu IP dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada setiap variabelnya. Untuk masalah meminimumkan, nilai fungsi objektif yang optimum di PL-relaksasi lebih kecil atau sama dengan nilai fungsi objektif yang optimum di IP, sedangkan untuk masalah memaksimumkan nilai fungsi objektif yang optimum di PL-relaksasi lebih besar atau sama dengan nilai fungsi objektif yang optimum di IP. [Winston, 1995] 2.3 Metode Branch and Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimum dari masalah IP digunakan software LINGO 8.0 yaitu sebuah program yang didesain untuk aplikasi riset operasi dalam membangun dan menentukan solusi model linear, nonlinear, dan optimisasi integer dengan prinsip pemecahannya berdasarkan metode branch and bound. Keunggulan metode ini terletak pada tingkat efektifitasnya dalam memecahkan masalah dengan hasil yang akurat. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah PL-relaksasi dengan membuat subproblemsubproblem. Daerah fisibel pemrograman linear adalah daerah yang memenuhi semua kendala pemrograman linear. Ö
Branch Membuat partisi daerah solusi dari masalah PL-relaksaasi ke dalam subproblem. Tujuannya untuk menghapus daerah solusi yang takfisibel. Hal ini dicapai dengan menentukan kendala yang penting untuk menghasilkan solusi IP, secara tidak langsung titik integer yang takfisibel terhapus. Dengan kata lain, hasil pengumpulan lengkap dari subproblem-subproblem ini menunjukkan setiap titik integer yang fisibel dalam masalah asli. Proses ini dinamakan branching.
Aspek kunci dari metode branch and bound adalah sebagai berikut. Langkah 1: Periksa apakah IP memenuhi kondisi berikut. 1) Subproblem takfisibel. 2) Subproblem menghasilkan solusi optimum dengan semua variabel bernilai integer. 3) Nilai optimum (nilai efektif yang dapat dicapai) untuk subproblem lebih kecil dari (dalam masalah memaksimumkan) batas bawah (lower bound). Jika ketiga kondisi tersebut terpenuhi maka cabang subproblem tidak diperlukan. Langkah 2: Sebuah subproblem mungkin dapat dihapuskan dari pertimbangan dengan kondisi sebagai berikut. 1) Subproblem takfisibel. 2) Batas bawah (yang menunjukkan nilai optimum dari kandidat terbaik) setidaknya lebih besar dari nilai optimum (nilai efektif yang dapat dicapai) subproblem. [Winston, 1995] Contoh 2 Misalkan diberikan pemrograman integer (IP) sebagai berikut: maksimumkan z = 5 x1 + 4 x2 terhadap: x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer Daerah fisibel untuk masalah IP tersebut diperlihatkan oleh titik-titik pada Gambar 1, sedangkan daerah yang diarsir pada Gambar 1 merupakan daerah fisibel untuk PL-relaksasi.
Solusi Optimum Subproblem 1
x1 = 3.75 x2 =1.25
Ö
Bound Misalkan masalah tersebut diasumsikan merupakan tipe maksimisasi, nilai objektif yang optimum untuk setiap subproblem dibuat dengan membatasi pencabangan dengan batas atas dari nilai objektif yang dihubungkan dengan sembarang nilai integer yang fisibel. Hal ini sangat penting untuk mengatur dan menempatkan solusi optimum. Operasi ini yang menjadi alasan dinamakan bounding. [Taha, 1975]
Gambar 1 Daerah Fisibel IP dan PL-relaksasi. PL-relaksasi dari IP pada Contoh 2 (selanjutnya disebut Subproblem 1) diselesaikan dengan menggunakan software LINDO 6.1 dan diperoleh solusi optimum x1 = 3.75, x2 = 1.25, dan z = 23.75 (lihat Lampiran 1 bagian Subproblem 1). Solusi tersebut tidak memenuhi kendala integer. Oleh karena itu,
4
harus dibuat subproblem baru dengan memilih variabel yang tidak memenuhi kendala bilangan bulat. Misalkan dipilih x1 = 3.75 secara sembarang. Diketahui bahwa daerah (3 ≤ x1 ≤ 4) dari daerah fisibel Subproblem 1 tidak akan memuat solusi IP yang fisibel karena tidak memenuhi kendala integer (bilangan bulat), maka dibuat subproblem baru yakni: • Subproblem 2: Subproblem 1 ditambah kendala x1 ≤ 3; • Subproblem 3: Subproblem 1 ditambah kendala x1 ≥ 4. Daerah fisibel untuk Subproblem 2 dan Subproblem 3 diberikan pada gambar berikut:
Gambar 2 Daerah Fisibel untuk Subproblem 2 dan Subproblem 3. Sekarang akan diselesaikan Subproblem 2 dan Subproblem 3 satu per satu. Misalkan Subproblem 2 dipilih pertama kali untuk diselesaikan, yaitu: maksimumkan z = 5 x1 + 4 x2 terhadap: x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≤ 3 x1 , x2 ≥ 0 Dengan menyelesaikan Subproblem 2 tersebut diperoleh solusi x1 = 3, x2 = 2, dan z = 23 (lihat Lampiran 1 bagian Subproblem 2). Semua variabel bernilai bilangan bulat (solusinya memenuhi kendala bilangan bulat), maka tidak perlu dilakukan pencabangan di Subproblem 2. Persamaan ini dijadikan kandidat solusi bagi masalah IP. Sekarang akan dipecahkan Subproblem 3, yaitu: maksimumkan z = 5 x1 + 4 x2 terhadap: x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≥ 4
x1 , x2 ≥ 0 Setiap titik (solusi) fisibel dari IP pada Contoh 2 termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dicabangkan oleh x1 . Sekarang dipilih subproblem yang belum diselesaikan, yaitu Subproblem 3, kemudian diselesaikan sehingga diperoleh solusi optimum untuk Subproblem 3 ini adalah x1 = 4, x2 = 0.8333, dan z = 23.3333 (lihat Lampiran 1 bagian Subproblem 3). Karena nilai fungsi objektif yang diperoleh dari Subproblem 1 lebih baik (lebih besar) dari pada nilai fungsi objektif yang diperoleh dari Subproblem 2, maka batas bawah bagi masalah ini adalah z = 23.75. Karena solusi optimum Subproblem 3 bukan solusi integer, maka dipilih pencabangan pada Subproblem 3 atas x2 , sehingga diperoleh dua subproblem lagi, yakni: • Subproblem 4: Subproblem 3 ditambah kendala x2 ≤ 0; • Subproblem 5: Subproblem 3 ditambah kendala x2 ≥ 1. Sekarang dipilih subproblem yang belum diselesaikan yaitu Subproblem 4 atau Subproblem 5. Subproblem 5 takfisibel (lihat Lampiran 1 bagian Subproblem 5) karena tidak memiliki solusi fisibel, maka subproblem ini tidak dapat menghasilkan solusi optimum. Solusi optimum untuk Subproblem 4 adalah x1 = 4.5, x2 = 0, dan z = 22.5 (lihat Lampiran 1 bagian Subproblem 4). Batas bawah bagi masalah ini adalah z = 23.75, karena nilai dari masalah ini lebih baik daripada nilai objektif yang diperoleh dari Subproblem 4. Penyelesaian Subproblem 2 menghasilkan solusi optimum x1 = 3, x2 = 2, z = 23. Nilai objektif dari Subproblem 4 tidak lebih baik dari nilai objektif yang dihasilkan oleh Subproblem 2. Dengan demikian, nilai solusi optimum Subproblem 2, yakni z = 23 menjadi batas bawah yang baru. Solusi optimum dari Subproblem 2 merupakan solusi optimum IP pada Contoh 2, yakni x1 = 3, x2 = 2, dan z = 23. Subproblem untuk permasalahan IP tersebut diberikan pada Gambar 3 mengenai pencabangan untuk menentukan solusi IP. Tanda (*) menyatakan kandidat solusi optimum untuk masalah IP tersebut.
5
Subproblem 1 x1 = 3.75; x2 = 1.25 dan z = 23.75 x1 ≤ 4
x1 ≥ 5
Subproblem 2*
Subproblem 3 x1 = 4; x2 = 0.8333 dan z = 23.3333 x2 ≥ 1
x1 = 3; x2 = 2 dan z = 23
x2 ≤ 0
Subproblem 5
Subproblem 4
Solusi takfisibel
x1 = 4.5; x2 = 0 dan z = 22.5
Gambar 3 Pencabangan yang dilakukan metode branch and bound untuk menentukan solusi IP.
III PEMODELAN 3.1 Model Penjadwalan Pertandingan dengan Sistem Round-Robin Model penjadwalan pertandingan sepak bola dibangun dari pendeskripsian masalah secara jelas. Masalah penjadwalan tersebut diformulasikan dalam bentuk ILP yang dapat diselesaikan dengan metode-metode yang ada. Dalam karya ilmiah ini, penjadwalan pertandingan menggunakan sistem roundrobin (setiap tim bertanding dengan semua tim peserta satu kali untuk setengah kompetisi). Sebuah pola terdiri atas H (home), A (away), dan B (bye) yang bersesuaian dengan periode waktu k. Misalkan T adalah banyaknya tim peserta, M adalah banyaknya pertandingan untuk setengah kompetisi, dan N adalah banyaknya pertandingan untuk satu periode waktu, maka diperoleh ⎛T ⎞ M = T C2 = ⎜ ⎟ , ⎝2⎠ ⎧T ⎪ N = ⎨2 ⎪0 ⎩
;
jika T genap
;
jika T ganjil.
Selanjutnya akan ditentukan banyaknya periode waktu k untuk setengah kompetisi, yaitu:
• T genap ⎛T ⎞ ⎜ ⎟ M ⎝2⎠ T! 2 k= = = ⋅ = T −1 T N (T − 2 )!2! T 2 • T ganjil ⎛T ⎞ ⎜ ⎟ 2 M T! 2 k= = ⎝ ⎠ = ⋅ =T T 1 − N (T − 2 )!2! T − 1 2 Dengan demikian banyaknya periode waktu k adalah ⎪⎧T −1 ; k =⎨ ; ⎪⎩T
jika T genap jika T ganjil.
Sebagai contoh, dalam pertandingan yang diikuti empat tim diperoleh 4! M = 4 C2 = = 6, (4 − 2)!2! N=
4 = 2, 2
dan
k = 4 − 1 = 3. Misalkan pola dipilih dari kombinasi H dan A saja. Akan ditentukan pola pertandingan selama setengah kompetisi yang berlangsung selama 3 minggu terlebih dahulu,
