PENYELESAIAN MASALAH PENJADWALAN PERTANDINGAN SEPAK BOLA DENGAN SISTEM ROUND-ROBIN ABDILLAH

PENYELESAIAN MASALAH PENJADWALAN PERTANDINGAN SEPAK BOLA DENGAN SISTEM ROUND-ROBIN

ABDILLAH

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008

PENYELESAIAN MASALAH PENJADWALAN PERTANDINGAN SEPAK BOLA DENGAN SISTEM ROUND-ROBIN

ABDILLAH G54103026

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008

ABSTRAK ABDILLAH. Penyelesaian Masalah Penjadwalan Pertandingan Sepak Bola dengan Sistem Round-Robin. Dibimbing oleh FARIDA HANUM dan TONI BAKHTIAR. Masalah penjadwalan pertandingan sepak bola dapat diselesaikan dengan beberapa cara. Salah satu caranya adalah dengan memodelkan masalah penjadwalan pertandingan sebagai suatu masalah Integer Linear Programming (ILP). ILP adalah masalah optimisasi dengan fungsi objektif dan kendala yang linear serta variabel integer (bilangan bulat). Solusi optimum dari masalah ILP diperoleh dengan bantuan software LINGO 8.0 yang prinsip pemecahannya berdasarkan metode branch and bound. Pada tulisan ini dipelajari pemodelan masalah penjadwalan pertandingan sepak bola dengan sistem round-robin. Sistem ini mengharuskan setiap tim bertanding dengan semua tim peserta lain satu kali untuk setengah kompetisi. Masalah tersebut kemudian diterapkan dalam penjadwalan pertandingan sepak bola babak kualifikasi Piala Eropa 2008 Grup B. Ada tiga langkah untuk menyelesaikan permasalahan tersebut, langkah pertama yaitu penentuan pola pertandingan yang terdiri atas home, away, dan bye. Selanjutnya pada langkah kedua ditentukan tabel pertandingan, sedangkan langkah ketiga merupakan perpaduan dari langkah pertama dan langkah kedua yang menghasilkan jadwal pertandingan.

ABSTRACT ABDILLAH. Solving the Football Game Scheduling Problem by Round-Robin System. Under the direction of FARIDA HANUM and TONI BAKHTIAR. The football game scheduling problem can be solved by means of many ways. One of them is by modelling the problem as an Integer Linear Programming (ILP) problem. ILP is an optimization problem which has linear objective functions, linear constraints and integer-valued variables. Optimum solution of ILP problem can be obtained by using LINGO 8.0, on which the branch and bound method is applied. In this paper we studied the modelling of football game scheduling problem with round-robin system. This system arranges each team met other teams once for half competition. We applied our model for match scheduling in the qualification round of Euro Cup 2008 Group B. There were three steps to complete that problem, Step 1 was to determine game patterns which consist of home, away, and bye. Then Step 2 was to determine timetable, and Step 3 was to combine the Step 1 and Step 2. The Step 3 produced a schedule.

PENYELESAIAN MASALAH PENJADWALAN PERTANDINGAN SEPAK BOLA DENGAN SISTEM ROUND-ROBIN

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

Oleh:

ABDILLAH G54103026

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008

Judul Nama NRP

: Penyelesaian Masalah Penjadwalan Pertandingan Sepak Bola dengan Sistem Round-Robin : Abdillah : G54103026

Menyetujui: Pembimbing I,

Pembimbing II,

Dra. Farida Hanum, M.Si. NIP. 131 956 709

Dr. Toni Bakhtiar, M.Sc. NIP. 132 158 750

Mengetahui: Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

Dr. Drh. Hasim, DEA NIP. 131 578 806

Tanggal Lulus: ……………………..

KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Allah SWT atas segala nikmat dan karunianya sehingga penulisan skripsi ini berhasil diselesaikan. Tema yang dipilih adalah Riset Operasi dengan judul Penyelesaian Masalah Penjadwalan Pertandingan Sepak Bola dengan Sistem RoundRobin. Skripsi ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Terima kasih penulis ucapkan kepada: 1. ibunda tercinta, Aliyah yang telah melahirkan, mendidik, dan membesarkan penulis dengan curahan cinta dan sayang yang tidak terbatas; bapakku tercinta, Rosyadi atas segala kerja keras sebagai kepala keluarga; serta kakak-kakakku tersayang, (alm) Amah, Agus, Abdul Azip, Abdullah, dan Ida Farida, atas segala kasih sayangnya; 2. Ibu Dra. Farida Hanum M.Si. dan Bapak Dr. Toni Bakhtiar M.Sc. selaku dosen pembimbing pertama dan kedua, atas segala kesabaran dan arahannya selama membimbing penulis; serta tak lupa kepada Bapak Drs. Siswandi M.Si. selaku penguji; 3. Mahnuri, Armi, dan Rama atas kesediaannya menjadi pembahas dalam seminar karya ilmiah penulis; 4. Mayang atas bantuannya dalam belajar software LINGO 8.0; Dwi dan teman-teman Wisma Ayu atas kesediaannya membantu penulis untuk konsumsi seminar; 5. teman-teman satu atap selama hidup di Bogor: Aam, Ali, Ari, Komenk, Prima, Demi, dan Anton; 6. teman-teman pecinta alam Liberte Da Forte Matematika: Rusli, Sawa, Mufti, Lili, Manto, Dimas, Achie, Ifni, Jaja, Gandronk, Mika, dan Mitha; 7. teman-teman angkatan 40: Beri, Azis, Ucup, Abay, Kafi, Febrian, Jayu, Palkon, Gono, Ami, Icha, Iwit, Kawal, Elis, Ulfa, Marlin, Nchi, Yuda, Uli, Sriti, Agatha, Herni, Nisa, Metha, dan Arin atas persahabatan yang luar biasa indah, semoga persahabatan ini tetap terjalin sampai kapanpun; 8. kakak-kakak mahasiswa matematika angkatan 39; adik-adik mahasiswa matematika angkatan 41 dan 42; serta seluruh dosen, pegawai, dan staf Departemen Matematika IPB; 9. keluarga besar DPM FMIPA IPB angkatan 2004-2005; serta pengurus GUMATIKA IPB 2004-2005; 10. teman-teman penghuni Lorong 1 Gedung C1 Asrama TPB IPB 2003-2004, terutama Abdan, Aswar, Haris, Adiyanto, Hilman, dan Latief atas persahabatannya; juga pihak-pihak lain yang telah membantu penyusunan skripsi ini, yang tidak dapat disebutkan satu persatu. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu dibutuhkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat khususnya bagi penulis dan pembaca pada umumnya.

