PENJADWALAN BABAK KUALIFIKASI PIALA DUNIA FIFA 2014 ZONA AMERIKA SELATAN
FAIZUL MUBAROK
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
ABSTRAK FAIZUL MUBAROK. Penjadwalan Babak Kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan. Di bawah bimbingan FARIDA HANUM dan TONI BAKHTIAR. Dalam kompetisi sepak bola terdapat perangkat-perangkat yang penting dalam penyelenggaraannya. Salah satunya adalah jadwal pertandingan. Penyusunan jadwal pertandingan harus dilakukan dengan hati-hati dan penuh dengan pertimbangan agar pertandingan sepak bola dapat berjalan dengan lancar. Babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan melibatkan 10 tim nasional yang tergabung dalam satu grup dengan setiap negara memiliki satu stadion yang digunakan dalam setiap periode waktu. Tim-tim dalam zona ini dikelompokkan berdasarkan karakteristik yang dimiliki yaitu tim kuat, tim paling populer, tim populer, dan tim tidak populer. Tujuan karya tulis ini ialah membuat jadwal pertandingan yang memenuhi beberapa preferensi, seperti setiap tim harus bertanding dua kali dengan tim lain sebagai tuan rumah dan tamu di setiap paruh kompetisi, pertandingan klasik antara tim kuat dan popular harus dimainkan di pekan ke-3, 5, dan 7, serta setiap tim sebanyak-banyaknya bertanding dua kali berturut-turut sebagai tuan rumah ataukah tamu. Masalah penjadwalan ini dimodelkan dalam bentuk Integer Linear Programming.
ABSTRACT FAIZUL MUBAROK. Scheduling of the South American Zone of 2014 FIFA World Cup Qualification. Supervised by FARIDA HANUM and TONI BAKHTIAR. In football competitions, there are some devices that are important in implementation. One of them is the match schedule. Scheduling must be done carefully and with full consideration in order a football game can run properly. Scheduling of the South American Zone of 2014 FIFA World Cup Qualification involves 10 national teams from 10 different countries that merged into one group with each state has one stadium that is used in each time period. The teams in this zone are grouped based on their characteristics, those are strong teams, most popular teams, popular teams, and unpopular teams. The purpose of this paper is to make a schedule that meets some preferences, such as each team must compete with other teams twice as a home team and an away team on each half of the competition, a classic match between strong teams and popular teams should be played in the third, fifth, and seventh weeks, and each team should have at most two consecutive games either as a home team or an away team. This scheduling problem is modeled in the form of Integer Linear Programming.
PENJADWALAN BABAK KUALIFIKASI PIALA DUNIA FIFA 2014 ZONA AMERIKA SELATAN
FAIZUL MUBAROK
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
Judul : Penjadwalan Babak Kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan Nama : Faizul Mubarok NIM
: G54062219
Menyetujui, Pembimbing I,
Pembimbing II,
Dra. Farida Hanum, M.Si. NIP 19651019 199103 2 002
Dr. Toni Bakhtiar, S.Si, M.Sc. NIP 19720627 199702 1 002
Mengetahui, Ketua Departemen Matematika
Dr. Berlian Setiawaty, M.S. NIP 19650505 198903 2 004
Tanggal Lulus : ………………………………………..
KATA PENGANTAR Assalamu’alaikum Wr. Wb. Alhamdulillahirabbil’alamin, segala puji dan syukur penulis sampaikan kepada Allah SWT atas segala limpahan nikmat, rahmat dan karunia – Nya sehingga penulis dapat menyelesaikan karya ilmiah ini. Shalawat beserta salam senantiasa tercurah kepada baginda Rasulullah Muhammad SAW yang syafa`atnya selalu diharapkan di hari akhir kelak. Penyelesaian karya ilmiah ini tidak terlepas dari bantuan berupa masukan, saran, maupun kritikan berbagai pihak. Sebagai bentuk rasa syukur kepada Allah SWT, penulis ingin menyampaikan terima kasih dan penghargaan kepada: 1. 2. 3. 4. 5.
6.
7.
8. 9.
10.
Ibu Dra. Farida Hanum, M.Si selaku dosen pembimbing I atas bimbingan, arahan, waktu dan kesabaran yang telah diberikan kepada penulis selama proses penyusunan skripsi ini, Bapak Dr. Toni Bakhtiar, S.Si, M.Sc selaku dosen pembimbing II atas bimbingan, arahan, waktu dan kesabaran yang telah diberikan kepada penulis selama proses penyusunan skripsi ini, Bapak Dr. Ir. Amril Aman, M.Sc selaku dosen penguji atas saran dan masukannya, Para dosen Departemen Matematika atas ilmu yang telah bapak dan ibu berikan, serta para staf departemen Matematika yang telah membantu penulis dalam urusan administrasi, Ayah Dr. H. Abdul Wahid Hasyim, MA, ibu Dra. Hj. Ida Hamdanah, adik-adik Fajar Prana, Fadel Askary dan Ahmad Fairuz beserta keluarga besar untuk semua do’a, cinta, dan dukungan yang diberikan. Semoga ini menjadi salah satu persembahan terbaik untuk kalian dan ke depan akan menyusul persembahan terbaik lainnya, Puspi Eko Wiranthi, SE yang dengan sabar telah meluangkan waktunya membantu dalam teknis penelitian penulis, serta dukungan, doa, kebersamaan, semangat, dan kritik yang diberikan. Semoga segera menyelesaikan kuliah program magisternya dan melanjutkan ke jenjang program doktor. Ke depannya, saya pun akan mengikuti jejak yang sama, Teman-teman mahasiswa matematika angkatan 43: Arif, Albrian, Apri, Slamet, Andrew, Subro, Dandi, Zulkarnaen, Dwi, Kuntoaji dan teman-teman lainnya atas segenap dukungannya selama penulis menempuh studi di Departemen Matematika IPB, Kakak-kakak mahasiswa matematika angkatan 41 dan 42 serta adik-adik mahasiswa matematika angkatan 44 dan 45 yang tidak bisa disebutkan satu per satu, Keluarga PPSDM BEM FMIPA Kabinet Ksatria Pembaharu 2008/2009, PSDM BEM KM Kabinet Generasi Inspirasi 2009/2010 dan teman-teman seperjuangan lainnya BEM KM Kabinet Totalitas Perjuangan 2008-2009, FOSMA ESQ 165 untuk semangat, dukungan, kebersamaan, persahabatan, doa, dan kenangan yang diberikan, Teman – teman Al Izzer`s, kakak kelas Syamsu Rizal, SP, Afid Khotami, S.Pi, teman seangkatan Satrio Ardi S.Pt, Herman Siregar, STP, Zenal Asikin, SE, M. Iman Damara, SE, Haryadi, S.Si, Maulana Ishak, Wahyu Hendana, Wirudy dan adik-adik kelas serta pihak-pihak lain yang telah membantu penyusunan skripsi ini, yang tidak dapat disebutkan satu per satu atas dukungan, nasihat dan bantuan kepada penulis selama ini.
Penulis berharap semoga karya ilmiah ini nantinya akan bermanfaat untuk berbagai pihak dengan berbagai cara. Penulis menyadari bahwa masih banyak kekurangan dalam penyusunan karya ilmiah ini. Oleh karena itu, kritik dan saran yang membangun sangat diharapkan dalam perbaikan atau kelanjutan karya ilmiah ini.
Bogor,
Desember 2011
Faizul Mubarok
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 14 Mei 1988. Penulis adalah anak pertama dari empat bersaudara dari pasangan Bapak Dr. H. Abdul Wahid Hasyim, MA dan Ibu Dra. Hj. Ida Hamdanah. Penulis menyelesaikan pendidikan taman kanak-kanak di TK. Islam Al Ghifary lulus pada tahun 1994, pendidikan dasar di Madrasah Ibtidaiyah Pembangunan UIN Jakarta lulus pada tahun 2000, pendidikan lanjutan menengah pertama di Madrasah Tsanawiyah Pembangunan UIN Jakarta lulus pada tahun 2003, dan pendidikan menengah atas di SMA Negeri 47 Jakarta lulus pada tahun 2006. Penulis diterima di Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI) pada tahun 2006 dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam pada tahun 2007. Selama mengikuti pendidikan, penulis cukup aktif berorganisasi. Beberapa diantaranya, penulis tercatat sebagai staf Departemen Pendidikan dan Pengembangan Sumberdaya Manusia (PPSDM) Badan Eksekutif Mahasiswa Keluarga Mahasiswa (BEM KM) IPB periode 2007-2008, staf Departemen Pengembangan Sumberdaya Manusia (PSDM) Himpunan Profesi Gugus Mahasiswa Matematika (GUMATIKA) IPB periode 2007-2008, kepala departemen Pengembangan Potensi Sumberdaya Manusia (PPSDM) Badan Eksekutif Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam (BEM FMIPA) IPB periode 2008-2009, Menteri Pengembangan Sumberdaya Manusia (PSDM) Badan Eksekutif Mahasiswa Keluarga Mahasiswa (BEM KM) IPB periode 2009-2010, dewan komisaris Leadership Entrepreneurship School (LES) Badan Eksekutif Mahasiswa Keluarga Mahasiswa (BEM KM) IPB periode 2009-2010. Penulis juga aktif mengikuti berbagai kepanitiaan dan sering ditunjuk sebagai koordinator dan steering committee. Di samping itu, penulis juga menjadi guru privat dan guru di beberapa bimbingan belajar di Jakarta maupun di Bogor.
DAFTAR ISI Halaman DAFTAR GAMBAR……………………………………………………..…………………………...viii I
PENDAHULUAN .................................................................................................................. 1 1.1 Latar Belakang ................................................................................................................. 1 1.2 Tujuan.............................................................................................................................. 1
II
LANDASAN TEORI .............................................................................................................. 2 2.1 Pemrograman Linear ........................................................................................................ 2 2.2 Integer Linear Programming ............................................................................................ 3 2.3 Metode Branch and Bound .............................................................................................. 4
III
DESKRIPSI DAN FORMULASI MASALAH ....................................................................... 7 3.1 Deskripsi Masalah ........................................................................................................... 7 3.2 Formulasi Masalah .......................................................................................................... 8
IV
PENYELESAIAN MASALAH PENJADWALAN BABAK KUALIFIKASI PIALA DUNIA 2014 ZONA AMERIKA SELATAN ...................................................................................... 9
V
SIMPULAN DAN SARAN ................................................................................................... 12 5.1 Simpulan ....................................................................................................................... 12 5.2 Saran ............................................................................................................................. 13
DAFTAR PUSTAKA ..................................................................................................................... 13 LAMPIRAN ................................................................................................................................... 14
vii
DAFTAR GAMBAR Halaman 1 2 3
Daerah fisibel untuk PL-relaksasi dari IP (6) .............................................................................. 5 Daerah fisibel Subproblem 2 (x2 1) dan Subproblem 3 (x2 2) ................................................. 6 Seluruh pencabangan pada metode Branch and Bound untuk menentukan solusi optimal dari IP (6), dengan t menyatakan urutan penyelesaian subproblem ........................................................ 7
viii
I PENDAHULUAN 1.1 Latar Belakang Pada tahun 206 SM, pada masa pemerintahan Dinasti Tsin dan Han, masyarakat Cina telah memainkan bola yang disebut tsu chu. Tsu sendiri artinya “menerjang bola dengan kaki”. sedangkan chu, berarti “bola dari kulit dan ada isinya”. Permainan bola saat itu menggunakan bola yang terbuat dari kulit binatang, dengan aturan menendang, menggiring dan memasukkanya ke sebuah jaring yang dibentangkan diantara dua tiang. Versi sejarah kuno tentang sepak bola yang lain datangnya dari negeri Jepang. Dikatakan bahwa sejak abad ke-8, masyarakat Jepang telah mengenal permainan bola, yang disebut dengan kemari. Sedangkan bola yang dipergunakan adalah kulit kijang, yang di tengahnya sudah berlubang dan berisi udara. Bill Muray, salah seorang sejarawan sepak bola, dalam bukunya The World’s Game: A History of Soccer, menyatakan bahwa permainan sepak bola sudah dikenal sejak awal masehi. Pada saat itu, masyarakat Mesir Kuno sudah mengenal teknik membawa dan menendang bola yang terbuat dari buntalan kain linen. Sedangkan dalam sejarah yang lain, khususnya Yunani Purba juga sudah mengenal sebuah permainan yang disebut episcuro, yang tidak lain adalah permainan menggunakan bola. Bukti sejarah ini tergambar pada relief-relief museum yang melukiskan anak muda memegang bola dan memainkannya dengan pahanya. Piala Dunia adalah kompetisi antarnegara dalam dunia sepak bola internasional yang diselenggarakan oleh Federation Internationale de Football Association. (FIFA). Babak final turnamen ini diikuti oleh tim yang lolos kualifikasi di berbagai zona. Piala Dunia diselenggarakan setiap empat
tahun sekali. Lebih dari 160 tim nasional setiap negara bertanding dalam turnamen kualifikasi regional untuk meraih tempat dalam babak final. Babak final melibatkan 32 tim nasional (peningkatan sejak tahun 1998) yang berkompetisi selama 4 minggu di negara tuan rumah. Dalam kompetisi sepak bola terdapat perangkat-perangkat penting dalam penyelenggaraannya, salah satunya adalah jadwal pertandingan. Penyusunan jadwal pertandingan harus dilakukan dengan hati-hati dan penuh dengan pertimbangan agar pertandingan sepak bola dapat berjalan dengan lancar. Masalah penjadwalan sepak bola dapat diselesaikan dengan beberapa cara. Salah satu caranya 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. Sumber utama karya ilmiah ini ialah tulisan Fiallos et al. (2010) yang berjudul “Scheduling Soccer League of Honduras using Integer Programming”. Karya ilmiah ini akan membahas bagaimana memformulasikan dan menyelesaikan masalah penjadwalan pertandingan dalam bentuk ILP dengan mengambil contoh kasus babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan dengan menggunakan bantuan software LINGO 8.0. 1.2 Tujuan Karya ilmiah ini bertujuan memodelkan dan menyelesaikan masalah penjadwalan pertandingan sepak bola babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan melalui Integer Linear Programming (ILP).
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.
7
Subproblem 1 x1 = 10, x2 = 1.66, z = 48.33 (batas atas) x2 ≥ 2
x2 ≤ 1 t=2
t=1 Subproblem 2
Subproblem 3 x1 = 9.33, x2 = 2, z = 47.33
x1 = 10, x2 = 1, z = 45 (batas bawah ke-1)
x1 ≥ 10
x1 ≤ 9
t=3 t=4
Subproblem 5 Solusi takfisibel
Subproblem 4 x1 = 9, x2 = 2.16, z = 46.83
x2 ≥ 3
x2 ≤ 2 t=6
Subproblem 7
t=5 Subproblem 6 Subproblem 1
x1 = 7.33, x2 = 3, z = 44.33
x1 = 9, x2 = 2, z = 46 (batas bawah ke-2) Subproblem 1
Gambar 3 Seluruh percabangan pada metode Branch and Bound untuk menentukan solusi optimal dari IP (6), dengan t menyatakan urutan penyelesaian subproblem.
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah Tim nasional yang terlibat babak kualifikasi zona Amerika Selatan ialah Brasil, Argentina, Uruguay, Chile, Paraguay, Kolombia, Peru, Bolivia, Venezuela, dan Ekuador. Menurut aturan FIFA negara sebagai tuan rumah Piala Dunia secara otomatis langsung lolos ke putaran final, tanpa melalui babak kualifikasi. Namun, model yang digunakan setiap tim harus bertanding satu kali per pekan, sehingga Brazil tetap diikutsertakan dalam masalah ini. Tim-tim dibedakan berdasarkan karakteristik yang dimiliki menjadi tim kuat, tim paling populer, tim populer, dan tim tidak populer. Tim yang termasuk ke dalam kategori
tim kuat adalah Brasil, Argentina, Uruguay, dan Chile. Tim paling populer adalah Brasil dan Argentina. Tim populer adalah Argentina, Brasil, Uruguay, dan Chile. Sedangkan tim tidak populer adalah Paraguay, Kolombia, Peru, Bolivia, Venezuela, dan Ekuador. Untuk menyusun penjadwalan pertandingan sepak bola babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan diperlukan data tentang kondisi yang menunjukkan bagaimana jadwal yang baru dapat dibuat. Kondisi-kondisi ini difokuskan untuk mempromosikan turnamen, menjaga iklim persaingan dan kesuksesan ekonomi dari suatu penyelenggaraan turnamen.
8
1, jika tim i bertanding sebagai tim tuan rumah pada pekan k dan k+1
Kondisi-kondisi ini dirumuskan sebagai kendala-kendala pada model yang digunakan. 3.2 Formulasi Masalah Masalah penjadwalan pertandingan sepak bola babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan dapat diformulasikan sebagai Integer Linear Programming (ILP). Untuk memudahkan pemahaman terhadap formulasi model matematis yang akan dikembangkan, terlebih dahulu disajikan notasi-notasi matematis yang akan digunakan dalam pengembangan model. Notasi tersebut dikelompokkan menjadi tiga kelompok, yaitu himpunan, parameter, dan variabel keputusan. Ketiga notasi tersebut secara lebih detail dapat dijelaskan sebagai berikut: a.
himpunan semua tim tuan rumah himpunan semua tim tamu himpunan tim kuat himpunan tim paling populer himpunan tim populer himpunan tim tidak populer himpunan pekan untuk paruh pertama turnamen
Parameter
Vijk
bobot untuk mengatur pertandingan klasik yang menjadi prioritas
Dalam model pengoptimuman ini yang menjadi prioritas adalah pertandingan klasik (pertandingan sesama kategori tim kuat dan populer) tidak dijadwalkan pada salah satu dari dua pekan pertama atau dua pekan terakhir dari setiap setengah turnamen. Akibatnya, pertandingan klasik dimainkan di pekan ke-3, 5, dan 7 dari setiap setengah turnamen. Dengan prioritas di atas dapat ditetapkan Vijk = 0 untuk i, j {Brasil, Argentina, Uruguay, Chile} dan k {3, 5, 7} dan Vijk 0 untuk i, j, k lainnya. Data lengkap bobot terdapat pada Lampiran. c.
0, selainnya
Wik =
Bfi =
1, jika tim i bertanding sebagai tim tamu pada pekan k dan k+1 0, selainnya 1, jika tim i bertanding sebagai tim tamu pada pekan ke-1 dan tim tuan rumah pada pekan ke-9 0, selainnya
Himpunan
I J STR MPOP POP NMPOP K b.
Yik =
Bli =
1, jika tim i bertanding sebagai tim tuan rumah pada pekan ke-1 dan tim tamu pada pekan ke-9 0, selainnya
Tujuan utama melakukan penjadwalan adalah menentukan tim tuan rumah dan tim tamu yang diikutsertakan pada setiap pekan dari paruh pertama turnamen dengan meminimumkan banyaknya bobot pertandingan klasik, maka untuk i≠j, fungsi objektif dari permasalahan ini dapat dimodelkan sebagai berikut: min
dengan kendala-kendala sebagai berikut: 1.
Di setiap paruh kompetisi setiap tim bertanding satu kali per pekan melawan tim lain.
2.
Di setiap paruh kompetisi setiap tim bertanding satu kali melawan tim lain, apakah sebagai tim tuan rumah ataukah tim tamu.
Variabel keputusan
Xijk =
1, jika tim i bertanding dengan tim j pada pekan k 0, selainnya
9
3.
4.
Sebanyak-banyaknya setiap tim bertanding dua kali berturut-turut melawan tim lain sebagai tim tuan rumah.
8.
Pertandingan klasik dipertandingkan pada pekan ke-3, 5, dan 7.
9.
Setiap tim tidak bertanding melawan tim kuat dua kali berturut-turut.
Kendala ini membatasi setiap tim yang bertanding melawan tim lain sebagai tim tuan rumah berturut-turut.
5.
Sebanyak-banyaknya setiap tim bertanding dua kali berturut-turut melawan tim lain sebagai tim tamu.
6.
Kendala ini membatasi setiap tim yang bertanding melawan tim lain sebagai tim tamu berturut-turut.
10. Kendala ini memaksa setiap tim tidak populer bertanding melawan dua tim paling populer masing-masing sebagai tim tuan rumah dan tim tamu di setiap paruh kompetisi.
7.
Karena seluruh pertandingan akan dilaksanakan dalam dua putaran, maka keberturutan suatu tim sebagai tim tuan rumah atau tim tamu harus juga diperhitungkan di dua pertandingan pertama atau dua pertandingan terakhir.
11. Kendala ini menjamin setiap tim populer bertanding melawan tim populer lainnya setidaknya sekali sebagai tuan rumah.
IV PENYELESAIAN MASALAH PENJADWALAN BABAK KUALIFIKASI PIALA DUNIA 2014 ZONA AMERIKA SELATAN Babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan melibatkan 10 tim nasional dari 10 negara yang berbeda yang setidaknya memiliki 1 stadion yang digunakan dalam setiap pertandingan. Di samping itu, setiap tim nasional akan bertemu sebanyak dua kali dengan tim nasional lainnya, yaitu satu sebagai tim tuan rumah dan satu sebagai tim
tamu. Banyaknya pertandingan dihitung sebagai 2(n 1) dengan n adalah banyaknya tim yang bertanding dalam kualifikasi ini. Tim nasional yang terlibat dalam kualifikasi ini memiliki karakteristik yang berbeda. Terdapat empat jenis karakteristik yang dipertimbangkan pada permasalahan ini, yaitu tim kuat, tim paling populer, tim populer,
10
dan tim tidak populer. Tim yang termasuk ke dalam kategori tim kuat adalah Brasil, Argentina, Uruguay, dan Chile. Tim paling populer adalah Brasil dan Argentina. Tim populer adalah Argentina, Brasil, Uruguay, dan Chile. Sedangkan tim tidak populer adalah Paraguay, Kolombia, Peru, Bolivia, Venezuela, dan Ekuador.
Setiap tim nasional bertanding maksimal sebanyak dua kali berturut-turut, sebagai tim tuan rumah maupun tim tamu serta melawan tim kuat. Setiap tim nasional bertanding sebagai tim tuan rumah atau tim tamu. Pertandingan klasik (pertandingan sesama kategori tim kuat) dimainkan di pekan ke-3, 5, dan 7.
Tabel 1. Daftar tim nasional peserta babak kualifikasi Piala Dunia 2014 Indeks Tim Nama Tim Nama Stadion Kategori Tim 1 Brasil Various National Stadia STR, MPOP, POP 2
Argentina
Antonio Vespucio Liberti
STR, MPOP, POP
3
Uruguay
Estadio Centenario
STR, POP
4
Chile
Nacional
STR, POP
5
Paraguay
Defensores del Chaco
NMPOP
6
Kolombia
El Campin
NMPOP
7
Peru
Estadio Nacional
NMPOP
8
Bolivia
Hernando Siles
NMPOP
9
Venezuela
Monumental de Maturin
NMPOP
10
Ekuador
Olimpico Atahualpa
NMPOP
Untuk memformulasikan ILP, kategori tim didefinisikan pada setiap tim i = 1, 2,…, 10, tim j = 1, 2,…, 10, pekan k = 1, 2,…, 9, kategori tim STR = 1, 2, 3, 4, kategori tim MPOP = 1, 2, kategori tim POP = 1, 2, 3, 4, kategori tim NMPOP = 5, 6,…, 10, sehingga masalahnya dapat diformulasikan dalam ILP berikut:
min dengan kendala: 1. Di setiap paruh kompetisi setiap tim bertanding satu kali per pekan melawan tim lain. Untuk, i = 1, 2,…, 10, j = 1, 2,…, 10, dan k = 1, 2,…,9:
2.
Di setiap paruh kompetisi setiap tim bertanding satu kali melawan tim lain, apakah sebagai tim tuan rumah ataukah tim tamu. Untuk, i = 1, 2,…, 10, j = 1, 2,…, 10, dan k = 1, 2,…, 9:
3.
Sebanyak-banyaknya setiap tim bertanding dua kali berturut-turut melawan tim lain sebagai tim tuan rumah. Untuk i = 1, 2,…,10, j = 1, 2,…, 10, dan k = 1, 2,…, 9:
11
4.
Kendala ini membatasi setiap tim yang bertanding melawan tim lain sebagai tim tuan rumah berturut-turut. Untuk i = 1, 2,…, 10, dan k = 1, 2,…, 9:
5.
Sebanyak-banyaknya setiap tim bertanding dua kali berturut-turut melawan tim lain sebagai tim tamu. Untuk i = 1, 2,…, 10, j = 1, 2,…, 10, dan k = 1, 2,…, 9:
6.
7.
8.
Kendala ini membatasi setiap tim yang bertanding melawan tim lain sebagai tim tamu berturut-turut. Untuk i = 1, 2,…, 10, dan k = 1, 2,…, 9:
Karena seluruh pertandingan akan dilaksanakan dalam dua putaran, maka keberturutan suatu tim sebagai tim tuan rumah atau tim tamu harus juga diperhitungkan di dua pertandingan pertama atau dua pertandingan terakhir. Untuk i = 1, 2,…, 10, j = 1, 2,…, 10, dan k = 1, 8, 9:
Pertandingan klasik dipertandingkan pada pekan ke-3, 5, dan 7. Untuk i = 1, 2,…, 4, j = 1, 2,…, 4, dan k = 3, 5, 7:
9.
Setiap tim tidak bertanding melawan tim kuat dua kali berturut-turut. Untuk i = 4, 5,…, 10, j = 1, 2,…, 4, dan k = 1, 2,…, 9:
10. Kendala ini memaksa setiap tim tidak populer bertanding melawan dua tim paling populer masing-masing sebagai tim tuan rumah dan tim tamu di setiap paruh kompetisi. Misalnya Brasil vs Peru, Peru vs Argentina. Untuk i = 5, 6,…, 10, j = 1, 2,…, 4, dan k = 1, 2,…, 9:
11. Kendala ini menjamin setiap tim populer bertanding melawan tim populer lainnya setidaknya sekali sebagai tuan rumah. Untuk i = 1, 2,…,4, j = 1, 2,…, 4, dan k = 1, 2,…, 9:
Pada uraian tersebut, terlihat bahwa banyak sekali persamaan maupun pertdaksamaan yang harus diselesaikan. Dalam hal ini sulit jika digunakan metode branch and bound secara manual. Masalah di atas selanjutnya diselesaikan dengan menggunakan LINGO 8.0. Detail dari pemodelan tersebut dapat dilihat di Lampiran 2. Total waktu yang dibutuhkan untuk mendapatkan solusi dari proses ini adalah 2 menit 32 detik. Komputer yang digunakan untuk melakukan proses ini adalah komputer dengan processor intel Core 2 Duo 2.20 GHz dengan kecepatan memori RAM 2940 MB. Hasil komputasi tidak semuanya dicantumkan, karena terlalu banyak. Hasil yang dicantumkan hanya untuk X yang bernilai 1 saja. Dari hasil yang diperoleh, setiap tim bertanding maksimal sebanyak dua kali berturut-turut, sebagai tim tuan rumah
12
maupun tim tamu serta melawan tim kuat, pertandingan klasik (pertandingan kategori sesama tim kuat) dimainkan pada pekan ke- 3, 5, dan 7, setiap tim nasional bertanding dan
bertindak sebagai tim tuan rumah atau tim tamu pada setiap pekan. Nilai fungsi objektif yang meminimumkan banyaknya jadwal pertandingan adalah 39.
Tabel 2. Jadwal pertandingan babak kualifikasi Piala Dunia 2014 Pekan ke-1 Pekan ke-2 Pekan ke-3 Argentina vs Venezuela Brasil vs Bolivia Argentina vs Uruguay Uruguay vs Paraguay
Uruguay vs Peru
Chile vs Brasil
Kolombia vs Brasil
Paraguay vs Kolombia
Kolombia vs Ekuador
Peru vs Chile
Venezuela vs Chile
Bolivia vs Peru
Bolivia vs Ekuador
Ekuador vs Argentina
Venezuela vs Paraguay
Pekan ke-4
Pekan ke-5
Pekan ke-6
Uruguay vs Venezuela
Brasil vs Argentina
Brasil vs Ekuador
Paraguay vs Brasil
Chile vs Uruguay
Argentina vs Kolombia
Peru vs Argentina
Kolombia vs Peru
Paraguay vs Chile
Bolivia vs Kolombia
Venezuela vs Bolivia
Peru vs Venezuela
Ekuador vs Chile
Ekuador vs Paraguay
Bolivia vs Uruguay
Pekan ke-7
Pekan ke-8
Pekan ke-9
Uruguay vs Brasil
Brasil vs Peru
Uruguay vs Ekuador
Chile vs Argentina
Argentina vs Paraguay
Kolombia vs Chile
Paraguay vs Bolivia
Chile vs Bolivia
Peru vs Paraguay
Peru vs Ekuador
Kolombia vs Uruguay
Bolivia vs Argentina
Venezuela vs Kolombia
Ekuador vs Venezuela
Venezuela vs Brasil
*keterangan : tim yang pertama kali disebut di setiap pekan bertindak sebagai tim tuan rumah. Contoh Peru vs Chile pada pekan 1, maka Peru menjadi tim tuan rumah dan Chile menjadi tim tamu.
V SIMPULAN DAN SARAN 5.1 Simpulan Dalam membuat jadwal pertandingan sepak bola yang baik dan tersusun rapi dalam kompetisi sepak bola sangatlah penting. Banyak aspek yang harus dikelola di dalamnya, seperti banyaknya penonton, penjualan tiket dan pertandingan besar antara kedua tim. Oleh sebab itu, permasalahan yang
muncul adalah bagaimana cara membuat jadwal pertandingan sepak bola yang tepat dan menguntungkan semua pihak. Dalam karya ilmiah ini, telah diperlihatkan bahwa masalah penjadwalan pertandingan dapat dipandang sebagai masalah Integer Linear Programming (ILP). Penyelesaian masalah ini menggunakan
13
software Lingo 8.0 dengan metode Branch and Bound. Studi kasus untuk masalah penjadwalan pertandingan tersebut adalah model penjadwalan pertandingan babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan. Adapun manfaatnya adalah pengguna dapat lebih efisien dalam menghasilkan jadwal yang baik, dibandingkan dengan cara manual yang memerlukan banyak waktu dan memungkinkan terjadinya kekeliruan. 5.2 Saran Pada karya ilmiah ini telah dibahas penjadwalan pertandingan babak kualifikasi
Piala Dunia FIFA 2014 Zona Amerika Selatan dengan membagi tim ke dalam beberapa kategori. Namun, masalah penjadwalan ini masih difokuskan dalam ruang lingkup di zona lokal yang tidak memperhitungkan ajang kompetisi lainnya. Akan lebih baik lagi jika ada yang menindaklanjuti penelitian ini dengan masalah yang lebih kompleks, misalnya pertandingan babak kualifikasi Piala Dunia FIFA 2014 Zona Amerika Selatan dengan memasukkan kendala dari tim yang berlaga di kompetisi lainnya, seperti kompetisi antara tim Amerika Selatan.
DAFTAR PUSTAKA Fiallos J, Perez J, Sabillon F, Licona M. 2010. Scheduling soccer league of Honduras using integer programming. A. Johnson, J. Miller, eds., Proc. 2010 Indust. Engr. Res. Conf. Canc´un, Mexico. Garfinkel RS & Nemhauser GL. 1972. Integer Programming. John Wiley & Sons, New York. Murray B. 1998. The World’s Game: A History of Soccer. Univ. of Illinois Press. Chicago. Nash SG & Sofer A. 1996. Linear and Nonlinear Programming. McGraw-Hill, New York.
Taha
HA. 1975. Integer Programming: Theory, Application, and Computations. Academic Press, New York.
Taha HA. 1996. Pengantar Riset Operasi. Alih Bahasa: Daniel Wirajaya. Binarupa Aksara, Jakarta. Terjemahan dari: Operations Research. Winston WL. 1995. Introduction to Mathematical Programming 2nd ed. Duxbury, New York. Winston WL. 2004. Operations Research Applications and Algorithms 4th ed. Duxbury, New York.
LAMPIRAN
15
Lampiran 1 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch-and-Bound beserta Hasil yang Diperoleh. Penyelesaian Subproblem 1 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x1>=0; x2>=0; end Global optimal solution found at iteration: Objective value:
Variable X1 X2 Row 1 2 3 4 5 6
Value 10.00000 1.666667 Slack or Surplus 48.33333 0.000000 0.000000 10.00000 10.00000 1.666667
3 48.33333
Reduced Cost 0.000000 0.000000 Dual Price 1.000000 0.8333333 1.500000 0.000000 0.000000 0.000000
Penyelesaian Subproblem 2 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2<=1; x1>=0; x2>=0; end Global optimal solution found at iteration: Objective value:
Variable X1 X2 Row 1 2 3 4 5
Value 10.00000 1.000000 Slack or Surplus 45.00000 4.000000 0.000000 12.00000 0.000000
2 45.00000
Reduced Cost 0.000000 0.000000 Dual Price 1.000000 0.000000 4.000000 0.000000 5.000000
16
6 7
10.00000 1.000000
0.000000 0.000000
Penyelesaian Subproblem 3 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2>=2; x1>=0; x2>=0; end Global optimal solution found at iteration: Objective value:
Variable X1 X2 Row 1 2 3 4 5 6 7
Value 9.333333 2.000000 Slack or Surplus 47.33333 0.000000 0.6666667 9.000000 0.000000 9.333333 2.000000
2 47.33333
Reduced Cost 0.000000 0.000000 Dual Price 1.000000 1.333333 0.000000 0.000000 -3.000000 0.000000 0.000000
Penyelesaian Subproblem 4 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2>=2; x1<=9; x1>=0; x2>=0; end
Global optimal solution found at iteration: Objective value:
Variable X1 X2
Value 9.000000 2.166667
3 46.83333
Reduced Cost 0.000000 0.000000
17
Row 1 2 3 4 5 6 7 8
Penyelesaian Subproblem 5 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2>=2; x1>=10; x1>=0; x2>=0; end
Penyelesaian Subproblem 6 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2>=2; x1<=9; x2<=2; x1>=0; x2>=0; end
Slack or Surplus 46.83333 0.000000 1.000000 8.500000 0.1666667 0.000000 9.000000 2.166667
Dual Price 1.000000 0.8333333 0.000000 0.000000 0.000000 1.500000 0.000000 0.000000
18
Global optimal solution found at iteration: Objective value:
Variable X1 X2 Row 1 2 3 4 5 6 7 8 9
Value 9.000000 2.000000 Slack or Surplus 46.00000 1.000000 1.000000 9.000000 0.000000 0.000000 0.000000 9.000000 2.000000
3 46.00000
Reduced Cost 0.000000 0.000000 Dual Price 1.000000 0.000000 0.000000 0.000000 0.000000 4.000000 5.000000 0.000000 0.000000
Penyelesaian Subproblem 7 max=4*x1+5*x2; !kendala; 3*x1+6*x2<=40; x1<=10; 3*x2<=15; x2>=2; x1<=9; x2>=3; x1>=0; x2>=0; end Global optimal solution found at iteration: Objective value:
Variable X1 X2 Row 1 2 3 4 5 6 7 8 9
Value 7.333333 3.000000 Slack or Surplus 44.33333 0.000000 2.666667 6.000000 1.000000 1.666667 0.000000 7.333333 3.000000
3 44.33333
Reduced Cost 0.000000 0.000000 Dual Price 1.000000 1.333333 0.000000 0.000000 0.000000 0.000000 -3.000000 0.000000 0.000000
19
Lampiran 2 Syntax Model LINGO 8.0 dan Hasil Komputasi untuk Masalah Penjadwalan Babak Kualifikasi Piala Dunia 2014 Zona Amerika Selatan. model: title Pola Penjadwalan Sepak Bola babak Kualifikasi Piala Dunia 2014 Zona Amerika Latin; sets: team/1..10/:Bf,Bl; round/1..9/; LINKS(team,team,round):V,X; LINKS2(team,round):Y,W; end sets data: V = @OLE('Bobot 8.xlsx', 'BOBOT'); enddata !Fungsi Objektif; min=@sum(team(i):@sum(team(j):@sum(round(k):V(i,j,k)*X(i,j,k)))); !kendala 1; @for(team(i): @for(team(j)|i#ne#j: @sum(round(k):X(i,j,k)+X(j,i,k))=1)); !kendala 2; @for(team(i): @for(round(k): @sum(team(j)|i#ne#j:X(i,j,k)+X(j,i,k))=1)); !KENDALA 3; @for(round(k)|k#lt#9: @for(team(i): @sum(team(j)|i#ne#j:X(i,j,k)+X(i,j,k+1))<=1+Y(i,k))); !KENDALA 4; @for(team(i): @SUM(round(k)|k#lt#9:Y(i,k))<=1); !KENDALA 5; @for(round(k)|k#lt#9: @for(team(i): @sum(team(j)|i#ne#j:X(j,i,k)+X(j,i,k+1))<=1+W(i,k))); !KENDALA 6; @for(team(i): @sum(round(k)|k#lt#9:W(i,k))<=1); !kendala 7; @for(team(i):
20
@sum(team(j)|i#ne#j:@sum(round(k)|k#eq#1:X(i,j,k)))+Bf(i)=@sum(team( j)|i#ne#j:@sum(round(k)|k#eq#9:X(i,j,k)))+Bl(i)); !kendala 7.1; @for(team(i):Bf(i)+Y(i,8)<=1); !kendala 7.2; @for(team(i):Bf(i)+W(i,1)<=1); !kendala 7.3; @for(team(i):Bl(i)+W(i,8)<=1); !kendala 7.4; @for(team(i):Bl(i)+Y(i,1)<=1); !kendala 8; @for(round(k)|k#ge#1#and#k#le#3: @sum(team(i)|i#ge#1#and#i#le#4:@sum(team(j)|j#ge#1#and#j#le#4#and#i# ne#j:X(i,j,2*k+1)))=2); !kendala 9; @for(team(i):@for(round(k)|k#lt#9: @sum(team(j)|j#ge#1#and#j#le#3:X(i,j,k))+@sum(team(j)|j#ge#1#and#j#l e#3:X(i,j,k+1))+@sum(team(j)|j#ge#1#and#j#le#3:X(j,i,k))+@sum(team(j )|j#ge#1#and#j#le#3:X(j,i,k+1))<=1)); !kendala 10; @for(team(i)|i#ge#5#and#i#le#10: @sum(team(j)|j#ge#1#and#j#le#2:@sum(round(k):X(i,j,k)))=1); !kendala 11; @for(team(i)|i#ge#1#and#i#le#4:@sum(team(j)|i#ne#j#and#j#ge#1#and#j# le#4:@sum(round(k):X(i,j,k)))>=1); @FOR(LINKS:@BIN(X)); @FOR(LINKS2:@BIN(Y)); @FOR(LINKS2:@BIN(W)); @for(team(i):@BIN(Bf(i))); @for(team(i):@BIN(Bl(i))); END
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Brasil
21
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Argentina
Uruguay
Chile
Paraguay
22
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Kolombia
Peru
Bolivia
Venezuela
23
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Ekuador
Global optimal solution found at iteration: Objective value:
548573 39.00000
Model Title: Pola Penjadwalan Sepak Bola babak Kualifikasi Piala Dunia 2014
V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V(
Variable BF( 9) BL( 2) 1, 1, 1) 1, 1, 2) 1, 1, 3) 1, 1, 4) 1, 1, 5) 1, 1, 6) 1, 1, 7) 1, 1, 8) 1, 1, 9) 1, 2, 1) 1, 2, 2) 1, 2, 4) 1, 2, 6) 1, 2, 8) 1, 2, 9) 1, 3, 1) 1, 3, 2) 1, 3, 4) 1, 3, 6) 1, 3, 8) 1, 3, 9) 1, 4, 1) 1, 4, 2) 1, 4, 4) 1, 4, 6) 1, 4, 8) 1, 4, 9) 1, 5, 1) 1, 5, 2)
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
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
24
V( 1, 5, V( 1, 5, V( 1, 5, V( 1, 5, V( 1, 5, V( 1, 5, V( 1, 5, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 6, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 7, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 8, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 9, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 1, 10, V( 2, 1, V( 2, 1,
3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2)
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 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 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
25
V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V(
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8,
4) 6) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2)
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 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 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
26
V( 2, 8, V( 2, 8, V( 2, 8, V( 2, 8, V( 2, 8, V( 2, 8, V( 2, 8, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 9, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 2, 10, V( 3, 1, V( 3, 1, V( 3, 1, V( 3, 1, V( 3, 1, V( 3, 1, V( 3, 2, V( 3, 2, V( 3, 2, V( 3, 2, V( 3, 2, V( 3, 2, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 3, V( 3, 4, V( 3, 4, V( 3, 4, V( 3, 4, V( 3, 4, V( 3, 4, V( 3, 5, V( 3, 5,
3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2)
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 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 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
27
V( 3, 5, V( 3, 5, V( 3, 5, V( 3, 5, V( 3, 5, V( 3, 5, V( 3, 5, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 6, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 7, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 8, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 9, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 3, 10, V( 4, 1, V( 4, 1,
3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2)
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 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 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
28
V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V(
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8,
4) 6) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 4) 6) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2)
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 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 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
29
V( 4, 8, V( 4, 8, V( 4, 8, V( 4, 8, V( 4, 8, V( 4, 8, V( 4, 8, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 9, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 4, 10, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 1, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 2, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 3, V( 5, 4,
3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
30
V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 4, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 5, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 6, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 7, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 8, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 9, V( 5, 10,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
31
V( 5, 10, V( 5, 10, V( 5, 10, V( 5, 10, V( 5, 10, V( 5, 10, V( 5, 10, V( 5, 10, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 1, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 2, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 3, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 4, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 5, V( 6, 6,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
32
V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 6, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 7, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 8, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 9, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 6, 10, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 1, V( 7, 2,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
33
V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V(
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
34
V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 8, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 9, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 7, 10, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 1, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 2, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 3, V( 8, 4,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
35
V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 4, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 5, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 6, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 7, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 8, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 9, V( 8, 10,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
36
V( 8, 10, V( 8, 10, V( 8, 10, V( 8, 10, V( 8, 10, V( 8, 10, V( 8, 10, V( 8, 10, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 1, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 2, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 3, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 4, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 5, V( 9, 6,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
37
V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 6, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 7, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 8, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 9, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 9, 10, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 1, V( 10, 2,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
38
V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V( V(
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1)
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 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 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
39
V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 8, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 9, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, V( 10, 10, X( 1, 2, X( 1, 7, X( 1, 8, X( 1, 10, X( 2, 3, X( 2, 5, X( 2, 6, X( 2, 9, X( 3, 1, X( 3, 5, X( 3, 7, X( 3, 9, X( 3, 10, X( 4, 1, X( 4, 2, X( 4, 3, X( 4, 8, X( 5, 1, X( 5, 4, X( 5, 6, X( 5, 8, X( 6, 1, X( 6, 3, X( 6, 4, X( 6, 7, X( 6, 10, X( 7, 2, X( 7, 4,
2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 1) 2) 3) 4) 5) 6) 7) 8) 9) 5) 8) 2) 6) 3) 8) 6) 1) 7) 1) 2) 4) 9) 3) 7) 5) 8) 4) 6) 2) 7) 1) 8) 9) 5) 3) 4) 1)
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 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 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 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.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
40
X( 7, 5, X( 7, 9, X( 7, 10, X( 8, 2, X( 8, 3, X( 8, 6, X( 8, 7, X( 8, 10, X( 9, 1, X( 9, 4, X( 9, 5, X( 9, 6, X( 9, 8, X( 10, 2, X( 10, 4, X( 10, 5, X( 10, 9, Y( 1, Y( 2, Y( 3, Y( 4, Y( 5, Y( 6, Y( 7, Y( 8, Y( 9, Y( 10, W( 1, W( 2, W( 3, W( 4, W( 5, W( 6, W( 7, W( 8, W( 9, W( 10,
9) 6) 7) 9) 6) 4) 3) 1) 9) 2) 3) 7) 5) 2) 4) 5) 8) 5) 3) 1) 7) 6) 8) 6) 3) 2) 4) 3) 4) 5) 1) 8) 6) 2) 7) 5) 6)
Row 2 3 4 . . . 196 197 199 200 201 204 205 206 207
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 Slack or Surplus 0.000000 0.000000 0.000000 . . . 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.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 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 Dual Price 0.000000 0.000000 0.000000 . . . 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
41
208 209 210 . . . 236 238 239 240 242 243 244 245 246 247 248 250 . . . 279 280 281 282 283 284 285 286 287 288 289 291 . . . 314 315 316 317 318 319 321 322 323 324 325 . . . 367 368 369 370
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
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
42
412 413 414 418 419 420 . . . 500 501 502 503
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