PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor ERLIYANA

PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor

ERLIYANA

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

ABSTRACT ERLIYANA. Courses Scheduling Using Integer Nonlinear Programming. A Case Study of Bina Sarana Informatika Bogor. Supervised by PRAPTO TRI SUPRIYO and FARIDA HANUM. This research aims to formulate courses scheduling based on lecturers’ and students’ preferences and other constraints. The model used is Integer Nonlinear Programming (INLP), with lecturers’ and students’ preferences are represented by course weights. The smaller weights of subjects indicate that their preferences are more prefered. This model is implemented to schedule courses of 5th semester classes at the Academy of Bina Sarana Informatika Bogor. The solution of this model is carried out using Lingo 8.0. The result shows that the schedule fulfill 98,57% preferences of regular students, 100% of extension students, and 100% of lecturers.

ABSTRAK ERLIYANA. Penjadwalan Mata Kuliah Menggunakan Integer Nonlinear Programming. Studi Kasus di Bina Sarana Informatika Bogor. Dibimbing Oleh PRAPTO TRI SUPRIYO dan FARIDA HANUM. Tujuan penelitian ini adalah membuat model penjadwalan mata kuliah berdasarkan preferensi dosen dan mahasiswa dan memenuhi berbagai kendala lain. Model yang digunakan adalah Integer Nonlinear Programming (INLP), sedangkan preferensi dosen dan mahasiswa direpresentasikan dengan suatu bobot. Bobot mata kuliah yang lebih kecil menandakan bahwa preferensinya lebih diutamakan. Model penjadwalan yang telah disusun diimplementasikan untuk menyusun jadwal mata kuliah semester 5 di Akademi Bina Sarana Informatika. Solusi yang diperoleh dari penyelesaian model dengan menggunakan Lingo 8.0 untuk studi kasus yang dilakukan adalah jadwal mata kuliah yang memenuhi 98,57% keinginan mahasiswa reguler, 100% keinginan mahasiswa ekstensi, dan 100% keinginan dosen.

PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor

ERLIYANA

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

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

Judul

: Penjadwalan Mata kuliah Menggunakan Integer Nonlinear Programming: Studi Kasus di Bina Sarana Informatika Bogor Nama : Erliyana NIM : G54050056

Menyetujui,

Pembimbing I

Pembimbing II

Drs. Prapto Tri Supriyo, M.Kom. NIP. 19630715 199002 1 002

Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002

Mengetahui: Ketua Departemen

Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004

Tanggal Lulus :

KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT atas berkat, rahmat dan kasih sayang-Nya sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga banyak sekali orang yang membantu dan berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1. Sang pencipta, Tuhan semesta alam Allah SWT, atas maha karya-Nya yaitu bumi yang sempurna ini; 2. nabi besar Muhammad SAW sebagai penutup para nabi; 3. keluarga tercinta: bapak dan ibu, ibu sebagai pemberi motivasi dan bapak sebagai sumber inspirasi, untuk Istiajid yang selalu memberikan semangat dan doa. 4. Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, semangat dan doa; 5. Dra. Farida Hanum, M.Si. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya; 6. Dr. Ir. Amril Aman, M.Sc. selaku dosen penguji yang telah memberikan ilmu, saran dan doanya; 7. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan; 8. staf Departemen Matematika: Bapak Yono, Bapak Hery, Bapak Deni, Ibu Ade, Bapak Epul, Bapak Bono dan Ibu Susi atas semangat dan doanya, 9. Raka yang selalu setia mendampingi, memberi dukungan, dan doa, 10. sahabat yang selalu memberi semangat: Niken, Idha, Oby, Eyyi, Jane, 11. teman-teman yang mengajarkan Lingo: Apri, Dj, Bima, 12. teman yang selalu memberi motivasi dan bantuan: Dio, Erpan, 13. Andri yang membantu dalam pembuatan abstrak, 14. semua teman Matematika 42 yang selalu menjadi contoh yang baik, 15. semua teman Matematika 43 yang selalu menjadi bagian dari keluarga, 16. semua teman Matematika 44 yang selalu mendukung agar terus berkembang, 17. teman satu pembimbing: Yudi, Slamet, Zil, 18. Gumatika yang telah mengasah pribadi ini menjadi pribadi yang tangguh, 19. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat.

Bogor, Juni 2011

Erliyana

RIWAYAT HIDUP Penulis dilahirkan di Bogor pada 10 Maret 1987 sebagai anak pertama dari dua bersaudara, anak dari pasangan Mochammad Yahya Permana dan Usmanah. Pada tahun 1999 penulis lulus dari SD Negeri Gunung Batu 01 Bogor kemudian tahun 2002 lulus dari SLTP Negeri 06 Bogor. Tahun 2005 penulis lulus dari SMA Negeri 6 Bogor dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB). Pada tahun 2007, penulis memilih Mayor Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis aktif dalam mengajar Matematika bimbingan belajar privat maupun kelompok mahasiswa dan siswa SMA. Penulis aktif dalam organisasi kemahasiswaan di kampus, seperti organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai anggota Departemen KEWIRAUSAHAAN tahun 2006/2007 dan kepala divisi Departemen KEWIRAUSAHAAN tahun 2007/2008. Selain itu, penulis juga terlibat dalam beberapa kegiatan, antara lain koordinator Humas Try-Out Pengantar Matematika mahasiswa IPB 2007, koordinator dekorasi Masa Pengenalan Departemen Matematika 2008, koordinator Dekorasi dan Dokumentasi Matematika Ria dalam acara Pesta Sains se-Indonesia 2009. Pada tahun 2009 penulis mencoba untuk mengajar di SMP/SMK Nusantara Mandiri dan beberapa lembaga bimbingan belajar.

DAFTAR ISI Halaman DAFTAR TABEL

viii

DAFTAR GAMBAR

viii

DAFTAR LAMPIRAN

viii

I

PENDAHULUAN 1.1 Latar Belakang 1.2 Tujuan

1 1

II LANDASAN TEORI 2.1 Pemrograman Linear 2.2 Integer Programming 2.3 Nonlinear Programming 2.4 Integer Nonlinear Programming 2.5 Metode Branch and Bound

1 3 3 4 5

III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah 3.2 Formulasi Masalah 3.3 Model Matematika

9 9 10

IV PENYELESAIAN MASALAH PENJADWALAN MATA KULIAH

11

V SIMPULAN DAN SARAN 5.1 Simpulan 5.2 Saran

16 16

DAFTAR PUSTAKA

16

LAMPIRAN

17

vii

DAFTAR TABEL 1 2 3 4 5

Subproblem-subproblem masalah INLP (10) Pencabangan Subproblem P(X1) Pencabangan Subproblem P ( X 13 ) Pencabangan Subproblem P(X2) Pencabangan Subproblem P( X 22 )

Halaman 7 7 7 8 8

6 Pencabangan Subproblem P( X 23 ) 7 8 9 10 11 12 13 14

4 2

8

Pencabangan Subproblem P( X ) Daftar mata kuliah semester lima di AMIK Ruangan yang tersedia Periode hari Periode waktu Daftar kelompok Daftar dosen Jadwal kegiatan belajar mengajar untuk program regular Akademi Manajemen Informatika dan Komunikasi BSI Bogor 15 Jadwal kegiatan belajar mengajar untuk program ekstensi Akademi Manajemen Informatika dan Komunikasi BSI Bogor

8 11 12 12 12 12 12 15 15

DAFTAR GAMBAR Halaman 6 1 Daerah fisibel (daerah yang diarsir) untuk NPL-relaksasi dari INLP (10). 6 2 Daerah fisibel subproblem P(X1) dan subproblem P(X2). 3 Bobot suatu mata kuliah yang diharapkan diajarkan di awal periode waktu untuk mahasiswa 10 program regular. 4 Bobot suatu mata kuliah yang diharapkan diajarkan di akhir periode waktu untuk mahasiswa 10 program ekstensi. 5 Bobot mata kuliah Pemrograman Visual FOXPRO (K) yang diharapkan diajarkan di awal 13 periode waktu untuk mahasiswa program regular. 6 Bobot mata kuliah Pemrograman Visual FOXPRO (P) yang diharapkan diajarkan di akhir 13 periode waktu untuk mahasiswa program ekstensi.

DAFTAR LAMPIRAN Halaman 18 1 Syntax Program LINGO 8.0 dalam mencari nilai awal solusi fisibel Contoh 2 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Taklinear dengan 18 Metode Branch-and-Bound Beserta Hasil yang Diperoleh 3 Program untuk menyelesaikan masalah penjadwalan kegiatan belajar mengajar di Akademi 23 Manajemen Informatika dan Komunikasi BSI Bogor.

viii

1

I PENDAHULUAN 1.1 Latar Belakang Salah satu bagian penting yang tidak dapat dipisahkan dalam sekolah tinggi dan universitas adalah masalah penjadwalan mata kuliah dengan kendala waktu yang diinginkan (preferensi) dosen, mahasiswa, dan banyaknya ruangan yang terbatas. Oleh sebab itu perlu dibuat sebuah penjadwalan mata kuliah yang memenuhi semua kendala dan memuaskan semua pihak. Bina Sarana Informatika (BSI) merupakan salah satu perguruan tinggi yang menyelenggarakan program regular dan ekstensi. Program regular diselenggarakan pada waktu pagi atau siang hari, sedangkan program ekstensi diselenggarakan pada waktu sore atau malam hari. Setiap mahasiswa dan dosen mempunyai preferensi hari dan periode waktu dalam pelaksanaan kuliah. Atas dasar ini, masalah penjadwalan mata kuliah akan dibuat.

Permasalahan penjadwalan mata kuliah ini dapat dimodelkan sebagai masalah Integer Nonlinear Programming (INLP). INLP adalah suatu model pemrograman matematika dimana variabel keputusan berupa bilangan integer dengan fungsi objektif atau kendalanya nonlinear. Tulisan ini merupakan rekontruksi dari artikel A 0-1 integer programming approach to a university timetabling problem yang ditulis oleh M Akif Bakir dan Cihan Askop. 1.2 Tujuan Tujuan dari karya ilmiah ini adalah memodelkan masalah penjadwalan mata kuliah yang meminimumkan ketidakpuasan mahasiswa dan dosen di Bina Sarana Informatika (BSI) Bogor ke dalam bentuk INLP. Selanjutnya model diselesaikan dengan bantuan software LINGO 8.0.