Bogor, Maret 2008

Abdillah

RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 4 Agustus 1985 sebagai anak keenam dari enam bersaudara. Ayah penulis bernama Rosyadi dan ibu bernama Aliyah. Tahun 1997 penulis menyelesaikan pendidikan MI Manba’ul Khair Kreo, Tangerang. Penulis melanjutkan pendidikan MTS Manba’ul Khair dan lulus pada tahun 2000. Pada tahun 2003 penulis menyelesaikan pendidikan SMA Negeri 32 Jakarta dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Selama mengikuti kegiatan perkuliahan, penulis aktif pada kegiatan kemahasiswaan antara lain sebagai staf ahli Gugus Mahasiswa Matematika (GUMATIKA) IPB periode 2004-2005, ketua Komisi Minat dan Bakat Dewan Perwakilan Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan alam (DPM FMIPA) IPB periode 2004-2005. Penulis juga aktif sebagai panitia pada beberapa acara antara lain Matematika Ria tahun 2005, Masa Perkenalan Departemen (MPD) Matematika IPB tahun 2006. Selain aktif di berbagai kegiatan kemahasiswaan, penulis juga aktif sebagai pecinta alam.

DAFTAR ISI Halaman DAFTAR GAMBAR ................................................................................................................ viii DAFTAR TABEL...................................................................................................................... viii DAFTAR LAMPIRAN.............................................................................................................. viii I

PENDAHULUAN 1.1 Latar Belakang .......................................................................................................... 1.2 Tujuan ........................................................................................................................

1 1

II LANDASAN TEORI 2.1 Pemrograman Linear ..................................................................................................... 2.2 Integer Linear Programming ........................................................................................ 2.3 Metode Branch and Bound............................................................................................

1 2 3

III PEMODELAN 3.1 Model Penjadwalan Pertandingan dengan Sistem Round-Robin................................... 3.2 Ilustrasi Penyelesaian Masalah Penjadwalan Pertandingan .......................................... 3.3 Penyelesaian Masalah Penjadwalan Pertandingan Sepak Bola .....................................

5 6 8

IV STUDI KASUS DAN PENYELESAIANNYA 4.1 Masalah Penjadwalan Pertandingan Babak Kualifikasi Piala Eropa 2008 Grup B ........

9

V SIMPULAN.......................................................................................................................... 12 DAFTAR PUSTAKA ................................................................................................................ 13 LAMPIRAN............................................................................................................................... 14

vii

DAFTAR GAMBAR Halaman 1 Grafik daerah fisibel IP dan PL-relaksasi ............................................................................. 2 Grafik daerah fisibel untuk Subproblem 2 dan Subproblem 3.............................................. 3 Pencabangan yang dilakukan metode branch and bound untuk menentukan solusi IP........

3 4 5

DAFTAR TABEL Halaman 1 Negara peserta ...................................................................................................................... 9 2 Periode waktu pertandingan ................................................................................................. 9 3 Jadwal pertandingan babak kualifikasi Piala Eropa 2008 Grup B........................................ 24

DAFTAR LAMPIRAN Halaman 1 Penyelesaian Contoh 2 dengan software LINDO 6.1............................................................ 15 2 Penyelesaian Langkah 1 dengan software LINGO 8.0 ......................................................... 19 3 Penyelesaian Langkah 2 dengan software LINGO 8.0 ........................................................ 22

viii

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,

6

sehingga kombinasinya menghasilkan k 3 2 = 2 pola yang mungkin, yaitu: 1: 2: 3: 4: 5: 6: 7: 8:

H H A; A H A; H A H; A A H; H H H; A H H; A A A; H A A.

Pemilihan pola harus memenuhi kriteriakriteria sebagai berikut: 1. Apabila dipilih suatu pola, misalkan HHA, maka pola yang berlaku sebaliknya, yaitu AAH, juga harus dipilih; 2. Terdapat H dan A yang sama banyaknya untuk setiap periode. Banyaknya H dan A 1 adalah dari pola yang terpilih. Untuk 2 kasus tim berjumlah ganjil, banyaknya H 1 dan A adalah dari pola yang terpilih 2 dikurangi 1. Contoh 3 a. Misalkan dari pola yang mungkin hanya diambil empat pola saja sesuai dengan banyaknya tim yaitu:

1: 2: 3: 4:

H H A; A H A; H A H; A A H.

Terlihat bahwa Pola 1, yaitu HHA, merupakan kebalikan dari Pola 4 (AAH), begitu juga Pola 2 (AHA) merupakan kebalikan dari Pola 3 (HAH). Pola-pola yang diambil tersebut telah memenuhi kriteria yang ada. b. Misalkan empat pola lain yang diambil adalah: 5: 6: 7: 8:

H H H; A H H; A A A; H A A.

Pola yang memuat H akan dipertemukan dengan pola yang memuat A untuk setiap periode waktu, yaitu setiap minggu. Berarti setiap periode berlangsung 2 pertandingan sehingga apabila diakumulasikan maka banyaknya pertandingan selama 3 minggu adalah 6 pertandingan. Apabila pola yang diambil tidak memenuhi kriteria tersebut

maka akan ada kesalahan dalam penyusunan pertandingan. Berikut ini diberikan contoh yang tidak memenuhi kriteria tersebut. Contoh 4 Misalkan empat pola yang diambil adalah:

