II LANDASAN TEORI Pada pembuatan model penjadwalan pertandingan sepak bola babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan, diperlukan pemahaman beberapa teori yang digunakan di dalam penyelesaiannya, di antaranya teori Pemrograman Linear (PL), Integer Linear Programming (ILP), dan metode Branch and Bound untuk menyelesaikan masalah Integer Programming. Berikut ini akan dibahas satu per satu. 2.1 Pemrograman Linear
c)
persamaan linear atau pertidaksamaan linear. Variabel keputusan harus taknegatif atau tidak dibatasi tandanya. (Winston 1995)
Suatu PL dikatakan memiliki bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear dikatakan mempunyai bentuk standar jika berbentuk:
Definisi 1 (Fungsi Linear) Misalkan menyatakan suatu fungsi dalam variabel-variabel . adalah suatu fungsi linear jika dan hanya jika untuk himpunan konstanta , . (Winston 2004)
minimumkan
Sebagai contoh, merupakan fungsi linear, sementara bukan fungsi linear. Suatu persamaan merupakan persamaan linear, apabila f fungsi linear.
(Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1.
Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear dan sembarang bilangan b, dan pertidaksamaan dikatakan pertidaksamaan linear. Misalkan b sembarang bilangan, suatu persamaan merupakan persamaan linear. (Winston 2004)
Solusi optimal terbaik adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terkecil (dalam masalah minimisasi). Untuk masalah maksimisasi, solusi optimal suatu PL adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terbesar.
Pemrograman Linear (PL) adalah suatu masalah optimasi yang memenuhi ketentuanketentuan 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
Untuk menyelesaikan suatu masalah PL metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimal. 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 secara berulang-ulang hingga didapatkan solusi yang diinginkan) untuk menyelesaikan masalah PL berbentuk standar.
terhadap ,
(1)
dengan x dan c merupakan vektor berukuran n, vektor b berukuran m, sedangkan A merupakan matriks berukuran m × n. Matriks A disebut matriks kendala.
Definisi 4 (Solusi Optimal)
(Winston 2004) Solusi Pemrograman Linear
3
Pada masalah PL (1), vektor x yang memenuhi kendala disebut sebagai solusi dari PL (1). Misalkan matriks A dinyatakan sebagai , dengan B merupakan matriks taksingular 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).
.
(4)
Dari PL tersebut diperoleh: ,
.
Misalkan dipilih dan
,
maka matriks basisnya adalah
Misalkan x dapat dinyatakan sebagai dengan
vektor variabel basis dan nonbasis, maka
adalah vektor
adalah vektor variabel dinyatakan sebagai
.
(2)
Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) dapat dinyatakan sebagai : .
.
(3)
Dengan menggunakan matriks basis di atas, didapatkan
Definisi 5 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika: i. ii.
solusi tersebut memenuhi kendala pada PL, kolom-kolom dari matriks koefisien yang berpadanan dengan komponen taknol adalah bebas linear. (Nash & Sofer 1996)
Definisi 6 (Solusi Basis Fisibel) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan . Salah satu cara menentukan solusi basis fisibel awal adalah dengan membuat . (Nash & Sofer 1996) Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1. Contoh 1 Misalkan berikut:
diberikan
minimumkan terhadap
pemrograman
linear
(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 basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Definisi 7 (Daerah Fisibel) Daerah fisibel untuk suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) 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
4
bilangan bulat (integer). Jika semua variabel harus 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) Definisi 9 (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 optimal di PL-relaksasi lebih kecil atau sama dengan nilai fungsi objektif yang optimal di IP, sedangkan untuk masalah memaksimumkan nilai fungsi objektif yang optimal di PL-relaksasi lebih besar atau sama dengan nilai fungsi objektif yang optimal di IP. (Winston 2004) 2.3 Metode Branch and Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimal 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 efektivitasnya dalam memecahkan masalah dengan hasil yang akurat. Prinsip dengan metode branch and bound adalah memecah daerah fisibel dari masalah PL-relaksasi dengan membuat subproblem-subproblem. Daerah fisibel pemrograman linear adalah daerah yang memenuhi semua kendala pemrograman linear. Branching Membuat partisi daerah solusi dari masalah PL-relaksasi ke dalam subproblem. Tujuannya untuk menghapus daerah solusi yang takfisibel. Hal ini dapat 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. Bounding Misalkan masalah tersebut diasumsikan merupakan tipe maksimisasi, nilai objektif yang optimal 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 optimal. Operasi ini yang menjadi alasan dinamakan bounding. (Taha 1975) Metode branch and bound diawali dengan menyelesaikan LP-relaksasi dari suatu masalah IP. Jika semua nilai variabel keputusan solusi optimal sudah berupa integer, maka solusi tersebut merupakan solusi optimal ILP. Jika tidak, dilakukan pencabangan dan penambahan batasan pada LP-relaksasinya kemudian diselesaikan. Winston (2004) menyebutkan bahwa nilai fungsi objektif optimal untuk ILP nilai fungsi objektif optimal untuk LP-relaksasi (masalah maksimisasi), sehingga nilai fungsi objektif optimal LP-relaksasi merupakan batas atas bagi nilai fungsi objektif optimal untuk masalah ILP. Diungkapkan pula oleh Winston (2004) bahwa nilai fungsi objektif optimal untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimal untuk masalah ILP asalnya. Suatu kandidat solusi didapat jika solusi dari suatu subproblem sudah menemui kendala integer pada masalah ILP, artinya semua variabelnya sudah bernilai integer. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch and bound. 1.
Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) ILP yang optimal. Pada awalnya ditetapkan z = - dan i = 0.
2.
Langkah 1 Subproblem PL(i) dipilih sebagai bagian masalah berikutnya untuk dipecahkan, Subproblem PL(i) diselesaikan dan diukur dengan kondisi yang sesuai.
5
a. Jika PL(i) terukur dan solusi PL yang ditemukan lebih baik maka batas bawah z diperbarui. Jika tidak, bagian masalah (subproblem) baru i yang dipilih dan langkah 1 diulangi. Jika semua subproblem telah diteliti maka proses dihentikan. b. Jika PL(i) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan PL(i).
dengan 1.
(Taha 1996) Untuk memudahkan pemahaman mengenai metode branch and bound diberikan contoh sebagai berikut. Contoh 2 Misalkan diberikan pemrograman integer (IP) sebagai berikut:
Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika terdapat kondisi sebagai berikut.
Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimal untuk IP. Subproblem tersebut menghasilkan suatu solusi optimal dengan semua variabelnya bernilai integer. Jika solusi optimal ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimal dan nilai fungsi objektifnya menjadi batas bawah nilai fungsi objektif optimal bagi masalah IP pada saat itu. Bisa jadi subproblem ini menghasilkan solusi optimal untuk masalah IP. Nilai fungsi objektif optimal untuk subproblem tersebut tidak melebihi batas bawah saat itu, maka subproblem ini dapat dieliminasi.
Langkah 2 Dipilih satu variabel xj yang nilai optimalnya adalah xj* yang tidak memenuhi batasan integer dalam solusi LPi. Bidang disingkirkan dengan membuat dua subproblem PL, yaitu dan , sehingga diperoleh kendala subproblem baru sebagai berikut: Subproblem baru 1: kendala subproblem lama + kendala
. Selanjutnya kembali ke Langkah
maksimumkan z = 4x1 + 5x2, terhadap: x1
3x1 + 6x2
40,
10,
3x2
15,
x1, x2
0 dan integer.
(6)
Setelah diselesaikan menggunakan software LINGO 8.0 didapatkan solusi optimal PL-relaksasi dari masalah IP (6) adalah x1 = 10, x2 = 1.66, z = 48.33 (lihat Lampiran 1). Batas atas nilai optimal fungsi objektif masalah IP (6) adalah 48.33. Daerah fisibel PL-relaksasi masalah (6) ditunjukkan pada Gambar 1 (daerah yang diarsir). Solusi optimal berada pada titik perpotongan garis yang berasal dari kendala pertidaksamaan masalah (6).
6.66
3.
Subproblem baru 2 : kendala subproblem lama + kendala
dengan didefinisikan sebagai integer terbesar yang kurang dari satu atau sama
x2 = 1.66
5
x1 = 10
0
10
13.33
Gambar 1 Daerah fisibel untuk PL-relaksasi dari IP (6). Langkah berikutnya adalah memartisi daerah fisibel PL-relaksasi menjadi dua bagian berdasarkan variabel yang berbentuk pecahan (non-integer). Dipilih x2 sebagai dasar pencabangan. Jika masalah PL-relaksasinya
6
diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 Subproblem, yaitu:
Subproblem 2: Subproblem 1 ditambah kendala x2 1; Subproblem 3: Subproblem 1 ditambah kendala x2 2;
Hal ini diilustrasikan secara grafis pada Gambar 2.
solusi optimum yang dihasilkan Subproblem 3 bukan solusi integer, maka dipilih pencabangan pada Subproblem 3 atas x1, sehingga diperoleh dua subproblem lagi, yakni:
Subproblem 4: Subproblem 3 ditambah kendala x1 ≤ 9; Subproblem 5: Subproblem 3 ditambah kendala x1 ≥ 10;
Subproblem 4 dan Subproblem 5 diselesaikan satu per satu. Subproblem 5 takfisibel (lihat Lampiran1), maka subproblem ini tidak menghasilkan solusi optimum. 6.66
Solusi optimal untuk Subproblem 4 adalah x1 = 9, x2 = 2.16, z = 46.83 (lihat Lampiran 1). Karena solusi optimum Subproblem 4 bukan solusi integer, maka dipilih pencabangan Subproblem 4 pada x2, sehingga diperoleh dua subproblem lagi, yaitu:
5 2 1
0
10
13.33
Gambar 2 Daerah fisibel Subproblem 2 (x2 1) dan Subproblem 3 (x2 2). Setiap titik (solusi) fisibel dari IP (6) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dikatakan dicabangkan atas x2. Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, kemudian diselesaikan. Solusi optimal yang didapatkan untuk Subproblem 2 adalah x1 = 10, x2 = 1, z = 45 (lihat Lampiran 1). Solusi dari Subproblem 2 semuanya bernilai integer sehingga tidak perlu lagi dilakukan pencabangan pada Subproblem 2. Nilai optimum Subproblem 2 menjadi batas bawah pertama yaitu 45. Saat ini subproblem yang belum diselesaikan adalah Subproblem 3. Solusi optimal untuk Subproblem 3 adalah x1 = 9.33, x2 = 2, z = 47.33 (lihat Lampiran 1). Karena
Subproblem 6: Subproblem 4 ditambah kendala x2 ≤ 2; Subproblem 7: Subproblem 4 ditambah kendala x2 ≥ 3;
Penyelesaian Subproblem 6 menghasilkan solusi optimum yang berupa integer, dengan x1 = 9, x2 = 2, z = 46 (lihat Lampiran 1). Diperoleh kandidat solusi optimum yang baru dari Subproblem 6. Karena nilai z baru pada Subproblem 6 lebih baik daripada nilai z pada Subproblem 2, maka solusi pada Subproblem 6 menjadi batas bawah yang baru. Subproblem 7 menghasilkan solusi optimum x1 = 7.33, x2 = 3, z = 44.33 (lihat Lampiran 1). Karena solusi optimum dari Subproblem 7 tidak lebih baik dari batas bawah yang baru, maka tidak perlu dilakukan pencabangan pada Subproblem 7. Dengan demikian, solusi optimum pada IP (6) adalah solusi optimum dari Subproblem 6, yaitu x1 = 9, x2 = 2, z = 46 (lihat Lampiran 1). Pohon pencabangan yang menunjukkan penyelesaian masalah IP (6) secara keseluruhan ditunjukkan pada Gambar 3.
