PEMECAHAN MASALAH PROGRAM TAK LINIER INTEGER CAMPURAN TAK KONVEKS DENGAN STRATEGI KENDALA AKTIF
DISERTASI
Oleh
HARDI TAMBUNAN 108110003/ ILMU MATEMATIKA
PROGRAM STUDI DOKTOR ILMU MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
PEMECAHAN MASALAH PROGRAM TAK LINIER INTEGER CAMPURAN TAK KONVEKS DENGAN STRATEGI KENDALA AKTIF
DISERTASI
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Doktor dalam Program Studi Doktor Ilmu Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh HARDI TAMBUNAN 108110003/ Ilmu Matematika
PROGRAM STUDI DOKTOR ILMU MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
Judul Disertasi
: PEMECAHAN MASALAH PROGRAM TAK LINIER INTEGER CAMPURAN TAK KONVEKS DENGAN STRATEGI KENDALA AKTIF
Nama Mahasiswa
: Hardi Tambunan
Nomor Induk Mahasiswa : 108110003 Program Studi
: Doktor Ilmu Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Promotor
(Prof. Dr. Saib Suwilo, M.Sc) Co Promotor
Ketua Program Studi
(Prof. Dr. Herman Mawengkang)
Tanggal lulus : 28 Oktober 2015
(Prof. Dr. Tulus, M.Si) Co Promotor
Dekan
(Dr. Sutarman, M.Sc)
Telah diuji pada: Tanggal 28 Oktober 2015
PANITIA PENGUJI DISERTASI Ketua : Prof . Dr. Herman Mawengkang Anggota: 1. Prof . Dr. Saib Suwilo, M. Sc 2. Prof . Dr. Tulus, M. Si 3. Prof . Dr. Opim Salim Sitompul, M. Sc 4. Prof . Dr. Anton Abdulbasah Kamil
PERNYATAAN Saya menyatakan dengan sebenar - benarnya bahwa segala pernyataan dalam disertasi saya yang berjudul:
PEMECAHAN MASALAH PROGRAM TAK LINIER INTEGER CAMPURAN TAK KONVEKS DENGAN STRATEGI KENDALA AKTIF Merupakan gagasan atau hasil penelitian disertasi saya dengan pembimbingan para komisi pembimbing, kecuali yang ditunjukkan rujukannya. Disertasi ini belum pernah diajukan untuk memperoleh gelar pada program sejenis di Perguruan Tinggi lainnya. Semua data dan informasi yang digunakan telah dinyatakan secara jelas dan dapat diperiksa kebenarannya. Medan, 28 Oktober 2015 Penulis,
Hardi Tambunan
ABSTRAK Program tak linier integer campuran (Mixed integer nonlinear programming (MINLP)) mengacu kepada program matematika dengan variabel kontinu dan diskrit, dan ketidaklineran dalam fungsi objektif dan kendala. Dalam disertasi ini dipaparkan strategi kendala aktif untuk memperoleh solusi integer layak dari suatu kelas pada masalah MINLP tak konveks dengan struktur dan subset variabel terbatas dan diasumsikan variabel diskrit terpisah dari variabel-variabel kontinu. Pemecahan masalah digunakan suatu strategi untuk menge- luarkan variabel nonbasic dari batas-batasnya dengan kombinasi kendala aktif dan konsep variabel superbasic. Strategi ini digunakan untuk mendorong variabel basis non-integer yang tepat bergerak ke sekitar titik-titik integer. Implementasi dari algoritma yang dibuat berhasil untuk tes masalah proses sistem sintesis. Kata Kunci: Program tak Linier, kendala aktif, solusi integer.
i
ABSTRACT Mixed integer nonlinear programming (MINLP) refers to mathematical programming with continuous and discrete variables and nonlinearities in the objective function and constraints. This dissertation has presented active constraints trategy for achieving integer feasible solution from a class of non-convex mixedinteger nonlinear programming problems has a structure characterized by a subset of variables restricted to assume discrete values, which are linear and separable from the continuous variables. Solving the problem used a strategy of releasing nonbasic variables from their bounds, combined with the active constraint and the notion of superbasic variable. This strategy is used to force the appropriate noninteger basic variables to move to their neighbourhood integer points. Successful implementation of these algorithms was achieved on a process system synthesis problem test. Keywords: Non-linear programming, active constraints, integer solution
ii
KATA PENGANTAR
Puji dan syukur penulis panjatkan kehadirat Tuhan Yang Maha Kuasa atas berkat dan anugerah-Nya, sehingga penulis dapat menyelesaikan disertasi dengan judul: Pemecahan Masalah Program Tak Linier Integer Campuran Tak Konveks dengan Strategi Kendala Aktif. Penyelesaian disertasi ini, penulis banyak mendapat arahan, bimbingan dan bantuan dari berbagai pihak baik material maupun moril. Pada kesempatan ini, penulis menyampaikan terimakasih yang tulus dan penghargaan setinggi-tingginya kepada:
1. Bapak Prof. Subhilhar, Ph.D selaku Pejabat Rektor Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Doktor Ilmu Matematika di Fakultas MIPA Universitas Suma- tera Utara. 2. Bapak Dr. Sutarman, M.Sc selaku Dekan Fakultas MIPA Universitas Sumatera Utara yang telah memberi kesempatan kepada saya menjalani pendidikan di Program Studi Doktor Ilmu Matematika. 3. Bapak Prof. Dr. Herman Mawengkang, selaku Promotor dan Ketua Program Studi Doktor Ilmu Matematika, Fakultas MIPA Universitas Sumatera Utara yang dengan ketulusan hati, kesabaran, iklas dan bijaksana dalam memberikan masukan dan arahan sehingga disertasi ini dapat selesai. iii
4. Bapak Prof. Dr. Saib Suwilo, M.Sc, selaku Co-Promotor dan Sekretaris Program Studi Doktor Ilmu Matematika, Fakultas MIPA Universitas Sumatera Utara, atas ketulusan hati dan kesabaran dalam memberikan masukan dan arahan sehingga dapat menyelesaikan disertasi ini. 5. Bapak Prof. Dr. Tulus, M.Si selaku Co-Promotor, atas ketulusan hati dan kesabaran dalam memberikan masukan dan arahan sehingga dapat menyelesaikan disertasi ini. 6. Bapak Prof. Dr. Opim Salim Sitompul, M.Sc selaku Penguji Luar Komisi atas semua masukan dan arahan mengenai isi disertasi ini. 7. Bapak Prof. Dr. Anton Abdulbasah Kamil selaku Penguji Luar Komisi atas semua masukan dan arahan mengenai isi disertasi ini. 8. Seluruh Staf Pengajar pada Program Studi Doktor Ilmu Matematika Fakultas MIPA Universitas Sumatera Utara yang telah memberikan ilmu yang sangat berharga selama masa perkuliahan. 9. Ibu Misiani, S.Si selaku Staf Administrasi Program Studi Doktor Ilmu Matematika Fakultas MIPA Universitas Sumatera Utara. 10. Buat sahabat-sahabatku mahasiswa angkatan 2010 Program Studi Doktor Ilmu Matematika Fakultas MIPA Universitas Sumatera Utara atas kerja sama yang baik selama perkuliahan.
iv
Penulis menyampaikan terima kasih dan rasa hormat kepada Ayahanda(Alm.) B.Tambunan dan Ibunda T Br Tobing serta Bapak S. Baringbing dan Ibu S. Br Sitorus yang selalu mendoakan dan memberikan semangat kepada penulis. Secara khusus, penulis menyampaikan terimakasih kepada Istriku tercinta Dra. Rosmiati Baringbing atas doa, pengertian dan dukungannya selama penulis mengikuti kuliah hingga penyelesaian disertasi ini, dan kepada anak-anakku tersayang dan yang kubanggakan; Toman Sony Tambunan, S.E, M.Si/N.L Hutagalung, S.E; Nico Tambunan, S.E; Luna Theresia Tambunan, S.E, M.Si/Leonard P. S Aruan, S.E; Wilson Raja Ganda Tambunan, S.H, M.H, dan Johannes Tuan Mulia Tambunan yang selalu memberi semangat. Akhir kata, semoga disertasi ini bermanfaat untuk pengembangan ilmu pengetahuan. Medan, 28 Oktober 2015 Penulis,
Hardi Tambunan
v
RIWAYAT HIDUP
Hardi Tambunan, Lahir di Tarutung pada tanggal 23 Juni 1957. Pendidikan dasar diselesaikan dari Sekolah Dasar Negeri Pardomuan-Aceh Tenggara pada tahun 1970. Kemudian melanjutkan ke SMP HKBP Lawe Desky, Aceh Tenggara dan lulus tahun 1973. Pendidikan Sekolah Menengah Atas lulus tahun 1976 dari SMA Tarutung, Tapanuli Utara. Selanjutnya, menempuh Pendidikan Tinggi di Institut Keguruan dan Ilmu Pendidikan (IKIP) Medan dan lulus Sarjana Muda Pendidikan Matematika tahun 1980 dan Sarjana Pendidikan Matematika lulus tahun 1983. Pada tahun 1999 memperoleh gelar Magister Pendidikan matematika dari Institut Keguruan dan Ilmu Pendidikan (IKIP) Surabaya. Studi S-3 dimulai tahun 2010 pada Program Studi Doktor Ilmu Matematika Fakultas MIPA Universitas Sumatera Utara. Pengangkatan pertama sebagai dosen pegawai negeri sipil yang dipekerjakan di Perguruan Tinggi Swasta melalui Kopertis Wilayah I dimulai tahun 1986. Saat ini bertugas sebagai dosen di Program Studi Pendidikan Matematika FKIP Universitaa Quality, Medan.
vi
DAFTAR ISI Halaman ABSTRAK
1
ABSTRACT
1
KATA PENGANTAR
1
RIWAYAT HIDUP
1
DAFTAR ISI
1
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
8
1.3 Tujuan Penelitian
9
1.4 Manfaat Penelitian
9
BAB 2 PROGRAM LINIER DAN TAK LINIER
10
2.1 Program Linier
10
2.2 Metode Pemecahan
11
2.2.1 Metode Grafik
11
2.2.2 Metode Simpleks
11
2.2.3 Metode Reduced Gradient
13
2.3 Program Tak Linier
15
2.3.1 Program Konveks
28
2.3.2 Program Tak Konveks
30
2.4 Metode Pemecahan
31
2.4.1 Line Search
31
2.4.2 Trust Region
32 vii
2.4.3 Penalty and Augmented Lagrangian
32
2.4.4 Active Set
33
BAB 3 PROGRAM LINIER INTEGER CAMPURAN
35
3.1 Program Linier Integer
35
3.2 Metode Pemecahan
36
3.2.1 Cabang dan Batas
36
3.2.2 Pemotongan Bidang
39
3.2.3 Neighbourhood Search
40
3.3 Program Linier Integer Campuran BAB 4 PROGRAM TAK LINIER INTEGER CAMPURAN
42 44
4.1 Model Program Tak Linier Integer Campuran
44
4.2 Metode Pemecahan
45
4.2.1 Cabang dan Batas
46
4.2.2 Generalized Benders Decomposition
48
4.2.3 Outer Approximation
50
4.2.4 Extended Cutting Plane
53
4.2.5 Hybrid algorithm
54
4.2.6 Feasibility Pump
54
4.2.7 Relaksasi Berdasarkan Heuristik
60
BAB 5 PROGRAM TAK LINER INTEGER CAMPURAN TAK KONVEKS
63
5.1 Model Program Tak Linier Integer Campuran Tak Konveks
63
5.2 Metode Pemecahan
64
5.2.1 Cabang dan Batas
68
viii
5.2.2 Feasibility Pump
74
5.2.3 Under Cover Heuristic
78
5.2.4 RECIPE
80
BAB 6 STRATEGI KENDALA AKTIF
88
6.1 Variabel Superbasic
88
6.2 Kendala
90
6.3 Kendala Aktif
91
BAB 7 PEMECAHAN MASALAH PROGRAM TAK LINER INTEGER CAMPURAN TAK KONVEKS DENGAN STRATEGI KENDALA AKTIF 7.1 Pemecahan Masalah
94 95
7.1.1 Pemecahan Masalah Program Tak Linier
95
7.1.2 Strategi Kendala Aktif
97
7.1.3 Algoritma Pemecahan Masalah
103
7.1.4 Konvergensi Algoritma Pemecahan Masalah
105
7.2 Mencari Solusi Integer
106
7.2.1 Pendekatan Dasar
106
7.2.2 Strategi Kendala Aktif
110
7.2.3 Algoritma Mencari Solusi Integer
116
7.2.4 Konvergensi Algoritma Mencari Solusi Integer
118
7.3 Hasil Komputasi
119
BAB 8 KESIMPULAN
123
8.1 Kesimpulan
123
8.2 Penelitian Lanjutan
123
DAFTAR PUSTAKA
124 ix