1: 2: 5: 8:

H H A; A H A; H H H; H A A.

Pada Contoh 4 terlihat bahwa dalam suatu periode banyaknya H atau A melebihi atau bahkan kurang dari yang seharusnya. Misalkan pada Periode 1 dilihat secara vertikal ke bawah terdapat H sebanyak 3 buah dan A hanya 1 buah. Pada periode ini pola yang memuat H dipertemukan dengan pola yang memuat A, akan tetapi ada pola yang memuat H bertemu dengan H. Pada kasus ini berarti ada dua tim yang saling bertanding di tempat sendiri, padahal seharusnya salah satunya harus berlaku sebagai H dan yang lainnya sebagai A. Apabila pola yang dipilih melebihi banyaknya tim, maka banyaknya pertandingan tidak sesuai atau melebihi dari yang seharusnya. Misalkan banyaknya tim adalah 4 dan banyaknya pola yang dipilih adalah 5, yaitu: 1: 3: 5: 7: 8:

H H A; H A H; H H H; A A A; H A A.

Pola yang memuat H dipertemukan dengan pola yang memuat A untuk setiap periode waktu, sehingga dari 5 pola tersebut diambil 4 pola saja. Akan tetapi terkadang timbul kesulitan dalam memilih pola, sehingga akan terjadi kerancuan atau dengan kata lain ada pola yang tidak digunakan, misalkan pada Periode 1 banyaknya H berlebih yaitu sebanyak 4 buah sehingga ada H yang tidak digunakan. 3.2 Ilustrasi Penyelesaian Masalah Penjadwalan Pertandingan Pada bagian ini diilustrasikan penyelesaian masalah penjadwalan pertandingan sepak bola yang diikuti empat tim selama tiga minggu atau setengah kompetisi terlebih dahulu. Misalkan empat pola yang dipilih adalah:

7

1: 2: 3: 4:

H H A; A H A; H A H; A A H.

Tim

Misalkan tim i adalah tim yang bermain dengan menggunakan pola i, untuk i = 1, 2,3, 4. Pada saat ini, belum ditentukan di antara Tim a, b, c, d yang merupakan Tim 1, 2, 3, 4. Selanjutnya akan ditentukan tabel waktu dari pola yang telah dipilih. Diasumsikan Tim 1 bertanding dengan tim lain berdasarkan urutan timnya (2, 3, 4). Misalkan Tim 1 bertanding dengan Tim 2 pada Periode 1, Tim 1 bertanding dengan Tim 3 pada Periode 2, dan Tim 1 bertanding dengan Tim 4 pada Periode 3 yang dituliskan dalam bentuk kotak-kotak dengan 4 baris dan 4 kolom. Selanjutnya, urutan tim pada Kolom 4 (Periode III) diasumsikan berlaku kebalikan dari Kolom 1 (Tim 1, 2, 3, 4). Setelah itu akan dilengkapi sisa pertandingannya sehingga menghasilkan tabel waktu seperti yang tertera di bawah ini. Tim 1: 2: 3: 4:

I 2 1 4 3

Periode II 3 4 1 2

III 4 3 2 1

Selanjutnya, misalkan tanda negatif (−) berarti suatu tim bermain di tempat lawan, sedangkan bila tidak negatif, berarti suatu tim bermain di tempat sendiri. Misalkan pada saat Tim 1 melawan Tim 2, Tim 2 bertanda (−) yang berarti Tim 2 bermain di tempat lawan (A) sedangkan yang menjadi tuan rumah (H) adalah Tim 1.

1: 2: 3: 4:

Periode II -3 -4 1 2

I -2 1 -4 3

III 4 3 -2 -1

Selanjutnya himpunan pola dicocokkan dengan tabel waktu. Pada saat ini akan ditentukan di antara Tim a, b, c, dan d adalah Tim 1 dan seterusnya. Misalkan Tim 1 adalah Tim a, Tim 2 adalah Tim c, Tim 3 adalah Tim b, dan Tim 4 adalah Tim d. Berikut ini adalah jadwal pertandingan selama setengah kompetisi (round-robin). Tim a c b d

Periode II -b -d a c

I -c a -d b

III d b -c -a

Selanjutnya akan ditentukan jadwal pertandingan untuk kompetisi penuh yang berlangsung selama 6 minggu. Pada langkah ini digunakan aturan mirror. Misalkan suatu kompetisi terdiri atas 2k periode, masingmasing k periode di setengah kompetisi pertama dan kedua. Aturan mirror mengharuskan bahwa jika Tim a bertindak sebagai home bagi Tim b pada periode ke-i di setengah kompetisi pertama, maka Tim a akan bertindak sebagai away bagi Tim b pada periode ke − (i + k ) di setengah kompetisi kedua. Periode i dan i + k dikatakan saling bercerminan (mirror). Dalam kasus kompetisi yang diikuti oleh 4 tim yang berlangsung selama 6 periode, periode-periode berikut adalah saling bercerminan: ( I,IV ) , ( II,V ) , dan ( III,VI ) , sehingga diperoleh jadwal pertandingan selama 6 minggu adalah sebagai berikut:

Tim a c b d

Periode I -c a -d b

II -b -d a c

III d b -c -a

Sebagai tambahan, misalkan banyaknya tim yang bertanding berjumlah ganjil maka ada tim yang tidak bertanding (mendapat bye) untuk setiap periode waktu. Misalkan peserta sebanyak 3 tim. Dengan sistem kompetisi

IV c -a d -b

V b d -a -c

VI -d -b c a

penuh selama 6 minggu dihasilkan jadwal pertandingan. Misalkan tanda (—) menyatakan tim tersebut tidak bertanding (mendapat bye). Jadwal pertandingannya dapat dilihat pada tabel berikut ini.

8

Tim a b c

Periode I -b a —

II c — -a

III — -c b