II LANDASAN TEORI Berikut ini akan dijelaskan definisi dan teori yang terkait dengan Integer Nonlinear Programming (INLP). 2.1 Pemrograman Linear Fungsi linear dan pertidaksamaan linear merupakan salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear. Definisi 1 (Fungsi Linear) dalam Suatu fungsi f ( x1 , x 2 ,..., x n ) variabel-variabel x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c2 ,..., cn , f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston 2004) Sebagai contoh, f ( x1 , x2 ) = 3x1 + 4 x2 merupakan fungsi linear, sementara f ( x1 , x2 ) = x12 x 22 bukan fungsi linear. Definisi 2 (Pertidaksamaan dan Persamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b , pertidaksamaan atau f ( x1 , x 2 ,..., x n ) ≤ b

f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear. Misalkan b sembarang bilangan, suatu persamaan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear. (Winston 2004)

Pemrograman linear (PL) atau linear programming (LP) adalah suatu masalah optimisasi yang memenuhi ketentuanketentuan sebagai berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel xi , pembatasan tanda menentukan xi harus taknegatif ( xi ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004)

2

Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar PL) Suatu PL dikatakan berbentuk standar jika berbentuk: min z = cT x terhadap Ax = b (1) x≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga matriks kendala. (Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimum bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan masalah PL. Metode ini berupa metode iteratif untuk menyelesaikan masalah PL berbentuk standar. Pada masalah PL (1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (1). Misalkan matriks A dinyatakan sebagai A = ( B N ) , dengan B adalah matriks taksingular berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n − m) yang elemen-elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (1). Misalkan x dinyatakan sebagai vektor ⎛x ⎞ x = ⎜ B ⎟ , dengan xB adalah vektor variabel ⎝ xN ⎠ basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan ⎛x ⎞ sebagai Ax = ( B N ) ⎜ B ⎟ ⎝ xN ⎠

= BxB + NxN = b.

(2)

Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: x B = B -1b − B -1 Nx N . Kemudian, fungsi objektifnya menjadi:

(3) berubah

min z = c B x B + c N x N . T

T

Definisi 4 (Daerah Fisibel) Daerah fisibel suatu masalah PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada masalah PL tersebut. (Winston 2004) Definisi 5 (Solusi Basis) Solusi dari suatu masalah PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala pada masalah PL; ii. kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer 1996) Definisi 6 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0. (Nash & Sofer 1996) Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan masalah PL berikut: min z = −3 x1 − 2 x2 , − 2 x1 + x2 + x3 = 3,

terhadap

− x1 + 2 x2 + x4 = 8,

(4)

x1 + x5 = 5, x1 , x2 , x3 , x4 , x5 ≥ 0. Dari PL tersebut diperoleh: ⎛ −2 1 1 0 0 ⎞ ⎛ 3⎞

A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜ 8 ⎟ . ⎜ ⎟ ⎜ ⎟ ⎝ 1 0 0 0 1⎠ ⎝ 5⎠

Misalkan dipilih x B = ( x3

x4

T

x5 )

dan x N = ( x1

maka matriks basisnya adalah

T

x2 )

,

3

⎛1 0 0⎞ ⎛1 -1 ⎜ ⎜ ⎟ B= 0 1 0 , B = 0 ⎜ ⎟ ⎜ ⎝0 0 1⎠ ⎝0 ⎛ -2 1 ⎞ N = ⎜ -1 2 ⎟ ⎜ ⎟ ⎝1 0 ⎠ cTB = (3 8 5) , cTN = ( 0 Dengan menggunakan tersebut, diperoleh x N = ( 0 0)

T

0 0⎞ 1 0⎟ ,

⎟

0 1⎠

0) .

matriks

basis

,

x B = B b = ( 3 8 5) -1

T

(5)

z = cTB B -1b = −25

Solusi (5) merupakan solusi basis, karena memenuhi kendala pada masalah PL (4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5), yaitu B 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. Hal yang juga penting dalam konsep pemrograman linear untuk model ini adalah daerah fisibel dan solusi optimum yang didefinisikan sebagai berikut. Definisi 7 (Solusi Optimum) Untuk masalah maksimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.2 Integer Programming Integer programming (IP) atau pemrograman integer adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming (MIP). IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser 1972)

Definisi 8 (Pemrograman Linear Relaksasi) Pemrograman linear relaksasi atau sering disebut PL-relaksasi merupakan suatu pemrograman linear yang diperoleh dari suatu IP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimum fungsi objektif PL-relaksasi lebih besar atau sama dengan nilai optimum fungsi objektif IP, sedangkan untuk masalah minimisasi, nilai optimum fungsi objektif PLrelaksasi lebih kecil atau sama dengan nilai optimum fungsi objektif IP. (Winston 2004) 2.3 Nonlinear Programming Model nonlinear programming (NLP) meliputi pengoptimuman suatu kondisi berikut : a) fungsi objektif nonlinear terhadap kendala linear, b) fungsi objektif nonlinear terhadap kendala nonlinear, c) fungsi objektif nonlinear dan takberkendala. (Sharma 2006) Definisi 9 (bentuk umum suatu NLP) Bentuk umum suatu nonlinear programming adalah : max (atau min) z = f(x1, x2, ..., xn) terhadap kendala: g1(x1, x2, ..., xn) (≤, =, ≥) b1 g2(x1, x2, ..., xn) (≤, =, ≥) b2

M

gm(x1, x2, ..., xn) (≤, =, ≥) bm

(6)

Komponen x1, x2, ..., xn merupakan variabel keputusan dan b1, b2, ..., bm adalah konstanta. f(x1, x2, ..., xn) adalah fungsi objektif dan gj(x1, x2, ..., xn) menyatakan fungsi-fungsi kendala persamaan atau pertaksamaan, dengan j = 1, 2, …, m. Jika bentuk umum memiliki kendala, maka masalah (6) dinamakan masalah nonlinear programming berkendala. Jika bentuk umum tidak memiliki kendala, maka masalah (6) dinamakan masalah nonlinear programming takberkendala. (Winston 2004) 2.3.1 Konsep Dasar NLP Untuk menyelesaikan suatu masalah nonlinear programming diperlukan konsep

4