3.3 Penyelesaian Masalah Penjadwalan Pertandingan Sepak Bola Ada tiga langkah untuk menyelesaikan masalah penjadwalan pertandingan tersebut. • Langkah 1: Penentuan pola dan himpunan pola. Pola i terdiri atas H, A, B. Misalkan P adalah himpunan pola i yang mungkin terjadi, sedangkan Q adalah himpunan pola i yang terpilih dan T adalah himpunan periode waktu k. Berikut ini didefinisikan beberapa variabel indeks yang bernilai 0 atau 1 xi = Indeks dari pola i yang diperoleh dari Q hik = Indeks dari tim yang bermain sebagai H dalam pola i pada periode k aik = Indeks dari tim yang bermain sebagai A dalam pola i pada periode k bi = Indeks dari pola i yang tidak dipilih n = Banyaknya pola yang memuat H atau A

dengan ⎧⎪1 ; ⎪⎩0 ;

xi = ⎨

jika pola i ada dalam Q jika selainnya,

⎧⎪1 ; hik = ⎨ ⎪⎩0 ;

jika pola i memuat H pada periode k jika selainnya,

⎧⎪1 ; aik = ⎨ ⎪⎩0 ;

jika pola i memuat A pada periode k jika selainnya,

⎧⎪1 ; bi = ⎨ ⎪⎩0 ;

jika pola i tidak dipilih jika selainnya.

Berdasarkan ilustrasi penyusunan jadwal pertandingan dengan peserta sebanyak 4 tim yang berlangsung selama 3 minggu atau setengah kompetisi pada Subbab 3.1 diperoleh P = {1, 2,...,8}

Misalkan dipilih pola pertandingan yang memenuhi kriteria sebagai berikut: HHA, AHH, HAH, AAH, maka Q = {1, 2,3, 4} .

IV b -a —

V -c — a

VI — c -b

Karena pola HHH tidak termasuk di dalam pola yang terpilih, yaitu 5 ∉ Q , maka x5 = 0 atau dikatakan pola HHH sebagai pola yang tidak dipilih ( b5 = 1 ). Sedangkan untuk pola HAH termasuk pola yang terpilih, yaitu 3 ∈ Q, maka x3 = 1. Fungsi objektif dari permasalahan tersebut adalah: minimumkan J1 = ∑ bi xi i∈P

Fungsi objektif tersebut menjelaskan bahwa hal yang akan diminimumkan adalah indeks pola yang tidak dipilih ( bi ) dan indeks dari pola xi yang diperoleh, dengan pola i ∈ P. Untuk solusi optimum, fungsi objektif tersebut selalu bernilai nol karena batas minimumnya tidak pernah negatif. Kendala-kendalanya adalah: 1. Pola yang memuat H sebanyak n pola (banyaknya pola adalah setengah dari banyaknya pola yang terpilih atau untuk kasus banyaknya pola adalah ganjil maka banyaknya pola adalah setengah dari pola yang terpilih dikurangi satu) untuk setiap periode waktu yang memenuhi kendala berikut ini

∑ hik xi = n; ∀k ∈ T .

i∈P

2. Pola yang memuat A sebanyak n pola (banyaknya pola adalah setengah dari banyaknya pola yang terpilih atau untuk kasus banyaknya pola adalah ganjil maka banyaknya pola adalah setengah dari pola yang terpilih dikurangi satu) untuk setiap periode waktu yang memenuhi kendala berikut ini

∑ aik xi = n; ∀k ∈ T .

i∈P

3. Variabel keputusan bernilai 0 atau 1, yaitu xi ∈ {0,1} ; (∀i ∈ P ).

9

• Langkah 2: Penentuan tabel waktu. Pada langkah ini akan ditentukan pertandingan berdasarkan pola tersebut, akan tetapi belum ditentukan timnya. Hasil dari langkah ini disebut tabel waktu. Pemodelan untuk masalah tersebut dibuat berdasarkan banyaknya tim dan periode waktu. Misalkan l adalah periode waktu yang merupakan pencerminan dari periode waktu k. Berikut ini didefinisikan variabel indeks yang bernilai 0 atau 1, yaitu: xijk = Indeks pertandingan tim i dengan tim j pada periode waktu k dengan ⎧ ⎪1 ;

jika tim i bertanding dengan

xijk = ⎨

tim j pada periode waktu k ⎪0 ; jika selainnya ⎩

Fungsi objektif dari permasalahan tersebut adalah: minimumkan J 2 =

∑ xijk

i, j ,k

Fungsi objektif tersebut menjelaskan bahwa hal yang akan diminimumkan adalah banyaknya pertandingan. Indeks i dan j didefinisikan sebagai tim, sedangkan k adalah periode waktu. Kendala-kendalanya adalah: 1. Setiap tim harus bertanding dengan tim lain

∑ xijk

= 1 ; i ≠ j ; ∀k ∈ T .

i , j ,k

2. Setiap pasangan tim bertanding satu kali untuk setiap periode waktu yang memenuhi kendala berikut ini

∑ xijk + ∑ x jik ≤ 1;∀k ∈T.

i, j ,k

i, j ,k

3. Adanya aturan mirror

xijk = x jil ; ∀(i, j, k ), ∀( j, i, l ) dengan k dan l memenuhi aturan mirror yaitu dua periode yang saling bercerminan. 4. Variabel keputusan bernilai 0 atau 1, yaitu xijk ∈ {0,1} ; ∀(i, j , k ).

Maka tabel waktu untuk setengah kompetisi akan diperoleh setelah masalah ILP tersebut diselesaikan. • Langkah 3: Pencocokan himpunan pola dengan tabel waktu. Langkah ini adalah perpaduan dari Langkah 1 dan Langkah 2, yaitu mencocokkan himpunan pola dengan tabel waktu. Pada langkah ini dihasilkan jadwal pertandingan selama satu musim kompetisi.

IV STUDI KASUS DAN PENYELESAIANNYA 4.1 Masalah Penjadwalan Pertandingan Babak Kualifikasi Piala Eropa 2008 Grup B Masalah penjadwalan pertandingan ini banyak dijumpai dalam kehidupan nyata. Salah satunya adalah masalah penjadwalan pertandingan babak kualifikasi Piala Eropa 2008 Grup B yang diikuti oleh 7 tim (lihat Tabel 1). Pada tahap ini digunakan sistem round-robin. Tabel 1 Negara peserta No Negara 1 Skotlandia (S) 2 Itali (It) 3 Perancis (P) 4 Ukraina (U) 5 Georgia (G) 6 Lithuania (L) 7 Kepulauan Faroe (K)

Tabel 2 Periode waktu pertandingan Periode Tanggal 2 September ‘06 1 6 September ‘06 2 7 Oktober ‘06 3 11 Oktober ‘06 4 24 Mei ’07 5 28 Mei ’07 6 2 Juni ’07 7 6 Juni ’07 8 8 September ’07 9 12 September ’07 10 13 Oktober ’07 11 17 Oktober ’07 12 17 November ’07 13 21 November ’07 14

Pola i terdiri atas H, A, B maka banyaknya pertandingan M dan N, yaitu:

10

M = T C 2 = 7 C2 =

7! = 21, (7 − 2)!2!

T −1 7 −1 = = 3, 2 2 sehingga banyaknya periode waktu k untuk setengah kompetisi adalah k = T = 7. Banyaknya elemen himpunan pola P adalah k (2k −1 ) = 7(26 ) = 448. Sehingga pola N=

i ∈ P = {1, 2,..., 448} dan k = 1, 2,..., 7.

• Langkah 1: Penentuan pola dan himpunan pola. Fungsi objektif dari permasalahan tersebut adalah: 448

minimumkan J1 = ∑ bi xi i =1

Fungsi objektif tersebut menjelaskan bahwa hal yang akan diminimumkan adalah bi dan xi dengan i merupakan banyaknya pola yang dimulai dari 1 sampai 448. Kendala-kendalanya adalah: 1. Pola yang memuat H diasumsikan sebanyak 3 pola dari 7 pola sesuai dengan kriteria pemilihan pola, yaitu banyaknya H adalah setengah dari banyaknya pola yang terpilih (untuk kasus banyaknya pola yang ganjil adalah setengah dari banyaknya pola yang terpilih dikurangi satu) untuk setiap periode waktu yang memenuhi kendala berikut ini 448

∑ hik xi = 3 ; (k = 1, 2,..., 7). i =1

2. Pola yang memuat A diasumsikan sebanyak 3 pola dari 7 pola sesuai dengan kriteria pemilihan pola, yaitu banyaknya A adalah setengah dari banyaknya pola yang terpilih (untuk kasus banyaknya pola yang ganjil adalah setengah dari banyaknya pola yang terpilih dikurangi satu) untuk setiap periode waktu yang memenuhi kendala berikut ini 448

∑ aik xi = 3 ; (k = 1, 2,..., 7). i =1

3. Variabel keputusan bernilai 0 atau 1, yaitu xi ∈ {0,1} (i = 1, 2,..., 448).

Permasalahan tersebut untuk selanjutnya diselesaikan dengan menggunakan software LINGO 8.0 (lihat Lampiran 2). Sebanyak 7168 variabel dan 3151 kendala dianalisis dalam 1159666 iterasi dengan waktu proses lebih kurang 3 jam 35 menit dengan menggunakan komputer Pentium 4 CPU 1.50 GHz dengan RAM 480 MB. Dalam tahap ini diperoleh J1 = 0. Pola yang diperoleh terdiri atas H, A, dan B, yaitu: 1: 2: 3: 4: 5: 6: 7:

H H H H A H B; H A H A H B H; A A A H B H A; A H A B A A A; H H B H H A H; A B H A A H H; B A A A H A A.

Berdasarkan pola yang dihasilkan dapat dilihat bahwa jika suatu tim mengambil pola pertama maka tim tersebut akan bermain di tempat sendiri (H) pada Periode 1, 2, 3, 4, dan 6 dan bermain di tempat lawan (A) pada Periode 5, sedangkan pada Periode 7 tidak bermain. Solusi penentuan pola tersebut tidak tunggal. Sesungguhnya ada banyak solusi lain untuk himpunan pola yang mungkin, salah satunya adalah: 1: 2: 3: 4: 5: 6: 7:

H A H A H H B; H H A H H B A; A A H A B H H; A H A B A A A; H H B A A A H; A B A H A H A; B A H H H A H.

Pada langkah ini belum ditentukan di antara ketujuh tim tersebut sebagai Tim 1 dan seterusnya. • Langkah 2: Penentuan tabel waktu. Pada langkah ini akan ditentukan pertandingan dari pola tersebut, akan tetapi belum ditentukan timnya. Hasil dari langkah ini disebut tabel waktu. Untuk memformulasikan ILP tersebut, didefinisikan variabel keputusan: ⎧ jika tim i bertanding dengan tim j ⎪1 ; xijk = ⎨ pada periode waktu k ⎪0 ; jika selainnya ⎩ ⎧ ⎪1 ;

jika tim i bertanding dengan tim j pada periode waktu l ⎪0 ; jika selainnya ⎩

xijl = ⎨

11

Fungsi objektif dari permasalahan ini adalah: minimumkan J 2 =

∑x

ijk

+

i, j ,k

∑x

i = 1,2,...,7 ; j = 1,2,...,7, k = 1,2,...,7; l = 8,9,...,14.

ijl

i , j ,l

Fungsi objektif tersebut menjelaskan bahwa hal yang akan diminimumkan adalah banyaknya pertandingan. Periode waktunya dibagi menjadi dua bagian yaitu bagian pertama didefinisikan dengan k dan bagian kedua dengan l. Kendala-kendalanya adalah: 1. Setiap tim harus bertanding dengan tim lain

∑ x + ∑x ijk

i , j ,k

= 1 ; i ≠ j,

ijl

i, j ,l

i = 1,2,...,7 ; j = 1,2,...,7, k = 1,2,...,7; l = 8,9,...,14.