dasar, yaitu gradien dan matriks Hesse fungsi banyak variabel. Vektor Gradien dan Matriks Hesse Misalkan f adalah fungsi dari n variabel x1 , x2 ,..., xn (biasa dituliskan dengan f ( x ) = f ( x1 , x2 ,..., xn ) dan terdiferensialkan dua kali secara kontinu, dan dinyatakan dengan f ∈ C 2 . Untuk f ∈ C 2 didefinisikan vektor gradien fungsi f di titik x adalah ⎛ ∂f ⎞ ⎜ ∂x (x) ⎟ ⎜ 1 ⎟ ⎜ ∂f ⎟ ( x) ⎟ ⎜ ∇f (x) = ⎜ ∂x2 ⎟ ⎜ M ⎟ ⎜ ⎟ ⎜ ∂f (x) ⎟ ⎜ ∂x ⎟ ⎝ n ⎠ Jika fungsi terdiferensialkan secara kontinu dua kali maka di titik x terdapat matriks turunan parsial yang disebut matriks Hesse (Hessian matrix) ⎧⎪ ∂ 2 f (x) ⎫⎪ 2 H ( x) = ⎨ ⎬ = ∇ f ( x) ∂ x ∂ x ⎩⎪ i j ⎭⎪ ⎛ ∂ f (x) ⎜ 2 ⎜ ∂x1 ⎜ 2 ⎜ ∂ f (x) = ⎜ ∂x2 ∂x1 ⎜ ⎜ M ⎜ 2 ⎜ ∂ f (x) ⎜ ⎝ ∂xn ∂x1 2

∂ f ( x) ∂ f ( x) ⎞ L ⎟ ∂x1∂x2 ∂x1∂xn ⎟ ⎟ ∂ 2 f ( x) ∂ 2 f ( x) ⎟ K ∂x2 ∂xn ⎟ ∂x2 2 ⎟ M O M ⎟ ⎟ ∂ 2 f ( x) ∂ 2 f ( x) ⎟ L ∂xn ∂x2 ∂xn 2 ⎟⎠ 2

2

2.3.2 Fungsi Konveks dan Fungsi Konkaf Definisi 10 (Fungsi Konveks dan Konkaf) Fungsi f dikatakan fungsi konveks pada selang I jika hanya jika f (λ x1 + (1 − λ ) x2 ) ≤ λ f ( x1 ) + (1 − λ ) f ( x2 ), untuk setiap x1 , x2 ∈ I dan untuk setiap 0 ≤ λ ≤ 1 . Fungsi f dikatakan fungsi konkaf pada selang I jika hanya jika f (λ x1 + (1 − λ ) x2 ) ≥ λ f ( x1 ) + (1 − λ ) f ( x2 ), untuk setiap x1 , x2 ∈ I dan untuk setiap 0 ≤ λ ≤ 1 . (Ecker & Kupferschmid 1998) 2.3.3 Pengoptimuman Berkendala Metode yang dapat digunakan dalam menyelesaikan pengoptimuman berkendala di antaranya adalah metode iteratif (metode

penalti) dan metode analitik (pengali Lagrange dan kondisi Karush-Kuhn-Tucker). Di bawah ini akan dibahas salah satu metode penyelesaian untuk pengoptimuman berkendala. Kondisi Karush-Kuhn-Tucker (KKT) Misalkan diberikan pengoptimuman kendala pertidaksamaan, maka salah satu alternatif penyelesaian adalah dengan mengubah semua pertaksamaan menjadi persamaan dengan menambah variabel tambahan, seperti: g ( x) ≤ 0 → g ( x) + y = 0 Namun dengan cara ini tidak efektif jika terlalu banyak kendala yang harus diubah karena mengakibatkan bertambah banyak variabel keputusan yang harus dilibatkan. Teknik lain untuk menyelesaikan masalah tersebut adalah dengan menggunakan kondisi Karush-Kuhn-Tucker. Misalkan diberikan masalah pengoptimuman: min f ( x) … (8) terhadap g j ( x ) = 0, j = 1, 2, ..., m − 1 g j ( x ) ≤ 0, j = m, ..., p dan x ∈ R

n

dengan f dan gj merupakan fungsi-fungsi yang mempunyai turunan pertama yang kontinu. Didefinisikan fungsi Lagrange L(x,λ) = f(x) +

m

∑λ g j =1

j

j

( x)

Karush (1939) dan Kuhn dan Tucker (1951) secara terpisah menurunkan syarat perlu yang harus dipenuhi oleh solusi (minimizer) x* dari masalah (8), yang disebut kondisi KKT, yaitu n

terdapat λ * ∈ R sehingga: m ∂g j ∂f (x*) + ∑ λ *j (x*) = 0, i = 1, 2,..., l 1. ∂xi ∂xi j =1 2. g j (x*) ≤ 0, j = m,..., p 3. λ *j g j (x*) = 0, j = m,..., p 4. λ *j ≥ 0, j = m,..., p dengan λ * pengali Lagrange. Kondisi di atas dapat menjadi syarat cukup untuk strong global minimizer x* jika f dan gj merupakan fungsi konveks. (Snyman 2005) 2.4 Integer Nonlinear Programming Model integer nonlinear programming (INLP) merupakan suatu model pemrograman matematika di mana variabel keputusan

5

berupa bilangan integer dengan fungsi objektif atau kendalanya nonlinear. (Ecker & Kupferschmid 1998) Bentuk umum dari masalah nonlinear programming (INLP) sebagai berikut: min f ( x)

integer adalah

terhadap gi (x) ≤ bi , i = 1, 2,..., m (9)

hk (x) = ck , k = 1, 2,..., l

n x ∈ X ⊆ Z

dengan f ( x ) , gi (x) , hk (x) merupakan fungsi n

n

bilangan real pada R dan Z merupakan n

himpunan nilai-nilai integer di R . x° Î X adalah solusi fisibel pada masalah (9) jika g i ( x°) £ bi , untuk semua i = 1,..., m dan hk ( x°) = ck , untuk semua k = 1,..., l . Sebuah

solusi fisibel x* dinamakan solusi optimal pada masalah (9) jika f ( x*) £ f ( x ) untuk semua solusi fisibel x pada masalah (9). Setiap menyelesaikan masalah INLP dilakukan relaksasi untuk melepaskan nilai x yang bernilai integer. Penyelesaian masalah relaksasi pada nonlinear programming, di antaranya menggunakan kondisi Karush Kuhn Tucker (KKT) dan metode global descent. 2.5 Metode Branch-and-Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimum dari masalah INLP digunakan software LINGO 8.0 yaitu sebuah program yang didesain untuk menentukan solusi model linear, nonlinear, dan optimisasi integer. Software LINGO 8.0 ini menggunakan metode branch and bound untuk menyelesaikan masalah IP atau INLP. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah (9) dengan memartisi ruang pencarian, dilakukan dengan membagi daerah fisibel ke dalam p himpunan bagian X1, X2,…, Xp dengan p ≥ 2 . • Branch Branching (pencabangan) adalah proses membagi-bagi permasalahan menjadi subproblem-subproblem yang mungkin mengarah ke solusi. • Bound Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas

atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum pada subproblem yang mengarah ke solusi. Metode branch-and-bound untuk masalah minimisasi diawali dengan membuat subproblem-subproblem. Sebuah subproblem pada node i, (P(Xi)), i=1,…, p adalah bentuk dari masalah (9) dengan menggantikan X dengan Xi. Satu atau lebih subproblem dipilih dari daftar subproblem yang ada. Untuk setiap node dipilih sebuah batas bawah LBi dari nilai yang optimal subproblem (P(Xi)) diperkirakan. Jika LBi lebih besar atau sama dengan nilai fungsi objektif dari nilai awal maka kandidat solusi fisibel terbaik telah ditemukan, kemudian subproblem (P(Xi)) dieliminasi dari pertimbangan selanjutnya. Jika tidak, masalah (P(Xi)) disimpan dalam daftar subproblem. Nilai awal diperbarui setiap kali sebuah solusi fisibel terbaik ditemukan. Satu dari node yang tidak dieliminasi, (P(Xi)), dipilih untuk dilakukan pencabangan (branching) menjadi subproblem yang lebih kecil. Proses ini diulang sampai tidak ada subproblem yang tersisa dalam daftar. Berikut ini adalah langkah-langkah penyelesaian suatu masalah minimisasi dengan metode branch-and-bound. Misalkan diberikan masalah INLP (9). • Langkah 0 (Inisialisasi) Didefinisikan L = {P(X)} sebagai subproblem dari fungsi INLP, x* dan v* = f (x) sebagai kandidat solusi optimum masalah INLP. Jika tidak ada solusi fisibel yang tersedia, maka dimisalkan v* = +∞ dan i = 0. • Langkah 1 (Pemilihan node) Jika L = ∅ , proses berhenti dan x* adalah solusi optimum INLP. Jika tidak, pilih salah satu atau lebih subproblem {P(X)} dari L sebagai bagian masalah berikutnya untuk diperiksa. Dinotasikan k sebagai banyaknya subproblem yang dipilih dari Ls = {P(X1),... s P(Xk)}. Misalkan L := L \ L ; i = 1. • Langkah 2 (Bounding) Subproblem P ( X i ) diselesaikan sehingga didapatkan batas bawah LBi . LBi P(X)

takfisibel.

Jika

LBi

≥

=

+∞ jika

v*

proses

6

dilanjutkan ke Langkah 5. Jika tidak, proses dilanjutkan ke Langkah 3.

Daerah fisibel

• Langkah 3 (Solusi fisibel) Simpan solusi fisibel yang ditemukan pada Langkah 2 atau temukan solusi fisibel yang lebih baik dari metode heuristik tertentu. Perbarui kandidat solusi optimal x* dan v*. Jika solusi INLP yang diperoleh lebih baik dari solusi fisibel yang diperoleh sebelumnya, LB j

≥

s

P ( X i ) dari

eliminasi

L yang

memenuhi

v * ; 1 ≤ j < i. Jika i < k ; i = i + 1 maka

Langkah 2 diulangi. Jika tidak, proses dilanjutkan ke Langkah 4 untuk melakukan pencabangan P ( X i ) . •

Langkah 4 (Branching) s

Jika L = ∅ , kembali ke Langkah 1. Jika tidak pilih salah satu subproblem P(Xi) dari s

L dan X i dibagi menjadi subset yang lebih s

s

p

kecil Li = { X 1 ,..., X i }. Eliminasi P(Xi) dari s

Ls dan misalkan L := L U L U Li . Kembali ke s

Langkah 1. •

Langkah 5 (Fathoming) s

Eliminasi P ( X i ) dari L . Jika i < k dengan i = i + 1 maka kembali ke Langkah 2. Jika tidak, kembali ke Langkah 4. (Li & Sun 2006)

Untuk memudahkan pemahaman mengenai metode branch-and-bound diberikan contoh sebagai berikut.

x12 + x2 2

P(X2)

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 , x2 ≥ 0

Langkah awal metode branch and bound adalah menentukan daftar subproblem L = {P(X)} dari kendala yang ada. Solusi yang didapatkan masalah (10) belum memenuhi syarat integer, maka dimisalkan v* = +∞ . Karena L ≠ ∅ maka dibuat subproblemsubproblem baru, dimisalkan sebanyak k = 2 yang memenuhi kendala masalah INLP (10). Subproblem-subproblem tersebut dinotasikan Ls={P(X1), P(X2)}, didefinisikan sebagai berikut: • Subproblem P(X1): masalah INLP (10) ditambah kendala 0 ≤ x2 ≤ 2 ; • Subproblem P(X2): masalah INLP (10) ditambah kendala 2 ≤ x2 ≤ 4 Hal ini diilustrasikan secara grafis pada Gambar 2.

P(X1)

Contoh 2 Misalkan diberikan INLP berikut: 2 2 min v = 2 x1 + x2 − 2 x1 x2 − 5 x1 − 2 x2 terhadap

Gambar 1 Daerah fisibel (daerah yang diarsir) untuk NLP-relaksasi dari INLP (10).

(10)

x1 , x2 integer. Solusi optimum NLP-relaksasi dari masalah INLP (10) adalah x1 = 2.57 , x2 = 3.06 , dan v = − 12.13 (lihat Lampiran 1). Batas atas nilai optimum fungsi objektif masalah (10) adalah v = − 12.13. Daerah fisibel masalah (10) ditunjukkan pada Gambar 1. Solusi optimum berada di daerah fisibel yang berasal dari kendala pertidaksamaan masalah (10).

Gambar 2 Daerah fisibel subproblem P(X1) dan subproblem P(X2) Langkah selanjutnya adalah menghitung batas atas UBi setiap subproblem. UBi merupakan pendekatan nilai fungsi objektif yang terdapat pada subproblem (P(Xi)). Jika subproblem (P(Xi)) memiliki solusi tidak fisibel maka UBi = +∞. Penghitungan semua subproblem menggunakan software LINGO 8.0, ditulis pada Lampiran 2. Hasil semua

7

subproblem masalah INLP (10) ditulis dalam Tabel 1 di bawah ini: Tabel 1 Subproblem-subproblem masalah INLP (10) No Subproblem UBi x 1 P(X1) (2.25,2) −10.13 2 P(X2) (2.57,3.06) −12.13 Langkah berikutnya adalah bounding dan fathoming. Jika UBi ≥ v * maka eliminasi subproblem P(Xi). Perbarui nilai x* dan v* dengan solusi fisibel yang memiliki nilai fungsi objektif terkecil dan memenuhi kendala integer. Batas atas yang dihasilkan pada subproblem P(X1), UB1 = −10.13 tidak lebih dari v* dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalnya dipilih x1 sebagai dasar pencabangan dari subproblem P(X1). Pencabangan Subproblem P(X1) s 1 2 menghasilkan L1 = { P ( X 1 ), P ( X 1 ), P ( X 13 ), P ( X 14 ) }, yaitu:

• Subproblem P ( X ) : Subproblem P(X1) ditambah kendala 0 ≤ x1 ≤ 1 ; • Subproblem P ( X 12 ) : Subproblem P(X1) ditambah kendala 1 ≤ x1 ≤ 2 ; • Subproblem P ( X 13 ) : Subproblem P(X1) ditambah kendala 2 ≤ x1 ≤ 3 ; • Subproblem P ( X ) : Subproblem P(X1) ditambah kendala 3 ≤ x1 ≤ 4 Solusi dari hasil pencabangan Subproblem P(X1) ditunjukkan dalam Tabel 2. 4 1

Tabel 2 Pencabangan Subproblem P(X1) No Subproblem UBi x P ( X 11 ) 1 (1,2) −7 3 4

P ( X 12 )

(2,2)

−10

3 1

(2.25,2)

−10.125

4 1

(3,2)

−9

P( X ) P( X )

Pencabangan subproblem P ( X 13 ) didefinisikan L13.s = {P ( X 13.1 ), P ( X 13.2 )} , yaitu:

•

3.1

3

Subproblem P ( X 1 ) : Subproblem P ( X 1 ) ditambah kendala 0 ≤ x2 ≤ 1 ;

•

3

Subproblem P ( X 13.2 ) : Subproblem P ( X 1 )

ditambah kendala 1 ≤ x2 ≤ 2 ; Solusi dari hasil pencabangan Subproblem 3

1 1

2

yaitu dihasilkan Subproblem P ( X 12 ) 1 UB1 = −10 < v * , solusi yang dihasilkan memenuhi kendala integer dan lebih baik dari Subproblem P ( X 11 ) sehingga perbarui x* = (2,2) dan v* = −10 sebagai kandidat solusi optimum INLP. Dari Tabel 2, batas atas Subproblem P ( X 13 ) tidak memenuhi syarat eliminasi, karena UB13 = −10.125 < v * . Solusi yang dihasilkan tidak memenuhi kendala integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalnya x2 sebagai dasar pencabangan subproblem P ( X 13 ) .

Periksa setiap subproblem baru, jika UBi ≥ v * maka eliminasi subproblem (P(Xi)). Dari Tabel 2, solusi yang dihasilkan Subproblem P ( X 11 ) memenuhi kendala integer dan UB11 = −7 < v * , maka perbarui x* = (1,2) dan v* = −7 sebagai kandidat solusi optimum. Langkah selanjutnya adalah memeriksa Subproblem P ( X 12 ) . Batas atas yang

P ( X 1 ) ditunjukkan dalam Tabel 3. 3

Tabel 3 Pencabangan Subproblem P ( X 1 ) No 1

Subproblem P ( X 13.1 )

x (2,1)

2

P ( X 13.2 )

(2.25,2)

UBi −7 −10.125

Dari Tabel 3, batas atas Subproblem P ( X 13.1 ) memenuhi syarat eliminasi karena UB13.1 = −7 > v * , sedangkan batas atas subproblem P ( X 13.2 ) tidak tereliminasi karena UB13.2 = −10.125 < v * . Solusi yang dihasilkan Subproblem P ( X 13.2 ) tidak diperbarui karena tidak memenuhi kendala integer. Selain dari itu Subproblem P ( X 13.2 ) memiliki daerah fisibel yang tidak dapat dipartisi sehingga tidak dicabangkan lagi. Selanjutnya diperiksa Subproblem P ( X 14 ). Batas atas Subproblem P ( X 14 ) , yaitu UB14 = −9 > v * sehingga x* dan v* tidak diperbarui. Subproblem yang belum diperiksa, yaitu Subproblem P(X2). Batas atas Subproblem P(X2) adalah UB2 = −12.13 < v * dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dilakukan pencabangan. Hasil pencabangan Subproblem P(X2) didefinisikan Ls2 = {P ( X 21 ), P ( X 22 ), P ( X 23 ), P ( X 24 )} , yaitu:

8

• Subproblem P ( X 21 ) : Subproblem P(X2) ditambah kendala 0 ≤ x1 ≤ 1 ; • Subproblem P ( X 22 ) : Subproblem P(X2) ditambah kendala 1 ≤ x1 ≤ 2 ; • Subproblem P ( X 23 ) :

Subproblem P(X2)

ditambah kendala 2 ≤ x1 ≤ 3 ; • Subproblem P ( X 24 ) : Subproblem P(X2) ditambah kendala 3 ≤ x1 ≤ 4 . Solusi dari hasil pencabangan Subproblem P(X2) ditunjukkan dalam Tabel 4. Tabel 4 Pencabangan Subproblem P(X2) No Subproblem UBi x 1 P( X 2 ) 1 (1,2) −7 2 3 4

P ( X 22 )

(2,3.33)

−11

3 2

(2.57,3.06)

−12.13

4 2

(3,2.65)

−11.16

P( X ) P( X )

Periksa setiap subproblem baru, jika UBi ≥ v * maka eliminasi subproblem (P(Xi)). Dari Tabel 4, batas atas yang dihasilkan subproblem P ( X 12 ), yaitu UB21 = −7 > v*, sehingga x* dan v* tidak diperbarui. Batas atas P ( X 22 ) , P ( X 23 ) ,dan P ( X 24 ) tidak lebih dari v* dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dilakukan pencabangan dari setiap subproblem. Hasil pencabangan Subproblem P ( X 22 ) , yaitu: • Subproblem P ( X 22.1 ) : Subproblem P ( X 22 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 22.2 ) : Subproblem P ( X 22 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 22 ) ditunjukkan dalam Tabel 5. Tabel 5 Pencabangan Subproblem P ( X 22 ) No Subproblem UBi x 2.1 P ( X ) 1 (2,3) −11 2 2 P(X22.2) (2,3) −11 Dari Tabel 5, batas atas Subproblem dan P ( X 22.1 ) P ( X 22.2 ), UB2 2 = −11 < v * sehingga perbarui nilai x* dan v*. Subproblem P ( X 22.1 ) dan P ( X 22.2 ) memiliki daerah fisibel yang tidak dapat dipartisi, maka subproblem ini tidak dicabangkan lagi. Semua variabel subproblem P ( X 22.1 ) dan P ( X 22.2 ) bernilai integer (solusinya memenuhi kendala integer) dan solusi yang dihasilkan pada

subproblem ini lebih baik dari batas atas sebelumnya sehingga solusi pada subproblem ini menjadi kandidat batas atas baru dari solusi INLP (10) yaitu x* = (2,3), v* = −11 . Hasil pencabangan subproblem P ( X 23 ), yaitu: • Subproblem P ( X 23.1 ) : Subproblem P ( X 23 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 23.2 ) : Subproblem P ( X 23 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 23 ) ditunjukkan dalam Tabel 6. Tabel 6 Pencabangan Subproblem P ( X 23 ) No Subproblem UBi x P ( X 23.1 ) 1 (2.65,3) −12.10 2

P ( X 23.2 )

(2.57,3.06)

−12.13

Nilai batas bawah Subproblem P(X23.1), dan Subproblem UB2 3.1 = −12.10 < v * sehingga P(X23.2), UB2 3.2 = −12.13 < v * perbarui nilai x* dan v*. Akan tetapi, solusi yang dihasilkan tidak memenuhi kendala integer sehingga x* dan v* tidak diperbarui. Subproblem P ( X 23.1 ) dan P ( X 23.2 ) memiliki daerah fisibel yang tidak dapat dipartisi lagi, maka subproblem ini tidak dicabangkan. Langkah selanjutnya adalah memilih masalah yang belum diselesaikan, yaitu pencabangan Subproblem P ( X 24 ) . Hasil pencabangan Subproblem P ( X 24 ) , yaitu: • Subproblem P ( X 24.1 ) : Subproblem P ( X 24 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 24.2 ) : Subproblem P ( X 24 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 24 ) ditunjukkan dalam Tabel 7. Tabel 7 Pencabangan Subproblem P ( X 24 ) No Subproblem UBi x 4.1 P( X 2 ) 1 (3,2.65) −11.17 2

P ( X 24.2 )

Takfisibel

+∞

Nilai batas atas P ( X 24.1 ), UB2 4.1 = −11.17 < v*, sehingga tidak memenuhi syarat eliminasi. Akan tetapi, solusi yang dihasilkan tidak memenuhi kendala integer sehingga x* dan v* tidak diperbarui. Subproblem P ( X 24.1 ) memiliki daerah fisibel yang tidak

9

dapat dipartisi lagi, maka subproblem ini tidak dicabangkan. Subproblem P ( X 24.2 ) memenuhi syarat eliminasi, yaitu UBi ≥ v *. Karena subproblem pada percabangan ini tereliminasi maka x* dan v* tidak diperbarui. Semua subproblem sudah diperiksa dan tidak ada subproblem tersisa dalam daftar

sehingga L = ∅ . Subproblem P ( X 22.1 ) dan P ( X 22.2 ) menghasilkan solusi optimal yang berupa integer. Dengan demikian, solusi optimum pada masalah INLP (10) adalah x1* = 2, x2* = 3, v* = −11.

III PEMODELAN Model penjadwalan pada karya ilmiah ini menggunakan enam parameter utama sebagai penyusun jadwal yaitu; 1. Hari, yaitu hari di mana kegiatan perkuliahan diselenggarakan. Hari = {Senin, Selasa, …, Jumat}. 2. Periode waktu, yaitu waktu kuliah di mana mata kuliah diselenggarakan. Periode waktu = {08.00-08.45, 08.45-09.30, …, (tt+1)}. 3. Kelompok, yaitu kelompok mahasiswa yang menghadiri mata kuliah yang sama berdasarkan program kuliah yang telah tersedia. Kelompok program regular diselenggarakan pukul 08.00-16.00, sedangkan pukul 17.00-22.00 untuk program ekstensi. 4. Dosen, yaitu orang yang mengajar suatu mata kuliah tertentu dalam suatu kelas. Dosen = {Dosen 1, Dosen 2, …, Dosen l}. 5. Mata kuliah, yaitu pelajaran yang diajarkan di kelas oleh seorang dosen. Mata kuliah = {mata kuliah 1, mata kuliah 2, …, mata kuliah m}. 6. Ruangan, yaitu tempat berlangsungnya kegiatan perkuliahan. Ruangan = {ruangan 1, ruangan 2, …, ruangan n}. Jadwal tersebut dibuat sedemikian rupa sehingga memenuhi kendala utama dan kendala tambahan. Kendala utama dalam penjadwalan, yaitu: 1. Semua mata kuliah terjadwalkan di setiap semesternya. 2. Tidak ada overlapping mata kuliah. 3. Dosen tidak boleh mengajar lebih dari satu kelas pada periode waktu yang sama. Sedangkan kendala tambahan, yaitu : 1. Untuk mata kuliah yang tediri atas kuliah dan praktikum, jadwal kuliah dilaksanakan lebih dulu dari jadwal praktikum. 2. Setiap mata kuliah diselenggarakan pada periode waktu yang sesuai. Misalkan mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam.

3. Setiap dosen tidak mengajarkan mata kuliah yang bukan bidangnya. 4. Sebagian dosen berharap tidak mengajar pada waktu tertentu. Dalam model penjadwalan karya ilmiah ini terdapat koefisien (bobot) yang merupakan nilai dari ketidakpuasan yang diberikan oleh mahasiswa program regular dan ekstensi terhadap penjadwalan suatu mata kuliah. Penentuan besar kecilnya bobot ditentukan atas keinginan mahasiswa terhadap suatu mata kuliah yang akan dijadwalkan di awal atau di akhir periode waktu. Semakin kecil bobot maka peluang dijadwalkannya mata kuliah yang sesuai dengan keinginan mahasiswa semakin besar. Penentuan bobot yang disebutkan tidaklah mutlak. Bobot yang ada di sini hanyalah sebagai gambaran saja. Sebagai contoh : 1. Mahasiswa program regular mengharapkan mata kuliah dapat diajarkan di awal periode waktu. Oleh karena itu kepuasan mahasiswa ini diberi bobot (koefisien) yang kecil di awal periode waktu dan bobot yang besar di akhir periode waktu, sehingga mata kuliah ini memiliki peluang yang lebih besar untuk dijadwalkan di awal periode waktu (Gambar 3). 2. Mahasiswa program ekstensi mengharapkan mata kuliah diajarkan di akhir periode waktu. Oleh karena itu kepuasan mahasiswa ini diberi bobot (koefisien) yang kecil di akhir periode waktu dan bobot yang besar di awal periode waktu, sehingga mata kuliah ini memiliki peluang yang lebih besar untuk dijadwalkan di akhir periode waktu (Gambar 4).

10

Variabel-variabel yang digunakan: = himpunan periode waktu pada kelompok mahasiswa regular = himpunan periode waktu pada Jkx kelompok mahasiswa ekstensi Jw2 = himpunan periode waktu tatap muka 2 jam = himpunan mahasiswa regular Kr = himpunan mahasiswa ekstensi Kx Mls = himpunan mata kuliah yang bukan spesialisasi dari dosen = himpunan mata kuliah berpraktikum Mp Mw3 = himpunan mata kuliah dengan waktu tatap muka 3 jam = himpunan dosen yang tidak dapat Ltj mengajar pada periode waktu tertentu = himpunan dosen yang tidak mengajar Lts mata kuliah yang bukan spesialisnya = himpunan hari di mana dosen Itl berharap tidak mengajar = himpunan periode waktu di mana Jtl dosen berharap tidak mengajar Jm2 = himpunan periode waktu untuk mata kuliah dengan tatap muka 2 jam = himpunan ruangan perkuliahan Nm = himpunan ruangan praktikum Np Jkr

Gambar 3 Bobot suatu mata kuliah yang diharapkan diajarkan di awal periode waktu untuk mahasiswa program regular.

Gambar 4 Bobot suatu mata kuliah yang diharapkan diajarkan di akhir periode waktu untuk mahasiswa program ekstensi.

Selain itu, diperlukan pula pendefinisian suatu variabel keputusan:

⎧⎪ 1 ; jika di hari i pada periode j kelompok mahasiswa k diajar oleh dosen l untuk mata kuliah m x = ⎨ yang diselenggarakan di ruangan n ijklmn ⎪⎩ 0 ; selainnya

{

= 1 ; jika di hari i pada periode waktu j dosen l berharap tidak mengajar 0 ; selainnya

b ijl

Model bertujuan meminimumkan ketidakpuasan mahasiswa program regular, ekstensi, dan dosen terhadap penjadwalan

mata kuliah, maka fungsi objektif dari permasalahan ini adalah sebagai berikut:

min ∑∑ a1mj (∑∑∑∑ xijklmn ) +∑∑ a2 mj (∑∑∑∑ xijklmn ) +∑∑∑ bijl (∑∑∑ xijklmn ) m

j

i

k

l

n

m

j

dengan: a1mj = koefisien yang nilainya bersesuaian dengan ketidakpuasan mahasiswa program regular terhadap penjadwalan mata kuliah , a2mj = koefisien yang nilainya bersesuaian dengan ketidakpuasan mahasiswa program ekstensi terhadap penjadwalan mata kuliah. Kendala yang terkait adalah sebagai berikut:

1. Setiap mata kuliah yang diselenggarakan hanya dihadiri oleh satu kelompok.

i

k

l

n

i

j

l

∑∑∑∑ xijklmn ≤ 1, i

j

l

k

m

n

∀m, k

n

2. Paling banyak satu mata kuliah yang diselenggarakan di setiap periode waktunya. ∑∑∑ xijklmn ≤ 1, ∀i, j, m k

l

n

3. Paling banyak satu ruangan yang dipergunakan dalam suatu periode waktu perkuliahan. ∑∑∑ xijklmn ≤ 1, ∀i, j, n k

l

m

11

∑∑∑∑ xijklmn = 0,

4. Setiap periode waktu perkuliahan hanya dihadiri oleh satu kelompok. ∑∑∑ xijklmn ≤ 1, ∀i, j, k m

l

i

j

k

l

i

periode

waktu

selama

seminggu untuk mata kuliah m 6. Jadwal kuliah mata kuliah berpraktikum harus diselenggarakan sebelum jadwal praktikum.

i

j

k

n∈N m

l

−∑∑∑∑ i +1 j +1 k

l

∑

n∈N p

l

m

n

k

l

n

10. Setiap dosen tidak mengajarkan mata kuliah yang bukan spesialisasinya. ∑∑∑∑ xijklmn = 0, ∀m ∈ M ls , l ∈ Lts

∑∑∑∑ ∑ xijklmn / w(m ) i

∀j ∈ J k x , k ∈ K r

n

9. Mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam. ∑∑∑∑ xijklmn = 0, ∀j ∈ J m2 , m ∈ M w3

n

dengan: h( m) = total

m

8. Tidak ada mata kuliah yang diberikan sebelum pukul 17.00 WIB untuk program ekstensi. ∑∑∑∑ xijklmn = 0, ∀j ∈ J k r , k ∈ K x

n

5. Terpenuhinya jumlah periode waktu yang diperlukan untuk setiap mata kuliah. ∑∑∑∑∑ xijklmn = h(m), ∀m i

l

t

i

j

k

n

11. Beberapa dosen berharap tidak mengajar pada waktu tertentu. Jika dosen l berharap tidak mengajar pada hari i periode waktu j, maka b = 1 ijl 12. Semua variabel keputusan bernilai nol atau satu. xijklmn ∈ {0,1}, ∀i, j , k , l , m, n

xijklmn / w(m p ) > 0 , ∀m ∈ M p

dengan: w(mt ) = lamanya waktu kuliah untuk mata kuliah teori (dalam jam) w(m p ) = lamanya waktu kuliah untuk mata kuliah praktikum (dalam jam) 7. Tidak ada mata kuliah yang diberikan setelah pukul 17.00 WIB untuk program regular.

bijl ∈ {0,1}, ∀i, j , l

IV STUDI KASUS Masalah yang akan dicontohkan di sini adalah masalah penjadwalan perkuliahan semester lima di Akademi Manajemen Informatika dan Komunikasi Bina Sarana Informatika (AMIK) BSI Bogor. Hal yang perlu diperhatikan adalah kepuasan dosen dan mahasiswa dalam menyelesaikan kegiatan perkuliahan, ketersediaan ruangan yang terbatas serta preferensi dosen dan mahasiswa berbeda-beda, sehingga kegiatan perkuliahan ini dilakukan lima hari dalam seminggu yang setiap harinya dibagi menjadi dua waktu dengan sejumlah mata kuliah yang dijadwalkan. Pertama, kelompok mahasiswa yang tergolong dalam program regular

melaksanakan kegiatan perkuliahan pada pukul 08.00-16.00 WIB. Kedua, kelompok mahasiswa yang tergolong dalam program ekstensi melaksanakan kegiatan perkuliahan pada pukul 17.00-22.00 WIB. Di Departemen AMIK, telah ditentukan bahwa satu jam tatap muka di kelas dilakukan selama 45 menit. Untuk mata kuliah yang terdiri dari dua pertemuan yaitu kuliah dan praktikum, jadwal kuliah harus mendahului jadwal praktikum. Data yang diperlukan untuk memodelkan penjadwalan mata kuliah semester lima untuk mahasiswa program regular dan program ekstensi diberikan sebagai berikut:

Tabel 8 Daftar mata kuliah semester lima di AMIK Indeks (m)

Mata Kuliah (MK)

Kode MK

Banyaknya periode waktu

1

Pemrograman Visual FOXPRO (K)

735

1

2 jam kuliah

2

Pemrograman Visual FOXPRO (P)

735

1

3 jam praktikum

3

Web Programming (K)

153

1

2 jam kuliah

Keterangan

12

Lanjutan Tabel 8 Indeks (m)

Mata Kuliah (MK)

Kode MK

Banyaknya periode waktu

Keterangan

4 5

Web Programming (P) Teknologi Ilmu Komputer

153 142

1 1

3 jam praktikum 2 jam kuliah

6

Etika Profesi

572

1

2 jam kuliah

7

E-Commerce

430

1

2 jam kuliah

Tabel 10 Periode hari Indeks (i) Nama hari

Tabel 9 Ruangan yang tersedia Indeks (n) Ruangan 1

Ruang 301

1

Senin

2

Ruang 302

2

Selasa

3

Ruang 303

3

Rabu

4

LAB A-B

4

Kamis

5

Jumat

Tabel 11 Periode waktu Indeks (j) Periode 1

Tabel 12 Daftar kelompok Indeks (k) Program

Periode waktu 08.00-09.30

Periode 2

09.30-11.45

Periode 3

13.00-14.30

Periode 4

14.30-16.45

Periode 5

17.00-18.30

Periode 6

18.30-20.00

Periode 7

20.00-22.15

Kelompok

1

regular

1

2

ekstensi

2

Tabel 13 Daftar dosen Indeks (l)

Nama dosen

Mata kuliah spesialisasi dosen

Dosen berharap tidak mengajar Hari

Periode waktu

1 2

Djuanda Sampuna Sandra Setyaningsih

Web Programming (K) Teknologi Ilmu Komputer

Jumat Kamis

1, …, 7 1, …, 7

3

R. Eny Ernawan

Etika Profesi

Rabu

1, …, 7

4


Selasa

1, …, 7

-

-

6 7 8 9

Muhammad Tabrani Yanuar Massuki Amin Rina Indriany Isnaeni Eni Kustini Dio Pratama

Teknologi Ilmu Komputer Web Programming (K) Pemrograman Visual FOXPRO (K) Web Programming (P)

Kamis Jumat Rabu -

1, …, 7 1, …, 7 1, …, 7 -

10

Hermawan


Jumat

2

5

E-Commerce

13

Tujuan karya ilmiah ini adalah membuat penjadwalan terbaik dengan meminimumkan suatu fungsi objektif yaitu penjumlahan dari koefisien-koefisien yang menyatakan ketidakpuasan dari mahasiswa program regular, ekstensi, dan dosen terhadap penjadwalan mata kuliah. Penentuan koefisien (bobot) yang telah disebutkan pada bagian sebelumnya tidaklah mutlak harus seperti itu. Pada kasus ini hanyalah gambaran saja. Beberapa contoh grafik bobot mata kuliah yang mungkin dapat digunakan diperlihatkan sebagai berikut:

Gambar 6 Bobot mata kuliah Pemrograman Visual FOXPRO (P) yang diharapkan diajarkan di akhir periode waktu untuk mahasiswa program ekstensi. Untuk memformulasikan penjadwalan mata kuliah ini dalam model INLP, peubah xijklmn didefinisikan pada setiap periode hari i = 1, 2, …, 5, periode waktu j = 1, 2, …, 7, kelompok mahasiswa k = 1, 2, dosen l = 1, 2, …, 10, mata kuliah m = 1, 2, …, 7, ruangan n = 1, 2, …, 4. Sehingga masalahnya dapat diformulasikan dalam model INLP berikut:

Gambar 5 Bobot mata kuliah Pemrograman Visual FOXPRO (K) yang diharapkan diajarkan di awal periode waktu untuk mahasiswa program regular.

min ∑∑ a1mj (∑∑∑∑ xijklmn ) +∑∑ a2 mj (∑∑∑∑ xijklmn ) +∑∑∑ bijl (∑∑∑ xijklmn ) m

j

i

k

l

n

m

j

i

k

l

n

i

j

l

k

m

n

dengan kendala-kendala: 1. Setiap mata kuliah yang diselenggarakan hanya dihadiri oleh satu kelompok. ∑∑∑∑ xijklmn ≤ 1, ∀m, k i

j

l

n

2. Paling banyak satu mata kuliah yang diselenggarakan di setiap periode waktunya. ∑∑∑ xijklmn ≤ 1, ∀i, j, m k

l

n

3. Paling banyak satu ruangan yang dipergunakan dalam suatu periode waktu perkuliahan. ∑∑∑ xijklmn ≤ 1, ∀i, j, n k

l

m

4. Setiap periode waktu perkuliahan hanya dihadiri oleh satu kelompok. ∑∑∑ xijklmn ≤ 1, ∀i, j, k m

l

n

5. Terpenuhinya jumlah periode waktu yang diperlukan untuk setiap mata kuliah. ∑∑∑∑∑ xijklmn = h(m), ∀m i

j

k

l

n

untuk h(m) = 2, 2, 2, 2, 2, 2, 2. Misalkan banyaknya periode waktu yang diperlukan untuk mata kuliah Pemrograman Visual FOXPRO per minggu adalah 2, satu periode untuk program regular dan satu periode untuk program ekstensi.

∑∑∑∑∑ xijklmn = 2 i

j

k

l

n

6. Jadwal kuliah mata kuliah berpraktikum, harus diselenggarakan sebelum jadwal praktikum a. Program regular 4

3

∑∑∑∑∑∑ xijklmn / 2 j =1 k =1

i

4

m =1 n =1

l

3

−∑∑∑∑ ∑ ∑ xijklmn / 3 > 0 i =1 j =1 k =1

l

m=2 n=4

14

4

∑∑∑∑ xijklmn = 0

3

∑∑∑∑ ∑ ∑ xijklmn / 2 j =1 k =1

i

4

i

m = 3 n =1

l

3

−∑∑∑∑ ∑ ∑ xijklmn / 3 > 0 i =1 j =1 k =1

l

m=4 n=4

b. Program ekstensi 7

3

∑∑∑∑∑∑ xijklmn / 2 j =5 k = 2

i

4

m =1 n =1

l

6

l

7

3

j =5 k = 2

4

m = 3 n =1

l

6

−∑∑∑∑ ∑ ∑ xijklmn / 3 > 0 i =1 j = 5 k = 2

l

l

m

m=4 n=4

n

8. Tidak ada mata kuliah yang diberikan sebelum pukul 17.00 WIB untuk program ekstensi. Untuk k = 2, j = 1, 2, 3, 4

∑∑∑∑ xijklmn = 0 i

l

m

n

9. Mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam. Untuk m = 2, 4, dan j = 1, 3, 5, 6 ∑∑∑∑ xijklmn = 0 i

k

l

n

10. Setiap dosen tidak mengajarkan mata kuliah yang bukan spesialisasinya. Untuk l = 1, 7, dan m = 1, 2, 4, 5, 6, 7 ∑∑∑∑ xijklmn = 0 i

j

k

n

Untuk l = 2, 6, dan m = 1, 2, 3, 4, 6, 7 ∑∑∑∑ xijklmn = 0 i

j

k

n

Untuk l = 3, dan m = 1, 2, 3, 4, 5, 7 ∑∑∑∑ xijklmn = 0 i

j

k

n

Untuk l = 4, 8, dan m = 2, 3, 4, 5, 6, 7 ∑∑∑∑ xijklmn = 0 i

j

k

n

Untuk l = 5, dan m = 1, .., 6 ∑∑∑∑ xijklmn = 0 i

j

k

i

j

k

n

11. Beberapa dosen berharap tidak mengajar pada waktu tertentu. Untuk i = 5, dan l = 1, 7 ∑ bijl = 7

j

7. Tidak ada mata kuliah yang diberikan setelah pukul 17.00 WIB untuk program regular. Untuk k = 1, j = 5, 6, 7 ∑∑∑∑ xijklmn = 0 i

n

Untuk i = 4, dan l = 2, 6 ∑ bijl = 7

m=2 n=4

∑∑∑∑ ∑ ∑ xijklmn / 2 i

k

j

−∑∑∑∑ ∑ ∑ xijklmn / 3 > 0 i =1 j = 5 k = 2

j

Untuk l = 10, dan m = 1, 3, 4, 5, 6, 7 ∑∑∑∑ xijklmn = 0

n

Untuk l = 9, dan m = 1, 2, 3, 5, 6, 7

Untuk i = 3, dan l = 3, 8 ∑ bijl = 7 j

Untuk i = 2, dan l = 4 ∑ bijl = 7 j

Untuk i = 5, j = 2, dan l = 10 b = 1 ijl 12. Semua variabel keputusan bernilai nol atau satu. xijklmn ∈ {0,1}, ∀i, j , k , l , m, n bijl ∈ {0,1}, ∀i, j , l

Penyelesaian masalah penjadwalan mata kuliah Akademi Manajemen Informatika dan Komunikasi BSI Bogor pada karya ilmiah ini dilakukan dengan bantuan software LINGO 8.0 menggunakan metode branch and bound. Syntax program dan hasil komputasi dicantumkan pada Lampiran 3. Solusi yang didapat adalah solusi optimal dengan nilai fungsi objektifnya adalah 14080 didapatkan pada iterasi ke 1581. Waktu yang dibutuhkan untuk mendapatkan solusi tersebut sekitar 1 jam 26 menit 41 detik dengan menggunakan komputer Intel Pentium 4 processor komputer 1.34 GHz dengan RAM 1 GB. Hasil komputasi tidak semuanya dicantumkan, karena terlalu banyak. Hasil yang dicantumkan hanya untuk variabel keputusan x (jadwal perkuliahan) dan b (jadwal sebagian dosen tidak bisa mengajar) yang bernilai satu saja, sedangkan jadwal perkuliahan yang terbentuk ditunjukkan dalam Tabel 15 dan Tabel 16. Dari hasil yang didapatkan bisa dilihat persentase rata-rata ketidakpuasan dosen adalah 0%, ketidakpuasan mahasiswa program regular 1,43%, dan ketidakpuasan mahasiswa program ekstensi 0%.

15

Tabel 15 Jadwal kegiatan belajar mengajar untuk program regular Akademi Manajemen Informatika dan Komunikasi BSI Bogor. Hari Periode Waktu Mata kuliah Ruangan Dosen Senin

08.00-09.30

Web Programming (K)

303

09.30-11.45


301

Selasa

08.00-09.30 09.30-11.45

Etika Profesi Pemrograman Visual FOXPRO (P)

302 Lab A-B

Rabu

08.00-09.30

Teknologi Ilmu Komputer

09.30-11.45

Web Programming (P)

08.00-09.30

E-Commerce

Kamis

301 Lab A-B 301

Isnaeni Muhammad Tabrani R. Eny Ernawan Hermawan Sandra Setyaningsih Dio Pratama Yanuar Massuki Amin

Tabel 16 Jadwal kegiatan belajar mengajar untuk program ekstensi Akademi Manajemen Informatika dan Komunikasi BSI Bogor. Periode Hari Mata kuliah Ruangan Dosen Waktu Senin 18.30-20.00 Web Programming (K) 303 Isnaeni Sandra Rabu 17.00-18.30 Teknologi Ilmu Komputer 302 Setyaningsih Yanuar Massuki 18.30-20.00 E-Commerce 301 Amin Kamis 18.30-20.00 Web Programming (P) Lab A-B Dio Pratama Jumat

17.00-18.30


303

Eni Kustini

18.30-20.00

Etika Profesi

301

R. Eny Ernawan

20.00-22.15


Lab A-B

Hermawan

16

V SIMPULAN DAN SARAN 5.1 Simpulan Telah diperlihatkan bahwa masalah penjadwalan perkuliahan di Akademi Manajemen Informatika dan Komunikasi dapat dipandang sebagai masalah INLP. Penyelesaian masalah ini menggunakan software LINGO 8.0 yang berbasis metode branch and bound. Hasil yang diperoleh yaitu jadwal perkuliahan semester ganjil yang memenuhi kendala yang diperoleh pada iterasi ke 1589. Keuntungan penyelesaian masalah penjadwalan menggunakan INLP adalah memungkinkan pengguna untuk mengontrol atau menambahkan kendala dengan bebas. Sebagai contoh, jika menginginkan keadaan bahwa dosen tidak dapat mengajar dua mata

kuliah dalam waktu yang berurutan, maka kendala tersebut dapat ditambahkan. Begitu pula, tingkat kepuasan pilihan mata kuliah dan pilihan waktu dapat diubah dengan menyertakan ke dalam koefisien fungsi objektif. Perubahan yang lain sangat mungkin untuk dilakukan. 5.2 Saran Pada tulisan ini telah dibahas penjadwalan mata kuliah di BSI Bogor dengan penyederhanaan yaitu kelompok yang sedikit. Akan lebih baik lagi jika ada yang dapat menindaklanjuti penelitian ini dengan masalah yang lebih besar, kompleks, dan membuat software yang lebih umum digunakan dalam mengaplikasikan model ini.

DAFTAR PUSTAKA Bakir MA, Askop. C. 2008. A 0-1 integer programming approach to a university timetabling problem: Hattepe Journal of Mathematics and Statistics 37(1): 41-55. Ecker JG, Kupferschmid M. 1998. Introduction to Operation Research. New York: John Willey & Sons. Li D & Sun X. 2006. Nonlinear Integer Programming. China: Springer. Nash SG, Sofer A. 1996. Linear and Nonlinear Programming. New York: McGraw-Hill.

Garfinkel RS, Nemhauser GL. 1972. Integer Programming. New York: John Willey & Sons. Sharma S. 2006. Applied Nonlinear Programming. New Delhi: New Age International. Snyman Jan A. 2005. Practical Mathematical Optimization. New York: Springer. Winston WL. 2004. Operations Research Applications and Algorithms. 4th ed. Duxbury, New York.

17

LAMPIRAN

18

Lampiran 1. Syntax Program LINGO 8.0 dalam mencari nilai awal solusi fisibel Contoh 2 min v = 2 x1 + x2 2

2

2

terhadap x1 + x2

−

2 x1 x2 − 5 x1 − 2 x2

2

≤ 16,

x2>=0; end

Hasil yang diperoleh

5 x1 − 3 x2 ≥ −4,

Global optimal solution found at iteration: 66 Objective value: -12.13022

x1 ≥ 0 x2 ≥ 0 Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; x1>=0;

Variable X1 X2

Value 2.570395 3.064812

Reduced Cost 0.000000 0.000000

Row Slack or Surplus 1 -12.13022 2 0.000000 3 7.657538 4 2.570395

5

Dual Price -1.000000 0.1649634 0.000000 0.000000

3.064812

0.000000

Lampiran 2. Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Taklinear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh Subproblem (P(X1)) 2 2 min v = 2 x1 + x2 − 2 x1 x2 − 5 x1 − 2 x2 2

terhadap x1 + x2

2

Subproblem (P(X2)) 2 2 min v = 2 x1 + x2 − 2 x1 x2 − 5 x1 − 2 x2 2

≤ 16,

terhadap x1 + x2

5 x1 − 3 x2 ≥ −4,

2

≤ 16,

5 x1 − 3 x2 ≥ −4,

x1 ≥ 0

x1 ≥ 0

x2 ∈ [0, 2]

x2 ∈ [2, 4]

Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; x1>=0; @BND (0,x2,2); end

Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=0; @BND (2,x2,4); end



Global optimal solution found at iteration: 60 -10.12500 Objective value:

Global optimal solution found at iteration: 59 Objective value: -12.13022

Variable X1 X2

Value 2.249999 2.000000

Reduced Cost 0.000000 0.000000

Row Slack or Surplus Dual Price 1 -10.12500 -1.000000 2 6.937503 0.000000 3 9.249997 0.000000 4 2.249999 0.000000

Variable X1 X2

Value 2.570395 3.064812


Reduced Cost 0.000000 0.000000 Dual Price -1.000000 0.1649634 0.000000 0.000000

19

X1 X2

¾ Pencabangan subproblem P(X1) Subproblem ( P ( X 11 ) ) min v = 2 x1 + x2 2

terhadap

2 x1

2

+ x2

−

2 x1 x2 − 5 x1 − 2 x2

2

Row Slack or Surplus 1 -10.00000 2 8.000000 3 8.000000

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [0,1]

Hasil yang diperoleh Global optimal solution found at iteration: 26 Objective value: -7.000000 Value 1.000000 2.000000


Reduced Cost -5.000001 -0.1000089E-05 Dual Price -1.000000 0.000000 0.000000

min v = 2 x1 + x2 2

terhadap

2

terhadap

2 x1

2

+ x2

−

Hasil yang diperoleh Global optimal solution found at iteration: 27 Objective value: -10.00000 Value

Reduced Cost

≤ 16,


Variable X1 X2

Value 2.249999 2.000000


¾

x2 ∈ [0, 2] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (1,x1,2); @BND (0,x2,2); end

2 x1 x2 − 5 x1 − 2 x2

Global optimal solution found at iteration: 30 -10.12500 Objective value:

≤ 16,

x1 ∈ [1, 2]

+ x2

−

2


2 x1 x2 − 5 x1 − 2 x2

2

2 x1

2

x1 ∈ [2, 3]

5 x1 − 3 x2 ≥ −4,

Variable

Dual Price -1.000000 0.000000 0.000000

5 x1 − 3 x2 ≥ −4,

Subproblem ( P ( X 21 ) ) min v = 2 x1 + x2

-1.000002 -2.000001

Subproblem ( P ( X 31 ) )


Variable X1 X2

2.000000 2.000000

Reduced Cost 0.000000 -2.500000 Dual Price -1.000000 0.000000 0.000000

Pencabangan subproblem P ( X 31 )

Subproblem ( P ( X 13.1 ) ) min v = 2 x1 + x2 2

terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [2, 3] x2 ∈ [0,1] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (2,x1,3);

20

@BND (0,x2,1); end

Hasil yang diperoleh Global optimal solution found at iteration: 6 Objective value: -7 Variable X1 X2

Value 2.000000 1.000000


Subproblem ( P ( X min v = 2 x1 + x2 2

terhadap

2 x1

2

+ x2

3.2 1

−

2


))

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [2, 3] x2 ∈ [1, 2] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (2,x1,3); @BND (1,x2,2); end Hasil yang diperoleh Global optimal solution found at iteration: 9 -10.12500 Objective value: Variable X1 X2

Value 2.249999 2.000000



Subproblem ( P ( X 14 ) ) min v = 2 x1 + x2 2

2

2

terhadap x1 + x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [3, 4] x2 ∈ [0, 2] Syntax program pada LINGO 8.0

!Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5*(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (3,x1,4); @BND (0,x2,2); end

Hasil yang diperoleh Global optimal solution found at iteration: 26 -9.00000 Objective value: Variable X1 X2

Value 3.000000 2.000000


Reduced Cost -3.000003 -4.000001 Dual Price -1.000000 0.000000 0.000000

¾ Pencabangan subproblem P(X2) Subproblem ( P ( X 21 ) ) min v = 2 x1 + x2 2

terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [0,1] x2 ∈ [2, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (0,x1,1); @BND (2,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 31 Objective value: -7.000000 Variable Value Reduced Cost X1 1.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 -7.000000 -1.000000 2 11.00000 0.000000 3 3.000000 0.000000

21

Subproblem ( P ( X 22 ) ) min v = 2 x1 + x2 2

terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x2 ∈ [2, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (1,x1,2); @BND (2,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 40 Objective value: -11.00000

Row 1 2 3

min v = 2 x1 + x2 2

Value 2.000000 3.333333 Slack or Surplus -11.00000 3.000004 5.000002

Reduced Cost -3.000001 0.000000 Dual Price -1.000000 0.000000 0.000000

terhadap

2

2

2

terhadap x1 + x2

−

2

x2 ∈ [2, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (2,x1,3); @BND (2,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 59 Objective value: -12.13022 Variable X1 X2

Value 2.570395 3.064812

Reduced Cost 0.000000 0.000000

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

x2 ∈ [2, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (3,x1,4); @BND (2,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 27 Objective value: -11.16601 Variable X1 X2

Value 3.000000 2.645751

Row 1 2 3

≤ 16,

x1 ∈ [2, 3]

+ x2

−

2

x1 ∈ [3, 4]

2 x1 x2 − 5 x1 − 2 x2

5 x1 − 3 x2 ≥ −4,

2 x1

2

5 x1 − 3 x2 ≥ −4,

Subproblem ( P ( X 23 ) ) min v = 2 x1 + x2

Dual Price -1.000000 0.1649634 0.000000 0.000000

Subproblem ( P ( X 24 ) )

x1 ∈ [1, 2]

Variable X1 X2


¾

Reduced Cost 4.779646 0.000000

Slack or Surplus Dual Price -11.16601 -1.000000 0.000000 0.5118575 11.06275 0.000000

Pencabangan subproblem ( P ( X 22 ) )


terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [1, 2] x2 = [2, 3] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (1,x1,2); @BND (2,x2,3); end Hasil yang diperoleh

22

Global optimal solution found at iteration: 28 Objective value: -11.00000 Variable X1 X2 Row 1 2 3


Reduced Cost -3.000000 0.1499245E-05 Dual Price -1.000000 0.000000 0.000000


2

2

terhadap x1 + x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [1, 2] x2 ∈ [3, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (1,x1,2); @BND (3,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 31 Objective value: -11.00000 Variable X1 X2 Row 1 2 3

¾


Reduced Cost -3.000000 0.1499245E-05 Dual Price -1.000000 0.000000 0.000000

Percabangan subproblem ( P ( X 23 ) )


terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [2, 3] x2 ∈ [2, 3] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala;

(x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (2,x1,3); @BND (2,x2,3); end

Hasil yang diperoleh Global optimal solution found at iteration: 38 Objective value: -12.10326 Variable X1 X2

Value 2.645751 3.000000

Reduced Cost 0.000000 0.000000

Row Slack or Surplus Dual Price 1 -12.10326 -1.000000 2 0.7880408E-01 0.000000 3 0.000000 8.228757


terhadap

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4, x1 ∈ [2, 3] x2 ∈ [3, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (2,x1,3); @BND (3,x2,4); end Hasil yang diperoleh Global optimal solution found at iteration: 39 Objective value: -12.13022 Variable Value Reduced Cost X1 2.570395 0.3352949E-07 X2 3.064812 0.000000 Row Slack or Surplus Dual Price 1 -12.13022 1.000000 2 0.1649634 0.000000 3 0.000000 7.657538

23

¾

Percabangan subproblem ( P ( X 24 ) )


2 x1

terhadap

2

+ x2

−

2


2 x1 x2 − 5 x1 − 2 x2

terhadap

≤ 16,

2 x1

2

+ x2

−

2

2 x1 x2 − 5 x1 − 2 x2

≤ 16,

5 x1 − 3 x2 ≥ −4,

5 x1 − 3 x2 ≥ −4,

x1 ∈ [3, 4]

x1 ∈ [3, 4] x2 ∈ [2, 3] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (3,x1,4); @BND (2,x2,3); end

x2 ∈ [3, 4] Syntax program pada LINGO 8.0 !Fungsi Objektif; min=2*(x1)^2+(x2)^22*(x1)*(x2)-5(x1)-2*(x2); !Kendala; (x1)^2+(x2)^2<=16; 5*(x1)-3*(x2)>=-4; @BND (3,x1,4); @BND (3,x2,4); end Hasil yang diperoleh

Hasil yang diperoleh Global optimal solution found at iteration: 28 Objective value: -11.16601 Variable X1 X2 Row 1 2 3

Value 3.000000 2.645751

Reduced Cost 4.779646 0.000000

Slack or Surplus Dual Price -11.16601 -1.000000 0.000000 0.5118575 11.06275 0.000000

Lampiran 3 Program untuk menyelesaikan masalah penjadwalan kegiatan belajar mengajar di Akademi Manajemen Informatika dan Komunikasi BSI Bogor. SETS: HARI/HR1..HR5/; PERIODE_WAKTU/PW1..PW7/; KELOMPOK/K1,K2/; DOSEN/L1..L10/; MATA_KULIAH/MK1..MK7/:H; RUANGAN/R1..R4/; LINKS(HARI,PERIODE_WAKTU,KELOMPOK,DOSEN,MATA_KULIAH,RUANGAN):X; LINKS1(HARI,PERIODE_WAKTU,DOSEN):B; LINKS2(MATA_KULIAH,PERIODE_WAKTU):A1,A2; ENDSETS DATA: A1=

0 80 100 1000 1000 1000 0 1000 80 1000 1000 80 1000 1000 0 1000 0 1000 80 1000 20 1000 100 1000 1000

1000 1000 1000 1000 1000

1000 1000 1000 1000 1000

24

0 0

1000 60 1000 1000 1000 1000 1000 100 1000 1000 1000 1000

; A2=

1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 60 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 80 1000 1000 1000 1000 100

0 1000 0 1000 0 0 0

1000 0 1000 0 1000 1000 1000

; H=2 2 2 2 2 2 2; ENDDATA !FUNGSI OBJEKTIF; MIN=@SUM(LINKS(I,J,K,L,M,N):X*A1(M,J))+@SUM(LINKS(I,J,K,L,M,N):X*A 2(M,J))+@SUM(LINKS(I,J,K,L,M,N):X*@SUM(LINKS1(i,j,l):B)); !KENDALA; !1. Setiap satu mata kuliah yang diselenggarakan hanya dihadiri oleh satu kelompok; @FOR(MATA_KULIAH(M):@FOR(KELOMPOK(K):@SUM(PERIODE_WAKTU(J):@SUM(HA RI(I):@SUM(DOSEN(L):@SUM(RUANGAN(N):X(I,J,K,L,M,N)))))<=1));

!2. Paling banyak satu mata kuliah yang diselenggarakan di setiap periode waktunya; @FOR(MATA_KULIAH(M):@FOR(PERIODE_WAKTU(J):@FOR(HARI(I):@SUM(KELOMP OK(K):@SUM(DOSEN(L):@SUM(RUANGAN(N):X(I,J,K,L,M,N))))<=1))); !3. Paling banyak satu ruangan yang dipergunakan dalam suatu periode waktu perkuliahan; @FOR(HARI(I):@FOR(PERIODE_WAKTU(J):@FOR(RUANGAN(N):@SUM(KELOMPOK(K ):@SUM(DOSEN(L):@SUM(MATA_KULIAH(M):X(I,J,K,L,M,N))))<=1))); !4. Setiap periode waktu prkuliahan hanya dihadiri oleh satu kelompok; @FOR(KELOMPOK(K):@FOR(PERIODE_WAKTU(J):@FOR(HARI(I):@SUM(DOSEN(L): @SUM(MATA_KULIAH(M):@SUM(RUANGAN(N):X(I,J,K,L,M,N))))<=1))); !5. Terpenuhinya jumlah periode waktu yang dperlukan untuk masing-masing mata kuliah.; @FOR(MATA_KULIAH(M):@SUM(RUANGAN(N):@SUM(DOSEN(L):@SUM(KELOMPOK(K) :@SUM(PERIODE_WAKTU(J):@SUM(HARI(I):X(I,J,K,L,M,N))))))=H(M)); !6. Jadwal kuliah pada mata kuliah berpraktikum harus diselenggarakan sebelum jadwal praktikum. Pemrograman visual FOXPRO kelas regular; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#LE#4:@SUM(KELOMPOK(K)|K#EQ#1: @SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#1:@SUM(RUANGAN(N)|N#LE#3:(X (I,J,K,L,M,N))/2))))))@SUM(HARI(I)|I#LE#4:@SUM(PERIODE_WAKTU(J)|J#LE#3:@SUM(KELOMPOK(K)| K#EQ#1:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#2:@SUM(RUANGAN(N)|N# EQ#4:(X(I+1,J+1,K,L,M,N))/3))))))>0; !WEB PROGRAMMING; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#LE#4:@SUM(KELOMPOK(K)|K#EQ#1: @SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#3:@SUM(RUANGAN(N)|N#LE#3:(X (I,J,K,L,M,N))/2))))))@SUM(HARI(I)|I#LE#4:@SUM(PERIODE_WAKTU(J)|J#LE#3:@SUM(KELOMPOK(K)| K#EQ#1:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#4:@SUM(RUANGAN(N)|N# EQ#4:(X(I+1,J+1,K,L,M,N))/3))))))>0;

25

!Pemrograman visual FOXPRO kelas ekstensi; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#LE#7#AND#J#GE#5:@SUM(KELOMPOK (K)|K#EQ#2:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#1:@SUM(RUANGAN(N )|N#LE#3:(X(I,J,K,L,M,N))/2))))))@SUM(HARI(I)|I#LE#4:@SUM(PERIODE_WAKTU(J)|J#LE#6#AND#J#GE#5:@SUM(K ELOMPOK(K)|K#EQ#2:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#2:@SUM(RU ANGAN(N)|N#EQ#4:(X(I+1,J+1,K,L,M,N))/3))))))>0; !WEB PROGRAMMING; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#LE#7#AND#J#GE#5:@SUM(KELOMPOK (K)|K#EQ#2:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#3:@SUM(RUANGAN(N )|N#LE#3:(X(I,J,K,L,M,N))/2))))))@SUM(HARI(I)|I#LE#4:@SUM(PERIODE_WAKTU(J)|J#LE#6#AND#J#GE#5:@SUM(K ELOMPOK(K)|K#EQ#2:@SUM(DOSEN(L):@SUM(MATA_KULIAH(M)|M#EQ#4:@SUM(RU ANGAN(N)|N#EQ#4:(X(I+1,J+1,K,L,M,N))/3))))))>0;

!7. Tidak ada mata kuliah yang diberikan setelah pukul 17.00 WIB untuk program regular.; @FOR(KELOMPOK(K)|K#EQ#1:@FOR(PERIODE_WAKTU(J)|J#LE#7#AND#J#GE#5:@S UM(HARI(I):@SUM(DOSEN(L):@SUM(MATA_KULIAH(M):@SUM(RUANGAN(N):X(I,J ,K,L,M,N)))))=0)); !8.Tidak ada mata kuliah yang diberikan sebelum pukul 17.00 WIB untuk program ekstensi.; @FOR(KELOMPOK(K)|K#EQ#2:@FOR(PERIODE_WAKTU(J)|J#le#4:@SUM(HARI(I): @SUM(DOSEN(L):@SUM(MATA_KULIAH(M):@SUM(RUANGAN(N):X(I,J,K,L,M,N))) ))=0));

!9.Mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#EQ#1:@SUM(KELOMPOK(K):@SUM(DO SEN(L):@SUM(MATA_KULIAH(M)|M#EQ#2:@SUM(RUANGAN(N):X(I,J,K,L,M,N)+X (I,J+2,K,L,M,N)+X(I,J+4,K,L,M,N)+X(I,J+5,K,L,M,N)))))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J)|J#EQ#1:@SUM(KELOMPOK(K):@SUM(DO SEN(L):@SUM(MATA_KULIAH(M)|M#EQ#4:@SUM(RUANGAN(N):X(I,J,K,L,M,N)+X (I,J+2,K,L,M,N)+X(I,J+4,K,L,M,N)+X(I,J+5,K,L,M,N)))))))=0;

!10.Setiap dosen tidak mengajarkan mata kuliah yang bukan spesialisasinya.; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#1:@SUM(MATA_KULIAH(M)|M#NE#3:@SUM(RUANGAN(N):X(I,J,K,L,M,N)+X (I,J,K,L+6,M,N)))))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#2:@SUM(MATA_KULIAH(M)|M#NE#5:@SUM(RUANGAN(N):X(I,J,K,L,M,N)+X (I,J,K,L+4,M,N)))))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#3:@SUM(MATA_KULIAH(M)|M#NE#6:@SUM(RUANGAN(N):X(I,J,K,L,M,N))) ))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#4:@SUM(MATA_KULIAH(M)|M#LT#8#AND#M#GT#1:@SUM(RUANGAN(N):X(I,J ,K,L,M,N)+X(I,J,K,L+4,M,N)))))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#5:@SUM(MATA_KULIAH(M)|M#LT#7#AND#M#GE#1:@SUM(RUANGAN(N):X(I,J ,K,L,M,N)))))))=0;

26

@SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#9:@SUM(MATA_KULIAH(M)|M#NE#4:@SUM(RUANGAN(N):X(I,J,K,L,M,N))) ))))=0; @SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(KELOMPOK(K):@SUM(DOSEN(L)| L#EQ#10:@SUM(MATA_KULIAH(M)|M#NE#2:@SUM(RUANGAN(N):X(I,J,K,L,M,N)) )))))=0;

!11.Beberapa dosen berharap tidak mengajar pada waktu tertentu.; @FOR(HARI(I)|I#EQ#5:@FOR(DOSEN(L)|L#EQ#1#AND#L#EQ#7:@SUM(PERIODE_W AKTU(J):B(I,J,L))=7)); @FOR(HARI(I)|I#EQ#4:@FOR(DOSEN(L)|L#EQ#2#AND#L#EQ#6:@SUM(PERIODE_W AKTU(J):B(I,J,L))=7)); @FOR(HARI(I)|I#EQ#3:@FOR(DOSEN(L)|L#EQ#3#AND#L#EQ#8:@SUM(PERIODE_W AKTU(J):B(I,J,L))=7)); @FOR(HARI(I)|I#EQ#2:@FOR(DOSEN(L)|L#EQ#4:@SUM(PERIODE_WAKTU(J):B(I ,J,L))=7)); B(5,2,10)=1; !INTEGER CONDITION TO X, B; @FOR(LINKS(I,J,K,L,M,N):@BIN(X)); @FOR(LINKS1(I,J,L):@BIN(B)); END Local optimal solution found at iteration: Objective value: Variable Value X( HR1, PW1, K1, L7, MK3, X( HR1, PW2, K1, L4, MK1, X( HR1, PW6, K2, L7, MK3, X( HR2, PW1, K1, L3, MK6, X( HR2, PW2, K1, L10, MK2, X( HR3, PW1, K1, L2, MK5, X( HR3, PW2, K1, L9, MK4, X( HR3, PW5, K2, L2, MK5, X( HR3, PW6, K2, L5, MK7, X( HR4, PW1, K1, L5, MK7, X( HR4, PW6, K2, L9, MK4, X( HR5, PW5, K2, L8, MK1, X( HR5, PW6, K2, L3, MK6, X( HR5, PW7, K2, L10, MK2, Row 1 2 3 4 5 6 7 8 9 . . .

Slack or Surplus 14080.00 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

R3) R1) R3) R2) R4) R1) R4) R2) R1) R1) R4) R3) R1) R4)

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

Dual Price -1.000000 0.000000 0.000000 0.000000 0.3765254E-05 0.000000 0.000000 0.000000 0.000000

1589 14080.00 0.000000 80.00000 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

493 0.000000 494 0.000000 495 0.000000 496 0.000000 497 0.000000 498 0.000000 499 0.000000 Variable B( HR2, PW1, L4) B( HR2, PW2, L4) B( HR2, PW3, L4) B( HR2, PW4, L4) B( HR2, PW5, L4) B( HR2, PW6, L4) B( HR2, PW7, L4) B( HR3, PW1, L3) B( HR3, PW2, L3) B( HR3, PW3, L3) B( HR3, PW4, L3) B( HR3, PW5, L3) B( HR3, PW6, L3) B( HR3, PW7, L3) B( HR3, PW1, L8) B( HR3, PW2, L8) B( HR3, PW3, L8) B( HR3, PW4, L8) B( HR3, PW5, L8) B( HR3, PW6, L8) B( HR3, PW7, L8) B( HR4, PW1, L2) B( HR4, PW2, L2) B( HR4, PW3, L2) B( HR4, PW4, L2) B( HR4, PW5, L2) B( HR4, PW6, L2) B( HR4, PW7, L2) B( HR5, PW1, L7) B( HR5, PW2, L7) B( HR5, PW3, L7) B( HR5, PW4, L7) B( HR5, PW5, L7) B( HR5, PW6, L7) B( HR5, PW7, L7) B( HR5, PW2, L10)

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

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

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

28

PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor ERLIYANA

Recommend Documents