2. Setiap pasangan tim bertanding satu kali untuk setiap periode waktu yang memenuhi kendala berikut ini

∑x

ijk

i , j ,k

+

∑x

≤ 1,

i, j ,k

∑ x +∑ x ijl

i , j ,l

jik

jil

dengan k dan l memenuhi aturan mirror

≤ 1,

i , j ,l

i = 1,2,...,7 ; j = 1,2,...,7,

4. Variabel keputusan bernilai 0 atau 1, yaitu xijk ∈ {0,1} ; ∀(i, j , k ), xijl ∈ {0,1} ; ∀(i, j , l ), i = 1,2,...,7 ; j = 1,2,...,7, k = 1,2,...,7; l = 8,9,...,14.

Permasalahan tersebut untuk selanjutnya diselesaikan dengan menggunakan software LINGO 8.0 (lihat Lampiran 3). Sebanyak 686 variabel dan 729 kendala dianalisis dalam 0 iterasi dengan waktu proses kurang dari 1 menit dengan menggunakan komputer Pentium 4 CPU 1.50 GHz dengan RAM 480 MB. Dalam tahap ini diperoleh J 2 = 42. Pada Langkah 2 didapat susunan pertandingan dari pola yang terpilih. Hasil pada langkah ini kemudian direpresentasikan dalam bentuk tabel waktu dengan sistem round-robin. Misalkan tanda (—) menyatakan tim yang tidak bertanding (bye). Tabel berikut ini merupakan tabel waktu yang dihasilkan dari Langkah 2 untuk tujuh periode waktu atau setengah kompetisi.

k = 1,2,...,7; l = 8,9,...,14.

3. Adanya aturan mirror xijk = x jil ; ∀(i, j , k ), ∀( j , i, l ),

Tim 1: 3: 2: 4: 6: 5: 7:

I -3 1 -4 2 5 -6 —

II -2 4 1 -3 — -7 5

III -4 2 -3 1 -7 — 6

Selanjutnya disusun tabel waktu selama 14 periode waktu. Tabel berikut ini adalah tabel

Periode IV -6 -7 5 — 1 -2 3

V 5 — -6 7 2 -1 -4

VI -7 -5 — 6 -4 3 1

VII — 6 -7 5 -3 -4 2

waktu yang merepresentasikan jadwal pertandingan untuk satu kompetisi penuh.

12

Tim 1: 3: 2: 4: 6: 5: 7:

I -3 1 -4 2 5 -6 —

II -2 4 1 -3 — -7 5

III -4 2 -3 1 -7 — 6

IV -6 -7 5 — 1 -2 3

V 5 — -6 7 2 -1 -4

VI -7 -5 — 6 -4 3 1

VII — 6 -7 5 -3 -4 2

• Langkah 3: Pencocokan himpunan pola dengan tabel waktu. Langkah ini merupakan perpaduan himpunan pola dan tabel waktu. Pada langkah

Tim S P It U L G K

I -P S -U It G -L —

II -It U S -P — -K G

III -U It -P S -K — L

IV -L -K G — S -It P

V G — -L K It -S -U

VI -K -G — L -U P S

VII — L -K G -P -U It

Setelah didapatkan tabel berupa jadwal pertandingan, selanjutnya periode waktu yang tertera pada tabel tersebut diganti dengan

Periode VIII 3 -1 4 -2 -5 6 —

IX 2 -4 -1 3 — 7 -5

X 4 -2 3 -1 7 — -6

XI 6 7 -5 — -1 2 -3

XII -5 — 6 -7 -2 1 4

XIII 7 5 — -6 4 -3 -1

XIV — -6 7 -5 3 4 -2

ini akan ditentukan di antara (S, It, P, U, G, L, K) adalah Tim 1 dan seterusnya. Tabel berikut ini adalah jadwal pertandingan yang dihasilkan dari Langkah 3.

Periode VIII P -S U -It -G L —

IX It -U -S P — K -G

X U -It P -S K — -L

XI L K -G — -S It -P

XII -G — L -K -It S U

XIII K G — -L U -P -S

XIV — -L K -G P U -It

periode waktu yang tertera pada Tabel 2. Setelah itu didapatkan jadwal pertandingan selama 14 periode waktu (lihat Lampiran 4).

V SIMPULAN Pembuatan jadwal pertandingan yang baik dan tersusun rapi dalam suatu kompetisi sepak bola sangatlah penting. Oleh karena itu, permasalahan yang muncul adalah bagaimana cara membuat jadwal pertandingan sepak bola yang tepat dan menguntungkan semua pihak. Dalam tulisan ini, telah diperlihatkan bahwa ilmu Matematika dapat diaplikasikan dalam pembuatan jadwal pertandingan, yaitu dengan memodelkan masalah penjadwalan pertandingan sebagai suatu masalah ILP. Permasalahan tersebut diselesaikan dengan menggunakan software LINGO 8.0 dengan metode Branch and Bound. Studi kasus untuk masalah penjadwalan pertandingan tersebut adalah model penjadwalan pertandingan pada babak kualifikasi Piala Eropa 2008 Grup B. Masalah

tersebut diselesaikan dalam tiga langkah yaitu penentuan pola dan himpunan pola, penentuan tabel waktu, dan langkah terakhir adalah perpaduan dari himpunan pola dan tabel waktu. Adapun manfaatnya adalah pengguna dapat lebih efisien dalam menghasilkan jadwal yang baik, dibandingkan dengan cara manual yang memerlukan banyak waktu dan memungkinkan terjadinya kekeliruan dalam penulisan.

13

DAFTAR PUSTAKA Garfinkel, R.S. & G.L. Nemhauser. 1972. Integer Programming. John Willey & Sons, New York. Nash, S.G. & A. Sofer. 1996. Linear and Nonlinear Programming. McGrawHill, New York. Nemhauser, G.L. & M.A. Trick. 1998. Scheduling a Major College Basketball Conference. Operations Research 46(1):1-8.

Taha, H.A. 1975. Integer Programming. Academic Press, New York. Winston, W.L. 1995. Introduction to Mathematical Programming 2nded. Duxbury, New York.

14

LAMPIRAN

15

Lampiran 1 Penyelesaian Contoh 2 dengan Menggunakan Software LINDO 6.1 Subproblem 1

Maximize 5X + 4Y Subject to X + Y <= 5 10X + 6Y <= 45 LP OPTIMUM FOUND AT STEP

0

OBJECTIVE FUNCTION VALUE 1)

23.75000

VARIABLE VALUE REDUCED COST X 3.750000 0.000000 Y 1.250000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 2.500000 3) 0.000000 0.250000 NO. ITERATIONS=

0

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 5.000000 1.666667 1.000000 Y 4.000000 1.000000 1.000000 ROW 2 3

RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 5.000000 2.500000 0.500000 45.000000 5.000000 15.000000

Subproblem 2

Maximize 5X + 4Y Subject to X + Y <= 5 10X + 6Y <= 45 X <=3 LP OPTIMUM FOUND AT STEP

1

16

OBJECTIVE FUNCTION VALUE 1)

23.00000

VARIABLE VALUE REDUCED COST X 3.000000 0.000000 Y 2.000000 0.000000 ROW 2) 3) 4)

SLACK OR SURPLUS DUAL PRICES 0.000000 4.000000 3.000000 0.000000 0.000000 1.000000

NO. ITERATIONS=

1

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 5.000000 INFINITY 1.000000 Y 4.000000 1.000000 4.000000 ROW 2 3 4

RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 5.000000 0.500000 2.000000 45.000000 INFINITY 3.000000 3.000000 0.750000 3.000000

Subproblem 3

Maximize 5X + 4Y Subject to X + Y <= 5 10X + 6Y <= 45 X >=4 LP OPTIMUM FOUND AT STEP

1

OBJECTIVE FUNCTION VALUE 1)

23.33333

VARIABLE VALUE REDUCED COST X 4.000000 0.000000 Y 0.833333 0.000000 ROW 2) 3) 4)

SLACK OR SURPLUS DUAL PRICES 0.166667 0.000000 0.000000 0.666667 0.000000 -1.666667

17

NO. ITERATIONS=

1

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 5.000000 1.666667 INFINITY Y 4.000000 INFINITY 1.000000 ROW 2 3 4

RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 5.000000 INFINITY 0.166667 45.000000 1.000000 5.000000 4.000000 0.500000 0.250000

Subproblem 4

Maximize 5X + 4Y Subject to X + Y <= 5 10X + 6Y <= 45 X >=4 Y <=0 LP OPTIMUM FOUND AT STEP

2

OBJECTIVE FUNCTION VALUE 1)

22.50000

VARIABLE VALUE REDUCED COST X 4.500000 0.000000 Y 0.000000 0.000000 ROW 2) 3) 4) 5)

SLACK OR SURPLUS DUAL PRICES 0.500000 0.000000 0.000000 0.500000 0.500000 0.000000 0.000000 1.000000

NO. ITERATIONS=

2

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 5.000000 1.666667 5.000000 Y 4.000000 INFINITY 1.000000

18

ROW 2 3 4 5

RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 5.000000 INFINITY 0.500000 45.000000 5.000000 5.000000 4.000000 0.500000 INFINITY 0.000000 0.833333 0.000000

Subproblem 5

Maximize 5X + 4Y Subject to X + Y <= 5 10X + 6Y <= 45 X >=4 Y >=1

19

Lampiran 2 Penyelesaian Langkah 1 Masalah Penjadwalan Pertandingan Babak Penyisihan Piala Eropa 2008 Grup B dengan Menggunakan Software LINGO 8.0 MODEL: TITLE Masalah Jadwal Pertandingan Sepak bola; SETS: POLA/1..448/:PILIH,TIDAK_DIPILIH; WAKTU/W1 W2 W3 W4 W5 W6 W7/; LINKS(POLA,WAKTU):HOME,AWAY; ENDSETS !Fungsi objektif; MIN=@SUM(POLA(I):PILIH(I)*TIDAK_DIPILIH(I)); !Kendala home; @FOR(WAKTU(J): @SUM(POLA(I) :HOME(I,J)*PILIH(I))=3); !Kendala away; @FOR(WAKTU(J): @SUM(POLA(I):AWAY(I,J)*PILIH(I))=3); !Setiap tim akan bermain sebagai home atau away untuk setiap periode waktu; @FOR(LINKS(I,J):HOME(I,J)+AWAY(I,J)=1); !Kendala variabel keputusan bernilai 0 atau 1; @FOR(LINKS:@BIN(HOME)); @FOR(LINKS:@BIN(AWAY)); @FOR(POLA:@BIN(PILIH)); @FOR(POLA:@BIN(TIDAK_DIPILIH)); END

Keterangan: tidak semua variabel dicantumkan dan hanya variabel yang bernilai 1 dan merupakan nilai yang dicari sedangkan yang bernilai 0 tidak ditampilkan karena jumlahnya terlalu banyak Local optimal solution found at iteration: Objective value:

1159666 0.000000

Model Title: Masalah Jadwal Pertandingan Sepak bola Variable PILIH( 144) PILIH( 145) PILIH( 314) PILIH( 432) PILIH( 447) PILIH( 448)

Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

Model Title: Masalah Jadwal Pertandingan Sepak bola Variable TIDAK_DIPILIH( 1) TIDAK_DIPILIH( 3)

Value 1.000000 1.000000

Reduced Cost 0.000000 0.000000

20

TIDAK_DIPILIH( 4)

1.000000

0.000000

Model Title: Masalah Jadwal Pertandingan Sepak bola Variable HOME( 1, W1) HOME( 1, W2) HOME( 1, W3) HOME( 1, W4) HOME( 1, W5) HOME( 1, W6) HOME( 1, W7) HOME( 3, W1) HOME( 3, W2) HOME( 3, W3) HOME( 3, W4) HOME( 3, W5) HOME( 3, W6) HOME( 3, W7) HOME( 4, W1) HOME( 4, W2) HOME( 4, W3) HOME( 4, W4) HOME( 4, W5) HOME( 4, W6) HOME( 4, W7) HOME( 144, W1) HOME( 144, W2) HOME( 144, W3) HOME( 144, W4) HOME( 144, W5) HOME( 144, W7) HOME( 145, W4) HOME( 145, W6) HOME( 314, W1) HOME( 314, W2) HOME( 314, W3) HOME( 314, W4) HOME( 314, W6) HOME( 314, W7) HOME( 432, W5) HOME( 447, W2) HOME( 448, W1) HOME( 448, W3) HOME( 448, W5) HOME( 448, W6) HOME( 448, W7)

Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

Model Title: Masalah Jadwal Pertandingan Sepak bola

AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY(

Variable 144, W6) 145, W1) 145, W2) 145, W3) 145, W5) 145, W7) 314, W5)

Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

21

AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY( AWAY(

432, 432, 432, 432, 432, 432, 447, 447, 447, 447, 447, 447, 448, 448,

W1) W2) W3) W4) W6) W7) W1) W3) W4) W5) W6) W7) W2) W4)

1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

22

Lampiran 3 Penyelesaian Langkah 2 Masalah Penjadwalan Pertandingan Babak Penyisihan Piala Eropa 2008 Grup B dengan Menggunakan Software LINGO 8.0 MODEL: TITLE Masalah Jadwal Pertandingan Sepak bola; SETS: POLA1/1..7/; POLA2/1..7/; WAKTU1/W1..W7/; WAKTU2/W8..W14/; BETA1(POLA1,POLA2,WAKTU1):X1; BETA2(POLA1,POLA2,WAKTU2):X2; ENDSETS !Fungsi objektif; MIN = @SUM(BETA1(I,J,K):X1(I,J,K))+@SUM(BETA2(I,J,L):X2(I,J,L)); !Kendala tanding; @FOR(POLA1(I): @FOR(POLA2(J)|I#NE#J: @SUM(WAKTU1(K):X1(I,J,K))+@SUM(WAKTU2(L):X2(I,J,L))=1)); !Kendala bahwa setiap pasangan hanya bermain satu kali; @FOR(POLA1(I): @FOR(WAKTU1(K): @SUM(POLA2(J):X1(I,J,K))+@SUM(POLA2(J):X1(J,I,K))<=1)); @FOR(POLA1(I): @FOR(WAKTU2(L): @SUM(POLA2(J):X2(I,J,L))+@SUM(POLA2(J):X2(J,I,L))<=1)); !Kendala mirror; @FOR(BETA1(I,J,K)|I#NE#J:X1(I,J,K)=X2(J,I,K)); @FOR(BETA2(I,J,L)|I#NE#J:X1(I,J,L)=X2(J,I,L)); !Kendala variabel keputusan bernilai 0 atau 1; @FOR(BETA1:@BIN(X1)); @FOR(BETA2:@BIN(X2)); END

Keterangan: tidak semua variabel dicantumkan dan hanya variabel yang bernilai 1 dan merupakan nilai yang dicari sedangkan yang bernilai 0 tidak ditampilkan karena jumlahnya terlalu banyak Global optimal solution found at iteration: Objective value:

0 42.00000

Model Title: Masalah Jadwal Pertandingan Sepak bola

X1( X1( X1( X1(

Variable 2, 1, W2) 3, 1, W1) 3, 2, W3) 4, 1, W3)

Value 1.000000 1.000000 1.000000 1.000000

Reduced Cost 1.000000 1.000000 1.000000 1.000000

23

X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1( X1(

4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7,

2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6,

W1) W2) W5) W4) W6) W7) W4) W5) W7) W6) W1) W6) W7) W4) W5) W2) W3)

1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

Model Title: Masalah Jadwal Pertandingan Sepak bola Variable X2( 1, 2, W9) X2( 1, 3, W8) X2( 1, 4, W10) X2( 1, 5, W12) X2( 1, 6, W11) X2( 1, 7, W13) X2( 2, 3, W10) X2( 2, 4, W8) X2( 2, 5, W11) X2( 2, 6, W12) X2( 2, 7, W14) X2( 3, 4, W9) X2( 3, 5, W13) X2( 3, 6, W14) X2( 3, 7, W11) X2( 4, 5, W14) X2( 4, 6, W13) X2( 4, 7, W12) X2( 5, 6, W8) X2( 5, 7, W9) X2( 6, 7, W10)

Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

Reduced Cost 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

24

Lampiran 4 Jadwal Pertandingan Babak Kualifikasi Piala Eropa 2008 Grup B

Tabel 3 Jadwal pertandingan babak kualifikasi Piala Eropa 2008 Grup B Home / Away

Skotlandia

Skotlandia

Perancis

Itali

Ukraina

Lithuania

Georgia

Kepulauan Faroe

2 Sep 2006

6 Sep 2006

7 Okt 2006

11 Okt 2006

17 Okt 2007

28 Mei 2007

12 Sep 2007

8 Sep 2007

21 Nov 2007

28 Mei 2007

11 Okt 2006

2 Sep 2006

24 Mei 2007

13 Okt 2007

2 Juni 2007

17 Nov 2007

21 Nov 2007

17 Okt 2007

6 Juni 2007

7 Okt 2006

Perancis

6 Juni 2007

Itali

8 Sep 2007

7 Okt 2006

Ukraina

12 Sep 2007

6 Sep 2006

6 Juni 2007

Lithuania

13 Okt 2007

2 Juni 2007

17 Okt 2007

28 Mei 2007

Georgia

24 Mei 2007

17 Nov 2007

11 Okt 2006

2 Juni 2007

2 Sep 2006

Kepulauan Faroe

17 Nov 2007

13 Okt 2007

21 Nov 2007

24 Mei 2007

12 Sep 2007

6 Sep 2006 8 Sep 2007